Skip to content

CSE Machine

Jump to bottom
Theoth Normie edited this page Apr 5, 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 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: 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 this environment (i.e. not primitive values). Each HeapObject is either an Array or a Closure.
  • thisContext: Unused in the current CSE Machine.
Clone this wiki locally