This note is called: [WHY-LISP]
The notations used in this note is described in [NOTATION]
LISP: A Prototype Thinker
I have always found LISP to be a compelling language to use when building AI systems. The point of this note is to describe how features of the LISP system architecture instinctively implemented ideas which I consider essential to building a thinking artifact.
LISP is Conversational
LISP is frequently described as having a read-eval-print style of user interface but a more interesting way of thinking about this is: you talk (ie type) to LISP; it interprets what you say; and it responds. This idea of interaction has become commonplace in apps and its importance is the same. Interaction is the key to producing useful, interesting, 'smart' systems. In fact, much of the work developing a computer application involves designing its 'user interface'. Such an interface ranges from arcane terse interaction languages (TECO (are you old enough to remember?), ...) to to more recent attempts at using different takes on natural language (search queries, simplified English, full NLP)
Quality of conversion
LISP distinguishes between spoken and mental language
A closer look at the LISP 'read-eval-print' loop reveals that read is a process of interpretation or understanding and that eval could reasonably be thought of as a mental act. That is, the LISP reader (listener) takes the stream of characters you type, 'parses' them, and builds data structures that are the in-memory representations of the s-expressions it 'heard'. Then LISP interprets each of these data structures as an instruction to be 'evaluated', a process which operates on this internal data; figures out how to describe the result and reports (prints/says) the result back to you.
You speak - type characters ie written language (text)
read
LISP listens
LISP turns your utterance into some internal form (a mental image)
eval
LISP decides what to do with this data
LISP (on the basis of this decision) changes its internal state
LISP decides if it will report back something
LISP (on the basis of this decision) creates a response
print
LISP speaks
LISP outputs its response
You listen/hear - read from the output device
All along LISP has been building 'mental models' of what you type. In fact, the LISP 1.5 manual p, 36 [LISP-1.5] describes in detail both an abstract (using boxes) and a concrete realization (using addresses in a computer memory) of how these 'mental images' might be realized in a computer memory.
Written Language/s-expressions
LISP simplifies the question of what language it uses in conversation by defining s-expression and describes both how to write them and a translation into the 'mental language' used internally by the LISP 'head'. The 1.5 Manual used the term 's-expression' (symbolic expression) for what you type and 'm-expression' (meta expressions) for its in-memory structures. I propose thinking of s-expressions as spoken expressions) and m-expressions as mentel 'expressions' The LISP 1.5 Manual also describes exactly how s-expressions and m-expressions are related.
Aside ------------------------------------------------------------------------------ The 1.5 Manual also describes how both data and programs could be described as s-expressions. The ability of s-expressions to describe programs has frequently sloganized as "LISP provides programs as data". It also gives examples of programs being used both as arguments of other programs and being returned as the 'values' of computations. (Aside (inside an aside): The original LISP failed to implement programs as data 'correctly' but the goals were clearly articulated. (see [ARGSvsVALS]) ------------------------------------------------------------------------------
The distinction between s-expressions/'external data' and m-expressions/'internal data' has been ignored by everyone. Since in LISP systems they 'look the same', programmers don't usually think about the difference. In fact, it is now common practice to call both types of data s-expressions. The semantics of LISP systems (i.e., the way they are implemented) guarentees that any time the system see two s-expressions, e.g., "(a b)" and "(a b)" that are EQUAL (see the section on 'equality' below), every LISP system builds a mental image of that s-expressions with the same properties (relatative to EQUAL), even though they may be located in the memories of different computers.
IN LISP 1.5 all mental data was either atomic or of type pair. The only atomic types were symbol and number. In the next section we discuss symbols but numbers are handled much the same way.
Symbols
Here we backtrack a little and ask what was meant by the 'A' mentioned above. Unlike many current programming languages LISP has a data type called 'symbol', which were treated in a particularly interesing way. When LISP read a series characters that 'looked like a symbols' it looked to see if it had seen this sequence before and if it had it didn't make a 'new' symbol but rather simplyimagined that it was the one it had seen before. Thus when LISP read a the symbol 'Richard' it would either recognize that it had seen it before or, if not, it would 'construct' it anew.
Since all LISP systems did this, symbols could be passed back and forth between LISPs and never loose their identity, even though it existed in two different LISPs and 2) the systems did not need to know how or at what memory locations it was stored. In this sence we could say that the symbol 'A' was consistently understood by all LISPS. These provides a 'solution' to the ancient and ongoing philosophical discussions about universals. Each LISP can have its own internal symbol 'A' (the structure of which is hidden from each of us) yet we can unambigously communicate about 'A'. In this sense there does not need to be an 'A' in the 'real' world even though we can reliably refer to it with a common understanding. In addition, 1) the ordinary semantics of equal holds for 'A' and 2) it allows us to extend the notion to more complex ideas.
Pairs
This was guaranteed because the the LISP implementation assured that the the only 'semantics' assigned to an s-expression was the common understanding that its 'meaning' depended only on the 'meaning's assigned to its parts together with the fact that it was a pair. By recursion this reduced to the 'meaning' of its atomic parts and how atomic data was used to build more complex data. The pair (written as a LISP s-expression)
(A . B)
'meant' a thing whose first element was A and whose second element was B. A programmer was free to use this in any way they chose but what it meant to be a LISP system was that every time that it 'read' an s-expression that looked like '(A . B)' the system would build a structure whose type was pair and whose first element was 'A' and whose second element was 'B'. By building a structure with these 'same' properties, a programmer was always able to have unambigous conversations with the LISP system.
The idea of having both 's-expressions' and 'm-expressions' is not new. In Summa logicae (1323) William of Ockham divided lamguage into mental language, spoken language and written language. I think of s-expressions as the artifical formal 'spoken' language of LISP and the corresponding in-memory data structure, m-expressions, as comprising LISP's mental language/magels.
William does not seem to make much of the difference between spoken and written languages (a point on which I disagree). In the case of interactions with LISP there is no spoken language but in-memory data structures correspond to mental language and s-expressions correspond to written language. To blur the distinction, a la Ockham, I refer to s-expressions as spoken (in fact actually typed) language.
EQUAL and EQ
LISP has always recognized the difference between the meaning of the s-expression '(A . B) and its esistenct as a da6ta structure in the memory of the computer.
Aside ------------------------------------------------------------------------------- In LISP 1.5 there were no 'strings'. Symbols and numbers were called atomic and pairs were not. In contemporary LISPs there are many data types that are notliterally atomic, e.g., strings, arrays, vectors, ... . This proliferation ofdata types has made the formal semantics of LISP more opaque and we do not really go into these issues here. We are strictly interested in building a head and understanding what would be in it. The operational semantics of programming languages is certainly well defined and well understood (people actually write useful applications using them) but formal semantics is illusive. This note is not about either. We really just want to know what to put in our 'head'. -------------------------------------------------------------------------------
Atomic objects are either the same object or not. The LISP operator EQ does this test. Two symbols (atoms) are EQ just in case they are exactly the same object. LISP used an interesting strategy to accomplish this. Whenever LISP read a sequence of characters that 'looked like' a symbol it looked to see if it had already seen such a chractorization before it used the same data structure as it already had for the 'symbol'. For example, every time it read the sequence 'c', 'a', 't' of characters it would imagine it to be the same symbol. This process was called interning. Another LISP system would do the same. Of course the symbols in the two systems were not the 'same' physical object (they were in different 'heads') but if either system again 'hears' 'c', 'a', 't' again, it will recognize that it has seen it before and will understand it to be the same symbol 'cat'.
Updating
Another feature of LISP (and other programming systems) that has been largely ignored by the formalism community (and the entire community of logicians - from Aristotle to the present) is the possibility that mental that can be updated. What I mean by this are structures that have persistant identity but may have different contents or structure over time. For those unequated with programming languages languages, think backpacks (or if you are old enough post office mailboxes). In our ordinary life we use things that can be updated all the time, eg, our pockets or purse. Their purpose is to act as storage 'of the moment' and keep things organized for us. We call this kind of data structures 'mutable'. I discuss this in detail in MUTABLE].