On this page:

2 Data structures

The main elements of any program are code and data, so that means two data structures should be enough. Unsurprisingly, the data stack will be a regular list. Everything related to the code (function definitions, the call stack, the code itself) can all go in one structure – the context.

Together, the stack and the context contain everything necessary to run the program.

(struct context
  ; Program code
  ([body        : Code]
   ; Symbols looked up in here
   [definitions : (Immutable-HashTable Symbol Function)]
   ; Bookkeeping required by uplevel
   [children    : (Listof Context)]
   ; The calling context (if it's currently in the middle of a function call)
   [parent      : (Option Context)])
  #:transparent #:type-name Context)
; I never remember the right order for fields, so here's a keyword constructor.
(define (make-context
          #:body [body : Code '()]
          #:definitions [defs : (Immutable-HashTable Symbol Function)
                              (make-immutable-hash '())]
          #:children [children : (Listof Context) '()]
          #:parent [parent : (Option Context) #f])
  (context body defs children parent))

I introduced a couple of types in there, hopefully with semi-obvious meanings. Here they are along with some other supporting type definitions:

; The data stack is just a list
(define-type Stack (Listof Any))
; A program is also just a list
(define-type Code (Listof Any))
; Builtin is a Racket procedure that updates a context and stack.
; It needs to be a procedural structure type in order to have a type predicate.
  ([f : (Context Stack . -> . (Values Context Stack))])
  ((lambda (self ctx stack) ((Builtin-f self) ctx stack))
   : (Builtin Context Stack . -> . (Values Context Stack))))
; A Function is either code or a builtin.
; TODO this should be Definition to be consistent with the document.
(define-type Function (U Code Builtin))
(: function? (-> Any Boolean : Function))
(define (function? v) (or (list? v) (Builtin? v)))
; Can't use (Option A) because its None value is #f,
; which is a value we want to use in Worst.
; Using Void instead avoids any ambiguity.
; (Not a problem if the host language supports proper algebraic data types.)
(define-type (Maybe A) (U Void A))