LISP-LIST Processor: Meaning and Features | Artificial Intelligence

In this article we will discuss about:- 1. Meaning of LISP 2. Salient Features of LISP 3. Elementary Syntax.

Meaning of LISP:

LISP is a dynamic language of exceptional power and flexibility and has been the dominant language for artificial intelligence programming. Originally designed for symbolic computing, LISP has been extended and refined over its life time in direct response to the needs of AI programming.

It was written by John McCarthy in 1958-60 to represent recursive functions on the computer and is called native language of AI research in USA. Its main features which satisfy the requirements for an AI language and which distinguish it from procedural languages are: Like most traditional programming languages LISP is procedural; LISP programs describe how to perform an algorithm. However, unlike traditional procedural languages (FORTRON, Pascal, etc.) LISP is functional; its syntax and semantics are derived from the mathematical theory of recursive function.

Salient Features of LISP:

LISP is highly extensible and flexible – Very complex extended lists may be written in LISP using more elementary LISP functions. The ‘bare bones’ primitive set of functions which any LISP interpreter or compiler must contain includes CAR, CDR, CONS, ATOM, and the equality test, EQ, along with the forms COND for conditional expressions and LAMBDA for defining functions. This extensibility of LISP makes it an ideal tool for writing application programs and even implementations of other languages such as Prolog, but it has also led to the problem of the proliferation of LISP dialects.

LISP is a recursive language- LISP functions may be defined in terms of themselves. Although some procedural languages such as Pascal support recursion, it is an integral part of LISP programming style.

1. LISP has a Highly Symbol-Oriented Data Structure:

The basic data structures are atoms and lists. Lists are objects composed of other lists and/or atoms which are the primitive, indivisible data type. Lists in LISP are also known ass-expressions or ‘symbolic expressions’. The unique feature of LISP is that programs, functions, and data are all represented by lists. This gives LISP programs the capability of operating on other programs as if they were data. This, in turn, leads to the remarkable property that LISP programs can modify themselves and even write other LISP programs!

2. LISP is an Interactive Language:

AI researchers at MIT in 1950 s were the first to recognise the need for an interactive programming environment. LISP has been routinely available as an interpreter on mainframe and minicomputers and compact implementations of LISP have become available even on microcomputers in both interpreter and compiler format.

3. LISP provides Automatic Dynamic Storage Allocation:

Since a LISP program is a dynamic collection of shrinking and growing lists, the problem of storage allocation can be quite complex. However, modern LISP systems provide for automatic storage allocation with ‘garbage collection’ to reclaim memory no longer needed by the program. Thus the programmer is relieved of responsibility for estimating the dimensions of the program’s data structures which procedural language programs require.

4. LISP is an Ideal Meta-Language:

Meta is Greek word for ‘about’, so a meta-language is a language for talking about language. The language to be talked about may be natural language, another computer language, or LISP itself. The meta-language characteristic of LISP is evident from the fact that a number of the languages such as Prolog have been written in LISP or many knowledge engineering language have been written in LISP.

Elementary Syntax of LISP:

Next we present an overview of the syntax of LISP data types and some of the functions available for manipulating these lists. The dialect selected is common LISP.

Atoms:

The smallest indivisible element of LISP syntax is called an atom. LISP supports several kinds of atoms including numbers, characters, symbols, hyphenated symbols, strings, and vectors.

Examples of numerical atoms include:

5      -300      + 31000      3.14159      1.234E+250

Characters in LISP syntax are designated by a ‘#\’ preceding the character and permit use of non-printing control characters.

Examples include:

Symbols are identifiers made from any combination of letters, numbers and special characters.

Examples of symbolic or literal atoms include:

x      Sanjeev      T      NIL      Suraksha      This-is-log-symbol

STRING:

LISP strings closely resemble strings of procedural languages and include any sequence of characters enclosed within double quotes. (” “):

“This is a string!” “So is this.” “City, State and Zip”.

VECTOR:

A vector is a data structure with an arbitrary number of components. Its structure resembles a list prefixed by a ‘#’.

An example is:

# (a b c d e f)

Examples of illegal atoms include:

(34      25       35)       This sentence has spaces

