Transcript Lisp/Scheme

Lisp/Scheme
Ruth Rutter
Functional and Logic Programming
Team P-Phunck
4-25-08
CS 331
Lisp/Scheme
1
LISP


Functional, not imperative
Created to process lists – LISt Processing
–
–
–
–
–
–
–

Checking mathematical proofs
Game playing and simulation
Graphics and display programming
Artificial intelligence
Integral and differential calculus
Electrical circuit theory
Etc.
Several dialects
– MacLISP, InterLISP, Franz LISP
– Common LISP and Scheme
4-25-08
CS 331
Lisp/Scheme
2
Timeline



1958, released at MIT by John McCarthy
1959, LISP 1
1962, LISP 1.5
–
–
–
–




Property lists for atoms
Insertion and deletion of elements from lists
Numbers represented with S-expressions instead of atoms
eval was developed
Contributed to
– Logo (1968)
– Smalltalk (1971)
– Scheme (1975)
1984, Common LISP
Contributed to CLOS (1989) Common-LISP Object System
1994, Common LISP first ANSI standard that incorporated OOP
4-25-08
CS 331
Lisp/Scheme
3
Data “Types”
Atoms – symbols or literals
 Lists – atoms delimited by parentheses

– (A (B C) D (E (F G)))
Not really “types” as in imperative languages
 Original LISP was typeless

4-25-08
CS 331
Lisp/Scheme
4
LISP Lists
Essentially linked lists
Sebesta: Concepts of Programming Languages
Copyright © 2007 Addison-Wesley. All rights reserved
4-25-08
CS 331
Lisp/Scheme
5
Syntax

s_expression = atomic_symbol \
/ "(" s_expression "."s_expression ")" \
/ list
list = "(" s_expression < s_expression > ")“
atomic_symbol = letter atom_part
atom_part = empty / letter atom_part / number atom_part
letter = "a" / "b" / " ..." / "z“
number = "1" / "2" / " ..." / "9“

empty = " "





4-25-08
CS 331
Lisp/Scheme
6
Functions

Expressed the same as data
– Lists of parentheses, symbols, literals

Cambridge Polish Notation
– Function( arg1 arg2 )
– * x y = TIMES(x y)

No iteration
– No counter variables
– Recursion instead
4-25-08
CS 331
Lisp/Scheme
7
Primitive Functions

CAR
–
–
–
–

Contents of the address register
Returns the first item in a list
CAR(A B C) = A
Undefined for atoms
CDR
– Contents of the decrement register
– Returns everything but the first item
– CDR(A B C) = (B C)

CONS
– Primitive list constructor
– CONS(A (B C D)) = (A B C D)
4-25-08
CS 331
Lisp/Scheme
8
QUOTE & CONS Examples
QUOTE returns unevaluated argument
(QUOTE X) = X
Shorthand = ‘X
CONS Examples
(CONS ‘A ‘()) = (A)
(CONS ‘A ‘(B C)) = (ABC)
(CONS ‘() ‘(A B)) = (()A B)
(CONS ‘(A B) ‘(C D)) = ((A B) C D)
4-25-08
CS 331
Lisp/Scheme
9
Predefined Functions

EQUAL
– Boolean function to test equality of S-expressions

Arithmetic Functions - detailed
– PLUS, DIFFERENCE, MINUS, TIMES, QUOTIENT,
REMAINDER, DIVIDE
– For FLOATS as well
– SQRT, EXPT, RECIP, ADD1, ABSVAL
– ENTIER: returns int <= arg
4-25-08
CS 331
Lisp/Scheme
10
Predicate Functions

Arithmetic
– NUMBERP, FIXP, FLOATP, ONEP, etc.
– ZEROP N
 T if N is a number
 False otherwise

List
– (NULL L) – T if L is empty or NIL
– (MEMBER L1 L2) – T if L1 is an element of L2

NOT/NULL
– (NOT P) returns true if P is NIL
4-25-08
CS 331
Lisp/Scheme
11
Functional Forms

Functional Composition
– Nonquoted lists are assumed to be functions
– Therefore, parameters must be evaluated first –
applied recursively
– Some built into single functions
 (CAAR x) = (CAR (CAR x))
 (CADDAR x) = (CAR (CDR (CDR (CAR x))))

Apply-to-All Functional Form
– mapcar: two params, a function and a list
4-25-08
CS 331
Lisp/Scheme
12
Nameless (LAMBDA) Functions
Temporarily define functions
 Syntax:
