stevan apter — 2003-06-28 13:25:18

have you considered implementing joy using continuation-passing?

john? have you thought about this for the functional rewrite of
your scheme implementation?

----- Original Message -----
From: "symstym" <symstym@...>
To: <concatenative@yahoogroups.com>
Sent: Saturday, June 28, 2003 3:34 AM
Subject: [stack] SECD-like (explicit stack) machine for executing Joy?

> The problem I ran into is that in the current C implementation of Joy, evaluation of
> quotations (by combinators) is done using recursion in C. For example, the
> implementation of dip 'recursively' calls the exeterm function to execute the
> quotation it popped off the stack. So, the current state of execution (dare I say, the
> continuation?) is stored implicitly on the C stack.
>
> For my (C++) application, I want a Joy interpreter that does one small (O(1)?) unit of
> work each time I invoke it. This seems to imply that I need to do more explicit
> bookeeping on some kind of stack. I looked into SECD machines a bit, and I think I'm
> looking for something exactly like that: a simple machine where the evaluation of
> each instruction affects a simple transformation of the data structures, so there is no
> recursive invocation of the evaluation function.

Brent Kerby — 2003-06-28 18:25:12

> The problem I ran into is that in the current C implementation of Joy,

evaluation of

> quotations (by combinators) is done using recursion in C. For example,

the

> implementation of dip 'recursively' calls the exeterm function to execute

the

> quotation it popped off the stack. So, the current state of execution

(dare I say, the

> continuation?) is stored implicitly on the C stack.
>
> For my (C++) application, I want a Joy interpreter that does one small

(O(1)?) unit of

> work each time I invoke it.

I've rewritten this kind of Joy interpreter before (granted, it was only a
slow toy for the obfuscated C coding contest :-)). The easy way to do it is
to use two stacks: the ordinary data stack, and a code stack. Then, "i",
"map", "dip", "ifte", etc. can be implemented by doing a few manipulations
to the code stack (i.e., they _change_ what the upcoming instructions are).
For example, to execute

3 [foo] dip more-instructions

When executing the thing on the left, after the interpreter pushed 3 and
"foo" onto the stack, it would implement "dip" by modifying the upcoming
code from this:

more-instructions

to this:

foo 3 more-instructions

It's also possible to merge the code and data stacks together, by thinking
of an instruction pointer moving through the program and applying rewrite
rules, such as (to use the same example)

3 [foo] dip more-instructions --> foo 3 more-instructions

But that's probably not terribly useful ...

Anyhow, back to task ... In implementing "map", you could use this approach:
If we just did

[1 2 3 4] [foo]

then, "map" could be implemented by pushing the following instructions onto
the code stack:

1 foo 2 foo 3 foo 4 foo [] cons cons cons cons

Or, alternatively,

[] 1 foo tack 2 foo tack 3 foo tack 4 foo tack

where "tack" is a combinator that "tacks" the top item onto the list
beneath:

[B] [A] tack == [B [A]]

Since you want really O(1) time, map could also be implemented in a
bite-size manner:

[1 2 3] [foo] map 4 foo tack

or

1 foo [2 3 4] [foo] map cons

> Russ
> symstym@...

Of course, there are some efficiency issues to worry about with this method.
It would be nice, for example, if all those copies of "foo" in the above
example were only really copies of pointers. It seems feasible, but would
probably require some work.

- Brent

Russel Simmons — 2003-06-29 03:38:50

> I've rewritten this kind of Joy interpreter before (granted, it was only a
> slow toy for the obfuscated C coding contest :-)). The easy way to do it is
> to use two stacks: the ordinary data stack, and a code stack. Then, "i",
> "map", "dip", "ifte", etc. can be implemented by doing a few manipulations
> to the code stack (i.e., they _change_ what the upcoming instructions are).

Yeah, I actually thought of something like this a little while after I posted :) As far as
the follow-up work to be done for 'ifte' after the evaluation of the IF part, I discovered
the 'branch' word, which does the trick. I guess if there are other words like 'ifte' that
_don't_ already have a corresponding word like 'branch' (and it can't be built out of
other words) then the word set would have to be augmented.. no big deal. But there
is a detail about map and other combinators that needs to be considered (see below).

> It's also possible to merge the code and data stacks together, by thinking
> of an instruction pointer moving through the program and applying rewrite
> rules, such as (to use the same example)

It's interesting to think about the different possible equivalent implementations. It
seems like the two stack method is the simplest one to implement, but its not
obvious to me how the performance would compare with other implementations. As
you mentioned, it would probably come down to management of lists. Copying
pointers where possible, copy on write, or perhaps garbage collection.. although it
seems like it would be possible to avoid GC if done carefully. Well hopefully the
simplicity of the two stack design should make thinking about the memory
management easier.

> Anyhow, back to task ... In implementing "map", you could use this approach:
> If we just did
>
> [1 2 3 4] [foo]
>
> then, "map" could be implemented by pushing the following instructions onto
> the code stack:
>
> 1 foo 2 foo 3 foo 4 foo [] cons cons cons cons

