Monday, June 12, 2006
  Rotor 2.0 

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

Monday, June 12, 2006 12:22:49 PM (Eastern Standard Time, UTC-05:00)  #    Comments [1]  | 
 Wednesday, June 07, 2006

 

A romance with musicals which started with Jesus Christ Super Star a few years back, is coming back. JCSS was brilliant – amazing music, amazing lyrics, very interesting characters – a very interesting shift of perspective. Very cool. I remember watching JCSS completely for the first time at Deepak’s place back at Bangalore – at one of our many of dinner + music sessions where Deepak would treat us to the pleasures of the local vegetarian home delivery service and his beautiful taste in music.

 

If you have not watched JCSS, it is highly recommended –

http://www.imdb.com/title/tt0275434/

 

 

Since coming to Cambridge I have had a chance to sample many interesting things – vintage wines, abstract mathematical models such as pi calculus and category theory, involved pieces of software such as the Glasgow Haskell Compiler, programming paradigms such as STM and monadic yield, London, beautiful medieval cathedrals, beer festivals etc and some musicals.

 

Its the musicals that this entry is about. A few weeks I got to watch Rigoletto the opera – a live performance at the “Cambridge Corn Exchange”. I had originally expecting nothing – only by the mild curiosity that the brochure was and also intending to sample the often heard “stiff upper lip” British formal occasion.

 

What I saw were a lot nicely dressed older people who were very polite and very at-ease. Rigoletto was in Italian with English subtitles displayed on a screen above the stage. As I watched Rigoletto, minor details like there actually nude women on the stage got swept aside and the power of music and metaphors started to take over. I started not to notice the gasps from the audience about the directness of presentation and more on what would be going through these characters in the play, if it was all real.

 

After I left the opera, one of the last pieces “La donna e mobile” played in my mind for days afterwards. This is an English approximation of “La donna e mobile”

 

Woman is unpredictable, like a feather in the wind,

she changes her voice, and her thoughts

Always a sweet, pretty face,

in tears or in laughter, always lying

Woman is unpredictable, like a feather in the wind,

she changes her voice, and her thoughts

and her thoughts, and her thoughts

 

Always miserable, he that trusts in her

who confides in her, his unwary heart!

Yet nobody feels fully happy

who on that bosom doesn't drink love,

Woman is unpredictable, like a feather in the wind,

she changes her voice, and her thoughts

and her thoughts, and her thoughts!

 

This is being sung by an overly licentious Duke who is about to be murdered by an assassin paid by the jester of the Duke’s court. The assassin’s sister who usually woos his victim’s for him such that he can stab them when they are distracted now pleads with him to spare the Duke’s life. The assassin consents on the condition that someone else should come through the door who he will murder instead of the Duke. The jester wanted the Duke killed because he had dishonored his daughter. The jester’s daughter however overhears the conversation between the assassin and his sister and decides to sacrifices herself to save the Duke, despite knowing that he had cheated her. As all this unfolds one can hear the Duke singing in his room awaiting his mistress for the night, the assassin’s sister. Its delicate and is one of those climaxes that’s not easy to forget.

 

Beautiful.

 

Two days back I saw the Phantom of the Opera – honestly I don’t have many ways to describe this other than that it sent me reeling ever so often. Its brilliant, its powerful and it is so exquisitely done. Its one of those things that one has to put on their “to do list before you die”. As you watch the Phantom of the Opera so many layers unfold. It one of those things that awoke many sleeping ghosts in my mind.

 

 

 

In sleep he sang to me,

In dreams he came,

That voice which calls to me,

And speaks my name.

And do I dream again?

For now I find.

The Phantom of the Opera is there-

Inside my mind.

 

This is the version I saw -

http://www.imdb.com/title/tt0293508/

 

Many tracks in the Phantom of the Opera hit you with the raw pathos comparable with Mukesh Chand Mathur (aka Mukesh) singing “Dost dost na raha” in Sangam or “Baharon Phool Barsao” of Mohammed Rafi in Suraj. Brilliant.

 

In short, I am hooked. Any suggestions for what I can watch next? I know that comparing with Verdi’s Rigoletto or Andrew Loyd Weber’s JCSS or Phantom of the Opera is a tall order – I don’t expect it to. I just want to sample some more real music.

Wednesday, June 07, 2006 5:41:07 PM (Eastern Standard Time, UTC-05:00)  #    Comments [0]  | 
 Monday, June 05, 2006

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.

 

Monday, June 05, 2006 4:42:30 PM (Eastern Standard Time, UTC-05:00)  #    Comments [0]  | 

Idea Foundry

 

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

 

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

 

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

 

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

 

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

 

The problem with computer science is that it’s a very very early science, so much so that many people in it don’t think of it as a science. They think of it more as an engineering discipline. Some refer to it as an art. I am more of the opinion that it is a science – the very early stages of a fundamental science about the nature of the universe and the reality of things in it. Computer science is a science of automata, a science of the nature of interaction of simple interacting components and the study of their behavior. Like all good scientists if you asked me for evidence that this was indeed the case, I must shy back. I don’t really have concrete evidence, but instead I must point in the direction of rice’s theorem, the curry-howard isomorphism, church-turing hypothesis, the pi calculus and say that I feel very strongly that this is the start of fundamental things.

 

 

Luton

 

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

 

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

 

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

 

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

 

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

 


 

Posted late, as usual.

Monday, June 05, 2006 4:27:10 AM (Eastern Standard Time, UTC-05:00)  #    Comments [0]  | 
 Monday, May 29, 2006

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

Tomorrow I visit MSR.

 

 

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

 

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

 

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

Monday, May 29, 2006 3:46:11 AM (Eastern Standard Time, UTC-05:00)  #    Comments [2]  | 
 Friday, May 05, 2006

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

 

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

 

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

 

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

 

 

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

 

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

 

 

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

 

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

 

The Little Machines

 

Thats all for now. More when time allows.

 

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

Friday, May 05, 2006 12:01:15 AM (Eastern Standard Time, UTC-05:00)  #    Comments [0]  | 
 Saturday, April 29, 2006

 

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

 

rebel_xt.jpg

 

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

 

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

 

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

 

Chicago1.jpg Chicago2.jpg Chicago3.jpg

 

 

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

 

Shedd1.jpg Shedd11.jpg Shedd10.jpg Shedd2.jpg Shedd3.jpg Shedd12.jpgShedd4.jpg Shedd5.jpg Shedd9.jpg Shedd6.jpg Shedd8.jpg Shedd7.jpg Shedd13.jpg Shedd14.jpg 

 

 cheers!

Saturday, April 29, 2006 2:45:54 PM (Eastern Standard Time, UTC-05:00)  #    Comments [0]  | 
 Friday, March 03, 2006

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

 

 

Friday, March 03, 2006 2:37:42 AM (Eastern Standard Time, UTC-05:00)  #    Comments [0]  |