The evaluator can read a finite program and preserve its environment.
A small eval/apply system can evaluate quoted top-level forms in one mutable global environment, return a transcript of definitions and values, and report whether an explicit form budget completed the batch.
What turns a collection of evaluator procedures into a program that can run a sequence of user forms?
- Separate host Lispex execution from the guest expressions represented as data
- Dispatch self-evaluating values, variables, special forms, and applications
- Apply host primitive procedures and represented compound procedures
- Preserve definitions and assignments in one explicit global environment
- Observe lexical closure capture across later global changes
- Report a complete or truncated finite top-level driver run
- Keep the top-level form budget distinct from work inside one form
The evaluator represents environments as lists of mutable frames. A guest variable lookup searches those frames; define changes the first frame; set! searches for an existing binding and changes that record. A guest lambda becomes a compound-procedure record containing parameters, body expressions, and the environment where the lambda was evaluated. apply-procedure either applies a host primitive or evaluates a compound body in a new frame.
run-program is the driver. It receives quoted top-level forms, one explicit global environment, and a form budget. Every completed form contributes one transcript value while definitions and assignments remain visible to later forms. The full run defines square, make-adder, add-five, and base; add-five keeps the local x value 5 even after the global base changes. The second run stops after five forms and reports four forms still pending. This form budget does not bound recursion or work inside a single form; the packaged browser runtime still supplies the lower-level execution limits.
(begin
(define (tagged-list? expression tag)
(if (pair? expression)
(eq? (car expression) tag)
#f))
(define (self-evaluating? expression)
(cond ((number? expression) #t)
((string? expression) #t)
((boolean? expression) #t)
(else #f)))
(define (quoted? expression)
(tagged-list? expression 'quote))
(define (assignment? expression)
(tagged-list? expression 'set!))
(define (definition? expression)
(tagged-list? expression 'define))
(define (if? expression)
(tagged-list? expression 'if))
(define (lambda? expression)
(tagged-list? expression 'lambda))
(define (begin? expression)
(tagged-list? expression 'begin))
(define (text-of-quotation expression) (cadr expression))
(define (assignment-variable expression) (cadr expression))
(define (assignment-value expression) (caddr expression))
(define (definition-variable expression)
(if (symbol? (cadr expression))
(cadr expression)
(car (cadr expression))))
(define (definition-value expression)
(if (symbol? (cadr expression))
(caddr expression)
(cons 'lambda
(cons (cdr (cadr expression))
(cddr expression)))))
(define (if-predicate expression) (cadr expression))
(define (if-consequent expression) (caddr expression))
(define (if-alternative expression) (cadddr expression))
(define (lambda-parameters expression) (cadr expression))
(define (lambda-body expression) (cddr expression))
(define (begin-actions expression) (cdr expression))
(define (operator expression) (car expression))
(define (operands expression) (cdr expression))
(define (pair-bindings variables values)
(cond ((and (null? variables) (null? values)) '())
((null? variables) (error "too many arguments"))
((null? values) (error "too few arguments"))
(else
(cons (cons (car variables) (car values))
(pair-bindings (cdr variables)
(cdr values))))))
(define (make-frame variables values)
(cons '*frame* (pair-bindings variables values)))
(define (first-frame environment) (car environment))
(define (frame-bindings frame) (cdr frame))
(define (extend-environment variables values base)
(cons (make-frame variables values) base))
(define (lookup-variable-value variable environment)
(if (null? environment)
(error "unbound variable" variable)
(let ((binding
(assoc variable
(frame-bindings (first-frame environment)))))
(if binding
(cdr binding)
(lookup-variable-value variable (cdr environment))))))
(define (define-variable! variable value environment)
(let* ((frame (first-frame environment))
(binding (assoc variable (frame-bindings frame))))
(if binding
(set-cdr! binding value)
(set-cdr! frame
(cons (cons variable value)
(frame-bindings frame)))))
(list 'defined variable))
(define (set-variable-value! variable value environment)
(if (null? environment)
(error "unbound assignment" variable)
(let ((binding
(assoc variable
(frame-bindings (first-frame environment)))))
(if binding
(begin
(set-cdr! binding value)
(list 'assigned variable))
(set-variable-value! variable value (cdr environment))))))
(define (make-procedure parameters body environment)
(list 'compound parameters body environment))
(define (compound-procedure? procedure)
(tagged-list? procedure 'compound))
(define (procedure-parameters procedure) (cadr procedure))
(define (procedure-body procedure) (caddr procedure))
(define (procedure-environment procedure) (cadddr procedure))
(define (list-of-values expressions environment)
(if (null? expressions)
'()
(cons (evaluate (car expressions) environment)
(list-of-values (cdr expressions) environment))))
(define (eval-sequence expressions environment)
(if (null? (cdr expressions))
(evaluate (car expressions) environment)
(begin
(evaluate (car expressions) environment)
(eval-sequence (cdr expressions) environment))))
(define (eval-if expression environment)
(if (evaluate (if-predicate expression) environment)
(evaluate (if-consequent expression) environment)
(evaluate (if-alternative expression) environment)))
(define (eval-assignment expression environment)
(set-variable-value!
(assignment-variable expression)
(evaluate (assignment-value expression) environment)
environment))
(define (eval-definition expression environment)
(define-variable!
(definition-variable expression)
(evaluate (definition-value expression) environment)
environment))
(define (apply-procedure procedure arguments)
(cond ((procedure? procedure)
(apply procedure arguments))
((compound-procedure? procedure)
(eval-sequence
(procedure-body procedure)
(extend-environment
(procedure-parameters procedure)
arguments
(procedure-environment procedure))))
(else
(error "not a guest procedure" procedure))))
(define (evaluate expression environment)
(cond ((self-evaluating? expression) expression)
((symbol? expression)
(lookup-variable-value expression environment))
((quoted? expression)
(text-of-quotation expression))
((assignment? expression)
(eval-assignment expression environment))
((definition? expression)
(eval-definition expression environment))
((if? expression)
(eval-if expression environment))
((lambda? expression)
(make-procedure
(lambda-parameters expression)
(lambda-body expression)
environment))
((begin? expression)
(eval-sequence (begin-actions expression) environment))
((pair? expression)
(apply-procedure
(evaluate (operator expression) environment)
(list-of-values (operands expression) environment)))
(else
(error "unknown guest expression" expression))))
(define primitive-bindings
(list (cons '+ +) (cons '- -) (cons '* *) (cons '/ /)
(cons '= =) (cons '< <) (cons '> >)
(cons 'cons cons) (cons 'car car) (cons 'cdr cdr)
(cons 'list list) (cons 'null? null?)
(cons 'pair? pair?) (cons 'not not)))
(define (make-global-environment)
(list (cons '*frame* primitive-bindings)))
(define (run-program forms environment form-budget)
(define (loop remaining budget transcript)
(cond ((null? remaining)
(list 'complete (reverse transcript) 0))
((= budget 0)
(list 'truncated
(reverse transcript)
(length remaining)))
(else
(loop (cdr remaining)
(- budget 1)
(cons (evaluate (car remaining) environment)
transcript)))))
(loop forms form-budget '()))
(define guest-program
'((define (square x) (* x x))
(define (make-adder x) (lambda (y) (+ x y)))
(define add-five (make-adder 5))
(define base 5)
(square (+ base 2))
(add-five 7)
(set! base 9)
(if (> base 8) (square base) 0)
(add-five 1)))
(list
(run-program guest-program (make-global-environment) 20)
(run-program guest-program (make-global-environment) 5)))- Output
- —
- Value
- —
- Diagnostic
- —
The complete run returns (complete ((defined square) (defined make-adder) (defined add-five) (defined base) 49 12 (assigned base) 81 6) 0). The limited run returns (truncated ((defined square) (defined make-adder) (defined add-five) (defined base) 49) 4).
Separate host calls that implement evaluate and apply-procedure from guest expressions stored in guest-program. Follow global frame mutation across define and set!, the new frame created for each compound application, and the environment captured by add-five. In run-program, one budget unit is spent only after one top-level form returns; this counter does not measure recursive guest work inside that form.
Change the program before you read the hint.
Add a guest definition (define (twice procedure value) (procedure (procedure value))) and evaluate (twice add-five 1). Predict the new transcript value and the remaining-form count when the form budget stays at 5.
Show one hint
The complete run applies add-five twice, so the guest result is 11. In the limited run, inserting another form after the existing definitions changes which expression becomes the fifth completed form.