Actually this and the other variations don't exactly match the behavior of Joy's map.
If foo eats down into the stack (e.g. foo = +) or leaves more than one value on top,
then the behavior will not generally be the same, because Joy's map basically saves
and restores the stack before the evaluation of each item in the list. I'm not sure that
map should necessarily have this behavior, but at least that's how it is in Joy. I think
that Martin said in his response that Monkey's behavious matches that of your
suggested map, in that it doesn't use "local" stacks. It is certainly easier to implement
that way, but I'm leaning towards the leniency of Joy's style. That would mean
pushing onto the code stack sequences to restore the stack.. not a big deal, just
perhaps slow. Other combinators that have the same problem would be ifte, infra,
etc.

Thanks for the help! I will let you guys know if I get it working happily.

now let's see if I can get the line wrapping right this time

Russ

Russel Simmons — 2003-06-29 08:23:55

> For example, to execute
>
> 3 [foo] dip more-instructions
>
> When executing the thing on the left, after the interpreter pushed

3 and

> "foo" onto the stack, it would implement "dip" by modifying the

upcoming

> code from this:
>
> more-instructions
>
> to this:
>
> foo 3 more-instructions

Actually I noticed a small problem with this.
If instead of '3', we had a sequence like '[+] first', leaving an unquoted operator or
combinator on the stack, the above will not work. After executing foo, when we get
to the '+' in the code stack, it will be executed rather than just pushed back on the
stack as we intended. I guess the solution would be to 'escape' non-literals with
something like '[non-literal] first' when we stick them in the code stack.

Russ

Brent Kerby — 2003-06-30 05:45:04

> > For example, to execute
> >
> > 3 [foo] dip more-instructions
> >
> > When executing the thing on the left, after the interpreter pushed 3 and
> > "foo" onto the stack, it would implement "dip" by modifying the upcoming
> > code from this:
> >
> > more-instructions
> >
> > to this:
> >
> > foo 3 more-instructions
>
> Actually I noticed a small problem with this.
> If instead of '3', we had a sequence like '[+] first', leaving an unquoted

operator or

> combinator on the stack, the above will not work. After executing foo,

when we get

> to the '+' in the code stack, it will be executed rather than just pushed

back on the

> stack as we intended. I guess the solution would be to 'escape'

non-literals with

> something like '[non-literal] first' when we stick them in the code stack.

Good point. Joy's semantics with these unquoted operators has always baffled
me a bit. As I see it, operators like 'first' that pull lists apart fall
into a different class from more well-behaved combinators like 'swap',
'dup', 'cons', 'cat', 'tack', etc. (In particular, these well-behaved
combinators could be implemented even if quotations were compiled programs,
whereas 'first' definitely requires that the program exist in its original
list-of-operators form). But, of course, first and unquoted operators are
useful, so by no means should we throw them out.

So then, here's another possible way of solving your problem, other than
using an escape ... When we do "[+] first", then there is something on the
stack, call it +' . (Perhaps it would be handy for Joy to have syntax
directly for unquoted operators so they don't have to be constructed
sneakily using 'first'). Anyhow, then when we do "[foo] dip", we can simply
push "foo +'" onto the instruction stream, like normal. This presumes then
that the interpreter can handle +' , so we have to augment the language a
bit (well, I suppose it could all be internal, if desired), but that doesn't
seems too bad.

> Russ

- Brent

phimvt@lurac.latrobe.edu.au — 2003-07-02 02:42:02

On Sun, 29 Jun 2003, Brent Kerby wrote:

[...]

> Good point. Joy's semantics with these unquoted operators has
always baffled
> me a bit. As I see it, operators like 'first' that pull lists apart fall
> into a different class from more well-behaved combinators like 'swap',
> 'dup', 'cons', 'cat', 'tack', etc.

Example: In a particular family there are children [peter paul mary]
and pets [dup dip pop] and kitchen tables [square round] and for
the next month guests will be expected on the dates [3 8 17 22 29].
In each case, to get the first item of the respective lists you
use the 'first' operator. This will always work, even though 'dup'
is a Joy builtin and 'square' is defined in a library. It will
continue to work even if in the future 'peter' becomes a builtin
or is defined in a library. All pretty regular, I think.

[...]

> So then, here's another possible way of solving your problem, other
than
> using an escape ... When we do "[+] first", then there is something on the
> stack, call it +' .

This postfix quote may be OK for the program, but what ends up on the
stack should not be this quoted thing. One would want to be able to
cons the top item into another list/quotation, maybe to be executed,
maybe to be written. If the quoted thing ends up on the stack, then
you need another dequote operation to be able to cons it into something
else.

