Optimizing MyLisp


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.

Lisp Debugger


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.

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

Lisp weekend


I’ve been reading up a bit on functional programming the last few week, the reason is just to comprehend the new features and possibilities in .NET 3.5 as much as possible.

Anyway, I got a bit carried away and started to read about Lisp, and decided to learn what it’s all about.
So what better way to learn a language than to make your own parser for it is there? ;-)

I started to hammer away on a simple parser, and once the parser was done, I couldn’t stop, so I began writing an engine too.
So after a few hours of Aha moments, I finally got my very own Lisp(ish) code executor and a bit more understanding for the language. ;-)

Well, enough blabbering, here are a few samples of whats currently possible in my still un-named language.

Hello world:

(print 'Hello world!')

Simple function and call:

(defun Mul (x y) 
 (* x y))       

(print (Mul 2 3))

Variables:

(let my-var 'hello lisp') 
(let my-int 123) 
(let my-double 123.456) 
(let half-pi (/ pi 2)) 
(let my-arr (arr 1 2 3 4 5 6 7))

Loops:

(foreach item my-arr 
 (print item))      

(for i 1 20 
 (print i))      

(let i 0) 
(while (< i 20) 
 ((print i) (++ i)))

Lambdas:

(let my-lambda (lambda (x y) (* x y))) 
(my-lambda 2 3)

Delegates:

(let my-delegate Mul) // delegate to Mul 
(let print other-print-func) //redirect the print function to "other-print-func"

Objects:

(let form (new Form)) 
(set form Text 'hello windows forms') 
(let button (new Button)) 
(set button Text 'my button') 
(set-event button Click MyButtonClick) 
(list-add (get form Controls) button) 
(call form Show)

List comprehensions:

(foreach item (select (lambda (concat 'transformed: ' item '!')) 
              (where (lambda (> (get item Length) 3)) 
              (list 'foo' 'bar' 'roger' '.net' 'lisp')))       

      (print item))

The next step will be to make it possible to define your own classes.
Im thinking of emitting true .NET classes and let the methods redirect the calls to the engine.
Thus making it possible to redefine the behaviour of a method in runtime.

That, and find some reason to use it :-P