CSE Machine

Overview

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 should always be 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.
• In general, arrows point to arrays from its left/right, and exit from array units from its top/bottom, travelling horizontally/vertically to the target objects.
  • For arrays within the same ArrayLevel but at different array sublevels, arrows take shortest path from the array unit to the target array
  • For arrows from an array to itself, the arrow exits array unit from top and points back down.

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 whenever 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 upon pressing the next button (moving forward by 1 step).

The CSE Machine currently supports animations for the following 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

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: Arrows moving horizontally within an ArrayLevel between array sublevels currently overlap.
• 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
• Large Canvas Scrolling (see above)
• Toggle between 'show all frames created' and 'show current frames only'
• Show array indexes done by SA2324
• Animations (see above, work in progress)
• Arrows (see above)
• Testing (see above)
• Garbage collected functions and arrays done by SA2324