From: Ivan Tomac [mailto:e1_t@...]

><william.d.tanksley.jr@s...> wrote:

>>My implementation, as usual, won't do exactly this. Let me provide
>>a little background. I apologise in advance for destroying your
>>sanity, but:
>> http://citeseer.nj.nec.com/hieb93subcontinuations.html
>> http://citeseer.nj.nec.com/queinnec91dynamic.html

>Interesting. I'll have to read those papers sometime.

In short, the articles point out that traditional continuations give you
only limited control: you can return control to an earlier point in the
program's execution, but you can't _call_ that earlier point (i.e. control
never returns to you), and the programmer can't specify where the
continuation _ends_ (in essence, every continuation ends at the command
prompt).

The solution documented in these papers is to provide a way to mark the
start of a "subcontinuation", AKA a "partial continuation", and allow the
programmer to save and call partial continuations. This allows much finer
control.

In Forth, partial continuations are easy (although the ANSI standard doesn't
provide promises that they'll work on every machine), but first-class
partial continuations are hard. "mlg", at http://www.forth.org.ru/~mlg/,
describes a backtracking system based on partial continuations, with the
added twist of being able to manipulate individual return addresses (a
classical Forth ability). Mlg has also done some other work in Forth
continuations, and I found his source code illuminating (but challenging).

>An old version of Meta/4 does something like that. I don't know if
>you had a look at it yet but cont and xcc words in prim3.inc pretty
>much work in the way you described.

I've read through some of it, and I like it (I didn't see that part).

>I've given up on that for now though. For interpretation I believe
>using 3 stacks has a few advantages (simplicity and clarity are
>probably the main ones).

I see too many problems, actually. Using an instruction stack is interesting
and novel, but isn't needed; conventional execution does the same thing.
Using a continuation stack can actually cause problems, since the
continuation stack is actually tied to the instruction stack in subtle ways.

It makes more sense to me to use two stacks, one for data and one for return
addresses, and since return addresses completely describe continuations, tag
the return stack to indicate where continuations start and end. As I've
said, making this first-class is hard in Forth, but in an array or
list-based language it's simple -- just dump the portion of the return stack
indicated by the continuation markers into an array or list distinct from
the stack, and pass a pointer to that array.

> And for compiled programs I'm thinking
>about trying to optimize the code to eliminate continuations
>possibly at the expense of code size. I haven't really thought about
>it that much yet though. I'll probably go for some hybrid approach
>in the end as some continuations would probably be too difficult to
>replace with conventional structures depending on how the code is
>written.

It would seem to me to make more sense to provide conventional means of
expressing meaning, and if the programmer instead chooses to use a
continuation, assume they meant it. Continuations, like gotos, can express
things which cannot be expressed using structured code -- and conversely,
things which can be expressed with structured code generally should not be
expressed using continuations. In other words, I would actually consider
doing the reverse: don't eliminate continuations, instead provide structures
which actually can compile to continuations.

I can see the point of view of Lisp's designers in not including
continuations, just as many other languages chose not to include gotos.
Continuations can be viewed as a low-level detail to many possible
structures, and many people don't believe low-level things belong in
high-level languages. Personally, I don't believe that; I simply believe
that it should be possible to craft a language into something that matches
your problem, and to me low-level things are just as eligible for use in the
solution as anything else.

>Ivan

-Billy

Tanksley, William D. Jr. scripsit:

> I can see the point of view of Lisp's designers in not including
> continuations, just as many other languages chose not to include gotos.
> Continuations can be viewed as a low-level detail to many possible
> structures, and many people don't believe low-level things belong in
> high-level languages.

AFAIK continuations were excluded from Common Lisp because they were believed
to be too expensive in optimized implementations (they are fairly cheap in
unoptimized ones, but the cost is swamped by everything else). Scheme has
always had continuations, and nobody calls Scheme a low-level language,
though it is understood that it pays to wrap them in easier-to-use
constructs such as generators, coroutines, and backtracking.

