Shadama: A Particle Simulation
Programming Environment for Everyone

Yoshiki Ohshima, Dan Amelang and Vanessa Freudenberg
HARC/Y Combinator Research

We present a prototype of a programming system called Shadama. Shadama is designed for writing programs that create, control and visualize large numbers of objects. The basic execution model follows the tradition of StarLogo and its "turtles and patches" abstraction. Turtles, Termites, and Traffic Jams: Explorations in Massively Parallel Microworlds
  This abstraction has been proven to be effective and easy to use. The primary goal of the language is to facilitate the writing of scientific simulations by students at the high school level.

The Shadama environment supports liveness. Once changes to the program are saved, the effect on the running simulation is immediate; there is no need to restart the simulation.

Shadama programs are run on the GPU by means of code translation to the OpenGL Shading Language. The OpenGL Shading Language   Program data resides entirely on the GPU, which enables high performance.

A prototype of Shadama can be found here. Be aware that Shadama requires WebGL 2 and is affected by the floating point precision provided by your graphics card. Thus, it only works on certain computer systems. From our experience, it seems to work better on computers with an AMD Radeon graphics card and on Chrome or Firefox browsers.

Introduction

The computing power available to us today is astounding. Achieving one teraflop of performance was a milestone for a building-sized supercomputer in the late '90s, but now we expect smart phones to reach this same milestone soon. Computing performance will only continue to increase in the future.

But what are people using this power for? Not to be critical, but people are generally more interested in watching cat videos and playing games than trying to invent self-piloting personal airplanes or discover the graviton. All joking aside, one of the big problems we face today is our struggle to advance science literacy, even within a technologically-advanced society. We need the next generation to embrace science more, not less.

We think now is a good time to redouble our efforts to provide environments where students and even professional programmers can more easily tap into the computing power that is available. To this end, we have been working on a prototype of a programming language intended for high school students to explore scientific concepts.

Science is about making the invisible visible. One notable example of an invisible yet important concept is molecules in a gas. We would like students to learn about this, not by rote memorization, but through actual experiments and model-building. With the help of computers, students can make a dynamic model and understand it more deeply. This kind of environment will help students construct knowledge by doing, in line with the constructivism philosophy of education.

A Science Experiment

Before introducing the Shadama programming environment, we first give an example of a physics experiment that could also be modeled and simulated on a computer.

This movie demonstrates a vacuum cannon. The cannon is a six foot PVC pipe connected to a vacuum pump. We put a ping pong ball inside the pipe, cover the ends with sturdy but breakable material (such as plastic plates), and pump the air out.

The pump reduces the pressure inside the tube to about 20% of full atmospheric pressure.

When the end near the ping pong ball is broken open by a box cutter, the air molecules that rush into the pipe move into the low pressure space and the ping pong ball is pushed out the other end. Our crude setup can accelerate the ball to a speed of over 200 meters per second (about 60% of the speed of sound). Others have built similar setups that can achieve supersonic speed.

An interesting point to understand is that it is just movement of molecules that is causing the ball to shoot out. It is not that the vacuum is sucking molecules into the pipe.

The invisible molecules that cause the ball to shoot out can be made “visible” in a sense not only through this physical experiment, but also through a computer simulation that reproduces the same phenomenon. Creating such simulations is the purpose of our programming environment.

Language Goals

We had the following goals when designing Shadama:

To make learning Shadama easy, we based our language on StarLogo, whose turtles and patches approach has proved intuitive to young learners. In addition, we expect students familiar with Scratch to learn Shadama easily because of similarites in how object behavior is programmed and how objects can sense values near them spatially.

To encourage openness, we designed Shadama to be capable of implementing complex behavior in the language itself, with as few primitives as possible. We think that a learning environment should be open in the sense that a student should be able to see, change and understand how the various parts of the system work. Although many sophisticated scientific software packages and simulation environments exist, they are presented as immutable black boxes, which limits understanding and stifles curiousity. When additional software support is required, it should be provided in the end-user's programming language, and it should be capable of modification within the end-user's environment.

To support large numbers of particles, we designed the language to execute on graphics hardware. Graphics processors today are capable of computing on massive amounts of data. Unfortunately, this requires a trade-off between ease of use and high performance because there are fundamental limitations in the execution model of today's graphics hardware. Although Shadama has some features to mitigate these limitations, certain behaviors cannot be implemented.

