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…

As of 20 July 2004, I no longer work for Microsoft.

You are not going to be seeing any leaving Microsoft letters of the sort you may have seen from some ex-microsofties. I am going back to college. Over the years, I figured I don’t understand computer science very well. I figured I lack some fundamental things in my understanding of the way this science works. I love computer science and the only way I am going to be able to good enough to quit the field and probably go sell airplane rides for a living, is if I understand it better. So I am going to college.

I am joining Indiana University this fall for my Masters in Computer Science. I am navigating primarily by instinct right now, so I don’t have clear answers to ‘What next Rosh?’

I left Microsoft with very good opinions about the company. Easily the best company I worked for – for the quality of the work they do, for the quality of the people, for the culture and the spirit. I wish it was a much braver company with respect to taking risks, and boldly chasing after the next step in the everyday computing. I wish it leveraged its people better, I wish it was more about blood and genius and less about schedules and numbers. But it is easily better than most places that I have had the opportunity of knowing.

I am going to be thinking about a different class of problems for the next few years - problems about nature of computation, logic and mathematics.

The weekend I left Hyderabad I got to visit Golconda once more –

Golconda Fort, Hyderabad

I am now back at home, in beautiful Cochin –

Cruise boats at Marine drive, Cochin

After several months, and several ISPs, TMS is back up and stable. Which means that our blogs are live again.
Thanks Pandu

:)

"I am not sure I want to be perfect and finished. Talk about boredom..."
"Look at the sky," Don said.
"Well, it is always a perfect sky, Don."
"Are you telling me that even though it's changing every second, the sky is always a perfect sky?"

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

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

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

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

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

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

<pattern> {

      do ( <args> ) { <code> }

      is { <value> }

      comment <string>

      def <ident> {

            render <password | list | text>

            include <filename>

            alias <pattern> <name>

            code { <code> }

            <one or more pattern blocks>

}

}

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

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

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

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

gg <what to search for>

Imagine we have a file called library.rb that has

def browser(url)

      # invoke browser with specified url

end

def urlEncode(value)

      #return a urlEncoded version of value

end

This will be the NS rules file –

include “library.rb”

gg {

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

       comment “Search Google”

       def arg {

              * {

                     is { urlEncode(value) }

              }

}

}

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

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

include “library.rb”

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

Neat?

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

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

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

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

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

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

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

@ <rest of command here>

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

@ gg

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

I have not really go down to implementing this yet.

Someday…

Refers:

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

Part 2 - Compiling Scheme style function dispatch to IL

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

Effectively I can have the full set of lambda signatures -

(lambda () <code>)

(lambda (a) <code>)

(lambda (a b) <code>)

(lambda a <code>)

(lambda (a . b) <code>)

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

I hope all this is consistent with scheme.

Download

Refers:

Part1 - The weekend ‘Scheme’ compiler in C#

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

Function Definition and Variables

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

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

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

The equivalent of

object lambda1(<args>)

{

}

delegate object call_lambda1(<args>);

object foo = new call_delegate1(lambda1);

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

Function Dispatch

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

(foo 1 2)

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

The above call will get compiled to the following in IL

ldsfld     object Program::foo

castclass  [SchemeLibs]SchemeLibs.call2

ldc.i4     0x1

box        [mscorlib]System.Int32

ldc.i4     0x2

box        [mscorlib]System.Int32

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

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

Problems with variable argument dispatch

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

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

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

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

params array

Firstly what C# officially does which is

void foo(params object[] args)

{

      foreach(object arg in args)

      {

      }

}

foo(1, 2, 3, 4);

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

arglist

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

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

{

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

       ldloca.s   V_0

       //create the arglist object

       arglist

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

(value class [mscorlib]System.RuntimeArgumentHandle)

       br.s       IL_001d

       //get one argument at a time

       IL_000b:  ldloca.s   V_0

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

       refanyval  [mscorlib]System.Int32

       //do something with the value here

       ldind.i4

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

       //get the next ones index

       IL_001d:  ldloca.s   V_0

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

       ldc.i4.0

       bgt.s IL_000b

       ret

}

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

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

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

-          type casting a an object to delegate type

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

-          call indirectly via a delegate

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

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

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

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

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

-          It is a subset of the language

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

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

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

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

So effectively I can compile code like this

(define print (lambda (s)

      (display "Value is ")

      (display s)

      (newline)))

(define gcd (lambda (a b)

      (if (= b 0)

            a

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

(print (gcd 50 70))

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

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

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

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

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

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

So the code flow would be like this –

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

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

Things I cant solve -  

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

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

So I can say -

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

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

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

(define a (x 10))

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

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

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

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

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

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

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

(define if 10)

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

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

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

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

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

Things I hope I can implement

-          closures

-          continuations

-          more special forms (list, quote)

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

-          tail calls

-          cond, let, letrec

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

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

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

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.