CSE Machine

Overview

TODO: Add control and stash information.

This tool generates drawings of the control, stash and environment models of a program at a particular point in its execution. The model aims to follow as closely as possible the structure defined in the official module textbook.

To run the CSE Machine, click on the "CSE Machine" tab and run the program to view the models.

Data structures such as arrays and pairs are visualised using box-and-pointer notation. The box for a pair has two parts, the left containing the head and the right containing the tail. The box for an array comprises multiple parts, each representing the corresponding index in the array.

We followed certain heuristics when creating the diagram:

• Frames assigned an (x, y)-coordinate with the y-coordinate being its depth from the global frame, and the x-coordinate representing the order of creation of each frame, where x-coordinate of newer frames ≥ x-coordinate of older frames.
• Function objects and arrays are placed to the right of its enclosing environment frame.
  • Function objects and arrays are drawn next to the environment they are created in.
  • Function objects can be hovered over to view the tooltips containing its parameters and function body.
  • Arrays can be hovered over to view the indexes of each array unit.
  • In print mode, all function tooltips and array indexes are shown, with function tooltips being shortened to fit inside the reduced vertical space.

Technical Details

The visualiser works closely with JS Slang. Whenever the CSE machine meets a breakpoint, the current program context is sent to both the debugger and the visualiser. The visualizer receives the context in the form of an EnvTree, which represents all of the frames created in the program's execution. Each node in the tree represents a frame, which in turn is a table of bindings (as defined in the textbook). The parent pointer of each node is hence a pointer to its enclosing environment. The tree is rooted at the node representing the global function bindings.

The visualiser depends on KonvaJS and its corresponding React bindings from react-konva. The feature resides under src/features/cseMachine and is exposed via CseMachine.tsx in that directory.

We make use of Typescript and try to follow OOP concepts with JS ES6 classes. Drawing logic and dimension calculations etc. pertaining to a certain type of value (array, for example) are encapsulated within their own class files. Overall, this has led to better correctness, extensibility, maintainability, and collaboration (its predecessor was a single file with ~3K LoC).

For a rough outline, we have a Layout class that encapsulates the canvas and calculations. The Layout contains an array of Levels, which in turns contain an array of Frames.

Each Frame is assigned an (x, y) coordinate, sharing the same y-coordinate as its Level, with later Frames having larger x-coordinates. If the x-coordinate of a Frame is smaller than the x-coordinate of its parent Frame, then its x-coordinate is increased to align with its parent Frame.

A Frame has Bindings, which consists of a key (string) and the associated data. The data can be of any type: functions, arrays, pairs, etc. Hence, we have wrapper classes for each of these types, encapsulating the logic for dimension calculations and drawing for that specific type.

Some of these [Binding]s could also be dummy bindings, which have keys that are numeric strings. They represent the objects that are in the environment heap but are not included inside the environment head. This ensures that objects will always get drawn next to the environment frames they are created in, whether it is through actual bindings or dummy bindings.

After the objects are initialised and the dimensions/coordinates are calculated, Layout.draw() is invoked, which in turns triggers a cascade of draw() invocations in all the nested children, similar to how objects are initialised. Most arrows from any object or frame would be created and handled within the object’s draw method, with the only exception being the frame-to-frame arrows which can be created in the initialisation step. The frames and layers are drawn from top to bottom, left to right.

Exporting: The last JS Slang Context is stored, and toggling printable mode will reuse the current Context and redraw the entire diagram with different colours and the truncated tooltip being used for function objects. Clicking on save will obtain the image data url of the entire Konva stage, and save it as multiple images of width ≤ 25000px.

Testing

Snapshot testing is implemented here. It executes some previously problematic or tricky code samples and calculates the layout. It then checks that the general structure of the layout and data in the frames is correct. However, it may be worth noting that this may not be a fully comprehensive test. It aims to prevent glaring errors but subtly wrong visualizations may still pass. Some automated tests conducted for each sample program includes: checking function object is next to enclosing frame, ensuring svg path of arrows from function object to enclosing frame, and from array unit to array within the same level behaves correctly. More tests can be added to reduce the amount of manual testing needed.

For a more comprehensive test, a manual visual inspection may still be required. We have amassed a collection of code samples to test against.

Animations

The CSE Machine additionally supports animations when the control and stash are enabled. The animations aim to help users observe dynamic data flow by offering a visual representation of how data is processed and transferred, resulting in a better comprehension of complex code execution. Currently, animations are played only upon pressing the next button (moving forward by 1 step).

The CSE Machine currently supports animations for the following expressions/instructions:

• Array access
• Array assignment
• Array creation
• Assignment (to binding)
• Binary operation
• Block evaluation (splitting of control item into more items)
• Branch (conditionals)
• Environment change
• Frame creation
• Function application
• Literals
• Lookup (identifier)
• Pop
• Unary operation

Technical Details

Foundation

Animation components are subtypes of Visible, meaning that they have an abstract draw method just like all other CSE machine components, and are initialised and drawn in a similar way. However, note that animation components are drawn on a separate canvas layer on top of the CSE machine layout.

Animation components are divided into two types, Animatable and AnimatableTo (both inside Animatable.ts), which extends from the standard Visible component.

Animatable are for more complex animations, having an animate() method where one can describe more advanced animation choreography. The animate method also takes in an optional config argument which is only supported in some animations, such as frame creation, where a delay is needed.

AnimatableTo are for simpler animations, having an animateTo(props, config) method instead. They are for components that wrap one or two Konva nodes in their draw method, and calling animateTo will animate the drawn node to the target props. AnimatableTo also have addListener and removeListener methods, which can attach listener functions that run on every frame that the animation is running.

