Page 58 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Introduction to Artificial Intelligence & Expert Systems

Notes manipulate source code as a data structure, giving rise to the macro systems that allow
programmers to create new syntax or even new domain-specific languages embedded in LISP.
LISP was invented by John McCarthy in 1958 while he was at the Massachusetts Institute of
Technology (MIT). McCarthy published its design in a paper in Communications of the ACM in
1960, entitled “Recursive Functions of Symbolic Expressions and Their Computation by Machine,
Part I” (“Part II” was never published). He showed that with a few simple operators and a
notation for functions, one can build a Turing-complete language for algorithms. Information
Processing Language was the first AI language, from 1955 or 1956, and already included many of
the concepts, such as list-processing and recursion, which came to be used in LISP. LISP was first
implemented by Steve Russell on an IBM 704 computer. Russell had read McCarthy’s paper, and
realized (to McCarthy’s surprise) that the LISP eval function could be implemented in machine
code. The result was a working LISP interpreter which could be used to run LISP programs, or
more properly, ‘evaluate LISP expressions.’ The first complete LISP compiler, written in LISP,
was implemented in 1962 by Tim Hart and Mike Levin at MIT. This compiler introduced the LISP
model of incremental compilation, in which compiled and interpreted functions can intermix
freely. The language used in Hart and Levin’s memo is much closer to modern LISP style than
McCarthy’s earlier code.

LISP was a difficult system to implement with the compiler techniques and stock hardware of
the 1970s. Garbage collection routines, developed by then-MIT graduate student Daniel Edwards,
made it practical to run LISP on general-purpose computing systems, but efficiency was still a
problem. This led to the creation of LISP machines: dedicated hardware for running LISP
environments and programs. Advances in both computer hardware and compiler technology
soon made LISP machines obsolete. During the 1980s and 1990s, a great effort was made to unify
the work on new LISP dialects (mostly successors to Mac lisp like Zeta LISP and NIL (New
Implementation of LISP)) into a single language. The new language, Common LISP, was
somewhat compatible with the dialects it replaced (the book Common LISP the Language notes
the compatibility of various constructs). In 1994, ANSI published the Common LISP standard,
“ANSI X3.226-1994 Information Technology Programming Language Common LISP.”

4.1 LISP Application

LISP is an expression-oriented language. Unlike most other languages, no distinction is made
between “expressions” and “statements”; all code and data are written as expressions. When an
expression is evaluated, it produces a value (in Common LISP, possibly multiple values), which
then can be embedded into other expressions. Each value can be any data type. McCarthy’s 1958
paper introduced two types of syntax: S-expressions (Symbolic expressions, also called “sexps”),
which mirror the internal representation of code and data; and M-expressions (Meta Expressions),
which express functions of S-expressions.

!

Caution M-expressions never found favor, and almost all Lisps today use S-expressions to
manipulate both code and data.
The use of parentheses is Lisp’s most immediately obvious difference from other programming
language families. As a result, students have long given LISP nicknames such as Lost In Stupid
Parentheses, or Lots of Irritating Superfluous Parentheses. However, the S-expression syntax is
also responsible for much of Lisp’s power: the syntax is extremely regular, which facilitates
manipulation by computer. However, the syntax of LISP is not limited to traditional parentheses
notation. It can be extended to include alternative notations.

Example: XM LISP, for instance, is a Common LISP extension that employs the meta
object-protocol to integrate S-expressions with the Extensible Markup Language (XML).

52 LOVELY PROFESSIONAL UNIVERSITY