I've read a lot of research papers over the years, but there I keep coming back to like Professor Dr. Michael Franz' doctoral dissertation: Code-Generation On-the-Fly: A Key to Portable Software (PDF).

I've been harping about Semantic Dictionary Encoding (SDE) ever since I first read the paper back in 1994, and got quite close to actually implementing at one point. So let me give a brief overview, since I can't drag it out often enough (someone take it mainstream, damn it!):

SDE is, at it's most basic, a compression mechanism for the intermediate representation of a compiler. Similiarly to Huffman coding, an SDE encoder and decoder pair both builds a dictionary of the datastream while building it and decoding it respectively. The dictionary entries is the used to encode/decode the following part of the data stream, which cause more entries to be added to the dictionary, etc., meaning that the later you are in the data stream, the more of the stream will refer to previously added dictionary entries instead of having to be all verbose and include the full definition.

But to call it just a compression method would be selling it very short. The appeal of SDE is that it can be used as a machine independent representation of a program, while at the same time it can (if used properly) retain far more semantic information about the program than a typical bytecode. Contrary to most bytecode, SDE retains the structure of the program as represented by the compiler.

This has a few very appealing properties beyond the nice parts of JIT (such as being able to target specific CPU versions):

• When (re)building the dictionary on decoding, you can store auxiliary information and even partway generated code, to speed up generation of subsequent pieces of code that use that dictionary element. The compression removes the need for pattern recognition - the pattern recognition was already done at encoding time. Franz' specifically tested outright code copying to speed up the code generation, where small pieces of code that was generated was tracked if it was invariant, in which case future uses of the same dictionary entry would lead to just copying the previously generated piece.
• You retain the ability to do JIT, but have high level flow information available, making it trivial to do things like sub-expression elimination and a number of similar "cheap" optimizations at JIT time based on knowledge available at runtime. The more you can defer generation and the more additional information becomes available before generation, the better you can do.
• The code generator can be modified to specifically recognize higher level dictionary elements that can be specifically optimized, while dictionary definitions for those elements can be provided that represents them in terms of lower level patterns. What that buy you is a backwards compatible way of improving performance that can provide significantly improved performance when running on systems or platforms for which the newest decoder is available, while still retaining full compatibility with the lowest common denominator - lowering the threshold for porting and for innovation.
• SDE retains the block structure and type information of the program, making it well suitable for highly dynamic languages (such as Ruby) that tend to either result in complex, bloated and slow bytecode or highly specialized, language specific VM's. With SDE, a highly specialized decoder can still exist, but by providing dictionary entries that act as templates for the specialized constructs of the language as part of the program, a generic decoder can still execute the program. The same benefits apply for more static languages, but it would appear to be more pronounced for dynamic languages where the final generated code can be far more effectively optimized once more information is known (i.e. in Ruby you can potentially do a far better job if you can JIT and cache specialized versions of code that take into account the actual layout of a class once all code that may reopen and extend/modify the class has been loaded - this doesn't really apply to languages where the structure of a class is known definitively at some point before the program is run).
• Because of the level of semantic information retained in the file format, SDE is not at odds with generating native binaries. Where a typical VM such as JVM's may or may not suffer a semantic disconnect with the destination architecture which means that a native binary generated from their bytecode might end up varying significantly from what a code generator would have generated with full knowledge of both the high level structure of the program and the target architecture, SDE doesn't have the same issue since very little of the semantics of the original program is lost in translation.

This means that a compiler can reasonably be split into a portable part outputting SDE binaries, and either a runtime SDE decoder/linker and/or a linker producing native code without loss of information. Such a native code generator can be run either prior to delivery of the code, or it can be run on installation, to be able to optimize for a specific CPU model, and can use more expensive optimizations than might be acceptable for runtime code generation.

