LIBRARY OF THE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN no 510.84 74G-75I cop. Z The person charging this material is re- sponsible for its return to the library from which it was withdrawn on or before the Latest Date stamped below. Theft, mutilation, and underlining of books are reasons for disciplinary action and may result in dismissal from the University. UNIVERSITY OF ILLINOIS LIBRARY AT URBANA-CHAMPAIGN 90l 1 3 10 1 2RECD H L161 — O-1096 Digitized by the Internet Archive in 2013 http://archive.org/details/lispcaiimplement749szol POY UIUCDCS-R-75-7 1 +9 f/7/ 7 LISP: A CAI IMPLEMENTATION by Tom Szolyga and A. B. Baskin September 1975 UIUCDCS-R-75-7 1 +9 LISP: A CAI IMPLEMENTATION by Tom Szolyga and A .B . Baskin September 1975 Department of Computer Science University of Illinois at Urbana-Champaign Urbana, Illinois 6l801 ACKNOWLEDGMENT The authors would like to thank the many people who have helped in the preparation of the Lisp implementation on PLATO and in the preparation of this report. The Regional Health Resource Center and the Department of Computer Science provided support for the authors during the preparation of the Lisp compiler and execution package. Al Davis and Mike Tindall answered numerous questions and provided invaluable assistance at all stages of the project. In addition, Al Davis has provided many suggestions and a careful reading of this report. Finally, the authors would like to thank Connie Slovak for typing this manuscript. 1 . INTRODUCTION Lisp is both a formal mathematical language and a programming language. It deals with the expression and evaluation of arbitrary symbolic expressions. As such, it differs markedly from such languages as PL/l and FORTRAN which are primarily suited to numerical processing. Learning the language Lisp thus involves learning much about symbolic data processing. The recursive nature of Lisp contrasts with most other programming languages, even those which allow recursion. Because Lisp is so different from programming languages which are normally presented as introductory material, the authors believe that it is important to provide exposure to Lisp as a programming language. In order to further that goal, the authors have implemented an interactive Lisp compiler and an execution interpreter for the output of the compiler. The Lisp system was implemented as a part of the Computer Assisted Programming System (CAPS) [13] implemented on the PLATO [l] system. The Lisp system implemented on PLATO was designed to provide an adequate tool for learning Lisp. It was never intended for serious problems to which Lisp can be applied. The goal of providing an enhanced learning environment allows some of the problems associated with the implementation of Lisp on PLATO to be simplified. At the same time, the requirement that the system foster the learning of Lisp posed some severe problems for the implementation on PLATO. There were three major goals in the design of the Lisp system on PLATO. The first was that the system should be interactive as much as possible. This represents a radical departure from most implementations of Lisp. Although Lisp compilers do exist, most systems are interpretive with no differentiation between program recognition and program execution. Such systems whether compiler- or interpreter-based provide a batch oriented service. The intent of this system is to provide real time error checking of a Lisp program and as much user interaction at execution time as possible. A second major goal was the inclusion of concise readily available information about Lisp. Ideally, this information should be available at all times, and the use of the summary information should not interfere with the normal use of the system. This is particularly important for Lisp where the number of predefined functions and keywords can be quite large. These 'data sheets' should provide basic information such as normal function execution, error conditions, numbers of arguments, etc. More detailed information about the language can be presented more effectively in a separate CAI sequence which may invoke the system described here to allow the student to try what he has learned. Thus it was not a goal of this system to actually teach Lisp or to provide general information about programming techniques in Lisp. The third and final goal of this Lisp system was to provide good diagnostics. This is particularly Important for any CAI system. Lisp is not well suited to compile time error checking. Since Lisp is so versatile, most structures are syntactically correct even when they are destined to produce an execution error. For this reason, some Lisp systems do not provide extensive error checking until interpretation time when all errors can be caught. The philosophy that was used in this system was to check everything that could be checked before interpretation began. Obvious errors caught here are certain to be more easily understood by a student not familiar with Lisp. Good diagnostics at program interpretation are also a problem. As pointed out by Davis [k], the sites of an execution error and the cause of the error are frequently widely separated. This problem is again emphasized by Lisp. The next three sections will discuss the compiler for Lisp which is used for this system. The final sections will discuss the execution interpreter for Lisp. The interested reader is referred to the Lisp Maintainance Manual [2] for the details of the implementation. None of the details of the implementation will be included here except when necessary to indicate the reasons for certain aspects of the final system. For completeness, a general overview of the translator writing system [13] (CAPS) will be presented. For further information on existing languages and major system components, the reader is referred to the specific papers describing each [3,h,9,ll] . 2. CAPS: OVERVIEW OF A RECOGNIZER It could be argued that all of the currently used compilers in the system are really just recognizers. This is particularly true of Lisp. Because of this, the compiler for Lisp will be referred to as a recognizer to emphasize the fact that it merely tokenizes the source which is then interpreted and does not 'compile' Lisp as some systems do. The basic philosophy of the CAPS system has greatly influenced the implementation of Lisp. The interactive editing provided for Lisp is the same as that provided for FORTRAN and PL/l. It is also a basic feature of the CAPS system that nothing which can be profitably done at execution time should be done at compile time. This implies that character strings which are recognized to constitute numbers are not converted to numbers until execution time. It is also a part of the basic philosophy of the CAPS system that help should always be available. The existing implementations of languages on the system emphasize all of these features. The Computer Assisted Programming System provides FORTRAN, PASCAL, PL/l, COBOL, and now Lisp. Each language implementation emphasizes error detection and diagnostics. There is no attempt at error correction. The student enters into a dialogue with a table driven error system which forces the student to repair the error before he can continue typing in the program. For more detailed information about the error system, the reader is referred to the papers by Tindall [10,11] and Davis [k] . The structure of the CAPS system defines much of the form of any specific compiler implemented on it. The system consists of four main parts. The lexical analysis and the syntactic analysis are carried on by two co-routines. Each lexical token is immediately syntactically parsed and if necessary an error condition is raised. The third component of the system is a set of semantic routines supplied by the language implementer. These routines are invoked by the syntactic analysis as required to process the source program. A student programmer interacts directly with the language editor which is the final component of the system. In the remainder of this section, a discussion of the major aspects of the CAPS system will be presented. A more detailed discussion can be found in Wilcox [Ik] . 2.1 LEXICAL ANALYSIS Lexical analysis is performed by a table driven finite state machine model of a lexical processor. This processor proved particularly simple to implement for Lisp and appears to offer a most satisfactory approach to the definition of a lexical processor. The lexical processor provides one character of lookahead which proved sufficient for Lisp. There is no auxiliary storage associated with the lexical processor, so it is necessary to use states to remember specific characters. This proved a limitation for Lisp and will be discussed in the next section. 2.2 SYNTAX ANALYSIS The model for the syntax analysis is that of a virtual computer which executes machine instructions specified by the compiler author in the syntax source program [9l- This program is assembled into a set of tables which drive the parser and the automatic error analysis system. The use of a machine language in which the language implementer must code his specification of the recognizer is quite different from other translator writing systems (TWS) . There is no need for the language implementer to formulate a precise grammar for the language to be recognized. On the other hand, the initial specification of the syntax source can be expected to be more difficult than the specification of BNF or an LR grammar for the same language. This added work results from the need for the language implementer to actually program the recognition process. As a positive side effect of the programming process, it is possible to govern when error conditions are raised and to better control the recognition of specific errors at the earliest possible moment. This is particularly important in a system whose primary goal is good error diagnostics . Major constructs in the language to be recognized are recognized by separate subroutines in the syntax source. It is possible to give these routines names and refer to the global constructs which they represent in the error dialogue. This would correspond to the ability to single out special non-terminals in the grammar -- a feature infrequently allowed in TRS systems based on grammatical descriptions of compilers [6] . The subroutines in the syntax source are allowed to use recursion when needed. This allows a recursive top down process to be used for Lisp which is particularly simple to implement and under- stand. The use of recursion allows the language implementer to avoid some of the bookkeeping that would otherwise result. In summary, the method used for the specification of the syntax analyzer in this TWS system is more cumbersome than methods based on grammatical approaches to the specification, but it is a more versatile method of specification, since it allows the language implementer to specify the most convenient time to raise an error condition or invoke a semantic routine. In addition the use of recursive descent allows the greatest ease of programming available. 2.3 SEMANTIC ANALYSIS The CAPS system provides no automatic operations which can handle all of the semantic checking done by such languages as PL/I and FORTRAN. The semantic checking must be supplied by the language implementer in the form of TUTOR [8] subroutines which can be invoked by the syntax analyzer at appropriate times. The semantic routines can be expected to do such things as check all labels used in a given program to see that all labels which are referenced are also defined. This sort of check cannot be effectively integrated into the syntax source specification. Since it was possible to implement Lisp without the use of any semantic routines, the semantic routines will not be discussed further . 2.k EDITOR The final component to the CAPS system is the system editor. The control keys may be chosen by the language implementer, and the function of the various control keys may be changed to suit the particular language. The editor is tied closely to the compiler system. When the cursor is moved to the right all new tokens are compiled and no tokens may be input after an error is raised. When • the cursor is moved to the left, the compilation process is reversed. Thus at any given time the tokens to the left of the cursor constitute a syntactically correct part of a program. The fact that this editor responds to each keystroke allows it to monitor the input program constantly for syntactical and lexical errors . 3. LISP RECOGNIZER The recognizer for Lisp has the structure outlined above for languages in the CAPS system. In this section the basic structure of the Lisp compiler will be discussed. This compiler represents a radical departure from all Lisp systems known to the authors. It provides a level of interaction and diagnostics which should prove most helpful to the student of Lisp. 3.1 LEXICAL ANALYSIS OF LISP The lexical analyzer (lexi) for this implementation of Lisp is a simple finite state machine. The machine requires fourteen states and uses twelve classes of input characters. Despite the simplicity of Lisp, it was necessary to restrict the convention for 'unusually spelled' atom names. Historically, the convention has been that an arbitrary 8 sequence of characters bounded by a delimiter could be the print name for the 'unusually spelled' atom. The construct $$ was used to signal such a special atom name and the first character following the $$ would be the delimeter. Thus, only the delimeter (which could be chosen arbitrarily) was excluded from the name. With a pure finite state machine approach, such freedom could not be allowed. It would be necessary to have a state in the finite state machine for each character in the input alphabet. In order to overcome this problem, the two delimeters ' and " are the only two delimeters allowed by the lexical analysis. It is interesting to note that if lexi had some small amount of local memory, this problem could be easily solved. Such memory could consist of several registers and transitions could be made based on comparisons between the input symbol and a register rather than just based on the input symbol. This capability does not increase the power of the machine, because a finite state machine with a larger number of states could do the same thing. What this does do is significantly reduce the complexity of the statement of the lexical process. Because of storage constraints the interpreter uses only integers; lexi recognizes the special symbols: , . ( ) and the complex symbols for atom names and signed and unsigned numbers. An unusual feature of the lexical processor is its handling of delimeters. Because the lexical and syntactic processors in the CAPS system use different memory maps and because memory maps can only be changed on timeslice boundaries, it is important to minimize the transitions between lexi and the syntax analyzer (syna) . In order to avoid one invocation of syna and in order to simplify syna, lexi processes delimeters in lists. This is quite trivial when the deliraeter chosen is a blank, but when the comma is chosen it is necessary for lexi to require that the next non-blank following the comma not be another comma. Such restrictions are easily handled by the finite state model for lexi . As an extension to normal Lisp syntax, lexi allows comments delimeted by /* and */ as in PL/l. The extension was included in order to encourage students to use comments to make their Lisp programs more readable. The ability to use leading and trailing blanks freely in any situation should also aid in readability of Lisp programs. 3-2 SYNTAX ANALYSIS FOR LISP As mentioned earlier, the syntax analysis for Lisp is controlled by the syntax source which provides the pseudo-instructions for syna. Although there exists a simple grammar for valid Lisp syntax [5,12], this grammar does not provide an effective diagnostic for all errors. Because of the generality of the definition of Lisp, certain program structures which must lead to execution errors are not generally recognized as errors until execution time. Where possible, the Lisp system on PLATO recognizes errors at the earliest possible point. This means that the student is not allowed to make such errors as: invoking an undefined function or supplying the wrong number of arguments to a function call. In addition, complex structures such as lambda definitions and the prog feature are required to be of the proper form. All of the errors detected as the student enters the program in the Lisp editor/ recognizer would be detected at run time, but their detection at the earliest possible moment offers a level of interaction not found in batch oriented Lisp systems. The frames in Figure 1 show the diagnostics given 10 FILE - workspace LISP WORKSPACE (4 4- new) SPRCE - 28« define (( (test (lffmda, 1 Figure la. Compiler marking of an invalid use of a keyword. At this point student may press term and enter either of the keywords defined or lambda for a more detailed discussion of either. 11 FILE = workspace LISP JJORKSPRCE (44-new) SPRCE - 289 define { ( (test ill arnJa) ********** Possible Correction *****»*#*.* iME) ° r dl^D to fix, Rep 1 ace [J [with "1 ambda " . Press (help) for a different suggestion. FILE « workspace LISP WORKSPACE (44 -new) SPRCE - 289 define (( (test (Jlamdi t*********ERROR********** $mx) or |RiR to fj x< This literal atom is not permitted here. Press fHELPj for more information. F ^-^ = w or kspace LISP WORKSPACE (4 4 -new) SPRCE = 289 lefine (( (test fillamda * » »»*»»» a Pqq s i b 1 e Correction ********** ^ro? j or (crrseJ to fix, Replace | | with a lamboa function definition. Press (HjiLP! for a different suggestion. Figure lb. Successive frames available to the student by pressing help. 12 to a student after the error boxed in Figure la is entered. The frames shown in Figure lb show the information available to the student by pressing help successively. 3-3 LISP SEMANTICS As mentioned earlier, the CAPS system provides a set of up to 20 semantic routines which can be defined by the language implementer to perform special purpose language dependent operations . The Lisp recognizer does not make use of any semantic routines. The primitive operations supplied in the pseudo -ma chine of the syntax analyzer were sufficient for all compile time checks in Lisp. h. RECOGNIZER: NORMAL USE and DIAGNOSTIC MESSAGES The recognizer for Lisp implemented in the CAPS system differs significantly in intent from most implementations of Lisp. At every keystroke an effort is made to restrict the student to valid basic syntax and to do as much compile time checking as the generality of Lisp allows. As an example of this, a compile time check is made whenever an atom is used as a function. If the name is not the name of a system function or a user defined function an error is raised. Figure 2a shows such an error raised when the student tried to use the function 'error'. Figures 2b through 2f show the various stages of the subsequent error dialogue with the student. The number of arguments supplied to a Lisp function can be easily confused by someone unfamiliar with Lisp or a specific implementation. It is a simple matter to check the number (and in some cases nature) of arguments supplied to a function at compile time. Appendix A shows an example of a function called 'cons' which requires two arguments. The various frames 13 FIl E = workspace LISP WORKSPACE (44- new) SPACE = 281 car ( (cdr (a b c d) ) ) error; ( Figure 2a. An error raised when the student tried to invoke the undefined function error. FILE = workspace LISP WORKSPACE (44 -new) SPACE = 281 car ( (cdr (a b c d) ) ) error **********ERROR**** ****** [sack] or (i£isg) to fix. This literal atom is not permitted here. Press (help) for more i n format i on . Figure 2b. The first error message pointing out that error is a literal atom (and not a function name) . FILE = workspace LISP WORKSPACE (44-new) SPACE = 281 car ( (cdr (a b c d) ) ) srroi ********** Possible Correction ********** |5ck) or £rbj€) to fix, Insert a level zero function call in front of J. — — — — — — — — — — — — _ _ _ — _ -J — ac — xtf _ Press (help) for a d i f f erent suggest i on . Press EIT^elp) to examine a level zero function call. Figure 2c. At this point the student is allowed to choose either a different suggestion or more information about functions. At this point shift-help was selected. Ik FILE = work space LISP UJORKSPfiCE (44-new) SPACE car((cdr (abed))) error * ********* Possible Correction ********** (back) or (EJusf) to fix. Replace | | with a function. Press (help) for a d i f f erent suggest i on . Press glT^HELP) to see a legal function. Figure 2d. At this point the student is told that a function name and not a literal atom (error) is required. Shift-help is now selected. FILE = workspace LISP UJORKSPfiCE (4 4 -new) SPACE = 2 car((cdr (abed))) error ********** Possible Correction ********** £ack) or HD to fix. Replace | | with a function 2 c _? r _,'._ _ _ _ _ _ Press (help) for a different suggestion. Press C__-_^__B to see another legal function. FILE = workspace LISP UJORKSPftCE (44-new) SPACE car ( (cdr (a b c d) ) ) error ********** Possible Correction ********** £«*) or £rk| to fix, Replace | | with a function ^ c _^^«_ "Press FeIp) for a different suggestion. Press GUThelp) to see another legal function. Figure 2e. The student may see a large number of example predefined functions. Both examples of functions help was pressed. 15 FILE = workspace LISP WORKSPACE (4 4 -new) SPRCE * 231 :ar ( (cdr (a b c d) ) ) rroi I******** Possible Correction ********** (back) or (errs;) to fix, Replace | | with an user defined function. Press (help) for a d i f f erent suggest i on . Figure 2f. At this point the student is told to replace error with a user defined function. At this point it is assumed that the student has understood that the function error must be defined and the help dialogue ends. A large number of suggestions can still be made after this point if necessary. 16 in Appendix A show the error raised when an argument is missed and the suggestions made to the student to repair the error. At this point, it is appropriate to consider the kind of error messages provided by the system. The error diagnostic package was provided by Tindall and is described in [11]. Since the recognizer is entirely table driven and behaves like a simple machine, it is possible to view an error condition as an abnormal state which the machine is not allowed to reach. When such a state is reached, an error condition is raised and the CAPS error analysis system takes over. The error system looks at the state of the recognizer and suggests changes to the student which will remove the recognizer from the error state and leave it in an allowed state. The suggestions are made closest to the token in the input causing the error and alternate suggestions are made moving away from the site of the recognition of the error. This technique of error analysis has proved adequate for the CAPS Lisp system, but has required numerous changes to the syntax specification during development to facilitate appropriate error messages. The errors in Figure 2 and Appendix A could have been diagnosed with more precise error messages. However, this would have required that the error messages be "hard-coded" in the body of the recognizer. This facility is provided in CAPS, but since it bypasses the automatic error system, alternate suggestions would be impossible. As it is, Tindall 's system proves quite general and is sufficient for more languages than just Lisp. This means that a trade off has been made; the student may be forced to look at two or more suggestions for fixing an error, but on the other hand, (l) the Lisp implementers have been relieved of the burden of construcing the error diagnostic service and (2) the diagnostic messages will change automatically with the future changes in the recognizer. 17 Finally, Appendix B shows the frames associated with a typical interaction with the recognizer. The student is presented an index of allowed options at each point where a decision is required and the sample program shown has been executed. More detailed information about the execution of Lisp programs will be presented in the sections which follow. 5. EXECUTION PACKAGE 5.1 DIFFERENCES BETWEEN LISP AND Pl/l OR FORTRAN 5.1.1 INCOMPATIBILITY The execution package for Lisp is written as a separate self- contained Tutor lesson. The lesson, LISPRUN, accepts a program's symbol table and intermediate text from the CAPS system. Thus, Lisp is compatible with the current CAPS system. Although an effort is being made to produce a code generation-execution package for PL/l and FORTRAN, no attempt has been made to make Lisp compatible with it. The reason for the incompatibility is that Lisp is an interpretive language. Lisp compilers do exist, but most Lisp systems process Lisp interpretive] y. A code generator for Lisp would be radically different from one for PL/l or FORTRAN. For example, the common Lisp function 'car' involves following a pointer from one Lisp cell to another Lisp cell. FORTRAN has no use for such an operation. Thus a separate code generator or at a minimum, a different set of opcode-operation look-up tables would be needed for Lisp. Instead of introducing the extra overhead into the code generator, it was decided to use the present approach of simply passing a tokenized version of the source to the execution package . 18 5.1.2 PROGRAM INTERPRETATION In the current CAPS system, each language has its own execution package. In all the current languages, the source text is interpreted at execution time. No structure is built from the intermediate text; the intermediate text and the symbol table are the only structures used to execute the program. This method has short- comings. Each token must be examined to determine if it is a command such as GO TO, an operand or a punctuation mark. Also, the same intermediate text must be interpreted on every pass through a loop. This process can be very time consuming. In the Lisp execution package, it was decided to process the intermediate text just once, and build an internal representation of the Lisp program. A Lisp program is nothing more than a string of s-expressions. Input to the interpreter from the student's keyboard consists to the same type of s-expressions. If the input stream can be switched from the student's keyboard to the intermediate text, the Lisp interpreter can read the intermediate text and build a list structure in the same manner as data is read from the student's keyboard and built into a list structure. The interpreter now has to deal with one type of data structure, lists, instead of lists and intermediate text. Execution is therefore much more efficient. 5-1.3 USER DEFINED FUNCTIONS In the CAPS system, none of the currently implemented languages allow user defined functions. User defined functions are the most powerful feature of Lisp. Without such functions, the user would be allowed to enter only one Lambda expression and evaluate it. This would 19 make a very poor subset of Lisp. In Lisp, the DEFINE pseudo- function and the DEFLIST psuedo- function create the structure to define a function. In our implementation of Lisp, only the DEFINE function is supported. This is because DEFLIST puts an arbitrary property on an atom's property list. In our implementation, atoms do not have property lists. This limitation is forced upon the interpreter by the CAPS system symbol table. Instead of a property list, atoms may have one of 5 specific properties. One property indicates that an atom has an applied value and resembles an ordinary variable in PL/l or FORTRAN. The other four properties indicate specific types of functions. The four types of functions are: built-in subroutine, built-in forms subroutine, user defined Lambda expression function, and user defined forms Lambda expression function. (A forms subroutine or function receives its arguments unevaluated.) Of the four types of functions, the forms Lambda expression function is not implemented because it requires the use of DEFLIST to create the structure to define it. Otherwise, the user can define an arbitrary function of any number of arguments which returns any type of result. No other language in the CAPS system allows the user this much freedom in defining functions. J.l.k RECURSION Lisp is a very recursive language by nature. Functions can be defined using the PROG feature and be non-recursive, but the PROG feature was tacked onto the original definition of Lisp as an after -thought. Since recursion is so essential to Lisp, it was decided to support recursion to a depth limited only by available storage . The Tutor DO statement could not be used to invoke functions because it limits the 20 recursion depth to 10 levels. Instead, a recursive calling scheme was implemented using GOTO and a stack. Each entry point in the interpreter was assigned a unique integer number. A recursive call consists of a GOTO to the unit CALL followed by a new entry point. The unit CALL expects two arguments: the entry point number of the entry point following the GOTO and the entry point number of the desired unit. CALL pushes the return entry point number onto the stack and does a computed GOTO to the desired unit. A return from a recursive unit consists of simply a GOTO the unit RETURN. RETURN pops the stack and does a computed GOTO using the value popped off the stack as an index into a list of all entry points to return to the calling unit. Storage limitations limit the recursive call depth to about 100 levels which is sufficient for most programs, since the CAPS editor limits programs to 32 lines. 5-1.5 DATA STRUCTURES The data structures supported by FORTRAN, PL/l and Lisp are very different. FORTRAN supports numbers and arrays of numbers. Characters can be handled only by packing them into numbers. PL/l supports numbers, arrays of numbers and character strings. Numbers must be of type FIXED DECIMAL and character strings must be of fixed length. Lisp supports atoms and arbitrary list structures. There are two types of atoms within the Lisp system: literal atoms and numeric atoms. Literal atoms consist of a character string of arbitrary length beginning with a letter and made up of alphanumeric characters. (There is also a special form of literal atom called an unusually spelled atom. This literal atom begins with "$$ ' " followed by any number of any 21 characters, terminated by the character '"".) A literal atom can be assigned an arbitrary value consisting of any valid Lisp data structure. A numeric atom is an integer within the range 1-2**21. .2**21-1. The size or numbers is limited by the size of a Lisp cell: 22 bits. Larger numbers could be supported by allocating numbers in a special number cell space instead out of list cell space but this would make garbage collection more difficult. Lisp list structures are not limited to any form. They may be linear, circular, tree structured or nested to any depth. The only limitations on list structures are things like a circularly linked list cannot be printed. 5.1.6 PERFORMANCE Note: In the following examples, wall clock time was used since Lisp does not provide a measure of cpu time. The wall clock times represent an average of several trials and all trials were performed at the same time of day, so the affects of system loading should not be too significant. 5-1.6.1 NUMERICAL EXAMPLE Calculating the factorial of a given number was chosen for the numerical example. The program was written in PL/l using a "DO" statement. In LISP, recursion was used since recursion is much easier to program than iteration. The PL/l program is as follows: TEST: PROC OPTIONS (MAIN) ; DCL (I, FAC, RESULT) FIXED DECIMAL; GET LIST (FAC) ; RESULT = 1; DO I = FAC TO 1 BY -1; RESULT = RESULT * I; END; PUT LIST (RESULT) ; END TEST; 22 The program executed in 13 seconds wall clock time. There is a slight difficulty in understanding this program. FAC equal to zero is treated as a special case; the "DO" loop is not executed. This may he hard for a new user of PL/l to understand. The LISP program is as follows : define (( (factorial (Lambda (x) (cond ((zerop x) l) (t (times x (factorial (subl x))))))) (test (Lambda () (print (factorial (read))))) )) test () The program executed in 20 seconds wall clock time. There are no special cases in the LISP program. It is a straightforward recursive function. The only difficulty in understanding the program may be understanding recursion itself. This is not a weak point of the Lisp system; recursion is one of the most powerful features of LISP. A new student of LISP should master recursive techniques as soon as he under- stands the basics of the language. 5.1.6.2 LIST MANIPULATION EXAMPLE Reversing the words in a sentence was chosen as the list manipulation example. However, this program proved too difficult to write in this PL/l implementation. Instead, the PL/I program simply reverses the letters in an 8 character word. The LISP program does reverse the order of the words in an arbitrary sentence. The PL/l program is as follows: TEST: PROC OPTIONS (MAIN) ; DCL (OLD, NEW) CHAR (8), I FIXED DECIMAL; GET LIST (OLD) ; NEW = " ; DO I = 1 TO 8; NEW = NEW ! ! SUBSTR(0LD,9-I, l) ; END; PUT LIST (NEW) ; END TEST; 23 The program, as simple as it is, required 35 seconds wall clock time to execute. There is nothing difficult to understand about this program. It is a straightforward application of the function SUBSTR. The LISP program is as follows: define (( (flip (lambda (x) (cond ( (null x) x) (t (list (flip(cdr x)) (car x)))))) (test (lambda (.) (print (flip (read))))) )) test () The LISP program is easy to understand. The function FLIP recursively calls itself with CDR X as its argument until X is nil. FLIP then strings all the CAR's of X together into the resulting list. The program executes in 30 seconds wall clock time. This is roughly the same amount of time required to execute a much simpler PL/l program. It should be noted there is a built-in LISP function, REVERSE, which could be used to replace the function FLIP. It would be an unfair comparison to use REVERSE and compare the results to PL/l. However, the large number of built-in functions make LISP an easier language to program. 5-2 DIAGNOSTIC AIDS 5.2.1 TRACING In the current Lisp interpreter there exist two forms of tracing: Function tracing and Argument tracing. Function tracing prints the name of each function as it is being called. Argument tracing prints the argument list passed to a function when the function is called. These modes of tracing add little overhead to the interpreter. Since all calls within the interpreter must go through the unit CALL, a central point to check the trace mode already exists. If the mode is Function 2k tracing, then a massive WRITEC using the desired function number as an index to a list of all the function names in the interpreter is done. When a function is called, arguments are passed to the function on the top of the interpreter stack. Thus if the mode is Argument trace, the top element in the stack is printed to display the arguments. These two modes of tracing are easy to do and require little extra code in the interpreter. However, they do not provide the first time user of Lisp with a good feel for what is going on within the interpreter. Some alternate ways of tracing have been suggested. One method is to box the current function being executed. When a user function is called, a box would be put around the entire definition. As execution proceeds through the function, each built-in function would be boxed as it was invoked. The disadvantage to this method is that information must be added to the internal representation of the program to locate specific areas on the screen. If this method of tracing was implemented, it would probably be better to interpret the intermediate text, since it provides information on screen locations. Another method of tracing would be to display only the function being executed on the screen. When entering a user function, the function is displayed on the screen. As execution proceeds through the function, the built-in functions are boxed as above. When a user defined function is encountered, it is boxed and then the screen is erased, and the definition of the new function is displayed. When returning from a user defined function, the screen is erased and the definition of the calling function is again displayed. This method has the same disadvantage as the previous one -- locating a functions definition within the intermediate text. 25 The current method of tracing resembles the methods used in many batch Lisp systems. It is not really adequate for a PLATO based CAI lesson. PLATO makes drawing boxes and displaying text so easy that the alternate methods of tracing mentioned above should be implemented. 5.2.2 ERROR DETECTION There are two areas for error detection within the execution package. The first is PLATO execution errors; the second is Lisp errors. Clearly, any CAI lesson should not give a PLATO execution error if the user makes a mistake. This has special meaning for Lisp. Since Lisp deals with lists, a common piece of data within the interpreter is a pointer to a list. The list cell space is implemented as a segmented array. A subscript of or minus will give an array error. Thus every time a pointer is used, it must be checked for a positive range unless it can be assumed the pointer is correct. If there is any possibility that the pointer came from the user, this assumption cannot be made. Another common error is to divide by zero. This is much easier to check. Division is done only in two functions, so the checking needs to be done only twice. The important point is that all effort must be made to prevent PLATO execution errors. The other area for error detection is Lisp errors. It is easy to detect a fatal error in Lisp. For example, if the function CAR receives an atomic argument, this is a fatal, error. The present implementation reports the exact error cause to the user. In the above example, the user would be told: CAR RECEIVED AN ATOMIC ARGUMENT. In 26 this case, such an error message might convey enough information to the user to fix the problem. However, the error message — STACK OVERFLOW — (which the student receives if he exceeds the fixed stack size of 150) may not. The problem here is that the message does not tell whether the user went into an infinite loop or the user just exceeded the recursion depth of the interpreter. This problem is very difficult for the interpreter to solve and is thus left to the user to determine . 5.2.3 EXECUTION- TIME ERROR ANALYSIS AND REVERSE EXECUTION In Lisp the site of a programming error can be widely separated from the resulting execution error. Problems of this nature have been demonstrated by Davis [k] for PL/I. In order to provide good diagnostic advice for the student, it is necessary that the site of the error be found. The method used for PL/l involves the use of reverse execution from the execution error to possible sites of the error. As each candidate is pointed out to the student, an appropriate corrective action is suggested. Although reverse execution works well for non- recursive structures in PL/l, it does not work easily for Lisp where garbage collection may occur during execution. Because of the difficulties associated with reverse execution in Lisp, no diagnostic advice is presented to the student beyond the normal Lisp execution error messages. It might be possible to partially overcome this and make use of the techniques used by Davis if the concept of reverse execution were slightly modified. In order for reverse executior to take place it is necessary to maintain a history stack which records previous values of variables when they are changed. Strictly speaking, only storage locations which are not currently in use and are not 27 referenced by the history stack may be garbage collected. It can be shown that when it becomes necessary to garbage collect, all of the available storage is either in use or pointed to by the history stack. Thus, garbage collection must not be performed if reverse execution is to be envoked at a later time. One approach to reverse execution in Lisp would be to maintain the history stack as a local history of execution. Only 'recent' transactions would be recorded. This is equivalent to using the history stack as a fixed length queue. When the queue fills up the oldest entries in the queue are deleted and the storage pointed to by these entries can be garbage collected. Thus, the length of the queue sets the size of a 'window' on the execution of the program in which good diagnostic messages can be generated. If the site of the programming error is outside the window a good diagnostic message may not be generated. There are two contradictory demands on the length of the history queue. First, it should be long to provide a large window and thus a high probability of including the site of the programming error. Second, it should be short to keep a reasonable amount of storage available for garbage collection. Some of the items that are essential to keep on the history stack are pointers to user defined functions, pointers to the association list, pointers to applied values and pointers to function argument lists. Each time a user defined function is entered, a pointer to the function's definition must be pushed onto the history stack. Also at this point, a pointer to the current association list must be pushed onto the history stack. The association list contains the values of all dynamic variables. To reverse execute a function, the values of all dynamic variables must 28 be saved. Changes to a variable's Applied value or to its value on the association could be handled the same way PL/l handles assignments Function Argument lists should be saved so that the list can be presented to the student when the function call is encountered while reverse executing. 29 References [1] Albert, D. and D. L. Bitzer, "Advances in Computer Based Education/' Science , Vol. 167 (20 March 1970), PP- 1582-1590. [2] Baskin, A. B., and Szolyga, T., "Maintainance Manual for LISP on the CAPS System, " interdepartment communication — available from CAPS staff. [3] Barnett, R. D., "An Interactive Cobol System for Plato," UIUCDCS-R-75-685, Department of Computer Science, University of Illinois at Urbana- Champaign (January 1975)- [k] Davis, A. M., "An Interactive Analysis System for Execution- Time Errors," Ph.D. Thesis, UIUCDCS-R-75-695, Department of Computer Science, University of Illinois at Urbana-Champaign (January 1975) • [5] McCarthy, J. et al., LISP 1.5 Programmer's Manual , M.I.T. Press, Cambridge, Massachusetts, 1973 • [6] McKeeman, W. M., Horning, J. J., and Wortman, D. B., A Compiler Generator , Prentice-Hall, Inc., Englewood Cliffs, N.J., 1970. [7] Nievergelt, J., Reingold, E. M., Wilcox, T. R., Watanabe, D. S., Friedman, H. G., Montanelli, R. G., and Pradels, J., "ACSES: An Automated Computer Science Education System, " to appear in Proc . 197^ National Computer Conference, AFIPS Conference Proceedings, Vol. k-3, AFIPS Press. [8] Sherwood, B. A., The TUTOR Language , Computer- Based Education Research Laboratory, University of Illinois, Urbana, 197 1 +- [9] Tindall, Michael H., "An Interactive Table-Driven Parser System," Master's Thesis, UIUCDCS-R-75-7^5, Department of Computer Science, University of Illinois at Urbana-Champaign (January 1975) • [10] , "Table-Driven Compiler Error Analysis," Ph.D. Thesis Proposal. [11] , "An Interactive Compile-Time Diagnostic System," Ph.D. Thesis, UIUCDCS-R-75-7i4-8, Department of Computer Science, University of Illinois at Urbana-Champaign (October 1975) • [12] Weissman, C, LISP 1.5 Primer , Dickenson Publishing Co., Belmont, California, 19W- [13] Wilcox, T. R., "The Interactive Compiler as a Consultant in the Computer Aided Instruction of Programming, " Proceedings of the Seventh Annual Princeton Conference in Information Sciences and Systems, March 1973- [l4] , "An Interactive Table-Driven Diagnostic Editor for High Level Programming Languages," to be published. 30 Appendix A ILE = workspace k (s 1 )} L I SP WO 3KSPACE (44- new) 31 SFACE * 29 3 ILE = workspace L I SP WORKSPACE ( 4 4 - new) SPRCE = 2 93 >ns (50 t » * * * * * * *ERROR* * * * * * * * * * "his right paren is not peiTnitted here. Press (help) for more information. (back) or |err|| to Hx. ILE =» workspace LISP WORKSPACE (44-new) >ns (50 SPACE « 293 [******** Possible Correction ********** {back) or ?ep 1 ace with a dot. Press (hel^ for a d i f f erent suggest i on , to fix, FILE = workspace LISP WORKSPACE (44-new) SPACE « 29 cons (50 ********** Possible Correction **** ***** * (back) or fcfinst) to fix. Insert a s-e> press ion in front of | | . Press (help) for a d i f f erent suggest i on . Press £T II helf] to examine e s-expression. FILE = workspace LISP WORKSPACE (4 4- new) SPACE » 29 cors (50 ********** Possible Correction ********** $hcz) or fossE) to fix. Insert a left paren in front of [ | . Press Ikzlp) ^or a different suggestion. FILE = workspace LISP WORKSPACE (44-new) SPACE * 29 cons (50 ********** Possible Correction ********** (back) or Erbse) to fix. Insert a predefined atom in front of I | . Press Helij for a different suggestion. 33 FILE » workspace LISP WORKSPACE (44-new) SPRCE » 293 ons Bs) ********* Possible Correction ********** (Eftcx) or piiE) to fix. Insert e left poren in front of | | . Press (hilp) for a different suggestion. 'ILE = workspace LISP WORKSPACE (44-new) SPACE = 293 3ns (5) ********* Possible Correction ********** (emck) or |rH) to fix, Replace j with a function "car". Press ij£LP) for a different suggestion. "ILE = workspace LISP WORKSPACE (44-new) SPACE - 293 >ns (5) >»»»*»»» * Pos sible Correction ********** E^ck) or jfRJJH) to fix, Replace | [ with a function "cdr". Press (help) for a different suggestion. 3h FILE - workspace LISP WORKSPACE (44 -new) SPACE - 293 cons (j|J) ********** Pcssible Correction »♦♦»♦ »»»♦♦ (back) or Ekme) to fix. Insert an integer atom in front of J. Press teifl for a d i f f erent suggest i on . FILE * workspace LISP WORKSPACE (4 4- new) SPACE « 293 cons © ********** Possible Correction ♦»♦♦♦♦♦ »»» (b eck) or ^Hg) to fix. Insert a predefined atom in front of | | . Press Help) for a different suggestion. FILE « workspace LISP WORKSPACE (4 4 -new) SPACE « 293 cons © ********** Possible Correction ********** £ack) or fra|§ to fix. Insert a literal atom in front of I 1. »_„__.— — — — .— — — — — — — ' 1 MT — — —. — —. — — — — Press Heu3 for a different suggestion. 35 FILE » workspace LISP UJORKSPRCE (44-new) SPRCE « 29 3 :ons (50 »*****»** Possible Correction **** ***** * HH^I or H^Z) to fix. Insert a literal atom in front of | | . Press (h^ip) for a d i f f erent suggest l on . FILE * workspace LISP UJ03KSPRCE (44-new) SPRCE = 293 :ons ,,tr ?*»»**««** Possible Correction ********** ( Eftowj or dH?) to fix. Insert a s-expression in front of | | . | . Press hfLPj for a d i f f erent suggest i on . FILE « workspace LISP WORKSPRCE (44-new) SPRCE « 293 x>ns © >********* Possible Correction ** ***** *** |ack) or H^ to fix. Insert a left paren in front of | J . Press Help) for a different suggestion. 36 Appendix B 7 Jl •mm 1 o 38 » §3* § c a id -* Q. u t- "- 1 <~ U ft O X M ■M -J ft- m i. u 3 3 C <~ $ 9 4-» W M M M «u '■* W •<* tjfl Wl •— < V ■— • c>c>c>cc w (d w UULJLJUJUUU W > W ^GRAPHIC DATA r 1. Report No. UIUCDCS-R-75-7 1 +9 3. Recipient's Accession No. ind Subt it le LISP: A CAI IMPLEMENTATION 5. Report Date September 1975 6. or(s) Tom Szolyga and A. B. Baskin 8. Performing Organization Rept. No. Muting Organization Name and Address partment of Computer Science iversity of Illinois at Urbana- Champaign bana, Illinois 6l801 10. Project/Task/Work Unit No. 11. Contract/Grant No. >n--oring Organization Name and Address partment of Computer Science iversity of Illinois at Urbana- Champaign bana, Illinois 6l801 13. Type of Report & Period Covered 14. plcrruntary Notes s paper outlines the structure of a student oriented implementation of Lisp the PLATO [l] system. The basic design criteria and the form of the diagnostic piler and execution interpreter are presented. The PLATO implementation affords igh level of diagnostic advice for the student of Lisp. Examples of compilation execution diagnostic messages are presented as well as a typical sample student eraction. 1 Words and Document Analysis. 17a. Descriptors I, Lisp, errors tntifiers /Open-Ended Terms JSATI Field/Group ilabil lty Statement 19. Security Class (This Report) UNCLASSIFIED 20. Security Class (This Page UNCLASSIFIED 21. No. of Pages 22. Price TIS-35 ( 10-70) USCOMM-DC 40329-P7 INSTRUCTIONS FOR COMPLETING FORM NTIS-35 (10-70) (Bibliographic Data Sheet based on COSATI Guidelines to Format Standards for Scientific and Technical Reports Prepared by or for the Federal Government, PB-180 600). 1. Report Number. Each report shall carry a unique alphanumeric designation. Select one of the following types: (a) alpha- numeric designation provided by the sponsoring agency, e.g., F AA-RD-68-09; or, if none has been assigned, (b) alphanu- meric designation established by the performing organization e.g., FASEB-NS-87; or, if none has been established, (c) a Iphanumeric designation derived from contract or grant number, e.g., PH-43-64-932-4. 2 Leave blank. 3. Recipient's Accession Number. Reserved for use by each report recipient. 4- Title and Subtitle. Title should indicate clearly and briefly the subject coverage of the report, and be displayed promi- nently. Set subtitle, if used, in smaller type or otherwise subordinate it to main title. When a report is prepared in more than one volume, repeat the primary title, add volume number and include subtitle for the specific volume. 5- Report Date. I ach report shall carry a date indicating at leas.t month and year. Indicate the basis on which it was selected (e.g., date of issue, date of approval, date 01 preparation. 6. Performing Organization Code. Leave blank. 7. Author(s). Give name(s) in conventional order (e.g., John R. Doe, or J.Robert Doe). List author's affiliation if it differs from the performing organization. 8. Performing Organization Report Number. Insert if performing organization wishes to assign this number. 9. Performing Organization Name and Address. Give name, street, city, state, and zip code. List no more than two levels of an organizational hierarchy. Display the name of the organization exactly as it should appear in Government indexes such as USGRDR-I. 10. Project/Task Work Unit Number. Use the project, task and work unit numbers under which the report was prepared. 11. Contract Grant Number. Insert contract or grant number under which report was prepared. 12. Sponsoring Agency Name and Address. Include zip code. 13. Type of Report and Period Covered. Indicate interim, final, etc., and, if applicable, dates covered. 14- Sponsoring Agency Code. Leave blank. 15. Supplementary Notes. Enter information not included elsewhere but useful, such as: Prepared in cooperation with . . . Translation of . . . Presented at conference of . . . To be published in . . . Supersedes . . . Supplements . . . 16. Abstract. Include a brief (200 words or less) factual summary of the most significant information contained in the report. It the report contains a significant bibliography or literature survey, mention it here. 17. Key Words and Document Analysis, (a). Descriptors. Select from the Thesaurus of Engineering and Scientific Terms the proper authorized terms that identify the major concept of the research and are sufficiently specific and precise to be used as index entries for cataloging. (b). Identifiers and Open- Ended Terms. Use identifiers for project names, code names, equipment designators, etc. Use open-ended terms written in descriptor form for those subjects for which no descriptor exists. (c). COSATI Field/Group. Eield and Group assignments are to be taken from the 1965 COSATI Subject Category List. Since the majority of documents are multidisciplinary in nature, the primary Field/Group assignment(s) will be the specific discipline, area of human endeavor, or type of physical object. The application(s) will be cross-referenced with secondary Field/Group assignments that will follow the primary posting(s). 18. Distribution Statement. Denote rcleasability to the public or limitation for reasons other than security for example "Re- lease unlimited". Cite any availability to the public, with address and price. 19 8c 20. Security Classification. Do not submit classified reports to the National Technical Information Service. 21. Number of Pages. Insert the total number of pages, including this one and unnumbered pages, but excluding distribution list, if any. 22. Price. Insert the price set by the National Technical Information Service or the Government Printing Office, if known. FORM NTIS-35 (10-70) USCOMM-UC 40329-P" OCT 1 r»75 ■*