April 7nth: Update: Clip.1.10 is posted here. See below.

April 8th: Update: Clip.1.11 is posted here. See below.

I finally scratched a long standing itch and wrote this tool. I don't understand why I didn't do this a few years back.

Clip lets you interact with the Windows clipboard from the command line. Of course, you need to do this only if you are a heavy command line user.

Clip lets you copy/move/delete files in the clipboard from the command line; you can copy and paste files between cmd shell windows and between the cmd shell and windows explorer. You can also dump clipboard data on the console (redirect it to files, if you choose) and pipe data into the clipboard. It also lets you examine various clipboard formats and such. The clip command t2f is rather handy for situations where you have a list of file names (as cut/copied text) in the clipboard and you want to perform actual file operations on them.

Finally, Vista apparently comes with a clip.exe that does very little. It might be lying in your path before my clip.exe is. Fix it by (1) renaming one of these programs OR (2) putting this program's dir before system32 in the PATH. I did the later.

Clip v1.11 - A Clipboard tool for the Command Line
March 2009 (c) Roshan James

Usage:
  clip <cmd sequence>

Commands:
formats - Lists data formats currently available in the Clipboard
text    - If the clipboard has text, display it
clear   - Clears clipboard
in      - Copies stdin to clipboard as text
put <text> - Puts text into clipboard.

flist   - List files in clipboard (uses "FileDrop" format)
fcopy   - Copy files in clipboard to current dir
fmove   - Move files in clipboard to current dir
fdelete - Delete files in clipboard to current dir
faction <cmd> - Executes the specified command as the action.
          Possible use: delegate file copy to robocopy.
files <wildcard> - Extends (uniquely) the file list in the clipboard.
cut     - Sets the shell action for files to 'cut'
copy    - Sets the shell action for files to 'copy'
paste,drop - Executes the current shell action, like a shell 'paste'.

display <format name>
        - Displays clipboard data (if possible). Format names are those
          listed by "formats" command. Use doubles quotes if format
          names have spaces

t2f     - Text to Files: takes the current text data in the clipboard and
          converts it into a list of filenames for pasting. Each text line
          is treated as a file path.

Ex: Copy file contents to clipboard.
> type test.text | clip in

Ex: Copy clipboard contents to file.
> clip text > test.txt

Ex: Put *.txt files in clipboard.
> clip files *.txt

Ex: Cuts *.txt files into the clipboard.
> clip files *.txt cut

Further, clip commands are executed in sequence. Hence we have:
Ex: Copy txt files from all subdirs to current dir.
> dir *.txt /s/b | clip in t2f fcopy

Ex: Convert clipboard content to plain text.
> clip text | clip in

Send me bugs, typos, suggestions.

Clip is written in C# and has been tested on Windows Vista; it may/should run on other windows versions where the right version of the .Net framework is installed - the 2008 version - whatever it is called. All the file operations assume a certain semantics for the "FileDrop" format of the clipboard - this could very well change between windows versions, so if you have a different windows and file operations don't work, let me know. Clip is free for use; use it at your own risk - I am not responsible for any damage caused.

April 7nth: Update: Cut, Copy, Paste...

Clip has been upgraded to version 1.10. The new commands include cut, copy and paste. "Clip files *.txt" acts like a select operation where files are added to the clipboard without specifying a shell behavior when pasting happens. On pasting the shell reverts to its default action, which is "copy". The newly added cut and copy commands lets one specify the shell action. Hence "clip files *.txt cut" will place the txt files into the clipboard with a cut action associated with them. Simply executing "clip copy" or "clip cut" will change the action for the files currently in the clipboard. The paste command acts like a shell paste - it will copy or cut/move depending on what the current action is.

April 8th: Update: Adding "Copy Path to Clipboard" in the "Send To" context menu.

Clip has a new command called put. "clip put hello" will put the string hello into the clipboard. This is handy in several instances. One of which is motivated by Jean Pierre Daviau's comment below. We can add a "Send To" shortcut in explorer to copy any file's path. Go to an explorer window and type "shell:sendto" in the address bar.

This should display a list of shortcuts that are in the default "Send To" menu. Create a new shortcut there to clip.exe and give it a nice nice name such as "Send Path to Clipboard" and then edit the shortcut to have the command line argument "put" as well.

We are done. As a consequence we can right click on a file and now do:

The above instructions are for the Vista shell.It should be easy to find the equivalent for XP as well.

 

Download Clip Binary

