Work at MSRC has been moving slowly, though I have been busy.

 

Parallel GC for Haskell

Not much to say on the Haskell parallel GC front except that I am yet to actually start writing any code. I have been trying to understand the existing code base and it has been a little over whelming. This is certainly not one of the best code bases that I have seen. Actually quiet far from it. There are functions of several hundred lines in length. The main GC function itself is 800+ lines long. I have been told that several people have got their PhDs of that GC.c file. I was expecting a pure functional language to contain a couple of core object types and everything else to be built around them. Far from it, there are 70+ types of objects in the system – they have special cased almost everything they can think of for efficiency sakes. Being a pure lazy language these things matter I guess.

 

That aside the source is littered with lots of interesting ideas. The problem with something so interconnected is that its hard to build incrementally on this. So I am little stuck. The GC has a copy collector and a mark compact collector in the same code base – they share a large amount of code. For a long time this confused me. The system switches from a copy collector to a mark compact collector depending upon memory usage of every step of every GC. The number of generations is runtime configurable. The number of steps per generation is runtime configurable. It’s a crazy, interesting system.

 

I have been making some notes over here, which I hope to continue updating over the period of my internship –

http://cvs.haskell.org/trac/ghc/wiki/GarbageCollectorNotes

 

Papers - Quantum

That aside, I helped complete – or rather didn’t help complete – a paper on Quantum Computing since I landed in Cambridge. I actually didn’t do much for that paper. I had some interesting ideas, but they remained undeveloped enough to not go into the final paper (though we initially thought it would). So well, in some sense my first paper is not really my first paper. :)

 

Papers - Yield

I finished my second paper since landing at Cambridge this past weekend. The paper is about yield, (yes, finally!). It is coauthored with Simon Peyton Jones and Amr Sabry, though most of the actual writing was done by me. So in many senses this paper will not be of comparable caliber to most Amr Sabry or Simon Peyton Jones papers. Writing this paper was quiet an experience – as it is, it was my first real paper. Usually, I am told, people don’t write their first papers completely themselves, they write a section or so. Secondly I had the names of two very respected computer scientists on this and I was afraid of writing accidental stupidity. They however did give me lots of comments over email. And at the end of it I think I have come out braver, a tab bit less afraid of writing papers.

 

The paper has been submitted to the Haskell Workshop 2006. Haskell is probably the most difficult language to suggest a new control flow operator. Being the pinnacle of pure functional programming, with monads and lazy evaluation it is a very very hard language to make a value proposition to in terms of adding control flow operators. All the same, I think we may have one or two interesting arguments in favor of yield.

 

Breadth First Renumbering

As an example of control flow based on lazy evaluation consider this problem: You are given a binary and asked to renumber the nodes in breadth first order, thus creating a new tree of the same structure but with changed node values.

 

 to

 

Think about it. See if you can do this by only one traversal of the tree and use constant space etc. Basically the best solution you can think up.

 

In Haskell, lazy evaluation is used as a control flow operation. But one that is an implicit control flow operation – in the sense that the programmer doesn’t have to specify the order of evaluation the system will figure it out, driven by need.

 

Here is the lazy Haskell solution -

 

data T a = B a (T a) (T a) | L a

       deriving Show

 

bfn :: ([Int], T a) -> ([Int], T Int)

bfn (k : ks, L a) = (k + 1 : ks, L k)

bfn (k : ks, B x a b) = (k+1 : ks'', B k a' b')

    where (ks', a') = bfn (ks, a)

          (ks'', b') = bfn (ks', b)

 

bfnum :: T a -> T Int

bfnum t = t'

    where (ks, t') = bfn (1 : ks, t)

 

It is just mind boggling that something like this can work – and work so perfectly. If you know how to read Haskell and you haven’t seen this solution before, get ready for a mild surprise. :) The implementation is adapted from the appendix of Chris Okasaki’s  paper –

http://portal.acm.org/citation.cfm?id=351253&dl=ACM&coll=ACM

 

Even if you don’t understand Haskell, try to solve this in your pet language and see what you come up with.

 

Haskell

Since I am in a mood for writing a bit – here is a little bit about Haskell. A tiny tiny intro. Haskell is a pure functional language. If you don’t know what that means, there is good chance that you haven’t seen one before. Also Haskell is one of the few languages that are lazy evaluated. Values are computed only on a need basis – hence one gets to write all sorts of crazy circular dependencies between function parameters and their results – if one is careful. Also it is strongly typed – Haskell is a laboratory for stuffy of type systems, if nothing else.

 