• Instructions for tracing, additional safety (bound checking etc. in languages that don't require it) can be generated at code-generation time automatically. Thus you can support constructs that would slow down the final binary and only turn them on if needed. This can go as far as leaving in debug assertions and logging constructs that can be turned on at the command line, that need never even make it into the generated code if the appropriate switch isn't present, thus allowing extra capabilities to be included without burdening the system in normal use.

For programs where large parts of functionality is switched on or off from the command line, large parts of the program may just get discarded as a result of simple sub-expression elimination in the code generator, something which is particularly beneficial where the various parts cross-cut the same algorithm and substantial simplifications can be made.

Note that the some of the above is beyond the scope of the original dissertation, though all of it is hinted at or implied by the architecture.

One thing that may or may not be obvious from the above is that SDE, beyond efficiently encoding a tree version of the intermediate representation actually also turns the tree into a directed graph. Nodes further down in the tree get reused, linked the tree together at places where common sub-expressions are used.

Compared to a typical VM, SDE has one potential drawback in terms of delayed code generation, and that is that the dictionary can potentially grow quite large. This is ameliorated by scoping - by marking the start of a scope in the dictionary, and then throwing away any data generated specific to the local scope when reaching the end of the local scope the dictionary can be kept fairly compact.

Performance concerns?

Franz' addressed performance reasonably thoroughly, showing that SDE in most cases - on a mid 90's system based around a M68040 CPU running at 40MHz - performed very reasonable compared to loading native binaries. Franz' mused that CPU speed at the time was increasing faster than disk speeds, and that there is/was a very real possibility that this difference might be reversed so that SDE might eventually get faster. I don't know if that held up - it'd be interesting to redo those tests.

As for runtime performance, the paper contains a few benchmark tests against the then current MPW C implementation for Mac, and the tested Oberon code using SDE beat the corresponding C code hands down.

What's happened since?

Not much, unfortunately. Franz has continued work on various code generation methods, but Java came along around the same time and more or less monopolized interest the portability aspect. At least Mac Oberon had support for SDE, but as for much other great stuff coming out of the ETH computer science departments it was hampered by it's ties to Oberon, which fell out of favor together with Modula and Pascal type languages.

Franz' publications page is well worth a look - he's continuing to churn out great stuff.

My interest in SDE

I first got interested in SDE as a potential feature to contribute to a longwinded debate on comp.sys.amiga.misc back in '94 about writing an open source replacement for AmigaOS. It fell by the wayside (but one of the original people, Aaron Digulla has stuck with it, and AROS is probably the closest we today have to a real open source descendant of AmigaOS).

At various times I've wanted to resurrect my original attempts, but never have had the time.

This time? We'll see - I'm loosely thinking about looking at adding SDE support as one of the forthcoming steps for my series about writing a compiler in Ruby. I've learned a lot about compiler technology in the meantime, and I got quite far the first time - SDE isn't hard to do, anyway - so I'm hoping that I'll find the time to do a working implementation at some point in the not to far future.

_why is at it again...

I can't quite agree with myself if this is seriously demented or tremendously cool... (Yes, it's mostly only an idea, with only the barest hint of doing anything "useful", but anyway..)

This is the sixth in a series. Please start on part 1 first if you haven't already to get the background, or see here for the full series so far

Since we established last time that I'm going to blatantly steal stuff from Lisp, Scheme and friends (as well as from all over the place - I feel no need to be original with this project... Not until we're much further along, anyway), now is the right time to start introducing some more powerful concepts.

How about some deferred evaluation and anonymous functions?

Lambdas, or anonymous functions, can be passed around like values and called at your convenience (or not at all). Generally, they can access variables from the surrounding scope that gets "bound" to the function as an environment that allows it to pass state. That's a closure. What we're going to do this time is not going to bring full closure support, but it's the start, and we'll get to full closures down the road.

Let's be clear: As almost everything in programming languages, they are syntactic sugar. You can consider them equivalent to defining a class with a single method to call it and instance variables to be the environment, for example (or you can treat closures as a way of building an object system instead - a concept explored by Wouter van Oortmerssen who has been a hero of mine ever since I discovered Amiga E. If you're a programming language geek you need to take a look at the stuff Wouter has done over the years) - many concepts are reasonably orthogonal.

