Implementing an SPL interpreter

TL;DR

We implement an interpreter for the PetitParser SPL case study using a small-step operational semantics in which the state of a running program consists of: (1) an AST representing the rest of the code to be executed, (2) the environment of variables and their values, and (3) the output produced so far.

Operational semantics of SPL

We will directly implement a so-called Structural Operation Semantics for SPL. In essence, we model a running SPL program as a transition system, or state machine, in which execution means taking a “small step” from one program state to another.

An SPL program state consists of three parts, which we call a “context” for running the program. The context is updated with each execution step.

1. The rest of the code

An AST is used to represent the code to be executed. With each step, this tree will be “reduced”, or transformed, to another tree. For normal, terminating programs, this AST will shrink in size until it reachs the empty program, and stop.

2. The environment

SPL has variables, so we must keep track of their values. With each variable declaration, a new variable is added to the environment. With each variable initialization or assignment, the environment is updated.

3. The output

The output is simply a growing collection of strings produced by print statements.

At the end of the program, the only side effect is the output produced.

Implementing the SPL semantics

To implement the semantics we need (1) the SPLContext Object subclass: #SPLContext instanceVariableNames: 'environment outputHolder traceHolder nodeHolder' classVariableNames: '' package: 'GToolkit-Demo-SPL-Interpreter' object to keep track of the execution states, and (2) stepInContext: methods for every node in the SPLNode Object subclass: #SPLNode instanceVariableNames: '' classVariableNames: '' package: 'GToolkit-Demo-SPL-Interpreter' hierarchy.

Furthermore, every node must know if it is fully reduced or not. This is false in general (see SPLNode>>#isReduced isReduced "This node is fully reduced. Only true for values and empty blocks." ^ false ), and is only true for values (like 3 or true) and empty blocks of statements.

Let's see the example of the print statement. SPLPrintStatement>>#stepInContext: stepInContext: aContext ^ self expression isReduced ifTrue: [ aContext printLn: self expression value asString. SPLExpressionStatement for: self expression ] ifFalse: [ self class for: (self expression stepInContext: aContext) ]

A print statement prints an expression. If the expression is fully reduced to a value, then we print that value to the output and replace the print statement by an SPL expression statement, which will take the next step.

If, on the other hand, the expression is not reduced, we ask the expression take a step, and then replace the print statement by a new print for the partially reduced expression.

Running a simple program

Consider this simple SPL program. The three boxes show the execution context. The code to execute is print (3+4);, and the environment and output are empty.

After one step, the environment is updated with x=3, and the variable declaration has reduced to an expression statement.

After another step, the expression statement has been discarded, and we move to the print statement.

After a few more steps, the print statement has been evaluated, and the output has been produced.

Testing the interpreter

We define SPLContextExamples Object subclass: #SPLContextExamples instanceVariableNames: '' classVariableNames: '' package: 'GToolkit-Demo-SPL-Examples' containing numerous examples to test all of the step rules.

A typical example is this “hello world” test.

printHello
	<gtExample>
	| result context |
	context := self context: '// Hello program in SPL
print "hello";'.
	result := context.
	result := context reduce.
	self assert: context output allButLast equals: 'hello'.
	^ context

In this example we send reduce to the context to tell it to step until the end.

Inspector views for SPL contexts

By adding a few custom inspector views to the SPLContext Object subclass: #SPLContext instanceVariableNames: 'environment outputHolder traceHolder nodeHolder' classVariableNames: '' package: 'GToolkit-Demo-SPL-Interpreter' class, we obtain a simple back-in-time debugger almost for free.

The “Continuation” view shows the code to be executed in a text editor element, here for a factorial program.

The “AST” view shows the AST of the code.

The “Environment” view shows the current variable bindings, here after 7 steps of the factorial program.

The “Output” is another text editor view, here for the reduced factorial.

The “State” view composes these three views into one, here one step before the end.

Finally, after every step, we save the new context in a trace collection, so the “History” view summarizes all the previous states.

Naturally, the Inspector view combines all of these views, and adds “step” and “reduce” buttons to the “State” view.