Lets do some examples. Immediately following the example, I write what it means.

 

n = 5

n is a function that takes no parameters and returns the value 5.

 

 

f n = n+1

f is a function that takes one parameter, namely n and return n+1. Hence if one writes (f 1) it is the equivalent of calling f with the parameter 1 and will return 2.

 

If you write code like the above, it will work. But usually people write the types of everything they write. If you miss out the types, Haskell has a type inferencer which will automatically figure out the types (and might occasionally complain if there are ambiguities).

 

So here is the definition of the function f with its type signature.

 

f :: Int -> Int

f n = n+1

So the type of f is written by putting two colons after f and is “from Int to Int”. In other words the function f takes an Int and returns an Int.

 

Here is the type of the function even, a function that checks if a number is even.

even :: Int -> Bool

It takes an Int and returns a Bool.

 

So what is the type of the function n?

n :: Int

n = 5

Simple? The type of n is simply Int.

 

Here is a function g that takes two parameters, namely x and y and returns their sum.

g :: Int -> Int -> Int

g x y = x+y

The type says that g takes an Int and yet another Int and returns an Int. The value of (g 5 10) is 15.

 

The interesting this is that in haskell, unlike in many other languages, the expression (g 5)  by itself has a meaning.

g5 :: Int -> Int

g5 = g 5

(g 5)  is a function that takes an Int  and returns an Int. Here I assigned the name g5 to be (g 5) hence is I say (g5 20) the result will be 25. The general idea behind applying only some of the parameters of a function thereby result in a new function that awaits the remaining argument is called “currying” – named after Haskell B Curry.

 

Does this interest you? If so you should consider reading up about Haskell a bit. Maybe I will drop a few simpler examples of lazy evaluation based niceties sometime.

 

Idea Foundry

 

I was trying to explain to someone the other day about what I am doing in computers. I didn’t have a concrete way to explain previously but these days this seems to be a good way -

 

There are people who need to solve some problem and they use a piece of software to solve it for them. For example someone would wish to buy a flight ticket and they buy it through a website. They are usually called users or end-users. We are all end users. Then there are people who write the software they used to solve their problem. For example the people who wrote the website, all of the complex interactions between reserving your ticket and handling the monetary aspects are handled by these folk. They are the people who developed your software. I used to once do that, or something very similar. Then if you think about it, there is yet another layer - the people who wrote the tools using which the developers of the website wrote their website. These people write tools so that other write tools which you as end users use. The chain of people who write tools which are used to build other tools is a pretty long chain. Its like any services industry – one service is consumed by another service and so – providing several levels of users and tool providers.

 

Somewhere high up this chain in computers usage are the people who write the compilers and the languages and other infrastructural things which everyone else uses. This is very close to where I am today, except maybe one level of abstraction beyond that. I am in the business of studying and developing languages and programming paradigms. These are the ideas that are made manifest by the folk who create real languages and write interpreters and compilers for those languages.

 

The business of being in programming languages is a tricky one at best. It is one of trying to create fundamental ideas related to the way people think about writing software. Writing software, designing languages etc are a lot like real languages and cultures. They come with a lot of overhead and inertia and the sort of languages people use tend to affect the way they perceive and express ideas about the world around them. To create new paradigms and approaches for programming usually entails walking upto some very smart people and tell them that you can better the way they think about the world – “See, here is another way, you just have to rewire your brain a bit and it will make perfect sense… “. Tricky business.

 

If I were to add another line or two of abstraction to my work, I would land up in what is well considered to be mathematics. That is not to say that it is all not mathematical in nature already, but it is only slightly more so than the mathematics that can be expressed in any field of life. I remember one of my last days in Hyd at Microsoft, when I was in the process of leaving for university. It was at the canteen at lunchtime that I was having this conversation with friends and I was trying to tell them how I saw computer science as science and that the fact that there was something called software and the software industry only incidental to its true nature.

 

 

Luton

 

I had been to Luton this weekend to see Jims, my neighbor back at Cochin and an old friend. Luton had a carnival happening that day – good fun! Lots of floats and people dancing and such. If it hadn’t been for the soggy UK weather and the near perfect unpredictability of the rain, it would have been lots of fun indeed.

 