(As further digression, have you noticed a lot of people like me who are obsessed with programming languages that have this horrible tendency to nest sentence fragments and abuse punctuation to interject random thoughts all over the place, or is that just me?)

But instead of having to go to all that trouble, and litter your namespace with small functions, lambdas let you define them inline, and return a value representing the function instead of executing it.

For now, we'll add these constructs:

(lambda (args) body)
(call f (args))

The former will return the function - for now just the address - instead of executing the body. "call" will call the address passed with the arguments it's given, no surprise there.

So how does this differ from "real" closures?

The tricky part about real closures is that if you refer to variables from the surrounding scope, they are supposed to "stay live" for the next invocation. That is, they are meant to be kept around whenever you call the closure later on. It should be clear that returning just the address to the function isn't sufficient to achieve that. So let's look at one way of doing it, so you get an idea of the work involved (it's not huge, but not trivial either):

• We need to create an "environment", namely somewhere to store the variables that should survive past the lifetime of the function the closure is created in. This environment must exist on the heap, and each invocation of the function surrounding the lambda must result in a new environment.
• What is returned must allow you to access the environment. You can do this by creating an "object" and make the environment represent instance variables, or you can use a "thunk" - a small generated function that contains a pointer to the object and loads it into a predefined location before calling the anonymous function, or any number of other ways.
• You need to decide what variables go into the environment. This could be either "everything" accessible at the time of the execution of the "lambda" expression, or you could scan the expression body of the lambda and explicitly put only the ones used by one or more lambda expression in the function in the environment. The latter is potentially a lot more space efficient, but is slightly more work.

Ok, so for now just lets get the "anonymous function" in place. As usual I'll go through the changes step by step, but note that I've done some minor cleanups that are inconsequential to these changes as well, that I won't go through because they'll lust clutter things up.

The first piece is the code to handle the "lambda" expression:

  def compile_lambda args, body
    name = "lambda__#{@seq}"
    @seq += 1
    compile_defun(name, args,body)
    puts "\tmovl\t$#{name},%eax"
    return [:subexpr]
  end

Hopefully this is pretty self-explanatory. All it does is create a function name on the form lambda__[number] that we'll use to refer to the function, since we won't actually output it inline. Nothing really prevents us from spitting it out inline, but I find it messy, so for now anyway, I'll treat it as just another function. We then call compile_defun to generate just another named function - so it's only anonymous for the user. We then move the address of the function into %eax, which is where we've established the result of our subexpressions go. Note that this is yet another shortcut - eventually we'll need to do something more sophisticated to handle more complex expressions properly, but register allocation is a complex subject (and the alternative, to push everything onto the stack works but is slow).

Last we return [:subexpr] to indicate to the caller where/how to find the result of this expression.

Next we'll do some refactoring. You may have noticed that the inner loop of #compile_exp was getting ugly, handling different types of arguments. So we extract this:

  def compile_eval_arg arg
    atype, aparam = get_arg(arg)
    return "$.LC#{aparam}" if atype == :strconst
    return "$#{aparam}" if atype == :int
    return aparam.to_s if atype == :atom
    return "%eax"
  end

Notice the appearance of :atom, too. This allows us to take the address of C functions and pass them to :call. It was so simple to add, I figured why not. To go with that, we add this to #get_arg:

   return [:atom, a] if (a.is_a?(Symbol))

Next up, as part of the refactoring, :call falls out almost by itself:

  def compile_call func, args
    stack_adjustment = PTR_SIZE + (((args.length+0.5)*PTR_SIZE/(4.0*PTR_SIZE)).round) * (4*PTR_SIZE)
    puts "\tsubl\t$#{stack_adjustment}, %esp"
    args.each_with_index do |a,i|
      param = compile_eval_arg(a)
      puts "\tmovl\t#{param},#{i>0 ? i*4 : ""}(%esp)"
    end
    res = compile_eval_arg(func)
    res = "*%eax" if res == "%eax" # Ugly. Would be nicer to retain some knowledge of what "res" contains                            
    puts "\tcall\t#{res}"
    puts "\taddl\t$#{stack_adjustment}, %esp"
    return [:subexpr]
  end

This might look familiar. It's because it's the guts of #compile_exp, with #compile_eval_arg replacing some of the more ugly bits. The main other change is that it calls compile_eval_arg to get the function too, and does something weird to "%eax" - it prepends a "*".

Either you're confused now, or you might start seeing possibilities - both of doing nice things and of shooting yourself in the foot. The above is the equivalent of casting an arbitrary expression into a pointer and jumping to it with no validation. It makes it deliciously easy to cause a segfault by jumping to random addresses. It also, incidentally, makes things like a virtual pointer table for a class system trivially easy, and a number of other things. Safety will have to come later. As it turns out, the "*" is needed in front of indirect "call"'s.

So what does #compile_exp look like now? The obvious answer is "a hell of a lot cleaner":

 def compile_do(*exp)
    exp.each { |e| compile_exp(e) }
    return [:subexpr]
  end
  def compile_exp(exp)
    return if !exp || exp.size == 0
    return compile_do(*exp[1..-1]) if exp[0] == :do
    return compile_defun(*exp[1..-1]) if (exp[0] == :defun)
    return compile_ifelse(*exp[1..-1]) if (exp[0] == :if)
    return compile_lambda(*exp[1..-1]) if (exp[0] == :lambda)
    return compile_call(exp[1],exp[2]) if (exp[0] == :call)
    return compile_call(exp[0],exp[1..-1])
  end

Nice, isn't it? Compile_call, as it turns out does almost exactly the same as what the guts of compile_exp used to do, apart from what was farmed out to the other functions.

So we do a little test:

prog = [:do,
  [:call, [:lambda, [], [:puts, "Test"]], [] ]
]

(yeah, not exactly earth-shattering)

Compile and run:

$ ruby step6.rb >step6.s
$ make step6
cc    step6.s   -o step6
$ ./step6
Test

The full code for this step is here

Following parts

Since I combined three parts last time, here's an updated list of the remaining pre-written "just-in-need-of-cleanup" parts - I guess I better free up some time to write some new stuff soon, as I'm fairly sure I might end up combining a couple of the parts below when I get around to cleaning them up (such much for posting it as 30 parts...)

• Step 7: Revisiting loops with anonymous functions, accessing function arguments
• Step 8: Adding assignment and basic arithmetic
• Step 9: A cleaner "while" loop
• Step 10: Testing the language: Writing a simple text mangling program to make input cleaner
• Step 11: Refactoring the code generation and starting to abstract out the target architecture
• Step 12: Discussion of various concepts and future direction
• Step 13: Adding arrays
• Step 14: Local variables and multiple scopes
• Step 15: Accessing variable length arguments
• Step 16: Revisiting the text mangler - cleanups to test new functionality, and run it on itself
• Step 17: Identifying the constructs needed to self host the compiler
• Step 18: A start on a proper parser

"Everyone" that's geeky enough sooner or later at least toy with the idea of their own language (or like me write several half-assed toy compilers to test concepts - hopefully I'll actually see my latest one all the way through).

