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.
«context» ::=
(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:
«types» ::=
; 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. (define-struct/exec Builtin ([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))