From: Jim Pryor <profjim@jimpryor.net>
Date: Sun, 3 Oct 2010 05:46:36 +0000 (-0400)
Subject: continuing advanced
X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=3aee752272f074a9da41820f4dbda60d641e9809;ds=sidebyside

continuing advanced

Signed-off-by: Jim Pryor <profjim@jimpryor.net>
---

diff --git a/index.mdwn b/index.mdwn
index 4f115e85..d75578c9 100644
--- a/index.mdwn
+++ b/index.mdwn
@@ -19,7 +19,7 @@ It can help you check whether your answer to some of the homework questions work
 
 There is now a [library](/lambda_library) of lambda-calculus arithmetical and list operations, some relatively advanced.
 
-There's also a page of [advanced challenges and techniques](/advanced) for the untyped lambda-calculus.
+There's also a page of [advanced challenges and techniques](/lambda_advanced) for the untyped lambda-calculus.
 
 
 <!--
diff --git a/lambda_advanced.mdwn b/lambda_advanced.mdwn
index dbdf9c89..1f8ae61b 100644
--- a/lambda_advanced.mdwn
+++ b/lambda_advanced.mdwn
@@ -94,6 +94,361 @@ can use.
 	on P-numerals](http://okmij.org/ftp/Computation/lambda-calc.html#p-numerals).
 
 
-3.	Implementing (self-balancing) trees
+
+3.	**Sets**
+
+	You're now already in a position to implement sets: that is, collections with
+	no intrinsic order where elements can occur at most once. Like lists, we'll
+	understand the basic set structures to be *type-homogenous*. So you might have
+	a set of integers, or you might have a set of pairs of integers, but you
+	wouldn't have a set that mixed both types of elements. Something *like* the
+	last option is also achievable, but it's more difficult, and we won't pursue it
+	now. In fact, we won't talk about sets of pairs, either. We'll just talk about
+	sets of integers. The same techniques we discuss here could also be applied to
+	sets of pairs of integers, or sets of triples of booleans, or sets of pairs
+	whose first elements are booleans, and whose second elements are triples of
+	integers. And so on.
+
+	(You're also now in a position to implement *multi*sets: that is, collections
+	with no intrinsic order where elements can occur multiple times: the multiset
+	{a,a} is distinct from the multiset {a}. But we'll leave these as an exercise.)
+
+	The easiest way to implement sets of integers would just be to use lists. When
+	you "add" a member to a set, you'd get back a list that was either identical to
+	the original list, if the added member already was present in it, or consisted
+	of a new list with the added member prepended to the old list. That is:
+
+		let empty_set = empty  in
+		; see the library for definition of any
+		let make_set = \new_member old_set. any (eq new_member) old_set
+							; if any element in old_set was eq new_member
+							old_set
+							; else
+							make_list new_member old_set
+
+	Think about how you'd implement operations like `set_union`,
+	`set_intersection`, and `set_difference` with this implementation of sets.
+
+	The implementation just described works, and it's the simplest to code.
+	However, it's pretty inefficient. If you had a 100-member set, and you wanted
+	to create a set which had all those 100-members and some possibly new element
+	`e`, you might need to check all 100 members to see if they're equal to `e`
+	before concluding they're not, and returning the new list. And comparing for
+	numeric equality is a moderately expensive operation, in the first place.
+
+	(You might say, well, what's the harm in just prepending `e` to the list even
+	if it already occurs later in the list. The answer is, if you don't keep track
+	of things like this, it will likely mess up your implementations of
+	`set_difference` and so on. You'll have to do the book-keeping for duplicates
+	at some point in your code. It goes much more smoothly if you plan this from
+	the very beginning.)
+
+	How might we make the implementation more efficient? Well, the *semantics* of
+	sets says that they have no intrinsic order. That means, there's no difference
+	between the set {a,b} and the set {b,a}; whereas there is a difference between
+	the *list* [a;b] and the list [b;a]. But this semantic point can be respected
+	even if we *implement* sets with something ordered, like list---as we're
+	already doing. And we might *exploit* the intrinsic order of lists to make our
+	implementation of sets more efficient.
+
+	What we could do is arrange it so that a list that implements a set always
+	keeps in elements in some specified order. To do this, there'd have *to be*
+	some way to order its elements. Since we're talking now about sets of numbers,
+	that's easy. (If we were talking about sets of pairs of numbers, we'd use
+	"lexicographic" ordering, where `(a,b) < (c,d)` iff `a < c or (a == c and b <
+	d)`.)
+
+	So, if we were searching the list that implements some set to see if the number
+	5 belonged to it, once we get to elements in the list that are larger than 5,
+	we can stop. If we haven't found 5 already, we know it's not in the rest of the
+	list either.
+
+	This is an improvement, but it's still a "linear" search through the list.
+	There are even more efficient methods, which employ "binary" searching. They'd
+	represent the set in such a way that you could quickly determine whether some
+	element fell in one half, call it the left half, of the structure that
+	implements the set, if it belonged to the set at all. Or that it fell in the
+	right half, it it belonged to the set at all. And then the same sort of
+	determination could be made for whichever half you were directed to. And then
+	for whichever quarter you were directed to next. And so on. Until you either
+	found the element or exhausted the structure and could then conclude that the
+	element in question was not part of the set. These sorts of structures are done
+	using **binary trees** (see below).
+
+
+4.	**Aborting a search through a list**
+
+	We said that the sorted-list implementation of a set was more efficient than
+	the unsorted-list implementation, because as you were searching through the
+	list, you could come to a point where you knew the element wasn't going to be
+	found. So you wouldn't have to continue the search.
+
+	If your implementation of lists was, say v1 lists plus the Y-combinator, then
+	this is exactly right. When you get to a point where you know the answer, you
+	can just deliver that answer, and not branch into any further recursion. If
+	you've got the right evaluation strategy in place, everything will work out
+	fine.
+
+	But what if you're using v3 lists? What options would you have then for
+	aborting a search?
+
+	Well, suppose we're searching through the list [5; 4; 3; 2; 1] to see if it
+	contains the number 3. The expression which represents this search would have
+	something like the following form:
+
+		..................<eq? 1 3>  ~~>
+		.................. false     ~~>
+		.............<eq? 2 3>       ~~>
+		............. false          ~~>
+		.........<eq? 3 3>           ~~>
+		......... true               ~~>
+		?
+
+	Of course, whether those reductions actually followed in that order would
+	depend on what reduction strategy was in place. But the result of folding the
+	search function over the part of the list whose head is 3 and whose tail is [2;
+	1] will *semantically* depend on the result of applying that function to the
+	more rightmost pieces of the list, too, regardless of what order the reduction
+	is computed by. Conceptually, it will be easiest if we think of the reduction
+	happening in the order displayed above.
+
+	Well, once we've found a match between our sought number 3 and some member of
+	the list, we'd like to avoid any further unnecessary computations and just
+	deliver the answer `true` as "quickly" or directly as possible to the larger
+	computation in which the search was embedded.
+
+	With a Y-combinator based search, as we said, we could do this by just not
+	following a recursion branch.
+
+	But with the v3 lists, the fold is "pre-programmed" to continue over the whole
+	list. There is no way for us to bail out of applying the search function to the
+	parts of the list that have head 4 and head 5, too.
+
+	We *can* avoid some unneccessary computation. The search function can detect
+	that the result we've accumulated so far during the fold is now true, so we
+	don't need to bother comparing 4 or 5 to 3 for equality. That will simplify the
+	computation to some degree, since as we said, numerical comparison in the
+	system we're working in is moderately expensive.
+
+	However, we're still going to have to traverse the remainder of the list. That
+	`true` result will have to be passed along all the way to the leftmost head of
+	the list. Only then can we deliver it to the larger computation in which the
+	search was embedded.
+
+	It would be better if there were some way to "abort" the list traversal. If,
+	having found the element we're looking for (or having determined that the
+	element isn't going to be found), we could just immediately stop traversing the
+	list with our answer. Continuations will turn out to let us do that.
+
+	We won't try yet to fully exploit the terrible power of continuations. But
+	there's a way that we can gain their benefits here locally, without yet having
+	a fully general machinery or understanding of what's going on.
+
+	The key is to recall how our implementations of booleans and pairs worked.
+	Remember that with pairs, we supply the pair "handler" to the pair as *an
+	argument*, rather than the other way around:
+
+		pair (\x y. add x y)
+
+	or:
+
+		pair (\x y. x)
+
+	to get the first element of the pair. Of course you can lift that if you want:
+
+		extract_1st === \pair. pair (\x y. x)
+
+	but at a lower level, the pair is still accepting its handler as an argument,
+	rather than the handler taking the pair as an argument. (The handler gets *the
+	pair's elements*, not the pair itself, as arguments.)
+
+	The v2 implementation of lists followed a similar strategy:
+
+		v2list (\h t. do_something_with_h_and_t) result_if_empty
+
+	If the v2list here is not empty, then this will reduce to the result of
+	supplying the list's head and tail to the handler `(\h t.
+	do_something_with_h_and_t)`.
+
+	Now, what we've been imagining ourselves doing with the search through the v3
+	list is something like this:
+
+
+		larger_computation (search_through_the_list_for_3) other_arguments
+
+	That is, the result of our search is supplied as an argument (perhaps together
+	with other arguments) to the "larger computation". Without knowing the
+	evaluation order/reduction strategy, we can't say whether the search is
+	evaluated before or after it's substituted into the larger computation. But
+	semantically, the search is the argument and the larger computation is the
+	function to which it's supplied.
+
+	What if, instead, we did the same kind of thing we did with pairs and v2 lists? That is, what if we made the larger computation a "handler" that we passed as an argument to the search?
+
+		the_search (\search_result. larger_computation search_result other_arguments)
+
+	What's the advantage of that, you say. Other than to show off how cleverly you can lift.
+
+	Well, think about it. Think about the difficulty we were having aborting the
+	search. Does this switch-around offer us anything useful?
+
+	It could.
+
+	What if the way we implemented the search procedure looked something like this?
+
+	At a given stage in the search, we wouldn't just apply some function f to the
+	head at this stage and the result accumulated so far, from folding the same
+	function (and a base value) to the tail at this stage. And then pass the result
+	of doing so leftward along the rest of the list.
+
+	We'd also give that function a "handler" that expected the result of the
+	current stage as an argument, and evaluated to passing that result leftwards
+	along the rest of the list.
+
+	Why would we do that, you say? Just more flamboyant lifting?
+
+	Well, no, there's a real point here. If we give the function a "handler" that
+	encodes the normal continuation of the fold leftwards through the list. We can
+	give it another "handler" as well. We can also give it the underlined handler:
+
+
+		the_search (\search_result. larger_computation search_result other_arguments)
+				   ------------------------------------------------------------------
+
+	This "handler" encodes the search's having finished, and delivering a final
+	answer to whatever else you wanted your program to do with the result of the
+	search. If you like, at any stage in the search you might just give an argument
+	to this handler, instead of giving an argument to the handler that continues
+	the list traversal leftwards. Semantically, this would amount to *aborting* the
+	list traversal! (As we've said before, whether the rest of the list traversal
+	really gets evaluated will depend on what evaluation order is in place. But
+	semantically we'll have avoided it. Our larger computation  won't depend on the
+	rest of the list traversal having been computed.)
+
+	Do you have the basic idea? Think about how you'd implement it. A good
+	understanding of the v2 lists will give you a helpful model.
+
+	In broad outline, a single stage of the search would look like before, except
+	now f would receive two extra, "handler" arguments.
+
+		f 3 <result of folding f and z over [2; 1]> <handler to continue folding leftwards> <handler to abort the traversal>
+
+	f's job would be to check whether 3 matches the element we're searching for
+	(here also 3), and if it does, just evaluate to the result of passing `true` to
+	the abort handler. If it doesn't, then evaluate to the result of passing
+	`false` to the continue-leftwards handler.
+
+	In this case, f wouldn't need to consult the result of folding f and z over [2;
+	1], since if we had found the element 3 in more rightward positions of the
+	list, we'd have called the abort handler and this application of f to 3 etc
+	would never be needed. However, in other applications the result of folding f
+	and z over the more rightward parts of the list would be needed. Consider if
+	you were trying to multiply all the elements of the list, and were going to
+	abort (with the result 0) if you came across any element in the list that was
+	zero. If you didn't abort, you'd need to know what the more rightward elements
+	of the list multiplied to, because that would affect the answer you passed
+	along to the continue-leftwards handler.
+
+	A **version 5** list would encode this kind of fold operation over the list, in
+	the same way that v3 (and v4) lists encoded the simpler fold operation.
+	Roughly, the list [5; 4; 3; 2; 1] would look like this:
+
+
+		\f z continue_leftwards_handler abort_handler.
+			<fold f and z over [4; 3; 2; 1]>
+			(\result_of_fold_over_4321. f 5 result_of_fold_over_4321  continue_leftwards_handler abort_handler)
+			abort_handler
+
+
+		\f z continue_leftwards_handler abort_handler.
+			(\continue_leftwards_handler abort_handler.
+				<fold f and z over [3; 2; 1]>
+				(\result_of_fold_over_321. f 4 result_of_fold_over_321 continue_leftwards_handler abort_handler)
+				abort_handler
+			)
+			(\result_of_fold_over_4321. f 5 result_of_fold_over_4321  continue_leftwards_handler abort_handler)
+			abort_handler
+
+		and so on		
+		
+	Remarks: the `larger_computation_handler` should be supplied as both the
+	`continue_leftwards_handler` and the `abort_handler` for the leftmost
+	application, where the head 5 is supplied to f. Because the result of this
+	application should be passed to the larger computation, whether it's a "fall
+	off the left end of the list" result or it's a "I'm finished, possibly early"
+	result. The `larger_computation_handler` also then gets passed to the next
+	rightmost stage, where the head 4 is supplied to f, as the `abort_handler` to
+	use if that stage decides it has an early answer.
+
+	Finally, notice that we don't have the result of applying f to 4 etc given as
+	an argument to the application of f to 5 etc. Instead, we pass
+
+		(\result_of_fold_over_4321. f 5 result_of_fold_over_4321 one_handler another_handler)
+
+	*to* the application of f to 4 as its "continue" handler. The application of f
+	to 4 can decide whether this handler, or the other, "abort" handler, should be
+	given an argument and constitute its result.
+
+
+	I'll say once again: we're using temporally-loaded vocabulary throughout this,
+	but really all we're in a position to mean by that are claims about the result
+	of the complex expression semantically depending only on this, not on that. A
+	demon evaluator who custom-picked the evaluation order to make things maximally
+	bad for you could ensure that all the semantically unnecessary computations got
+	evaluated anyway. At this stage, we don't have any way to prevent that. Later,
+	we'll see ways to semantically guarantee one evaluation order rather than
+	another. Though even then the demonic evaluation-order-chooser could make it
+	take unnecessarily long to compute the semantically guaranteed result. Of
+	course, in any real computing environment you'll know you're dealing with a
+	fixed evaluation order and you'll be able to program efficiently around that.
+
+	In detail, then, here's what our v5 lists will look like:
+
+		let empty = \f z continue_handler abort_handler. continue_handler z  in
+		let make_list = \h t. \f z continue_handler abort_handler.
+			t f z (\sofar. f h sofar continue_handler abort_handler) abort_handler  in
+		let isempty = \lst larger_computation. lst
+				; here's our f
+				(\hd sofar continue_handler abort_handler. abort_handler false)
+				; here's our z
+				true
+				; here's the continue_handler for the leftmost application of f
+				larger_computation
+				; here's the abort_handler
+				larger_computation  in
+		let extract_head = \lst larger_computation. lst
+				; here's our f
+				(\hd sofar continue_handler abort_handler. continue_handler hd)
+				; here's our z
+				junk
+				; here's the continue_handler for the leftmost application of f
+				larger_computation
+				; here's the abort_handler
+				larger_computation  in
+		let extract_tail = ; left as exercise
+			;; for real efficiency, it'd be nice to fuse the apparatus developed
+			;; in these v5 lists with the ideas from the v4 lists, above
+			;; but that also is left as an exercise
+
+	These functions are used like this:
+
+		let my_list = make_list a (make_list b (make_list c empty) in
+		extract_head my_list larger_computation
+
+	If you just want to see `my_list`'s head, the use `I` as the
+	`larger_computation`.
+
+	What we've done here does take some work to follow. But it should be within
+	your reach. And once you have followed it, you'll be well on your way to
+	appreciating the full terrible power of continuations. (Silly [cultural
+	reference](http://www.newgrounds.com/portal/view/33440).)
+
+	Of course, like everything elegant and exciting in this seminar, [Oleg
+	discusses it in much more
+	detail](http://okmij.org/ftp/Streams.html#enumerator-stream).
+
+
+
+5.	Implementing (self-balancing) trees