In AI Memo 8 of the MIT Research Laboratory of Electronics (March 4, 1959), John McCarthy gives a definition of the universal
S-function `apply`

:

apply is defined by apply[f;args]=eval[combine[f;args]] eval is defined by eval[e]=[ first[e]=NULL→[null[eval[first[rest[e]]]]→T;1→F] first[e]=ATOM→[atom[eval[first[rest[e]]]]→T;1→F] first[e]=EQ→[eval[first[rest[e]]]=eval[first[rest[rest[e]]]]→T; 1→F] first[e]=QUOTE→first[rest[e]]; first[e]=FIRST→first[eval[first[rest[e]]]]; first[e]=REST→rest[eval[first[rest[e]]]; first[e]=COMBINE→combine[eval[first[rest[e]]];eval[first[rest[rest [e]]]]]; first[e]=COND→evcon[rest[e]] first[first[e]]=LAMBDA→evlam[first[rest[first[e]]];first[rest[rest [first[e]]]];rest[e]]; first[first[e]]=LABELS→eval[combine[subst[first[e];first[rest [first[e]]];first[rest[rest[first[e]]]]];rest[e]]]] where: evcon[c]=[eval[first[first[c]]]=1→eval[first[rest[first[c]]]]; 1→evcon[rest[c]]] and evlam[vars;exp;args]=[null[vars]→eval[exp];1→evlam[ rest[vars];subst[first[vars];first[args];exp];rest[args]]]McCarthy asserts that “if f is an S-expression for an S-function φ and args is a list of the form (arg

_{1}, …, arg

_{n}) where arg

_{1}, ---, arg

_{n}are arbitrary S-expressions then

`apply[f,args]`

and φ(arg_{1}, …, arg

_{n}) are defined for the same values of arg

_{1}, … arg

_{n}and are equal when defined.”

I find it hard to puzzle through these equations, so I've transcribed them into S-expressions to get the following:

;;; Hey Emacs, this is -*- Lisp -*- (in-package "CL-USER") ;; Don't clobber the system definitions. (shadow "APPLY") (shadow "EVAL") (defun apply (f args) (eval (combine f args))) (defun eval (e) (cond ((eq (first e) 'NULL) (cond ((null (eval (first (rest e)))) t) (1 nil))) ((eq (first e) 'ATOM) (cond ((atom (eval (first (rest e)))) t) (1 nil))) ((eq (first e) 'EQ) (cond ((eq (eval (first (rest e))) (eval (first (rest (rest e))))) t) (1 nil))) ((eq (first e) 'QUOTE) (first (rest e))) ((eq (first e) 'FIRST) (first (eval (first (rest e))))) ((eq (first e) 'REST) (rest (eval (first (rest e))))) ((eq (first e) 'COMBINE) (combine (eval (first (rest e))) (eval (first (rest (rest e)))))) ((eq (first e) 'COND) (evcon (rest e))) ((eq (first (first e)) 'LAMBDA) (evlam (first (rest (first e))) (first (rest (rest (first e)))) (rest e))) ((eq (first (first e)) 'LABELS) (eval (combine (subst (first e) (first (rest (first e))) (first (rest (rest (first e))))) (rest e)))))) (defun evcon (c) (cond ((eval (first (first c))) (eval (first (rest (first c))))) (1 (evcon (rest c))))) (defun evlam (vars exp args) (cond ((null vars) (eval exp)) (1 (evlam (rest vars) (subst (first args) (first vars) exp) (rest args)))))We just have to add a definition for

`combine`

as a synonym for `cons`

and this should
run:* (eval '(eq (first (combine 'a 'b) (combine 'a 'c)))) T

As Steve “Slug” Russell observed, `eval`

is an interpreter for Lisp. This version of `eval`

uses an interesting evaluation strategy. If you look carefully, you'll see that there is no conditional clause for handling variables. Instead, when a lambda expression appears as the operator in a combination, the body of the lambda expression is walked and the bound variables are substituted with the expressions (not the values!) that represent the arguments. This is directly inspired by β-reduction from lambda calculus.

This is buggy, as McCarthy soon discovered. In the errata published one week later, McCarthy points out that the substitution process doesn't respect quoting, as we can see here:

* (eval '((lambda (name) (combine 'your (combine 'name (combine 'is (combine name nil))))) 'john)) (YOUR 'JOHN IS JOHN)With a little thought, we can easily generate other name collisions. Notice, for example, that the substitution will happily substitute within the bound variable list of nested lambdas.

Substitution like this is inefficient. The body of the lambda is walked once for each bound variable to be substituted, then finally walked again to evaluate it. Later versions of Lisp will save the bound variables in an environment structure and substitute them incrementally during a single evaluation pass of the lambda body.

## 1 comment:

This is a call-by-name interpreter, so more Algol 60 than Lisp.

Post a Comment