OK, thank you all for your responses. I'm impressed how fast you were. 2009/3/8 Rick R :

http://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours

I have it. However, Scheme is strict, which is the reason I didn't complete my reading. Maybe I am wrong.

Or go for the Real Thing: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-35.html#%_sec_5.5

I just opened the page. I'll see what I can take. Thank you. 2009/3/8 Jeremy Shaw :

I can say from experience that the spineless-tagless-gmachine paper you referenced does contain all the information needed to implement an STG->C compiler. But, you should expect to spend a lot of time alternating between trying to implement the thing and rereading the paper.

So I just didn't tried hard enough. Time for a re-read, then!

Also, you may find that it is easier to do STG->Assembly at first (via harpy or something). With assembly it is easier to express exactly what you want to happen. With C you have to try to figure out how to trick the C compiler into doing your bidding.

Scary. I know only C.

Also, maybe it is more satisfying to output assembly, because then you really feel like you are writing a compiler ;)

Well, maybe later.

I am sure others will say that LLVM is a better option than C or assembly. I know almost nothing about LLVM, so they may be right.

Neither do I. But I definitely try this. One day.

-- jeremy

2009/3/8 Austin Seipp :

Excerpts from Loup Vaillant's message of Sat Mar 07 17:32:48 -0600 2009:

...

Ideally, I would very much like to compile to C. [...] -> have some kind of FFI with C (I suppose it imply some support for unboxed values).

Unfortunately, after working on LHC, I can verifiably say (like all the researchers who wrote the papers which I *didn't* read beforehand,) that for a lot of purposes, C is an unsuitable fit for a compilers' target language. It works pretty well if you can make the source language execution model fit well enough, but if you can't, you've a price to pay (both in sanity and/or performance.)

Yep.

However, since your goal is *not* efficiency, you will be happy to know that the issues with compiling to C (like garbage collection and exception handling) can be worked around viably.

I hope so.

For garbage collection, please see.

"Accurate Garbage Collection in an Uncooperative Environment" - http://citeseer.ist.psu.edu/538613.html [...] http://code.haskell.org/ddc/ddc-head/runtime/

Thank you, I'll look into that.

You can find a lot of info on C-- here; I recommend the paper at the bottom to start off:

http://research.microsoft.com/en-us/um/people/simonpj/papers/c--/

I'll look at that. But I am not sure it is the simplest path for me: I know C, and I don't know C-- —yet.

http://research.microsoft.com/en-us/um/people/simonpj/papers/slpj-book-1987/

I have it. Maybe I should study it a bit more.

As for the FFI, I don't really have any papers on 'how to implement an FFI', but Matthias Blume's paper might be of interest:

"No-Longer-Foreign: Teaching an ML compiler to speak c "natively"" http://ttic.uchicago.edu/~blume/papers/nlffi-entcs.pdf

libffi may also be worth investigating: http://sourceware.org/libffi/

I didn't know them, thank you.

...

I have chosen the STG machine because I thought i would be easier to get an FFI and case exprs out of it. Maybe I am wrong, and template instantiation is really easier. There is also the BRISK machine, and GRIN. But the paper I read were less readable to me than the three mentioned.

How far into GRIN have you looked?

Not far enough, it seems.

It is one of the intermediate languages for lhc/jhc, and for a low-level intermediate representation it works quite well I think; it is a strict, monadic intermediate language - being strict, we must still be able to model closures ('suspendeded applications' or thunks,) so we model closures/partial applications in a sort of 'defunctionalized' way (making grin a sort of 'defunctionalized intermediate language' really,) by turning them into something along the lines of an algebraic data type in GRIN. A good benefit of this is that you actually /don't/ have to write eval/apply yourself, because the compiler is supposed to generate it *for* you.

Here is my biggest problem with GRIN: it is not STG by far. I formatted my brain one way, so I find difficult to reformat it another way

In fact, this is a core part of GRIN - the generation of eval by the compiler is critical for many important optimizations to take place. It also makes the runtime a bit simpler.

If I find GRIN is overall simpler, I am happy.

This comes at the price that GRIN is by design a whole-program intermediate form; in order to pull off any of these sophisticated transformations everything must be in memory at once. But as we have seen with LHC/JHC, it can make a *huge* difference (apps that are 10x smaller *and* 10x faster than ones created by GHC.)

I intend my final language to be quite simple. That imply a relatively small standard library. So, maybe having all the program in memory will not be such a big deal.

Having dealt with GRIN as I work on LHC (when time now permits...) I can say that it's a reasonable strategy and in practice it turns out pretty well, but if you're not into optimizing the code, then STG might be a better fit.

OK, maybe I will choose STG for now, then.

I can't really give you that much advice on this area so much as you'll just have to choose. But GRIN does have at least two excellent references:

Code Optimisation Techniques for Lazy Functional Languages - U. Boquist, http://www.cs.chalmers.se/~boquist/phd/index.html

The GRIN Project: A Highly Optimising Back End For Lazy Functional Languages, U. Boquist, http://www.cs.chalmers.se/~boquist/ifl96-abstract.html

Oh, I forgot about the second paper, thank you. I find it a bit clearer than the thesis. Having the GRIN BNF helps a lot.

Then again you said you're not interested in optimization, so perhaps I'm just preaching to the totally wrong choir... :)