One may very well want a unary quotation operator, say your postfix
quote or a prefix Q. Note that this is a different sense of 'unary',
not the sense in which 'rest', 'not', 'square' are (semantically)
unary. Whatever the exact notation used, "+'" or "Q+" or "Q +" will
be an atom which pushes the (binary) addition operator, or whatever
the argument of the "'" or "Q" is. So in general,
[foo] first == foo' == Q foo
But the "'" or "Q" cannot stand on their own, they need an atom
as an argument to become syntactically correct. In the grammar
there would need to be another production:
factor ::= "Q" factor
This raises the question of what 'Q Q Q foo' should mean.
Perhaps the same as 'Q foo'. The implementation of Q would not
be quite as trivial as it may look, even just for single Q's,
because Q is not just another atom. Is it worth it ?

[...]

> (Perhaps it would be handy for Joy to have syntax
> directly for unquoted operators so they don't have to be constructed
> sneakily using 'first').

You are not persuaded? You don't like sneaky Joy? You want Yacl :

YACL = Yet Another Concatenative Language

Every syntactically correct Joy program is also a syntactically
correct Yacl program. The difference is in the semantics. What
in Joy are called operators and combinators are exactly like
literals in Yacl: when executed they result in a push operation.
So after the execution of
5 dup *
the stack will contain three items: '*' on top, 'dup' second,
and '5' third. (So execution is a bit like reversal, if you think
of the stack as a list). Quotations are left untouched, so
[1 2] [foo bar] concat
result in a stack of three items, 'concat' on top, '[foo bar]'
second, '[1 2]' third.

What is the point, you ask? Well, everything is treated as if it
were quoted, either as '[foo] first' or as "foo'" or as "Q foo"
So there is no need for the unary quotaion operator in Yacl.

But how does Yacl do any computation, like the square or 5 ?
Easy: There is another atom, not a unary operator, called 'E'
for 'execute'. The square of 5 is computed by either
5 dup E * E
or 5 E dup E * E
Semantically the E executes the top single item on the stack in
the same way that Joy would. If that item is an operator or combinator
E will execute it as such. If that item is a literal such as 5,
then E will push it on the stack. So for literals x, x E == x.
One could define such an E in Joy as E == [] cons i, of course,
and the little joy-in-joy uses something like that. But E in Joy
would be rarely used, in Yacl it is essential. One more example:
[1 2 3 4] [dup E * E] map E ==> [1 4 9 16]
In the now very exceptional case where you actually want the E
on top of the stack you would need '[E] first E', unless you
want to introduce a unary quotation operator: "E'" or "Q E".

End-of-Yacl-manual

Thank you all, I really enjoy (!) these discussions.

- Manfred

Nick Forde — 2003-07-02 09:09:47

Hi Russel,

Russel Simmons writes:

> > I've rewritten this kind of Joy interpreter before (granted, it was only a
> > slow toy for the obfuscated C coding contest :-)). The easy way to do it is
> > to use two stacks: the ordinary data stack, and a code stack. Then, "i",
> > "map", "dip", "ifte", etc. can be implemented by doing a few manipulations
> > to the code stack (i.e., they _change_ what the upcoming instructions are).
>
> Yeah, I actually thought of something like this a little while after I posted :) As far as
> the follow-up work to be done for 'ifte' after the evaluation of the IF part, I discovered
> the 'branch' word, which does the trick. I guess if there are other words like 'ifte' that
> _don't_ already have a corresponding word like 'branch' (and it can't be built out of
> other words) then the word set would have to be augmented.. no big deal. But there
> is a detail about map and other combinators that needs to be considered (see below).

Some time ago I did a quick and dirty port of the C Joy interpreter to
PalmOS. The interpreter's use of the C stack was the first thing I had
to change due to both OS stack size limits and the need to respond to
UI events from the user, e.g. to stop running a program.

I also used a "code" stack but didn't get much further than updating a
few of the recurisive primitives. At the same time I did some
performance profiling and found that often instruction dispatch time
was significant. I think this could be significantly reduced by
implementing a few common VM optimisation techniques. In particular
converting the main execution loop to threaded code, caching the
top-of-stack in a register, and using superinstructions for common
bytecode sequences.

> Thanks for the help! I will let you guys know if I get it working happily.

I'd love to hear how you get on. Given a little free time I'd like to
resurrect the PalmOS port I started and am sure I could learn from
your experiences in reimplementing the recursive primitives.

Good luck.

Regards,

Nick.

John Cowan — 2003-07-03 16:46:52

phimvt@... scripsit:

> One may very well want a unary quotation operator, say your postfix
> quote or a prefix Q. Note that this is a different sense of 'unary',
> not the sense in which 'rest', 'not', 'square' are (semantically)
> unary. Whatever the exact notation used, "+'" or "Q+" or "Q +" will
> be an atom which pushes the (binary) addition operator, or whatever
> the argument of the "'" or "Q" is. So in general,

We already can say "+" intern to push a raw + on the stack. You can
even build up operator names this way: "p" "op" concat intern [] i
will do a pop.

--
Do what you will, John Cowan
this Life's a Fiction jcowan@...
And is made up of http://www.reutershealth.com
Contradiction. --William Blake http://www.ccil.org/~cowan

Re: [stack] SECD-like (explicit stack) machine for executing Joy?