I was speaking with a friend the other day and we were talking about the interaction of effects and how to explain them.

One informal way to explain some additions to languages are that they are scale down localized structured versions of features that were largely available for the whole program. Let me explain: Did you start programming with an imperative language with global variables? (There is one called C that affected the minds of many people.) When you switch to an object oriented language, someone might have explained to you that there is no longer any need for real global variables. You may make these wannabe globals members of a class. You can turn methods that need the globals into members of that class as well. So they are global as far as the methods in question go, but they are not truly global.

In much the same way, we can explain yield. Programming languages have always had input and output operators - scanf-printf, gets-puts etc. However these operators are global with respect to your program. When you execute a printf, it is the output of the whole program, not of any one part of it. Yield on the other hand can be thought of as a localized input output operator. You can yield values from one part of the program to another part of the program. You get input from one part of the program. A method that yields is a packaged up opaque entity, a little sub-program, that communicates using yield with its consuming-context, the rest of the program.

We can explain exceptions in this way as well. In the absence of exceptions when there was a fault, the whole program would come down. It would core dump, modulo global error handlers. The whole machine does not come down, just the program that faults does. The environment that hosts the program may realize that there is a fault and do something about it. Its much the same with exceptions, but with the difference that only a part of the program "core dumps". Its a localized failure of the program that the environment (the rest of the program) can handle (or not handle, thereby making it a global failure).

So can you play this game or any other global program features, turning them into powerful localized structured operators?

An odd idea from a few days ago:

I watched this video a while back, this is Richard Feynman giving a lecture about discovering laws in physics -

He is talking about laws in physics. (the underlying Philosophy of Science that Feynman describes here is due to Karl Popper)

What Feynman is describing seems fundamentally different from what we do in the formal sciences like math/logic/cs. In the later we usually choose an axiom set that we believe to be right, based on our aesthetics, and then go on to prove other things that are right wrt our axioms.  Only things that are provable are taken to right and things that are right are irrefutably so. The system is inconsistent if we deduce False from the rules that we have. Inconsistent systems are not interesting. All formal methods work like this, in spirit - they keep track of what is right.

In what Feynman is describing, they don’t have a formal notion of right. They have a notion of what is wrong and as long as something cannot be constructively (by experiment) shown to be wrong, they can temporarily accept it to be not-wrong. If you look at this as a formal system, this is one where “what is not wrong yet” is known instead of what is right. Something is not wrong because 1) We don’t know a proof by which we can construct F from it or 2) Given our current inference rules there is no proof for it. But, we may add a new inference rule to the system in the future which may invalidate the belief that something is not wrong. It’s a feels like the opposite of what we do with logics.

Imagine a formal system or a model of computation based on notion like this. We are, in a fundamental sense, giving up the notion of consistency and completeness when we do this. I wonder if there exists a computational model that corresponds to such a “co-logic” of the sort they use in the *real* sciences. Such a system, in spirit, might be able to deal with partially correct data, incorrect assumptions etc. in a natural way. Absolutely correct data (or properties about the data) would be the exception.

(I wonder what this implies for the incompleteness theorem and such. I have been told that the "co-logic" I refer to here is actually co-induction. I see some similarities there, but I am not sure if its exactly that. )

A Tutorial on (Co)Algebras and (Co)Induction - Jacobs, Rutten

A Tutorial on Co-induction and Functional Programming

Being at Indiana University, which is an old time Scheme hub, every now and then I am exposed to some of the turmoil in Scheme community over the new Scheme standard, R6RS. Essentially the community is having a hard time agreeing on what should be in the new standard. There are some very smart, very accomplished, very opinionated people who belong to this community and the language spec is a bit of a battle ground, from what I hear. (As are all language specs... some battles, I suspect, lack the intellectual quality of this one)

I am not very much of a Schemer myself, I sometimes indulge the language on a need basis. I hear from some my more intensely-Scheme-happy friends about some of the latest news at Scheme-spec land. One of the names that was mentioned in recent times is that of Will Clinger. Apparently, Will Clinger set into motion some of the discussion that formed the origins of the new standard, called R6RS (that is short for Revision-6 of the Report on Scheme - or something approximately like that). Over the years the formalization of R6RS has had its ups and downs. Of the many differences of opinion on the standard, some resulted in the formation of a group that decided to create an alternate standard. This group is called SchemePunks, apparently headed by Will Clinger himself (*). While this is mostly hearsay, it seemed amusing none the less. I also, sort of, like Scheme - so I listen in when one of these conversations come up.

Today I was searching for something and I came across the SchemePunks webpage/wiki. I didn't realize they had a webpage. Better yet no one told me that it written in excellent Hitchiker style! I read this and burst out laughing - what a way to motivate a language standard! I don't know any of the design decisions they have made, but the introduction here is sheer genius. Despite not being a Schemer, I am almost tempted to join in. :)

From the SchemePunks webpage:

On 29 August 2007, the Revised Revised Revised Revised Revised Revised Report on Scheme was ratified by the Steering Committee. This has made a lot of people quite angry and has been widely regarded as a bad move.

Many programmers believe that it was created by some sort of community process, though the Jatravartid people of Viltvodle VI believe that the entire Standard was in fact sneezed out of the nose of a being called the Great Green Arkleseizure. This theory is not widely accepted outside Viltvodle VI, and so, standards being the puzzling documents that they are, other standards are being designed. And this wiki, which is called SchemePunks, is definitely not part of the Scheme Underground, even if it is, which it isn't.

Which is very odd, because without that fairly simple piece of knowledge, nothing that is written on here could possibly make the slightest bit of sense. We hope to develop an alternative specification for the Family of Programming Languages known as Scheme. Watch this space.

Being somewhat bowled over, I had to look for the man - William Clinger, Professor of Computer Science, Northeastern U.
http://www.ccs.neu.edu/home/will/Personal/western1.jpg

:)

I wish more languages where designed in H2G2 spirit. Aah!

From his webpage:
http://www.ccs.neu.edu/home/will/R6RS/essay.txt

More than twenty years have passed since I wrote this [1]:

Programming languages should be designed not by piling feature on top of feature, but by removing the weaknesses and restrictions that make additional features appear necessary. Scheme demonstrates that a very small number of rules for forming expressions, with no restrictions on how they are composed, suffice to form a practical and efficient programming language that is flexible enough to support most of the major programming paradigms in use today.

I have to say, I am compelled to agree, though I wonder how of it applies to the Scheme of today. The essay is worth a read, even if you are not a Schemer. You can skip over the Scheme specific parts and just look at the language design philosophy.

I get irritated because too many people in the "computing" business don't understand the word "lambda". Its just irritating because at the heart of it, its just a simple fundamental idea, like the notion of natural numbers or counting. So just spend a few minutes, understand what it means and stay educated. In a few years (if not already), almost every language is going to expose something like a lambda to its programmers. So just pick up the idea ok?

This is a working description, it wont make you an expert on the Lambda Calculus. It might give you some intuitions about it though. Lets get started.

So assuming you are familiar with a C-like language, how do you write a function that takes an integer and returns it?

int foo(int x) {
    return x;
}

Now lets look at what this is saying, it says there is a function called foo, it takes an int which it names x and it returns an int. the body of the function has a single statement called return x. Great! Now, this function is a very famous one and is called the identity function (usually goes by the nick-name id). Also when we talk about functional programming we dont really care very much for the C-style types. So let's rename the function and drop the types.

id(x) {
      return x;
}

Don't worry too much about the types. Typed functional languages usually have a different notion of types from the C like languages. The types will come back, but in a bigger and better form. We however wont discuss any type theory in this article.

So now, what it is saying? It says here is a function called id, it takes some value that it calls x and it returns x. Ok, now lets take a look at this closely. In the syntax that we have here, the name of the function is part of the syntax. We would like to say - here is a function and then assign it the name id. So that we are able to look at the function and its name as two different things. Lets do that by introducing the keyword called "function". Javascript, for example, has such a keyword.

id = function(x) {
      return x;
}

Ok. Now lets make one more simplification. Lets say that the language is a little like Ruby or so where that last statement in a functions body is its return value. Did you get that? That means that we no longer need the keyword return. We can simply make the last statement x and by that we know that the return value from the function will be x.

id = function(x) {
      x;
}

Great, lets rewrite this a bit:

id = function(x) { x; }

Now for one more simplification (really C like languages are so complex!) - lets assume that we can write only one statement inside each function. Just one. If that's the case it can be much like a if with just one statement - we don't need the curly braces anymore. We also don't really need the semicolon.

id = function(x) x

Great! Congratulations ladies an gentlemen, you are looking at a lambda. Simply rename the keyword function and call it lambda and we are all set.

id = lambda(x) x

If we drop the name assignment and look at it we have:

lambda(x) x