Both Animatable and AnimatableTo have an abstract destroy() method. When creating a new animation component, you must ensure that any nested animations or listeners are destroyed/removed when destroy() is called, to ensure proper clean up and prevent errors.

Use of JS Promises

Both animate and animateTo methods are promises that do not return any value. These promises are resolved when the animation is complete. Using promises allow us to write code for animation steps in a flat, linear manner, without nested callbacks. However, note that the timings are not very precise due to overhead from promises and Konva itself, and the promises don't resolve instantly after the animation ends. If you need exact timing, use the delay property inside the animation config instead.

Animation Components

The abstract class BaseAnimationComponent is where all the animation logic lie. It extends AnimatableTo and contains an animation function that runs on every frame of the animation, driven by a Konva.Animation object.

A custom interpolation function lerp is used to interpolate between starting and ending values based on the current delta of the animation (a value from 0 to 1), and the easing function. The delta is calculated from the frame's current time alongside starting and ending times, and the value obtained from lerp is then set to the Konva node inside the animation function.

The concrete class AnimationComponent is a wrapper for a single Konva node and implements the draw method. We can create an animation component like this:

const animationComponent = new AnimationComponent(
  Rect,
  { x: 0, y: 0, width: 100, height: 100, fill: '#ff0000' }
);

This creates a red rectangle when drawn, with x and y coordinates set to 0 and height and width set to 100. If we then call animationComponent.animateTo({ x: 100, fill: '#0000ff' }), we would observe the rectangle turning blue while also moving right in 300ms, the default duration specified in CseAnimation.

There are four animation components defined that are wrapper for Konva's Text, Rect, Path and Arrow nodes: AnimatedTextComponent, AnimatedRectComponent, AnimatedPathComponent, and AnimatedArrowComponent. They contain default props that set the colors and size of each node, so it is preferable to use these components in most cases instead of creating an animation component with no default props.

Why Konva.Animation?

The use of a Konva.Animation instead of a Konva.Tween allows for high flexibility for animations of different properties. Consider the following code inside the animate method of another animation:

// inside constructor
this.animationComponent = new AnimationComponent(
  Rect,
  { x: 0, y: 0, width: 100, height: 100, fill: '#ff0000' }
);
// inside animate()
await Promise.all([
  this.animationComponent.animateTo({ x: 100 }),
  this.animationComponent.animateTo({ y: 200 }, { duration: 2 })
]);
this.animationComponent.animateTo({ x: 0 });

Assuming that this.animationComponent is drawn in the draw method and that animate is called, we obtain the following result:

// TODO: add result video/gif

Observe how multiple animateTo calls can happen concurrently with different animation config properties, i.e. duration, delay, easing. This is present in multiple different top-level animations where cross-fade effects are common and require opacity to be animated on a different duration or delay than other properties.

The CSE Machine uses the konva and react-konva libraries for its animations. It makes use of KonvaNodeComponents from the react-konva library, most commonly Rect and Text. We represent general animatable components under the classes Animatable and AnimatableTo, with the main difference being that AnimatableTo supports simultaneous animations on the same component. We mostly encapsulate the unique animation of each instruction into its own file as an Animatable, which makes use of more basic animation components such as AnimatedTextbox (which is an AnimatableTo). The precise logic for each animation is defined in the animate() function within each Animatable.

For a rough outline, we store information from the previous step i in previousControlComponent and previousStashComponent. Note that this is necessary as the animation for step i is played when the 'next' button to step i+1 is pressed, which means that we need to read information from step i after processing the runtime context of step i+1 to determine what animation to play. We initialise the animations in CseMachineAnimation after processing the runtime context from JS Slang in CseMachineLayout, reading the instruction type of the top control item from the previous step. After the visualisation state has been updated in the CSE Machine, we play the created animations.

Limitations

• UI Testing: While there is snapshot testing implemented currently, it may not be very comprehensive and complete. It may be possible for wrong/broken layouts to pass the tests. By nature, testing of this tool may ultimately require visual inspection. It is not clear how to programmatically verify the visual 'correctness'.
• Animation Testing: There is no clear way to test that animations are running correctly, as it requires tests to peek into the props of the animation component at a precise timing and use correct interpolation functions to verify that the props match. By nature, testing of animations also require visual inspection.
• Arrows: Most arrows are drawn as just a straight line from source to target, which causes many overlaps in the CSE machine. A past implementation of an environment visualiser had ArrowLanes, so one could look into that to create less messy arrows.
• Garbage Collected Frames: Objects that are garbage collected can already be represented in the CSE machine. However, environment frames that are no longer referenced are not represented by the CSE machine yet.
• Large Canvas Scrolling: Our current implementation is slow at handling large canvas such as the environment model of a metacircular evaluator. A possible way to optimise this is to emulate the scrollbars using canvas, to render only the visible portion of the environment model at a time. To get started, you may want to refer to Large Canvas Scrolling Demo using Konva.

Future Improvements

• Solve the limitation of not being able to show all historically created frames as mentioned above (will need changes to js-slang) done by SA2122
• Visualisation of arrays done by SA2122
• Representation of functions belonging to the global frame (e.g. const x = pair) should be implemented done by SA2122
• Improve text formatting in data structures (eliminate the problem of long text being cut off) done by SA2122
• Allow arrows to be hovered over individually instead of all at once (this involves coding each arrow as its own object with its own properties) done by SA2122
• Downloading visualizations
• Show array indexes done by SA2324
• Garbage collected functions and arrays done by SA2324
• Animations done by SA2324
• Toggle between 'show all frames created' and 'show current frames only'
• More animations
• Large Canvas Scrolling (see above)
• Arrows (see above)
• Testing (see above)