--
John Cowan <jcowan@...> http://www.ccil.org/~cowan
"One time I called in to the central system and started working on a big
thick 'sed' and 'awk' heavy duty data bashing script. One of the geologists
came by, looked over my shoulder and said 'Oh, that happens to me too.
Try hanging up and phoning in again.'" --Beverly Erlebacher

From: John Cowan [mailto:cowan@...]

>Tanksley, William D. Jr. scripsit:

>>I can see the point of view of Lisp's designers in not including
>>continuations, just as many other languages chose not to
>>include gotos.
>>Continuations can be viewed as a low-level detail to many possible
>>structures, and many people don't believe low-level things belong in
>>high-level languages.

>AFAIK continuations were excluded from Common Lisp because
>they were believed to be too expensive in optimized
>implementations (they are fairly cheap in unoptimized ones,
>but the cost is swamped by everything else).

They were accurately judged to be incompatible with many existing
implementations, and the implementations they would need for those were
judged to be too slow to require.

Continuations needn't be expensive.

> Scheme has
>always had continuations, and nobody calls Scheme a low-level language,
>though it is understood that it pays to wrap them in easier-to-use
>constructs such as generators, coroutines, and backtracking.

Lisp programmers consider Scheme a low-level language: it provides the atoms
you need to build high-level services, but provides few of the services
themselves.

>John Cowan <jcowan@...> http://www.ccil.org/~cowan

>"One time I called in to the central system and started
>working on a big thick 'sed' and 'awk' heavy duty data
>bashing script. One of the geologists came by, looked
>over my shoulder and said 'Oh, that happens to me too.
>Try hanging up and phoning in again.'" --Beverly Erlebacher

Never worked with TECO, J, K, or APL, huh? :-)

Here's a line of J code (which happens to be a complete function
definition):

flat=: < :. (}:@}."1@}:@}.)

HTH HAND.

I like J, but prefer K.

-Billy

On Wed, 20 Aug 2003, Tanksley, William D. Jr. wrote:

> From: John Cowan [mailto:cowan@...]
> >Tanksley, William D. Jr. scripsit:
> >John Cowan <jcowan@...> http://www.ccil.org/~cowan

[...]

> >"One time I called in to the central system and started
> >working on a big thick 'sed' and 'awk' heavy duty data
> >bashing script. One of the geologists came by, looked
> >over my shoulder and said 'Oh, that happens to me too.
> >Try hanging up and phoning in again.'" --Beverly Erlebacher
>
> Never worked with TECO, J, K, or APL, huh? :-)