Since I have been saying this to a lot of people, I might as well write it down: I grew up reading lots of Enid Blyton (yes..). The thing about Famous Five and such is that you actually do believe that they had wonderful summers in the UK and there was always lots of great food around. Not so. The weather is terrible – I expected a summer and came to this country without a single warm jacket – and its been rainy wet and cold in a perfectly unpredictable way. Cycling with numb fingers and a frozen face isn’t what nice south Indian boys like me were designed for (hear! Hear!).

 

That aside, back to the topic of Luton. I had to write this entry because Luton was a place different from any I had seen in a while. It has a large Indian and Pakistani community and I was genuinely surprised to see streets with urdu and hindi shop names and streets that could have been some part of India. It was also nice to see women in salwar kameez’s – rather fashionable salwar kameez’s at that.

 

It was all very nice, until it started getting to me. It happened suddenly at a moment when I wasn’t watching – my mind let open a torrent of things which used to disturb me about back home which came screaming back. The mad screaming mediocrity of the place started blocking out everything in my head. Why are these people like this? Why? Suddenly I started seeing the look people’s eyes judging you continuously to see  if you are one of them or one of someone else. The road blocks caused by bad parking and lack of courtesy while driving.  The dirt on the street, the littler, the attitude that I don’t care and it doesn’t matter. The whole overwrought cultural pretentiousness – what was that old phrase “we are like this only”. Indeed. The completely lack of politeness, the constant suspicion at an existential level, the lack of the slightest bit of subtlety. When I was finally in my bus back, part of my head was screaming “No not all Indians are like that, look at me, I am different, I care”. But I don’t think it mattered.

 

I think our country and the people lack subtlety simply because they are constantly hounded by a constant deafening noise at an existential level such that they are almost deaf to everything else. The noise of being hammered by “you have to be like this” “even if you chose to change it is futile” “this is the system, live in its rules” “don’t think” – everyday, all you life – it eats away large parts of you faculties. These things were upsetting.

 

---

 

Posted late, as usual.

I was thinking of a highly opinionated, racist (in the funny sense (yes such a usage exists (now it does))) standup comedian of Indian origin called Russel Peters who was talking about his visit to Africa. And he said something to effect of, I went to the motherland .. and quickly correct himself saying, “No not my mother land, black people’s motherland. I am Indian, we have our own motherland, England.”

 

So I am in the pseudo metaphorical  motherland. It’s a beautiful country. I didn’t see much of London – I had friends pick me up at the airport and we drove down to Cambridge. I am staying with friends of Michel Salim from back at IU. Michel was studying at Cambridge sometime back. So I was amazed and grateful for generosity of these guys who drove all the way to Gatwick to pick me up. Its been half a day but already the conversation are interesting.

 

I am also beginning to have the dormant British accent in me wake up. If you know me, you can stop laughing now (that’s for people who don’t know me to reflect on). Its odd – you have to be Indian – grow up reading Archie and Enid Blyton. And go to US, get confused by everything being reversed and learn bits of American. And then finally come to  England and hear the all to familiar British English accent and cars on the left side of the street, to know what I mean.

 

Cambridge is so beautiful. It has narrow roads, quaint brick buildings. I haven’t seen much yet, I just one short walk. Saw an old church, an amazingly beautiful cathedral. I am told that the colleges are very beautiful.

 

Also for the record, I was actually told, in as many words (yes!) that I was cool. Hear ye! Hear ye!

 

Which reminds, when the plane was landing I had the Grandmom in Kumars at No 42 singing “Hare Parky, Hare Parky..” in my mind.
Anyway …

 

For one, what I am doing for summer is cool in the fullest definition of cool in my dictionary. What are you doing for summer? Oh just flaying to UK and am going to be writing an experimental garbage collector and some other things for Haskell at MSR. And maybe write a paper or two in the meanwhile, And maybe see a lot ok UK and some of Europe (the mainland) while I am at it.  That is cool. This is a little outside what I imagined possible a few years back.

 

I am sitting on the window sill of their first floor flat (not apartment). Opposite is a Indian restaurant that says “Chutney Balti House” – ha ha – what does that mean? I wonder if anyone in India would name their restaurant like that.

 

Tomorrow I visit MSR.

 

