List Processing
List processing is a computer programming language that involves the maintenance and manipulation of lists of data. It involves such actions as the adding and deleting of elements, writing data into elements, and examining the list. List processing is the basis of the artificial-intelligence (AI) programming language LISP (LISt Processing), and it is one of the oldest computer languages still in widespread use. American computer scientist John McCarthy (1927-) developed list processing from 1959 to 1960.
There are many variants (or dialects) of LISP including Scheme and T. In the 1980s there was an attempt to standardize the language. The result is Common LISP, which is now the most popular dialect. Since its creation list processing has undergone considerable evolution over the years, and modern variants are quite different in detail from the original LISP 1.5.
Unlike most languages (such as C, Pascal, or FORTRAN), list processing uses an interpreted programming process. This means that, unlike "compiled" languages (ones that use compilers in order to be translated from a high-level language into executable machine code prior to any executions), an "interpreted" language translates and executes statements at the same time so that the interpreter responds directly to programs. The BASIC language is well known as an interpreted language, although most current implementations of BASIC allow (or require) the programmer to compile the program as well. APL (A Programming Language) is also an interpreted language.
During list processing a LISP interpreter will initiate a prompt to appear, something like: >. The LISP interpreter waits for a user to enter a LISP expression. The interpreter then runs what is known as a read-eval-print loop. That is, it reads what is typed, evaluates it, and then prints the result, before providing another prompt. For example:
In this example, the user types in the LISP expression (+ 2 4 8 3), indicating to sum (+) the four numbers, and the interpreter responded with 17 and a new prompt.
Data objects (like character strings and other symbols) that are manipulated within list processing are called symbolic expressions, or simply "s-expressions." An s-expression can be thought of as any expression from which LISP can create some meaning or value. Lists and atoms, the two basic building blocks of LISP programs, can be thought of as s-expressions. Lists include all programs and program statements. Used in this way, a list is defined to be an ordered set of zero or more elements surrounded on each side by parenthesis and separated by spaces (e.g., (4 5)). Each element in a list can either be (another) list or an atom. An atom, or atomic element, is a simple s-expression and is usually thought of as a variable. It should be noted that both numeric values, such as the numeric "4," or symbolic text-type names, such as "NIL," are both considered to be atoms. For example, consider the expression (ONE (TWO 3) ((4 5) (SIX 7) (8 9))) to be a list. This list is comprised of three elements: the atom ONE, the list (TWO 3), and the list ((4 5) (SIX 7) (8 9)). This example demonstrates that a list can be comprised of both atoms and lists, and that lists can be elements of other lists to create levels of list nesting.
A special type of list is the empty list. The empty list is defined as a list that has no elements, and is represented by parenthesis with nothing inside: "()." In LISP, the atom NIL is interchangeable with the empty list. The idea of an empty list is very important in computer problem solving and is always included in the LISP language definition.
Today, list processing is extensively used in research and academic organizations, and has been considered the "standard" way to perform AI research. LISP was developed for the purpose of creating a new tool to perform list processing and symbolic expression manipulation. The result is an excellent programming language with continuing significant potential for computer science, especially in the fields of artificial intelligence and natural language processing.
This is the complete article, containing 671 words
(approx. 2 pages at 300 words per page).