Download Clip Sources

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?

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.

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

Today over dinner Will Byrd mentioned the Collatz function to Michael Adams and me. The Collatz function is a simple little function that on receiving any natural number seems to always terminate with the result 1. However the strange thing is that no one has been able to prove this property of the function. As a matter of fact one rather famous mathematician is quoted to have said that mathematics isn’t ready to prove the Collatz conjecture and such problems.

 

So what is Collatz function?

 

collatz :: Integer -> Integer

collatz 1 = 1

collatz n | n `mod` 2 == 0 = collatz (n `div` 2)

collatz n                  = collatz (3 * n + 1)

 

Let me translate that into a C* style syntax:

 

int collatz(int n)

{

      if(n == 1)

            return n;

      else if (n % 2 == 0)

            return collatz(n/2);

      else

            return collatz(n*3+1);

}

 

Here is a wikipedia page about it:

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

 

If you look at it hard enough certain patterns emerge and we took some shots at what a proof might entail. In summary its sufficient to say that we didn’t get very far. The interesting consequence though is that enough information about the nature of the function emerged that we were able to create another one:

 

Hence is our new function that we call collatz’ (read as collatz-prime)

 

collatz' :: Integer -> Integer

collatz' 1 = 1

collatz' n | n `mod` 3 == 0 = collatz' (n `div` 3)

collatz' n | n `mod` 3 == 1 = collatz' (4 * n - 1)

collatz' n                  = collatz' (4 * n + 1)

 

Cute?

Later in the evening I found this one which I call collatz’’ (read collatz-double-prime)

 

collatz'' :: Integer -> Integer

collatz'' 1 = 1

collatz'' n | n `mod` 5 == 0 = collatz'' (n `div` 5)

collatz'' n | n `mod` 5 == 1 = collatz'' (6 * n + 4)

collatz'' n | n `mod` 5 == 2 = collatz'' (6 * n + 3)

collatz'' n | n `mod` 5 == 3 = collatz'' (6 * n + 2)

collatz'' n                  = collatz'' (6 * n + 1)

 

Like the original collatz function, both collatz’ and collatz’’ seem to terminate on all inputs with the result 1. Again there is no proof that it will do so. I have (at the time of this writing) verified termination of both of these till for all numbers 1 to100,000.

 

Here is a little verifier:

 

verify :: (Integer -> Integer) -> Int -> Bool

verify f n = foldl isOne True (map f (take n [1..]))

    where

    isOne :: Bool -> Integer -> Bool

    isOne b x = (x == 1) && b

 

 

verify collatz’ 100000 returns True.

 

Here is collatz in Scheme:

 

(define C

   (lambda (n)

     (cond

       ((zero? (sub1 n)) 1)

       ((even? n) (C (quotient n 2)))

       (else (C (+ 1 (* 3 n)))))))

 

And Collatz’

 

(define C

   (lambda (n)

     (cond

       ((= n 1) 1)

       ((= 0 (modulo n 3)) (C (quotient n 3)))

       ((= 1 (modulo n 3)) (C (- (* n 4) 1)))

       (else (C (+ (* n 4) 1))))))

 

Here is a good time to make a potential conjecture: Is it true that there are infinitely many such functions?

 

Updated

 

For a long time I thought that Roman numerals were the worst counting system out there, until I got down to thinking about Microsoft Excel’s column naming convention. The last time I thought about Excel I wasn’t satisfied with the solution I had – the last time was at Applibase with Sid.

 

So what do I mean? You know the way columns are numbered in excel they go A, B, C.. till Z and then become AA, AB, AC … AZ, BA, BB, BC … BZ, CA, CB… etc. You get the idea I guess. So in some sense its fair to imagine that you can think of these as representing numbers.

 

So can you write a mapping from natural numbers to excel-numbers and vice versa?

 

Lets look at look at the problem in a reduced sense and see what we get – lets consider only A, B and C. Therefore we could count as follows – A, B, C, AA, AB, AC, BA, BB, BC, CA, CB, CC, AAA, AAB, AAC etc.

 

Lets write these down with their natural numbers next to them –

 

1 : A

2 : B

3 : C

4 : AA

5 : AB

6 : AC

7 : BA

8 : BB

9 : BC

10 : CA

11 : CB

12 : CC

13 : AAA

14 : AAB

 

Can you write a function that takes a number and returns the corresponding excel number? Its not as easy as you think. The reverse, ie, taking an excel number and producing a natural number out of it is easier, conceptually.

 

