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 [6] |

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 off goto. The offspring forms the basis of almost all imperative programming today.

The real value of something powerful that we cannot tame yet is in what you can derive out of it. That’s when you say, in the conventional sense, that something is sufficiently mature – when people who don’t understand the first thing about it can use it to solve their programs (that’s the sense in which I sometimes say that windows is more mature than linux…). I think I should stop now. As you can see, college has been fun so far.

What then to do about this Jesus-mania?

Now how to we deal with a carpenter king?

Where do we start with a man who is bigger

Than John was when John did his baptism thing?

- This Jesus must die, Song of the Priests, JCSS

I dreamed I met a Galilean;

A most amazing man.

He had that look you very rarely find:

The haunting, hunted kind.

I asked him to say what had happened,

How it all began.

I asked again, he never said a word.

As if he hadn't heard.

- Pilate’s Dream, JCSS

Ethos | Languages | Mish Mash

Wednesday, October 12, 2005 9:37:40 PM (Eastern Standard Time, UTC-05:00)

Comments [0] |

Search for Yield the Magnificent

After a long time, one missing piece in the yield (iterator) puzzle fell in place in my head. It should have been obvious because it had been staring at me in the face for a while now. I am not sure, but it seems to me at this moment, that some of this might be of lasting importance beyond the scope of this blog entry.

Time warp 3 or 4 years back to when Sid and I were discussing ruby iterators and python list comprehensions. Sid had this notion that there was something missing in the Python implementation that made ruby iterators more powerful. We however could not place it at that time and we let it be. And we missed it for years after that. I am going to make some claims that some languages can and cant do certain things – I might be wrong and I hope that I am – if I am do show me how and maybe we can take this forward.

The most powerful yield (iterator) construct that I can think of, needs all of these –

1) the parent function that takes arguments

2) the parent function yields values

3) the parent function can return a one or more values finally and terminate

4) the parameter block of the yield should be able to ‘break’

5) the yield should be able return values into the iterator

6) it should possible to iterate two or more iterators in an interleaved manner.

1 and 2 are obvious. Almost all implementations of yield do this.

3 means that there is a notion of the function returning a value as the exit case of the function (such that the function instance terminates and that it will not produce any more values).

4 means that you should be able to do this

x.each {|y| break }

5 means that you should be able to do this

def foo

n = yield 5

puts n

end

6 means that you should be able to do this

a = foo1()

b = foo2()

puts a.next() + b.next()

puts b.next() + a.next()

Now, here is the search for yield the magnificent – I don’t a language that gives me a yield that can do all of the above and I am upset.

C# and Python rely on transformation of iterator (the callee) into an object that models the the state machine of iterator code. They use the objects state to maintain the environment for their closure (their state machine transformed iterator function). Read more about C# 2.0 iterator implementation here. The ruby way as I understand is that the callers block is passed to the callee as a closure. Scheme does not intrinsically have a yield, but you make an equivalent by passing a closure to a callee function. I am aware that there are other languages that implement the yield – Comega and Groovy, Icon and CLU – I don’t much about these (except that I believe that Cw is similar to C# in this regard), and so I wont discuss them here. Ever since ruby popularized the construct, it has found its way into many languages.

All of these support 1 and 2 above.

C# and Python support 4 and 6. They don’t support returning values from the function and do not support sending values into the iterator. This means that you cannot write code similar to the powerful inject and other similar ‘reduce’ like constructs. Here is what the inject (courtesy of smalltalk looks like)

class Array

def inject n

each { |v| n = yield n, v }

return n

end

def sum ls

v = ls.inject(0){|n, v| n + v }

return v

end

Inject is very powerful as it enables creating a large number of reduce like behavior. Inject itself is only one example of many things you can do if you can control the execution of iterator by passing it values from its consumer. The argument in favor of the return is weaker, but it is sufficient to say that it it important to separate a final value, from that of the last yielded value.

(I am not sure that Py cannot return a final value. If I am correct it terminates iteration of next() calls by throwing an exception. It don’t know if it captures a return value in the function object)

