Lambda the Ultimate

Hi All,

This is a quick note to say that LLVM 1.5 is out, with many new features above and beyond LLVM 1.4. Perhaps the biggest feature of interest to this community is full support for proper tail calls, as described in the release notes. More details about the release can be found in the release notes and in the two status updates [1,2] since 1.4.

For those not familiar with LLVM, it is a compiler system that can be used to build a wide variety of compiler and language systems. It provides language- and target-independent tools for building static compilers, interprocedural optimizers, JITs, etc. If you are working on a new language and need a code generator, you should check it out. LLVM can be used in two ways: 1) link to the libraries we provide for direct access to the APIs. or 2) emit the LLVM IR as a text file. People have even written (toy) languages in perl using the second technique.

Hi,

Is anyone aware of any systems which use AST intermediate representations instead of byte code? A few years ago, I read papers by Michael Franz concerning use of compressed ASTs in the Oberon system (e.g. A Tree Based Alternative to Java Byte Codes - pdf). Work on AST intermediate representations seems to have continued particularly in relation to mobile code (e.g. Towards Language-Agnostic Mobile Code - pdf).

Typically the AST intermediate representation of a program is compiled at the destination on the fly (with varying degrees of optimisation depending on time constraints). I'm interested in interpreting ASTs to see what the performance of AST interpretation is like as a first step (possibly with a subset of Oz). So far I've only found one attempt at anything like this.

Just wondering if LtU readers had come across any other work on AST representations and interpretation.

Regards,
Chris

Hello and sorry if this question has been already answered somewhere, though i searched for it.

The question is: tail-recursion is something badly needed _only_ in Scheme?

Here's a related question: if it isn't, that is, if it's possible to generally get compilers or interpreters to correctly detect recursion and automatically apply and implicit goto to it, then why should i bother, when it just complicates matters?

I gave a though to it when a saw a recent post here about LLVM and its recent support for tail-call for Scheme and also for playing with Haskell a bit.

So, to keep things simple, let's look at the examples:

;; in Scheme
(define (fact n)
  (define (product min max)
    (if (= min n)
	max
	(product (+ 1 min)
		 (* min max))))
  (product 1 n))

That's one way to look at a factorial, but not the _natural_, i guess.

-- in Haskell
-- and just to add a bit more argument
dec n = n - 1

fact 0 = 1
fact n = fact( dec n ) * n

That's the _natural_, let's call it that, high-school definition for factorial, pristine clear. There's no tail-call anywhere to be seen, and yet, it doesn't cause stack overflow with large numbers...

Am i missing something? or is Scheme being stubborn? R6RS is coming and perhaps should address it?

Sorry for being provocative, but it's a sincere question...