separate stacks

I note that Forth has traditionally had 2 stacks - data and return.

Then came the float stack.

Then, there has been further separation with a locals stack, and even an
'object' stack for forths with OO capability.

What do people think about this separation of stacks? Does it clutter the
thinking to separate out locals and objects into their own stacks, or is
it more of a help?

DavidM wrote:
> I note that Forth has traditionally had 2 stacks - data and return.
>
> Then came the float stack.
>
> Then, there has been further separation with a locals stack, and even an
> 'object' stack for forths with OO capability.
>
> What do people think about this separation of stacks? Does it clutter the
> thinking to separate out locals and objects into their own stacks, or is
> it more of a help?

In the implementations I'm familiar with, locals are implemented on the
Return Stack, and objects do not have a separate stack. I know some
people have experimented with separate loop stacks and other things, but
IMO they don't offer sufficient advantages to justify the added code
complexity.

A separate float stack solves two problems: dealing with the cumbersome
additional size of IEEE fp numbers, and enabling use of hardware fp
stacks, both very worthwhile objectives.

Cheers,
Elizabeth

--
==================================================
Elizabeth D. Rather (US & Canada) 800-55-FORTH
FORTH Inc. +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================

Elizabeth D Rather <erather@forth.com> writes Re: separate stacks

> DavidM wrote:
>> I note that Forth has traditionally had 2 stacks - data and return.

>> Then came the float stack.

>> Then, there has been further separation with a locals stack, and even an
>> 'object' stack for forths with OO capability.
[..]
> In the implementations I'm familiar with, locals are implemented on the
> Return Stack, and objects do not have a separate stack. I know some
> people have experimented with separate loop stacks and other things, but
> IMO they don't offer sufficient advantages to justify the added code
> complexity.

For simple implementations it doesn't matter, but locals on a separate
stack are easier to optimize; e.g.

iForth version 3.0.15, generated 22:47:30, July 28, 2008.
x86 binary, native floating-point, double precision.
Copyright 1996 - 2008 Marcel Hendrix.

FORTH> variable d ok
FORTH> d H. $00558E50 ok
FORTH> : foo { a b c } a b + c * a xor c and d ! ; ok
FORTH> : test 1 2 3 foo d @ . ; ok
FORTH> see test
Flags: ANSI
$00559300 : test
$00559308 mov $00558E50 dword-offset, 0 d#
$00559312 push $00558E50 dword-offset
$00559318 jmp .+8 ( $00482068 ) offset NEAR

( foo completely optimized away as its result can be pre-computed to be 0 )

> A separate float stack solves two problems: dealing with the cumbersome
> additional size of IEEE fp numbers, and enabling use of hardware fp
> stacks, both very worthwhile objectives.

-marcel

Elizabeth D Rather <erather@forth.com> wrote:
> DavidM wrote:

> > I note that Forth has traditionally had 2 stacks - data and
> > return.
> >
> > Then came the float stack.
> >
> > Then, there has been further separation with a locals stack, and
> > even an 'object' stack for forths with OO capability.
> >
> > What do people think about this separation of stacks? Does it
> > clutter the thinking to separate out locals and objects into their
> > own stacks, or is it more of a help?

> In the implementations I'm familiar with, locals are implemented on
> the Return Stack, and objects do not have a separate stack. I know
> some people have experimented with separate loop stacks and other
> things, but IMO they don't offer sufficient advantages to justify
> the added code complexity.

Sometimes, though, a stack can be a useful data abstraction when
writing applications. For example, I've used a string stack when
parsing application-specific languages, and it works really well.
In general, though, I agree with you: separate loop stacks, etc., are
a mistake.

Andrew.

Fist was the program stack which instructions were poped from one by
one, then a data stack seemed a useful idea, then return addresses
were clogging the data stack, and so processors implemented subrotine
calls, and the return stack arrived, the data stack got lost a while
in the expansion of the register file, but came back with java. Then a
split float stack came for the number crunchers, and an object stack
with stacks on. IIRC.

jacko wrote:
> Fist was the program stack which instructions were poped from one by
> one, then a data stack seemed a useful idea, then return addresses
> were clogging the data stack, and so processors implemented subrotine
> calls, and the return stack arrived, the data stack got lost a while
> in the expansion of the register file, but came back with java. Then a
> split float stack came for the number crunchers, and an object stack
> with stacks on. IIRC.

I'm not sure what's your frame of reference here. Are you talking about
the history of computing in general, or Forth? I'm not sure I've ever
encountered a "program stack", and float stacks precede Java, I think.