If you think about it enough you will realize that unlike many number systems out there this one is different because it does not have a zero character – hence you can’t express things like A00.

I don’t think I have a good enough solution yet. My current solution still checks if a value is 0 and if so does something otherwise does something else. I would like to write a solution in a clearly recursive fashion such that the only condition-check I do is to terminate the recursion. Think about how you convert a number from natural numbers to a base 2 representation for example – you can write this recursively and you only need a check to terminate your recursion. Here I need checks for other things. I guess in some sense what I am complaining about is that my number to excel-number conversion is not “mathematical” enough.

 

Anyway, here is solution as a piece of Haskell code – it’s a spoiler so don’t look at it until you have tried to solve it yourself. (Set base to 26 to get full A to Z numbering).

 

base = 3

 

ch :: Integer -> Char

ch n = intToDigit ((digitToInt 'a') + (fromInteger n) - 1)

 

num :: Char -> Integer

num c = toInteger $ (digitToInt c) - (digitToInt 'a') + 1

 

mdiv m n | m `mod`n == 0 = m `div` n - 1

mdiv m n = m `div` n

 

mmod m n | m `mod` n == 0 = n

mmod m n = m `mod` n

 

excel2int :: String -> Integer

excel2int s = excel2int' s 0

    where

    excel2int' (c:[]) r = r * base + (num c)

    excel2int' (c:cs) r = excel2int' cs  (r * base + (num c))

 

 

int2excel :: Integer -> String

int2excel n | n <= base = [(ch n)]

int2excel n = (int2excel (mdiv n base)) ++ [ch (mmod n base)]

 

Update

Here is a very clean solution, courtesy of Abhijit Mahabal who pointed it out in a couple of minutes. He even stated a proof and went on to show how you can do this with logarithms…

 

i2e n | n < 3 = [ch (n+1)]

i2e n = i2e (n `div` 3 - 1) ++ [ch ((n `mod` 3) + 1)]

 

The following solution (that I disagree with in spirit) is by Kyle Ross. It looks rather cute for some values of cute –

 

i2e = (gen !!) . pred

 

xs <+> ys = [x ++ y | x <- xs, y <- ys]

gen = base ++ (gen <+> base)

         where base = ["a", "b", "c"]

 

 

Write the following into a text file:

 

A -> B;

B -> C;

C -> A;

A -> D;

D -> C;

C -> B;

 

And then run the following ruby script with the text file as a command line parameter:

 

require "win32ole"

 

def load(fn)

      s = File.new(fn).readlines().join ""

end

 

 

gr = WIN32OLE.new "WinGraphviz.DOT"

s = "digraph G {#{load(ARGV[0])}}"

 

png = gr.ToPNG(s)

png.Save("#{ARGV[0]}.png")

 

And then you get the following PNG file:

 

 

Interesting?

 

I recently needed to draw a graph (as in connected graph – in graph theory…) and looked around a bit. I came across the Graphviz library developed by the old AT&T. There is a port of the libaray available for windows and it can be downloaded from:

http://www.graphviz.org/

 

Graphviz or rather, WinGraphviz is available as a COM component which is registered by the installer. So instead of getting my hands dirty with C++,I decided to take the COM bindings in ruby for a walk.

 

This is where the ruby code comes – it creates an object of WinGraphviz.DOT component and uses it to create a graph. Notice how I can interact with a COM object as though it were a regular Ruby object – fun fun.

 

As for the language in the text file – Graphviz graphs can be specified using a language (you can find a spec on their website). The A-> B etc at the beginning of the blog post was simply a subset of this language.

 

Of course if your data is in some other format, you will have to translate it into the graph language – but then again if its in an excel file or something you can just use Ruby to talk to excel COM component and read the data out and then talk to the Graphviz component.

 

 

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.

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

 

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?

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

Now that I am at home I needed to start cataloging my data and getting things in order before I move on. I spent some time yesterday writing a small app to help catalog my CDs. I had a look around but most CD cataloging apps I could find were paid apps.

 

 

CdScan scans the CDs and lets you do a simple substring search (a little like the old Winamp J option) and also gives you an explorer kind of view of your CDs.

 

Its got a nifty little auto-scan option where you can simply set it to autoscan and keep changing CDs in your drive.

 

There are a whole host of features I can think of adding, but you might want to grab hold of it and use it to catalog your Cds and maybe add a feature or two (since I am giving away source code).

 

Download Binary: cdscan_binary.zip (250.75 KB)