I have been at Cambridge for about three weeks now. MSR is wonderful. I got to shake hands with a Knight and Turing Award winner – Tony Hoare. Random people you get to meet over lunch are pretty much the reigning best in their fields in computer science. Its like you were an insect of some sort (when I say that I don’t mean anything hoopy like a butterfly or firefly – more like one of those little cricket like things) and you managed to crawl into the midst of a league of intellectual superheroes. It’s a lot like the old Justice League of America comics http://www.hyperborea.org/flash/jla.html (with the minor difference that there aren’t many Americans here).

 

Cambridge is a wonderful place too. Its just that I haven’t had time to write. Seen a bit of Cambridge, been to London, been to Peterborough, am going to Luton today. And the the computer science is intoxicating – along with other minor details like operas, wine, beer festivals etc. Joi di Vivre!

 

An over exposed shot of the statue of Eros at Piccadilly Circus, London.

After several weeks (running into months) of blog silence, here is a post.

 

I have been busy. Been teaching myself several new things. Life in Bloomington has been good on the whole.

 

Several good things have happened in life. I am on the verge of finishing my first formal paper in computer science. I have been teaching myself how think in formal terms, not just as a programmer, but like a computer scientist. It is an interesting process.

 

My first paper should be about the yield operator – it turned out that what was idle tinkering and curiosity over the past few years actually seems to have given rise to something of theoretical value. The paper has some formalizations of things, reference implementations, comparison with existing operators and such. Looks like I just may have enough material for a follow up paper as well.

 

 

I have an interesting summer job. I am going to be (finally) at Microsoft Research in Cambridge. I am going to be an intern working with Simon Marlow and at this time it looks like I will be working on a parallel garbage collector for Haskell. It should be good fun to get back to writing systems code for a change.

 

I have seen so many things in code that I am unsure of code that I write these days. I keep seeing demons in my code. Most of the time I don’t code. When I do, and I intend to use it, it is usually in some extreme language – ruby being one extreme and Haskell being the other. I am afraid of what code I will actually write, when I get down to it and if I actually think about the code. There is an interesting Phil Wadler paper titled “Imperative Functional Programming” – I am afraid that if you give me C these days code I write maybe better described as Functional Imperative Programming. Maybe not that bad though.. at heart I think I am still an imperative programmer – a little shaken, but I can still see the machine execute in my head.

 

 

I also spent sometime writing a little book. It is incomplete, but I offer it for download here. If you are the sort, do read it for the fun of it and give me feedback. My intention is to add for text and add more machines and make it a more complete “little” book.

 

It is a book about abstract machines – machines that will teach you the essence of programming languages and constructs. It shows you how several constructs work in a concise formal way to the extend that you can take the definitions in the book, apply the syntax of your favorite language to it and create your own interpreters and potentially your own programming languages.

 

The Little Machines

 

Thats all for now. More when time allows.

 

ps. If you have any suggestions about places to visit in the UK and such let me know. I am looking for interesting things to do in the time I can take away from work.

 

I now have a new weapon. This time it’s a really dangerous one.

 

 

I now have a Canon Digital Rebel XT – aka the EOS 350d. I have the 18-55mm kit lens and a 50mm f1.8 prime lens. Of course, this is far from the sort of thing I can afford very often – set me back by a $900+ when everything came together, I had some help from my friends to get things to work out. But as life would have it, I had to buy the camera now or wait for ~3 months, since I was leaving the US for a while. More on that later.

 

I have decided to call him “Keeper” based on the keepers in Babylon 5. J

 

I had been Chicago on Thu and took “Keeper” along.

 

  

 

 

This trip also gave me the chance to visit Shedd Aquarium which I had been meaning to visit for a while.

 

             

 

 cheers!

Why Haskell?

So how long does it take for a completely fledgling Haskell programmer to implement a weird language? 2 nights.

 

Its pretty amazing if you think about it – and it fun and not stressful as well. If I did as much in C or Cpp it would have been significantly more stressful and would have take a over a weekend for sure. And even after that it wouldn’t be as flexible as this is.

 

In some sense, in my current limited opinion, Haskell is to Scheme what Ruby is to C++. To add to it, it is purely functional than scheme, is lazy, comes with A REAL library, allows for pattern matching and discriminated unions etc… the goodness goes on – as matter of fact, it can even pretend to be imperative for a bit. Also, GHC generates actual Win32 exes that I can run. If you are a languages person you might think it’s a moot point, but for someone who likes to build tools and wants to sometimes share them with his (less inclined) friends, this is essential.

 

