Transcript function

CSE3302
Programming Languages
(n-n-n-notes)
Summer 2003
Dr. Carter Tiernan
Summer 2003
Programming Languages
Ch. 9
1 jcmt
Functional Programming
• List Processing - LISP
• Complex interrelationships among data
• Recursion in conjunction with
conditional expressions
• Primitive list-handling subroutines
• Applicative language
Summer 2003
Programming Languages
Ch. 9
2 jcmt
LISP
• Function applications
– Prefix (Polish) notation : flexibility
– Fully parenthesized : no precedence rules
• Symbolic data
– Lists of symbols called atoms
– List is ONLY data structure in LISP
Summer 2003
Programming Languages
Ch. 9
3 jcmt
Lists
• S-expressions
– Function applications are evaluated
– Quoted lists are treated as data
• Programs and data represented the
same way
– Convenient for one program to generate
and call for execution of another
– Simple to write program manipulators
Summer 2003
Programming Languages
Ch. 9
4 jcmt
LISP Execution
• Usually interpreted and often
interactive
• Functions
– Pure : compute a value only
• eq, plus, difference, etc.
– Pseudo : have side effects on computer state
• set, defun, etc.
Summer 2003
Programming Languages
Ch. 9
5 jcmt
Data Structures
• Constructor : list
• Primitives : atoms
– Numeric (integer and floating point)
• Many ops provided: arithmetic, increment,
decrement, max, min, relational, predicates
– Nonnumeric character strings
• Limited ops: comparisons for equality
• nil (false, empty set)
• null is the test op
Summer 2003
Programming Languages
Ch. 9
6 jcmt
Constructor
• List
–
–
–
–
–
Surrounded by parentheses
Separated by blanks
Zero, one or more elements
Can contain lists
() equivalent to nil; called empty or null list
Summer 2003
Programming Languages
Ch. 9
7 jcmt
Accessing Parts of a List
• Car
– Selects the first element of a list
• Cdr
– Returns all of a list except its first element
• Car and Cdr are selectors
• Car and Cdr can be combined to access
interior parts of a list: ex. caadr
Summer 2003
Programming Languages
Ch. 9
8 jcmt
Building a list
• Cons
– Creates a list from a first element and a list
– Is the inverse of car and cdr
– Example:
• (car ‘(to be or not))
• (cdr ‘(to be or not))
• (cons ‘to ‘(be or not))
Summer 2003
= to
= (be or not)
= (to be or not)
Programming Languages
Ch. 9
9 jcmt
Info Representation
• Property lists
– (p1 v1 p2 v2 … pn vn) where pn is the nth
property and vn is the value of that
property
– P-lists give flexibility
– Easy to define a function to get properties
Summer 2003
Programming Languages
Ch. 9
10 jcmt
Info Representation
• Association lists
– ((a1 v1) (a2 v2) … (an vn))
– Handles properties which are flags or
properties with multiple values
Summer 2003
Programming Languages
Ch. 9
11 jcmt
Recursive list construction
• Append two lists together
– Identify simplest cases
• (append ‘() L) = L
• (append L ‘()) = L
– Reduce other cases to the simplest cases
• (append L M) = (cons (car L) (append (cdr L) M)
– (defun append (L M)
(if (null L))
M
(cons (car L) (append (cdr L) M) ))
Summer 2003
Programming Languages
Ch. 9
12 jcmt
Atoms
• Created by mentioning them
• Have properties and relations (p-list)
– Print name / pname
– putprop adds a property to an atom
– apval denotes the binding of an atom to a
value
– set binds an atom
– symbol-plist shows property list of an atom
Summer 2003
Programming Languages
Ch. 9
13 jcmt
List representation
• Linked list
• Cells in the list have a right and a left
– Right part points to next cell in list
– Left part points to value of the cell
• Data and programs both represented
the same way
– Program linked list called an expression tree
Summer 2003
Programming Languages
Ch. 9
14 jcmt
List Primitives
• Efficient
–
–
–
–
Car returns a left part
Cdr returns a right part
Cons requires storage allocation for new cell
Car, Cdr, and Cons do not change values
• Sublists can be shared
• Pseudo-functions alter lists
– rplaca, rplacd
– Have same drawbacks as aliasing
Summer 2003
Programming Languages
Ch. 9
15 jcmt
Conditional expression
• Cond
– Mimics mathematical notation
– Logical ops are defined in terms of the
conditional
• And & Or
– Operands are evaluated sequentially
– Conditional interpretation vs. strict
Summer 2003
Programming Languages
Ch. 9
16 jcmt
LISP on omega
• LISP interpreter on both omega and
gamma
• Invoke by typing ‘lisp’
• Exit by typing ‘(quit)’
• CMU Common Lisp
• Info at www.cons.org/cmucl/
Summer 2003
Programming Languages
Ch. 9
17 jcmt
Iteration
• Performed by recursion
• Reduction
– Perform some op on every element of a list
– Uses a binary function to reduce a list to a single
value
• Mapping
– Apply a function to every element of a list
– Returns a list of the results
• Filtering
– Forms a sublist containing all elements that satisfy
some property
Summer 2003
Programming Languages
Ch. 9
18 jcmt
Functional arguments
• Abstracting out pattern
• Mapcar
• Filter
• Reduce
• Suppress details
• Simplify combination
Summer 2003
Programming Languages
Ch. 9
19 jcmt
Recursive Interpreters
• Arranged by cases
– Atoms
• Numeric
• Nonnumeric
– Quote
– Conditional
– Functions
Summer 2003
Programming Languages
Ch. 9
20 jcmt
Interpreters
• Primitive ops performed explicitly
• User-defined functions
–
–
–
–
Evaluate parameters
Bind formals to actuals
Add bindings to environment
Evaluate function in environment
Summer 2003
Programming Languages
Ch. 9
21 jcmt
Environment of evaluation
• Arguments going to (apply f x a) (p.380)
– f the function - lambda expression
– x the parameters - bound formals
– a the environment - existing environment
with the addition of the bound formals
• Universal function
Summer 2003
Programming Languages
Ch. 9
22 jcmt
Static scoping
• Closure to indicate environment of
definition - function keyword
– Instruction part (ip) - program, lambda expr.
– Environment part (ep) - definition environment
• (closure ip ep)
• User-defined functions can be
– Dynamically scoped lambda expressions
– Statically scoped function closures
Summer 2003
Programming Languages
Ch. 9
23 jcmt
Incompatible scope rules
• Options
– Adopt uniform static scoping
– Use default static scoping but allow
“special” dynamic scoping
Summer 2003
Programming Languages
Ch. 9
24 jcmt
Storage reclamation
• Explicit erasure
– Work for programmers
– Security problems (dangling pointers)
• Automatic reclamation
– Reference counts
– Garbage collection
Summer 2003
Programming Languages
Ch. 9
25 jcmt
Reference counts
• Accessible cells are referenced
• Reference count keeps track of how
many other cells reference the current
one
• Count must be incremented and
decremented correctly
• Cells with zero count are added to the
free list
Summer 2003
Programming Languages
Ch. 9
26 jcmt
Reference counts
• Cycles defeat reference counts
– Cyclic reference boosts the count of each
member plus one member has an outside
reference.
– If outside reference goes away, cycle still
has references internally but no access from
anywhere else in program
– Allowing cycles is an open issue
Summer 2003
Programming Languages
Ch. 9
27 jcmt
Garbage Collection
• When storage becomes low, system
starts up garbage collection
• Mark and sweep process
– Starting at roots mark all cells that can be
reached recursively moving from each cell
to its children
– When all are marked, sweep through
memory from top, free unmarked cells and
reset flags on marked cells
Summer 2003
Programming Languages
Ch. 9
28 jcmt
Garbage Collection
• Wreaks havoc on execution time
• Non uniform and unpredictable
• Approaches to more efficiency include
– Continuous garbage collection
– Parallel
Summer 2003
Programming Languages
Ch. 9
29 jcmt
LISP
• AI - represent and manipulate complex
interrelationships among symbolic data
• Suited to ill-specified problems
• Easy to manipulate LISP programs in LISP
Summer 2003
Programming Languages
Ch. 9
30 jcmt