Array Animation Language (AAL) is a small, statically-typed, imperative programming language designed for visualizing algorithms on arrays. It's also useful for visualizing the behavior of the call stack during execution of recursive algorithms (see the merge sort example program).

AAL programs are compiled to a special instruction set that describes how to animate them.

Included in the online version:

1. a JavaScript implementation of the compiler
2. an animation runtime to run the compiled programs using HTML5 Canvas

Keywords

array, def, while, if, else, int, string, bool, unit, tt, T, return

Types

The set of types is given by the following grammar:



Integers are 32 bits. unit is the singleton type with only one value: tt. Note that there is no char type -- only string.

Operators

Syntax

The syntax is mostly C-like with a few exceptions:

• Function definitions begin with the 'def' keyword. Type annotations are in ML style, and are required (no type inference).
• Currently, while loop bodies and branches of if/else statements must always be enclosed in curly braces.
• Function calls may be annotated with a type parameter using the '@' syntax. See the 'Parametric Polymorphism' section.
• Parentheses aren't required around control structure guard conditions.
  e.g., while (true) { ... } is equivalent to while true { ... }.

Semantics

Variables

All variables are stack-allocated. At the beginning of each function invocation (including the main), all of the function's formal parameters and local variables are allocated on the new stack frame and given appropriate initial values. The scope of a variable is the entire function in which it resides, no matter where it appears inside the function body.

Explicit variable declarations are not necessary (or even possible). Simply assigning a value to an identifier will declare a variable with the type of the value being assigned (similar to Python, but statically typed). Variables can contain values of the basic types (bool, int, string) or arrays.

Arrays

Arrays are homogeneous. That is, all values in an array must have the same type. Arrays can, however, contain other arrays. Arrays be be created either with the array literal syntax (e.g., A = [a1, ..., an]) or with the built-in create function. Creating an empty array using create is the only situation in which explicit type parameter annotation is strictly necessary.

User-defined Functions

All function declarations must be at the beginning of the program. Arguments are passed by value by default (a copy is made on the newly allocated stack frame) but they can be passed by reference by appending '&' at the end of the type annotation. Here is an example function that takes an int parameter by reference and increments it:

Functions with a return type other than unit must terminate every control flow path with a return command. Explicitly returning the unit value tt from functions with return type unit is allowed, but not required. When a function is called as a standalone command (its return value is not being used) its return type must be unit.

All functions may call themselves or other functions (mutually) recursively.

Parametric Polymorphism

The special type T can be used in place of actual types in the formal parameters and return types of function definitions. This provides a limited form of parametric polymorphism (there can only be one type parameter per function definition). A polymorphic function will typecheck successfully if its polymorphic arguments are used in a way that is compatible with all types (the intrinsic functions listed below are polymorphic and thus compatible with all types).

Usually, at the call site of a polymorphic function, the types of the arguments can be used to infer which type to instantiate T with. If there are no such arguments, then the actual type for T must be explicitly provided using the @ syntax. See the create intrinsic function below.

Intrinsic Functions

The following functions are built-in:

Implementation

The "compiler" is written entirely in OCaml and uses OCamllex, Menhir, and Batteries. It's maybe a bit disingenuous to call it a compiler, since it's really just an AST interpreter that evaluates the program and produces animation step instructions along the way. It's compiled to JavaScript using js_of_ocaml and runs in an HTML5 Web Worker.

The code editor is Ace. The animation runtime is written in JavaScript using victor.js, sexp, and a custom thin layer over HTML5 Canvas. Bootstrap provides CSS.