A.N.A.L.O.G. ISSUE 8 / NOVEMBER 1982 / PAGE 39
Writing a review of Lisp is a little difficult when not too many people know about Lisp in the first place. So this article will start out with Lisp in general, and then review a specific implementation. There are many conceptions about what Lisp is like—an artificial intelligence language, a memory waster, a group of parentheses for syntax. So, in part, I’ll have to give you my own feelings about the language.
First of all, I like Lisp. The ideas behind it, its applications and its elegance outweigh all those parentheses, and its speed. Lisp is not solely another programming language, but also a programming environment, due to its extensibility and power.
Lisp is short for LISt Processing language. Its strength is derived from the representation of both programs and data as lists, and from operators that work on any list structured data—possibly a program. You can, by looking at Listings 1 and 2, get a quick flavor of the language. Oh yes, SETQ, takes the first argument and gives it the value of the second and COND is the same as CASE statement. Listings 1, 2, and 3 all are the same program; Listing 1 is a recursive version, Listing 2 is a straightforward version, and Listing 3 is a version in BASIC.
Why aren’t more people using this language? It looks strange. Availability is certainly one problem, and memory is another, (Data-Soft requires 48K and a disk). It is a tad slow—depending on the application, and well, it does have many parentheses. But these are trade-offs in any language, BASIC vs. Assembler, for example. Once one understands the inherent limitations of any language, including its implementation, the reasons for using it are also clearer.
Don’t get impatient, we will illustrate where Lisp might be used. The field of artificial intelligence is one place, where one would like to construct “expert” systems that can draw hypotheses from principles and data. In fact, some oil companies use such a system to keep track of the confusion of interrelated geological facts and rules so they can decide if a piece of land may have oil under it. I’m looking at another application, working on a program to do manipulation of symbolic expressions for formal logic. If I can understand how to make it general enough, I’ll also use it for matrix manipulation, tensor calculation and other goodies. In short, I want a general purpose mathematical assistant.
Data-Soft has implemented Lisp for the ATARI with 48K and a single drive. It comes with an 86 page manual, a single disk, and a book—Lisp, by Winston and Horn. The book is so good that I had bought it before I bought Lisp. It is the single best book on the subject for a beginner, and an excellent reference. The system itself is successfully modelled after Inter-Lisp with such ATARI specific commands as sound, color, stick, trigger and peek/poke. In addition all the graphics modes are available.
On booting up, I was in control of Lisp version 2.1, so without reading the manual, (version 2.0), I typed in:
Listing 1.
(DEFINEQ FIBO (N)
(COND((EQ N 2) 1)
( (EQ N 1) 1)
(T (+ (FIBO( SUB N 1) ) (FIBO( SUB N
2) ) ) )
)
)
which defines a program called FIBO recursively, that is, in terms of itself. It worked, generating the Nth Fibonacci number, (i.e. a number from the sequence 1 1 2 3 5 8 13 21 34 etc. Do you know the rule for generating this sequence?)
With a slightly more complex program it becomes necessary to use the editor. The commands take a single evening to understand and use. Written in Lisp, the editor is a joy. (Take it from someone who tried, be careful editing the editor). It can step in to different levels of parentheses, remove or insert parentheses or expressions, and pretty-print listings as the above program was done. This last feature helps to find both logical and structural faults. The editor also has features to save and retrieve files, which like almost everything else in Lisp, is a list.
Standard Lisp I/O funcdons of READ, READA and READC are implemented as are PROG, PROGN, MACRO, DEFINE and DEFINEQ. For those acquainted with MACLISP there is a package that simulates the actions of many MACLISP functions, (including property lists—for Inter-Lisp uses A-lists). Also included are: a program for a light show demo; an RPN calculator program; yet another version of ELIZA and Towers of Hanoi; CLISP, a program which changes algebraic expressions into valid Lisp expressions; and a worthwhile utilities package.
The manual is a pleasant surprise. Looseleaf bound with plenty of examples and a clarity usually reserved for a cold drink on a hot summer day, it is a refreshingly complete reference for this implementation of Lisp.
Listing 2. (DEFINEQ FIBO (LAMBDA (N) (PROG (XX N1 N2 COUNT) (SETQ XX 1) COND ( (EQ N 2) RETURN XX) ) ( ( EQ N 1) (RETURN XX) ) ) (SETQ COUNT 2) (SETQ N2 1) (SETQ N1 1) LOOP (SETQ X(+ N1 N2) ) SETQ N2 N1) (SETQ N1 X) SETQ COUNT (+ COUNT 1) ) (COND ( (EQ COUNT N) (RETURN XX) ) ) (GO LOOP) ) ) ) A non recursive version of the program in Listing 1.
Listing 3.
10 INPUT N
20 N1=1:N2=1
30 IF N=1 OR N=2 THEN X=1:GOTO 90
40 FOR I=3 TO N
50 X=N1+2
60 N2=N1
70 N1=X
80 NEXT I
90 PRINT X
The problems that exist are minor, the worst being that GENSYM from the MACLISP package does not work. Although peek and poke are implemented there is no simple way to transfer control to a machine language program and this makes the problem of speed painful. The execution speeds of the above programs are 16, 1, and 1/6 seconds respectively, (which says the algorithm used affects speed greatly). But speed of execution is not the reason one would use Lisp anyway, (or BASIC for that matter). Rather, applicability to a given problem is the reason for using Lisp. Consider a program like ELIZA. It can be written in Assembly language and run much faster than Lisp. But the time to write or modify the program far outweighs the advantages in speed.
The final problem seems to result from some difficult choices facing the people when they wrote the language. Lisp usually has infinite, (or large), precision arithmetic. But this version uses the routines in the OS rom. This saves space—in not having to write another routine—but means it has the same limits of accuracy as ATARI BASIC, and its always floating arithmetic.
In summary. Lisp is not a language for everyone. But if you have the application Data-Soft Lisp is a good choice. Do I like the product? Emphatically, yes—and if I didn’t have it, I’d buy it!
A.N.A.L.O.G. ISSUE 10 / MARCH 1983 / PAGE 85
LISP is an old language, dating to the dark ages of computers (pre 1960), still hardly standardized, yet still making a contribution to the evolution of new languages. Its influence will continue to be felt in the years to come. And now it is emerging from the hallowed halls of academe and made available to us lesser mortals. It is a language for research; its availability on personal computers will allow anyone so inclined to participate in the future.
LISP is primarily a symbol manipulation language used today in many areas of the ever-expanding field of artificial intelligence. Programs in LISP can do calculus problems (on a level equivalent to college freshmen), prove mathematical theorems, solve geometric analogy problems, provide natural language interfaces to data base systems for limited domains such as moon rocks and inventory systems, and have been used for word processing, symbolic mathematics, and writing operating systems, utility programs, compilers, and interpreters for personal computers. These applications have been developed on large computers, but there is no reason why LISP’s capabilities cannot be harnessed on a personal computer. (See the review of a LISP implemenation for the ATARI in A.N.A.L.O.G. #8, particularly noting its limitations, which effect the speed of flexibility of LISP programs.) In this tutorial, I will attempt to convey the power, beauty, and sophistication of this language, while trying to demystify the aura which surrounds artificial intelligence.
LISP is essentially a functional language, meaning that its capabilities are implemented through functions (comparable to the functions in FORTRAN and analogous to the the subroutines in BASIC). A function is LISP is always enclosed in parentheses, with the function name given first, followed by its arguments (or values to be given to the function, if any). For example, (+ 2 5) will return the value 7. This prefix notation is important, since it ensures that the system always knows where to look for a function name. Other functions can also be used as arguments, nested to any depth. Listing 1 shows several examples of mathematical functions. Arguments for the more complex examples are discernible by balancing the parentheses.
As is evident from the examples in Listing 1, parentheses proliferate in LISP. This brings us to another main characteristic of LISP, namely, that it is a list processing language. The fundamental entities in LISP are called atoms (roughly corresponding to variable names in most other languages). Atoms may by numeric, such as 4 or 5.2374. Some symbolic atoms are given special meaning when they are used as function names (recognized as such either by the system or through user definition). Other symbolic atoms many be given values or properties. Atoms may be grouped together into lists, which can then be grouped into higher-level lists, and so on. Lists are always enclosed in parentheses. The functions in Listing 1 are nothing more than lists, some containing sublists, and all of them distinguished in that their first elements are symbolic atoms recognized as function names which cause a computation to be performed.
Listing 1.
(+ 3.14 1.27) ;User input
4.41 ;LISP response
(* 4.13 3) ;User input
12.39 ;LISP response
(/ 327 200) ;User input
1.635 ;LISP response
(* (+ 3 4) (SUB 13 5)) ;User input
56 ;LISP response
(SQRT 1.4641) ;User input
1.21 ;LISP response
Atoms and lists collectively are called symbolic expressions, or s-expressions. Their manipulation is the essence of LISP. As mentioned above, symbolic atoms may be given values; these values do not have to be numbers; they can be other symbolic atoms, lists, and even lists which are also functions. This makes LISP a symbolic language in addition to being a functional and list processing language.
The ability to give atoms values which are other atoms, lists, or functions is what gives LISP its power. Understanding how this is done is therefore of primary importance. There is a simple function called SETQ which gives a symbolic atoms its value. Thus, we can write (SETQ X 3); this is equivalent to the BASIC or FORTRAN assignment statement X=3. We can also write (SETQ X 'Y) or (SETQ X '(A B C)). These give X the value Y or (A B C), respectively, but they do so in a peculiar manner. First note that these values were preceded by a quote mark. This quote mark inhibited what is known in LISP as evaluation.
Whenever LISP encounters an atom or list, it attempt to evaluate it. That is, it will substitute the value of the atom or the list for the atom or list itself. In the case of the Y above, LISP would substitue the value of Y and make that value the value of X, if we had not inhibited evaluation with the quote mark or with the equivalent QUOTE function. In the case of the list (A B C), LISP would have attempted to determine its value by assuming that it is a function with name A and arguments B and C. Not finding a function with such a name would have caused an error. The quote mark inhibits such evaluation. In both cases, the QUOTE function returns the literal expression which follows it. This enables X to be given the literal values intended.
In the examples of Listing 1, where a function was given as an argument to another function, the absence of a quote mark permitted the evaluation of the function. The value of the function thus became the value of the first function’s argument. Sometimes, however, it is necessary to use the opposite of the QUOTE function and let a symbolic atom go through two (or more) stages of evaluation. This is accomplished with the EVAL function. Listing 2 shows an example of this, where the atom A is given the value B and the atom B is given the value C. When A is entered, LISP returns it value B; Similarly, B returns the value C. But, typing (EVAL A) returns the value C. In creating the listings for this article, I set a variable to the lines marked “User input” and then EVALuated that variable to get the LISP response. In most of the listings, this resulted in the evaluation of the function.
Listing 2.
(SETQ A (QUOTE B)) ;User input
B ;LISP response
(SETQ B (QUOTE C)) ;User input
C ;LISP response
A ;User input
B ;LISP response
B ;User input
C ;LISP response
(EVAL A) ;User input
C ;LISP response
Since LISP is a list processing language, it has special functions for manipulating them. The most basic functions are CAR (for Contents of Address Register) and CDR (for Contents of Decrement Register), where both acronyms were taken from the structure of the IBM 7090. CAR returns as its value the first s-expression of the list, while CDR returns the list that remains after the first element is removed. Listing 3 contains some examples of the functions; note again that the QUOTE function was used to inhibit evaluation.
Listing 3.
(CAR (QUOTE (A B C)) ;User input
A ;LISP response
(CDR (QUOTE (A B C))) ;User input
(B C) ;LISP response
(CAR (CDR (QUOTE (A B C)))) ;User input
B ;LISP response
(CDR (CDR (QUOTE (A B C)))) ;User input
(C) ;LISP response
(CAR (QUOTE ((A B) C))) ;User input
(A B) ;LISP response
Three other basic functions are APPEND, LIST and CONS. APPEND merges all the elements of each of its argument lists into one list, while LIST simply forms its arguments into a single list. CONS takes its first argument, any s-expression, and makes it the first element of the list which is its second argument. Listing 4 shows several examples of their use; in these cases, X has been given a value before use by the demonstrated function; no quote mark has been used in order to show what happens when an atom is evaluated prior to its use by a function. Several other list processing function are usually available in any implementation of LISP.
Listing 4.
(SETQ X (QUOTE (A B))) ;User input
(A B) ;LISP response
(APPEND X X) ;User input
(A B A B) ;LISP response
(LIST X X) ;User input
((A B) (A B)) ;LISP response
(CONS X X) ;User input
((A B) A B) ;LISP response
Lists may have any degree of complexity; by giving some lists a certain degree of regularity, they can be used in special ways by using system or user defined functions. Listing 5 shows one type of list I have created for analyzing the semantic structure of dictionary definitions. I have developed special functions to access particular parts of such lists when I wish to perform specific analyses. This list is known as a property list, in this case associated with the atom IF. An atom may have any number of properties, each of which in turn may have values.
Listing 5.
(PROPERTY LIST FOR THE DEFINITION OF "IF")
((CODE (I1))
(TOKEN
(IF)
(if))
(#DEFS (10))
(DEFS
((1 in the event that))
((2 in case))
((3 allowing, conceding, or granting that ))
((4 SUPPOSING))
((5 so long as))
((6 on condition that))
((7 WHETHER))
((8 USEGENOTE --used to introduce an
exclamation expresising a wish ))
((9 even though))
((10 altough perhaps))
))
LISP is a logical language in addition to being a functional, symbolic, and list processing language. LISP has two special atoms, T and NIL, roughly corrsponding to ‘true’ and ‘false’, respectively. If one were to enter an atom, thus requesting its value, and it had none, the system would respond NIL. If it had a value, that value would be returned. LISP has several functions which ask questions which demand an answer of T or NIL. Among these are ATOM (which asks whether its argument is an atom), EQUAL (which asks whether its two arguments are equal in value), NULL (which asks whether its argument is the null set), MEMBER (which asks whether its first argument, an s-expression, is an element of the second argument, a list), and the logical connectives AND, OR, and NOT (which act in the usual way). Several other predicate functions are usually available, and others are easily created.
Each LISP implementation has a special function for defining new functions. In the system which I use, this function is called DEFINEQ. The arguments of this function are the function name, the parameters of the function being defined, and the body of the function which articulates what the function is to do when it is called. The body of a function is much easier to comprehend for anyone with programming experience. Usually, the body of a function will contain a series of s-expressions combined in the form desired. After the function is defined, it can be used by itself or as part of another fucntion. When used, the function always returns a value (which may be just about anything).
One important type of s-expression which is frequently used in functions is the COND function, which makes use of the predicate functions. COND can have any number of arguments, each of which is a conditional expression called a clause. In each clause, the first s-expression is a predicate function; if this function has the value T (for true), then any expressions which follow are executed (or evaluated, to be a purist). The last such expression is returned as the value of COND. LISP examines each clause of a COND in turn, until it finds one whose first expression evaluates to T (actually, to anything that is nonNIL), and then evaluates everything else in the clause. Listing 6 is a function like CONS, except it will add an item to a list only if it is not already a member of the list. The first clause of the COND asks whether the item is already in the list and, if so, returns the list without the item being added. If the item is not on the list, COND will bypass the first clause, going to the second. Since we have made the first element of the second clause T, we have guaranteed that the consequents of this clause will always be executed if the first clause is not successful. In this case, the item not on the list will be added. The two examples in the listing show what happens to the list L when using this function.
Listing 6.
(DEFINEQ UNIQUECONS
(LAMBDA (ATM LST)
(COND ((MEMBER ATM LST)
LST)
(T (CONS ATM LST))))
)
(SETQ L (QUOTE (A B))) ;User input
(A B) ;LISP response
(UNIQUECONS (QUOTE D) L) ;User input
(D A B) ;LISP response
(UNIQUECON (QUOTE A) L) ;User input
(A B) ;LISP response
Conceivably, a function can be written in only one line, but typically several steps are performed. This requires the use of the function PROG which can have an indefinite number of arguments, each of which is an s-expression. Each argument is evaluated in turn and the last such argument is the value of the function. The first argument of PROG is a list of the variables to be used in the remainder of the arguments; when this function is entered, all such variables are initially given the value NIL. When one of the arguments in PROG is a symbolic atom, it is construed as a label which marks a place in the s-expressions to which a transfer can be made. This is done using the GO function. Listing 7 is a function to compute the factorial of the number N. This function also shows another example of how the COND function can be used. In this example, COND has only one clause; as long as the first expression in not T, the second expression (the function RETURN, used to exit and return a value from the PROG function) will not be evaluated.
Listing 7.
(DEFINEQ FACTORIAL-1
(LAMBDA (N)
(PROG (I J)
(SETQ I N)
(SETQ J 1)
(SETQ J 1)
LOOP
(COND ((EQ I 0)
(RETURN J)))
(SETQ J (* J I))
(SETQ I (SUB I 1))
(GO LOOP)))
)
(FACTORIAL-1 6) ;User input
720 ;LISP response
The factorial function can also be defined recursively, since LISP is also a recursive language, meaning that essential aspects of the language can be defined in terms of themselves. Thus, an s-expression can be defined as either an atom or as a left parentesis followed by a sequence of s-expressions separated by blanks and followed by a right parenthesis. To define a function recursively means to use the function as part of the body of the function itself. Such a function is self-referential. Listing 8 is the factorial function written recursively. Note that every use of this function terminates when N equals 0, and returns the number 1, the second expression of the first clause of the COND function.
Listing 8.
(DEFINEQ FACTORIAL-2
(LAMBDA (N)
(COND ((EQ N 0)
1)
(T (* N (FACTORIAL-2 (SUB N 1))))))
)
(FACTORIAL-2 6) ;User input
720 ;LISP response
An important capability in LISP is the ablility to use functions as arguments of other functions. For example, in developing a parser for analyzing English sentences, one first defines a series of functions known as an interpreter to handle the analysis. These functions in effect constitute an entire new programming language, defined by the user and then used to write the actual parsing programs. In LISP the ability to create such special programming languages arises from functions which can take function arguments. EVAL and QUOTE are two such functions; APPLY (or APPLY* in my system) is another such function.
APPLY takes two arguments, a function name and a list; the list contains the arguments necessary for the given function. APPLY then applies the function to the list and returns the values as if the function had been executed directly with its list of arguments. The significance of this function is that it allows “computed” function calls. At first glance, the value of this function may seem obscure, but it provides an ability to write programs which can write programs and then execute them.
One way APPLY can be used is in what [is] called “mapping functions”, with which a function is applied iteratively to a list of arguments. Listing 9 contains a definition of the function MAPCAR which applies its function argument to the CAR of a list. As can be seen, this function is also written recursively. It builds a list, one element at a time (using the CONS function), starting at the last element. This is done by recursive calls to MAPCAR until the second argument is the empty list (the first clause of the COND function). The function is primed to perform the CONSing operation for each element of the list, but makes sure it has reached the end of the list before it actually begins to form the list which will be the output. The second part of Listing 9 shows an example of this function’s use; in this case, the first argument is the function ATOM (which takes a single argument and asks if it is an atom or a list, returning T if it is an atom). The second argument of MAPCAR is the list of elements we wish to test. The value returned by this example is a list showing which elements of the list are atoms and which are not.
Listing 9.
(DEFINEQ MAPCAR
(LAMBDA (FN X)
(COND ((EQ X)
NIL)
(T (CONS (APPLY* FN (CAR X))
(MAPCAR FN
(CDR X))))))
)
(MAPCAR (QUOTE ATOM) (QUOTE (A B (A B) C (D E)))) ;User input
(T T NIL T NIL) ;LISP response
Using the material described thus far, it is now possible to present an example of a very powerful LISP function. Listing 10 contains a function which will determine if a list contains a pattern of a specified form. Despite its apparent simplicity, it can be used in quite imaginative ways to search for patterns in an input stream. I will describe one such way below after I have explained the function and one example of its use.
Listing 10.
(DEFINEQ MATCH
(LAMBDA (P D)
(COND ((AND (EQ P)
(EQ D))
T)
((OR (EQ P)
(EQ D))
NIL)
((OR (EQ (CAR P) (QUOTE >))
(EQ (CAR P) (CAR D)))
(MATCH (CDR P) (CDR D)))
((AND (EQ (ATOMCAR (CAR P)) (QUOTE >))
(MATCH (CDR P) (CDR D)))
(SET (ATOMCDR (CAR P)) (CAR D)) T)
((EQ (CAR P) (QUOTE +))
(COND ((MATCH (CDR P) (CDR D))
T)
(T (MATCH P (CDR D)))))
((EQ (ATOMCAR (CAR P)) (QUOTE +))
(COND ((MATCH (CDR P) (CDR D))
(SET (ATOMCDR (CAR P)) (LIST (CAR D))) T)
((MATCH P (CDR D))
(SET (ATOMCDR (CAR P)) (CONS (CAR D) (EVAL (ATOMCDR (CAR P)))))
T)))))
)
The arguments of the function, P and D, are both generally assumed to be lists, the first argument defining the pattern we wish to test for and the second argument the input we wish to test. The function constists of one condition, containing several clauses, and returns T if the pattern has been matched and NIL if the pattern has not been matched. The function is written recursively, so that it calls itself many times; the final call returns a value from one of the first two clauses in the condition statement. The expression (EQ P) asks if P is the empty set; if so, its value is T. The test in the first clause asks whether the lists P and D are both empty, i.e., have been exhausted at the same time, thus indicating a successful match, causing T to be returned. If they are not both empty, but one is, the test in the second clause will be T and cause NIL to be returned, since there is not total agreement between the pattern and the input being tested.
There are two tests in the third clause (indicated by the OR), the second of which asks if the first element of the pattern is the symbol [>] which is a privileged special atom which can match any atom. In other words, if the pattern has a [>], it does not matter what the input has; it will always yield a successful match. If either of these two conditions is met, the function says OK for the first two elements and asks if the rest of the two lists match (hence the call (MATCH (CDR P) (CDR D))). The fifth clause of the condition involves another privileged symbol +, which allows the pattern to match an arbitrary number of atoms in the input. It does this as follows: If the first element of the pattern is +, another COND statement is posed, in which one of the two tests can be successful in order to return an overall value of T. Either the remainder of P and D match or P matches the remainder of D. The second possibility is kind of tricky. Notice that we keep the list P, which we know begins with the special symbol + (since that was the test that got us into this situation); by keeping the same list, when the call (MATCH P (CDR D)) is made, we will end up at this same test on the next pass through the function. In effect, we have ignored the first element of the input in matching against the pattern. This will be made clearer in the example below.
In the fourth and sixth clauses of the condition, we are again testing for the presence of the special symbols + and [>], but with a twist. In these cases, we are testing to see if the symbols are actually part of the atoms. For example, we could have the symbol +L as part of the pattern. The function ATOMCAR unpacks the symbol into the list (+ L) and returns the + as its CAR. If the test of an atom shows that it has one of these special symbols as its leading character, the remainder of the clause then sets the value of the following atom to the element or elements in the input which matches the special symbols. This allows the unspecified part of the input to be used as the value of a variable, which can be used in any desired manner. The example will demonstrate this.
Listing 11.
(DEFINEQ DOCTOR
(LAMBDA NIL
(PROG (L MOTHER S)
(POKE 128 0)
(PRINT (QUOTE (SPEAK UP)))
LOOP
(SETQ S (READ))
(COND ((ATOM S)
(SETQ S (LIST S))))
(COND ((MATCH (QUOTE (I AM WORRIED +L)) S)
(PRINT (APPEND (QUOTE (HOW LONG HAVE YOU BEEN WORRIED)) L)))
((MATCH (QUOTE (+ MOTHER +)) S)
(SETQ MOTHER T) (PRINT (QUOTE (TELL ME MORE ABOUT YOUR FAMILY))))
((MATCH (QUOTE (+ COMPUTERS +)) S)
(PRINT (QUOTE (DO MACHINES FRIGHTEN YOU))))
((OR (MATCH (QUOTE (NO)) S)
(MATCH (QUOTE (YES)) S))
(PRINT (QUOTE (PLEASE DO NOT BE SO SHORT WITH ME))))
(MOTHER (SETQ MOTHER NIL) (PRINT (QUOTE (EARLIER YOU SPOKE OF YOUR MOTHER))))
(T (PRINT (QUOTE (I AM SORRY OUR TIME IS UP))) (RETURN (QUOTE GOODBYTE))))
(GO LOOP)))
)
The example using the matching function is shown in Listing 11, which is a much simplified version of the notorious ELIZA program written by Joseph Weizenbaum in the early 1960s. It is notorious because it simulates conversation between a computer and a human that can be very beguiling. It was so beguiling to Dr. Weizenbaum’s secretary that she asked him to leave because she felt she was having an intimate conversation with a psychologist. This incident, stemming from a simple program, set him against many of the initiatives of artificial intelligence. (See his book, Computer Thought and Human Reason.)
The program in Listing 11 begins by asking the human to initiate a conversation and set this input to the variable S. The main condition statement of the function DOCTOR then attempts to match key phrases against the input and then prints output based on the particular match. The second and third clauses of the condition look for instances of the words MOTHER and COMPUTERS, using the privileged symbol + to ignore any of the surrounding input. Note that when MOTHER is found in the input stream, the consequent part of the condition clause sets the atom MOTHER to T, so that if the rest of the converstation becomes repetitive, the response returns to this earlier reference in the fifth clause of the condition. (A value for MOTHER of T will activate the fifth clause.)
The first clause of the condition makes use of the facility to set the value of a variable to part of the input stream. If the input begins with the phrase “I AM WORRIED”, one can expect that the following part of the input will begin with the word “about” and then contain the object of the worry. The program is designed to catch this regularity by setting the variable L to the phrase beginning with “about” and using it in responding to the human, thus giving the illusion of intelligence. Finally, the last clause of the condition, having exhausted its repertoire, finishes its conversation. Since any number of clauses may be added to a COND expression, the sample program can be extended to cover a wide range of apparent conversational complexity.
The simplicity with which the pattern matching function was written should give some idea of the power of LISP. With such a function alone, it is possible to write simple programs like DOCTOR to accomplish such things as theorem proving, solving algebra word problems, differentiating complex mathematical functions, accessing a data base with a relatively free form input, developing chess playing programs, and examining data (e.g. astronomical data) for patterns. The power in LISP comes from being able to write ever more complex functions in terms of simpler functions, so that the user is operating on a high level with all the details hidden at a very deep level within the machine. In effect, LISP allows one to create a high level language to handle particular problem domains. A user can operate on the problem domain without being concerned with the details.
My particular interest lies in determining the semantic relationships between the different meanings of words, with the hope of eventually incorporating semantic properties in English language parsers. LISP enables me to conceptualize the problems at a higher level. My first problem is to analyze the regularities of dictionary definitions. To do this, I must develop a parser which will handle the peculiarities of dictionary definitions. I can build such a parser by identifying patterns at the lowest level, such as nouns, adjectives, and verbs. By ascertaining the existence of patterns of particular parts of speech, I can build more and more complex parsers which will look for particular types of noun or verb phrases. With a pattern matcher, I can first determine if a particular definition fits an existing pattern, and, if not, hypothesize a new pattern which I can easily add to the set of pattern for which I test.
When I wish to add a pattern to an existing parser, I have to build program statements which can be inserted into an existing program. Here again, LISP comes with a ready-made capability., A program is nothing more than a list, so to alter the program it is only necessary to alter the list. This is simplified in LISP since a program can be treated as a list. In fact, to print the functions accompanying this article, their definitions were given as arguments to another function which printed them out in a pretty form, so that the plethora of parentheses would not be confusing. (This is known as prettyprinting.)
It is therefore possible in LISP to create a program based on another program. I can use a pattern matching program to look for particular patterns. Using the COND expression, I can then build a list which consists of program-like words. Using the EVAL function, such a list can be transformed into a program and executed. This is the power of LISP.
A.N.A.L.O.G. ISSUE 14 / NOVEMBER 1983 / PAGE 19
“Logo with Turtle Graphics” is the hottest educational catchphrase since “Computer Literacy.” BASIC cartridges across the nation are gathering chalk dust as teachers leap onto the Logo bandwagon. School departments will soon be making big purchasing decisions based on the availability of a good Logo system—and woe to the manufacturer who doesn’t offer at least one.
Why is Logo so popular among educators? Reasons vary, but the two most often cited are its simplicity and its versatility.
Logo was designed from the ground up to be easy to learn. Developed by Dr. Seymour Papert at the Massachusetts Institute of Technology, Logo uses a direct, procedure-oriented command syntax that encourages logical thinking and good programming technique. Its turtle graphics system is a great motivator for young students, who delight in creating patterns and movement on a TV set with their own programs. Yet Logo belies its MIT heritage by incorporating many of the powerful list processing functions found in Lisp, Prolog and other so-called artificial intelligence languages. Logo’s list-oriented structure makes it suitable for parsing, pattern recognition and other exotic applications that would be difficult to implement in a conventional language like BASIC.
ATARI has taken their sweet time about coming out with a Logo. But the new Atari Logo package looks as if it was worth the wait. The 16K cartridge-based language was developed for ATARI by Logo Computer Systems, Inc. (LCSI), a Toronto-based firm best known for its implementation of Logo on the Apple computer. As a result of this collaboration, the Atari Logo system and documentation have a clean, confident “feel” that is noticably lacking in ATARI’s previous language releases.
Figure 1 shows all of the built-in commands or “primitives” in the Atari Logo vocabulary. These are the basic building blocks that are used to define new words called “procedures,” which are in turn combined to form applications called “useful programs.” Many BASIC hackers would sacrifice their little sister for the ability to define new commands. New commands are exactly what Logo programming is all about.
Figure 1. Atari Logo Vocabulary.
TURTLE GRAPHICS
ASK BACK BG
CLEAN COLOR CS
EACH EDSH FORWARD
GETSH HEADING HOME
HT LEFT PC
PE PEN PENDOWN
PENUP PN POS
PUTSH PX RIGHT
SETBG SETC SETH
SETPC SETPN SETPOS
SETSH SETSP SETX
SETY SHAPE SHOWNP
SPEED ST TELL
WHO WINDOW WRAP
XCOR YCOR
WORDS, LISTS & VARIABLES
ASCII BUTFIRST BUTLAST
CHAR COUNT EMPTYP
EQUALP .EXAMINE FIRST
FPUT LAST LIST
LISTP LPUT MAKE
MEMBERP NAMEP NUMBERP
SE THING WORD
WORDP
MATH & LOGIC OPERATIONS
AND COS FALSE
INT NOT OR
PRODUCT RANDOM REMAINDER
RERANDOM ROUND SIN
SQRT SUM TRUE
+ - *
/ < =
>
PROCEDURE CONTROL & EDITING
.CALL COND EDIT
EDNS END IF
OUTPUT OVER REPEAT
RUN STOP TO
TOUCHING WAIT WHEN
INPUT/OUTPUT
CT FS JOY
JOYB KEYP PADDLE
PADDLEB .PRIMITIVES PRINT
RC RL SETCURSOR
SETENV SHOW SS
TOOT TS TYPE
MEMORY & FILE MANAGEMENT
CATALOG .DEPOSIT ERALL
ERASE ERF ERN
ERNS ERPS LOAD
NODES PO POALL
POD PODS PONS
POPS POTS RECYCLE
SAVE SETREAD SETWRITE
Nearly one-third of the Atari Logo vocabulary is devoted to its turtle graphics system. The concept of turtle graphics may seem strange if you’ve been brought up on ATARI BASIC. Instead of PLOTting points on an X-Y grid and using DRAWTOs to describe lines, turtle graphics uses a “drawing pen” which is dragged around the TV screen by an imaginary entity called a “turtle.” You can instruct the turtle which way to turn, how far to move, to pick up a pen, put it down or switch to another pen color. Turtles are easier for novices to grasp than PLOT-type graphics because their movements more closely resemble the familiar act of drawing on a piece of paper.
The turtle graphics in Atari Logo make the Apple, Tandy and Commodore Logos look primitive. By exploiting many of the ATARI’s special hardware capabilities, including player/missiles and color indirection, the Logo cartridge offers a definitive implementation of the turtle graphics concept on an 8-bit micro.
Atari Logo supports four independent turtles and three drawing pens. You can control the speed, direction and absolute positioning of each turtle, individually or simultaneously. The turtle, pen and background colors can be set to any of 128 different hues. The system includes a .SETSCR command that controls the aspect ratio of the turtle’s horizontal and vertical steps, and a WRAP command that determines whether or not turtles will “wrap around” if they move off the edge of the screen.
The turtles in Atari Logo actually look like little turtles. If you get tired of looking at them, you can use the HT (Hide Turtle) command to make them invisible, or type EDSH to enter the built-in shape editor. The editor lets you design and store up to 15 alternate turtle shapes. You can instantly change the shape of a turtle by TELLing it to assume one of your predefined designs. An enterprising Logo programmer could use this capability to create smooth animation and other special effects.
Unlike BASIC, which lets you set up dozens of different graphics modes. Atari Logo allows only three screen formats: full text, full graphics with BASIC mode 7 resolution, or a split-screen mode with five lines of text on the bottom. Old-timers may consider this limitation somewhat restricting. But Logo isn’t designed for hackers—it’s for rank beginners who want to make pictures on their TV set without having to worry about graphics modes or color clocks.
The Atari Logo vocabulary includes a pair of interesting commands for the manipuladon of sound, TOOT and SETENV. TOOT wins the award for best command name of the year. Its syntax is:
TOOT voice frequency volume duration
The “voice” parameter specifies one of Logo’s two sound channels. Why just two, you ask? In order to improve the frequency range and resolution, Logo slaves together sound channels ½ and ¾. The benefit of this technique becomes apparent with the “frequency” parameter, which accepts values directly in Hertz (cycles per second) instead of the arbitrary values used by BASIC. Logo’s extended-range sound system can accurately reproduce frequencies from 14 Hz to beyond the limits of audibility.
TOOT’s “duration” parameter tells Logo how long to play a sound before shutting it off. The maximum play time is 255 “jiffies” or a little over 4 seconds. The SETENVelope command lets you control the decay (rate of volume decrease) of your sound effects.
Like its ancestor Lisp, the Logo programming environment is organized around two fundamental data types: words (atoms) and lists (groups of words). All data and procedure definitions in Logo can be broken down into words and lists. A Logo program is itself nothing more than a list! Logo’s unitized data structure gives the language a number of fascinating capabilities. For example, it’s possible to write a Logo procedure that can compose new Logo procedures based on external data. You can then instruct Logo to execute the procedures it has written—all from within a Logo procedure. Think of the weird things you could do with a program-writing program!
Another idea central to the design of Logo is recursion, or defining a procedure in terms of the procedure itself. This may sound like the computer equivalent of a dog chasing its tail, but in the hands of a skilled user recursion can save hours of programming effort while yielding clean, readable code.
Atari Logo provides a surprisingly broad selection of list-manipulating primitives that can pull apart, analyze and synthesize Logo lists of any type. Once you get tired of playing with turtles, take an afternoon to explore the list-processing and recursive properties of Logo. I think you’ll be pleasantly impressed.
The Logo cartridge includes a built-in procedure editor that works like a mini text-processor. You call the editor with the word EDIT, followed by the name of the procedure you want to work on. Logo automatically clears the screen and displays the latest definition of the specified word. When you exit the EDIT mode (by hitting the ESCape key), Logo dumps the contents of the 3840-byte edit buffer directly into Logo’s workspace, exactly as if you had typed it in manually. A useful side effect of this design is that any Logo commands which appear outside a procedure definition will be executed immediately.
Another feature of Atari Logo that deserves special mention is its “dribble file” capability. Suppose you’re a teacher who wants to keep track of a student’s progress during a Logo session, but you don’t have time to sit and personally monitor his/her performance. You can use Atari Logo’s SETWRITE mode to open a disk file which will automatically record everything the student types on the TV screen. Later, you can step through the entire session (a line at a time, if you like) and see exactly what the student did or didn’t do. Nice.
Still gnashing your teeth over ATARI BASIC’s meaningless error codes? Then check out Logo’s superb error-handling system, which tells the user exactly what went wrong in complete English sentences. “PROCEDURE DOESN’T LIKE X AS INPUT” is a whole lot friendlier than “ERROR – 8” in my book.
The documentation supplied with Atari Logo is well-written and reasonably complete. $99.95 gets you the Logo cartridge along with three books: a 160-page Introduction To Programming Through Turtle Graphics that offers a breezy, entertaining walk through the Logo environment; a 216-page Reference Manual that describes the usage and syntax of each Logo primitive in detail, with numerous useful examples; and a 16-page Quick Reference Guide that does exactly what its title suggests. They’re all fully indexed, thoughtfully laid out and attractively printed to boot. Let’s hope that future ATARI languages follow the example of Logo in this regard.
Atari Logo is a hog-o when it comes to RAM usage. Its basic memory unit is a five-byte cell called a “node.” Each word in a Logo program requires two nodes, plus an additional node for every two letters in its name. Numbers require two nodes apiece; lists use up one node for each element in the list, plus all the nodes required by each element! So the Logo list:
[LOGO EATS RAM FAST]
requires 16 nodes or 80 bytes of storage! Too bad ATARI didn’t use bank-switching to make Logo “look” like an 8K cartridge—the extra 8K of user RAM would have been mighty handy.
Logo is nothing to cheer about when it comes to speed, either. The benchmarks I was able to devise suggested that Logo was at least two or three times slower than ATARI BASIC when it comes to simple repetitions and commands like .EXAMINE (POKE) and .DEPOSIT (PEEK). Recursive procedures make Logo really look like a turtle.
I hasten to point out that Logo was never intended to be a model of speed or memory efficiency. It’s more concerned with teaching than with pinching bytes, and most educational users with a 32K system should never have to worry about running out of RAM. But Logo’s greediness just might get you into trouble if you start getting ambitious with its list-processing and recursive functions. Logo is the best introduction to these concepts you’ll find on an ATARI computer, but serious list-hackers should start shopping for a bigger machine.
No language system is perfect, and Atari Logo is no exception. Although the system appears to be free of any serious defects, I did run across a couple of “undocumented restrictions” the prospective user may want to watch out for.
My biggest gripe is the way the editing cursor “takes off” when you hold down one of the CTRL-arrow keys. Time and time again I found myself backing up the cursor after it had gone sailing past my desired editing point, completely out of control. I also experienced fatal editing lock-ups on more than one occasion. Even the SYSTEM RESET key wouldn’t help me—which was probably just as well, since hitting RESET will erase your Logo program even if you aren’t locked up.
The Reference Manual says that unused or “dead” words can be cleaned out of the system with the RECYCLE command. This is not completely true. If you attach a value to a variable and later edit that variable out of your program, the deleted variable will never go away, even if you write the program out to disk and load it back into Logo from a coldstart! The only way to permanently remove “deleted” variables is to use the ERN (Erase Name) command on the offending words.
I’m happy to report that Atari Logo does include a way to access machine-language subroutines, using the built-in .CALL command. But the manual doesn’t say how to get your routines into memory, where to put them, how to pass data back and forth or how to return to Logo when you’re finished. I suspect that the majority of Logo users will have very little need for machine language, but the info would be nice to have, just in case. And while we’re on the subject of documentation, how about a chart that shows what frequencies to specify with TOOT when you want to play a certain musical note?
The above comments notwithstanding. Atari Logo is one of the most intelligently-conceived and well-executed pieces of software ever published by ATARI. I highly recommend it to parents and educators as a tool for computer education, and to hobbyists interested in learning the fundamentals of list processing and recursive programming. If someone you know has been looking for a reason to buy an ATARI home computer for their family, they need look no further than this little cartridge (and maybe Star Raiders).