Dynamo - FScheme Refactor Progress

I've been spending the past few weeks working on various improvements to FScheme, the core scripting engine of Dynamo. Originally I was focusing on performance, but I ended up adding a bunch of things to bring the language closer to actual Scheme. The core language is getting there, but the library is still missing a lot of what's in the R5RS Scheme standard.

What's FScheme?

Way back when Ian first created Dynamo, it used an event structure to notify nodes that their inputs have been evaluated. This was slow already, and the fact that it couldn't work inside of one Revit API transaction meant that each node had it's own transaction (something that present-day Dynamo does in Debug mode) meant that updates to Dynamo could take forever to propagate to Revit.

Starting in March of 2012, I began working on modifying the Dynamo engine so that the node interface could be converted to a Scheme-like expression which could then be evaluated, thus making Dynamo itself as full-featured a programming language as Scheme (in theory). In May, I committed these changes to GitHub.

FScheme began as a prototype in Python that I made in order to demonstrate that you can imperatively create Scheme expressions and then execute them. The idea is that the imperative interface could be wrapped by a GUI. I then set out to port the prototype to .NET so that it would be compatible with the Revit API and the existing Dynamo code. Originally, I was going to write the engine in C#, but after doing some research on tail call optimization in the language, I realized this wouldn't work. After doing a little more research, I came to the conclusion that F# would be the best candidate: it has full tail call optimization (even for x86) and it compiles to CLR code, meaning that it is not interpreted. The fact that F# code is callable from C# means that I could access this engine directly from the existing Dynamo code.

The problem with writing it in F# was that I didn't know anything about the language; the closest language to F# that I had used in the past was Haskell, and I had only used it briefly.  Fortunately, I found this great tutorial about writing a Scheme interpreter in F#, and--even better--the code was open source on GitHub. After doing some basic modifications to facilitate some features that Dynamo should support (with respect to performance and dynamic updating), I had a basic Scheme language that would be hidden to the end user behind Dynamo's UI.

So What's New?

It turns out that there were a ton of problems with the FScheme language outlined by the tutorial. The first problem was that lexical scope was broken and would prevent tail calls from being optimized properly. Macros were also first-class and evaluated at runtime, which on the one hand was cool because you can then pass macros as arguments just like you can pass functions, but it made writing library functions in F# a total headache. It also greatly messed up evaluating lists, since the evaluator made no distinction between a list data-structure and a syntax-list used for function calls.

After attempting to fix some of these things, I quickly realized that it would be simpler to rewrite the language from the ground up. So that's what I did. FScheme is now much closer to normal Scheme, except it retains the features I need for interoperability with Dynamo.

Unfortunately, a lot of these changes are not user-facing. Macros are now evaluated at compile-time, and so are no longer first class. Fortunately people don't usually pass if statements as arguments to functions, so this won't be missed. I also had to remove call/cc since nobody uses it and it was bogging down performance. Finally, I added a (simple) compiler that performs a bunch of optimizations and produces quick F# code.

For a basic benchmark, I ran the following expression in both the old FScheme implementation and the new one, and compared the execution times:

(begin (define counter (lambda (x) (if (<= x 0) x (counter (- x 1))))) (counter 1000000))

Avg. Old FScheme Execution Time: 5130ms

Avg. New FScheme Execution Time: 2539ms

Admittedly, this test only really benchmarks function call speed, but since that's the most common operation in FScheme, the fact that it runs over twice as fast is a significant accomplishment.

You can see all the new changes to the FScheme language in the fscheme-improvements branch on GitHub.