| Marlene Miller 2007-06-19, 8:08 am |
| Adrian wrote:
> Please be kind - this may be a very dumb question.
>
> I was wondering why an expression that is not a procedure doesn't
> simply evaluate to itself in a procedure application? i.e., why don't
> all such expressions have an intrinsic procedure that returns the
> expression?
>
> Why can't (123) return 123?
>
(123) to be equivalent to ((lambda (x) x) 123)?
(123) == (cons 123 '()). See postulate 3 below.
"The theory of recursion equations deals with functions over the natural
numbers. In LISP, however, one is interested in being able to manipulate
algebraic expressions, programs, and other symbolic expressions as data
structures. While such expressions can be encoded as numbers (using the
technique of "arithmetization" developed by Kurt Godel), such an encoding is
not very convenient. Instead, a new kind of data called "S-epxressions" (for
"symbolic expressions") is introduced specifically to provide convenient
encodings. S-expressions can be defined by a set of formal inductive axioms
analogous to the Peano postulates used to define natural numbers. Here we
will give only an informal and incomplete definition of S-expressions; for
a more complete description, see {Note S-expressions Postulates and
Notation}." pg 4
"Numeric constants are encoded as numeric atoms; variables are encoded as
non-numeric atom(which henceforth we will call atomic symbols); and
procedure invocations are encoded as lists, where the first element of the
list represents the procedure and the rest represent the arguments." pg 5
"{S-expression Postulates and Notation} Pages 4,41
S-expressions form a number system analogous to that for the natural
numbers. Each can be used to encode arbitrary strings of symbols by means of
"Godelization", but the S-expression encoding is usually far more convenient
than the numerical encoding.
[...]
The Postulates for S-expressions
1. Atoms are S-expressions.
2. The cons of any two S-expressions is an S-expression.
3. An atom is not the cons of any two S-expressions.
4. If alpha differs from beta, or if gamma differs from delta, then cons of
alpha and gamma differs from cons of beta and delta.
5. (Induction Principle) Any property which is true of all atoms, and is
such that if it is true for two S-expressions it is alos true for their
cons, is true for all S-expressions." pg 65
Guy Lewis Steele, Jr. and Gerald Jay Sussman. "The Art of the Interpreter
of, the Modularity Complex (Parts Zero, One, and Two)". MIT AI Lab. AI Lab
Memo AIM-453. May 1978. Available online: ps pdf. Abstract and citation.
|