Transcript complangLisp

Comparative Programming
Languages
Functional programming with
Lisp/Scheme
Fundamentals of Functional
Programming Languages
• The objective of the design of a functional programming
language (FPL) is to mimic mathematical functions to the
greatest extent possible
• The basic process of computation is fundamentally
different in a FPL than in an imperative language
– In an imperative language, operations are done and the results are
stored in variables for later use
– Management of variables is a constant concern and source of
complexity for imperative programming
• In an FPL, variables are not necessary, as is the case in
mathematics
CS 363 Spring 2005 GMU
2
Lisp
• Lisp – based on lambda calculus (Church)
– Uniform representation of programs and data
using single general data structure (list)
– Interpreter based (written in Lisp)
– Automatic memory management
– Evolved over the years
– Dialects: COMMON LISP, Scheme
CS 363 Spring 2005 GMU
3
Scheme
• Scheme is a functional programming
language and a dialect of Lisp. It was
developed by Guy L. Steele and Gerald Jay
Sussman at MIT
• Use Programming Languages ->Dr. Scheme
here in the Comp Sys lab
CS 363 Spring 2005 GMU
4
Common Lisp
• Use: clisp for Common Lisp here in the
systems lab
CS 363 Spring 2005 GMU
5
Scheme (dr scheme, guile)
(define (gcd u v)
(if ( = v 0)
u
(gcd v (remainder u v))
)
)
(define (reverse l)
(if (null? l) l
(append (reverse (cdr l))(list (car l)))
)
)
CS 363 Spring 2005 GMU
6
Scheme (dr scheme, guile)
Using guile (gnu scheme):
(load "slides.scm")
(gcd 56 108) --> 4
(reverse '(2 3 556)) --> (556 3 2)
CS 363 Spring 2005 GMU
7
Common Lisp (clisp)
(defun mygcd (u v)
(if (= v 0)
u
(mygcd v (rem u v))
)
)
(defun myreverse (l)
(if (null l) l
(append (myreverse (cdr l))(list (car l)))
)
)
;; (load "slides.lsp"), (mygcd 56 108) --> 4
;; (myreverse '(2 3 556)) --> (556 3 2)
8
Scheme
(define (gcd u v)
(if ( = v 0)
u
(gcd v (remainder u v))
)
)
• Once defined in the interpreter:
 (gcd 25 10)
5
9
Scheme/Lisp
expression
→ atom | list
atom
→ number | string
| identifier | character | boolean
list
→ ‘(‘ expression-sequence ‘)’
expression-sequence → expression
| expression-sequence expression
10
Scheme Expression vs. C
In Scheme:
(+ 3 (* 4 5 ))
(and (= a b)(not (= a 0)))
(gcd 10 35)
In C:
3+4*5
(a = = b) && (a != 0)
gcd(10,35)
11
Evaluation Rules for Scheme
Expressions
1. Constant atoms (numbers, strings)
evaluate to themselves
2. Identifiers are looked up in the current
environment and replaced by the value
found there (using dynamically
maintained symbol table)
3. A list is evaluated by recursively
evaluating each element in the list as an
expression; the first expression must
evaluate to a function. The function is
applied to the evaluated values of the rest
of the list.
12
Scheme Evaluation
To evaluate (* (+ 2 3)(+ 4 5))
1. * is the function – must evaluate the
two expressions (+ 2 3) and (+ 4 5)
2. To evaluate (+ 2 3)
1.
2.
3.
4.
3.
4.
+ is the function – must evaluation the two
2
expressions 2 and 3
2 evaluates to the integer 2
3 evaluates to the integer 3
+23=5
*
+
+
3 4
5
To evaluate (+ 4 5) follow similar steps
* 5 9 = 45
13
Scheme Conditionals
If statement:
(if ( = v 0)
u
(gcd v (remainder u v))
)
Cond statement:
(cond (( = a 0) 0)
((= a 1) 1)
(else (/ 1 a))
)
(if (= a 0) 0 (/ 1 a))
14
Example of COND (Scheme)
(DEFINE (compare x y)
(COND
((> x y) (DISPLAY “x is greater than y”))
((< x y) (DISPLAY “y is greater than x”))
(ELSE (DISPLAY “x and y are equal”))
)
)
15
Example of COND (Lisp)
(defun compare (x y)
(COND
((> x y)(format t “x is greater than y”))
((< x y)(format t “y is greater than x”))
(t (format t “x and y are equal”))
)
)
16
Predicate Functions (Scheme)
EQ? takes two symbolic parameters;
it returns #T if both parameters
are atoms and the two are the same
e.g., (EQ? 'A 'A) yields #T
(EQ? 'A '(A B)) yields ()
– Note that if EQ? is called with list parameters, the
result is not reliable
– EQ? does not work for numeric atoms (use = )
17
Predicate Functions (Lisp)
EQ takes two symbolic parameters;
it returns #T if both parameters
are atoms and the two are the same
e.g., (eq 'A 'A) yields #T
(eq 'A '(A B)) yields nil
18
Predicate Functions (Scheme)
LIST? takes one parameter; it returns #T if the
parameter is a list; otherwise()
3. NULL? takes one parameter; it returns #T if the
parameter is the empty list; otherwise()
Note that NULL? returns #T if the parameter
is()
4. Numeric Predicate Functions
=, <>, >, <, >=, <=, EVEN?, ODD?,
ZERO?, NEGATIVE?
19
Predicate Functions (Lisp)
LISTP takes one parameter; it returns #T if the
parameter is a list; otherwise nil
3. NULL takes one parameter; it returns #T if the
parameter is the empty list; otherwise nil
Note that NULL returns #T if the parameter
is()
4. Numeric Predicate Functions
=, <>, >, <, >=, <=, EVENP, ODDP,
ZEROP
20