Home » forums » LtU Forum

"Down with Lambda-Lifting"

With regard to the absence of new posts (and Eric Meijer), I don't think this paper has been much discussed.

Simplifications of the Spineless Tagles G-Machine and TIM are presented, which
like the classic SECD machine or the Krivine machine reduce lambda-expressions to weak
head normal form -- no prior lambda-lifting is necessary. The machines are at least as
efficient as their combinatorforebears but more importantly they are simpler due to the
elimination of a translation step that obfuscates programs without improving their efficiency.

Note that this marked (on his home-page) as an unfinished draft. Not sure when it was last revised, but it looks post-1992.

Actually I'm hopeing someone might be able to translate the gist of the paper to something a Schemer might understand :), since I think at least Chicken uses lambda-lifting.

By dbfaken at 2006-04-20 17:32 | LtU Forum | previous forum topic | next forum topic | other blogs | 13311 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Here's what I understand after a quick skim

The STGM is a graph reduction virtual machine that is used to implement lazy functional languages (Haskell at least). I believe the TIM is very similar, but I'm not sure where the difference is [It may be that it's tag- and spine- ful]. Instead of passing around an explicit environment, they are based on combinators, functions without any free variable (much like the S/K/I combinators, but with a larger set of more complete combinators, or even supercombinators to improve efficiency). By using combinators, they avoid the need to model the lexical environment. Instead, free variables are lambda lifted and received as arguments. On further reduction, the (references to the) arguments are directly embedded and copied in the subgraph representing the function. The environment is implicit and modelled by the reduction, as new subgraph are created from a template, and references to arguments fixed.

Meijer's paper presents similar machines with an explicit environment object. In the first section, it's a stack, like in the SECD machine. He then describes a similar system with named registers instead of a stack. Finally, he argues that the intermediate code under these environment-ful schemes is clearer without being less efficient.

As for Chicken, I'm not sure if there is anything to relate it to the current paper. However, given the finite function argument limit in C, I doubt that it does full lambda-lifting. Also, (IIUC) closures are pretty much needed for the CPS transform in Cheney on the MTA to make any sense.

I'm really not well-read on the current topic, but it's a first stab. Please correct :)

By pkhuong at Thu, 2006-04-20 18:13 | login or register to post comments

Wow, this is a really nice

Wow, this is a really nice paper! thnx, i can't add much at the moment but i can point to two papers by Simon Peyton Jones that are a great introduction to the G-Machine (STGM == Standard G-Machine?) and the TIM. The links are: a tutorial and
the book
By Jillis ter Hove at Thu, 2006-04-20 21:47 | login or register to post comments

spineless tagless

stgm == spineless tagless g-machine

By jimdesu at Thu, 2006-04-20 22:14 | login or register to post comments

Anybody has a copy?

I am unable to find this paper anywhere — Erik Meijer moved, and neither Google nor Google Scholar turn up any copy of the paper.

CiteSeerX only shows a citing document, but is not helpful otherwise.
http://citeseerx.ist.psu.edu/showciting?cid=1614722

By Blaisorblade at Mon, 2014-02-24 16:58 | login or register to post comments

Ask him

Send him an email? He could maybe just post it on arxiv.org for durable archival.

By gasche at Mon, 2014-02-24 17:04 | login or register to post comments