;;; apl-meta.scm APL version of metacircular evaluator.
;;; SETTING UP THE ENVIRONMENT
;;; APL primitives aren't part of the environment. They are not subject
;;; to redefinition, for example. They are kept in a separate list. So
;;; the initial environment is empty. But define! only works if there is
;;; a non-empty environment, so we fake something.
(define the-global-environment '())
;;; INITIALIZATION AND DRIVER LOOP
;;; The following code initializes the machine and starts the APL
;;; system. You should not call it very often, because it will clobber
;;; the global environment, and you will lose any definitions you have
;;; accumulated.
(define (initialize-apl)
(set! the-global-environment
(extend-environment '(no-name) '(no-value) '()))
(set! apl-operators
(list (make-scalar-op '+ (lambda (x) x) +)
(make-scalar-op '- - -)
(make-scalar-op '*
(lambda (x) (cond ((< x 0) -1) ((= x 0) 0) (else 1)))
*)
(make-scalar-op '% / /)
(make-scalar-op 'bar abs rem)
(make-scalar-op '= error (apl-pred2 =))
(make-scalar-op '< error (apl-pred2 <))
(make-scalar-op '> error (apl-pred2 >))
(make-op '/ error compress)
(make-op 'iota iota error)
(make-op 'rho shape reshape)
(make-op 'comma ravel cat)
(make-op 'gets error 'set!)))
(apl-loop))
;;; APPLYING PRIMITIVE PROCEDURES
;;; The mechanism for applying primitive procedures is somewhat
;;; different from the one given in the course notes. We can recognize
;;; primitive procedures (which are all inherited from Scheme) by asking
;;; Scheme if the object we have is a Scheme procedure.
(define (primitive-procedure? p)
(applicable? p))
;;; To apply a primitive procedure, we ask the underlying Scheme system
;;; to perform the application. (Of course, an implementation on a
;;; low-level machine would perform the application in some other way.)
(define (apply-primitive-procedure p args)
(apply p args))
;;; Now for the code from the book!!!
;;; Section 4.1.1
(define (mini-eval exp env)
(cond ((self-evaluating? exp) exp)
((variable? exp) (lookup-variable-value exp env))
((assignment? exp) (eval-assignment exp env))
((application? exp)
(mini-apply (mini-eval (operator exp) env)
(list-of-values (operands exp) env)
env))
(else (error "Unknown expression type -- MINI-EVAL" exp))))
(define (mini-apply procedure arguments env)
(cond ((primitive-procedure? procedure)
(apply-primitive-procedure procedure arguments))
((compound-procedure? procedure)
(eval-sequence (procedure-body procedure)
(extend-environment
(parameters procedure)
arguments
env)))
(else
(error "Unknown procedure type -- MINI-APPLY" procedure))))
(define (list-of-values exps env)
(cond ((no-operands? exps) '())
(else (cons (mini-eval (first-operand exps) env)
(list-of-values (rest-operands exps)
env)))))
(define (eval-sequence exps env)
(cond ((last-exp? exps) (mini-eval (first-exp exps) env))
(else (mini-eval (first-exp exps) env)
(eval-sequence (rest-exps exps) env))))
(define (eval-assignment exp env)
(let ((new-value (mini-eval (assignment-value exp) env)))
(set-variable-value! (assignment-variable exp)
new-value
env)
new-value))
;;; Section 4.1.2 -- Representing expressions
;;; numbers
(define (self-evaluating? exp) (number? exp))
;;; variables
(define (variable? exp) (symbol? exp))
;;; assignment
(define (assignment? exp)
(if (not (pair? exp))
#f
(eq? (car exp) 'set!)))
(define (assignment-variable exp) (cadr exp))
(define (assignment-value exp) (caddr exp))
;;; sequences
(define (last-exp? seq) (null? (cdr seq)))
(define (first-exp seq) (car seq))
(define (rest-exps seq) (cdr seq))
;;; procedure applications
(define (application? exp)
(if (not (pair? exp))
#f
(procedure? (car exp))))
(define (procedure? exp)
(or (applicable? exp) (compound-procedure? exp)))
(define (operator app) (car app))
(define (operands app) (cdr app))
(define (no-operands? args) (null? args))
(define (first-operand args) (car args))
(define (rest-operands args) (cdr args))
;;; Representation of procedure objects
(define (make-procedure lambda-exp env)
(list 'procedure lambda-exp env))
(define (compound-procedure? proc)
(if (not (pair? proc))
#f
(eq? (car proc) 'procedure)))
(define (parameters proc) (cadr (cadr proc)))
(define (procedure-body proc) (cddr (cadr proc)))
(define (procedure-environment proc) (caddr proc))
;;; Section 4.1.3
;;; Operations on environments
(define (lookup-variable-value var env)
(if (assq var apl-operators)
var
(let ((b (binding-in-env var env)))
(if (found-binding? b)
(binding-value b)
(error "Unbound variable" var)))))
(define (binding-in-env var env)
(if (no-more-frames? env)
no-binding
(let ((b (binding-in-frame var (first-frame env))))
(if (found-binding? b)
b
(binding-in-env var (rest-frames env))))))
(define (extend-environment variables values base-env)
(adjoin-frame (make-frame variables values) base-env))
(define (set-variable-value! var val env)
(let ((b (binding-in-env var env)))
(if (found-binding? b)
(set-binding-value! b val)
(error "Unbound variable" var))))
(define (define-variable! var val env)
(let ((b (binding-in-frame var (first-frame env))))
(if (found-binding? b)
(set-binding-value! b val)
(set-first-frame!
env
(adjoin-binding (make-binding var val)
(first-frame env))))))
;;; Representing environments
(define (first-frame env) (car env))
(define (rest-frames env) (cdr env))
(define (no-more-frames? env) (null? env))
(define (adjoin-frame frame env) (cons frame env))
(define (set-first-frame! env new-frame)
(set-car! env new-frame))
;;; Representing frames
(define (make-frame variables values)
(cond ((and (null? variables) (null? values)) '())
((null? variables)
(error "Too many values supplied" values))
((null? values)
(error "Too few values supplied" variables))
(else
(cons (make-binding (car variables) (car values))
(make-frame (cdr variables) (cdr values))))))
(define (adjoin-binding binding frame)
(cons binding frame))
(define (assq key bindings)
(cond ((null? bindings) no-binding)
((eq? key (binding-variable (car bindings)))
(car bindings))
(else (assq key (cdr bindings)))))
(define (binding-in-frame var frame)
(assq var frame))
(define (found-binding? b)
(not (eq? b no-binding)))
(define no-binding '())
;;; Representing bindings
(define (make-binding variable value)
(cons variable value))
(define (binding-variable binding)
(car binding))
(define (binding-value binding)
(cdr binding))
(define (set-binding-value! binding value)
(set-cdr! binding value))