Lisp – Introduction
Download
Report
Transcript Lisp – Introduction
Lisp – Introduction
יעל נצר
מערכות נבונות
סמסטר ב'
תשס"ו
• http://clisp.cons.org/
• http://sourceforge.net/projects/clisp
LISP – (LISt Processing)
1. Parenthesized prefix notation: (+ 2 4)
2. Expressions can be nested: (- (+ 2 3 4 5) (* 2 5))
3. Evaluation rule:
apply function to value of arguments.
4. Symbolic computation: other types
Primitive: numbers, characters, strings, symbols.
Compound: lists.
(append '(a b) '(c d)) --> (a b c d)
Quote: block the evaluation of the following expression.
'(a b) --> (a b)
(a b) --> error: a undefined function.
5. Self-evaluating types: numbers, characters, strings.
6. Symbols as variables - not case sensitive.
VARIABLES
1. Define new objects in terms of others +
name them.
2. (setf p '(a b)) --> (a b)
p --> (a b)
3. Symbols also used to name functions.
SPECIAL FORMS:
1. Forms not evaluated according to the
evaluation rule.
2. Special forms:
defun, defparameter, setf, let, case, if,
function, quote.
LISTS
1. Primitive aggregating type.
2. Primitive functions: first, second, ..., length,
last. append, cons, list.
DEFINING NEW FUNCTIONS:
1. (defun <name> (<parameters>)
"doc"
<body>)
(defun last-name (name)
"Select last name from a name represented
as a list."
(first (last name)))
(last-name '(john r vandamme)) --> vandamme
(last-name '(john quirk MD))
--> MD
2. Importance of abstraction.
(defun first-name (name) (first name))
USING FUNCTIONS:
1. (setf names '((john x ford) (peter p rabbit) (fabianna f
wayne)))
(mapcar #'last-name names) --> (ford rabbit wayne)
#' from name of function to function object.
mapcar primitive.
2. (defparameter *titles*
'(Mr Mrs Miss Madam Ms Sir Dr Admiral Major General))
(defun first-name (name)
"Select first name from a list representing a name."
(if (member (first name) *titles*)
(first-name (rest name))
(first name)))
(if <test> <then-part> <else-part>)
(first-name '(Madam Major General Paula Jones)) --> Paula
3. Trace functions
HIGHER ORDER FUNCTIONS
1. Functions as first-class objects: can be
manipulated, created, modified by running code.
2. Apply: (apply #'+ '(1 2 3 4)) --> 10
3. Funcall: (funcall #'+ 1 2) --> 3
(funcall #'+ '(1 2)) -->
error (1 2) is not a number.
4. Function constructor: lambda.
(lambda (parameter ...) body...):
non atomic name of a function.
((lambda (x) (+ x 2)) 4) --> 6
(funcall #'(lambda (x) (* x 2)) 4) --> 8
***Can create functions at run time.***
OTHER DATA TYPES
1. Strings: (length "abc") --> 3
2. Many number types.
LISP EVALUATION RULE
1. Every expression is either a list or an atom.
2. Every list to be evaluated is either a special form or a function
application.
3. A special form expression is a list whose first element is a special
form operator and is evaluated according to the special rule of
that operator.
4. A function application is evaluated by first evaluating the
arguments (the rest of the list) and then finding the function
named by the first element of the list and applying it to the list of
evaluated arguments.
5. Every atom is either a symbol or a non-symbol.
6. A symbol evaluates to the most recent value assigned to the
variable.
7. A non-symbol atom evaluates to itself.
WHAT MAKES LISP DIFFERENT
1. Built-in support for Lists.
2. Automatic memory management.
3. Dynamic typing.
4. First-class functions.
5. Uniform syntax.
6. Extensibility
Why LISP?
– Especially designed for symbol manipulation.
– Provides built-in support for lists (“everything is a
list..”)
– Automatic storage management (no need to
keep track of memory allocation).
– Interactive environment, which allows programs
to be developed step by step. That is, if a change
is to be introduced, only changed functions need
to be recompiled.
Everything's a List!
• Data
(a b c)
• Functions
(defun plus (x y)
(+ x y))
• Simple syntax:
(function-name arg1 arg2 …)
Interpreted & interactive
• Interpreted
• Interactive
USER(1): 12
12
USER(2): (+ 12 3)
15
USER(3): (setf Almost-age 31)
31
USER(4): Almost-age
31
USER(5): 'Almost-age
ALMOST-AGE
USER(6):
Symbolic
• Why do we care about symbols?
– Understand human cognition with a language
like symbolic processing
Physical Symbol System Hypothesis
"A physical symbol system has the
necessary and sufficient means for
general intelligent action." (Newell &
Simon 1976)
• Physical symbol system
– Set of entities called symbols - physical
patterns that can occur as components
– Expressions (or symbol structures) built of
symbols
Dynamic
• Functions are first-class objects
– Pass functions as arguments to other functions
USER(1): (+ 1 2 3)
6
USER(2): (apply #'+ '(1 2 3))
6
One Function, and a Side of Fries, To Go
• Create functions on the fly
USER(1): (funcall #'(lambda (x y) (+ x y))
17 14)
31
• Lisp contains itself: eval
Name Calling
• Lisp remembers function names separately
from variable names
USER(22): (defun add (x y) (+ x y))
ADD
USER(23): (setf add 9)
9
USER(24): add
9
USER(25): #'add
#<Interpreted Function ADD>
Basic terminology
• Atoms: word-like indivisible objects which can be numbers or symbols.
• Lists: sentence-like objects formed from atoms or other lists, and
enclosed in parentheses.
• S-expressions: compositions of atoms and lists.
• Procedures: step by step specifications how to do something.
– Primitives: procedures supplied by the LISP itself
Example: (+ 5 6)
– User-defined procedures: procedures introduced by the programmer.
Example: (students 'anna)
• Program: a collection of procedures working together.
S-expressions
• An s-expression can have other s-expressions nested in it.
Examples:
(+
(* 5 7) ( / 2 4))
(This (is a dog) (or a cat))
• Expressions can be interpreted both, procedurally and
declaratively.
– If interpreted procedurally, an expression provides a direction
for doing something. Such an expression is called a form, and
its first element is the name of a procedure to be used to
produce the value.
– The process of computing the value of an expression is called
evaluation.
– If interpreted declaratively, expressions represent data.
Data and procedures have the same syntax.
Evaluation of atoms
• The value of a number is the number itself.
Example: 5 ==> 5
• The value of a string is the string itself.
Example: “Nice day” ==> “Nice day”
•
•
•
•
The value of the symbol T is T (true).
The value of the symbol NIL is NIL (false).
The symbol NIL and the empty list ( ) are the same thing.
Variables are names of memory locations. The contents stored in a
given memory cell is the value of the variable serving as a name of this
location.
Example: Let x be a variable, and 5 be the contents of the memory cell called x.
Then, the value of x is 5.
Numbers
•
•
•
•
Integers: 179, 45
Ratio: 5/7, 7/9
Floating point: 5.2, 7.9
Examples:
* (/ 25 5)
5
* (/ 46 9)
46/9
; do not divide evenly
* (float (/ 46 9))
5.111111
* (round (/ 46 9))
5
; the nearest integer
1/9
; the remainder
More numeric primitives
* (- 6)
-6
* (- -6)
6
* (max 5 7 2)
7
* (min 5 7 2)
2
* (sqrt (* (+ 1 3) (* 2 2)))
4.0
* (+ (round (/ 22 7)) (round (/ 7 3)))
5
* (+ 2 2.5)
4.5
* (expt 3 6)
729
* (sqrt 81)
9.0
* (sqrt 82)
9.055386
* (abs 6)
6
* (abs -6)
6
Problems:
1. Write a function (power 3 2) = 3^2 = 9
2. Write a function that counts the number of atoms in an
expression.
(count-atoms '(a (b) c)) --> 3
3. (count-anywhere 'a '(a ((a) b) a)) --> 3
4. (dot-product '(10 20) '(3 4)) --> 10x3 + 20x4 = 110
5. Write a function (flatten '(a (b) () ((c)))) --> (a b c)
which removes all levels of parenthesis and returns a flat list
of
atoms.
6. Write a function (remove-dups '(a 1 1 a b 2 b)) --> (a 1 b 2)
which removes all duplicate atoms from a flat list.
(Note: there is a built-in remove-duplicates in Common Lisp,
do not use it).
Solutions 1-3
(defun power (a b)
"compute a^b - (power 3 2) ==> 9"
(if (= b 0) 1
(* a (power a (- b 1)))))
(defun count-atoms (exp)
"count atoms in expresion - (count-atoms '(a (b) c)) ==> 3"
(cond ((null exp) 0)
((atom exp) 1)
(t (+ (count-atoms (first exp)) (count-atoms (rest exp))))))
(defun count-anywhere (a exp)
"count performances of a in expresion (count-anywhere 'a '(a ((a) b) (a))) ==> 3"
(cond ((null exp) 0)
((atom exp) (if (eq a exp) 1 0))
(t (+ (count-anywhere a (first exp))
(count-anywhere a (rest exp))))))
Solutions
(defun flatten (exp)
"removes all levels of paranthesis and returns flat list of atomsi
(flatten '(a (b) () ((c)))) ==> (a b c)"
(cond ((null exp) nil)
((atom exp) (list exp))
(t (append (flatten (first exp))
(flatten (rest exp))))))