But what keeps amazing me is how new languages tends to get popular largely by chance. Many good languages have languished because the inventor simply did not "sell" the language right. There are a lot of languages far better suited for Java's niche than Java, for example. But Java was sold right:

The right people to target are not other compiler writers. The right people are ordinary programmers that might try out and comment on how your language works in the "real world". Far too many languages are "sold" to other compiler writers or advanced programmers based on features the average programmer might have run across once or twice but probably doesn't even know the formal name of.

Here are two examples I stumbled across, from the same language, of how to attract and not attract ordinary programmers.

The bad one first. The web page for The Pure Programming Language starts like this:

Pure is a functional programming language based on term rewriting. It has a modern syntax featuring curried function applications, lexical closures and equational definitions with pattern matching, and thus is somewhat similar to languages of the Haskell and ML variety. But Pure is also a very dynamic and reflective language, and is more like Lisp in this respect. The interpreter has an LLVM backend to do JIT compilation, hence programs run blazingly fast and interfacing to C modules is easy.

It got me slightly interested. But I like looking at new languages. It only got even me slightly interested, though. It throws a lot of buzzwords around; good ones. But what it doesn't do it say anything about why you should care.

Programmers looking at a new programming language tends to ask why they should use a new language, and what it will give them.

The firstThe second example is a file containing lots of small examples of the Pure language. I'm not convinced, but seeing a few of those snippets does a hell of a lot more for me than the paragraph quoted above..