Sacriledge! Don't mention TECO in the same paragraph as
sed, awk, J, K or APL! Us old hands who have the TECO manual
in out fingertips don't like it! What other language allows
you to do day to day editing, at the end of a course adding
up the marks for all students, and writing self-compiling
compilers! :-(

- Manfred

--- In concatenative@yahoogroups.com, "Tanksley, William D. Jr."
<william.d.tanksley.jr@s...> wrote:

> In Forth, partial continuations are easy (although the ANSI

standard doesn't

> provide promises that they'll work on every machine), but first-

class

> partial continuations are hard. "mlg", at

http://www.forth.org.ru/~mlg/,

> describes a backtracking system based on partial continuations,

with the

> added twist of being able to manipulate individual return

addresses (a

> classical Forth ability). Mlg has also done some other work in

Forth

> continuations, and I found his source code illuminating (but

challenging).

It definitley is challenging. I went through his code and
documentation a few times but I think I'll have to spend more time
analyzing it in detail before I figure out exactly how it works.
Right now I'm busy finishing my entry for a certain programming
competition (http://www.beyond3d.com/articles/shadercomp/) so it'll
have to wait :)

>
> >An old version of Meta/4 does something like that. I don't know

> >you had a look at it yet but cont and xcc words in prim3.inc

pretty

> >much work in the way you described.
>
> I've read through some of it, and I like it (I didn't see that

part).

>

If anyone else is interested in having a look at it I'd be glad to
put it up somewhere.

> >I've given up on that for now though. For interpretation I

believe

> >using 3 stacks has a few advantages (simplicity and clarity are
> >probably the main ones).
>
> I see too many problems, actually. Using an instruction stack is

interesting

> and novel, but isn't needed; conventional execution does the same

thing.

> Using a continuation stack can actually cause problems, since the
> continuation stack is actually tied to the instruction stack in

subtle ways.

>

So far I've only played around with trivial continuations. I'll have
to do more reading before I can understand the limitations and ways
to solve them.

> > And for compiled programs I'm thinking
> >about trying to optimize the code to eliminate continuations
> >possibly at the expense of code size. I haven't really thought

about

> >it that much yet though. I'll probably go for some hybrid

approach

> >in the end as some continuations would probably be too difficult

> >replace with conventional structures depending on how the code is
> >written.
>
> It would seem to me to make more sense to provide conventional

means of

> expressing meaning, and if the programmer instead chooses to use a
> continuation, assume they meant it. Continuations, like gotos, can

express

> things which cannot be expressed using structured code -- and

conversely,

> things which can be expressed with structured code generally

should not be

> expressed using continuations. In other words, I would actually

consider

> doing the reverse: don't eliminate continuations, instead provide

structures

> which actually can compile to continuations.
>

I probably didn't clarify what I meant by eliminating continuations
using conventional structures. I was referring to the compiler
replacing trivial continuations with jumps. I'm sure that more
complex continuations would be too hard and impractical to optimize
in such a way though. Essentially I think that is covered by what
you called an aggressively evaluated concatenative language.

> -Billy

Ivan

i find this stuff very hard to think about. apparently some
people don't, and i'd really like to understand why. (for
that reason, i've started down the scheme road, where it seems
much of this work has been done.)

at this point, i'm working with the following "structural"
assumptions:

1. primitives and programs take and return triples x y z.
x is the data stack and y is the instruction stack. z is
either null or a triple (possibly nested in the third
position). the way i've implemented x and y, the last
element of x is the most recent, and the first element of
y is the next. e.g. if the program is 2 3 4 5 + * -, and
you've executed up to and including the '+', then

x = 2 3 9
y = * -

i just find it easier to think about

... 2 3 9 * - ...

2. the evaluator takes x y z and pops the first element from
y. if y isn't executable, it appends it to x, else it
executes it on x y z to get a new x' y' z'.

currently, i have the operations 'cc' which takes x y z and
returns x y (x y z), and 'c' which takes x y (x' y' z') and
returns x'' y' z', where x'' is (-1_ x'),-1#x, which is k
for the result of replacing the last element of x' with the
last element of x. e.g. if x y (x' y' z') is

(10 20 30) y ((40 50) y' z')

then the result of applying 'c' is

(40 30) y' z'

i've been experimenting with various ways to directly manipulate
x y z triples. for example, the operation 'xyz' pops the first
element from the data stack, which is assumed to be an x y z
triple, and returns it. this is (or looks like) 'goto'. the 'z'
operation takes x y z and returns x' y z, where x' is the result
of appending z to x. so e.g. 'cc' followed by 'z' puts what 'cc'
cached in z onto the data stack. at that point it can be
manipulated. then 'xyz' can return it.

is this an adequate framework for modelling continuations?
subcontinuations? or perhaps i shouldn't ask the question
that way. perhaps what i should ask is this: given the
framework, can we define an operational vocabulary to manipulate
flow-of-control in useful ways?

the current state of things is in www.nsl.com/k/tck.k

----- Original Message -----
From: "Tanksley, William D. Jr." <william.d.tanksley.jr@...>
To: <concatenative@yahoogroups.com>
Sent: Wednesday, August 20, 2003 2:11 PM
Subject: RE: [stack] Re: continuations in a tiny concatenative language

> From: Ivan Tomac [mailto:e1_t@...]
> ><william.d.tanksley.jr@s...> wrote:
>
> >>My implementation, as usual, won't do exactly this. Let me provide
> >>a little background. I apologise in advance for destroying your
> >>sanity, but:
> >> http://citeseer.nj.nec.com/hieb93subcontinuations.html
> >> http://citeseer.nj.nec.com/queinnec91dynamic.html
>
> >Interesting. I'll have to read those papers sometime.
>
> In short, the articles point out that traditional continuations give you
> only limited control: you can return control to an earlier point in the
> program's execution, but you can't _call_ that earlier point (i.e. control
> never returns to you), and the programmer can't specify where the
> continuation _ends_ (in essence, every continuation ends at the command
> prompt).
>
> The solution documented in these papers is to provide a way to mark the
> start of a "subcontinuation", AKA a "partial continuation", and allow the
> programmer to save and call partial continuations. This allows much finer
> control.
>
> In Forth, partial continuations are easy (although the ANSI standard doesn't
> provide promises that they'll work on every machine), but first-class
> partial continuations are hard. "mlg", at http://www.forth.org.ru/~mlg/,
> describes a backtracking system based on partial continuations, with the
> added twist of being able to manipulate individual return addresses (a
> classical Forth ability). Mlg has also done some other work in Forth
> continuations, and I found his source code illuminating (but challenging).
>
> >An old version of Meta/4 does something like that. I don't know if
> >you had a look at it yet but cont and xcc words in prim3.inc pretty
> >much work in the way you described.
>
> I've read through some of it, and I like it (I didn't see that part).
>
> >I've given up on that for now though. For interpretation I believe
> >using 3 stacks has a few advantages (simplicity and clarity are
> >probably the main ones).
>
> I see too many problems, actually. Using an instruction stack is interesting
> and novel, but isn't needed; conventional execution does the same thing.
> Using a continuation stack can actually cause problems, since the
> continuation stack is actually tied to the instruction stack in subtle ways.
>
> It makes more sense to me to use two stacks, one for data and one for return
> addresses, and since return addresses completely describe continuations, tag
> the return stack to indicate where continuations start and end. As I've
> said, making this first-class is hard in Forth, but in an array or
> list-based language it's simple -- just dump the portion of the return stack
> indicated by the continuation markers into an array or list distinct from
> the stack, and pass a pointer to that array.
>
> > And for compiled programs I'm thinking
> >about trying to optimize the code to eliminate continuations
> >possibly at the expense of code size. I haven't really thought about
> >it that much yet though. I'll probably go for some hybrid approach
> >in the end as some continuations would probably be too difficult to
> >replace with conventional structures depending on how the code is
> >written.
>
> It would seem to me to make more sense to provide conventional means of
> expressing meaning, and if the programmer instead chooses to use a
> continuation, assume they meant it. Continuations, like gotos, can express
> things which cannot be expressed using structured code -- and conversely,
> things which can be expressed with structured code generally should not be
> expressed using continuations. In other words, I would actually consider
> doing the reverse: don't eliminate continuations, instead provide structures
> which actually can compile to continuations.
>
> I can see the point of view of Lisp's designers in not including
> continuations, just as many other languages chose not to include gotos.
> Continuations can be viewed as a low-level detail to many possible
> structures, and many people don't believe low-level things belong in
> high-level languages. Personally, I don't believe that; I simply believe
> that it should be possible to craft a language into something that matches
> your problem, and to me low-level things are just as eligible for use in the
> solution as anything else.
>
> >Ivan
>
> -Billy
>
>
> To unsubscribe from this group, send an email to:
> concatenative-unsubscribe@egroups.com
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>

phimvt@... scripsit:

> > >"One time I called in to the central system and started
> > >working on a big thick 'sed' and 'awk' heavy duty data
> > >bashing script. One of the geologists came by, looked
> > >over my shoulder and said 'Oh, that happens to me too.
> > >Try hanging up and phoning in again.'" --Beverly Erlebacher
> >
> > Never worked with TECO, J, K, or APL, huh? :-)
>
> Sacriledge! Don't mention TECO in the same paragraph as
> sed, awk, J, K or APL! Us old hands who have the TECO manual
> in out fingertips don't like it! What other language allows
> you to do day to day editing, at the end of a course adding
> up the marks for all students, and writing self-compiling
> compilers! :-(

Well, Emacs -- it's a wise child that knows its own father.

I have hacked TECO, sed, and awk heavily, and APL casually. One of my
back-burner projects is to write a Unicode-aware TECO engine in Java.
As for my name, it jumps to the beginning of the buffer and then
crashes on the non-existent label "HN COWAN". Which I admit is not
as cool as executing Q-register A, loading the next page, and attempting
to read from a file named "ED VON THUN", probably without success.

Beverly Erlebacher, BTW, is a friend of mine and the author of the
texi2roff TeX-to-[nt]roff translator.

--
They do not preach John Cowan
that their God will rouse them jcowan@...
A little before the nuts work loose. http://www.ccil.org/~cowan
They do not teach http://www.reutershealth.com
that His Pity allows them --Rudyard Kipling,
to drop their job when they damn-well choose. "The Sons of Martha"

From: stevan apter [mailto:sa@...]

>i find this stuff very hard to think about. apparently some
>people don't, and i'd really like to understand why. (for
>that reason, i've started down the scheme road, where it seems
>much of this work has been done.)

I'm not personally aware of anyone who actually finds continuations easy to
think about. Some of their subsets are reasonably workable (backtracking,
generators, or coroutines, for example, can be individually mastered), but
the full power of the whole thing is just too much.

But yes, Scheme is a great place to look for people who've studied it and
understand it. The one warning is that few of them have worked with partial
continuations -- that's not part of their language. Forth is the only
production language I know of in which anything like partial continuations
is used -- and at that, its method is only _somewhat_ like continuations,
and it's an advanced technique that the ANSI standard doesn't promise will
work.

(Specifically, Forth's normal technique is to pop return addresses off the
stack and play with them as partial continuations -- this works nicely
unless the Forth compiler does tail-call elimination or some other function
in the call stack has done the same thing before you got to it.)

>at this point, i'm working with the following "structural"
>assumptions:

>1. primitives and programs take and return triples x y z.

Excellent. In Forth all words take and return pairs (d r), data and return
stack.

>currently, i have the operations 'cc' which takes x y z and
>returns x y (x y z), and 'c' which takes x y (x' y' z') and
>returns x'' y' z', where x'' is (-1_ x'),-1#x, which is k
>for the result of replacing the last element of x' with the
>last element of x. e.g. if x y (x' y' z') is
> (10 20 30) y ((40 50) y' z')
>then the result of applying 'c' is
> (40 30) y' z'

>i've been experimenting with various ways to directly manipulate
>x y z triples. for example, the operation 'xyz' pops the first
>element from the data stack, which is assumed to be an x y z
>triple, and returns it. this is (or looks like) 'goto'.

May I assume that when you say "returns it" you mean "loads it into the xyz
variables"? If so, then yes; it's like a goto that COMPLETELY specifies the
machine's state. A pure goto would only alter the 'y' variable.

>the 'z'
>operation takes x y z and returns x' y z, where x' is the result
>of appending z to x. so e.g. 'cc' followed by 'z' puts what 'cc'
>cached in z onto the data stack. at that point it can be
>manipulated. then 'xyz' can return it.

Yes, I see what you mean. Yes, that's a way to call a continuation.

>is this an adequate framework for modelling continuations?

Yes, definitely.

>subcontinuations?

Probably not; it's storing too much state.

> or perhaps i shouldn't ask the question
>that way. perhaps what i should ask is this: given the
>framework, can we define an operational vocabulary to manipulate
>flow-of-control in useful ways?

Yes.

-Billy

i'm relieved that someone understands what i'm saying. i was
starting to think that my drug-addled adolescence had returned
with a vengeance. ah well, can't alter the past -- (unless ...
nah!)

From: stevan apter [mailto:sa@...]

>i find this stuff very hard to think about. apparently some
>people don't, and i'd really like to understand why. (for
>that reason, i've started down the scheme road, where it seems
>much of this work has been done.)

>at this point, i'm working with the following "structural"
>assumptions:

>1. primitives and programs take and return triples x y z.

Excellent. In Forth all words take and return pairs (d r), data and return
stack.

>currently, i have the operations 'cc' which takes x y z and
>returns x y (x y z), and 'c' which takes x y (x' y' z') and
>returns x'' y' z', where x'' is (-1_ x'),-1#x, which is k
>for the result of replacing the last element of x' with the
>last element of x. e.g. if x y (x' y' z') is
> (10 20 30) y ((40 50) y' z')
>then the result of applying 'c' is
> (40 30) y' z'

Interesting. Your continuation includes almost the entire data stack. That
won't work with partial continuations, and it'll make full continuations
rather limited unless you provide words to manipulate the data stack of a
continuation. Rather than do that, though, I would personally recommend not
saving the data stack at all; let the programmer set it up at will, since
that's where much of the power of continuations comes from.

if the continuation of + in 2 3 4 + * 6 % is an f which
takes 2 7 and computes * 6 %, then it must contain the
data stack. or have i misunderstood something - is the
continuation of + merely a function * 6 % which takes
*something* (whatever that is) and continue on with that?

In other words, have 'c' take: xyz--xy[yz], and 'cc' take xy[ab]--xa[b].

i think you've got 'c' and 'cc' backwards, but still,
that has a wonderfully simplifying effect on the code:

cc:{(x;y;(y;z)}
c:{(x;*z;z)}

and my examples still work. but can you really discard
the data stack like that?

>i've been experimenting with various ways to directly manipulate
>x y z triples. for example, the operation 'xyz' pops the first
>element from the data stack, which is assumed to be an x y z
>triple, and returns it. this is (or looks like) 'goto'.

May I assume that when you say "returns it" you mean "loads it into the xyz
variables"?

yes

If so, then yes; it's like a goto that COMPLETELY specifies the
machine's state. A pure goto would only alter the 'y' variable.

>the 'z'
>operation takes x y z and returns x' y z, where x' is the result
>of appending z to x. so e.g. 'cc' followed by 'z' puts what 'cc'
>cached in z onto the data stack. at that point it can be
>manipulated. then 'xyz' can return it.

Yes, I see what you mean. Yes, that's a way to call a continuation.

>is this an adequate framework for modelling continuations?

Yes, definitely.

>subcontinuations?

Probably not; it's storing too much state.

how about now? can you frame a problem involving subcontinuations?

> or perhaps i shouldn't ask the question
>that way. perhaps what i should ask is this: given the
>framework, can we define an operational vocabulary to manipulate
>flow-of-control in useful ways?

Yes.

thanks

-Billy

To unsubscribe from this group, send an email to:
concatenative-unsubscribe@egroups.com

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

>i find this stuff very hard to think about. apparently some

Stevan,

I felt the same until I stumbled into a real world example:
Christan Queinnec described the interaction of a web user with the
server as a multiple continuation (and also a long transaction, by the
way):
"The Influence of Browsers on Evaluators or, Continuations to Program
Web Servers (2000)". CiteSeer has it in several formats:
http://citeseer.nj.nec.com/queinnec00influence.html

Eberhard

On Sat, 30 Aug 2003 23:43, e7l3 wrote:

> "The Influence of Browsers on Evaluators or, Continuations to Program
> Web Servers (2000)". CiteSeer has it in several formats:
> http://citeseer.nj.nec.com/queinnec00influence.html

If you're interested I list some papers and examples of continuation based web
servers at:

http://radio.weblogs.com/0102385/2003/08/30.html

Chris.
--
http://www.double.co.nz

RE: [stack] Re: continuations in a tiny concatenative language

Tanksley, William D. Jr. — 2003-08-20 18:11:38

John Cowan — 2003-08-20 19:01:57

Tanksley, William D. Jr. — 2003-08-20 19:29:46

phimvt@lurac.latrobe.edu.au — 2003-08-21 06:52:25

Ivan Tomac — 2003-08-21 10:20:24

stevan apter — 2003-08-21 13:00:03

John Cowan — 2003-08-21 16:12:41

Tanksley, William D. Jr. — 2003-08-21 18:42:45

sa@dfa.com — 2003-08-21 19:14:07

e7l3 — 2003-08-30 11:43:34

Chris Double — 2003-08-30 12:15:46