Download Source Code: cdscan_source.zip (268.43 KB)

This is written using .Net 2.0 Beta 2, so you need at least the Beta2 runtime to get the binary to work.

 

Here are a lot of things I can think of adding, maybe you can add them for me –

-          wildcard and regex based searching

-          a more flexible explorer view

-          save more data for an item (EXIF data, Thumbnails, Text index)

-          more intuitive UI, with some helpful text messages…

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.

 

I recently had some C# code that that had to be made localizable. Most articles about localization/internationalization that you find on the web would talk about how nice Visual Studio is for code internationalization and would show nice examples of how many ways the forms-designer would extract code out into a resx file. I am perfectly ok with studio doing all the work for you. However there are very often, strings in your actual code that studio does not externalize to resx files.

 

Strings.rb is a ruby script that will parse your C# code base and identify literal string definitions in the code base and will move them to your resx file. The code was hacked up to fill out a personal need so your mileage on this may vary. The tool certainly isn’t fool proof and there are certain cases that it doesn’t handle too well. If you are however on the smart-scripter side of things then you may find it useful.

 

The script needs to be setup for your specific project. Once done you can run it several times on your code base and it can incrementally catch strings and externalize them for you. This is handy to have while your code is still undergoing changes so new strings can be identified as they pop up and can be moved out.

 

Getting Started

 

Downloads

1) First thing download the script (strings.rb) and put it in your project folder.

 

2) Download and install ruby from here – http://rubyforge.org/frs/?group_id=167, its about 12mb and the installation happens in a snap.

 

3) Download an install REXML library for XML handling in Ruby from here –

http://www.germane-software.com/archives/rexml_3.1.2.zip

http://www.germane-software.com/software/rexml/docs/tutorial.html

 

 

Patching Strings.rb for your project

1) You need to patch the script file to have the correct path to your resx file and the path to your wrapper class that will be used to read strings from your resx file.

 

Open the script file in a text editor. (If you have ruby installed you should find this editor called scite in the ruby installation folder – that’s a nice editor. Alternately you might want to try installing scite - http://scintilla.sourceforge.net/SciTEDownload.html - about 600k).

 

In your project identify your resx file. It will usually be in Properties\Resources.resx.

Change the following line the rb file to reflect the path path to your resx file.

strings.rb:4:$resx_fn = "properties/Resources.resx"

(The actual line number might change a bit)

 

2) Now create a new class in your project called Strings. VS should typically create an empty class definition file that looks like this.

 

#region Using directives

 

using System;

using System.Collections.Generic;

using System.Text;

 

#endregion

 

namespace <Some Namespace>

{

    public class Strings

    {

 

 

    }

}

 

Patch the file with the following additions

- Add a using directive for your ‘Properties’ namespace.

- Add a comment that stays //start and one that says //stop. These ad as delimiters between with the script will generate the string definitions.

 

 

#region Using directives

 

using System;

using System.Collections.Generic;

using System.Text;

using <Some namespace>.Properties;

 

#endregion

 

namespace <Some Namespace>

{

    public class Strings

    {

 

//start

//stop

 

    }

}

 

3) This is the wrapper class into which the script will generate string definitions. You need to patch the script with the path to this class file. Basically patch this line –

strings.rb:5:$stringsclass_fn = "helper/Strings.cs"

 

Done

If you have got this far then your installation is done and you are ready to go.

For sake of completeness let me just list out things again –

1) download the script and put it into the project folder

2) install ruby

3) install the REXML library for Ruby

4) patch the script with the path to the resx file of the project

5) create a empty Strings class and add the namespace directive and comment markers to it

6) patch the script to have the correct path to your Strings.cs file.

 

What does the script do?

The script does a few basic things.

1) it parses your *.cs files in all subdirectories and looks for strings.

2) when it finds a string a it prompts the user for an action

3) if it is a string that should be localized the user can provide a pseudonym for the string. On getting this name the script will -

            1) add the string and the name to the resx file

            2) add a property to the Strings class that will read the string from the rex file

            3) replace the string literal in the code with a call to the property.

 

Running the script

To run the script after all the previous setup, simply go to the command line and type strings.rb

 

Here is a sample run of the Strings.rb script

Let me take up a simple project and show you how the internationalization script works.

 

Here is a project that has only one Program.cs file –

#region Using directives

 

using System;

using System.Collections.Generic;

using System.Text;

 

#endregion

 

namespace ConsoleApplication1