This isn't to put down Pure or it's author. It doesn't look revolutionary, but it looks far more interesting than a lot of other new languages I've seen. It's just that seeing web pages for new programming languages that are not well known without the examples featured as one of the most prominent features is almost as frustrating to me as seeing web pages for desktop applications without a screenshot staring me in the face as soon as the page loads (hint: I'm not going to read through several paragraphs about a new IM client without seeing a screenshot first - most apps are bad and in niches where better apps are dime a dozen, and a screenshot is a good first filter, just as examples are with languages).

Inheritance or configuration options has a cost in terms of increased complexity that can in some cases with advantage be avoided by maintaining multiple versions of the component and adding new features to new branches instead of continuing to work on a single code base, in the same way integrated circuits often exist in a wide range of similar, static, models with the same basic functionality. Better merging support in modern version control systems make this model increasingly viable for software.

One thing I've thought a lot about over the year is why software reuse is so hard.

A big problem is that designing reusable software when you don't know where it might be reused is hard

Over the years, a number of people have brought up integrated circuits as a model for software reuse. I tried to find one of the old articles I read about it this morning, but was unfortunately unable to track it down. But this is not an original idea.

Simple ICs have a number of properties that affect how they are used:

• When they're "complete" they're often never changed other than possibly to fix problems. The design may evolve, but the next "version" tends to be given a new designation and is often treated as a separate product.
• There's often a myriad of different versions with smaller or larger differences - many products exists in variation rather than being configurable. Configurability often adds complexity. In hardware, complexity has a very visible impact.
• Apart from very large complex general purpose processors, most ICs tend to have a very high cohesion, because they have to in order to make financial sense.
• They are "black boxes" in that you can't (or won't) change them, but the details of how you interface with them and how they will respond is well documented and wel understood.

In the software world, meanwhile, we keep trying to design reusable libraries, components and services, and a lot of the time we end up with incredibly complex APIs, because we try to prepare for every eventuality.

The result is both more code (that needs to be tested, and that takes up memory) and abstractions that aren't needed for the core functionality, but that needs to be there to facilitate the configurability (which may add significant overheads).

Why should we put up with this?

Distributed version control and reuse

One thing that struck me this morning was that one of the big features of distributed version control systems promise is to ease the burden of merging, and that this is a major stepping stone towards a simpler model of reuse.

First of all, let me say that I am not against configurable components. I strongly believe in making classes and libraries generic and reusable in itself - specifically by ensuring low coupling and high cohesion. However, sometimes making a component highly flexible comes at the cost of reducing cohesion, of making the component try to please everyone at the same time by exposing interfaces that requires massively increased complexity in order to avoid exposing internal implementation details, or where the choice is taken to "surrender" and expose the guts of the component for everyone to hook into.

Both alternatives are bad.

The "software IC" idea taken to it's ultimate conclusion is this:

Develop strongly cohesive components that export generic interfaces to ensure loose coupling, and "freeze" those components - refuse to add any more features or make any interface changes or adapt it. Limit changes to internals that don't change the observed behavior other than fixing bugs and improving performance characteristics.