To support liveness, we designed the Shadama environment to show the effects of code changes immediately. Of course, a running simulation should not be updated for each and every key stroke. Instead, the user submits a batch of code changes for the environment to apply.

Shadama in Action

The following movie introduces our prototype programming environment through several examples. For details on the language, see the appendix. The script for the narration of the movie is included below. You can pause the movie at any time to scroll through and read the script.

Implementation

Shadama is built on web technologies, including WebGL 2.0 and OpenGL Shading Language version 3.0. Our code translator is written in Ohm Ohm: A library and language for building parsers, interpreters, compilers, etc. and generates vertex shader, fragment shader and JavaScript code from the Shadama program. All the values for a given breed and property are stored in a single OpenGL texture. These textures are created with the OpenGL type "R32F", to match their use as an array of floating-point scalar values. The values for a given patch and property are similarly represented.

Shadama static functions are translated to Javascript code that runs OpenGL shaders derived from the Shadama methods. For each method, a vertex shader is generated to fetch property values from textures and perform the computation required for that method. A generated fragment shader stores the property values back into textures, using the multiple render targets feature of OpenGL.

Previously, one of the authors implemented a particle system called Kedama as an extension of Etoys. Kedama: A GUI-Based Interactive Massively Parallel Particle Programming System.
Kedama screenshot
   Shadama can be considered an attempt to give the same idea new life. Kedama's target audience was middle school children, while Shadama's target audience is high school students.

The biggest inspiration for Shadama (and Kedama) was Resnick's StarLogo. As such, it provided the basis for the basic organization of objects in Shadama. However, StarLogo has certain features that Shadama does not, as mentioned in the introduction.

Based on Extempore, Swift et al. created a live programming environment for physics. Live Programming in Scientific Simulation
Extempore PIC demo screenshot
   This environment brings dynamic code swapping and interactive data inspection to a sophisticated and optimized particle-in-cell simulation engine. The spirit of this work is much in line with ours, although their environment uses a third-party engine that cannot be modified from this same environment. This is a reflection of their focus on empowering scientific researchers. Such users are already familiar with the concepts behind the simulation and value the tight interaction offered by this approach. While it is possible to rewrite parts of the third-party engine in Extempore, this is beyond the ability of most users, especially our target audience.

Nicky Case's simulation construction environment represents an interesting point in the design space. Simulating the World (in Emoji)
Simulation in Emoji screenshot   The system features a user-friendly design for creating many types of open-ended models. However, it is only designed to handle a few hundred particles and cells.

Programming the GPU from a high-level language is a hot topic. Object Support in an Array-based GPGPU Extension for Ruby   Researchers in this area aim for better performance through increasingly sophisticated compilation techniques and the use of the CUDA API to more directly access the GPU. Ease of use is given little consideration. The authors think that Shadama can occupy a unique position by striking a better balance between performance and ease of use.

Some languages for programming massively parallel particle simulations are based on visual programming blocks. StarLogo Nova is a notable example. StarLogo Nova: A Programming Environment For Students and Teachers to Create 3D Games and Simulations for Understanding Complex Systems Shadama is currently text-based because we feel that scientific simulations can be naturally expressed with concise text. However, we have not ruled out other possiblities for syntax, including a visual representation of the program.

Although many simulation environments such as Liquid Fun LiquidFun: A 2D Rigid-body and Fluid Simulation C++ Library for Games Based Upon Box2D
LiquidFun screenshot are available today, they do not provide an end-user language.

Conclusions and Future Work

We have presented an early prototype of a language in which users can make enlightening simulations and intricate visualizations. The liveliness of the environment encourages an exploratory style of programming that enables trying out different ideas quickly. We have also discovered that such an interactive and graphical environment can be motivating even as bugs appear because of the spectacular unintentional visual effects that are produced.

We are considering various improvements to the system. One major addition would be to fully support simulations in 3D, not just 2D. While computation in Shadama only uses scalar values and is agnostic to dimensionality, the primitives and concepts the system currently provides only work well for 2D applications. We will need new ideas to manage 3D spatial data.