No, you're not. A long (looong) term goal of mine is having crazy optimizations. I will definitely explore that path.

Austin

2009/3/8 wren ng thornton :

Loup Vaillant wrote:

...

-> support algebraic data types and case expressions (unless I can get away with encoding them as functions),

Which you always can, [snip]

The only trick is that you need to have closures (in order to build the Foos) and you need to have first-class functions (in order to pass the destructors in). If you're familiar with the STG machine, this is what they do under the covers anyways. At the core level, all you need is some primitive to force evaluation.

Ah, that is what I was missing. I thought I had to implement seq on top of case, not the other way around. Maybe that can make Template instantiation viable

~wren

Anyway, thank you all very much. Time for some reading. Cheers, Loup

On Sat, Mar 07, 2009 at 07:45:06PM -0600, Austin Seipp wrote:

(On that note, I am currently of the opinion that most of LHC's major deficiencies, aside from a few parser bugs or some needed optimizations, comes from the fact that compiling to C is currently our only option; because of it, we have no exception handling or proper garbage collection at all. As well, the runtime system is a little needlessly 'clever' (if small and understandable) so it can deal with that.)

It would be interesting if you could revive the ghc back end I wrote for jhc in lhc. the code is still in the repository but was disabled a while ago, and I was just fretting over whether I should just delete it from the codebase as an interesting experiment. I mainly used it as a debugging aid once upon a time, but it was difficult to keep up to date with the C back end. I know it is sort of a silly back end, but it might be interesting.

Having dealt with GRIN as I work on LHC (when time now permits...) I can say that it's a reasonable strategy and in practice it turns out pretty well, but if you're not into optimizing the code, then STG might be a better fit.

I think a big deciding factor here would be the answer to one question "do you want to deal with unboxed values in your compiler internally?" As in, you plan on a lazy language, so, do you ever want to open up those thunks and deal with unboxed values in your compiler guts or do you want to treat them as abstract boxes to be evaluated by the runtime? if you do want to think about unboxed values, for optimization or other purposes, bite the bullet and go for something like GRIN as the back end and support unboxed values all the way through to the front end from the get go. If you really only want to support lazy thunks, go with one of the quasi virtual machine style implementations like STG. John -- John Meacham - ⑆repetae.net⑆john⑈

On Mon, Mar 09, 2009 at 09:25:58AM -0500, Austin Seipp wrote:

Indeed, I stumbled upon it whilst looking at how unsafeCoerce worked (to find out it is super-duper-special and implemented as part of E.) I think it's actually pretty clever, and who knows, maybe it could be useful as at least a debugging aid. :)

It is actually not all that special, it is just a primitive like any other than transates to a nop, or no code. Since the optimizer can't know what is inside a primitive in general, it leaves it alone and the only affect is the type coercion implicit in its signature. When translating to Grin, the unsafeCoerces are simply dropped. Coercions used to be more complicated because once upon a time I required them to be used to translate to/from newtype declared synonyms, I found they inhibited optimizations too much so switched to the current mechanism whereby newtype expansion happens transparently in the type checker when needed. As a side effect I worked hard to try to recognize and optimize around coercions, but now that they occur fairly rarely, it isn't much of an issue any more.

This is a very good point I hadn't even thought about! Indeed, since GRIN represents thunks in a defunctionalized way - encoded as nodes - dealing with boxed/unboxed values becomes more of the compiler's job, since the nature of unboxed values etc. becomes more transparent.

The main reason I think it is important is because I feel not including unboxed values from the get-go was one of the biggest false starts I had when writing jhc. When I initially started writing it I considered unboxed values as a feature to be added later. When I started implementing them, I found that there were a lot of decisions I would have made differently and a lot of places they would have greatly simplified my initial design had I had them from the start. Namely, A whole host of 'compiler magic' could have gone away if I implemented all primitive types in pure haskell like I implement floats and chars now, data Float = Float_ Float32_ data Char = Char Bits32_ (where Float32_ and Bits32_ are the unboxed raw types) Since instead I had the compiler implement Int and friends directly, it suddenly had the responisibity to conjure up all sorts of operations on them, such as the Num instances, creating the big mess of compiler magic in PrimitiveOperators.hs. The more I can express in the haskell source directly the better, it raises odd questions when the compiler has to do things like implement Num instances directly, like the instances are built in, but we might not have 'imported' the types needed to declare them into the current scope, so we end up having to deal with instancse for types that don't exist yet. In any case, yeah. if you plan on unboxed types at some point, include them from the start because they can simplify a lot to offset their cost of implementation, by trying to add them on later I ended up having to pay the cost of implementing them, but also had to deal with the cruft left over from not utilizing them from the beginning.

Since you bring this up, I figure this decision also had some influence on E in lhc/jhc, considering its type system is rich enough to distinguish values in whnf/boxed/unboxed etc.?

Yeah, there were a couple things that motivated this. A big one is that evals are bad in jhc, signifigantly moreso than traditional ghc. The points-to analysis is the main way to fight it, but I also decided I wanted to give it the best shot possible by getting rid of as many evals as I could in higher level optimizations, which necessitated a fairly rich type system since it actually made sense for jhc to keep strict track of what was in WHNF vs not even if they were both boxed. in general ghc didn't care unless a value was either CPRable or unboxable, but jhc can benefit from such knowledge no matter what the type, even if it is a partially applied function. Though, it is interesting that GHC may be moving to a jhc-style semi-tagging mechanism according to this paper[1] so more optimizations may help both equally in the future. The other main motivating factor was that I was always enamoured with the idea of jhc supporting more than one source language, in particular, I wanted to explore it having an SML front end, so wanted a core type system that was equally good at expressing lazy haskell as strict ML, and more importantly would be able to seamlessly intermingle the two without difficulty. So, when designing it, I kept that in mind, "is this equally useful as a ML compilers core?" or a "wacky ML/Haskell hybrid?". Although the ML front end is more of a thought experiment at this point, I think it helped me come up with a coherent type system that had intruiging possibilies for haskell optimizations, as well as some language implications, such as the ability to declare new 'strict' algebraic types that may lead to new ideas for language extensions. John [1] http://research.microsoft.com/en-us/um/people/simonpj/papers/ptr-tag/ -- John Meacham - ⑆repetae.net⑆john⑈