Cheers,
Elizabeth

--
==================================================
Elizabeth D. Rather (US & Canada) 800-55-FORTH
FORTH Inc. +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================

On 2008-08-02, Andrew Haley <andrew29@littlepinkcloud.invalid> wrote:
> Elizabeth D Rather <erather@forth.com> wrote:
>> DavidM wrote:
>
>> > I note that Forth has traditionally had 2 stacks - data and
>> > return.
>> >
>> > Then came the float stack.
>> >
>> > Then, there has been further separation with a locals stack, and
>> > even an 'object' stack for forths with OO capability.
>> >
>> > What do people think about this separation of stacks? Does it
>> > clutter the thinking to separate out locals and objects into their
>> > own stacks, or is it more of a help?
>
>> In the implementations I'm familiar with, locals are implemented on
>> the Return Stack, and objects do not have a separate stack. I know
>> some people have experimented with separate loop stacks and other
>> things, but IMO they don't offer sufficient advantages to justify
>> the added code complexity.
>
> Sometimes, though, a stack can be a useful data abstraction when
> writing applications. For example, I've used a string stack when
> parsing application-specific languages, and it works really well.
> In general, though, I agree with you: separate loop stacks, etc., are
> a mistake.
>
> Andrew.

i propose a stack stack. a single stack stack for now. but later i may
have to add a second stack stack. ([wink])
--
r

Elizabeth D Rather <erather@forth.com> wrote:
> DavidM wrote:
>
> > What do people think about this separation of stacks? Does it
> > clutter the thinking to separate out locals and objects into their
> > own stacks, or is it more of a help?
>
> In the implementations I'm familiar with, locals are implemented on
> the Return Stack, and objects do not have a separate stack. I know
> some people have experimented with separate loop stacks and other
> things, but IMO they don't offer sufficient advantages to justify the
> added code complexity.

I just stopped to wonder, how much extra complexity would it take to
implement DO loops on the return stack like locals?

People talk like locals have hardly any runtime costs. If you could put
do loop parameters at the bottom of the word's return stack usage, with
the locals, they'd be better because the top of the return stack would
be free. I see no downside at all unless there's a performance penalty.

On Sat, 02 Aug 2008 17:52:01 -0400, Jonah Thomas wrote:

> I just stopped to wonder, how much extra complexity would it take to
> implement DO loops on the return stack like locals?

IMHO it's not very complex at all. I've done it in aumForth.

What I do is keep a compile-time variable which measures the total number
of data elements in the return stack. So then, it's possible to have a
break or exit anywhere inside any control structures, and the compiler
will know out how much data is on the return stack and generate code to
'pop n data cells' from the return stack prior to breaking.

In fact, my 'unloop' word is a no-op because it's unnecessary, and I just
have it there for ANS compatibility.

> People talk like locals have hardly any runtime costs.

The question of whether locals have significant runtime costs is
determined by the size of the word def in which they occur, and/or the
cost of the stack-juggling which would be needed to perform the same task
without locals.

If a word has simple control structures and only a tiny number of
invocations of other words, and especially if this word is invoked inside
a tight loop, then the performance penalty of locals will be high. But if
a word has long code paths and takes up a screenful of source code
(indented control structures etc), then the cost of locals would be
pretty insignificant, and would give a huge saving in other ways such as
code maintainability, programmer sanity etc.

> If you could put
> do loop parameters at the bottom of the word's return stack usage, with
> the locals, they'd be better because the top of the return stack would
> be free. I see no downside at all unless there's a performance penalty.

That's the solution I like. Especially since one can then flip stuff
around on the data stack without having to worry about the loop variables.

On Aug 2, 8:03*am, m...@iae.nl (Marcel Hendrix) wrote:
> FORTH> variable d *ok
> FORTH> d H. $00558E50 ok
> FORTH> : foo { a b c } *a b + *c * *a xor *c and *d ! ; *ok
> FORTH> : test 1 2 3 foo *d @ . ; *ok
> FORTH> see test
> Flags: ANSI
> $00559300 *: test
> $00559308 *mov * * * * * $00558E50 dword-offset, 0 d#
> $00559312 *push * * * * *$00558E50 dword-offset
> $00559318 *jmp * * * * * .+8 ( $00482068 ) offset NEAR
>
> ( foo completely optimized away as its result can be pre-computed to be 0)

Can you explain why it is easier to perform constant folding on locals
compared to stack code?

Can iForth prove that the following word always outputs 4?

: foo ( a -- b ) dup 0 < if dup xor 3 + else drop 3 then 1 + ;

Slava