EK201 HAND OUT #6 FEB,11 1987

  Time: 7:30-9:30 MON, 7:30-8:30 WED
  Instructor: George Carrette
  Office:     room 171, sociology building
  Hours:      6:30-7:30 Wed, on-line during evening hours

Today: A review of computational cost computation.
       Introduction to the evaluator.

NOTATIONS:
  => means evaluates to.
  === means semantically identical to. (used in identities)
  ==> means can be expanded into for the purpose of evaluation.
 


GET and PUTPROP allow data to be stored on symbols keyed by a symbol.
e.g. (PUTPROP 'JUMP 'JUMPING 'GERUND)
     (PUTPROP 'DATUM 'DATA 'PLURAL)

(DEFUN PLURALIZE (SYMBOL) (OR (GET SYMBOL 'PLURAL) (INTERN (STRING-APPEND SYMBOL "S"))))

(PLURALIZE 'PIG) => PIGS
(PLURALIZE 'DATUM) => DATA

CASE, a special form convenient for dispatching.

(CASE A (X (EXP1)) (Y (EXP2)) (T (EXP3)))
 ==> (COND ((EQ A 'X) (EXP1)) ((EQ A 'Y) (EXP2)) ('ELSE (EXP3)))


* The definition of the Evaluator *
The evaluator is self contained except for the model of
the application of primitives.

(defun meval (form env)
  (cond ((not (atom form))
	 (let ((op (car form)))
	   (cond ((and (symbolp op) (get op 'special-form))
		  (funcall (get op 'special-form) form env))
		 ('else
		  (mapply (function-value op env) (meval-args (cdr form) env))))))
	((symbolp form)
	 (variable-value form env))
	('else
	 form)))

(defun mapply (f args)
  (cond ((primitive-p f)
	 ;; this case assumes a model for primitives.
	 (primitive-apply f args))
	('else
	 (meval (function-code f) (create-environment (function-arguments f) args)))))


(defun meval-args (l env)
  (mapcar #'(lambda (a) (meval a env)) l))


(defprop quote meval-quote special-form)

(defun meval-quote (form env)
  (cadr form))


(defprop if meval-if special-form)

(defun meval-if (form env)
  (if (meval (cadr form) env)
      (meval (caddr form) env)
      (meval (cadddr form) env)))

(defprop setq meval-setq special-form)

(defun meval-setq (form env)
  (set-variable-value (cadr form) env (meval (caddr form) env)))


(defprop defun meval-defun special-form)

(defun meval-defun (form env)
  (set-function-value (cadr form) env (make-function (cddr form))))

(defprop progn meval-progn special-form)

(defun meval-progn (form env)
  (do ((l (cdr form) (cdr l)))
      ((null (cdr l))
       (meval (car l) env))
    (meval (car l) env)))

;; the rest depends only on our implementation (as opposed to model)
;; for environments and primitives.
;;

(defun variable-value (var env)
  (cdr (or (assq var env)
	   (get var 'value-cell)
	   (error "unbound variable" var))))

(defun set-variable-value (var env value)
  (rplacd (or (assq var env)
	      (get var 'value-cell)
	      (putprop var (cons var nil) 'value-cell))
	  value)
  value)


(defun function-value (f env)
  (cdr (or (get f 'function-cell)
	   (error "undefined function" f))))


(defun set-function-value (f env v)
  (rplacd (or (get f 'value-cell)
	      (putprop f (cons f nil) 'function-cell))
	  v)
  v)


(defun make-function (l)
  (list 'function (car l) (if (= 2 (length l)) (cadr l) (cons 'progn (cdr l)))))


(defun function-arguments (f)
  (cadr f))


(defun function-code (f)
  (caddr f))

(defun create-environment (formals actuals)
  (mapcar #'cons formals actuals))


(defun primitive-p (f)
  (symbolp f))


(defun primitive-apply (f l)
  (apply f l))


;; setup some primitives

(dolist (f '(+ * 1+ 1- > < = car cdr cons))
  (set-function-value f nil f))


Howework:

 This evaluator will be in the file /usr2/ek_ai/examples/meval.l
 Modify it so that an unbound variable evaluates to itself,
 and an undefined function evaluates to one that will cons
 up a call to itself. e.g.

 (meval 'x ()) => X
 (meval '(foo x (1+ 3))) => (foo x 4)