LISP Tutorial

By
Marc Schwarz

From the Forthcoming Text

Natural Language Computing Workbook

By
Ray C. Dougherty and Marc Schwarz

This web site is best viewed using Netscape Navigator 2.0 or later, and when your web browser's width is set to these dimensions

Return to NYU Natural Language Computing Project Online Tutorials
Return to NYU Natural Language Computing Project
Return to Research at NYU Linguistics

---

Table of Contents

I. LISP Fundamentals

1.0 Introduction
1.1 Entering and Exiting LISP

1.2 Resetting The Interpreter

1.3 LISP Syntax

• Representing Data in LISP
  • An atom
  • A list
• User-Defined Commands

1.4 An Introduction to LISP Primitives

• Defun
• If
• Let*
• Setq
• Cond
• Princ, Print and Terpri
• Summary

1.5 Primitives Specifically Used For Manipulating Lists

• Cons
• Append
• List




II. Programming Styles




2.1 Recursion

2.2 Iteration

---

---

I. LISP Fundamentals

1.0 Introduction

LISP is among the oldest high level programming languages. It was first developed in 1958 by John McCarthy. It was later adopted as the primary research language of Artificial Intelligence (AI), which was born at a research conference in 1956. Despite later developments of such languages as FORTRAN, BASIC, ALGOL, APL, and C, LISP remains the predominant language in AI. There are a number of reasons as to why LISP continues to see widespread use.

LISP has among the least restrictive syntaxes of any higher-lever computer languages. Higher-level languages, such as BASIC, FORTRAN, and C, represent programs and data in a format that people can readily understand. Lower-level languages represent programs and data in a format that machines can understand. Lower-level languages are fast, but can be difficult to program. Because LISP's syntax is relatively unrestrictive, there are fewer forms that a programmer must learn in order to program in the language.

LISP was originally developed as an interpreted language. Robert Wilensky, a noted AI researcher and author, likens an interpreted language to that of a hand calculator; the user punches/types in the data, and the machine immediately computes and prints out an answer (Wilensky, R., 1986, p.2). Interpreted languages are beneficial, because sub-system development can be done more easily in a language such as LISP than in compiled languages, such as Pascal and C. A number of current versions of LISP, including Common LISP, make use of an incremental compiler. The programming examples in this tutorial include transcripts of LISP code being run on an interpreter.

Among LISP's strongest features is that programs may be treated as data. In LISP, entire programs can be used as input to other programs or subprocedures directly. In Pascal and C, input data must be represented in specific ways; programmers often have to expend substantial time and effort to implement comparable forms in these languages that are otherwise easily handled in LISP.

There are numerous implementations and variations of LISP. The examples in this book were developed on Sun workstations running Kyoto Common LISP (KCL), and IBM compatibles running XLISP. Unless otherwise noted, the code in this book works properly on Sun workstations, IBM compatibles, and Apple Macintoshes running XLISP or Common LISP.

This document is not an introduction to either LISP or Prolog. The intent of this section is to present readers with just enough information such that they can enter, exit, and reset LISP, as well as run the program examples resident on the CD-Rom included with the book, Natural Language Computing Workbook. Actual user-inputs are displayed in BOLD type. The references listing at the end of this section provides a number of sources for those readers interested in a more formal introduction to LISP.

---

---


1.1 Entering and Exiting LISP

Please refer to the instructions that are included with the CD-ROM included with the book, Natural Language Computing Workbook., to install your software. If you are accessing this document via the Internet, please refer to the Installing The Free Software Subsection of the NYU Natural Language Computing Project Home Page.

To begin an XLISP session on the Macintosh, double-click on the XLISP icon. To begin an XLISP session in Windows, double-click on the File Manager Icon, which is under the Main Folder. Double-click the xlisp.exe Icon. To exit XLISP from within Windows, first drag the cursor to the menu bar, and click on the word, "File," and double-click on exit. If you are using the DOS version of XLISP, type "(bye)" to exit. If you are using a different version of LISP, you might need to type either: "(quit)", ":q", ":quit", or ":bye" to exit the interpreter.


---

---

1.2 Resetting The Interpreter

In XLISP, a user types "(top-level)" to exit the debugger. Different versions of LISP might use a different command. If the version of LISP the reader is using does not recognize the command, "(top-level)", then he or she should try using the commands: "(reset)", ":r", or ":reset". When in doubt, it is always a good idea to check the reference manual for the version of LISP you are using. In XLISP, a user types "(top-level)" to exit the debugger. Different versions of LISP might use a different command. If the version of LISP the reader is using does not recognize the command, "(top-level)", then he or she should try using the commands: "(reset)", ":r", or ":reset". When in doubt, it is always a good idea to check the reference manual for the version of LISP you are using.