Scheme iterators, the simplistic approach that I have in mind is

(define iterator

(lambda (x cls)

(cls (+ 1 x)) ; yield 1

(cls (+ 2 x)))) ; yield 2

(define caller

(lambda ()

(iterator 10

(lambda (n) ; this lambda is in the lexical scope of caller

(display n)))))

Should be equivalent to

def iterator x

yield x + 1

yield x + 2

end

def caller

iterator {|n|

puts n

}

end

The limitation in scheme is that you cannot do a ‘break’ the block of the caller. Atleast there is no easy way to do this without grabbing a continuation at the point of the call of the call to ‘iterator’, and then invoking the abortive continuation in the closure argument cls.

If if it given that the abortive continuation is a natural way to do this, it is not obvious about how two iterators can created to lockstep iterate into a single block of code. I will discuss this further below.

So scheme can do 1, 2, 3 and 5. It can’t ‘break’ without continuations and cannot interleave or lockstep iteration in any obvious way.

Ruby, by far comes out with a lot of the above – the only thing it can’t do is 6, that you cant interleave iterations. The fact that you cannot interleave or lockstep iterations means that there whole classes of problems that you cannot solve. The simple case is the classical example of co-routines or continuations, the problem of comparing leaves of two trees. To compare the leaves of two trees the standard solution is write a routine that traverses the tree recursively and yields leaf values out of the recursive structure. You can then write a simple compare routine that initializes two instances of this procedure with two trees you want to compare, and then it merely compares the yielded values. This is the solution in Comega –

//the int* represents a stream of 0 or more ints. It is not a int pointer.

static int* getleaves(node n)