So I think Haskell is going to takes its place in my bag of tools. The only thing I really miss from Scheme land are macros. I wish Haskell had macros – better, I wish Haskell had multistage evaluation.

 

Being a almost ‘pure’ imperative programmer when I joined college, Prof Dan Friedman’s Programming languages class hurt my head really badly. And I was coming to terms with functional programming.

 

Last semester I also took a class with Prof Amr Sabry – Quantum computing – and this was my first real introduction to Haskell. I am working with him this semester and of late I have been trying to understand Monads. Its one thing to have working knowledge of a concept, and its quiet another to formally study it. Monads hurt like few other things hurt before – and the fact is that it makes you look at imperative programming in this totally other way.

 

So that’s the context for why this is in Haskell. The blog entry is really about this little language I wrote in .. in all fairness a little more than a late night. And I haven’t used the parser generator or other tools before this.

 

Yield Language 1.0

So whats the language like? Well, you’re not going to want to use it at all. But all the same it is the lambda calculus with the following additions (some of which take away its purity) – yield (with all the right behavior in place), if-then-else, numbers (+, -, ==), strings (+, ==). In other words, it’s a simple higher order language with strings and numbers and fancy control flow operator called yield, which is the only “impure” part of the language.

 

To support yield I introduce a funny tagging operator I call ‘pi’ to tag a sub-expression that can yield. A pi-expression can be called like a normal application, or can be used as a coroutine using co, next and run.

 

The actual internal implementation is what is best described as “stackless”.

 

 

f = \x ->

  ((("x = " + x) + ", ") +

  if (x == 0)

    "zero"

  else

    "not zero");

 

(f 10)

 

This evaluates and returns “x = 10, not zero”

 

Basic syntax

e =     \x->e

| x

| e1 e2

| if e1 e2 else e3

| (e1 + e2)

| (e1 – e2)

| (e1 == e2)

| <num>

| <string>

| x = e1; e2

 

The above syntactic categories as basically all pure. The last rule is a let. There is no fixed point operator and you will need to add one of your own to do recursion. Evaluation is strict, applicative order. The following are the extensions for yield support.

 

      | pi e

      | yield e

      | co e

      | next e1 e2

      | run e1 as x1 x2 -> e2 or x3 -> e3

 

Some more examples, assume that we have an applicative order Y combinator called “fix”.

-- Applicative Y combinator

fix = \f -> ((\x -> (f \y -> ((x x) y)))

          (\x -> (f \y -> ((x x) y))));

 

Here  is a relatively simple function that takes a number and yields as many times. I have used the fixed point operator so that I can loop inside the pi block.

-- An iterator that yields 'x' times

iter = \x ->

  (pi  (((fix \loop -> \x -> \s ->

                  if (x == 0)  s

                  else v = yield x;

                        ((loop (x-1)) (v+s)))

            x)

      0));

 

One can call this function in two ways – simple invocation –

((iter 1000) \x->(x+x))

 

Or using the coroutine-like behavior, that is sometimes called external-iterators or generators.

call = (fix  (\call -> \c ->

                  run c

                  as (x1 x2) -> (call (next x2 (x1 + x1)))

                  or x1 -> x1));

 

 

v1 = (call (co (iter 1000)));

 

So one can save the following code into a file and execute it from command line using the command –

langy.exe < filename.txt

 

[update: made some simple syntactic niceties to the language]

 

-- Applicative Y combinator

fix = \f -> (\x -> (f \y -> (x x y))

             \x -> (f \y -> (x x y)));

 

-- An iterator that yields 'x' times

iter = \x ->

       (pi  ((fix \ loop x s ->

              if (x == 0)  s

              else v = yield x;

              (loop (x-1) (v+s)))

             x 0));

       

                                  

-- Call will invoke an iterator any number of times

-- At each point it thunks the return value and then uses that as the

-- next value paramter.

call = (fix  \ loop c ->

        run c

        as x1 x2 -> (loop next x2 (x1 + x1))

        or x1 -> x1);

                        

 

v1 = (call co (iter 1000));

                      

v2 = (iter 1000 \x->(x+x));

                      

("Values are " + v1 + ", " + v2)

 

