0

Some LISP expressions evaluate to themselves (examples are MIT-Scheme REPL, though GNU Common Lisp agrees):

1 ]=> 3
;Value: 3

And are in normal form. Evaluation of an expression (such as (+ 2 1)) thus can properly be said to be conversion to normal form. That's nice, because that's how I've always understood evaluation formally.

But with lists we're in trouble:

1 ]=> (list 3 2)
; Value 16: (3 2)
1 ]=> (3 2)
;The object 3 is not applicable.
;To continue, call RESTART with an option number:
; (RESTART 2) => Specify a procedure to use in its place.
; (RESTART 1) => Return to read-eval-print level 1.

Am I right in thinking that:

  1. (many[0]) LISPs don't have normal forms for (non-empty) lists, and
  2. (many) LISPs do not have the property that evaluation is reduction to normal form?

If so, isn't this somewhat at odds with formalisms in PLT such as abstract rewriting systems? What alternative formalisms do capture evaluation in LISPs?

[0] Or perhaps more accurately, "most of the prominent LISPs", such as CL, Clojure, and Scheme. But I'd be interested in less well-known counter-examples!

user2141650
  • 2,827
  • 1
  • 15
  • 23
  • 3
    There is no 'normal form' in Lisp and evaluation isn't conversion to a normal form. That all data (other than symbols and lists) evaluate to themselve is just by definition in later Lisp dialects. Lisp is not an implementation of lambda calculus. It uses specific types of evaluators. – Rainer Joswig Feb 10 '17 at 20:29

1 Answers1

2

Lisp can be defined in terms of only a few primitive operators. How many primitives does it take to build a LISP machine? Ten, seven or five? So you could consider there to be a normal form for what you get from expanding to them.

But Lisp isn't the lambda calculus. What type of lambda calculus would Lisp loosely be an example of?

And Lisp wasn't designed to be like the lambda calculus:

To use functions as arguments, one needs a notation for functions, and it seems natural to use the lambda-notation of Church. I didn’t understand the rest of the book, so I wasn’t tempted to try to implement his more general mechanism for defining functions.
-- History of Lisp, Stanford AI Laboratory memo 1979 by J. McCarthy, page 6

Community
  • 1
  • 1
philipxy
  • 14,867
  • 6
  • 39
  • 83