Roger Alsing Weblog

MyLisp is now named DSLisp - Domain Specific (Language) Lisp.

I have published it as a project on CodePlex:
http://www.codeplex.com/DSLisp

The new name imples the purpose of the project.
To act as a host for DSL’s.

The idea is to compile your DSL into the DSLisp AST.
And then run your DSL inside the DSLisp engine.
By doing this you can very easily add single step debugging and breakpoint support to your DSL. 

See the codeplex site for more info.

Today I stumbled across the weirdest thing.

I was comparing the performance of MyLisp to L# and MyLisp was terribly slow in comparison.
(Running the exact same Fibonacci code)

So I checked the code of L# and they seem to do pretty much the same as I do, quite similar design and code.

The only thing I could find was that I evaluated the first arg twice when calling Add, Sub,Mul and Div.
So I changed the code for those functions so that all args are evaluated only once.
And suddenly the performance was increased by some 1000 times or so, things that took a bout a minute before now completes in less than 0.1 sec.
I would get it if performance was increased about 2 times, but not like this.
The only thing I can think of is that the original code did some bugged recursive evaluation of some sort.

Well, I’m happy about the performance gain, but a bit annoyed that I can’t find the reason why the old code was so much slower.

Updated source code (C# 3) can be downloaded at:
http://www.puzzleframework.com/roger/mylisp.zip

[Edit. oh dear god I'm so stupid..]

Two minutes after I published this post I found the cause.
I even wrote the reason in this post..
I evaluated the first arg in Add, Sub, Mul, Div twice.
And the Fib code looks like this:

(= fibonacci (fn (n)
   (if (< n 2) n
      (+ (fibonacci (- n 1)) (fibonacci (- n 2))))))
;;;         ^ problem is right there...

The first arg of the last Add call is a recursive call to itself..
I feel so dumb now..
Well I guess the best way to find the cause of a problem is to try to describe it for someone else. 

In this case it was pretty much like that IQ test where you should count the letter ”F”’s in an english text where most people don’t count the “F” in “of”.

I was only looking at the (- n 1) and (-n 2) parts of the code..
Not seeing that I was also adding the result of recursive function calls.

I’ve added multi threading support to MyLisp today.

The earlier implementation of the callstack was not up to the task, so I had to rewrite it completely.
The new callstack is based on stack frames which can hold local symbols.

So behold! , the first multi threaded application in MyLisp

(func FooBar ()
  (
    (let i 0
      (for i 0 1000000
        (print (format "thread {0}" i)))))) 

(= thread (new-thread FooBar))
(call thread Start)
(for i 0 1000000
  (print (format "main {0}" i)))

Sure , the “new-thread” function is a bit of cheating, I dont have any generic code for .NET delegate <-> MyLisp delegate yet.
So I have to use hard coded methods to cast from and to delegates for now.

OK, this was not much of a real post, more of a “yay, it works!” shout

My Lisp now supports Lazy evaluation.

I’ve made it possible to define per function if it should use lazy or eager evaluation.
(The next step will be to decide that through code analysis.)

For those who don’t know what lazy evaluation is about, the purpose of lazy evaluation is to avoiding unnecessary calculations.

Take the following example (in C#)

public static void FooBar ()
{
  int res = GetSomeValue();        
  //pass the value to a logger
  Logger.Log ("value of GetSomeValue was:" , res);
}          

public static int GetSomeValue()
{
 //some realy heavy algorithm here
 ... heavy code ...
 ... more heavy code ...  
 return res;
}           

... logger code ...           

public void Log (string message,params object[] args)
{
 //lets assume we can attach multiple providers to our logger
 foreach (LogProvider provider in LogProviders)
 {
  provider.WriteString(message,args);
 }
}

In this case, we would always need to execute “GetSomeValue” first in order to call our logger.
EVEN if there is no provider attached to the logger.
So, even if we don’t want to write anything to disc or DB or anywhere, we would still have to call “GetSomeValue”.

It is ofcourse possible to add special code to your consumer , “if (logger.Providers.Count == 0) then ignore…”.
But that forces you to add responsibility to your code that isn’t supposed to be there.
My FooBar method should not have to care about the number of log providers etc.

Lazy evaluation can solve this for us.
By applying Lazy evaluation to ”GetSomeValue” method, we would only need to call the method once the result of it is used.
Sounds odd?
How can you use the result before the code have executed?

It’s quite simple, its done through delegates, we can even do this in C# by passing delegates around.
However, you do have to know that you are passing delegates and not simple values, so it is not very implicit in C#.

In My Lisp, the code would look something like this:

(func FooBar ()
    (
        (= res (GetSomeValue))
        (call logger log "value of GetSomeValue was:" res)))     

(lazy-func GetSomeValue ()
    (
         ... heavy code ...
         ... more heavy code ...
        (return res)))     

...logger...     

(func Log (message data)
    (
        (foreach provider Providers     

            ;;; GetSomeValue will be called here
            (call provider WriteString message data))))

As you see, there is no special code to handle the lazy evaluation.
The only thing that I need to do was define “GetSomeValue” as a lazy function.

So if we do not have any log providers attached to our logger, “GetSomeValue” will never be executed, since its result is never needed.

And if there are providers attached, “GetSomeValue” will be executed from within the foreach loop inside the logger.
(Once, then caching its value)

Pretty slick IMO.

I just got home from a conference with my new job, a little bit tipsy and couldn’t sleep.
So I decided to add some new features to my Lisp clone.

I’ve made it possible to set operator priority for functions.
Eg.

(operator-priority + 1)
(operator-priority - 1)
(operator-priority * 2)
(operator-priority / 2)

This will make the engine scan every list that does not start with a function for operators.
The engine will enter a loop that search for the operator with the highest priority and replace the operator together with the left and right argument with a new list where the operator is the first arg (a function call).
The process will be repeated untill no operators are found.

So a statement like:

(let a ((1 + 10) * 3 / 5 - 1))

Will be turned into:

(let a (-(/(*(+ 1 10) 3) 5) 1))

Which is a normal Lisp expression that can be evaluated.

Well, thats it for now, I’d better get some sleep now.

 [Edit]

Update:

Ok, I’ve decided to change this a little bit.
The syntax will be:

(# 1 + 2 * 3 / 4)

And # will be a function that takes the rest of the formula as args.
Thus, not breaking any Lisp rules or syntax.

Remeber kids,
Don’t drink and develop…

I’m still working on my Lisp language clone.
Today I started to add debugging support to it.
I made the AST aware of the original source code, so each node can reference back to the place it was parsed from, and I also added a bit of call stack features.

I’m pretty satisfied with it so far, it almost feels like a real language now

Anyway, here is a screenshot of the not so well designed GUI.

 
Click for full size.

Downloads are available at: 

Source: http://www.puzzleframework.com/roger/mylisp.zip
Binaries: http://www.puzzleframework.com/roger/mylispbin.zip

(The code is written in C#3, VS.NET 2008 solution)