We also plan to support more mathematical concepts, such as vectors and matrices. While first-time users may not initially have use for such abstractions, we would like them to eventually learn and use these powerful concepts. Ideally, the environment would gradually introduce the user to new, more difficult approaches.

We would like to conclude this paper by stressing the importance of education. Education raises our awareness and enables us to see our world from new perspectives. In this way, we are empowered with new approaches to solve problems. For the next generation to solve the challenges of the future, their science literacy is imperative. Our aim with Shadama is to leverage the power and ubiquity of computing devices to improve science literacy for high school students by providing an engaging, open environment in which to explore scientific concepts.

References

  1. The OpenGL Shading Language (Khronos OpenGL Registry)
  2. Ohm: A library and language for building parsers, interpreters, compilers, etc. (project page)
  3. Yoshiki Ohshima. Kedama: A GUI-based Interactive Massively Parallel Particle Programming System. In 2005 IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC’05), pages 91–98, Sept 2005.
  4. Ben Swift, Andrew Sorensen, Henry Gardner, Peter Davis, and Viktor K Decyk. Live Programming in Scientific Simulation. Supercomputing Frontiers and Innovations, 2(4):4–15, March 2015. (DOI)
  5. LiquidFun: A 2D Rigid-body and Fluid Simulation C++ Library for Games Based Upon Box2D (project page)
  6. Nicky Case. Simulating the World (in Emoji) (project page)
  7. Matthias Springer and Hidehiko Masuhara. Object Support in an Array-based GPGPU Extension for Ruby. In Proceedings of the 3rd ACM SIGPLAN International Workshop on Libraries, Languages, and Compilers for Array Programming, ARRAY 2016, pages 25–31, New York, NY, USA, 2016.
  8. StarLogo Nova: A Programming Environment For Students and Teachers to Create 3D Games and Simulations for Understanding Complex Systems (project page)

Appendix: A Primer for the Shadama Language

The Shadama language uses a turtles and patches abstraction, drawn from the tradition of StarLogo.

Breeds

Turtles are organized into "breeds". Each breed has its own set of properties. A breed is declared in a program with the "breed" statement. For example: 

breed MyBreed (x, y)

The above creates a breed of turtle called MyBreed, and declares that each turtle in the breed has individual properties x and y.

Currently, properties in Shadama can only be scalar floating-point numbers.

Methods provide turtle behavior. The def statement is used to define methods, as follows: 

def move() {
  this.x = this.x + 1;
  this.y = this.y + 1;
}

As expected, when this method is invoked on a turtle, the turtle's x and y properties are incremented by one.

Methods can only be invoked from static functions. Methods calls are made by first specifying a breed, then the method name. The method is applied to all turtles in the breed concurrently. For example: 

static step() {
  MyBreed.move();
}

The step function above calls the move method on all turtles of the MyBreed breed.

Shadama provides many built-in features made available through primitive methods:

Patches

A patch is a 2D set of cells that store values. Patches are fixed size, 512 × 512 by default. The following declares a patch: 

patch Field (nx, ny)

Each cell in this patch stores two values, nx and ny.

A patch can be manipulated by passing it as an argument to a method on a breed. As the method is executed for each turtle, turtles can access the patch cell nearest them. No other patch cells are available to them. For example: 

breed MyBreed (x, y, r, g, b, a)
patch Field (r, g, b, a)

def store(field) {
  field.r = this.r;
}

static setup() {
  MyBreed.fillImage("x", "y", "r", "g", "b", "a", anImage);
  MyBreed.store(Field);
}

The above declares a patch called Field which is used as an argument to store. When store is executed for each turtle in MyBreed, the turtle's r property is stored in the r property of the nearest cell in Field.

A turtle can read values from patch cells as well. For example: 

def load(field) {
   this.r = field.r;
}

When the above method is executed, each turtle reads the r property of the nearest patch cell and stores the value into its own r property.

Methods can receive multiple patches as arguments. For example: 

patch Field1 (nx, ny, r, g, b, a)
patch Field2 (nx, ny, r, g, b, a)
def transfer(f1, f2) {
  f2.r = f1.r;
  f2.a = f1.a;
}

The following code is also valid, and correctly swaps values between patches. 

def swap(f1, f2) {
  f2.r = f1.r;
  f1.r = f2.r
}

Local Variables

