Transcript LISP

LISP
John McCarthy and Marvin Minsky formed MIT’s AI Project
in 1958.
McCarthy developed LISP in 1958 –1959.
Suggested reading: John McCarthy’s home page
http://www-formal.stanford.edu/jmc/
Functional Programming
• Imperative languages are based on Von Newman
Architecture.Functional programming paradigm is based
on mathematical functions.
•Mathematical function is mapping of members of one set,
called the domain set, to another set called the range set.
F(x) = 2x + 5
Functional Programming
• Evaluation is controlled by recursion and conditional
expressions rather than by sequencing and iterative
repetition that are common to imperative languages.
•Imperative languages refer to values stored in memory
locations, so side effects are generated.
•In mathematical functions there are no variables in
the sense of imperative languages, so there can be no
side effect.
Functional Programming
• Naming a function can be separated from defining a
function. Lambda notation is devised to define a nameless
function.
((x) x*x*x) (2)
Functional Forms
• A high order function, is one that either takes functions as
parameters or yields a function as its results, or both.
Function composition
hfg
If
f(x)  x + 2
g(x)  x * 3
Then,
h(x)  f(g(x)), or h(x)  (3 * x) + 2
Functional Forms
Construction
• Is a functional form that takes a list of functions as
parameters and collects the results in a list.
Let
f(x)  x * x
g(x)  x * 3
h(x)  x / 2
then,
[f, g, h](4) yields (16, 12, 2)
Functional Forms
Apply-to-all
• Is a functional form that takes a single functions as a
parameter and and applies it to a list of arguments.
Let
h(x)  x * x
then,
(h, (2, 3, 4)) yields (4, 9, 16)
Fundamentals of Functional Programming
In imperative programming an expression is evaluated and
the result is stored in memory location which is
represented as a variable in the program.
A purely functional programming language does not use
variables and assignment statements. Without variables iterative
constructs are not possible. Repetition must be done by
recursion.
The execution of a function always produces the same result
when given the same parameters. This is called referential
transparency.
Fundamentals of Functional Programming
Although functional languages are often implemented with
interpreters, they can also be complied.
Functions in imperative languages have restrictions on the types
of values that can be returned. In many languages only scalar
types are allowed. More importantly, they can not return a
function.
Imperative languages may have functional side effects.
LISP
• LISP was the first functional programming language.
• With the exception of the first version all LISP dialects
include imperative language features such as, imperative
style variables, assignment statements, and iteration.
Symbolic Expressions, the Syntactic Basis
of LISP
• The syntactic elements of the LISP programming language are
symbolic expressions.
• Both programs and data are represented as s-expressions. An sexpression may be either an atom or a list.
• Symbolic atoms are composed of letters numbers and certain nonalphanumeric characters (* - + $ % ^ &_ > < )
• A list is a sequence of either atoms or other lists separated by blanks
and enclosed in parentheses.
Examples
• (A B C D)
• (A (B C) D (E (F G)))
Concepts behind LISP
• McCarthy thought that the processing of symbolic links
is more natural than Turing machines.
• One of the common requirements of the study of
computation is that one must be able to prove certain
computability characteristics of the whole class of
whatever model of computation is being used.
• In the case of Turing machine model one can construct a
universal Turing machine that can mimic the operations
of any Turing Machine.
Concepts behind LISP
• From this emerged a universal LISP function that could
evaluate any other function in LISP.
• The first requirement for the universal LISP function
was a notation that allowed functions to be expressed in
the same way data was expressed.
• Function calls were specified in a prefix list form called
Cambridge Polish.
Concepts behind LISP
(function_name arg_1 … arg_n)
Example
(+57)
evaluates to 12.
Examples
• (- (+ 3 4) 7)
0
• (=(+ 2 3) 5)
t
• (list 1 2 3 4)
• (nth 0(list a b c d)
(1 2 3 4)
a
• In evaluating a function LISP first evaluates its arguments
and then applies the function indicated by the first element
of the expression to the results of these evaluations. For
example in evaluating the expression
(+ (* 2 3) (* 3 5))
• LISP first evaluates the arguments (* 2 3) and (* 3 5).
These results are then passed to the top level addition
which is evaluated, returning 21.
Definition
S-Expression
An s-expression is defined recursively:
1. An atom is an s-expression.
2. If s1, s2,...,sn are s-expressions,
then so is the list (s1, s2,...,sn).
• A list is a non-atomic expression.
• In evaluating an s-expression:
– If the s-expression is a number, return the value of the
number.
– If the s-expression is an atomic symbol, return the value
bound to that symbol; if it is not bound then it is an
error.
– If the s-expression is a list, evaluate the second through
the last arguments and apply the function indicated by
the first argument to the result.
Control of LISP Evaluation: quote and eval
The purpose of the quote is to prevent evaluation of sexpression that should be treated as data rather than an
evaluable form.
•(quote(a b c ))
•(quote(+1 3))
•(list(+1 2) (+ 3 4))
•(list ‘(+ 1 2) ‘(+ 3 4))
•(>(* 5 6) (+ 4 5))
(‘(a b c ))
(‘(+ 1 3))
(3 7)
(a b c)
(+ 1 3 )
((+ 1 2) (+ 3 4))
t
Control of LISP Evaluation: quote and eval
eval is a complement to quote.
(quote(+ 2 3))
(+ 2 3)
(eval(quote(+ 2 3)))
5
Programming in LISP: Creating New Functions
LISP supports a large number of built in functions
– Arithmetic functions supporting both integers and real
numbers.
– Program control functions
– List manipulation and other data structuring functions.
– Input/Output functions
– Forms for the control of function evaluation
– Functions for the control of the environment and
operating system.
(defun square(x)
(* x x))
>(square 5)
25
; causes 5 to be bound to x
(defun <function name> (<formal parameters>) <function body
(defun hypotenuse(x y)
(sqrt(+ (square(x)) (square(y))))
Program Control in LISP: Conditionals
and Predicates
cond takes as arguments a number of condition - action pairs.
cond
(<condition1> <action1>)
(<condition2> <action2>)
................
(<conditionn> <actionn>)
(defun absolute-value(x)
(cond ((< x 0) (-x))
((> = x 0) (x))))
(defun absolute-value(x)
(cond ((< x 0) (-x))
(t x)))
if takes three arguments
(defun absolute-value(x)
(if (< x 0 ) (-x) x ))
Predicates
A predicate is a LISP function that returns nil to indicate ‘false’ and
anything other than nil to indicate ‘true’.
> (= 9 (+ 4 5))
t
>(oddp 4)
nil
Examples to arithmetic predicates are: <, >, =, oddp, evenp, zerop, plusp,
minusp.
>(member 3 ‘(1 2 3 4 5))
(3 4 5)
All Boolean functions are short circuit in Common LISP. They
return a value as soon as the result is determined.
>(and(t t nil t))
nil
>(or( t nil t t)
t
Functions, lists, and Symbolic Computing
Using nth it is possible to define access functions for the various fields of
a data record.
Example
Suppose a record consists of the fields name, salary, employee number.
>(defun name-field(record)
(nth 0 record))
>(name-field ‘((Ada Lovelance) 45000.00 38519))
(Ada Lovelance)
>(defun first-name(name)
(nth 0(name))
>(first-name(name-field ‘((Ada Lovelance) 45000.00 38519)))
Ada
list is a built in LISP function.
>(list 1 2 3 4)
(1 2 3 4)
>(defun build-record(name salary emp-number)
(list name salary emp-number))
>(build-record ‘((Ada Lovelance) 45000.00 38519))
((Ada Lovelance) 45000.00 38519)
Using build record and the access functions we may
construct functions that return a modified copy of a record .
(defun replace-salary-field(record new-salary))
(build-record (name-field record)
new-salary
(number-field record)))
>(replace-salary-field ‘(((Ada Lovelance) 45000.00 38519)
((Ada Lovelance) 50000.00 38519)
50000.00))
Lists as Recursive Structures
The basic functions for accessing the components of a list are
car and cdr.
car (first)
- Takes a list as its argument and returns the
first element of the list.
cdr (rest)
- Takes a list as its argument and returns the
list with the first argument removed.
>(car ’(a b c ))
a
>(cdr ‘(a b c))
(b c)
>(car(cdr ’(a b c d)))
b
A recursive approach to manipulate list structures to perform
an operation on each of the elements of a list
1. If the list is empty quit
2. Perform the operation on the first element of the list and
recur on the remainder of the list.
Common LISP predicates for list processing are
member : Determines whether an s-expression
is a member of a list.
length : Determines the length of a list.
Example:
Define ‘my-member’ which takes an atom and a list
as arguments and returns nil if the atom is not
present in the list, otherwise returns the portion of
the list containing the atom as the first element.
(defun my-member(element list)
(cond((null list) nil)
((equal element(car list)) list)
(t (my-member element (cdr list))))
>(my-member 4 ‘(1 2 3 4 5 6))
(4 5 6)
(defun my-length(list)
(cond((null list) 0)
(t (+ (my-length (cdr list) 1)))))
cons is a basic list constructor
(cons ‘A’ ‘(L I S))
(A L I S)
(cons ‘A’ B)
(A.B)
(cons ‘(A) ‘(L I S))
((A) L I S)
(defun filter-negatives (number-list)
(cond((null number-list) nil)
((plusp(car number-list)) (cons (car number-list)
(filter-negatives (cdr number-list))))
(t (filter-negatives(cdr number-list)))))
>(filter-negatives ‘(1 -1 2 3 -4 -5 6))
(1 2 3 6)
car and cdr tear lists apart and drive the recursion ; cons
selectively constructs the result as the recursion unwinds.
Recursion is used to scan the list element by element, as the
recursion unwinds the cons function reassembles the solution.
If cons is called with two lists as arguments it makes the
first of these a new first element of the second list,
whereas append returns a list whose elements are the
elements of the two arguments:
>(cons ’(1 2) ‘(4 5 6))
((1 2) 4 5 6)
>(append ’(1 2) ‘(4 5 6))
(1 2 4 5 6)
Lists are powerful representations for tree structures
especially for search and parse trees. In addition nested
lists provide a way of hierarchically structuring complex
data.
(1 2 3 4)
((1 2) 3 4)
car-cdr recursion adds one more dimension to simple cdr
recursion.
(defun count-atoms (list)
(cond ((null list) 0)
((atom list) 1)
(t (+(count-atoms(car list))
(count-atoms(cdr-list))))))
>(count-atoms ‘((1 2 ) 3 (((4 5 (6)))))
6
Functional Programming
(set ‘inc 0)
(defun f(x)
(set ‘inc (+ inc 1))
(+ x inc))
>(f 4)
5
>(f 4)
6
In this example x is a bound variable where inc is a free
variable.
All the variables that appear as the formal parameter of a function
are bound variables, and all the other variables that appear in the
body of the function are free variables.
When a function is called any bindings that a bound variable may
have in the global environment are saved and the variable is
rebound to the calling parameter.
After the function has completed execution, the original bindings are
restored. Thus setting the value of a bound variable inside a function
body has no effect on the global bindings of that variable
As it is seen from the example free variables in a
function definition are the primary source of side
effects in functions.
(defun fo(x)
(setq x (+ x 1))
(x))
The Assignment of Value
setq : The variable is assigned the value of the form.
set: symbol is assigned the value given
setf refers to memory location
(setq x 23)
;x assigned 23
(set a 999):
;arguments are evaluated
The Assignment of Value
setf regards the first argument as naming a memory location.
>(setf x ‘(a b c))
(a b c)
>x
>(setf(cdr x) ‘(2 3))
(a b c)
(2 3)
>(setf(car x) 1)
>x
1
(1 2 3)
>x
(1 b c)
Data types in Common LISP
Built in types are: integers, floating numbers, strings
and characters. LISP also includes structured types as
arrays, hash tables, sets, and structures .
Unlike other strongly typed languages as Pascal, in Lisp it is
the data objects that are typed rather than variables. Any
LISP symbol may bind to any object ; the object itself is
typed. Consequently LISP implements run time type
checking.
High-Order Functions and Procedural Abstraction
Functions that take other functions as parameters or return
them as results are called higher-order functions and
constitute an important tool for procedural abstraction.
(defun filter-evens(number-list)
(cond(null number-list) nil)
((oddp(car number-list))
(cons(car(number-list) (filter-evens(cdr number-list)))
(t filter-evens(cdr number-list))))
funcall takes as arguments a function and a series of arguments
and applies that function to those arguments:
>(funcall ‘plus 2 3)
5
(defun filter (list-of-elements test )
(cond(null list-of-elements) nil)
((funcall test(car number-list))
(cons(car(number-list) (filter (cdr list-of-elements) test))
(t (filter (cdr list-of-elements) test))))
The function, filter applies the test to the first element of the
list. If the test returns non-nil it conses the element onto the
result of filtering the cdr of the list; oterwise it just returns the
filtered cdr.
>(filter ‘(1 3 -9 5 -2 -7 6) ‘plusp)
>(filter ‘(1 a b c 5 7) ‘numberp)
(1 3 5 6)
(1 5 7)
Another important class of higher-order functions
consists of mapping functions.
>(mapcar ‘+ ‘(1 2 3) ‘(2 4 6)
(3 6 9)
Functional Arguments and Lambda Expressions
Lambda expressions allows the programmer to separate a
function definition from the function name. Without lambda
expressions the programmer must define every functiom in the
global environment using a defun even though the function may
be used only once.
((lambda (x y) (* x y) (30 40))
1200
((lambda (x y) (* x y) ()) 20 30)
nil
Lambda Expressions
((lambda (&optional x y) (list x y)))
((lambda &optional x y)
(nil nil)
(10 20)
(list x y)) 10 20)
((lambda &optional (x 0) (y 0))
(list x y)) 10 20)
(10 20)
Functional Arguments and Lambda Expressions
Lambda expressions allows the programmer to separate a
function definition from the function name. Without lambda
expressions the programmer must define every functiom in the
global environment using a defun even though the function may
be used only once.
>(funcall ‘(lambda( x y) (+ (*x x) y)) ( 2 3))
7
>(mapcar ‘(lambda(x) (* x x)) ‘(1 2 3 4 5))
(1 2 9 16 25)
Pattern Matching in Lisp
match takes two arguments and returns t if the expressions
match. Matching requires that both expressions have the same
structure as well as having identical atoms in corresponding
positions.
>(match ‘(likes bill wine) ‘(likes bill wine))
t
>(match ‘(likes bill ?) ‘(likes bill wine))
t
>(match ‘(likes bill ?) ‘(likes ? wine))
t
Homework
Define a LISP function that reverses a given list