[LLVMdev] Closures, newbie question

[David Given]

On 26/01/13 19:20, Torsten Rüger wrote:
[...]
> Just at the end it mentions closures and I was wondering how those are done in llvm. 
> The link was to wikipedia, and i do know what closures/blocks/continuations are, (i think) but maybe someone could point me to where to read about how to do them in llvm.

I've implemented closures in the past --- it's fiddly and a surprising
amount of work, but not actually hard. Basically:

- do static analysis of your code to determine what functions import
what upvalues from where and what functions export upvalues to where.

- any function exporting upvalues needs to allocate its stack frame (or
at least, enough of its stack frame to contain the upvalues) from the heap.

- any function which imports upvalues must take an extra parameter
pointing to the imported stack frame.

- any call to a function which imports upvalues must pass in the stack
frame in the call.

And of course it all has to be recursive, because you may need to pass
said stack frame through another function.

e.g.:

function level1() /* exports i, imports nothing */
{
  var i = 0;
  function level2() /* exports i, imports i */
  {
    function level3() /* exports i & j, imports i */
    {
      var j = 0;
      function level4() /* exports nothing, imports i & j */
      {
        return i + j;
      }

      level4();
    }

    level3();
  }

  level2();
}

There are numerous ways to pass the stack frames into the inner
functions. The naive approach is to simply have each stack frame contain
a pointer to the enclosing frame, but that means that level4 has to
evaluate f.level3.level2.level1.i. Optimising this is easy, and that's
what I've done in the past, but I'm actually wondering whether it may
not be easiest just to pass each frame in as a separate parameter and
then let LLVM take care of the details:

function level1()
{
  var level1frame = { i = 0; };
  level2(level1frame)
}

function level2(level1frame)
{
  var level2frame = { };
  level3(level1frame, level2frame)
}

function level3(level1frame, level2frame)
{
  var level3frame = { j = 0 };
  level4(level1frame, level2frame, level3frame)
}

function level4(level1frame, level2frame, level3frame)
{
  return level1frame.i + level3frame.j;
}

My current project is a very small pure functional language. It doesn't
support closures, but it does have upvalues. I'm implementing them in
this by just passing the variables in as parameters directly --- as it's
pure, I don't have to worry about nested functions changing an upvalue.
(It's at http://cowlark.com/calculon/dir?ci=tip if you're interested,
but be warned, upvalues are currently broken.)

-- 
┌─── ｄｇ＠ｃｏｗｌａｒｋ．ｃｏｍ ───── http://www.cowlark.com ─────
│ "Of course, on a sufficiently small planet, 40 km/hr is, in fact,
│ sufficient to punt the elastic spherical cow into low orbit." ---
│ Brooks Moses on r.a.sf.c

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 262 bytes
Desc: OpenPGP digital signature
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130126/3b09c346/attachment.sig>