Spark's Pensieve - Monday, October 24, 2005

This article is relevant in the context of

Other relevant articles include:

Iterators that listen (for Python, by Sidharth Kuruvila)

Implementing a generator in Ruby (by Sidharth Kuruvila)

I finally got down to ironing out the issues in the previous (rather hasty) entry about scheme iterators. I have code that is a little better tested.

To sell any idea, you have to demonstrate the value that believers in the idea get, before you discuss the cost. So here is the value –

Iterators support a style of programming where you separate producers of streams of data from consumers of these streams. For example you want to do a certain something on strings of text, irrespective of where the text comes from. In a more general case, iterators are a more powerful programming device, they can be thought of call-tree walkers, they can be thought of the notion of structured programming as applied to continuations. (Refer: Warming up to Iterators, Ruby: Containers, Blocks and Iterators, C#: Create Elegant Code with Anonymous Methods, Iterators, and Partial Classes)

The following is a demonstration of yield (similar to yield in Ruby, C# or Py) as a device to create iterators in scheme. There are some extensions to the idea, so the yield implementation here can do more things than the any of the other implementations can do (refer here for details). The implementation below is however useful in a functional context (its easy to see the use of yield in a imperative context). All of the code snippets below are functional in nature, the actual implementation of iterators need not be, but these internal details are abstracted away from you.

lambda-iter, yield, foreach

Iterators (functions that use yield) are defined using lambda-iter

(define even

(lambda-iter ()

(let loop ((i 0))

(printf "even recieved ~a ~n" (yield i))

(loop (+ i 2)))))

; Using foreach

(foreach (even)

(printf "it = ~a ~n" it) ; ‘it’ is the yielded value

(if (> it 20)

(break 0)) ;break out if we has enough

it) ;return the yielded value to yield

The even above is an produces an infinite stream of even numbers. The parameter to break is the return value of the foreach. ‘it’ is the value of the value that has been yielded. This common to many languages (Groovy, COmega etc). Everything else should be easy to understand.

coroutine, co-move-next, co-value, co-return, co-finished?, co-not-finished?

Iterators can be turned into first class entities as follows –

; Using coroutines explicitely

; Here the control flow mechanism is something we control

(let loop ((co (coroutine (even)))) ;create the corotuine object

(let ((co (co-move-next co))) ; start/advance the execution

(printf "Yielded ~a ~n" (co-value co)) ; print the yielded value

(loop (co-return (co-value co) co)))) ;return the yielded value

There, that’s said, you have all the devices that you need for a yield the magnificent implementation for scheme. There are more things in this implementation to make it useful for general purpose programming, but this much covers all the intellectual content. What follows is some essential documentation after which we have some of the extra forms.

Documentation

lambda-iter

(lambda-iter <params> <body>)

Same as lambda, except that you can do a yield in its body

yield

(yield <value>)

Yields a value to the caller

foreach

(foreach <iterator> <body>)

Takes an iterator and list of expressions, the expressions are invoked everytime the iterator yields. The value yielded is available as ‘it’. The expression can abort from the foreach by calling break. The parameter to break is the return value of the foreach. If the iterator returns, before break is called, the foreach returns the value of the iterator. Tha value of the last evaluated expression in the expression list is the return value into the iterator.

coroutine – wraps the iterators into a coroutine object

coroutine

(coroutine <iterator>)

Wraps the iterator into a first class object and returns it.

co-move-next

(co-move-next <coroutine>)

Executes the iterator in the coroutine, till it yields or till it returns. The new coroutine is returned.

co-value

(co-value <coroutine>)

Retrieves the current value of the coroutine. This might be a yielded value or a return value of the iterator. Functional programmers may want to use the analogy of car and cdr for co-value and co-move-next.

co-return

(co-return <value> <coroutine>)

Sets a return value into the coroutine and returns the new coroutine object. The return value is the value that will be avilavle as the return value of a yield call inside the iterators. Example (let ((a (yield 10)) … ) here the value of a will be the value that was set using a co-return in the coroutine object.

co-finished?, co-not-finished?

(co-finished? <coroutine>)

Returns a bool to indicate if the coroutine has returned. If it has yielded and can potentially do something meaningful for subsequent co-move-next calls, co-finished will return #f. co-not-finished is the complement.

Recursive yields

;; recursive yielding

; yields all combinations of true and false for n bits

(define states

(lambda-iter (n)

(if (eq? n 1)

(begin

(yield '(#f)) (yield '(#t)))

(foreach (states (- n 1))

(yield (cons #f it))

(yield (cons #t it))))))

(foreach (states 5)

(printf "state = ~a ~n" it))

Here is an example of recursive yielding. The states function returns all the values of a bit vector of size ‘n’ bits.

yield-all

yield all is a useful pattern sometimes when you recursively call iterators. Here is a tree walker that is implemented using yield-all and yield.

(define walk-tree

(lambda-iter (tree)

(cond

((null? tree) '())

((atom? tree)

(yield tree))

(else

(yield-all (walk-tree (car tree)))

(yield-all (walk-tree (cdr tree)))))))

(foreach (walk-tree '(1 2 3 (5 6 7) (4 5) 8))

(printf "value ~a~n" it))

There is an intuitive way to think about these sort of programs – each node is a tree yields itself if it is a a leaf (an atom). Else it asks each of its children to yield-all.

Solving the Same-Fringe problem

The same fringe problem is the problem of comparing two trees to see if they have the same leaf values, irrespective of the structure of the trees. One way of solving the same fringe problem is to use the walk-tree defined above and create two couroutines, to represent the two trees that are to be compared.

(define same-fringe

(lambda (t1 t2)

(let loop ((t1 (coroutine (walk-tree t1)))

(t2 (coroutine (walk-tree t2))))

(let ((t1 (co-move-next t1)) (t2 (co-move-next t2)))

(if (and (co-finished? t1) (co-finished? t2))

#t

(if (or (co-finished? t1) (co-finished? t2))

#f

(if (eq? (co-value t1) (co-value t2))

(loop t1 t2)

#f)))))))

The intuitive way of looking at this is that it created two coroutines and advances both of them. If they both finish, then the trees have same fringe. If only one of them have terminated then the trees are not equal with respect to fringe values. If neither of them have terminated and the values they yielded are the same, then we can loop and ask for the next value. As an aside, I find the code above to be far more readable that the equivalent in the Dorai Sitaram text.

coroutines, co-all-move-next, co-all-finished?, co-any-finished?

Here is a solution to the same fringe using some handy helper routines that help with dealing with collections of coroutines. These functions are usually useful only when all the coroutines are similar or related in some way.

(define same-fringe2

(lambda (t1 t2)

(let loop ((ts (coroutines (walk-tree t1) (walk-tree t2))))

(let ((ts (co-all-move-next ts)))

(cond

((co-all-finished? ts) #t)

((co-any-finished? ts) #f)

((eq? (co-value (car ts)) (co-value (cadr ts))) (loop ts))

(else #f))))))

Solving the repmin problem

The repmin problem requires that you trake a tree and construct a new tree where every leaf is replaced by the global minimum leaf value of the original tree. (This is the problem that started this saga off and was the one that none of the C#, Ruby, Py yields could handle)

The solution below can repmin trees not only binary trees, but trees of any arity. This shows of the flexibility of the some of the couroutine list comprehension functions that are available –

;a powerful repmin that works on trees with arbitrary numbers of leaves

(define repmin

(lambda-iter (tr)

(cond

((atom? tr) (yield tr))

((null? tr) '())

(else

(let* ((co-trs (co-all-move-next (map coroutine (map repmin tr))))

(co-vals (co-values co-trs)))

(co-values

(co-all-move-next

(co-all-return (yield (apply min co-vals)) co-trs))))))))

;Test

(define tree1 '(3 ((2)) (3 4) 1))

(printf "Repmin of ~a is ~a ~n" tree1 (foreach (repmin tree1) it))

Documenting the extra forms

yield-all

(yield-all <iterator>)

Equivalent of (foreach <iterator> (yield it))

coroutines

(coroutines <iterator>+)

Create a list of coroutines. Equivalent of (map coroutine <iterator list>)

co-all-finished?

co-none-finished?

co-any-finished?

(co-all-finished <coroutine list>)

co-values

(co-values <coroutine list>)

Returns a list of values, which are the value sof each of the coroutines

co-all-move-next

(co-all-move-next <coroutine list>)

Moves all the coroutines in the list to the next value and returns the new list of coroutines.

co-all-return

(co-all-return <value> <coroutine list>)

Applies a return value to all of the coroutines and returns the new list of coroutines.

co-each-return

(co-each-return <values list> <coroutine list>)

Applies a return value from the values list to each of the coroutines and returns the new list of coroutines.

Implementation

Here is the implementation of coroutine, yield and all the support stuff…

;Roshan James (Mon 10/24/2005)

;call/cc based implementation of Yield the Magnificient for Scheme

;

;Yield the Magnificient:

;http://www.thinkingms.com/pensieve/default,date,2005-10-11.aspx

;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;

;A coroutine is represented by a list of 3 values. The first of these is a

;proc(1), the second is a value(2), the third is a bool(3). According to

;different stages in the lifetime of a coroutine, these have different values.

;

; Values of proc(1)

;1) When a corotuine is created the proc is the 'first lambda'

;2) When the iterator is running, the proc is the continuation of the iterator

;3) When the iterator has returned, the proc is the null-proc.

;

;Values of value(2)

;1) When the coroutine is created, it is simply #t

;2) When the iterator is running, it is the current yielded value

;3) When the iterator has returned, it is the final return value

;

;Values of bool(3)

; The bool of #f after the iterator has returned. Until then the bool is #t.

;

;Coroutines can be sent return values, by replacing value(2) in the list

;before calling co-move-next. Once a coroutine has terminated, co-move-next can be

;called an infinite number of times without having any effect. The return

;value is preserved (all these calls are sent to null-proc).

(define coroutine

(lambda (prod)

(list (lambda (ret) ;first lambda

(letrec ((esc (car ret))

(null-proc (lambda (x)

(cons null-proc (cdr x)))))

(let ((stopped (list null-proc

(prod (lambda (it)

(let ((res (call-with-current-continuation

(lambda (k)

(esc (list k it #t)))))) ; iterator k

(set! esc (car res)) ;Evil!

(cadr res))))

#f)))

(esc stopped))))

#t #t)))

(define co-move-next

(lambda (co)

(call-with-current-continuation

(lambda (esc)

((car co) (list esc (cadr co) (caddr co)))))))

;There is no intellectual content past this point, the rest of the code is required

;to provide abstractions that I thought are are useful from my experince with using

;yield.

(define co-value

(lambda (co) (cadr co)))

(define co-finished?

(lambda (co) (not (caddr co))))

(define co-not-finished?

(lambda (co) (caddr co)))

(define co-return

(lambda (val co) (list (car co) val (caddr co))))

;Some useful macros

;create a producer that has a implicit curried yield

(define-syntax lambda-iter

(lambda (f)

(syntax-case f ()

[(_ (x* ...) body body* ...)

(with-syntax ([yield-syntax (datum->syntax-object (syntax _) 'yield)])

(syntax

(lambda (x* ...)

(lambda (yield-syntax)

body

body* ...))))])))

;can be called in an iterator to yield all the values yielded

;by an iterator it is calling

(define-syntax yield-all

(lambda (f)

(syntax-case f ()

[(_ iter)

(with-syntax ([yield-syntax (datum->syntax-object (syntax _) 'yield)])

(syntax

(iter (lambda (it) (yield-syntax it)))))])))

;a foreach that mostly useful only in an imperative context

(define-syntax foreach

(lambda (f)

(syntax-case f ()

[(_ iter body* ...)

(with-syntax ([it-syntax (datum->syntax-object (syntax _) 'it)]

[break-syntax (datum->syntax-object (syntax _) 'break)])

(syntax

(call-with-current-continuation

(lambda (break-syntax)

(break-syntax (iter

(lambda (it-syntax)

body* ...)))))))])))

;reduce

(define reduce

(lambda (proc ls)

(cond

((null? (cddr ls)) (proc (car ls) (cadr ls)))

(else

(proc (car ls) (reduce proc (cdr ls)))))))

;useful functions for dealing with lists of iterators

(define coroutines

(lambda ls

(map coroutine ls)))

(define co-all-finished?

(lambda (ls)

(reduce (lambda (a b) (and a b))

(map (lambda (iter) (co-finished? iter))

ls))))

(define co-any-finished?

(lambda (ls)

(reduce (lambda (a b) (or a b))

(map (lambda (iter) (co-finished? iter))

ls))))

(define co-none-finished?

(lambda (ls)

(reduce (lambda (a b) (and a b))

(map (lambda (iter) (co-not-finished? iter))

ls))))

(define co-values

(lambda (ls)

(map co-value ls)))

(define co-all-move-next

(lambda (ls)

(map co-move-next ls)))

(define co-all-return

(lambda (ret ls)

(map (lambda (iter) (co-return ret iter)) ls)))

Here are the files for download.

What is the value of all of this?

The value of all of this would be to look at the above as a general way of implementing yield in languages where the approach is to pass a closure from the caller to the callee. Ruby is another language in this category and I believe the Generator class was an attempt to solve this problem.

The real value in all of this is in setting a base for further exploration of the style of programming that yield lends itself to. Is it sufficiently expressive to express all implementation of certain classes of problems? If so, then yield maybe useful as a primitive building block for large classes of control structures in programming languages. If not, all of this was fun anyway. :)

Download

Languages | Programming

Monday, October 24, 2005 5:40:28 PM (Eastern Standard Time, UTC-05:00)

Comments [5] |

Metaphors/Dil-li

Anand

Ethos

Sunday, October 16, 2005 12:44:51 PM (Eastern Standard Time, UTC-05:00)

Comments [0] |

Yielding to Magnificence

Python

Firstly, halfway across the planet, Sid created what could be for most part Yield the Magnificent for Python. (I am not fully convinced that he hasn’t lost property 6, but he has fixed 3 and 5.) But that should not come as much of a surprise to me because I have met few Py programmers like Sid :) Here is Sid’s Iterators that Listen

Scheme

Here is something that I have for scheme. It needs to have details ironed out. But effectively this does a coroutining “transform” of the caller. This puts it in the same category of ‘solution’ as ruby’s ‘generator’ class. This is also the operational equivalent of what py and c# have done. In the scheme world resume state is maintained by a continuation. In the Py or C# world, state is maintained by creating an object. For the scheme solution below, the basic ideas came from the brain storming session with William Byrd and Matt Ellis on this Friday.

Here is the scheme code:

(define coroutine

(lambda (prod)

(list (lambda (ret)

(let ((esc (car ret)))

(list (lambda (x) x)

(prod (lambda (it)

(let ((res (call-with-current-continuation

(lambda (k)

(esc (list k it #t))))))

(set! esc (car res)) ;Evil!

(cadr res))))

#f)))

#t #t)))

(define move-next

(lambda (co)

(call-with-current-continuation

(lambda (esc)

((car co) (list esc (cadr co) (caddr co)))))))

(define valueof?

(lambda (co) (cadr co)))

(define finished?

(lambda (co) (caddr co)))

(define set-return

(lambda (co val) (list (car co) val (caddr co))))

Writing a Producer / Generator / Iterator

One this is in place one can write an iterator that looks like so –

(define even

(lambda ()

(lambda (yield)

(let loop ((i 0))

(display (yield i))(newline)

(loop (+ i 2))))))

It is conceivable that we can have a macro to hide the currying of the inner lambda (yield). However it is easy to see that One can write producers that assume that they have a yield keyword handy.

Writing the consumer

To use the use the iterator as a first class object, you simply do –

(let loop ((co (coroutine (even))))

(let ((co (move-next co)))

(display "Yielded ")(display (valueof? co))(newline)

(loop co)))

Consumer code like the above is free from any forced invocation by the producer and hence does not need a ‘break’.

Functional programming

The co objects are first class and can be passed around – they are not bound to any syntactic structure. Hence having a yield facility is now meaningful in a functional context (which was one of Will Byrd’s concerns). The implementation of the coroutine is itself is not functional.

Lockstep iteration / apply-iterator / Iterator composition

It is conceivable that when you have a one one producer you might want a syntactic structure that also gives you a break.

However I don’t think its meaningful to create a general purpose apply-iterator. The reason is simple: Iterators are blocks of code that can yield a arbitrary number of values. If you decide to lockstep with each iterator producing a different number of yields, when should the composition of these iterators stop? There would be problems that need all of them can halt when the first one halts. There would be others where you might want the last iterator to stop before the the whole structure stops. So at the least you need at least ‘and’ and ‘or’ semantics between the finished cases. There might be algorithms where you need other behaviors.

Instead of defining these syntactic structures and defining rules for composition it is sufficient to convert individual iterators into coroutines. You can see that it would be very handy to have some nice list comprehensions to make it easy to use several coroutines in combination. As a matter of fact, all sorts of useful macros could be devised. However, there maybe no useful apply-iterator operator.

Now who can fix my imperative favorites, C# and Ruby?

Languages | Programming

Saturday, October 15, 2005 9:39:12 PM (Eastern Standard Time, UTC-05:00)

Comments [4] |

Judas to the Temple of Lambda

Last night I was writing some for OS161 – I was implementing a fork(), execv(), getpid(), waitpid() and exit() for the OS161 kernel. I was using Visual Studio Express VC++ edition beta2 to write the code and I had a little ruby script to upload changed file to my linux (gasp!) box and a little script there that would build the kernel whenever the files changed. That way I get to develop code on an OS that has a notion of a unified clipboard and such pleasantries and get to build it wherever the tools are available. I also got a minimal shell like first process done.

Don’t get me wrong when I say this, but I sometimes like to think of myself as a fairly decent imperative programmer – I would be comparably good to many people you might meet. Ever since I came to college functional programming has been rewiring my brain. And its beginning to hurt. And I am enjoying it. And sometimes you need a break.

Hence writing missing pieces in a simplistic os kernel is a nice break. And I am going “Ooh! Look I have variables! Ooh! Look I can reassign the value of this thing. Look, I have loops”. And that’s a nice world to be in, if you can think in terms of state well – for those of you imperative programmers don’t know what that is, it means that things have changable values (like x=5 and x ++;) – and those of you who don’t realize you are imperative programmers, here is a simple test: if you are not a Haskell (and similar) programmer Or Scheme programmer (without set!) Or mathematician Or someone who goes from day to day without anything in the world affecting you, you are a imperative programmer of some device.

So I was enjoying being imperative for a while and then when I had it all going halfway into the night – I had multiple processes forking and execing and waitpiding and exiting – the whole crashes. And then it crashed again. And this was crazy, because all the of the pieces were things I had tested separately and yet they crashed when they came together. Somewhere in the back of my head there was this little elephant called lambda laughing on the floor ignoring his cons-kit for a bit. But wait a minute, I thought all this functional programming was making me a better programmer – I thought I could think more clearly about composition.

After about 2hours of meditation and atleast one or two sets of forays into the debugger as a last recourse, I realized what the problem was that I was not writing things back onto the user space stack in the correct alignment in some cases – and the this was some dword alignment requirement of this machine that was not mentioned anywhere. Lambda and the Turing tape looked down, looking a little sorry. I was in a bad mood by the end of it and that wasn’t fair – that was my little imperative break.

All of this, gets me to some of the conversations with some of my professors here. Dan Friedman is one of the kindest gentlest people you can talk to – and pretty much every other sentence some brain mutilating idea, said in the kindest subtlest way possible. So it happened that I needed to prove that something is not possible (it is related to the hypothetical apply-iterator operator I speak of here). Fifiteen minutes after the conversation I am thinking about higher order programming with continuations and my brain is hurting. (do you know what that means? If you don’t you need to go though the experience of hitting upon an idea that changes the way you look at the world. Changes the way you look at the world does not mean that the next time you eat a burger you look at it slightly more from the left, it is a little more encompassing an idea.)

An idea isn’t responsible for the people who believe in it.

Programming languages are devices to express thought. The fact that you can also create software using them are only secondary to this larger idea. Languages carry ideas of meaning and operation and you can compose these things together to create larger meanings and wider operations, or compose them to narrow down their scope. If you are a starting C programmer or an accomplished C# or Java programmer, it maybe hard to see things this way – but that is ok, you don’t always have to know the full import of what you could be doing. (I will write about Haskell and the wizard called Prof Amr Sabry some other time.)

One of the hardest things or like Prof Friedman says it is probably the simplest of all things is the idea of a continuation. It is an idea so simple that it drives you crazy trying to understand it. Imagine that if you did something, anything, it has rippling effects across the rest of all time – now imagine that you can take this ‘rest of all time’ and assign it to a variable and pass it around through all the operations you do, such that at some time you can go back to that rest of the world. That is a continuation. That as a programming device is good way to inflict some brain damage if you try to internalize it.

That’s about when I thought I should quit. That I probably should not go functional. All of this was too hard – you start out with something because you feel that there is some beauty and some truth in it. And when that fails you, maybe its time to betray you way of thinking – maybe its time to quit. By this point, you realize, that I might be quiet crazy, and that it might be rubbing off on you since you are still reading this. Betray the temple of Lambda?

That’s when Judas’s song from Jesus Christ Super Star (which I have been listening to a lot these days) plays in the back of my mind, when he does to Caiphus to betray Christ -

Now if I help you, it matters that you see

These sordid kinda things are coming hard to me.

It's taken me some time to work out what to do

I weighed the whole thing out before I came to you.

I have no thought at all about my own reward.

I really didn't come here of my own accord.

Just don't say I'm ... damned for all time.

I came because I had to; I'm the one who saw.

Jesus can't control it like he did before.

And furthermore I know that Jesus thinks so too.

Jesus wouldn't mind that I was here with you.

I have no thought at all about my own reward.

I really didn't come here of my own accord.

Just don't say I'm ... damned for all time

- Damned for All time, Judas’s Song, JCSS.

And then something snapped back in place and I was at it again. Why have such a device as continuations? Why bother? Well we understand little of continuations in my opinion. They are a thinking tool for the future. How can something so mind bogglingly hard be useful?

A long time back I remember seeing a beginner book about BASIC programming. That book had an example of the quicksort algorithm in basic written using gotos. It was a only a few lines. I spent a whole evening trying to understand what that was doing. And I didn’t succeed. I could execute the statements in my mind and see how they work, but I could see how such a beast could be created. I couldn’t see the way you would have to think to create something like that. Several years later I saw copper bars by Tylisha C Anderson and it was the same death by gotos. I could not understand it.

Many years ago they got together and killed off gotos and created a new-kid-on-the-block called structured programming. They took gotos and created a set of patterns that are sufficiently expressive to do anything that you could do using gotos. And then they killed o