---

---


1.3 LISP Syntax

Representing Data in LISP

The formal name for a single unit whose format the system can recognize is called an S-expression. The standard syntax for an S-expressions is: (command data1 data2 data3 ... dataN). A user need only input the intended data (to be processed) and corresponding evaluator, applying proper syntax rules; the system will then process the data according to the evaluator, and return an answer immediately. An S-expression can be either a function to be evaluated, or the data that is to be applied to an evaluateable function. Within an S-expression, we also need a way to use symbols as inputs to functions such that the inputs themselves are not evaluated; we do this with quoting (Touretsky, D., 1984 P.71). Quoting entails putting an apostrophe, " ' ", immediately infront of any symbol we want to treat as data. When the interpreter reads in the symbol, it will see the apostrophe and subsequently know to treat the symbol as data, and not evaluate it any further (Ibid.). For the moment, An S-expression can be thought of as being either an atom or a list.

An atom is a number or symbol that cannot be broken into smaller components (Ibid., p.131). The symbol, A, is atomic. So are the symbols ATOMIC and (). The provided definition for atom should be taken within the context of standard LISP. It is possible to isolate individual parts of an atom in LISP, just as it is possible to isolate protons, neutrons and quarks in physics. A later section of this chapter will discuss how to split atoms in LISP. Generally, it is understood that atoms are indivisible.

A list is a way of representing a set of atoms and lists. A list has the form of an open-parentheses, "(", followed by a set of atoms or lists, followed by a close parentheses, ")". The name, "LISP", is a contraction of the term, List Processor (Sethi, R., 1990, p.252). Essentially, anything enclosed within two parentheses can be considered a list. A list can contain either atoms or lists. (An Atom) is a list composed of 2 atoms. (Up (And Atom)) is a list composed of an atom (e.g., UP) and the list (And Atom). As noted earlier, the single quote, " ' ", tells the interpreter not to evaluate the list, but to treat it as a data item. The system treats the quote itself as a symbol as well. '(An Atom) is a list composed of a symbol, ', and a two-symbol list, (An Atom). '(An Atom) may also be written as (QUOTE (An Atom)). The S-expression (+ 1 2) is a list that does not begin with a quote. Upon input, the interpreter would evaluate the list, (+ 1 2), and return the value, 3. It is worth noting that there is an important distinction between a symbol's value and its input-form. Whereas 5 is a number, (+ 2 3) is not considered to be a number, but a list that returns a number upon evaluation.

The standard method of breaking down lists in LISP is to think of a list as the conjoinment of a head and a tail. The head is simply the first element of a list. The tail is every element in the list that comes after the head. Here is the input-form of a list: '(Greetings (I Am A List)). In this example, Greetings is the head of the list, ((I Am A List)) is the tail of the list, and (Greetings (I Am A List)) is the value of the list (as derivable from the input-form). Note that (I Am A List) is itself a list, and that ((I Am A List)) is not equivalent to (I Am A List). Lists are not atomic, because they can be broken down into smaller parts (Touretsky, 1984, p.131). In LISP, the formal name for the head of a list is the CAR; CDR is the formal name for the tail. The terms CAR and CDR are acronyms, and they derive from registers (which are place-holders that store small amounts of memory) that were built into a now-defunct IBM mainframe computer.

