Skip to content

CSE Machine

Jump to bottom
Theoth Normie edited this page Apr 6, 2024 · 15 revisions

Overview

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.

Structure

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.

Control

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.

Stash

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.

Environment

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: A Set<HeapObject> that contains the objects that are bound to the environment (i.e. not primitive values). Each HeapObject is either an Array or a Closure.
  • thisContext: Unused in the current version of the CSE machine.

Behavior

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 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.

Functions

evaluate

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: An object representing information regarding the current evaluation. In particular, the CSE machine uses the following components of context:
export interface Context<T = any> {
  ...
  /** The source version used */
  chapter: Chapter

  /** All the errors gathered */
  errors: SourceError[]

  /** Runtime Specific state */
  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[]
  }
  prelude: string | null
  ...
}
  • options: An object representing the configuration of the CSE machine for the evaluation. In particular, the CSE machine uses the following components of options:
export interface IOptions {
  ...
  stepLimit: number
  isPrelude: boolean
  envSteps: number
  ...
}
  • Returns: The result of evaluating the given program.
Clone this wiki locally