lexical goto would include full continuations?

classic Classic list List threaded Threaded
22 messages Options
12
Reply | Threaded
Open this post in threaded view
|

lexical goto would include full continuations?

Charles Engelhard
In the current 5.2 spec, it mentions that goto cannot see labels through a nested function body. I think this is unfortunate for a few reasons and hope that the eventual goal is to extend the functionality. There are two problems with this restriction: 
- It's un-Lua-ish, in that suddenly there's a place in the language where function scopes are special. It's a pretty surprising restriction, unless you think in terms of the admittedly difficult implementation issues.
- It's a missed opportunity to have the power of Scheme-style continuations with an understandable interface. I've always thought that this feature of Scheme failed to spread as much as other features that Scheme introduced simply because call-with-current-continuation, as an interface to the feature, tends to confuse people. A quick proof that a proper lexical goto would implement continuations is as follows:

function callcc(fun)
  local ret
  ::exit::
  if ret then
    return table.unpack(ret)
  else
    return fun(function(...)
      ret = {...}
      goto exit
    end)
  end
end

(Note that "goto exit" requires visibility of the label through a nested function body.)
(Actually, this undocumented bit of code is a more understandable explanation of how call/cc works than any I've ever seen!)

Technically, this addition to the language would also mean that the coroutine library could be implemented in pure Lua! This might not be a good idea for performance reasons (depending on implementations) but is another good argument for the power of the feature. Similarly, it would allow for all sorts of non-local exits, such as exceptions. 

Lua has been in a state of "almost having continuations" for a while, and I think it's about time to bring them in. A lexical goto would be a novel, straightforward, and unsurprising way of doing this. 
Reply | Threaded
Open this post in threaded view
|

Re: lexical goto would include full continuations?

David Kastrup
Charles Engelhard <[hidden email]> writes:

> Technically, this addition to the language would also mean that the
> coroutine library could be implemented in pure Lua! This might not be
> a good idea for performance reasons (depending on implementations) but
> is another good argument for the power of the feature. Similarly, it
> would allow for all sorts of non-local exits, such as exceptions. 
>
> Lua has been in a state of "almost having continuations" for a while,
> and I think it's about time to bring them in. A lexical goto would be
> a novel, straightforward, and unsurprising way of doing this. 

Scheme tries to be incomprehensible by mapping everything and its dog
through the concept of continuations, a barely structured approach.

Now Lua should try to become incomprehensible by mapping everything
through the concept of goto, an unstructured approach?

Back to the BASICs?

--
David Kastrup


Reply | Threaded
Open this post in threaded view
|

Re: lexical goto would include full continuations?

Dirk Laurie
In reply to this post by Charles Engelhard
On Tue, Jul 12, 2011 at 04:34:21AM +0200, Charles Engelhard wrote:
> In the current 5.2 spec, it mentions that goto cannot see labels through a
> nested function body.
Let's have the actual words from beta-rc7.
| A label is visible in the entire block where it is defined, except inside
| nested blocks where a label with the same name is defined and inside nested
| functions. A goto may jump to any visible label as long as it does not enter
| into the scope of a local variable.
I presume your point is that this spec prohibits jumping from inside
a function to a label outside it.  You want to do this sort of thing:

    a,b,c = f(d,e,f)
    -- lots of other code
    ::target:: print "Naughty, naughty!"; os.exit(-1)
   
    function f(x,y,z)
        if z==nil then goto target end
    --  lots of other code
        end

> - It's un-Lua-ish, in that suddenly there's a place in the language where
> function scopes are special. It's a pretty surprising restriction, unless
> you think in terms of the admittedly difficult implementation issues.
Implementation for ordinary, Lua-ish applications is not difficult.  

You do the equivalent of:

goto_target = {}    -- unique object
a,b,c = f(d,e,f)
if a==goto_target then goto target end
-- lots of other code
::target:: print "Naughty, naughty!"; os.exit(-1)

function f(x,y,z)
    if z==nil then return goto_target end
--  lots of other code
    end

Point is, as you can see, this is dead easy in Lua itself.  It costs
three lines of code and a new table, but it gives the bonus that any
reader of the code knows, right up there where f is called, that there
may be a jump.

Moreover, doing it this way is more powerful than lexical scoping,
because if the call to f and the label in question are inside the
same scope of a local variable, it's still possible.

But OK, the main point of your post was that you could implement
something called call/cc if Lua had lexical calls.  I had to look
up Wikipedia to find out that call/cc is a Scheme speciality, in which
it can be used “to emulate the functionality of the return statement …
which is missing from Scheme”.  (Random thought: why not post a request
for including a return statement on Scheme's mailing list?)

I can't understand the rest of that article; I can't even understand
your code which you claim is the most understandable explanation
you've ever seen.  So I can't check whether the construction I show
above is be enough to enable you to implement your callcc function.
You might be able to tell.

But is it worth while, even so?  You say:
> I've always thought that this feature of Scheme failed to spread as
> much as other features … because … tends to confuse people.
I can confirm that tendency first-hand.

Can't we leave call/cc to people who understand Scheme and Haskell and
phrases like “Curry-Howard correspondence” and “intuitionistic logic”,
and just carry on our state of Lua-tic bliss, contentedly puffing on our
return statements?

Dirk


Reply | Threaded
Open this post in threaded view
|

Re: lexical goto would include full continuations?

Tony Finch
In reply to this post by Charles Engelhard
Charles Engelhard <[hidden email]> wrote:

> - It's a missed opportunity to have the power of Scheme-style continuations
> with an understandable interface.

I think this is a contradiction in terms. Continuations need to be tamed
in some way to be understandable. For instance, Lua's coroutines are
essentially one-shot continuations.

Fully general first class continuations are difficult to implement
efficiently. They either put enormous stress on the garbage collector
or they require some kind of stack copying.

Lua also needs to work in a standard C environment which means there would
have to be some awkward restrictions on continuations.

Tony.
--
f.anthony.n.finch  <[hidden email]>  http://dotat.at/
Lundy, Fastnet, Irish Sea: Variable mainly northeast, 3 or 4. Slight or
moderate. Showers. Moderate or good.

Reply | Threaded
Open this post in threaded view
|

Re: lexical goto would include full continuations?

David Kastrup
Tony Finch <[hidden email]> writes:

> Charles Engelhard <[hidden email]> wrote:
>
>> - It's a missed opportunity to have the power of Scheme-style continuations
>> with an understandable interface.
>
> I think this is a contradiction in terms. Continuations need to be tamed
> in some way to be understandable. For instance, Lua's coroutines are
> essentially one-shot continuations.
>
> Fully general first class continuations are difficult to implement
> efficiently. They either put enormous stress on the garbage collector
> or they require some kind of stack copying.

It is not that bad.  You put the return stack on the heap, and leave
cleaning it up to the garbage collector.  Since garbage collection is a
major part of most dynamic languages (including Lua) anyway, the impact
is tolerable.

The Scheme compiler Chicken actually uses the normal call instructions
IIRC.  It just does not return, and the stack gets garbage collected
occasionally.

> Lua also needs to work in a standard C environment which means there
> would have to be some awkward restrictions on continuations.

IIRC, Chicken mixes with C.

--
David Kastrup


Reply | Threaded
Open this post in threaded view
|

Re: lexical goto would include full continuations?

Tony Finch
David Kastrup <[hidden email]> wrote:

> Tony Finch <[hidden email]> writes:
> >
> > Fully general first class continuations are difficult to implement
> > efficiently. They either put enormous stress on the garbage collector
> > or they require some kind of stack copying.
>
> It is not that bad.  You put the return stack on the heap, and leave
> cleaning it up to the garbage collector.  Since garbage collection is a
> major part of most dynamic languages (including Lua) anyway, the impact
> is tolerable.

It requires a heap allocation for all function calls and it destroys
the locality benefits you get from stack allocation. Freeing a stack
frame requires a gc rather than a pointer adjustment. To minimize the
overheads you need a bump allocator (so that heap allocation is as
efficient as stack allocation), you need to keep tight control of
pointers into the nursery (to make GC quick), and you need to make the
nursery a decent size (to amortize the cost of GC) but not so large that
it blows the CPU cache.

So I think it is that bad.

Tony.
--
f.anthony.n.finch  <[hidden email]>  http://dotat.at/
Trafalgar: North or northwest 4 or 5, increasing 6 or 7. Slight or moderate,
becoming moderate or rough. Showers. Moderate or good.

Reply | Threaded
Open this post in threaded view
|

Re: lexical goto would include full continuations?

steve donovan
On Tue, Jul 12, 2011 at 1:30 PM, Tony Finch <[hidden email]> wrote:
> So I think it is that bad.

Also, it's possible that I've led a sheltered life under a bush, but
what would full continuations give us that we don't already have?

(This feature may not have migrated from Scheme often for a good reason)

steve d.

Reply | Threaded
Open this post in threaded view
|

Re: lexical goto would include full continuations?

David Kastrup
In reply to this post by Tony Finch
Tony Finch <[hidden email]> writes:

> David Kastrup <[hidden email]> wrote:
>> Tony Finch <[hidden email]> writes:
>> >
>> > Fully general first class continuations are difficult to implement
>> > efficiently. They either put enormous stress on the garbage collector
>> > or they require some kind of stack copying.
>>
>> It is not that bad.  You put the return stack on the heap, and leave
>> cleaning it up to the garbage collector.  Since garbage collection is a
>> major part of most dynamic languages (including Lua) anyway, the impact
>> is tolerable.
>
> It requires a heap allocation for all function calls and it destroys
> the locality benefits you get from stack allocation. Freeing a stack
> frame requires a gc rather than a pointer adjustment.

"Freeing a stack frame" does not need continuous action on every
return.  It is done when necessary, like heap collection.

> To minimize the overheads you need a bump allocator (so that heap
> allocation is as efficient as stack allocation), you need to keep
> tight control of pointers into the nursery (to make GC quick), and you
> need to make the nursery a decent size (to amortize the cost of GC)
> but not so large that it blows the CPU cache.
>
> So I think it is that bad.

You need good garbage collection.  Having a bad garbage collector and
hoping it will not show too much is not a good option for dynamic
languages with or without continuations.

--
David Kastrup


Reply | Threaded
Open this post in threaded view
|

Re: lexical goto would include full continuations?

David Kastrup
In reply to this post by steve donovan
steve donovan <[hidden email]> writes:

> On Tue, Jul 12, 2011 at 1:30 PM, Tony Finch <[hidden email]> wrote:
>> So I think it is that bad.
>
> Also, it's possible that I've led a sheltered life under a bush, but
> what would full continuations give us that we don't already have?

Incomprehensibility.  We already have goto, but it can't cross function
boundaries.

It can be used to some degree for optimization tasks involving different
execution paths depending on some choice.  I can make _both_ choices,
one after the other, and keep track of all partial executions not yet
fallen through a min-max sieve, continuing (for better estimate
boundaries) or dropping them on an as-needed base.

The optimization process itself becomes utterly incomprehensible and
intractible but tightly capsuled, but developing the various
possibilities (and their scoring) becomes easily extensible and
understandable.  And in the end result, magically all the right
decisions have been made, even though the first decisions need not
correspond with local maxima and thus interdepend with later decisions.

Basically, when you have good reason to postpone one way of finishing
some operation, in particular when you want to try finishing it in
several different, incompatible ways, continuations can be useful.

Not comprehensible in itself, but as a tool for confining the
incomprehensibility to small code paths closely watched by wizards.

--
David Kastrup


Reply | Threaded
Open this post in threaded view
|

Re: lexical goto would include full continuations?

Tony Finch
In reply to this post by steve donovan
steve donovan <[hidden email]> wrote:
>
> Also, it's possible that I've led a sheltered life under a bush, but
> what would full continuations give us that we don't already have?

This looks like a useful survey:
http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.4790

Tony.
--
f.anthony.n.finch  <[hidden email]>  http://dotat.at/
Biscay: North or northwest 4 or 5, occasionally 6 later. Slight or moderate.
Thundery showers. Good, occasionally poor.

Reply | Threaded
Open this post in threaded view
|

Re: lexical goto would include full continuations?

Tony Finch
In reply to this post by David Kastrup
David Kastrup <[hidden email]> wrote:
>
> You need good garbage collection.  Having a bad garbage collector and
> hoping it will not show too much is not a good option for dynamic
> languages with or without continuations.

I think you should look at the relative frequency of table allocation,
closure allocation, and function calls in typical Lua code.

Most dynamic languages have crappy garbage collectors.

Tony.
--
f.anthony.n.finch  <[hidden email]>  http://dotat.at/
West Forties, Cromarty, Forth, Tyne: Mainly northerly or northeasterly 3 or 4,
occasionally 5 later. Slight or moderate. Showers. Good.

Reply | Threaded
Open this post in threaded view
|

Re: lexical goto would include full continuations?

Alex Queiroz
In reply to this post by David Kastrup
Hallo,

On Tue, Jul 12, 2011 at 7:32 AM, David Kastrup <[hidden email]> wrote:
>
> Scheme tries to be incomprehensible by mapping everything and its dog
> through the concept of continuations, a barely structured approach.
>

     This is beyond wrong, it's FUD. One can be completely unaware of
the concept of continuations and use 95% of the language described in
R5RS.

--
-alex
http://www.artisancoder.com/

Reply | Threaded
Open this post in threaded view
|

Re: lexical goto would include full continuations?

Alex Queiroz
In reply to this post by Tony Finch
Hallo,

On Tue, Jul 12, 2011 at 1:30 PM, Tony Finch <[hidden email]> wrote:

>
> It requires a heap allocation for all function calls and it destroys
> the locality benefits you get from stack allocation. Freeing a stack
> frame requires a gc rather than a pointer adjustment. To minimize the
> overheads you need a bump allocator (so that heap allocation is as
> efficient as stack allocation), you need to keep tight control of
> pointers into the nursery (to make GC quick), and you need to make the
> nursery a decent size (to amortize the cost of GC) but not so large that
> it blows the CPU cache.
>

     The already cited Chicken Scheme compiler allocates *everything*,
not just function call frames, on the stack, until a minor GC is
requested, which makes the C stack effectively work as the first
generation of a generational garbage collection and makes allocation
be *very* fast.

--
-alex
http://www.artisancoder.com/

Reply | Threaded
Open this post in threaded view
|

Re: lexical goto would include full continuations?

David Kastrup
In reply to this post by Tony Finch
Tony Finch <[hidden email]> writes:

> David Kastrup <[hidden email]> wrote:
>>
>> You need good garbage collection.  Having a bad garbage collector and
>> hoping it will not show too much is not a good option for dynamic
>> languages with or without continuations.
>
> I think you should look at the relative frequency of table allocation,
> closure allocation, and function calls in typical Lua code.
>
> Most dynamic languages have crappy garbage collectors.

Since you are objecting to continuations in Lua rather than some
hypothetical dynamic language, your argument would apply when you
consider Lua's garbage collector crappy.  What particular performance
degradation do you expect from it?

--
David Kastrup


Reply | Threaded
Open this post in threaded view
|

Re: lexical goto would include full continuations?

David Kastrup
In reply to this post by Alex Queiroz
Alex Queiroz <[hidden email]> writes:

> Hallo,
>
> On Tue, Jul 12, 2011 at 7:32 AM, David Kastrup <[hidden email]> wrote:
>>
>> Scheme tries to be incomprehensible by mapping everything and its dog
>> through the concept of continuations, a barely structured approach.
>>
>
>      This is beyond wrong, it's FUD. One can be completely unaware of
> the concept of continuations and use 95% of the language described in
> R5RS.

Sure, but if you want coroutines or other non-local control structures,
you mostly have to revert to continuations rather than less powerful
constructs.

--
David Kastrup


Reply | Threaded
Open this post in threaded view
|

Re: lexical goto would include full continuations?

Alex Queiroz
Hallo,

On Tue, Jul 12, 2011 at 3:02 PM, David Kastrup <[hidden email]> wrote:
>
> Sure, but if you want coroutines or other non-local control structures,
> you mostly have to revert to continuations rather than less powerful
> constructs.
>

     You are right, so I misunderstood what "everything and his dog" meant.

--
-alex
http://www.artisancoder.com/

Reply | Threaded
Open this post in threaded view
|

Re: lexical goto would include full continuations?

Tony Finch
In reply to this post by David Kastrup
David Kastrup <[hidden email]> wrote:

> Tony Finch <[hidden email]> writes:
> > David Kastrup <[hidden email]> wrote:
> >>
> >> You need good garbage collection.  Having a bad garbage collector and
> >> hoping it will not show too much is not a good option for dynamic
> >> languages with or without continuations.
> >
> > I think you should look at the relative frequency of table allocation,
> > closure allocation, and function calls in typical Lua code.
> >
> > Most dynamic languages have crappy garbage collectors.
>
> Since you are objecting to continuations in Lua rather than some
> hypothetical dynamic language, your argument would apply when you
> consider Lua's garbage collector crappy.  What particular performance
> degradation do you expect from it?

My comment about crappy garbage collectors was to reinforce my point that
dynamic languages stress GC much less than functional programming
languages. Lua's GC is much better than most others.

We agree that continuations work best with a bump allocator, which
requires a moving GC. Lua's GC doesn't move objects so it would need
rewriting. Maybe you could keep the current GC for most objects and
add a new one for local variables, closures, upvalues, and so forth.

Lua would need much more memory reserved for its stack, to provide space
for call frames that are not immediately reclaimed.

I can't think of anything that is likely to become noticably simpler.

http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.8219
http://home.pipeline.com/~hbaker1/CheneyMTA.html
http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.2789

Tony.
--
f.anthony.n.finch  <[hidden email]>  http://dotat.at/
Biscay: North or northwest 4 or 5, occasionally 6 later. Slight or moderate.
Thundery showers. Good, occasionally poor.

Reply | Threaded
Open this post in threaded view
|

Re: lexical goto would include full continuations?

Roberto Ierusalimschy
> We agree that continuations work best with a bump allocator, which
> requires a moving GC. [...]

There are several other issues with continuations besides frame
collection. For multi-shot continuations, we would need some kind of
stack copies, but plain stack copies will not work in Lua because local
variables live in the stack. (Most Scheme compilers do "assignment
convertion" for assignable variables. This is reasonable for Scheme,
where assignment is the exception, but I guess it would be too expensive
for Lua, where assignment is the norm.)  (Of course, we can also argue
what should be the proper semantics for assignable local variables in
presence of multi-shot; that would only emphasise that things are not
as simple as a better GC...)

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: lexical goto would include full continuations?

Javier Guerra Giraldez
In reply to this post by Charles Engelhard
On Mon, Jul 11, 2011 at 9:34 PM, Charles Engelhard <[hidden email]> wrote:

> function callcc(fun)
>   local ret
>   ::exit::
>   if ret then
>     return table.unpack(ret)
>   else
>     return fun(function(...)
>       ret = {...}
>       goto exit
>     end)
>   end
> end

that's _really_ eye-opening; but what i interpret of this is not that
"whe're so close to full continuations" instead, i think it means:
"fully lexical goto is just as hard to implement as continuations".
putting it way out of scope for current goals of 5.2.

maybe Lua 6.0 would have lexical goto, and implement continuations
over it, and coroutines on top of continuations; or maybe
continuations as primitive and goto as derivate.... or maybe some
other, more general mechanism that makes all this trivial to write. or
maybe we find that goto is actually a bad idea and eschew it totally.

--
Javier

Reply | Threaded
Open this post in threaded view
|

Re: lexical goto would include full continuations?

Tony Finch
In reply to this post by Roberto Ierusalimschy
Roberto Ierusalimschy <[hidden email]> wrote:
>
> There are several other issues with continuations besides frame
> collection.

The major one that I forgot to mention (!) is that both SML/NJ and Chicken
Scheme do CPS conversion of the code which eliminates all function
returns. This requires the parser to build an AST which is extensively
rewritten before being reduced to executable code. This would be a fairly
big slowdown for Lua.

Tony.
--
f.anthony.n.finch  <[hidden email]>  http://dotat.at/
Malin, Hebrides: East or northeast, becoming variable 3 or 4, occasionally 5
at first in Hebrides. Slight or moderate. Mainly fair. Good.

12