To simplify typing, CAR's and CDR's can be nested. (car (cdr '(Greetings (I Am A List)))) can also be written as (cadr '(Greetings (I Am A List))). (car (car (cdr '(Greetings (I Am A List))))) can be written as (caadr '(Greetings (I Am A List))).

Nesting CAR's and CDR's may make the writing process easier, but it can make comprehending what is being evaluated more difficult for the person trying to read the code. Most implementations of LISP do not permit nestings greater than four levels deep in order to discourage excessively ambiguous CAR and CDR expressions. Manipulating extremely long lists in earlier versions of LISP proved awkward, and often resulted in code that was difficult for a human reader to follow. To remedy this potential difficulty, an alternative construct was developed. The Nth command may be used to obtain place-values much like CAR and CDR. Nth takes a number and a list as inputs, where the number is between 0 and (length of the list minus 1). Nth then returns the value at the number-th place of the input list. Typing in (Nth 0 inputlist) will return the first item (I.E., the CAR) of the list named inputlist. Nth works best when the input data is a long, non-nested list.

For example, suppose we have defined an input list, '(a b c d e f g h i j k l m n o p q r s t u v w x y z), which we have assigned the name, alphabet. If we wanted to use the Nth command to retrieve the 12th element from alphabet (I.E., the letter, m), we would write: (Nth 12 alphabet). If we instead chose to do this using combinations of CAR's and CDR's, we would have to write: (car (cdr (cdr (cdr (cdr (cdr (cdr (cdr (cdr (cdr (cdr (cdr (cdr alphabet))))))))))))).

The Nth command may be used on nested lists. In such cases though, the resulting code is frequently as cryptic as it would have been using combinations of CAR's and CDR's. Utilizing the Nth command, (caadr '(Greetings (I Am a List))) would be written as: (Nth 0 (Nth 1 '(Greetings (I Am a List)))).



---

User-defined Commands

There are a number of commands that are built into LISP. These include arithmetic expressions, such as: +, -, *, /, as well as expressions that permit a programmer to create new commands not already present (and thus write more complex programs). In LISP, built-in commands are called primitives, and user-created commands are called procedures. Procedures enable the programmer to break an overall task into smaller, more manageable parts. These smaller subtasks can then be implemented and debugged separately from the other parts of the code. When the individually working subtasks are integrated, a program that solves the overall task is realized. In LISP, a program is a collection of procedures that generates a desired output from a specified given input.

---

---


1.4 An Introduction to LISP Primitives

In this section, we will discuss how a number of LISP primitives may be used to build procedures. Examples of actual working code will be presented, often alongside transcripts of that code being executed.



Figure T1

The following program makes use of most of the LISP primitives used in the Natural Language Computing Workbook (defun Trite(h) (if (equal h 0) (BadDay) (let* ((new-h (+ 1 h))) (cond ((equal h -1) (Trite 1)) ((< h 0) (Trite new-h)) (t (princ '|I'm having a |) (princ '|nice day!|) (terpri) (princ '|I hope you |) (princ '|have a nice day|) (terpri) (princ '|for the next |) (princ new-h) (princ '| days!|) (terpri) ;;; (print new-h) *Used ;;; in debugging ))))) ;; A variation on a line attributed ;; to Sir Winston Churchill (defun BadDay() (princ '|I'm having a lousy day!|) (terpri) (princ '|But tomorrow, |) (princ '|I might be happy.|) (terpri) (princ '|You however, will still |) (princ '|be ugly.|) (terpri) )) ;;; Lines that begin with semicolons ;;; are comments. Upon reading a ";" ;;; the evaluator skips to the next line.

The following is a screen shot of some sample executions of the Trite program > (Trite 3) I'm having a nice day! I hope you have a nice day for the next 4 days! NIL > (Trite -4) I'm having a nice day! I hope you have a nice day for the next 2 days! NIL > (Trite 0) I'm having a lousy day! But tomorrow, I might be happy. You however, will still be ugly. NIL





Princ, Print and Terpri



Princ is used to display text to the screen. Print is used to print atoms and lists, while princ is used to print strings of characters. Print also inserts a newline at the end of whatever it is told to print. Princ will keep the cursor on the same line unless explicitly instructed to move the cursor down one line. Terpri is the LISP command for printing a carriage-return.

The "|" character that appears on every line containing a princ command (in the Trite and BadDay procedures) is colloquially referred to as a pipe. Pipes are used in LISP primarily for printing text to the screen. The evaluator treats any data within two pipes as an implicit list. The second line of the BadDay procedure, (princ '|I'm having a lousy day!|), is an example of a princ expression containing pipes.

---

Defun

The defun command is used to define functions. LISP refers to functions as procedures (Sethi, R., 1990, p.258).

Defun takes the form: 
(defun ProcedureName(Optional-Input-Variable-Seq) Procedure-Body). 

The procedure being defined in the above diagram is called, Trite. The Trite procedure takes 1 variable as input, and that variable has the name h. The (Optional-Input-Variable-Seq) sequence that immediately follows the ProcedureName is a list of zero or more atoms and/or lists. The entire procedure is itself a list; this is true for all legally formed procedures in LISP. Because procedures are themselves lists, they can be used as inputs into other procedures.

---

If

If is used as a boolean test.

The standard format for an IF statement is: 
(if TEST Do_if_Test_Result_Not_NIL Do_if_Test_Result_Is_NIL)  

An If does the following: The TEST is first evaluated. If the value returned is not NIL, then Do_if_Test_Result_Not_NIL is evaluated. Otherwise, Do_if_Test_Result_Is_NIL is evaluated. If no explicit Do_if_Test_Result_Is_NIL is defined, then the system will return the value '() as its Do_if_Test_Result_Is_NIL.



Figure T2

The following LISP program uses an if-clause to determine if a given inputted word is a conjunction: (defun ConjTest(word) (if (member word '(and but or)) 'T '())) ;;; Note: member is a LISP primitive ;;; that tests if an item is a member of a ;;; list. Member has the syntax: ;;; (member item input-list). ;;; Member will return NIL if the item is ;;; not in the input-list. If the item is ;;; in the input-list, then member will return ;;; the sub-list of the input-list where the ;;; item is the CAR. ;;; E.G.: (member 'but '(and but or)) will ;;; return the sub-list (but or). The IF ;;; clause (within ConjTest) would then, in ;;; turn, examine the returned sub-list, ;;; '(but or). Because '(but or) is NOT Nil, ;;; the system will perform the appropriate ;;; Do_if_Test_Result_Not_NIL sub-clause, ;;; which returns the value, TRUE.

This is a screen shot of some sample executions of the ConjTest program > (ConjTest 'every) NIL > (ConjTest 'and) T > (ConjTest 'or) T





---

Let*

Let* is used to denote local variables. Local variables are recognizable only within the procedure in which they are defined. Global variables, in contrast, are recognizable over the entire program. Global variables are most commonly instantiated via the built-in Setq command. An example of Let* is shown on line 3 of the Trite procedure, in Figure T1. The local variable new-h is being defined to be the value of (+ 1 h); (i.e., new-h = 1 + h).

The standard format for a Let* is: 
(let* 	( (Name1 (evaluateable-S-Expression1)) ...
          (NameN (evaluateable-S-ExpressionN))) Procedure-Body ) 
 

A Let* is always defined within the context of a procedure. The variable Name1 here takes the value returned by an evaluation of (evaluateable-S-Expression1). Name1 may then be used in place of (evaluateable-S-Expression1) in the procedure body.



Figure T3

The following LISP program determines if a given inputted word is a conjunction. ConjTestII uses a let-clause to instantiate a local variable, called resultbak. Resultbak takes the value returned by a call to the original ConjTest program, with the given inputted word. (defun ConjTestII(word1) (let* ((resultbak (ConjTest word1))) (print resultbak) (terpri)))

This is a screen shot of some sample executions of the ConjTestII program > (ConjTestII 'every) NIL NIL > (ConjTestII 'and) T NIL > (ConjTestII 'or) T NIL





---

Setq

Setq is used for instantiating global variables. Global variables are recognizable both internal and external to every procedure and sub-procedure that has been loaded into the LISP interpreter. The setq primitive can be placed within procedures, and can also be evaluated directly, external to any specific procedure. Setq returns the value derivable from the given input-form. It should be noted that using global variables may produce unintended or undesirable side-effects. Global variables should thus be used sparingly, and with care.



The standard syntax for setq is:
(setq Name Input-Form) 

Figure T4

The following is a screen shot of some sample executions of setq > (setq nouns '(boy girl dog tree lake)) (BOY GIRL DOG TREE LAKE) > nouns (BOY GIRL DOG TREE LAKE) > (setq verbs '(read talk write study walk)) (READ TALK WRITE STUDY) > verbs (READ TALK WRITE STUDY) > (setq conjunctions '(and but or)) (AND BUT OR) > conjunctions (AND BUT OR)





---

Cond

Cond is formally called a conditional statement. Cond takes the standard form:

(cond    ((TEST1)          (Do-if-TEST1-is-TRUE))
         ((TEST2)          (Do-if-TEST2-is-TRUE))
         ((TEST3)          (Do-if-TEST3-is-TRUE)) ...
         ((TEST_N)         (Do-if-TEST_N-is-TRUE))
         (t                (Do-if-TEST1-to-TEST_N-are-FALSE)))

;;;      left-hand-side    right-hand-side
 

A cond clause is evaluated in a two-part process. Step One involves evaluating a left-hand-side test clause, beginning from TEST1. The tests are evaluated in order, until the system finds a test-clause that returns the boolean value, TRUE. Step Two occurs once such a clause is identified. At this point, the system evaluates the (Do-if-TEST*-is-TRUE) right-hand-side that corresponds to the identified true test-clause. Once a right-hand-side is evaluated, the system then exits the cond clause. If none of the tests returns a true value, the system will return a cond out-of-bounds error and halt all processing. To remedy this, it is standard coding practice to include a TRUE-statement as the final test condition on the left-hand-side.

Order of test placement is crucial in cond statements. The system looks, in placement-order, for the first (and not necessarily the best) TEST that returns the value, TRUE. If TEST2 is a more specific version of TEST1, then (Do-if-TEST2-is-TRUE) will never be evaluated. This predicament makes the cond statement a common place for programmers to make logic errors. Many beginning LISP programmers think of the Cond statement as a nested If statement. While this statement not completely correct, it simplifies notions that do apply to the cond statement, and make the clause's use easier to understand.

The following diagram presents a pseudo-representation of the cond statement based on this perspective:



Cond If  TEST1-is-TRUE  THEN   Do-THIS             Else
     If  TEST2-is-TRUE  THEN   Do-THAT             Else
     If  TEST_N-is-TRUE THEN   Do-THE-OTHER-THING  Else
     TRUE               THEN   Do-SOMETHING-COMPLETELY-DIFFERENT 




Figure T5

The following small LISP program uses a cond-clause to determine the proper class of an inputted word. The various word classes are based on the examples used in the Setq subsection above. (defun WordClass(word) (cond ((member word nouns) (princ '|NOUN|) (terpri)) ((member word verbs) (princ '|VERB|) (terpri)) ((member word conjunctions) (princ '|CONJUNCTION|) (terpri)) (t (princ '|DATABASE INCOMPLETE|) (terpri) (princ '|Word class cannot |) (princ '|be found.|) (terpri))))

The following is a screen shot of some sample executions of the WordClass program > (WordClass 'and) CONJUNCTION NIL > (WordClass 'tree) NOUN NIL > (WordClass 'verb) DATABASE INCOMPLETE Word class cannot be found. NIL > (WordClass 'walk) VERB NIL




---

Summary



There are many other primitives in LISP. As the reader leafs through the chapters about LISP in the Natural Language Computing Workbook, he or she will likely notice that most of the included code only uses about 10 primitives. Defun, if, let*, cond, car, cdr, and the set of arithmetic/boolean primitives {+, -, *, /, <, >, eq, equal} are the basic building blocks for creating user-defined procedures in Common LISP. Print, princ, and terpri are the basic building blocks for outputting data to the screen. There are also three primary primitives for modifying lists: cons, append, and list; they are discussed at length in the next sub-section.

---

---


1.5 Primitives Specifically Used For Manipulating Lists



The primitives cons, append, and list are the principle methods of manipulating lists directly.

Cons

Cons concatenates an atom or list onto the front of a second list. Cons takes whatever the first item is, and inserts that item into the front of the second item. If the second item is not a list, then the resulting returned value will be dependent on the version of LISP being used. Some versions of LISP will not permit a cons expression where the second item is not a list, and will return an error statement. Xlisp and KCL will permit such a cons expression to be evaluated. These versions of LISP will return a list in which the first and second element are separated by a dot, ".".



Figure T6

The following is a screen shot of some sample executions of cons > (cons 'a '(1 2 3)) (A 1 2 3) > (cons '(a b) '(1 2 3)) ((A B) 1 2 3) > (cons '(1 2 3) 'a) ((1 2 3) . A) ;; NOTE: 'a is not a list, so a dot is placed ;; between it and the (1 2 3). > (setq list1 '(a b c d e f 1 2 3 4 5 6)) (A B C D E F 1 2 3 4 5 6) > (cons (car list1) (cdr list1)) (A B C D E F 1 2 3 4 5 6)





---

Append



Append conjoins two lists together. Append strips away 1 list-layer from the first element (i.e., 1 pair of "(" and ")", and then inserts the modified item into the front of the second list. In the example below, (append '((a b)) '(1 2 3)) returns ((A B) 1 2 3). The first list-layer of '((a b)) is stripped, leaving the list, (a b). The modified item, (a b), is then inserted into the beginning of the second item, yielding ((A B) 1 2 3). As with the cons expression, some versions of LISP will permit the second item in an append expression to be an atom, (i.e., a non-list). In the diagram, the expression (append (cdr list1) (car list1)) returns (B C D E F 1 2 3 4 5 6 . A), because the value of the second item, (car list1), is an atom and not a list. If the first item of an append expression is not a list, then it does not have a list-layer that can be removed. In such instances, the system will return an error statement and halt.

Finally, List takes an item, and adds a list-layer to it. Here are some examples of LISP evaluating append and list expressions.



Figure T7

The following is a screen shot of some sample executions of append and list > (append '(a b) '(1 2 3)) (A B 1 2 3) > (append '((a b)) '(1 2 3)) ((A B) 1 2 3) > (setq list1 '(a b c d e f 1 2 3 4 5 6)) (A B C D E F 1 2 3 4 5 6) > (append (cdr list1) (car list1)) (B C D E F 1 2 3 4 5 6 . A) ;; NOTE: Notice the dot between the 6 and the A? ;; This is because (car list1) is not a list. > (append (cdr list1) (list (car list1))) (B C D E F 1 2 3 4 5 6 A) > (append (car list1) (cdr list1)) Error: A is not of type LIST. Fast links are on: do (use-fast-links nil) for debugging Error signalled by APPEND. Broken at APPEND. Type :H for Help. ;; NOTE: (car list1) here equals the atom, A. ;; A is not a list, so the system is unable to ;; strip 1 list-layer from it. Because the system ;; cannot correctly evaluate the append, based on ;; the given data input, it returns an error ;; message. To clear the error-prompt, the ;; user must reset the system to top level. >> :r Top level. > (append (list (car list1)) (cdr list1)) (A B C D E F 1 2 3 4 5 6) > (list 'a) (A) > (list '(a)) ;; NOTE: This item already has 1 list-layer ((A)) ;; NOTE: A second list-layer has been added to the first item




---

---

II. Programming Style

2.1 Recursion

Computers are very good at executing repetitive tasks. Recursion and iteration are the formal names for methods of doing something over and over again. Recursion entails self-referential repetition; a program that calls itself is recursive. LISP is a recursive language, and most of the LISP programming examples in the Natural Language Computing Workbook use recursion.

The following small program, Sans, from the French sans, without, removes an item from a list. The Sans program is composed of two procedures. The first procedure, called Sans, checks the inputs to ensure that a computable solution is possible. If no such solution is possible, given the inputs, then the procedure will return nil. Otherwise, Sans makes a call to the procedure, GoSans, with the initial loop conditions. Initial loop conditions represent what the data looks like at the very beginning of a repetitive task. The statement, (GoSans item itemlist '()) contains the initial loop conditions. GoSans takes these initial inputs, performs the actual repetitive manipulations, and then returns a final answer. GoSans is recursive, because the looping mechanism within the procedure is self-referential. The LISP primitive, remove, effectively does the same thing as our Sans program.



Figure T8

The Sans program removes an item from a list (defun Sans(item itemlist) (cond ((null itemlist) nil) (t (GoSans item itemlist '())))) (defun GoSans(pattern stlist finlist) (cond ((null stlist) finlist) ((eq pattern (car stlist)) (GoSans pattern (cdr stlist) finlist)) (t (GoSans pattern (cdr stlist) (append finlist (list (car stlist))) ))))

The following is a screen shot of some sample executions of the Sans program > (Sans '1 '(1 2 3)) (2 3) > (Sans '1 '(1 2 3 1)) (2 3) > (Sans '1 '(1 2 3 11)) (2 3 11) > (Sans NIL '(1 2 3 () 4 5)) (1 2 3 4 5)





---

---


2.2 Iteration

Iteration is another approach to executing countably infinite repetitive tasks. A program or procedure that uses looping constructs that do not involve a self-referential procedure call is iterative, or tail-recursive. The FOR and WHILE loop-constructs found in languages such as Pascal and C are iterative; they need not call themselves in order to execute properly. FOR and WHILE loops each contain internal mechanisms that control the repetition. Within FOR and WHILE loops, an internal loop-test (or counter) is maintained. During the execution of an iterative loop, this loop-test will be inspected. If the loop-test is true, the system will make one step (or iteration) through the loop. The loop-test is then inspected again, and so on... The looping stops when the loop-test is no longer true. If the looping never stops, the construct is said to contain an infinite loop.


---

---

The remaining pages of this web site are best viewed when your web browser's width is set equal to that of the following violet bar:

Before continuing on to another page at this web site, please go to the OPTIONS or PREFERENCES on your browser's Menu, and modify the settings until your display's right edge is flush with the bar immediately above this paragraph.

Suggested Next Link: Sample LISP Programs

---

© Copyright 1996 Marc Schwarz & Ray C. Dougherty.
All Rights Reserved.

This document may be distributed for non-commercial use on the condition that it will be distributed intact, unaltered, and that any and all such distributions will include this copyright notice. All other uses of this document, including the use of it's design/concept, without the expressed and prior written consent of the authors is prohibited.

---