{

    class Program

    {

        static void Main(string[] args)

        {

            string a = "hello world";

            string x = "skip this line";

            string b = "escape sequences  \n\r\t\\\"";

            string c = @"cant handle this one";

        }

    }

}

 

The resx file looks like this –

<?xml version="1.0" encoding="utf-8"?>

<root>

  <resheader name="resmimetype">

    <value>text/microsoft-resx</value>

  </resheader>

  <resheader name="version">

    <value>2.0</value>

  </resheader>

  <resheader name="reader">

    <value>System.Resources.ResXResourceReader, System.Windows.Forms, Version=2.0.3600.0, Culture=neutral, PublicKeyToken=b77a5c561934e089</value>

  </resheader>

  <resheader name="writer">

    <value>System.Resources.ResXResourceWriter, System.Windows.Forms, Version=2.0.3600.0, Culture=neutral, PublicKeyToken=b77a5c561934e089</value>

  </resheader>

</root>

(I have removed some unnecessary details from the original resx file here)

 

I created this Strings class –

#region Using directives

 

using System;

using System.Collections.Generic;

using System.Text;

using ConsoleApplication1.Properties;

 

#endregion

 

namespace ConsoleApplication1

{

    public class Strings

    {

 

//start

//stop

 

    }

}

 

This is what happens when you run the strings.rb script –

C:\work\vcsexpress\Sample1\Sample1>strings

Error reading skip data! continuing with no skip data.

HelloString = hello world

EscString = escape sequences  \n\n\t\\\"

Program.cs:0:n++#region Using directives

Program.cs:1:

Program.cs:2:using System;

Program.cs:3:using System.Collections.Generic;

Program.cs:4:using System.Text;

Program.cs:5:

Program.cs:6:#endregion

Program.cs:7:

Program.cs:8:namespace ConsoleApplication1

Program.cs:9:{

Program.cs:10:    class Program

Program.cs:11:    {

Program.cs:12:        static void Main(string[] args)

Program.cs:13:        {

Program.cs:14:            string a = "hello world";

"hello world">?

Help ----------

        =<name> = the string will be externalised as <name>

        sf = skip file : file will not processed on next run

        if = ignore file : file will be processed on next run

        sl = skip line : line will be processed on next run

        il = ignore line : line will be processed on next run (default)

        x, exit = exit script

        all skip information in stored in "skip_list.txt"

Program.cs:14:            string a = "hello world";

"hello world">=HelloString

            string a = Strings.HelloString;

Program.cs:15:            string x = "skip this line";

"skip this line">sl

Program.cs:16:            string b = "escape sequences  \n\r\t\\\"";

"escape sequences  \n\r\t\\\"">=EscString

            string b = Strings.EscString;

Program.cs:17:            string c = @"cant handle this one";

Program.cs:18:        }

Program.cs:19:    }

Program.cs:20:}

Writing Resource File "properties/Resources.resx" : done

Writing Strings class "Strings.cs" : done

Writing Skip data "skip_list.txt" : done

 

Effectively you can see the script run through the source file (actually it runs through all the cs files) and prompt you with each string. It also shows a little help on the actions possible.

 

To replace a string, you need to give it a name. Simply type =<name> and the string will get replaced.

 

If you don’t want to do anything about a particular line, type ‘sl’ for skip line and it will skip that line. It also adds the line to a file called skip_file.txt so that in subsequent runs of strings.rb it will not keep prompting you to patch the same line.

 

You can similarly choosing skip a file using the ‘sf’ option. You may typically want to skip the *.designer.cs files, the strings.cs file etc.

 

All skip information is human readable and is stored in a text file called skip_list.txt.

 

Strings.rb is deisgned to be run multiple times over the sample project through its development so that it can catch new strings as they appear in your code base, incrementally. The resx and strings.cs files are recreated at each run.

 

To show you the output of the process, this is what happened.

 

This is the new Program.cs file –

#region Using directives

 

using System;

using System.Collections.Generic;

using System.Text;

 

#endregion

 

namespace ConsoleApplication1

{

    class Program

    {

        static void Main(string[] args)

        {

            string a = Strings.HelloString;

            string x = "skip this line";

            string b = Strings.EscString;

            string c = @"cant handle this one";

        }

    }

}

 

This is the new resx file –

<?xml version="1.0"?>