And this outputs –

"Values are 1001000, 1001000"

 

Downloads

 

 

(A much delayed part 2. Previous article is here)

 

Pipelines

 

This article primarily describes the pipeline construct. The simplest way to describe a pipeline is to say the way the trampoline models the interaction between a caller and iterator and, the pipeline models a call tree. One can think of a pipeline as a cascade of trampolines.

 

Suppose one had a call tree where each frame in the call tree corresponded to that of an iterator. As each iterator yields or returns to a yield, what the program effectively does is that it moves values up and down the call tree.

 

Consider the following function –

def bits(n)

      if n == 1

            yield 0

            yield 1

      else

            bits(n-1){|v|

                  yield v*2

                  yield v*2+1

            }

      end

end

 

Here invoking bits with a value n, causes it to yield every possible n-bit binary number. Now this sort of thing is not easy to model with a trampoline. A trampoline lets one process in the trampoline act as a iterator and the other as a caller (though the device itself does not introduce an asymmetry).

 

To do something equivalent to code snippet above, one needs to maintain a chain of iterators. How does control transfer between iterators in call chain, assuming that none of the iterator return? Control can move up and down the call tree corresponding to when a caller returns the value to a yield statement higher up the tree OR the iterator can yield a value to a caller further down the tree. Something like  the diagram below – each up arrow being a return to a yield called by a block on top and each down arrow being a yield. (The direction of the arrow indicates which way control transfers.)

 

The pipeline device gives every process in it to communicate with the process to the left of it or to the process to the right of it. One can choose a convention here where the process to the left of a process can be considered it callee and the process to the right can be considered its caller.

 

The picture below gives a comparison of what the pipeline device does.

 

Every process in a pipeline device is created using a lambda-pipe. A lambda-pipe, unlike the lambda-iter, makes available the binding ‘left’ and ‘right’ in the scope of its body.

 

A process can call left to pass control to the process to its immediate left. It can call righ to pass control to its immediate right. The ‘left’ and ‘right’ are similar to the yield in the sense that they take a parameter and return a value.

 

If a process in a pipe, executes a right with a values ‘v’, the value is made available to a process to its left as the returned value of a ‘left’ executed by it. Hence left and right alls by the process have to match up to facilitate control flow.

 

This is the basic idea behind the pipeline device.

 

Example:

Consider the following function basis, which is basically a rewrite of bits, but for usage in a pipe.

 

