-
Notifications
You must be signed in to change notification settings - Fork 104
CSE Machine
The CSE machine is an evaluation model for Source languages, based on Chapters 3 and 4 of Structure and Interpretation of Computer Programs (SICP). It is used to evaluate programs in Source §4 Explicit-Control, as well as display the CSE Machine visualization for programs in Source §3 and Source §4.
The specific functions that implement the CSE machine can be found in src/cse-machine/interpreter.js.
The CSE machine consists of three key components:
-
Control: A stack that stores syntax tree nodes to be evaluated and instructions to be executed.
-
Stash: A stack of values that is manipulated through instructions.
-
Environments: Structures containing variable and function bindings within a given scope.
The Control stack is represented by the class Control
, which is an alias for Stack<ControlItem>
. Each ControlItem
is either:
- A
Node
: an Abstract Syntax Tree (AST) node representing part of the program to be evaluated; or - An
Instr
: an instruction to be executed on the machine.
The Stash is represented by the class Stash
, which is an alias for Stack<Value>
. Each Value
represents some intermediate value generated during evaluation of the program.
Each Environment in the machine is represented by the class Environment
, which has the following structure:
export interface Environment {
readonly id: string
name: string
tail: Environment | null
callExpression?: es.CallExpression
head: Frame
heap: Heap
thisContext?: Value
}
-
id
: A unique identifier for the environment. -
name
: A descriptive name of the environment. For example, program environments would have the name"programEnvironment"
, while function environments would have the name of the respective function. -
tail
: A reference to the enclosing environment of the environment. The enclosing environment is used to recursively search for variable bindings. -
callExpression
: An AST node representing the call expression that resulted in the creation of the environment (applicable only to function environments). -
head
: An object that contains the variable/function bindings in the environment. -
heap
: ASet<HeapObject>
that contains the objects that are bound to the environment (i.e. not primitive values). EachHeapObject
is either anArray
or aClosure
. -
thisContext
: Unused in the current version of the CSE machine.
The CSE machine uses a Context
object to keep track of the current state of the machine, as well as other information regarding the current evaluation. In particular, it uses the following components of Context
:
export interface Context<T = any> {
...
chapter: Chapter
errors: SourceError[]
prelude: string | null
runtime: {
break: boolean
debuggerOn: boolean
isRunning: boolean
environmentTree: EnvTree
environments: Environment[]
nodes: Node[]
control: Control | null
stash: Stash | null
objectCount: number
envStepsTotal: number
breakpointSteps: number[]
changepointSteps: number[]
}
...
}
-
chapter
: The Source chapter in which the program is being evaluated. -
errors
: An array containing errors encountered during evaluation of the program. -
prelude
: Before the evaluation of a Source program, a prelude program is evaluated which declares and defines some set of variables and functions. If the prelude has not yet been evaluated, this field is where it is stored. -
isRunning
: Whether the context is currently being used by the CSE machine. -
environmentTree
: A tree representation of all environments in the machine. This is generated by the CSE machine but not used by it - it is intended to be consumed by the frontend. -
environments
: An array containing the environments that are currently in scope.environments[0]
is called the current environment and represents the innermost scope the CSE machine is in at any given point during environment. For alli
,environments[i+1]
is the enclosing environment ofenvironments[i]
. The last environment in the array is the global environment, where all primitive functions reside. -
nodes
: An array with at most one element:nodes[0]
is the most recent node evaluated by the machine. -
control
: TheControl
stack, as described above. -
stash
: TheStash
, as described above. -
objectCount
: The total amount of objects (arrays/functions) that has been created in the machine. -
envStepsTotal
: The total number of steps that has been performed in the current/last evaluation. -
changepointSteps
: An array containing the step indices where the machine had a change in environments (creation of environment, creation/modification of bindings).
The machine is run by calling the function evaluate
. This function sets up the runtime components of the machine, performs some pre-run validation checks, transforms the program for optimization purposes, and finally, calls runCSEMachine
.
runCSEMachine
performs the actual task of running the machine. It calls generateCSEMachineStateStream
, which is a generator function that runs and returns individual evaluation steps of the machine on-demand. (This is similar to streams in SICP.) It then iterates through the returned generator to run the machine. After evaluation is complete, the function returns the top of the Stash
as the result of evaluating the given program.
At each step, the CSE machine takes the ControlItem
at the top of the stack, and runs the CmdEvaluator
corresponding to its type, as given in the cmdEvaluators
dictionary. The CmdEvaluator
processes the item and manipulates the Control
, Stash
and Environments
accordingly. This loop repeats until one of the following happens:
- The control stack is empty, at which point the evaluation is complete.
- The step limit given in
stepLimit
is reached. - The number of steps to be evaluated (given in
envSteps
) is reached. - The machine encounters a runtime error.
export function evaluate(program: es.Program, context: Context, options: IOptions)
Evaluates the given program using the CSE machine.
-
program
: An AST node representing the program to be evaluated. -
context
: AContext
object representing an instance of the CSE machine to be used. -
options
: An object representing the configuration of the CSE machine for the evaluation. In particular, the CSE machine uses the following components ofoptions
:
export interface IOptions {
...
stepLimit: number // step limit
isPrelude: boolean // is the current program the prelude?
envSteps: number // number of steps
...
}
-
stepLimit
: Number of steps before the CSE machine is halted. -
isPrelude
: A boolean signifying whether the program being evaluated is a prelude or not. -
envSteps
: number of steps that the user wants to evaluate, before "pausing" the CSE machine. Used in the CSE machine visualization. -
Returns: The result of evaluating the given program.
function runCSEMachine(
context: Context,
control: Control,
stash: Stash,
envSteps: number,
stepLimit: number,
isPrelude: boolean = false
)
Given a context
object representing an instance of the CSE machine, runs the CSE machine on said context until one of the conditions described in [Behavior] happens.
-
context
: AContext
object representing an instance of the CSE machine to be used. -
control
: A reference tocontext.runtime.control
. -
stash
: A reference tocontext.runtime.stash
. -
envSteps
,stepLimit
,isPrelude
: Configurations passed down fromoptions
. -
Returns: The result of running the CSE machine on the given
context
.