Transcript Common Lisp

Common Lisp
Derek Debruin
Mark Larue
Vinh Doan
Problem Domains
• There was a need in the early 1960s to
define a programming language whose
computational model could be based on
some well characterized mathematical
principles rather than on the efficiency of
implementation.
• Lisp become one of the best examples of
these language definitions.
John McCarthy
• Lisp was invented by John McCarthy in
the late 1950's as a formalism for
reasoning about the use of recursion
equations as a model for computation.
• The name Lisp derives from "List
Processing Language".
• Of computer languages still in widespread
use today, only FORTRAN is older.
McCarthy Cont…
• Around 1956 McCarthy understood the
central role of a programming language for
his scientific goal -- artificial intelligence.
• McCarthy desired for an algebraic list
processing language for artificial
intelligence work on the IBM 704 computer
(1958)
Variation in Lisp
• Since the inception of Lisp many variations
have been created.
• Of each of these variations, there also has
been many dialects born.
• The most widely-known general-purpose
Lisp dialects are Common Lisp and
Scheme.
Common Lisp
• Rapid was beneficial in early development,
but demand for a standard eventually
grew.
• Developed to standardize the divergent
variants of Lisp.
• It is not an implementation but more of a
language specification.
Basic Concepts
• Everything is a list. Everything.
• Language can be redefined at run-time.
• Code is data and can be generated at runtime.
– This is one of the primary reasons that Lisp is
so popular in artificial intelligence.
Greenspun’s Tenth Rule
• Any sufficiently complicated C or Fortran
program contains an ad-hoc, informallyspecified, bug-ridden, slow implementation
of half of Common Lisp.
• Lisp is often considered the “Grand-Daddy
of them all.”
• Many important features of other
languages come from Lisp.
Macros
• Not the same as C’s preprocessor macros
• Lisp macros formalize the ability of Lisp to
implement other languages and to change
it’s defined behavior dynamically.
Examples
• The S-expression is the basic syntax of
Lisp: a parenthesized list.
• (list 1 2 3)
The basic definition of a list.
• (cons 1 2) constructs a basic list with
contents (1 2)
Examples (cont.)
• The car function yields the “head” (first
element) of a list: (car (1 2 3)) → 1
• The cdr function yields the “tail”
(everything following the head) of a list:
(tail (1 2 3)) → (2 3)
Examples (cont.)
• Quoting prevents lists from being
evaluated automatically.
• ‘(one two three) is a quoted list.
• Quoting prevents the list from being
evaluated as three identifiers “one,” “two,”
and “three.”
Complete Example
• An unquoted form is evaluated when
encountered and again when used:
(setq a ‘b)
(setq b ‘c)
(eval a)
→c
Comparing Lisp to C++
• Lisp is a functional programming
language; C++ is procedural.
• This causes Lisp and C++ to have
numerous differences in syntax, function
definition, typing, etc.
Prefix Syntax
• Lisp expressions use prefix notation.
The expression:
(* l 2 3 4) evaluates to 24.
• The equivalent expression in C++ would
use infix notation:
1 * 2 * 3 * 4;
Functions
• Functions are created through the use of the
special operator lambda.
• lambda takes an argument list and an
expression, evaluating the arguments according
to the expression.
• The expression:
((lambda (arg) (* arg 2)) 3) describes
a function that takes one argument, 3, and
multiplies it by 2, yielding a result of 6.
Functions (cont.)
• Contrast this with C++, where a function
stores an argument which is explicitly
manipulated by statements that follow:
int lambda( int arg )
{
return arg * 2;
}
Cons and Implicit Typing
• Lisp uses lists as its primary data
structure.
• Lists are constructed similarly to other
functional languages, using cons,
append, etc.
• Data is implicitly typed in list and can
therefore be mixed in a given list.
• For example, (cons ‘a (2 3))
evaluates to (a 2 3).
Lists and Typing (cont.)
• In C++ data is explicitly typed.
• C++ also lacks a primitive list data
structure—the closest equivalent is the
array, which may contain only one data
type. The following code is not valid in
C++:
int list[3] = {‘a’, 2, 3};
Impact and the Future
• McCarthy pioneered the if-then-else
structure through Lisp’s cond structure
• Lisp has had a resurgence in popularity
lately.
• The lack of variables in Lisp causes
programs without side-effects. This may
prove very useful in parallel computing.