The var statement declares a local variable within a method. The scope of a local variables is the whole method, regardless of where in the method it is declared. In the same method, there can be no more than one declaration for a given variable name. This is in contrast to variable declarations in JavaScript. For example: 

def average() {
  var avg = (this.x + this.y) / 2.0;
  this.x = avg;
  this.y = avg;
}

The above code properly defines and uses a local variable called avg. However, the following code would raise an error because the variable diff is declared in two places: 

def gcd() {
  if (this.a > this.b) {
    var diff = this.a - this.b;
    this.a = diff;
  } else {
    var diff = this.b - this.a;
    this.b = diff;
  }

The variable declaration has to be manually hoisted, as follows: 

def gcd() {
  var diff;
  if (this.a > this.b) {
    diff = this.a - this.b;
    this.a = diff;
  } else {
    diff = this.b - this.a;
    this.b = diff;
  }

Static Function Variables

Static function variables are declared within static functions, also using the "var" statement. Static function variables are not available to methods, but are visible to all static functions. For example: 

static setup() {
  var begin = 1;
}

static loop() {
  if (begin) {
    begin = 0;
  }
}

The two static functions above refer to the same begin variable.

Shadama provides the following built-in static function variables:

Be aware that mouse event objects are JavaScript objects. Thus, they can't be passed to methods because methods can only take scalar arguments.

There is one additional variable called Display for invoking certain system primitives. For example: 

static loop() {
  Display.clear();
  MyPatch.draw();
}

The above code clears the canvas and then draws MyPatch by calling the draw primitive. Display has loadProgram, and clear.

Parallelism Considerations

It's possible for two or more nearby turtles to write into the same patch cell. Which value gets stored in the patch is non-deterministic.

Also, updates to turtle properties and patch properties are not visible until after the method is run. Consider the following method: 

def test() {
  if (this.r > 0) {
     this.r = 0;
  } else {
     this.r = 1;
  }
  this.b = this.r;
}

Even though the last line reads this.b = this.r;, the r property and b property will not be equal after the invocation. This is because the update to the r property seen earlier does not take effect until after the method call is finished. Thus, the b property will have the previous r value.

The properties this.b and this.r can have the same value through the following use of a local variable: 

def test() {
  var r = this.r;
  if (r > 0) {
     r = 0;
  } else {
     r = 1;
  }
  this.r = r;
  this.b = r;
}

A script can be started by calling start on it. Likewise, you can stop it stop, and execute it once with step.

Control Structures

The if statement is the only control structure that Shadama supports. Loops may be supported in a future version of Shadama because the OpenGL shader language version 3.0 does support variable-count loops.

Primitive Functions

There are a number of primitive functions that can be called from methods. Most of them actually result in a direct call to a GLSL built-in function. For example: 

def prims(x) {
  var c = cos(x);
  var s = step(0.5, x);
  var a = abs(x);
  var f = fract(x); // the fraction part of x

  this.r = c * s * a * f;
}

The above code uses several primitive functions to compute a contrived value which is then stored into the turtle's r property.

Method Binding

Methods are not defined for any particular breed, but a given method can only be applied to breeds that have the properties referenced in the method. For example: 

breed A (x, r)
breed B (x, y, r, g)
breed C (r)

def set() {
  this.r = 1;
  this.x = 0;
}

static test() {
  A.set();
  B.set();
}

The set method above can be called for both breed A and breed B. This is the not the case for breed C because it does not have an x property, which is referenced in set.

Limitations

The following are important limitations of the Shadama language.

Methods can not take breeds as arguments. For example, the following code is invalid: 

breed A (x, y)
breed B (x, y)

def hit(other) {
  var diff = other.x - this.x;
  ...
}

static step() {
  A.hit(B);
}

The step function passes breed B as an argument to the hit method, which is not allowed. Even if it were, it is not clear which turtle from breed B should be bound to the argument other.

Another limitation is that a given method can either update the turtle's properties or the patch's properties, but not both. For example, the following code is invalid: 

def test(field) {
  field.r = 1;
  this.r = 1;
}

This limitation arises from limitations in WebGL itself. Future versions of WebGL, and thus Shadama, may no longer have this restriction. In the meantime, a workaround is to split the method into two methods — one for updating the patch and one for updating the turtle. It is also possible that a future version of Shadama will automatically perform this code transformation.