<root>

  <resheader name="resmimetype">

    <value>text/microsoft-resx</value>

  </resheader>

  <resheader name="version">

    <value>2.0</value>

  </resheader>

  <resheader name="reader">

    <value>System.Resources.ResXResourceReader, System.Windows.Forms, Version=2.0.3600.0, Culture=neutral, PublicKeyToken=b77a5c561934e089</value>

  </resheader>

  <resheader name="writer">

    <value>System.Resources.ResXResourceWriter, System.Windows.Forms, Version=2.0.3600.0, Culture=neutral, PublicKeyToken=b77a5c561934e089</value>

  </resheader>

  <data name="HelloString">

    <value xml:space="preserve">hello world</value>

  </data>

  <data name="EscString">

    <value xml:space="preserve">escape sequences 

 

       \"</value>

  </data>

</root>

 

Notice that the two strings have appeared here.

 

And this is the new Strings.cs file –

#region Using directives

 

using System;

using System.Collections.Generic;

using System.Text;

using ConsoleApplication1.Properties;

 

#endregion

 

namespace ConsoleApplication1

{

    public class Strings

    {

 

//start

              // "escape sequences  \n\r\t\\\""

              public static string EscString { get { return Resources.ResourceManager.GetString("EscString"); } }

 

              // "hello world"

              public static string HelloString { get { return Resources.ResourceManager.GetString("HelloString"); } }

 

//stop

 

    }

}

 

Also, if you are interested in seeing the skip data, this is the skip_list.txt that got created –

Program.cs:::string x = "skip this line";

 

Limitations

1) The string matching that is done by the script is fairly limited. Basically it identifies strings in the the c# code by comparing with the following regex –

strings.rb:15:$string_pattern = /[^@]("(\\.|[^\\"])*")/

This does not cleanly cover all sorts of escape sequences that a string can have. It also does not support @””. But .. well… this covers large number of strings that you would face, so its good enough to get along. Also if you can get me a better pattern match, I would be happy.

 

The script iterates over all strings on a line of cs code using –

      line.scan($string_pattern).each {|str,e1|

            //str is the string

      }

 

 

2) The resx file tags that are generated by script are those that are valid for Visual C# Express Edition Beta 1 format. I don’t know if this resx format is valid for other versions of studio. I would expect that it is. Even if it is not, you can easily patch it for you version of studio. This is how –

 

The resx file has a tag added for each string definition that looks like this –

  <data name="HelloString">

    <value xml:space="preserve">Hello world</value>

  </data>

 

If your studio generates tags like this, then you are ok. If you are not just patch the following block of ruby code to generate your tags. It’s fairly easy –

            el = doc.root.add_element "data"

            el.add_attribute("name", key)

            val = el.add_element("value")

            val.add_attribute("xml:space","preserve")

            val.text = remove_esc_seq($map[key])

This is part of the writeresx() function.

 

3) The escape sequence handling in the script is a hack – its funny – it’s limited. It’s actually a little sad:

def add_esc_seq(str)

       str.gsub("\\", "<double_back_slash>").gsub("\"", "\\\"").gsub("\n", "\\n").gsub("\t", "\\t").gsub("\r", "\\r").gsub("<double_back_slash>", '\\\\\\')

end

 

def remove_esc_seq(str)

       str.gsub("\\\\","<back_slash>").gsub("\\n", "\n").gsub("\\t", "\t").gsub("\\r", "\r").gsub("\\\"", "\"").gsub("<back_slash>","\\")

end

 

These are however good enough for \r \n \t \\ \” etc.

 

4) The resx XML doesn’t look too nice. It works however. This is because the REXML library produces badly formatted XML. You can download the XML Pretty Printing program on mine and run it on the output resx file for pretty XML formatting.

 

5) “The setup is a little contrived and all this requires me to know ruby programming “

If you actually said that then this script is not for you. For the simple reason that this is something home-grown and not meant to be a polished product in any way. You don’t need to know ruby much to just get it working. You need to know ruby only if you need to extend it in non-obvious ways. Secondly the setup isn’t that contrived if you have been using ruby. You would, most likely, have most of the tools in place already.

 

Finally, Why Ruby?

My only real answer to the question is that I wanted to get the job done. For an example take a look at the engine code and peaceful separation that it gives me from the prompt/ui code.  

 

That’s it. So if you are geeky enough and consider it below your dignity to get down to doing a menial job of looking through source files and copying out strings to the resx files – then this script might help you.

 

Download Strings.rb

 

Ps. It’s a lot of effort documenting any ruby program that is more that 200 lines. It just does too many things.