(define basis

  (lambda-pipe ()

    (let ((v (left)))

      (if (eq? v 'end)

          (right 'end)

          (begin

            (right (cons #f v))

            (right (cons #t v))

            (yield-all (basis)))))))

 

One can put multiple instances of basis into a pipe and have an initial process that will start the cascade by right yielding a empty list, immediately followed by the end marker.

 

    (foreach (command-shell-pipeline (gen-pipe '() 'end)

                                     (basis)

                                     (basis)

                                     (basis))

             (printf "num: ~a~n" (port-value it))))

 

This produces –

num: (#f #f #f)

num: (#t #f #f)

num: (#f #t #f)

num: (#t #t #f)

num: (#f #f #t)

num: (#t #f #t)

num: (#f #t #t)

num: (#t #t #t)

num: end

 

In the above code a gen-pipe, will simply right yield each of it arguments in the same order. One may notice that I use the command-shell-pipeline in a foreach, which means that it is itself an iterator. The pipe device wraps values in something called a ‘port’, to extract the value from the port, one uses the port-value function.

 

The Pipe device is an iterator: To understand why the command-shell-pipeline is itself an iterator (while trampoline is not) one has to look at the diagram above for the pipe device. The left yield of the left most process (or topmost depending on how you look at it) and the right yield of the right most process are yields that transfer control outside of the pipe device. Hence the pipe device itself is an iterator.

 

[updated] The interesting thing about the pipeline is that each process in the pipeline gets state management for free.

 

The pipe device lets you build only a linear data structure, in the sense that each process in the pipe can only communicate with its left and right neighbors. One can use pipe nested in other pipes or in trampolines to make arbitrarily complex control flow structures.

 

Caveats: In retrospect, to be honest, I haven’t really used the pipe much in actual code. It was created more to fill a missing link in the usage of yields that a device than out of practical usage patterns. One might actually resort to nesting trampoline usages more often that one might use the pipe.

 

Also, the more I think about this device I can see more than one ‘correct’ behavior in the model that it presents to the user which sometimes makes it rather un-intuitive to program with. Desipte this it is easy to see how many problems can be implemented as a pipeline of filters that can each maintain state and back track. I need to try and express more problems with the pipe to see how well they can be expressed.

 

Due to some of these concerns the code for the actual pipe device implementation, takes as a parameter a ‘semantics’ function so that the user can describe the behavior required from the pipe externally. One predefined pipe available is what I have called the command-shell-pipe.

 

 

I am also interested in finding analogous constructs to this – one of the things that I should look at is a non-determinism monad used with a monad for state threads. The processes in the pipeline device are similar to what is described as an ‘online transducer’ by Olin Shivers and Matthew Might in Continuations and Transducer Composition. After putting this up online I see that the transducers are studied in detail by many people.

 

Download code.

 

This is a series of blog entries that introduce three devices written using the yield operator for Scheme. Previously I had the following entries that described the requisite features of a complete yield operator and an implementation of such a yield operator for Scheme.

 

Yield the Magnificent

Yield Implementation for Scheme

 

Trampolines, Pipelines and Pi are programming devices or constructs that are built on top of the yield and purely the functional subset of Scheme.

 

There are many ways one can look at the power provided by the yield operator. One way to look at the yield is that it is a call-tree walker. It can move information up and down the call tree. If the yield implementation is sufficiently flexible, it can walk up and down several call-trees which exist concurrently.

 

Another way to look at the yield is to think of it as adding input and output capabilities to a function in functional system. A function during the process of computing its value changes state, creates temporary variables etc. When the result or return value of the function is computed the state of the function collapses and the value is returned. Yield offers a way for functions to do input and out with other functions while they maintain state. More about this later.

 

Trampolines

I want to start off by introducing the simplest of the three devices, the trampoline – sometimes I refer to this construct as the trampoline process as well. (Note: The name trampoline is used only in the context of the yield based programming device I describe here and is not a logical extension of other trampoline constructs you may have encountered before.)

 

The trampoline was introduced to address the following scenario – in a purely functional context what is the meaning of a parameter code block that is passed to an iterator cannot affect the caller’s state. Such a parameter code block is always a closure, in a functional context. On invoking a closure, the closure cannot maintain or modify state in the caller without resorting to some sort of a side effecting operation such as an assignment.

 

The trampoline packages such a computational effect so that the programmer need not think in non-functional terms when using the yield. Instead of using a set! or an assignment as the computational effect, the trampoline device uses a jump as the computational effect.

 

To illustrate what I mean, one has to look at the relation ship between the caller and a yielding callee in an imperative language. The flow of control is almost always as follows for a Ruby or C# yield (yes, I am abstracting out many details here) –

1. caller calls iterator, control transfers to iterator
2. iterator does some computation and produces a values, yields it
3. control transfers to caller,
4. caller does something with the value – this something is usually a side effect
5.  caller returns a value to iterator, control transfers back to iterator
6. steps 2 to 6 can repeat any number of times till the iterator returns.

 

The problem with this functional programming land is that the there is no use in yielding the value if the caller cant to anything with it – an alternative is pass an environment back and forth between the caller and iterator or some such thing, which is always tedious to manage.

 

The trampoline does the following. The trampoline becomes the caller for two functions, both of which are iterators that concurrently maintain state. One iterator place the role of the caller in the imperative case and the other one plays the role of the callee. Since the function playing the roles of the caller is an iterator, its free to maintain any sort of local state it chooses.

 

The trampoline device is a simple device, but to see the correct analogy that argues its purpose is a little tricky. Another way to look at a trampoline is to look at it as two iterators such that when one yields control passes to the other and when the other yields control passes back to the first. The process terminates when one of the two iterators terminate.

 

 

Here is an example of code that uses the trampoline. When the trampoline process terminates, a list of values that are the return (or last yielded values) of both iterators is returned.

 

This is an iterator that adds values that it gets yielding the current sum at any point.

(define adder

  (lambda-iter ()

     (let loop ((s 0))

       (loop (+ s (yield s))))))

 

This is an iterator that yields the first ‘n’ Fibonacci numbers

(define fibonacci

  (lambda-iter (n)

    (let loop ((a 1)(b 1)(n n))

      (if (not (zero? n))