elements. Implement this:
This week in lecture we introduced the concept of tagged data. We have discussed using this approach to allow us to transparently change our representation of data without having to change code that makes use of the datai (AKA client code). While tags are useful in designing general programs you have probably seen them in other contexts as well.
Most of the world's data is tagged with type information (albeit not very well). You've seen file extensions everywhere: .html, .pdf, .doc, and so on. A graphical shell such as Windows will perform dispatch-on-type based on the extension of a file to open an appropriate program.
The need for dispatch-on-type arises frequently within programs. Consider an event-driven graphical application. The program waits in a loop for events to occur, and when something happens a function call returns with a data structure describing the event. On many systems, this event structure has a tag specifying whether it represents a mouse click, a keypress, or some other event:
(define (handle-event event)
(cond ((equal? (event-tag event) 'mouseClick) (handle-click event))
((equal? (event-tag event) 'keyPress) (handle-key event))
...))
Later this semester we will see how object-oriented programming in C++ makes this kind of control flow easier.
By now you are experienced at implementing and using operations on lists. Soon you will feel the same way about streams, which are abstractions that allow us to model potentially infinite sequences of data.
When is the idea of an infinite stream useful? Of course nothing in a real computer is infinite, so when we say ``infinite'' we really mean something more like ``indefinite''. In other words, we use streams to model sequences whose lengths we don't know in advance, or for which the concept of ``length'' is meaningless for some reason. Infinite sequences from mathematics such as ``all even integers'' clearly fall into this category, but streams have other uses as well. For example, sometimes when reading from a file or network connection we don't know how much data to expect; we just want to keep pulling in information until it stops.
A stream consists of 1) a current item, and 2) a ``promise'' to produce the rest of the stream on request. In Scheme, a stream is a cons cell whose cdr is a function that returns a stream. Note the similarity to the definition of a list. The critical difference is that the cdr is not itself a stream, but a delayed stream. This is what allows a stream to be ``infinite'': we don't insist on keeping the whole thing around at once; the rest of the stream is always a function call away.
This property of deferred evaluation allows stream definitions to be self-referential. Here is a generic definition that creates a stream where the rest of the stream is determined by an arbitrary function operating on the stream:
(define foo (cons first-el (lambda () (dosomething foo))))
For convenience, we use delay and force instead of an
explicit function. We can rewrite this example as:
(define foo (cons first-el (delay (dosomething foo))))
In a moment we will see an example of a stream with this form.
To actually get the rest of the stream, you have to force the promise that represents it: (force (cdr stream)).
Often we will write functions that create streams. Note that a function returning a stream is not the same thing as a stream.
The force function makes sure that a delayed expression is only evaluated once. Scheme remembers the value of a promise so that if it is forced a second time, the old value is returned instead of repeating the computation. Since there are no side effects, it doesn't matter how many times a computation is done. This is an example of how functional programming can be efficient.
Let's try to implement some of our familiar list operations for streams. For example, in the space below, implement stream-reverse:
Oops, it isn't possible. Some operations we're accustomed to using on lists still make sense for streams, and others emphatically do not. Try to list a few operations in each category:
| Works for both | Not on streams |
|---|---|
| car, cdr | append |
In dealing with streams, we write functions that return functions. What happens if we want to build and return functions that depend on passed parameters? For example, say I want to write a function n-adder that returns a function that adds n to its argument:
(define (n-adder n)
(lambda (x) (+ x n)))
Think about what happens when you call this function and its result like so:
> (define addsix (n-adder 6))
> (addsix 2)
8
This should strike you as somewhat strange. During the call to n-adder the variable n was locally bound to 6. When this call terminates, we would expect its local variables to vanish (as in C and many other languages). And yet the function it created, addsix, is still able to use the value of n to add 6 to its argument.
What happened was that we created a closure. A closure is a function together with an environment that remembers variable bindings from where the function was defined. When we returned that lambda expression, the binding of n to 6 was captured in this fashion. This is a result of Scheme's use of lexical scope. Under lexical scope, variable bindings are determined according to the text of a program rather than its execution history. In other words, to see which value of a symbol applies, you can just look at the function or let statement that contains it.
Closures are a seriously powerful programming technique. They give you more ways to specialize the behavior of functions according to parameters you specify (imagine creating closures that capture functional arguments). They also give you more control over variable scope: if you define two or more functions inside another function, any captured bindings will be shared among all of them, creating your own sort of mini-global scope.
A function that creates or modifies a stream has to take care of the two parts of the stream. Typically your new stream will consist of 1) some function of the first element of a given stream, and 2) a promise to run your function again on the rest of the stream in the future.
We need closures immediately in writing even simple stream functions. The utility of closures becomes more obvious when the behavior of the created stream depends on parameters:
(define (stream-add-n s n)
(cons (+ n (car s))
(delay (stream-add-n (force (cdr s)) n))))
Stream functions come in different flavors. stream-add-n is the ``simple'' kind; transforming a single stream element-by-element. Here we'll look at two more interesting kinds of stream functions.
The need to aggregate two infinite streams arises in many real-world applications. It sounds a bit greedy, at first: even though the streams are infinite, we need access to all the data in both. For example, imagine two temperature sensors, each producing continuous readings. We'd like to hide the fact that there are two sensors, and send all the data in a single stream to a network node for processing. Clearly, we can't ``append'' the streams, sending all the data from one followed by all the data from the other!
Instead, we have to interleave the streams:
(stream-interleave (a1 a2 a3 ...) (b1 b2 b3 ...)) => (a1 b1 a2 b2 a3 b3 ...)
Write stream-interleave:
(define (stream-interleave s1 s2)
Next, we'd like to reduce ``all'' the elements of a stream to a single value. Once again, it seems we will have to wait an awfully long time to get an answer. While we cannot reduce an entire stream to a single value ahead of time, we can produce a stream of successive reductions.
Start by making the problem finite: we know we can reduce over
elements. Implement this:
(define (stream-reduce-n func base s n)
Now we can implement stream-reduce by reducing for successive
values of :
(define (stream-reduce func base s)
(stream-reduce-help func base s 0))
(define (stream-reduce-help func base s n)
Filtering streams is a fun operation to think about. How well does it work?
(define (stream-filter pred stream)
This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -no_navigation -split 0 sec5.tex
The translation was initiated by CS51 Course Library on 2008-02-29