It's both incredibly powerful, and at first glance incredibly limiting.

Powerful because it means that when you learn a specific "model" of a component, you have every reason to believe it won't break on you. Imagine linking to the same specific version of a library and never upgrading other than selectively for bug fixes.

Incredibly limiting because software people have a feature fetish. We crave adding functionality, and go all "ohh, shiny" whenever we see something cool has been added. And that's fair, at least when it actually is helpful.

I don't want to stop that. I want to take a much more conscious approach to the fact that when DingbatShell goes from version 1.x to 2.x it's a different model - a different product - than the previous version. Upgrading, even if the API seems to stay mostly backwards compatible, requires new rounds of testing and careful review.

Software IC's aren't new - they're called branches and versions

This is the crux of the matter. You've been able to do this "forever" - and some have done. But very few take the conscious approach that this applies to the whole stack, including third party libraries, build tools that have any kind of effect on the final product etc.

Even fewer extend this to creating a multitude of branches - a new branch for every major "niche" the component is meant to work in, or every major axis of configurability.

A key reason being that in the age of version control systems that have been abysmally bad at merging changes, you really don't want to have to merge in a bug fix across 42 different versions of a component.

I'm not sure we're still quite there yet, but that's almost what I'm proposing. A vital point being that such changes should be exceedingly rare exactly because you freeze features regularly, branch of new components, and continue new feature development while leaving the branches frozen.

Only for critical bug fixes would you be faced with a potentially massive merge job. But if the components remain small and simple that merge job might not be so bad.

This is of course where the new breed of distributed version control systems comes in. Because they're distributed, better merging has been vital. A system like GIT is heavily focused around a workflow that for many users involves frequent multi-way merges of a very high degree of complexity.

We're finally getting tools that are actually specifically geared towards managing large number of branches.

What are the benefits?

Whenever there's a high cost to providing configurability, either in increasing complexity or reducing performance due to complex abstractions you have a point where it's worth considering a new "model".

You can:

• Simplify the API - configuration options that are needed for only one or the other axis of configuration (say using a database vs a set of files as the data source, if the nature of the component is such that it's always either or) can be left out entirely. A good test for whether splitting a component into branches is a good thing is to look at how large parts of the API you can prune away or how many arguments you can remove from methods.
• Improve performance by hardwiring logic that might otherwise go through multiple level of indirection.
• Massively simplify testing, because the number of permutations of configurations may drop significantly (look for m*n effects, where configuration happens along more than one "axis" and where many combination may not make sense, but will still need to work - if branching the component can make testing against a single axis at the time it may be a big win).

This doesn't work for end users and not always even for developers

Imagine if an end user had to look through a catalogue to see which model of Gimp had exactly the features they want. It's not going to happen.

This is an approach for developers, and even then, it is an approach for relatively small, highly cohesive, components.

It is not a panacea. It is not always appropriate.

It's yet another tool, and an approach that I personally will start considering more seriously whenever I get to a point where I want to add more features.

But are you using it?

I have ranted about why I don't like frameworks before, and written a number of small Rack handlers for example, and the direction I'm increasingly taking for web development is to compose applications of small components designed to be extremely small, cohesive and loosely coupled.

That's the ideal scenario for "software ICs". Rather than adding more features to my dispatch class that I will quite possibly only use for a fraction of the apps I write, I will make a branch, add those features to separate branches, and pick and choose, keeping whichever version I pick for a new web app extremely simple. If I need a feature from another "model", I'll make another branch from whichever version is the closest match, and merge in the feature I want.

Currently, the dispatch class I use for this blog, for example, is about 20 lines. It doesn't need to be more. I just butchered it and removed most of the features it used to have because I realize that for this app those features were just cruft and bugs waiting to happen. I keep the code around - when/where I do need it, it's there in my repository.

The same is true for other components I use.

It reduces the need for documentation, even, because untangling the features from eachother have resulted in components that are so trivial to understand that the code does as good a job as a description, and is guaranteed to be much more precise.