(LAMBDA varlist body)
 Example: 43
(LAMBDA (X Y) (EXPT Y X)) (3 4)

4-25-08
CS 331
Lisp/Scheme
13
Defining Functions
Like a permanent LAMBDA function
 Pseudo-function

– One argument – list of functions to be defined
Syntax:
DEFINE((
(name1 (LAMBDA varlist body))
(name2 (LAMBDA varlist body))
))

4-25-08
CS 331
Lisp/Scheme
14
Example: N!
n! = UNDEF, n<0
= 1, n=0
= n * (n-1)!, n>0
DEFINE((
(FACTORIAL (LAMBDA (N) (COND ((ZEROP N) 1)
( T (TIMES N (FACTORIAL (SUB1 N))))))) ))
4-25-08
CS 331
Lisp/Scheme
15
Example

Comparing two lists
(DEFINE (equal lis1 lis2)
(COND
((NOT (LIST? lis1)) (EQ? lis1 lis2))
((NOT (LIST? lis2)) #F)
((NULL? lis1) (NULL? lis2))
((NULL? lis2) #F)
((equal (CAR lis1) (CAR lis2)
(equal (CDR lis1) (CDR lis2)))
(ELSE #F)
))
4-25-08
CS 331
Lisp/Scheme
16
Interpreters
EVAL – universal function to evaluate any other function
– Was altered to create the first LISP interpreter
 Accidental addition – dynamic scoping until 1975
 Online interpreter: (basic)

– http://www.joeganley.com/code/jslisp.html

CLISP most commonly used
– http://www.clisp.org/ has packages for different OS’s


http://home.att.net/~gobruen/progs/lisp/
Pico LISP (minimalist)
– http://lambda-the-ultimate.org/node/2124

Ufasoft Lisp
– http://www.ufasoft.com/lisp/
4-25-08
CS 331
Lisp/Scheme
17
Common LISP




Developed to combine and standardize previous LISPs
A general purpose and AI language
Supports imperative, functional, and object-oriented
paradigms
Has data types including
–
–
–
–


Numbers (int, ratio, float, complex, etc.)
Strings
Arrays
Symbols (name, value, function, and package)
Automatic memory management
Includes static and dynamic scoping
– Declare variables “special” to make dynamic

Larger, more complex
4-25-08
CS 331
Lisp/Scheme
18
Scheme
Developed at MIT, mid 1970s
 Not exclusively functional

– Supports imperative, functional, and message passing

Functions are first-class entities
– Can be values of expressions, elements of lists,
assigned to variables, and passed as parameters
First LISP to distinguish procedures from lambda
expressions and symbols
 First language to use first class escape procedures

4-25-08
CS 331
Lisp/Scheme
19
Scheme II

Functions that Build Code
– Replacing functions that only take numeric atoms,
such as Scheme’s + function
– Define function to embed “+” into the list, then
submit to EVAL
(DEFINE (adder lis)
(COND
((NULL? lis) 0)
(ELSE (EVAL (CONS ‘+ lis)))
))
4-25-08
CS 331
Lisp/Scheme
20
Modern Uses





Viaweb was written in LISP, and later became
Yahoo! Store
ITA Software’s airfare pricing and shopping
system QPX (used by Orbitz)
Naughty Dog’s Jak and Daxter for the
Playstation 2
Software for Roomba
Artificial Intelligence applications
4-25-08
CS 331
Lisp/Scheme
21
Bibliography











Hekmatpour, Sharam. Introduction to LISP and Symbol Manipulation. 1988
Prentice Hall International.
McCarthy, John. History of Lisp. Stanford, 1979.
Sebesta, Robert W. Concepts of Programming Languages. 2008 Pearson
Education, Inc.
Touretzky, David S. LISP: A Gentle Introduction to Symbolic Computation.
1984 Harper & Row Publishers.
Weissman, Clark. LISP 1.5 Primer. 1967 Dickenson Publishing Company,
Inc.
http://www.cs.aau.dk/~normark/prog3-03/html/notes/fu-intr-1_themeslisp-scheme.html
http://clisp.cons.org/propaganda.html
http://swiss.csail.mit.edu/projects/scheme/
http://www.levenez.com/lang/history.html#01
http://www.apl.jhu.edu/~hall/lisp.html
http://www.cui.unige.ch/dbresearch/Enseignement/analyseinfo/LISP/BNFindex.html
4-25-08
CS 331
Lisp/Scheme
22