The first is illegal because it is a special LISP character; the second is a list rather than a symbol; and the third contains spaces, the delimiter (blank) used by LISP. LISP symbols may contain such special characters as +, *, and ? but may not contain the following special LISP character; \ | ) ( ] [ ) } { ” ; # ’ ‘, @ and blank.

There are two special atoms which LISP programmers encounter frequently. The first of these is the atom indicating ‘true’ or ‘non-zero’. This is the atom ‘t’ which LISP refers to as # ! TRUE. For example, after evaluating the following predicate (a predicate asks a question about data): (→ indicates LISP prompt).

That is, LISP has indicated that “It is true that 5 = 5”. What if we asked LISP Code?

→(= ? 4 5)

We might expect that the answer would be ‘f‘ or #! FALSE, but instead we read:

( )

This is the second special symbol, referred to as NIL, and, in fact, if we ask LISP:

→ (equal ? Nil ())

it replies

    # ! TRUE

We may even use different equality queries for the numerical comparison and the special symbol comparison.

LISP provides several equivalence predicates, including:

NIL carries a very heavy load in the LISP language.

1. NIL is an atom. We can verify this with the LISP predicate, ATOM:

→ (atom ? nil)

and find

# ! TRUE

2. NIL is a list. NIL happens to be the empty or ‘NULL’ list.

We can verify this assertion by asking LISP if NIL is the NULL list:

→ (null ? ‘ nil)

and LISP responds:

# ! TRUE

3. NIL is equivalent to ‘false’ in testing predicates and conditions.

Thus, if we ask the question, “Is a list containing two NULL lists empty?”, we find:

_(null ?’ (( ) ()))

()

That is, the answer is ‘false’. A list cannot be empty if it contains two atoms 3 is an atom.

Lists:

As we have been through various types of atoms, so it is time that we consider lists a bit more formally. Lists are similar to sets. The differences are that lists are ordered and the same element can appear more than once in a list.

In keeping with the recursive spirit of LISP, we define:

A list is a sequence of atoms and/or other lists enclosed within parenthesis. The list may contain zero or more atoms or lists.

The delimiter is the blank. Examples of some valid LISP lists are:

Nested list occurs when one list contains another. For example (()) or (() ()). There is no limit in theory on the level of nesting of lists within lists.

LISP comments start with a semicolon,; and can be placed anywhere. Examples of illegal lists include (the reader should explain their illegality); this is not a list

Symbolic-Expressions:

We must notice that many of the lists presented so far seem to have the sentence-like structure:

→ (function arg1 arg2….)

This form is known as the Cambridge Polish notation for function representation. The objective of the LISP interpreter is to evaluate this symbolic expression (also known as ‘s-expression’ or simply, ‘expression’). The argument list may itself be composed of expressions, so here again is a case of recursion. The order of the evaluation logically must be from the innermost nested arguments outward, although on the same level of nesting, the order of evaluation is unspecified.

The model of a LISP interpreter is the simple sequence:

Read-Evaluate-Print (Rep):

Regular LISP functions all follow this REP rule (the only exceptions are the so-called special functions). There may be instances where the user wish to pass on a list as an unevaluated expression. LISP provides the quote special function to allow for this possibility. If we type in the simple list, for instance,

→ (a b e d e)

LISP will respond with the error message:

Variable not defined in the lexical environment E

Using quote, however, we can return this list as a literal, unevaluated expression:

This evaluation blocking function is used so frequently that while defining LIST most LISP systems, provide a short hand version using the single quote, “,” without the associated bounding parentheses.

For example:

The great power of LISP lies in the richness of the functions available for processing arguments and the ease with which new required functions may be generated. Below we illustrate several categories of functions available in LISP.

Input and Output Functions:

The most commonly used functions are read, print, princ, terpri, and format.

Read:

Takes no arguments. When read appears in a procedure, processing halts until a single s-expression is entered from the keyboard. The s-expression is then returned as the value of read and processing continues.

Example:

Print:

Takes one argument. It prints the argument as it is received and then returns the argument.

Example:

Double printing here is because of the fact that print first prints its arguments and then returns it, causing it to be printed by read-evaluate-print loop.

This is true with string

Princ:

This is an output function, printing function. It is the same as print, except it does not print the unwanted quotation (double) marks

This function allows multiple items on the same line.

Terpri:

This function takes no arguments. It introduces a new line wherever it appears and then returns nil format. This function permits a cleaner output than is possible with just basic printing functions.

Conditionals or Control Structures:

LISP provides the same or equivalent control structures as any other high level language.

These structures are called special forms, and several of the most important ones are summarised below:

This condition test checks all the clauses until it finds one with a true predicate. Upon finding a true predicate it evaluates the associated expression list, returning the last expression evaluated as the value for the condition test.

For example, the following comparison of numbers:

We may note that the COND special form is equivalent to the Pascal IF …ELSE IF structure.

An example of the use of this iterative special form to print out the five integers and return the value of the square of the sixth is shown:

Both init 1 and step 1 are optional parameters; if they are missing var 1 is not updated and, rather than looping, the DO structure performs as an IF structure. The key distinction between DO in LISP and in conventional languages are that the LISP DO allows multiple iteration variables each with its own increment control. A FORTRAN DO is essentially a subset of the LISP DO structure.

Recursion:

A recursion function calls itself successively to reduce a problem to a sequence of simpler steps. Recursion requires a stopping condition and a recursive step.

Example 1:

Factorial of a Number:

The recursive step in factorial is the product of n and factorial (n – 1). The stopping condition is reached when n = 0

Other LISP Structures:

There are some other structures and functions supported by LISP, which the space prohibits us to discuss. These include the MACRO, special form iterative MAPPING functions, a variety of function definitions structures and commands for file management and I/O.

Example 2:

Pythagorous Theorem:

The Pythagorous theorem states that the hypotenuse c, of a right angled triangle with short sides a and b is given by c = √ a² + b² .

We define the function, path, to calculate c as follows:

Example 3:

Convert Fahrenheit to Celsius Temperatures:

The standard conversion equation from Fahrenheit temperature F° to Celsius temperature C° is given by:

Example 4:

Fibonacci Sequence:

The Fibonacci sequence is an interesting mathematical series generated by the recursive definition:

This generates the sequence of numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … in which any given element is the sum of the preceding two elements.

The recursive definition of the Fibonacci sequence is captured by the following recursively defined LISP function (although it is computationally much less efficient than an iterative algorithm):

Dialects of LISP:

The very flexibility and extensibility of LISP has encouraged the development of numerous LISP dialects but at the same time prevented, until recently, the emergence of a LISP standard. This has proved to be a serious handicap for sharing of programs and techniques.

Recognition of these problems led to the development of COMMON LISP by a huge team of over 60 participants representing every major AI research institution. The effort was coordinated by Guy L. Steele, Jr., of Carnegie-Mellon University USA, and his book COMMON LISP-The Language has become the de facto definition of what is becoming the accepted standard LISP.

MACLISP developed at MIT is a direct descendant of John McCarthy’s LISP 1.5. It is a very fast, flexible language designed to run on the PDP-10 and PDP-20 series of machines and has had considerable influence on the development of other LISPs.