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: A Frame object, which is a dictionary that contains the variable/function bindings in the environment:
export interface Frame {
  [name: string]: any
}
  • 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.

State

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 all i, environments[i+1] is the enclosing environment of environments[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: The Control stack, as described above.
  • stash: The Stash, 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).

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

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: A Context 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 of options:
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.

runCSEMachine

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: A Context object representing an instance of the CSE machine to be used.

  • control: A reference to context.runtime.control.

  • stash: A reference to context.runtime.stash.

  • envSteps, stepLimit, isPrelude: Configurations passed down from options.

  • Returns: The result of running the CSE machine on the given context.

Clone this wiki locally