This is a function that has no name. It take one argument and return it. Various functional languages use slightly different syntax for writing out their lambdas. The lambda calculus, the underlying calculus of these systems, usually uses a \ instead of the verbose name lambda. It also uses a dot to separate the arguments from the body of the function. A little like this:

\x.x

The functional language Haskell uses an arrow to separate the body from the arguments.

\x->x

The language(s) ML, OCaml, SML, (maybe F#) etc. use the name fun to stand for lambda.

fun x -> x

The language Scheme uses the name lambda and lots of parenthesis.

(lambda (x) x)

Ruby lets you write something very similar to a lambda like this:

lambda {|x| x}

Most of these languages give you some mechanism by which you can give a name to your lambdas (otherwise most of the time you are a little hard pressed to refer to them).

Haskell

id = \x -> x

ML

let id = fun x -> x

Scheme

(define id (lambda (x) x))

There are some alternate syntaxes for writing named lambdas in most languages:

Haskell

id x = x

ML

let id x = x

Scheme

(define (id x) x)

So what is a lambda? It is usually a name used to define a function. The function is a value that can be assigned to a variable name. Just like any other value in your language.

A lambda is an abstraction form. Normally in a program you can read the value of a variable to which you have not assigned a value. In other words is you write (x + 1), it does not have any meaning if x has not been assigned a value already. One way to look at what lambda says is that it abstracts the value of the x. So \x.(x+1) means - give me a value for x and then I will give you the value for x+1. The value of x is abstracted in the body of the lambda. This description comes very close to our informal notion of a function in a C like language.

The lambda calculus usually allows only for lambdas that take one argument. Hence to write functions that take multiple arguments we nest lambdas. We write \x.(\y.(x+y)) for a function that adds two numbers. Most functional languages support multi-argument lambdas. In Haskell this would be \x y -> (x+y).

So what's the big deal? Nothing much and quiet a lot. Nothing much because the notion of functional abstraction is something we learn from high-school math which we port over to programming languages. This is an old and familiar notion.

That said, in the functional programming community, it has long been realized (it is a large community with varying beliefs, secret cults, traditions and practices) that lambdas are the only abstraction form required for a lot of things.  One can do away with loops and conditionals (if, switch) and assignments and numbers and object oriented programming and pretty much everything you can think of (and some things you cant) - they can all be encoded using lambdas. Hence lambdas form a sort of foundational building block for a large number of programming paradigms. At the heart of all of this is the notion of a function - hence the name functional programming.

This is a great slide deck from Benjamin Pierce, Professor Computer Science at UPenn, that shows what the world of programming languages research is doing especially in the context of types.

http://www.cis.upenn.edu/~bcpierce/papers/tng-lics2003-slides.pdf

Also from Pierce is a really good introduction (the best I have found to date) about polymorphic lambda calculi and actually programming in some of those languages. This describes the hierarchy starting with the simply typed lambda calculus (F1) and describes F2, F3, etc and Fw (F-omega). He also talks about encodings of various sorts of types and a whole lot of neat stuff. All of that written in a very readable fashion. I spent my weekend on this and it was time well spent.

http://www.cis.upenn.edu/~bcpierce/papers/leap.pdf

(For some reason this pdf seems to be back to front, but its just fine when printed)

Pierce's webpage is a gold mine of information for the PL student, including neat things like a 'Great Works in Programming Languages' list. He is also a pretty good photographer. I did see him in person when I was at MSRC in summer of 2006. I believe he was visiting those days. I now regret not having walked up to him and saying hi.

"Can you recommend any C++ books?"
"I don't recommend C++."

Afterwards I reluctantly come up with some names. I beginning to notice that I eventually end up mentioning the Scott Meyers "Effective C++" books. The last time I did this I started to wonder why I say this?

When I first read "Effective C++" I was horrified. If I derived any pleasure out of it, it was comparable to the morbid curiosity of going to witness an execution (I probably would not do that though, if I ever got such a chance. I don't have the stomach for it). Back to C++ - Firstly there was no way I was going remember all of that. Secondly I felt deeply uncomfortable. In time I realized that the whole book was written in the style of demonstrating "effective" usages of C++, while what it truly was is a careful documentation of the flaws of the language. Every chapter in that book talks of a language flaw in excruciating detail and how to live with it. That book should have been called "Defective C++".

Then there was "More Effective C++" which essentially did more of the same.  Here is what the language does, here is what you think it would do, here is what you'd like it to do and you put these together and it blows up in your face. In time, my intellectual immune system kicked in and started erasing most of my memories about all this.

So why do I recommend the "Defective" and "More Defective" books? My first recommendation would be to get out of the situation, don't deal with the language if that's possible. If not, and you intend to get it to serve you (instead of the converse) you need to quickly understand that most of the abstractions it provides are leaky. There are hardly any non-leaky abstractions that C++-land provides. (Some people associate this behavior with some notion of "freedom" - I trust evolution will take of those folk.)

So if your abstractions are leaky, in that they are going to have strange interactions with each other under-the-hood, then you should quickly start developing an understanding of what happens under the abstractions you are given. Your effectiveness as a developer becomes proportional to your understanding of what happens under the surface. Hence the "defective" C++ books are a useful read.

Today Aziz mailed me a build of his Ikarus compiler for Windows. Though I don't have much to do with software as such these days, I was excited. Ikarus is Aziz's Scheme Compiler. I use Petite Chez Scheme on my machine. Petite  is Kent Dybvig's Scheme interpreter, part of the Chez Scheme compiler system. I don't have Chez Scheme itself because it sells, I am told, for several thousands of dollars and hence I cant afford it. I expect Ikarus to be comparable to full Chez in many ways and surpass most other Scheme systems out there.

What Aziz sent me was a zip file that extracted to a 128k exe and 4mb "boot" file. He says the boot file says the same between windows, linux and mac. The bootstrap executable changes. This is amusing because the "boot" file is actually the compiler binary. It contains the compiled x86 code.  He able to get away with this because he only relies on the OS to load his little bootstrap exe. After that point he simply allocates memory pages from the OS and relies on the OS for almost nothing that he can do himself. So the exe loads the boot file into memory which then acts as its own loader, sets up its own stack, lays out its own code and data areas, does its own GC and such.

Of course, all of this is written in Scheme itself. There is probably a small C file somewhere that acts as the main() and the initial call into some ASM code that transfers control to Scheme. Fun fun.

I have talked to Aziz about many parts of this system and almost always the design has seemed to be of very high quality. His management of code objects, the runtime stack, continuations and on and on. The system has a large part of R6RS implemented and is already a superset of R5RS as far as I understand. Depending on how the development process stabilizes (after all, this is all one persons implementation), I might move over Ikarus altogether and maybe use it exclusively. 

 

One of the solutions that did not make it into my yield paper (though I sort of liked it) was one that used “braiding”.

 

The problem here is to do a breadth first traversal of a binary tree. I was looking for a solution using my pet control operator yield. The braiding solution occurred to some months back as a consequence. The solution that finally made it into the paper was one based on a more traditional queue based breadth first traversal (BFT from now on) which did have better perf than the braiding solution. I am however documenting the braiding solution here because I think its elegant at some level.

 

So how would one do a BFT of a binary tree? Look at this entry for a slightly more detailed problem description. Simple, we start out by defining braiding.

 

Say you have two yield based iterators. These are just computations that yield values during their process of evaluation. These iterators yield values of type Maybe. For those unfamiliar with the Haskell type “Maybe”, here is a definition –

data Maybe a = Just a | Nothing

 

It simply says that a value of type maybe is either some actual value or the special value nothing. If you desperately need an analog, think of it as a pointer or a reference – it either points to some object or its null.

 

So a stream of maybe-values looks like this

x1 x2 # x3 x4 x5 # # x6 # ..

 

where the ‘x’ denote actual values and the # denotes occasional ‘Nothing’. If one had two such streams of values, then one can braid them as follows. Consider the stream of xs’ and the stream of ys.

 

x1 x2 # x3 x4 x5 # # x6 # ..

y1 # y2 y3 # y4 y5 # y6 y7 # ..

 

On braiding gives a single stream with that switches between the original streams every time it sees a Nothing. This results is a single stream like this –

 

x1 x2 y1 # x3 x4 x5 y2 y3 # y4 y5 # x6 y6 y7 # ..

 

This is how braiding works.

 

So how does one do a BFT? Simple, one recursively traverses the tree as follows –

• If you are at a leaf, yield the leaf value and then yield a Nothing.
• If you are at a branch, yield the branch value, a Nothing and then braid the iterators of the left and right branches.

 

Simple – that’s a breadth first traversal. If you look at the algorithm closely you will realize that final stream produced will be in the breadth first order but will also contain occasional Nothing values – the Nothing values will be precisely in the those places when values of one level deeper in the tree are being produced. (Of course, you don’t want to expose the Nothings you can add a filter and remove them).

 

The other important observation, which is also a requirement of the problem, is that the values used to resume the iterator will be available to the branches or leafs that yielded the corresponding value – hence tree reconstruction is trivial.

 

-- This a breadth first tree walk that reconstructs the tree from the

-- the return values of the yield. It is expands the tree one level at

-- a time and internally uses Nothing to communicate level changes.

bfTreeWalk :: Tree a -> Yield i a (Tree i)

bfTreeWalk tr = suppressMaybe $ bft tr

    where

    bft (L v) = do (Just v') <- yield (Just v);

                   yield Nothing;

                   return (L v')

    bft (B v t1 t2) = do (Just v') <- yield (Just v);

                         yield Nothing;

                         (t1',t2') <- braidMaybe (bft t1)(bft t2);

                         return (B v' t1' t2')

 

Here is the tree walk in Haskell. Even if you are not able to run or fully grok the Haskell code above, you should be able to use it as a guide to reconstruct the solution in your pet language.

 

The supporting braid and suppress functions are below –

 

-- Convert maybe values into real values by ignoring the Nothing.

-- 1 2 10 # 3 30 # 5 6 70 50 # 8 ...

-- Becomes

-- 1 2 10 3 30 5 6 70 50 8 ...

suppressMaybe :: Yield (Maybe i) (Maybe o) r -> Yield i o r

suppressMaybe yb = runMapY yb sM

    where

    sM Nothing = return Nothing

    sM (Just v) = do r <- yield v;

                     return (Just r)

 

-- Alternates two iterators, every time one yields a Nothing

-- 1 2 # 3 # 5 6 # 8 ....

-- 10 # 30 # 70 50 # 80 ....

-- and makes (where # is a Nothing)

-- 1 2 10 # 3 30 # 5 6 70 50 # 8 .. 80 ... ....

braidMaybe :: Yield (Maybe i) (Maybe o) r  -> Yield (Maybe i) (Maybe o) r -> Yield (Maybe i) (Maybe o) (r, r)

braidMaybe yb1 yb2 = bM (runYield yb1) (runYield yb2) True

    where

    bM (Iterator (Just v) k) it ord = do i <- yield (Just v); bM (k i) it ord

    bM it1 it2 False = do yield Nothing; bM it2 (resume it1) True

    bM (Iterator Nothing k) it True = bM it (k Nothing) False

    bM (Done v1) (Done v2) True = return (v1, v2)

    bM (Done v) it True = bM it (Done v) False

    resume  (Iterator Nothing k) = (k Nothing)

    resume it = it

 

The code above uses a monadic yield implementation and can as easily be expressed by any language which supports a good yield operator. (As of now I have a yield implementation for Haskell and Scheme and I believe Sid has ones for Python and Ruby (?))

 

At this point I should note that I was referred to the naïve implementation of BFT using nested lists by Simon Peyton Jones. The cods is below

 

breadthFirstTW :: Tree Int -> [Int]

breadthFirstTW t = concat (bft t)

  where

     bft :: Tree a -> [[a]]

     bft (L x) = [[x]]

     bft (B t1 t2) = b_zip (bft t1) (bft t2)

 

     b_zip :: [[a]] -> [[a]] -> [[a]]

     b_zip [] ys = ys

     b_zip xs [] = xs

     b_zip (x:xs) (y:ys) = (x++y) : (b_zip xs ys)

 

The essential idea behind the braiding traversal is not very different from that of the nested solution with the operational encoding of nested lists using Maybe. However looking at the nested list solution, at this point, it is not apparent to me how it can be extended to reconstruct the tree.

 

The implementation of the monadic yield that this relies on is documented in my paper which I hope to put up on my academic website soon enough.

I was attending a talk by Andrew Kennedy today when I heard that Rotor 2.0 has been released. So it has the Shared Source version of the cool new C# compiler and such. Fun Fun.

Download

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.

 

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))

          (begin

            (yield a)

            (loop b (+ a b) (sub1 n)))))))

 

To sum the first n Fibonacci numbers, one create a simple trampoline between the iterators

(printf "Sum = ~a~n"

        (cadr (trampoline-process (fibonacci 10) (adder))))

 

The cadr is there because the trampoline returns a list of two values, the last value obtained from the Fibonacci and the last value obtained from the adder. We are interested in the sum yielded by the adder and so we take the cadr.

 

The trampoline process that is implemented in the library that I have shared below is a slight generalization of this idea – the generalization being that the trampoline process can take any number of iterators as arguments creates a circular list of control transfer using yield. While having two iterators in a trampoline can be thought of as the equivalent of an imperative caller and callee, there is no simple parallel I can think of for three of more iterators in a trampoline. Below is a diagram of trampoline with three iterators.

 

 

I frequently use a trampoline while programming in scheme using yield. While it may not be easy to see why trampolines are useful just by using a simple example like the above, they useful in managing code complexity when each of the iterators involved has to do a non trivial computation.

 

As an example I wrote a CPS transformer for a subset of scheme last semester, at the heart of which was a trampoline. One iterator would recursively walk down the source expression tree and would yield out values. The other iterator would reconstruct a CPSed expression. So it gives you the conceptual clarity of writing a two pass CPSer while in effect only one pass happens. (Of course I could mash both the analysis and construction phases into one big hairy ball of mutually recursive functions, but that would not let me focus on one problem at a time and possible build them up as reusable iterator components. This of course was a little non traditional and might not have been easy on the evaluator of the assignment).

 

Download Sources for Yield, the Trampoline and the Sample Code above.

 

In the next related entry I hope to discuss the Pipeline device (aka the Pipe device).

 

What is the Y combinator? I have seen lots of discussions on the web but nothing that seemed like a simple explanation of how it works or why it is needed. I finally understood the Y combinator a few days back and a lot of things snapped in place. So here I will try and explain it from my perspective. In this entry I am taking liberties with various syntaxes – please bear with me.

 

This is the Y-combinator for a normal order lazy language –

Y = \f.((\x.(f (x x))) (\x.(f (x x))))

 

(Here, the ‘\’ denotes a lambda). Scheme is an applicative order language and the above combinator cannot be used as such in scheme because it will lead to an infinite expansion. More on this later.

 

Let’s start from some basics – say we are writing a mathematical expression and we said

a = a + 1

While the above means something in imperative programming languages (like C), it does not mean anything in mathematics.

 

Now say I want to write the factorial function in mathematics, I would say something like this

fact(0) = 1

fact(n) = n * fact(n-1)

And this definition is perfectly valid. However you notice that it is similar to the a = a + 1 expression in the sense that in describing the value of something, we refer to that very thing.

 

This general principle, called a recursive definition, has a problem in the context of pure functions (like the lambda calculus). The problem is as follows – a function is a nameless entity – the only named entities that a function can use are function’s parameters (the variables introduced by the function itself) or parameters of a parent function that it is define in the scope of.

 

For example

(lambda (x y)

      ; can use x and y here

      (lambda (a)

            ; can use a, x and y here

      )

)

 

Now for a recursive definition, a function needs to be able to refer to itself (or like we say in some languages, a functions needs to ‘call’ itself).

 

So, the only way that one can define a recursive function would be to receive the function itself as one of the functions arguments. Think about this for a bit – if you are not used to programming in a language where you can pass a function, or return a function as though it were a value (similar to how you treat an integer), then this might be a hard idea. If you are from a programming background that wherein you are used to ‘higher order’ programming, then I am only stating the obvious here. (The general idea with higher order programming is that functions are first class values, like integers – which means that they can be passed as arguments, returned from functions, stored in data structures etc).

 

So we define a function such that it takes an additional argument which is itself.

Lets say

 

factorial0(factorialx, n) = if n == 0 then 1 else n * factorialx(factorialx, n -1)

factorial(n) = factorial0(factorial0, n)

Does this make sense? If it does not, then don’t bother read further. You notice that the factorial0 function takes 2 arguments one of which is the function itself.

 

Let me rewrite this in scheme-style syntax

(let ((factorial0 (lambda (fact, n)

                    (if (zero? n)

                        1

                        (* n (fact fact (sub1 n)))))))

 (let ((factorial (lambda (n)

                    (factorial0 factorial n))))

      ; I can use factorial here

  ))

 

Make sense? Ok, so now let me write the interesting function factorial0 as a nested lambda as follows -

(lambda (fact) (lambda (n)

(if (zero? n) 1 (* n ((fact fact) (sub1 n)))))

 

You notice that fact is applied to fact, to generate the inner lambda which is then invoked with n-1.

 

So now, suppose one has a handy function of the following form

omega = (lambda (x) (x x))

 

One can define factorial as follows

 (let ((factorial

       (omega (lambda (fact)

                (lambda (n)

                  (if (zero? n)

                      1

                      (* n ((omega fact) (sub1 n)))))))))

  ; use factorial here

  )

 

There you go – so now we have a way of defining recursive function definitions even if your language did not directly allow a recursive definition.

 

So why do we need the Y combinator? You notice that in the definition of factorial we had to do something that looks very strange in the definition of the function – we call the function omega to return a function that we can call. The Y combinator does away with this for us.

 

To start thinking about the Y combinator, think about things this way – suppose the parameter ‘fact’ was already ‘(omega fact)’ then we wouldn’t have to call omega inside the definition of factorial correct. Right?

 

If we wanted that we simply need to rewrite omega this way right –

(lambda (x) (x (x x)))

Such that the first parameter is already applied to itself. But then this is not enough, because when the recursive call is made, the second time the parameter is only fact and not (fact fact) or (omega fact). Well, so we can fix this by having one more level in the definition of omega, such that omega looks like this –

(lambda (x) (x (x (x x))))

 

But then the third time this would not be the correct parameter… ideally we need an infinite application of x, because we don’t know how many times the function will call itself. In other words the omega should look a little like this

(lambda (x) (x (x (x (x (x … ))))

 

This is exactly what the Y combinator does. To see how it does this consider OMEGA defined as

OMEGA = (omega omega)

(or expanding for little omega we get)

OMEGA = ((lambda (x) (x x)) (lambda (x) (x x)))

 

If you haven’t seen this before, look at this device for a bit – do you see how it is infinite self application? If you do then consider the following

((lambda (x) (f (x x))) (lambda (x) (f  (x x)))

It doesn’t matter what f is right now, but see what this does. After one reduction this would look like this -

(f (term term))

Where term = (lambda (x) (f (x x)))

The second reduction would look like this and so on

(f (f (term term)))

(f (f (f (term term))))

 

This, if you notice is similar to what we required earlier, where instead of ‘f’ we used ‘x’.

 

This is the basic mechanism for the Y combinator. And the Y combinator is simply

Y = (lambda (f) ((lambda (x) (f (x x))) (lambda (x) (f  (x x)))

 

So how do we define a recursive function using the Y? Here is factorial

(let ((factorial (Y (lambda (fact)

                      (lambda (n)

                        (if (zero? n)

                            1

                            (* n (fact (sub1 n)))))))))

  ; use factorial here

 )

 

Nice?

 

Now in the beginning I said that this Y is the Y for the last normal order language. Scheme is applicative order and non lazy. What that means is that  if you use the Y combinator defined above in scheme, during the definition of factorial it will try to do the infinite expansion and will never terminate.

 

Instead one just eta-expands the definition to get the applicative order Y combinator. Suppose you say that term is (lambda (x) (f (lambda (y) ((x x) y))))

And we define the combinator as

Y = (lambda (f) (term term))

Then we have the applicative order Y that is usable from scheme and other applicative order languages.

Look at its expansion to see what I mean

(f (lambda (y) ((term term) y))

So the first parameter to ‘f’ (recursive function we are interested in is a lambda – the application inside the lambda is done only if f calls it.

 

Let me define both the Y combinators described here in lambda form

Y = \f.((\x.(f (x x)) (\x.(f (x x)))

Y = \f.((\x.(f (\y ((x x) y))) (\x.(f (\y ((x x) y))))

 

Once you see why the Y combinator is needed and you understand omega – its easy to see what the Y is and how it useful in defining recursive functions in a mathematically pure way.

 

The Y combinator is described as a fixed point function or combinator. The idea is that is lets a function describe its behavior in terms of itself until the function reaches a fixed point – like in the case of factorial the function reaches 0 and does not need to recurse any more.

 

References –

http://en.wikipedia.org/wiki/Y_combinator

http://www.dreamsongs.com/NewFiles/WhyOfY.pdf

 

Though I myself had looked at the Y many times before I never really understood it until I had to write recursive functions in the pure lambda calculus and I used omega to do it. I then happened to mentioned to Prof Friedman that I did not understand the Y and in a minute he set my thinking right.

 

I understand that in the description above I have taken some liberties with syntax and something are described in a hand wavy sort of way. However if you have suggestions about how I can better explain this, let me know. Of course I require that you understand scheme style syntax and higher order programming (at least minimally).

 

Some context –

 

The other day in Prof Dan Friedman’s Advanced Programming Languages class we had an assignment where we had to write a lambda calculus interpreter that did non deterministic application and we had to write the factorial in it. Also, reduction was to continue even if the top level term was value.

 

As a consequence of working on this we were expected to discover a method of encoding numbers using pure lambda terms. A really long time back Alonzo Church (creator of the lambda calculus) created an encoding now called the Church numerals. I created the following set when working on the factorial problem.

 

t = \a.\b.a     true

f = \a.\b.b     false

 

zero = \x.t

zero? = \x.(x f)

 

s = \x.\b.((b x) b)      successor

p = \x.(x t)             predecessor

 

(Like in Haskell the ‘\’ represent lambda). So we have a way of saying zero, we have a way of checking if a number is zero and we have the ability to add one and subtract one. That gives us all the natural numbers including zero.

 

If you notice, the predecessor define above returns a value that is an invalid number when applied to zero. An alternate ‘type safe’ definition is the following –

p = \x.(((zero? x) x) (x t))

 

Here (p zero) is zero.  

 

Now you may think that that’s not great way of implementing numbers – its inefficient etc. Yes that’s true, but remember that the lambda calculus is a formal system, it’s a mathematical formalism and hence has no notion of cost. In the study of formal systems (other than the study of their complexity) we are interested in asking questions about what the system can do and cannot do. The above encoding I believe is equivalent to the encoding of Church numerals.

 

Following the definition of numbers, I can define ‘add’ in the following obvious way -

add = (Y \add.\a.\b.(((zero? a) b) ((add (p a)) (s b)))

 

Here ‘Y‘ is the fixed point Y combinator and this is equivalent to

add(a, b)  { if a == 0 then return b else return add(a - 1, b + 1) }

 

Similarly one can define ‘mul’ and ‘factorial’ as well.

 

I went ahead and defined operators so that I have scheme/lisp style lists. I am told that there are very similar to Church’s definitions.

 

cons =  \x.\y.\b1.\b2.((b1 f) ((b2 x) y))

car =   \ls.((ls #f) #t)

cdr =   \ls.((ls #f) #f)

null =  \x.x

null? = \ls.(ls #t)

 

Hence we have –

(null? null) -> #t

(car null) -> undefined

(cdr null) -> undefined

(car (cons a b)) -> a

(cdr (cons a b)) -> b

 

Can you shoot yourself in the foot using these definitions? Of course you can – but if you are careful you can write meaningful programs as well. To do other sorts of checks, like to prevent us from doing (s cons) we need some kind of type system or validations rules – but these are not relevant to the discussion of the pure lambda calculus.

 

Here is a basic lambda calculus reference - http://en.wikipedia.org/wiki/Lambda_calculus

Here is a Church encoding reference - http://en.wikipedia.org/wiki/Church_numeral

 

FooGroup Algebra is a little ‘algebra’ that I created while trying to solve a problem. It seemed sufficiently interesting to describe by itself. I would have liked to call it group algebra, but it seemd like the name would already have been taken, and it also seemed like that’s too nice a name to dedicate to something like this :)

 

FooGroup Algebra

 

A term in this algebra consists of one or more symbols enclosed in [] or (). An expression is a set of terms. The enclosing [] or () are called the type of the term. The symbols the enclose are called base of the term. The ordering of symbols inside a term is of no significance. The ordering of terms in an expression is of no significance.

 

Here are some expressions:

(a b c)[c d]

(a b)(c d)(a d)

 

An expression is said to be solved, if all the terms in the expression have only one symbol. The following is a solved expression:

(a)[b](c)(d)

The value of each symbol is the type of the term that it is held.

 

An expression is invalid or is a contradiction is there atleast two terms of different type but same base. The following expressions are contradictions:

(a b)[a b]

(a)(b c d)[a]

 

Term Reduction and Solving: One can solve and expression by reducing each term in the expression until every terms contains only one symbol. Terms can be reduced as follows –

(X Y) => (X)[Y] and [X](Y)

[X Y] => [X][Y] and (X)(Y)

Where X and Y are any set of terms.

 

Since a term can be reduced in two ways, there maybe more that one solution for a given expression. A valid solution cannot have a contradiction. Here are some example reductions –

(a b c)[c d]

(a)[b c][c d]

(a)(b)(c)(d)

 

This is another solution for the same –

(a b c)[c d]

(a)[b c][c d]

(a)[b][c][d]

 

This is another solution for the same –

(a b c)[c d]

[a](b c)[c d]

[a](b)[c][d]

 

This is another solution for the same –

(a b c)[c d]

[a](b c)[c d]

[a](b)[c][d]

Independent Variables: When reducing a term we select one variable and assign it both type values. The values of other symbols/variables might be get fixed as a consequence of this. Such variables are referred to as independent variables. In the general case, the maximum number of solutions than an expression can generate is 2^n where n is the number of independent variables. Since one or both choices of type assignment may result in a contradiction the number of actual solutions maybe lesser than this.

 

In the above example, there were two independent variables a and b. c and d values were fixed by the selection of values for a and b. Hence there were 4 solutions.

 

Ex:

(a b)(b c)(c a)

(a)[b](c)[a] <-- contradiction

[a](b)[c](a) <-- contradiction

This expression has no solutions.

 

(a b)(a c)(a d)[b c d]

(a)[b][c][d] <-- this is one solution

[a](b)(c)(d) <-- this is a contradiction.

The above expression has only one solution

 

End.

 

That’s it. That’s all I know about this thing. I would like to create a method to predict how many solutions an expression may have. I don’t know how to do that.

 

I also would like to explore extensions to the algebra in terms of adding more types to the algebra.

 

Adding More Types: Right now I have only two types () and []. One can think of the relation between these as that of the relation between –ve and +ve, or as odd and even.

 

()() = [] or odd odd = even or - - = +

()[] = () or odd even = odd or - + = -

 

One can consider adding three types (), [] and {} such that

() = []{} and {}[]

[] = (){} and {}()

{} = []() and ()[]

I don’t know what sorts of types map to.

 

One can consider +, -, +i and –i as four types as well and so on.

 

What is this useful for?

I was working on solving another problem and the search space for that was too large. I was looking for a way of reducing the search space and for compactly representing this search operation when I realized that I could express the problem like this.

 

The original problem was that I had a matrix like the one below. I could assign and + or negative sign to any variable such that the matrix when multiplied by its transpose would generate the identity matrix. (The transpose of a matrix is the matrix you get when you flip it along its diagonal).

a b c d

b a d c

c d a b

d c b a

 

Then I had to solve the problem for the larger 8x8 version of the same matrix –

a b c d e f g h

b a d c f e h g

c d a b g h e f

d c b a h g f e

e f g h a b c d

f e h g b a d c

g h e f c d a b

h g f e d c b a

 

These matrices are generated as a consequence of simple XOR order, that can be easily expressed by the following ruby program –

syms = %w(a b c d e f g h i j k l m n o p q r s t)

v = 8

v.times{|m|

      v.times{|n|

            printf("%s ", syms[n^m])

      }

      puts ""

}

 

The fact is that I had to solve the problem for matrices of any dimension that is a power of two and I couldn’t see any pattern that would help me automagically generate the signs for matrices of higher dimensions.

 

So I though about how to search the space of all possible sign assignment and then realised that I can group elements into groups of four such that each group would have 4 variables and would be of type (). As an example here is the expression in FooGroup algebra which when solved would give all the solutions possible.

(r1c0,r1c1,r0c0,r0c1)(r1c2,r1c3,r0c2,r0c3)(r2c0,r2c2,r0c0,r0c2)(r2c1,r2c3,r0c1,r0c3)(r2c0,r2c3,r1c0,r1c3)(r2c1,r2c2,r1c1,r1c2)(r3c0,r3c3,r0c0,r0c3)(r3c1,r3c2,r0c1,r0c2)(r3c0,r3c2,r1c0,r1c2)(r3c1,r3c3,r1c1,r1c3)(r3c0,r3c1,r2c0,r2c1)(r3c2,r3c3,r2c2,r2c3)

Where r0c1 is the symbol for the sign that should be given to element at row 0 column 1. (I further go on to fix my first row to be all positive numbers. )

 

Finally, if you are interested I have a .Net library to solve expressions in the algebra. I also have a ruby program that generates C# programs which get the library to solve the above matrix problem.  The build command takes as parameter the dimensions of the matrix that you wish to solve (this should be a power of 2).

Download FooGroup Algebra and the Matrix Solver

 

Running the solver on a 4x4 matrix generates 16 solutions. 2048 solutions for a 8x8 matrix.

Solving :(r1c0 r1c1)(r1c2 r1c3)(r2c0 r2c2)(r2c1 r2c3)(r1c0 r1c3 r2c0 r2c3)(r1c1 r1c2 r2c1 r2c2)(r3c0 r3c3)(r3c1 r3c2)(r1c0 r1c2 r3c0 r3c2)(r1c1 r1c3 r3c1 r3c3)(r2c0 r2c1 r3c0 r3c1)(r2c2 r2c3 r3c2 r3c3)

Solution 1 : (r1c1)(r1c3)(r2c2)(r2c1)[r2c3](r2c1)(r3c3)[r3c1](r3c2)[r3c1][r3c1](r3c2)[r1c0][r1c2][r2c0][r3c0]

Solution 2 : (r1c1)(r1c3)(r2c2)(r2c1)[r2c3](r2c1)[r3c3](r3c1)[r3c2](r3c1)(r3c1)[r3c2][r1c0][r1c2][r2c0](r3c0)

Solution 3 : (r1c1)(r1c3)[r2c2][r2c1](r2c3)[r2c1](r3c3)[r3c1](r3c2)[r3c1][r3c1](r3c2)[r1c0][r1c2](r2c0)[r3c0]

Solution 4 : (r1c1)(r1c3)[r2c2][r2c1](r2c3)[r2c1][r3c3](r3c1)[r3c2](r3c1)(r3c1)[r3c2][r1c0][r1c2](r2c0)(r3c0)

Solution 5 : (r1c1)[r1c3](r2c2)[r2c1](r2c3)[r2c1](r3c3)(r3c1)[r3c2](r3c1)(r3c1)[r3c2][r1c0](r1c2)[r2c0][r3c0]

Solution 6 : (r1c1)[r1c3](r2c2)[r2c1](r2c3)[r2c1][r3c3][r3c1](r3c2)[r3c1][r3c1](r3c2)[r1c0](r1c2)[r2c0](r3c0)

Solution 7 : (r1c1)[r1c3][r2c2](r2c1)[r2c3](r2c1)(r3c3)(r3c1)[r3c2](r3c1)(r3c1)[r3c2][r1c0](r1c2)(r2c0)[r3c0]

Solution 8 : (r1c1)[r1c3][r2c2](r2c1)[r2c3](r2c1)[r3c3][r3c1](r3c2)[r3c1][r3c1](r3c2)[r1c0](r1c2)(r2c0)(r3c0)

Solution 9 : [r1c1](r1c3)(r2c2)[r2c1](r2c3)[r2c1](r3c3)(r3c1)[r3c2](r3c1)(r3c1)[r3c2](r1c0)[r1c2][r2c0][r3c0]

Solution 10 : [r1c1](r1c3)(r2c2)[r2c1](r2c3)[r2c1][r3c3][r3c1](r3c2)[r3c1][r3c1](r3c2)(r1c0)[r1c2][r2c0](r3c0)

Solution 11 : [r1c1](r1c3)[r2c2](r2c1)[r2c3](r2c1)(r3c3)(r3c1)[r3c2](r3c1)(r3c1)[r3c2](r1c0)[r1c2](r2c0)[r3c0]

Solution 12 : [r1c1](r1c3)[r2c2](r2c1)[r2c3](r2c1)[r3c3][r3c1](r3c2)[r3c1][r3c1](r3c2)(r1c0)[r1c2](r2c0)(r3c0)

Solution 13 : [r1c1][r1c3](r2c2)(r2c1)[r2c3](r2c1)(r3c3)[r3c1](r3c2)[r3c1][r3c1](r3c2)(r1c0)(r1c2)[r2c0][r3c0]

Solution 14 : [r1c1][r1c3](r2c2)(r2c1)[r2c3](r2c1)[r3c3](r3c1)[r3c2](r3c1)(r3c1)[r3c2](r1c0)(r1c2)[r2c0](r3c0)

Solution 15 : [r1c1][r1c3][r2c2][r2c1](r2c3)[r2c1](r3c3)[r3c1](r3c2)[r3c1][r3c1](r3c2)(r1c0)(r1c2)(r2c0)[r3c0]

Solution 16 : [r1c1][r1c3][r2c2][r2c1](r2c3)[r2c1][r3c3](r3c1)[r3c2](r3c1)(r3c1)[r3c2](r1c0)(r1c2)(r2c0)(r3c0)

 

This article is relevant in the context of

Search for Yield the Magnificent

Yielding to Magnificence

 

Other relevant articles include:

Iterators that listen (for Python, by Sidharth Kuruvila)

Implementing a generator in Ruby (by Sidharth Kuruvila)

Implementation of Iterators in C# 2.0

 

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

 

 

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?

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

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

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.

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).

I just finished reading Erik Meijer and Peter Drayton’s work-in-progress paper on programming languages and type systems. The paper as correctly noted in the beginning is written-to-provoke and I think this line of work is required today when technologies like .Net and the JVM have opened up possibilities of experimenting with languages and language systems and potentially reduced barriers for acceptance of new languages. The value proposition the expressiveness of a new language provides can be more readily accepted today in frameworks like .Net where a programmers existing knowledge/use of an API and an existing code base will not be lost by switching over to the new language.

 

The paper touches a large variety of topics and is more in brain dump of thoughts around the general area of type systems in dynamic and static languages. They also have some very interesting pointers and references.

 

The papers discusses type inference, programming by contract as opposed to having the type system as the only means of contract, subtyping and potentially expressing subtyping as programming by contract, type-directed lifting in Cw and how that can be used as opposed to non-intuitive reflective code.

 

The paper talks mentions the SqlDataReader – even if you don’t grok anything else in the paper, try and understand this part and try and see the need to a better programming language model – especially if you have ever worked on the data tier or business logic tier of an n-tier data centric application.

 

The paper also mentions lazy evaluation and about potentially deprecating the need for using eval if you have a better system in place for most of the common uses of eval.

 

On the whole it’s a paper that worth your time if you have started thinking about why when using C++ its so damn hard to get anything right, why C# cant be a little more flexible when handling collections, XML like or SQL like data and why languages like your pet python or ruby don’t make the mainstream.

 

http://pico.vub.ac.be/~wdmeuter/RDL04/papers/Meijer.pdf

For a long time I have been using this little program misnamed netshortcut. It’s a little command line that pops when you press a key-combination; commands that it supports are configured into a rules file using a rudimentary declarative language that evolved ‘as-appropriate’. Read more about it here

http://www.thinkingms.com/pensieve/homepage/work/netshortcut/netshortcut.htm

 

While I had been using NS for a while, there was this growing frustration that it could be made to do more things – if it had a better designed language underlying it. This frustration continued for a long time, until sometime early last year I got to working it out. I had lots of help from Sid, against whom I would bounce the creations of my genius.

 

Today the notebook in which we had worked out our plans resurfaced after a year. I didn’t want to loose this stuff again, though it was going to be an embarrassment for the future – and hence this blog entry.

 

I remember Sid saying that is some south american there are a sort of monkeys that have really long tails that hang down branches when they sit. And I say “so?”. And he says ‘So maybe you can use that idea in your language’. I ponder that for a while and then figure that I won’t be so useful. I hindsight, maybe Sid was right after all…

 

So here is the language, in wonderfully non formal description -

 

<pattern> {

      do ( <args> ) { <code> }

      is { <value> }

 

      comment <string>

 

      def <ident> {

            render <password | list | text>

            include <filename>

            alias <pattern> <name>

            code { <code> }

            <one or more pattern blocks>

           

}

}

 

That’s it. All programs have to begin in some scope, so this language’s global scope is same as the scope that corresponding to the inside of an def <ident> { <this is the global scope> }.

 

Remember that this language is fundamentally declarative is used primarily as metdata for a command line. The standing idea was the code blocks inside do() {} and is {} would be handled by a regular programming language that allowed interpreter hosting – the idea was to go with ruby then.

 

There is also the notion that braces can be eliminated except for do and is blocks. If a var does not have a do or is block is its value is simple returned back up the tree.

 

Here is a definition for supporting invoking the browser to do a google search. The user at the NS command line would type something like this –

gg <what to search for>

 

Imagine we have a file called library.rb that has

def browser(url)

      # invoke browser with specified url

end

def urlEncode(value)

      #return a urlEncoded version of value

end

 

This will be the NS rules file –

 

include “library.rb”

 

gg {

       do (arg ) { browser(“www.google.com?q=#{arg}”) }

       comment “Search Google”

       def arg {

              * {

                     is { urlEncode(value) }

              }

}

}

 

Note that ‘value’ that is passed to the urlEncode() is a special variable that holds the value of the current match (* matches to anything).

 

Now this does look a little clunky (and yes unintuitive) but with the defaults and with some braces reduction it would look like this –

 

include “library.rb”

 

gg do(arg){ browser(“www.google.com?q=#{urlEncode(arg)}”) } comment “Search Google”

 

Neat?

 

The language actually allows for a LOT of flexibility for controlling what gets executed for what the user types, what comments are displayed, how the UI gets rendered etc. I cant really describel all of that here, but this is the essence -

-          The lowest do() {} block that is satisfied is executed wrt a command.

-          The is{} block at any level computes a value that may serve as a argument value to a do block higher up the tree.

-          The code {} blocks are executed in pre-order (when going down the tree)

-          The do(){} and is{} blocks are executed in post-order after the command is completed.

-          Any {} other than for do, is and code can be skipped. Doing so reduces the rest of the line to the scope of the starting instruction’s block.

 

The new NS is also to support a notion of setting scope. You use

@ <rest of command here>

to set scope. For example, if you are going to be doing a lot of google searches, you do a

@ gg

And from that point on whatever you type at the command line will the value of the arg parameter of the do(){} of the gg pattern.

 

I have not really go down to implementing this yet.

Someday…

Refers:

Part 1 - The weekend ‘Scheme’ compiler in C#

Part 2 - Compiling Scheme style function dispatch to IL

 

This is fun. I added variable argument support. So everything is of type void foo(object[] args) now.

 

Effectively I can have the full set of lambda signatures -

(lambda () <code>)

(lambda (a) <code>)

(lambda (a b) <code>)

(lambda a <code>)

(lambda (a . b) <code>)

 

Lambda’s now have a preamble that maps formal parameters and does arity checking. In the cases of lambda’s I populate I create one local variable each to represent each parameter. When there is a variable number of arguments I create a scheme list out of the section of the object[] and assign the list to the local variable.

 

I hope all this is consistent with scheme.

 

Download

Refers:

Part1 - The weekend ‘Scheme’ compiler in C#

 

The compiler as of now does not do functions with variable arguments. In scheme functions like + can take any number of arguments.

 

Function Definition and Variables

You right a function – more correctly a lambda in scheme like this (lambda <arguments> <code>) and you bind it to a variable like so

(define foo (lambda <args> <code>))

 

Effectively foo is a variable that can hold any type – at this point of time it is bound to the lambda. The way I represent this in the compiler is by creating foo to be of type object and then assigning to it a delegate instance which will invoke the function generated corresponding to the lambda.

 

The equivalent of

object lambda1(<args>)

{

}

delegate object call_lambda1(<args>);

 

object foo = new call_delegate1(lambda1);

 

This means that every function call via foo, basically causes a type cast from object to the corresponding delegate type and then an invocation via indirection. This is certainly slower than direct function calls, but this is atleast a close enough mapping to the semantics of scheme.

 

Function Dispatch

Looking at the above its easy to see that I will need delegates types of various arities and function dispatch will happen accordingly. So when compiling

(foo 1 2)

I know that foo is some value that is of delegate type that will take two arguments. I don’t really have to know the function that its bound, I just need a guarantee of the arity of the function and then I can invoke it.

 

The above call will get compiled to the following in IL

ldsfld     object Program::foo

castclass  [SchemeLibs]SchemeLibs.call2

ldc.i4     0x1

box        [mscorlib]System.Int32

ldc.i4     0x2

box        [mscorlib]System.Int32

callvirt   instance object [SchemeLibs]SchemeLibs.call2::Invoke(object, object)

- where call2 is a predefined delegate that takes two parameters.

 

Problems with variable argument dispatch

The problem with functions with variable arguments is this. When the compiler sees (foo 1 2)

what can it conclude about the arity of the function? With variable arguments, it can only say that foo is a delegate that points to function that requires not more that 2 mandatory arguments.

 

But that’s not too good in the IL world because the opcodes that you need to call functions with variable arguments are different from the opcodes that take a fixed count of arguments.

 

In the clr world there are two approaches to passing variable arguments to functions that I am aware of.

 

params array

Firstly what C# officially does which is

void foo(params object[] args)

{

      foreach(object arg in args)

      {

      }

}

 

foo(1, 2, 3, 4);

 

If you look at this in IL the compiler basically creates an array in the caller, fills it with the arguments and then calls the function with an array as the parameter.

 

arglist

The second approach - unofficially what C# does is the real way of supporting variable arguments at the CIL level using the IL instruction arglist. Here is an example from Vijay Mukhi’s book on IL –

.method public hidebysig static vararg void abc(int32 i) il managed

{

       .locals (value class [mscorlib]System.ArgIterator V_0)

       ldloca.s   V_0

       //create the arglist object

       arglist

       call       instance void [mscorlib]System.ArgIterator::.ctor

(value class [mscorlib]System.RuntimeArgumentHandle)

       br.s       IL_001d

       //get one argument at a time

       IL_000b:  ldloca.s   V_0

       call       instance typedref [mscorlib]System.ArgIterator::GetNextArg()

       refanyval  [mscorlib]System.Int32

       //do something with the value here

       ldind.i4

       call       void [mscorlib]System.Console::WriteLine(int32)

       //get the next ones index

       IL_001d:  ldloca.s   V_0

       call       instance int32 [mscorlib]System.ArgIterator::GetRemainingCount()

       ldc.i4.0

       bgt.s IL_000b

       ret

}

 

This does have an equivalent in C# via an undocumented (yes!! <insert swear word here>) keyword called __arglist. For more on this take a look at Vijay Mukhi’s discussion on Arrays and Undocumented C# Types and Keywords by Peter Bromberg (a C# MVP).

 

If you look at both of these, you see that the code generator of the compiler has to be able to look at the call (foo 1 2) and determine what instruction to generate. There is really no way I can determine the runtime type of foo. (Yes there are optimization possible in certain limited cases, but in a general sense no).

 

This has me thinking that the only way to solve the problem might be to always treat all function calls as calls with variable arguments. Yes, I know that’s bad. So now function dispatch will have to go through the overhead of

-          type casting a an object to delegate type

-          create a data structure for the variable arguments (for both the params and arglist case)

-          call indirectly via a delegate

 

I am tempted to go with params instead of arglist for implementing variable arguments for a bunch of reasons. Both create some sort of GC managed list structure for extra parameters. Its just that params has a more logical mapping in the C# world – so it would be easier to implement some library functions in C# that take only one argument of the form object[].

 

If you have a better idea about how to do function dispatch that accommodates for variable arguments, let me know.

 

 

This blog isn’t dead, it just smells that way. Actually, we have been having trouble with our ISP – something configuration has changed that causes the worker process in which context out web-application runs, to not have write permissions to the web folder where the entries and comments are stored. So that means that I cannot make blog entries and no one cane post comments. We need to have this sorted out or move to another ISP real quick. For now my solution is to generate the blog entry xml file on my local computer and upload it via ftp. That’s how you are seeing this entry.

 

Now to the real topic of this post - I have been toying around with Scheme for some time now – I would like to say a long time – but considering how long scheme has been around (as opposed to say C#), my time is not that long.

 

Over the weekend (literally) I have made for myself a compiler that compiles a language that has a lot of braces. I would really like to say that it is scheme – it is not – but it is very scheme-like. Why it is not scheme -

-          It is a subset of the language

-          It has some differences in semantics even in the subset that I managed to implement

 

Sometime last Thursday I watched a 90 minute video that shows how one can write a Scheme to C compiler. Sidharth originally pointed me to this. Well, I didn’t watch all 90 minutes – shortly after the 60^th minute or so I jumped up all charged up, ready to write a scheme compiler.

 

What the video showed me is how to solve some hard problems in scheme compilation – basically how get rid of closures and continuations. The video shows you how to do a closure conversion and CPS conversion. Those very two issues about scheme compilation that I had nagging for sometime – watching the video took them away.

 

This is the subset of scheme that I implemented so far. It has support for lambda, define, if and lists. In terms of library which is in C# and is extensible and I have +, =, car, cdr, cons, display, remainder, newline etc.

 

So effectively I can compile code like this

(define print (lambda (s)

      (display "Value is ")

      (display s)

      (newline)))

 

(define gcd (lambda (a b)

      (if (= b 0)

            a

            (gcd b (remainder a b)))))

 

(print (gcd 50 70))

 

and compile it to generate a .Net exe that actually runs :)

 

This has been really good fun and a rather creative thinking exercise. I currently plan to take it forward and implement a few more things I am curious about. Its good fun to see what code like this does to your thinking about things.

 

Right now the code flow of the compiler is structured like this –

Scanner -> Parser -> [Abstract Syntax Tree] -> Code generator -> exe

 

The once I have a stable code generator, I am expecting that instead of focusing on being able to compile every construct in scheme, I can translate constructs down into the simpler constructs which the code generator already handles.

 

For example I don’t intend to compile a ‘cond’ statement – instead I would take the AST that has the ‘cond’ and transform it into an AST which can the ‘cond’ replaced with a nested ‘if’. Similar closure conversion and CPS conversion (continuation passing style conversion) would be other AST transforms.

 

So the code flow would be like this –

Scanner -> Parser -> [AST] -> AST Transforms -> [AST] -> Code generator -> exe

 

Once I have the present code a little stabilized and I have a framework for doing tree transforms, I should have a fairly complete implementation of a scheme like language.

 

 

Things I cant solve -  

Why I say scheme-like language is because I doubt if I will ever actually implement a whole standards compliant system – simply for the sheer effort. That aside I presently don’t know enough to be able to compile some aspects of the language.

 

In scheme not many things have special status. As an example variable name is simply a binding to some value.

 

So I can say -

(define x (lambda (a) (+ a 10)))

which binds variable x to a lambda (a function) that takes a parameter and adds 10 to it and returns it.

 

Now I can call it and assign the result to another variable ‘a’ -

(define a (x 10))

 

Now in the same program I can define x to be something else, say just a number…

So typing of variables go for a toss. Similarly I cannot really hardcode any function calls in the generated code – I have to indirect them through a variable that holds a delegate, because at runtime I cannot really know which function that variable is bound to. But those are solvable problems.

 

The hard problem comes up when you deal with what scheme calls special forms. As an example ‘if’ is a special form.

(if (= a b) (display a) (display b))

Here either value of ‘a’ is displayed, or value of b is displayed.

Now it is not possible to implement ‘if’ using a function call. Because whenever you call a function, all the arguments to the function are fully evaluated. So if there was a function called ‘if’ the condition, then and else parts would be evaluated before the ‘if’ function is called. So in this case the user would see both ‘a’ and ‘b’ being displayed. So ‘if’ has to be treated differently by the compiler and I have to generate test and branch instructions for the ‘if’.

 

The problem comes in the fact that the user can perfectly well say something like this –

(define if 10)

So from now on ‘if’ is 10.. that’s crazy because that’s a runtime condition, whereas my compiler has already generated test/branch code for the if.

 

When writing a compiler and I see ‘if’ I emit intermediate code which tests a condition and braches to the right code block for execution. If at runtime the meaning of the ‘if’ itself changes then the branching and compile time generated code has no meaning.

 

You may argue that in the case of ‘if’, I can solve the problem by having variable that indicates the current value of ‘if’ and at compile time I can generate code for an additional check with this variable. However that’s a limited hack… and it doesn’t explain what I will do when at runtime the meaning of ‘define’ changes or the meaning of ‘lambda’ changes.

 

I cant solve this problem right now, I don’t know how to – so I have given define, lambda and if a special ‘keyword’ like status – similar to keywords in other languages where keywords cannot be redefined to mean something else at runtime.

I don’t know if this is a problem I will be solving also.

 

Things I hope I can implement

-          closures

-          continuations

-          more special forms (list, quote)

-          a better function dispatch mechanism (generate the delegates types)

-          tail calls

-          cond, let, letrec

 

Here is my early ‘over-the-weekend’ quality scheme compiler for download. Use with caution.

This also requires the elusive .Net 2.0. I am not releasing source just yet, but it will come.

 

However, if you are looking for an actual full fledged compiler scheme compiler for .Net GotDotNet lists the following -

Scheme	Northwestern University Hotdog Scheme
Scheme	Tachy (Scheme-like) language
Scheme	Indiana University Scheme.NET

You may have more luck with these.

 

You may not be able to leave comments on my blog right now.

Do send me mail for now roshan -dot- james -at- gmail -dot- com.

 

The little public information about Vulcan –

 

MSR-TR-2001-50

Vulcan: Binary transformation in a distributed environment

Andrew Edwards; Amitabh Srivastava; Hoi Vo

April 2001

http://research.microsoft.com/research/pubs/view.aspx?type=Technical%20Report&id=455

 

Over the months I had slowly lost touch with Scheme, with so much happening in life. Today I saw some scheme code again and somehow just looking at it made me happy. Some kind of inherent simplicity in seeing those brackets and that indentation style – something vague familiarity of old friendship. It was weird.

 

No no, I am not cracking up and I am still a good old pure imperative languages programmer at heart and yes (Small talk guys please stand to the corner), I believe that C++ is a OO language and I still like .Net and C#. But all said and done, I think I like scheme – need to get back to some old scheming as soon as time allows.

 

Digressing - been musing about dynamic languages a bit more. The real reason I have not been writing too much about it is because of the feeling that I am going to sound stupid because I don’t know enough. I think I am going to let go of that and take the risk of looking foolish for a bit and start writing down things as I go ahead.

 

Here is a bunch of things that could/would fall under the general umbrella of the lose term – dynamic languages –

1)       closures

2)       iterators

3)       coroutines

4)       continuations

5)       mutable types

6)       typeless variables

7)       dynamic method dispatch

8)       eval

 

I don’t want to get into method dispatch and sub-classing mechanisms here, but I think the above is a general list. Any biggies I have missed? Lets see if there are any appropriate mappings we can find in the CLR and such.

 

The iterators and closures are solved problems – or atleast are largely solved problems in C# 2.0 (yes I know we can’t do ref variables – I think that’s ok for now – I will be happy if you have an answer)

 

There are solutions to most of the others lying around in one way or the other in Jim’s IronPython and the lesser loved Jscript.Net compiler that ships in source form with Rotor.

 

Does anyone know where I can find a readable description of how a scheme compiler (not interpreter) would work?

Dynamic Languages on the CLR – Part 1

 

Today I came across a paper written in 1996 at MIT that spoke of Dynamic Languages implementation on the JVM. The paper is an interesting read and pleasant because it isn’t dotted with arcane notational jing-bang and actually talks about real implementation issues.

 

The paper is written by Olin Shivers of MIT, interesting person – ha ha, actually this is the real link.

 

The first section address the issues of optimization of small scalar data types like integers which cannot actually afford to have dynamic lookup. The solution he proposes entails an assumption to be imposed on pointer types – so that small values can be held immediately rather than via indirection. For this purpose he recommends the addition of a type called an ImmediateDescriptor. I could not help smiling because this seems so much like a solved problem in the CLR of today – value types.

 

The second big issue that the paper brings is one of custom operations that a particular language may require that the runtime may not support. I don’t really have an answer for this. The paper goes onto compare this as being the inherent contradiction between RISC and CISC systems and adds the angle of safety of the end programming construct. This is by far a brilliant piece of thinking and these are the two suggestions primarily

1)       Build it up in API

2)       Enable the VM to have an extendable instruction set – similar to micrcodes in a processor

a.       Enable compilability of such new instructions by compiling to a lower level more RISC instruction set than the high level instruction set of the runtime…

 

I am hoping to offset this second part by not affording extensibility in the runtime and instead believing in some magical set of primitives. I don’t know about work that is actually being planned by the CLR team in this regard, I wonder what they are planning.

It has been on my mind for a long time, to write about this – supporting dynamic languages on the most advanced runtime on the planet. I have been having this pet project on the back of my mind, and figured that I should probably write about it now. I was wondering how hard it would be to extend the CLR in a fundamental way to support dynamic languages – the idea here is not to add a whole bloat of features to the CLR, but to try and identify a set of primitive or simple rules/abstractions which when added to the CLR would enable implementation of dynamic languages efficiently on the CLR.

 

Why the CLR? Because the CLR is one of the fastest runtimes/VMs out there; it was inherently designed to run multiple languages; runs on a whole bunch of hardware and software platforms and has a very wide acceptance in the industry; it is an open standard that is not owned by any company; and there are atleast two publicly available implementations in source form – which means that it enables a language that previously had to lug along its own VM/interpreter to boldly go where no previous version has gone before.

 

Some smart languages like Groovy are doing this with the JVM. I was hoping for a while that Ruby would – but it turns out, after several mails on the Ruby mailing list that Matz the creator of Ruby, has other plans. Matz is writing his own VM for Ruby.

 

It looks like it’s a season for writing multi-language runtimes – head of the pack being Parrot, the new VM for Perl 6. There is of date, little or no information available about the actual architecture of Rite – ruby’s VM that Matz is working on.

 

What makes a runtime that supports dynamic languages different from runtimes that are built to support statically typed OO languages – I don’t have enough of a formal education or personal experience to answer that straight out. That is one of the things that I hope to teach myself in coming time. I can throw terms like dynamic method dispatch at you… but essentially I don’t know if I can nail it down to a set of fundamental primitives that make all the difference.

 

This is a blog entry about some of my early ramblings on the topic. I am hoping to teach myself some of the difference by looking at the opcode design for Parrot. I am expecting that there would be opcodes for runtime type lookup, runtime method invocation etc etc – does that solve the problem, I don’t know. It provides features that can be used to mitigate the problem, yes. In conjunction with studying the architecture of Parrot, I am hoping to compare and contrast that with what the CLR supports and see what is missing in the CLR. Again I am not expecting much to be missing – what I am expecting to be seeing be seeing is that a lot of what Parrot provides as opcodes, the CLR would not natively provide, but would instead be available as framework API.

 

There is another source – Jim Hugunin’s IronPython. Sometime early this year Jim Hugunin shocked the Python community and a large part of the dynamic languages world by implementing a python version that ran on the CLR – it was faster that the classical C Python. Jim previously was known for his Jython – a Python that ran on the JVM – but was a rather slow implementation. What Jim has essentially done is that he has written a bunch of libraries to augment what the framework provides and has used these liberally along with regular IL. Jim now works for the CLR team at Microsoft.

 

Once I think I have an understanding of how the Parrot opcodes makes it a better runtime for dynamic languages, looking at Jims work (which is openly available) should give me a good idea of what primitives can be derived and can be pushed into the CLR. That should be a good fun project to work on.

 

A lot of what I have typed would be plain common sense for someone who was actually following the field. A whole bunch of things are getting in the way of getting started, else I would have already.

I have been putting more of my free time into digesting Scheme. I am now working on XEmacs. After several stops and starts with emacs in the past, I am finally using it (might I add - productively) to write scheme code. I figured that even if emacs is of no use to me for most of my work, I could atleast use it to write scheme code. It should be good for that for sure.

 

Don’t misunderstand me when I say this, because you may have different opinion, especially if you have lived in Unix for a long time – which I haven’t. XEmacs still leaves me feeling like I am taking piano classes. I use Scite and Visual Studio for most of my day to day work.  Of course, if I am writing a document, then it is Word. I also have a love-hate relationship with Rob Pike’s Sam editor.

 

For a long time I used the old Turbo C++ IDE in DOS (yes I am not ashamed to confess) and it served me rather well. After which it was Visual Studio 5... it was a pain to use in some cases, but with this plug-in called ‘Whole Tomato’ that I used, it was a killer.

 

When I got started on Linux, editing was a real pain – it was like I had to learn to type all over again. That was major put-off. As a matter of fact I figured that I could not suffer the ‘miserable’ editors they have there and so decided to write my own editor. (Yes, I was crazy enough to try and write an editor instead of learning arcane key combinations…) Of course, since I could edit code on Linux, I decided to write my editor in a portable way in DOS and then figure out how to take it to Linux.

 

As most DOS code was written those days, I wrote interesting text mode menu libraries and such other things that assumed that I had access to VGA text buffer to access. Finally when I actually had something going, I decided to make the big switch – Prot to Linux. Almost immediately, I hit a blank wall.

 

The entire style of programming, with direct access to video memory that was used to write large Text-UI based apps on DOS, was simply non-existent in Linux. That, I still remember, was such a major put off that I was going around cursing Linux to anyone who would listen to me. The only alternatives that I was left with, was to use some editors that did old Word-Star like CTRL-K based key combinations, which was rather irritating. I also spent half a day looking at the ncurses lib that time, hoping for a way out. All I got was buggy behavior and one buggy lib after the other and numerous dependencies on some .so or the other which I had to go and find on the net .

 

Finally my entire work on the editor on Linux got scratched and I decided to turn it into a DOS only thing – which I used for much after that as file viewer. The thing was distributed as w.exe to my friends and the default config file used to display multicolor menu and the title “The Zen Masters Workbench”. In w.exe was viewer that could be given C like structures and could read data out of binary files to match the structures. That became the original basis for the implementation of my DDL language.

 

 

 

I don’t know why I typed all that down… anyway here is the little bit of scheme code that implements a for-loop as a macro. I know it is not much, but its good fun.

 

(require (lib "defmacro.ss"))

 

(define-macro for

  (lambda (init  cond  step  code)

    (let ((loop (gensym)))

      `(let ,loop ,init

             (if ,cond

                 (begin

                   ,code

                   (,loop ,step)))))))

 

;see nested for loops

(for ((i 1)) (< i 10) (+ i 1)

     (begin

       (for ((j i)) (< j 10) (+ j 1)

                (begin

                  (display i)

                  (display j)

                  (display " ")))

       (newline)))

 

Of course, written entirely in xemacs. One reason to use xemacs over Scite is that it gives me this really nice syntax driven indentation. The syntax high-lighting, for what I have seen, is pretty corny though. But on the whole, good enough to write scheme code for now.

 

If you are starting out on Scheme and already know how to program, I recommend Dorai Sitaram’s “Teach Yourself Scheme in Fixnum Days” as a starter. The SICP is a lovely text as well and full of ideas, but if you don’t have lots or free time on your hands and are not the sort who likes letting an idea go without giving it its due thought, then I wouldn’t recommend SICP. It will be a while before you get down to scheme-ing. Also Prof Kent Dybvig’s book on Scheme is good, but again if you are the impatient sort, the DS book is the better choice.

 

In a few weeks I should get my copy of the Little Schemer, I intend to be ready for it by then