CSE341, Winter 1997
David Notkin
Lecture #8 Notes
Announcements
- Today's Perlis epigram: "Programming is an unnatural
act."
- Next week:
- ML assignment is due on Tuesday.
- Quiz #1 on Thursday, in your rooms for your sections.
- On functional programming and ML.
- CLP(R) and constraint logic programming starts on Monday (6
lectures).
- CLP(R) minor assignment goes out Monday and is due Friday
(the original handout said Thursday).
- Reading for Monday is on the Web page.
Today's Instructional Objectives
- Parts of ML we didn't study, and why.
- Some cool things about functional programming languages.
ML stuff we didn't study
- The major aspect of ML that we didn't study is the module
system
- The primary features of the ML module system include the ability
to group items together, the ability to compile pieces of your
program separately, the ability to hide (encapsulate) the representation
of items, and to allow for easier change and reuse of code
- That is, they provide basically what you're used to thinking
about as abstract data types, and they make for better software
engineering of software systems
- In essence, they give the ability to separate the notion of
an interface from that of an implementationroughly, interfaces
define "what" and implementations define "how"
- "Structures are collections of types, datatypes, functions,
exceptions, and other elements that we wish to encapsulate."
Ullman, p. 145.
- "Signatures are collections of information describing
the types and other specifications for some of the elements of
a structure." ibid.
- "Functors are operations that take one or more structures
and produce another structure that combines them in some way."
ibid.
- We won't cover themeven though they are quite coolbecause
they aren't especially special. That is, other language paradigms
have pretty similar things. (The exception might be functors,
which really have a ton of cool uses.)
- We aren't discussing arrays and refs, because they are compromises
to the functional programming paradigm (well, arrays aren't entirely,
if you don't care about performance).
- We won't cover records, because they are kind of sort of just
tuples with names, not numbers, for fields.
Functional Programming
- On Wednesday I ranted and raved about why the functional programming
paradigm shows such wonderful promise.
- Here are some other interesting concepts about functional
programming languages.
- I will have to get a little mathematical on you; well, we
are talking about functions, after all.
- There are a few pages linked onto the class web site that
provide some basic added material on the -calculus, which I'll
breeze through
- You're responsible for the high-level ideas only
- ML is an eager functional programming language (for
this level of understanding, you can also talk about eager languages
being strict languages)
- In essence, this means that the arguments to a function are
evaluated before the function is evaluated.
- Remember the two versions of sumInts
that we looked at last week? Ullman suggested an alternative
that is both simpler and beautifully functional:
- fun file_to_chars f (*
maps a file to a list of characters *)
fun remove_white_space listChars
(* removes all extraneous whitespace *)
fun convert_to_int_list listChars (* converts list to list of
ints *)
fun sumInts file =
reduce(intplust,
convert_to_int_list(remove_white_space(file_to_chars
f)));
- But this walks the lists many, many times; that's avoided
in the two versions in the book.
- What if for some reason we used a sentinel in the list to
mark its end (such as actually placing a -1
in the file)? If the sentinel was in the middle of the file,
then this beautiful version would read all the file, even though
it could stop at the sentinel.
- Even worse, what if we had an infinite length file? OK, so
that's kind of unlikely (although very very big files might not
be).
- Here's another example, probably more straightforward to understand
- fun snork x y = if (x
> 0) then x else y;
snork 3 (z/0);
- In ML, an eager language, the call to snork
barfs because of the zero-divide.
- ML provides andalso
and orelse
to do lazy evaluation of these boolean operators, but in
general, ML is strict.
- So, what would a lazy (or
non-strict) language let you do, really? And are
there any? Yes, there are: Haskell, Miranda, etc.
- The basic idea of lazy languages is to evaluate arguments
only when you need them
- So, in the snork
example above, there would be no problem in the invocation
shown.
- So, why?
- Well, suppose I really did want infinite length lists.
- What? How can I have them?
- Well, in math you don't mind infinite sets (all positive integers,
for instance); you even don't mind notation like {1,2,3,
}
- So why can't I talk about an infinite list using something
like [1,2,
]?
- Even if I could, what would I want them for?
- Here's a nice way to compute factorial in ML:
- fun factorial N = reduce(inttimes,OneToN
N);
- It's not hard to write OneToN
by constructing the list.
- But suppose you had a function around that returns the first
k elements of a list?
- Then you could write OneToN in a lazy language by writing
fun OneToN N = takeFirst N
[1,2,
];
- Why doesn't this work in an eager language?
- And think back to the SumInts
example to see the consequences of laziness.
- So, why wouldn't I always want a lazy functional language
- It let's you do cool things
- It never evaluates something that it doesn't have to
- So, Notkin, why didn't you teach us Haskell instead of this
cruddy old ML?
- Let me tell you a story about some mathematics called the
-calculus
- A function in the lambda calculus has a single basic form:
x,y,z expr
where the x,y,z are identifiers (the names don't matter, and there
is no restriction on the number of identifiers) representing the
function's arguments. The value of the lambda expression is a
mathematical function (not a number, or a set of numbers, or a
float, or a structure, or a Pascal procedure, or anything else).
- Application consists of applying this function given values
for the arguments. We show this by listing the values after the
lambda expression:
(x,y if x > y then x else y) 5 6
(x if x > 0 then 1 else if x < 0 then -1 else 0) ~9;
(x,y x+y) 5 6
- Application is defined using the beta-reduction rule, which
in essence replaces the formals with the values of the arguments
that are applied.
(x,y if x > y then x else y) 5 6
if 5 > 6 then 5 else 6
6
(x,y x+y) 5 6
5+6
11
- These can be well-represented using set theory and quantification,
but that's not true for all functions. Consider the following
definition:
f,g x g(f(x))
This is the compose function, which takes two functions, f and
g, and composes them (applies one and then the other).
(f,g x g(f(x))) abs incr 7
(x incr(abs(x))) 7
incr(abs(7))
2
Note that in this definition, the composition stands alone as
a function that defines (returns) another function.
- We need to make sure that we can represent various kinds of
data. The underlying problem is that the basic lambda calculus
doesn't have any atomic elements other than identifiers, and these
don't represent any basic notion on their own. This isn't so
different from a Turing machine, in which there are only two atoms,
0 and 1, from which everything else is constructed. We have to
show how to represent data from atomic elements. In some important
sense, we cheating in the definition of "plus" above,
since we don't know what integers are nor do we know what "+"
is.
- Let's think about non-negative integers. Let's use the following
function to represent zero. That is, every time we see the function,
we should think, "Oh, that means 0."
0 f x x
And another function for 1:
1 f x f x
2 f x f (f x)
3 f x f (f (f x))
- Think of f as the successor (incr by 1) function, and the
representation of integers as unary. This allows us to define
functions that represent all the non-negative integers. Note
that we are using the functions to represent the values, without
consideration for what arguments are passed for f and x. You
can then define add as:
add a b f x a f (b f x)
- To add 1 and 2 we apply as follows:
(a b f x a f (b f x)) (f x f x) (f x f (f x))
Applying beta-reduction to both arguments:
f x (f x f x) f ((f x f (f x)) f x)
f x (f x f x) f (f (f x))
x (f x f x) (f (f x))
f x f (f (f x))
This is very much like adding in unary on a Turing machine (which
many of you don't know about, either).
- To handle booleans define two functions:
true t f t
false t f f
Basically, all these define are two functions, each of which takes
two arguments; the function true returns the first of the two
arguments and the function false returns the second of the two
arguments. You can then define the conditional function:
cond b c a b c a
cond true 2 1
(b c a b c a) true 2 1
(c a true c a) 2 1
(a true 2 a) 1
true 2 1
(t f t) 2 1
(f 2) 1
2
Of course, 2 and 1 could be represented as above, too.
- A lambda expression has reached normal form if no reduction
other than renaming variables can be applied. Not all expressions
have such a normal form. The normal form is in some sense the
value of the computation defined by the function.
- One Church-Rosser theorem in essence states that for the lambda
calculus the normal form (if any) is unique for an expression.
- A normal-order reduction sequentially applies the leftmost
available reductions. An applicative-order reduction sequentially
applies the leftmost innermost reduction first. This is a little
like top-down vs. bottom-up parsing and choosing what to reduce
when.
- The other Church-Rosser theorem in essence states that if
there is a reduction to a normal form, then there is a normal-order
reduction to normal form. (This does not hold for applicative-order
reductions.)
Example:
(x y) ((x x x) (x x x)) never reduces in applicative-order
(x y) ((x x x) (x x x)) reduces to y directly in normal-order
- Basically, normal-order defines a kind of lazy (non-strict)
semantics, where values are only computed as needed, in contrast
to applicative-order, which defines a kind of eager (strict) semantics,
where values for functions are computed regardless of whether
they are needed.
- Church found a theorem that shows that any recursive function
can be written non-recursively in the lambda calculus. Which
means that we can use recursion without thought, as we wish, in
defining programs in functional languages. (This requires some
cool mathematics and functional operators called fixpoint stuff,
but it's way beyond what we can do here.)