{

if(n != null)

{

if(n.value != null)

yield return n.value;

else

{

if( n.left != null) yield return getleaves( n.left );

if( n.right != null) yield return getleaves( n.right );

}

static bool samefringe(node tree1, node tree2)

{

en1 = getleaves(tree1).GetEnumerator();

en2 = getleaves(tree2).GetEnumerator();

t1 = en1.MoveNext();

t2 = en2.MoveNext();

//this is the lockstep iteration

for(; t1 && t2; t1 = en1.MoveNext(), t2 = en2.MoveNext())

{

if( en1.Current != en2.Current )

return false;

}

return !t1 && !t2;

}

As you can see, the class of problems that fall into the above category is fairly large and its annoying that they cant be solved in ruby.

Note: Ruby provides something called a generator to solve the problem of lockstep iteration. I like the language they describe this in –

Generator converts an internal iterator (i.e. an Enumerable object) to an external iterator.

Note that it is not very fast since it is implemented using continuations, which are currently slow.

The first problem is that it grabs continuations over something that already manages state. Lets assume that that’s transparent to us and is a non-issue, there is a larger problem that generator created iterators violate some of the other requirements, specifically 5: how you can send values into the iterator.

g = Generator.new { |g|

n = "hello"

loop {

n = g.yield( n )

puts n

break if n == nil

}

g.each {|n|

puts n

n + "."

}

This code does not work as expected (does not generate hellohello.hello..hello…). If there is something amiss above that you can point out, let me know.

All of this brings us closer to the conclusion – you will notice that there are two approaches to the implementation of iterators – one where the callee (the iterator) is closure converted (like C#, Python…) and the approach to grab a closure in the caller with a light-weight or heavy-weight abortive construct (as in Ruby and Scheme). Here is a pleasant discussion on iteration styles.

Finding Yield the Magnificent

Fixing the C# and Py approach requires two potentially simple changes. Make the C# MoveNext() or the Py next() functions take an argument. This is not strictly semantically correct, because this means that if MoveNext or next are used to start the computation then the first value passed is ‘hanging in space’. This fixes requirement 5. To fix 3 it is enough to create a new member in the closure object that retains the return value.

While this might be all very well in Py, its probably not as easy in C# or other strongly typed systems since you hit a syntactic limitation about where you express the return type of the function and the types of the value that yield returns to the function.

Fixing lockstep in a blocks/internal iterators/scheme-ruby-style approach can be done if it is possible to create a combinator that takes multiple iterators and a block that takes multiple values and does an iterator equivalent of scheme’s ‘apply’. I don’t if such an apply-iterator operator exists. Maybe this was the difficulty they weren’t built into ruby in the first place. I don’t have a solution to interleaved iteration when it’s the caller that is closure converted – there is probably no valid general purpose transformation of this sort possible.

There, I am glad all of this is said finally. I knew it all at the back of my mind as a shapeless dark area in my understanding of yield from which I could derive working knowledge, but nothing quantified. What started off all of this is that I finally needed a yield that did all of the above – that seemed to be the only natural way to express a particular algorithm. Now that all of this is said its quantified, weather it is all right or wrong. I will be happy to see what ideas you can contribute to the above discussion. I would also like work of the apply-iterator operator or if such a beast exists and you know about it, let me know.

I will get down to proof-reading this soon.

Languages | Programming

Monday, October 10, 2005 11:44:25 PM (Eastern Standard Time, UTC-05:00)

Comments [13] |

Mini Kanren

Mini Kanren programming gives you a few basic constructs and you are on your way doing logic programming.

It has a run construct which looks like this

(run* (q) <goals>)

And this means that the it generates all possible values of the variable q, that can be satisfied by all goals that are part of the run.

The simples goal constructor is that of unification and is denoted as a ==. The unifier tries to bind its values together. If both values are compatible the unifications succeeds.

(== 5 5) - this unification succeeds

(== x 10) – this succeeds and binds x to 10

(if there was no binding for x before)

(== a b) – this binds a to b and succeeds

(== a 10) – this binds a to 10 and succeeds, hence b is also 10

(== b 20) – this fails since the b cannot be bound to 20 in this context

So if you say

(run* (q) (== q 10))

You get 10 as the result.

The conde forms the equivalent of an ‘or’ relationship between sets of goals. It returns all the possible substitutions that are got by evaluating each of its goals sets.

(run* (q)

(conde

((== q 10))

((== q 20))

((== q 5) (== q 15))))

This returns values 10 and 20. The third relation under conde fails because q cant be bound to 15 after it is already bound to 5.

The last construct is fresh. The important thing about mk over prolog is that it has a notion of lexical scope for its logical variables. ‘run’ introduces the variable whose value it will return on evaluating the its goals. Fresh introduces or defines one or more new logical variables which can then be used in relations in the scope of the fresh.

(run* (q)

(fresh (a)

(== a q)

(== a 10)))

This returns 10.

There! That’s all you need to know about mini-kanren.

Embed this much into scheme and you have a full (I think) logic system. Take a closer look at more Mk here.

The real reason I wrote all this is that I had some potentially interesting random thoughts about the logic system. But I could not say it without establishing some context first.

Now, if you are using the Cw version here is the simple conversion Mk.run is run*, Mk.conde is conde. == is Mk.eq. I don’t need a fresh because I use the Cw type system and lexical scoping to create logic variables as instances of class ‘Var’. Get the Cw version is here.

Saturday, October 08, 2005 11:36:23 PM (Eastern Standard Time, UTC-05:00)

Comments [0] |

The Mini Kanren Logic System for the CLR

This is an implementation of the Mini Kanren logic system for the CLR. This was done last night, so you can take it with a pinch of salt. It does not cover the full set of constructs that original MK system covers. Here is a overly simplified introduction to miniknaren.

This implementation is done in Cw, the experimental language from MSR. You will need the COmega compiler if you wish to compile the source.

This implementation covers the basic ‘run’, ‘all’ and ‘conde’ constructs. You do not need a ‘fresh’ because I use the Cw type system and scoping to give me the equivalent of fresh. MiniKanren is implemented as an embedded language in scheme – so you get to do relational programming and then drop into scheme’s functional host language as need be. Since this implementation runs over Cw, this extends and hence you get a combination of a declarative logic programming system on top of everything that is Cw.

I am considering adding some more constructs and maybe a relational arithmetic system. I am also considering extending Cw syntax using an external precompiler so that it becomes as little more natural to write relational programs. The present ‘syntactic beauty’ is well a little lacking..

All that said, here are the sources from last night.

q = new Var();

a = new Var();

b = new Var();

c = new Var();

res = Mk.run( q,

Mk.eq( q, new object[]{ a, b}),

Mk.eq( a, c ),

Mk.eq( c, 10),

Mk.conde(

new goal[]{ Mk.eq(b, 5) },

new goal[]{ Mk.eq(b, 10) },

new goal[]{ Mk.eq(b, 20) },

new goal[]{ Mk.eq(b, 25) },

new goal[]{ Mk.eq(a, 50) }

));

//res is the potentially infinite lazy evaluated set

r = res.{ return Var.ToString( it ); };

r.{ Console.WriteLine( it ); };

A logic programming system is a great way to implement solutions to several kinds of problems like dependency analysis, all searching any relational space (ex: A Type Discipline for Authorization Policies)

Disclaimer:

(I am not responsible for your divergences).

(I am also not responsible for any halting problems with your compilation process).

(The full credit of MK goes to its original authors. This implementation is merely a transliteration with a certain imperative flavor added).

Languages | Programming

Friday, October 07, 2005 1:45:47 PM (Eastern Standard Time, UTC-05:00)

Comments [4] |

Of Muggles and Magicians

Its been a little over a month at IU and the experience has been overwhelming. As has been since when I can remember I have gotten myself involved in more things than I can handle – which is another way of saying that things have been fun, atleast when I am able to keep up with them.

Like Hogwarts, the university is dotted with signs of greatness from antiquity. And every once in a while you come across some one who can do things to your mundane set of ideas that is no lesser than of Gandalf.

Pictures from around the Indiana University Campus

I have been hit by some hard ideas and fortunately I had been preparing my mind for a while to handle these – had I not and had I tried to absorb them at the same rate now, I might have been in for some hardship.

Lindley Hall, Computer Science Dept

I have formally enrolled for Operating Systems by Andrew Lumsdaine, Programming Languages by Dan Friedman and Quantum Programming by Amr Sabry.

OS is primarily to scratch an old itch – because of that incomplete OS I left behind in college – this course gets to complete is half done os161 kernel – so there is a lots of traditional C programming there.

Programming Languages essentially covers the whole of ‘Essentials of Programming Languages’ with Prof Friedman saying things like ‘I will let you know when you need to think’, on day one. Most of us are thinking pretty hard already. This year the course also covers the new logic system he worked on with Will Byrd and Oleg Kiselyov called Mini-Kanren (source-forge is not as updated as it should be). This also forms the basis for his third ‘little’ book – The Reasoned Schemer.

Quantum Programming is … well a course about magic – it’s a huge thinking exercise about creating a model of computation for possible ‘quantum machines’. I will not venture to say much more here, except drop a link to an introductory paper.

OS and PL are supposed to be among the hardest courses in the CS department, many people don’t advice taking them both together. To put things in perspective, I am finding QP the hardest simply because of the breadth of the computer science from which the ideas in QP are coming from. The present state of QP is a little like the state of classical computing in the times of Church and Turing.

Kirkwood Hall and the walkway by Lindley

That aside, I am looking into some of these things as of right now (this is not a complete list)
-        join calculus, pi calculus and other process calculi
-        squiggol (Bird and Meertens formalism)
-        quantum circuits
-        grokking functional programming Haskell-style
-        logic programming

All of this aside, Bloomington is a beautiful place - small university town with lots of charm and a pleasant weather (for now). I am told that this place has bad winters with lots of snow.

I have a small single bedroom apartment that is a ~12 min walk from the university.

The red square is Lindley Hall, the main CS department building and the green square is my apartment.
(Courtesy: Google Earth)

And among other things, I have a new weapon – its called Qubit. Qubit is a Dell Inspiron 9300, UXGA 17” monitor, with 1Gb ram, 256 mb Nvidia Geforce 6800 graphics card and a dual layer Dvd writer.

Ethos | Mish Mash

Wednesday, October 05, 2005 10:34:17 PM (Eastern Standard Time, UTC-05:00)

Comments [9] |