Push-Enter vs Eval-Apply

I use a simple 'push-enter' method where the callee determines, given the arity of the combinator and the number of arguments passed, how to rewrite a closure. Most optimizing functional compilers do arity-analysis and use an 'eval-apply' compilation scheme where the caller generates the code for the arity known at compile-time.

I can see most  of the benefits, primarily, it makes it possible to compile to C using it's normal calling convention. I.e., instead of trampolining thunks in the heap, most calls are translated to regular calls using the stack (the machine's calling convention) and closures are build in the heap on demand.

Translating to an abstract machine which uses a stack and heap, instead of just a heap, isn't a trivial move. Though, theoretically, combinators are easily translated to a stack/heap machine, at the moment, I fail to understand all the ramifications.

Is it true, and why would this be the case, that Clean's ABC machine is as fast as optimized native code?

What are Type Classes?

I joined the Haskell-cafe mailing list out of curiosity, and looked at some posts with some type-hacks. One of the questions it immediately threw up is: "What is a type-class, exactly?"

One of the reasons Hi has simple interfaces on typed values is that there is no short direct answer to the above in plain English. Well, that and the fact that there are programs for which Haskell has, or had, problems deriving the type or acts counter-intuitive. (Don't ask me for examples, it was just stuff I found in certain papers.)

So, since I am bored for the moment, think I'll spend some time whether there is an easy neat answer to that question.

[ Sterling was so kind to start a Reddit thread on it, see the replies to this post. I don't like the current answers yet since I want a non-phenomenological explanation; I believe a construct in a programming language should have a clear description in plain English which precisely describes the operational behavior of constructs such that programmers do not experience surprises in using them. Most phenomenological explanations don't do it for me, neither does a precise mathematical explanation since you really don't want to understand code in terms of the typing algorithm, or a specification of that.]

SECD, G-Machines, Combinatorial Machines and DOTs

I am wondering whether I should sit down and write down my musings on DOT evaluation, I once dubbed it the C-Machine, as a pun at the G-Machine and my target language C. Thing is, I devised it myself and don't really know what to think about it.

On first glance, it is just a reverse polish term rewrite system with eager semantics which is compiled down to a machine. It doesn't really make sense to see the DOT notation as a machine like SECD; for example, there is no code stack. On the other hand, it's not very complex, but there are a bunch of restrictions, invariants, and extra rules, which make it somewhat baroque for a notation.

Still, it is the simplest I could come up with, and it is a lot simpler than SECD or ZINC. It would make a lot more sense for people to, for instance, verify this simple scheme than a SECD machine which has its roots in Lisp and for which there are no real design rationale except for the fact that it works.

I also wonder whether SECD is faster by design, since lambda terms are mapped to it trivially (I guess), and I need the extra overhead of compiling down to combinators.

Moreover, why bother? I thought it might be fast, but at the moment, I overshot three performance metrics, code size, running time and memory consumption, each by a factor ten. Still, I am not sure that is the result of the scheme used. Or rather, the explosion seems to occur in the translation from combinators in Dot notation to abstract assembly, so, I probably messed up there. Does GHC still compile down to combinators internally?

Log 121610

Changed the runtime to use the Hi ffi type structure as the normative reference instead of the libffi ffi type structure. Will need to extensively unit test this. Another feature, by seeing character data as values I'll end up copying to the heap, which is slow, and should probably automatically free whatever C returns, which may not always play well with the intension of C routines. Hey! It's a feature, not a bug.

The Woes of Change

To get to native string support, I ran into a set of mundane problems, the most pressing libffi support.

Since my language is bootstrapped, moving to string support is a non-trivial exercise since it changes a fundamental assumption on how data is represented.

In order to get it to work, I need to advance by going through the following steps:

1. Devise a runtime which supports native strings
2. Build a compiler which targets that runtime
3. Build a compiler which uses that runtime
4. Compile 2 with the regular compiler
5. Compile 3 with 2
6. Compile 3 with 3

Whoever taught me that bootstrapped languages are easily extended?

One problem is in the change of the runtime. To keep the implementation minimal, all Hi FFI type structures are compiled down to libffi type structures, and all subsequent data conversions are done with the libffi type structure as the normative reference. The latter choice I made because working with the libffi type structure is a bit faster and more easily expressible in C than working with the Hi FFI type structure, it also keeps the number of invariants down.

Problem now is that since I want to treat character data as values, but must pass a pointer to libffi, I want to discriminate between ordinary pointers and pointers to character data. Woe on me, I need an extra type tag in libffi types, which seems to be impossible. I ran into the expression problem in C.

There are two options:

1. A quick-and-dirty fix, encode character pointers as something else such as a structure containing just one pointer, or an unsigned integer of pointer size. Not nice, and it will break if an ABI treats such an encoding different as a pointer.
2. Take a step back, and use the Hi FFI type structure as the basis of all data conversions, which is a bit less nice, since I need to write some extra code for that, and it is probably somewhat slower.

Ah well. The better solution is to take a step back.

Log 121410

I did some programming, and threw all code away again. I am gonna cheat a bit and represent integers, floats, and other literals by their text representation and write conversion routines for them to native words. It keeps the number of AST nodes small since it doesn't introduce a separate case for each literal (like int, long, float, double) at the expense of inspecting the text representation from time to time.

Log 121310

After the joy of bootstrapping my language, and the subsequent tedious analysis of performance problems, I am programming again!

I failed to produce any interest in my language, which is somewhat expected. Programmers want completed tools, and other language writers are more interested in their own projects, so, I guess all interest will be suspended until I create a performing front-end to gcc or llvm. Which may never happen. It is questionable whether the simple rewrite system employed can be exploited to generate fast binaries. The DOT notation is a straight intermediate between a SECD machine and a TRS/GRS. Possibly, instead of inheriting the best of both worlds, it inherits the worst of both worlds performance wise.

But, ah well, it beats playing Sokoban. Changes I am now concentrating on are getting literal support (including strings) right before, possibly, changing to a ref-counting model.

Refcounting support isn't hard, but implementing it will probably mean wasting a few weeks on debugging. Still unsure about it. I was worried of running out of scratch space during a rewrite, now I get the feeling supporting strings may mean I need less scratch space. Simple examples like  [F s -> cons 'x' (cons 'y' (cons 'z' s)) ] actually need more scratch space than [F s -> append "xyz" s] in case the text s is small.

Now doing a bit boring work, the amount of literals just mean a lot more cases on the AST. It would be nicer if I could somehow factor literal support out with direct general support in the language, but it seems that would imply writing a lot of code.