# Notes on work in progress, and thoughts on reducing stack-fiddling.

## Chris Cogan — 2004-09-08 03:44:10

    Hi. I see I'm not the only one who hasn't been very active on this list

    lately.

    Worse, for me, I haven't been able to devote much of my work time to the Joy

    implementation in Visual Basic .NET for the past couple of weeks, so I've

    had to work on it mostly in the evenings and weekends.

    Two main sections follow, one with some notes and remarks on my

    implementation of Joy, and one on various ideas for reducing

    programmer-overhead with respect to the stack.

    ==== Notes on My Implementation of Joy in Visual Basic .NET ====

    Worse still, I keep almost getting it to work and then finding things to do

    to improve it and end up having to work back up to the level of functioning

    I had previously achieved. Most recently, I realized that I only need to

    carry around my own type indicator until each item is compiled, and then I

    can use Visual Basic's own type-determining functions. This means I don't

    have to put a multiple-member object on the stack when all I really want to

    do is push a number or string, etc., which should improve the efficiency of

    the pushing and popping operations considerably, since I only need to push

    and pop the values themselves (at least from the point of view of the

    programmer).

    (Of course, I'm not doing real compilation, but I am compiling to a kind of

    threaded code in which each code element is a multi-member object, with one

    member being the function (a Sub, actually, in Visual Basic) to be executed

    at run-time. Aside from the primitives, there are two internal functions,

    one of which is assigned to the run-time member at compilation-time:

      1.. One is for literals, which is just a function to push the value of the

    literal.

      2.. One is for user-defined functions (everything that is not "hard-coded"

    in Basic). This is just a Sub that calls the inner interpreter, passing it

    the threaded code associated with the defined atom.

    Here they are:

    Public Sub UDefXeq() 'User-Defined

    Xeq(Value)

    End Sub

    Public Sub LitXeq()  'Literal

    Push(Value)

    End Sub

    For all the primitives, a "delegate" is used. A delegate is the Visual

    Studio mechanism for doing what would be called pointers to functions in C.

    Here's the inner interpreter, with all the tracing stuff removed so you can

    see the core of it:

    Sub Xeq(ByRef CodeArray() As CodeElem)

    Dim I As Long

    For I = 0 To Ubound(CodeArray)

    CodeArray(I).Rx()

    If AbortFlag Then Exit For

    Next

    End Sub

    Because Visual Studio languages have their own built-in garbage collection,

    I've been spared having to worry about that.

    Also, I'm leaving out sets for now.

    ==== The Stack and Local Variables ====

    The stack is like an implicit variable with implicit variables as parts. But

    the parts have no names, so we access them and move them around by various

    functions that are designed specifically for doing these things.

    Because the stack is the only place where we can put things (not counting

    files, for the moment), we have the problem of managing the stack so that,

    when a function is invoked, it finds what it needs in the right places in

    the stack. This means, unless we have some special tools, that we end up

    doing a lot of stack manipulation.

    This section of this post is about ideas and suggestions for reducing the

    programmer-overhead of stack manipulation and/or the actual stack

    manipulation. Included are proposals for local variables, different ways of

    referencing things in the stack (that don't require so much re-calculation

    of top-relative positions of things), and additional functions to make

    accessing deeper items on the stack easier. In at least some cases, these

    ideas can be combined.

    I'd be willing to bet that others on this list (and, of course, in the world

    at large) have suggested everything I'm suggesting here (including the

    things I don't give references for). I say this to make it clear that I

    don't mean to try to take credit for anything that ideas that others have

    proposed. Think of this more as just a summary of stuff I've been thinking

    about, whether it's familiar to you or not, and then comment on it at will.

    To start, I'm implementing something like Salvatore Sanfilippo's local

    "variables" (http://wiki.tcl.tk/10870 and

    http://www.hping.org/tclsbignum/joy.tcl) to simplify coding.

    Sanfilippo restricts local variables to the level of the quoted program they

    occur in, to avoid breaking Joy's theoretical principles. However, I'm

    thinking of treating them like "by value" substitutions, so if "( a )"

    captures the top item on the stack in a variable named "a", then "[ $a ]"

    (following Sanfilippo's convention) following it in the code would make a

    list on the stack with the *value* of that variable at the time of the push,

    so there would be no "behind-the-scenes" changing of the value of the

    element in the list if another capture was done after the push. This

    protects the list from side-effects, and shouldn't "break" Joy's algebraic

    qualities (I think). It still amounts to a mere programmer convenience (so

    the programmer doesn't have to track so many items on the stack in his head

    as he programs) and an efficiency mechanism (because it can eliminate some

    time-consuming stack manipulations).

    Question: Am I right in thinking that this is sufficient to protect Joy's

    logic? I'm not entirely sure. Since

                                    "xyz" 2  ( a b )   [ $a  $b ]

    (at this point, $a and $b are "xyz" and 2, respectively)

    would be equivalent to:

    "xyz" 2  swap [] cons swap dup

    it would seem to be okay, but I haven't tried to perform an exhaustive

    analysis of what allowing this sort of thing could lead to).

    (And, obviously, we don't save any on coding in this case, but both $a and

    $b could be used many times after "[ $a $b ]" in the first example, at

    widely-spaced locations in the code for the function it occurs in, thereby

    gaining back more than the coding cost of defining them initially -- and,

    even if all they do is make things *easier* for the programmer by removing

    some of the stack-hassle from his mind, they could worth using).

    The stack is one-dimensional, like a stack of plates. The use of local

    variables in the way described above is analogous in some ways to taking

    some of the items off the stack and laying them out on a table so they can

    be accessed more easily. Even though we continue to do operations on the

    stack, we don't have to figure out where our accumulator is and then drag it

    back to the top of the stack (or near enough for a dip).

    Sanfilippo has some examples of the use of local variables in his TCL

    version of Joy (which he calls Apathy). Although I find much of his Joy code

    nearly as opaque as regular Joy (because of my lack of sufficient practice

    in following what's happening in it), it still shows how local variables can

    be used to reduce programmer overhead. I think my suggested extension would

    lead to further simplifications for the programmer.

    Other Ideas for Reducing Stack-Fiddling:

    I see the large amount of stack manipulation, which is the cost of doing

    without variables, as being a drawback to the regular use of Joy, so I'm

    also considering other mechanisms besides the one above that might make Joy

    a little easier to use (especially for novices). Some ideas:

    Peek and Poke with top-relative and bottom-relative indexing (i.e., indexing

    from the top of the stack or its bottom by means of negative indices). See:

    "The Theory of Concatenative Combinators," by Brent Kerby

    (http://tunes.org/~iepos/joy.html)

      1.. Peek and Poke with top-relative and/or bottom-relative indexing (i.e.,

    indexing from the top of the stack or its bottom). Inspired by "The Theory

    of Concatenative Combinators," by Brent Kerby (iepos@...). Kerby's

    piece was itself inspired by Joy.

      2.. Dig and Bury (with an index). Like Peek and Poke, but the items are

    moved, not merely copied. Indexes, again, could be top-relative (positive

    numbers) or bottom-relative (negative numbers). (ibid.) Kerby builds the

    index into the functions, but I think I would prefer them to be kept

    separate, so "3 peek" would first remove the 3 from the top of the stack and

    then copy the third item down to the top. "3 dig" would be like rolldown.

    The proposal for the use of negative (stack-bottom-relative indexing) for

    the four functions above is my own, so don't blame it on Kerby.

      Also, we might allow the programmer to set a "base" for negative indexing

    that would not be the bottom of the stack, but would be initially set

    relative to the top of the stack. Once set, the base would stay at that

    absolute location in the stack (within the function). This way, the

    programmer would not have to know where the top items are relative to the

    bottom of the stack in order to set things up for using this kind of stack

    accessing. If, for example the programmer knew that he was only going to be

    interested in the top five items, he could set the base at, say, 5 down from

    the top at the start of the function and then use negative indexes that

    would be based on that location.

      As always, we'd want to restrict the scope of such settings to the

    function they occur in.

      3.. Named locations in the stack, which, once set, would stay pointed to

    the same spot until set again (within the same function and at the same

    nesting level). This would be combined with a mechanism for getting and

    setting the value at that point in the stack (peek and poke). This would be

    another form of local variable, and, because it's a reference mechanism, we

    would want to restrict the scope enough to prevent it from causing problems

    with Joy's theory or practice.

      4.. Objects: Structures with named parts. If we want to avoid variables,

    we could allow the values of the components to be set only once. But, we

    could also allow them to be changed. These structures would be like lists

    (or trees, etc.) but with named parts for ease in programming. In fact, we

    might implement such a structure as a tree with some sort of naming

    mechanism laid over to give names to the locations in the list. By using

    names to reference parts of a list, we can get at them with less explicit

    list-fiddling, thereby reducing programmer-overhead. These structures, like

    anything else, would be worked with on the stack.

      5.. Classes. I think Manfred said once that we didn't need classes,

    because we don't have variables. I think this view rests on a too-narrow

    view of what a class is. I'd say, for example, that the set of functions for

    defining, manipulating, and working with trees amount to a class, even if we

    don't necessarily think of them that way. But, we can make this class-hood

    explicit, define objects by means of classes, and manipulate their data (and

    code) by means of their various members. This is really merely an expansion

    of the idea for objects above. In this case, the names of the parts would be

    determined by a kind of "template" (if "class" is not a good term), as would

    any default values of these parts.

      6.. Rearranging by rearranging indices. What I have in mind here is a

    means of listing the top n items of the stack (below the list) in a new

    order and having those items rearranged in that order. Thus, if you have the

    following as the top seven items on the stack,

                            "jumps" "brown" "quick" "the" "over" "fox" "The"

      . . . you could rearrange them by something with perhaps the following

    syntax:

                            (1 5 6 2 7 3 4)

      . . . to rearrange these items in this order

                             "The" "quick" "brown" "fox" "jumps" "over" "the"

      (I think something like this would also be useful in working with lists,

    and neither usage would be hard to implement).

      This kind of mechanism might be easier to use than some of the usual

    mechanisms, especially if there are more than a very few items to rearrange.

    And, it could easily be used to define more-specialized stack manipulators:

                          swap == (2 1) ;

                          rolldown == (2 1 3) ;

                             mystackfiddler  == ( 12 3 5 7 8 10 6 9 2 1 4 11);

    (* perhaps for some highly-specialized use *)

    That's it for now.

    --Chris Cogan

## sa@dfa.com — 2004-09-08 12:53:12

    hi chris

    true, the list has been slow lately, but i don't take this an indication

    that people haven't been thinking about the subject.  i do miss the

    conversation, though.  perhaps your post will spark renewed activity.

    i like the idea of what you call "local variables", although i think

    the term can be misleading, since they're read-only -- you can't assign

    back onto the stack (at least i hope not.)

    regarding your other suggestions (1-6):

    1, 2, 6:  implement these using "stack" and "at".  i.e. turn the stack

    into a list, index out what you want (possibly removing the items

    from the list), then unstack.

    3. joy is beautiful because it is simple.  this way lies madness.

    4, 5. simulate objects (what others call "dictionaries", associative

    arrays)

    with quotations.  one possible design:  a dictionary is a list of pairs,

    each

    of which consists of a name and a value.  then implement the access

    functions

    in joy.  if there is a way to instruct the interpreter to evaluate at a

    location

    in an arbitrary dictionary, then you've got name-spaces.

    you might want to have a look at XY (http://www.nsl.com/papers/xy.htm).

    there are really two ideas here:  the underlying model consists of a

    result stack and an input queue, both of which are passed to, and returned

    from every function; two pattern-matching primitives, {} and {{}}, are

    used to define the vocabulary of joy.  E.g. using patterns and elements

    from the XY core, one can define the stack manipulations words and the

    recursive combinators.  here's a sample:

    ; dup           { a a a } ;

    ; swap          { [a b] b a } ;

    ; pick          { [a b c] a b c a } ;

    ; cdr           { [[a A]] A } ;

    ; cons          { [a b] [a] b , } ;

    ; uncons        { [[a A]] a A } ;

    ; callcc        { [q n] [_x _y n continue] q i } ;

    ; continue      { [x_ y_ n] \c x_ i n -: _x # i y_ -> } ;

    ; callcc0       0 callcc ;

    ; callcc1       1 callcc ;

    ; call          i ;

    ; i             // ;

    ; dip           swap / i \ ;

    ; 2dip          -rot / / i \ \ ;

    ; linrec        {{ [c t e f] c i c t e f _x linrec. }} ;

    ; linrec.       {{ [b c t e f x] x <- b t [e i c t e f linrec f i] if }} ;

    "Chris Cogan" <ccogan@...> wrote on 09/07/2004 11:44:10 PM:

     >

    >

    > Hi. I see I'm not the only one who hasn't been very active on this list

    > lately.

    >

    >

    >

    > Worse, for me, I haven't been able to devote much of my work time to the

     Joy

     > implementation in Visual Basic .NET for the past couple of weeks, so I've

    > had to work on it mostly in the evenings and weekends.

    >

    >

    >

    > Two main sections follow, one with some notes and remarks on my

    > implementation of Joy, and one on various ideas for reducing

    > programmer-overhead with respect to the stack.

    >

    >

    >

    > ==== Notes on My Implementation of Joy in Visual Basic .NET ====

    >

    >

    >

    > Worse still, I keep almost getting it to work and then finding things to

     do

     > to improve it and end up having to work back up to the level of

     functioning

     > I had previously achieved. Most recently, I realized that I only need to

    > carry around my own type indicator until each item is compiled, and then

     I

     > can use Visual Basic's own type-determining functions. This means I don't

    > have to put a multiple-member object on the stack when all I really want

     to

     > do is push a number or string, etc., which should improve the efficiency

     of

     > the pushing and popping operations considerably, since I only need to

     push

     > and pop the values themselves (at least from the point of view of the

    > programmer).

    >

    >

    >

    > (Of course, I'm not doing real compilation, but I am compiling to a kind

     of

     > threaded code in which each code element is a multi-member object, with

     one

     > member being the function (a Sub, actually, in Visual Basic) to be

     executed

     > at run-time. Aside from the primitives, there are two internal functions,

    > one of which is assigned to the run-time member at compilation-time:

    >

    >

    >

    >   1.. One is for literals, which is just a function to push the value of

     the

     > literal.

    >   2.. One is for user-defined functions (everything that is not

     "hard-coded"

     > in Basic). This is just a Sub that calls the inner interpreter, passing

     it

     > the threaded code associated with the defined atom.

    >

    >

    > Here they are:

    >

    >

    >

    > Public Sub UDefXeq() 'User-Defined

    >

    > Xeq(Value)

    >

    > End Sub

    >

    >

    >

    > Public Sub LitXeq()  'Literal

    >

    > Push(Value)

    >

    > End Sub

    >

    >

    >

    > For all the primitives, a "delegate" is used. A delegate is the Visual

    > Studio mechanism for doing what would be called pointers to functions in

     C.

     >

    >

    >

    > Here's the inner interpreter, with all the tracing stuff removed so you

     can

     > see the core of it:

    >

    >

    >

    > Sub Xeq(ByRef CodeArray() As CodeElem)

    >

    > Dim I As Long

    >

    >

    >

    > For I = 0 To Ubound(CodeArray)

    >

    > CodeArray(I).Rx()

    >

    > If AbortFlag Then Exit For

    >

    > Next

    >

    >

    >

    > End Sub

    >

    >

    >

    > Because Visual Studio languages have their own built-in garbage

     collection,

     > I've been spared having to worry about that.

    >

    >

    >

    > Also, I'm leaving out sets for now.

    >

    >

    >

    > ==== The Stack and Local Variables ====

    >

    >

    >

    > The stack is like an implicit variable with implicit variables as parts.

     But

     > the parts have no names, so we access them and move them around by

     various

     > functions that are designed specifically for doing these things.

    >

    >

    >

    > Because the stack is the only place where we can put things (not counting

    > files, for the moment), we have the problem of managing the stack so

     that,

     > when a function is invoked, it finds what it needs in the right places in

    > the stack. This means, unless we have some special tools, that we end up

    > doing a lot of stack manipulation.

    >

    >

    >

    > This section of this post is about ideas and suggestions for reducing the

    > programmer-overhead of stack manipulation and/or the actual stack

    > manipulation. Included are proposals for local variables, different ways

     of

     > referencing things in the stack (that don't require so much

     re-calculation

     > of top-relative positions of things), and additional functions to make

    > accessing deeper items on the stack easier. In at least some cases, these

    > ideas can be combined.

    >

    >

    >

    > I'd be willing to bet that others on this list (and, of course, in the

     world

     > at large) have suggested everything I'm suggesting here (including the

    > things I don't give references for). I say this to make it clear that I

    > don't mean to try to take credit for anything that ideas that others have

    > proposed. Think of this more as just a summary of stuff I've been

     thinking

     > about, whether it's familiar to you or not, and then comment on it at

     will.

     >

    >

    >

    > To start, I'm implementing something like Salvatore Sanfilippo's local

    > "variables" (http://wiki.tcl.tk/10870 and

    > http://www.hping.org/tclsbignum/joy.tcl) to simplify coding.

    >

    >

    >

    > Sanfilippo restricts local variables to the level of the quoted program

     they

     > occur in, to avoid breaking Joy's theoretical principles. However, I'm

    > thinking of treating them like "by value" substitutions, so if "( a )"

    > captures the top item on the stack in a variable named "a", then "[ $a ]"

    > (following Sanfilippo's convention) following it in the code would make a

    > list on the stack with the *value* of that variable at the time of the

     push,

     > so there would be no "behind-the-scenes" changing of the value of the

    > element in the list if another capture was done after the push. This

    > protects the list from side-effects, and shouldn't "break" Joy's

     algebraic

     > qualities (I think). It still amounts to a mere programmer convenience

     (so

     > the programmer doesn't have to track so many items on the stack in his

     head

     > as he programs) and an efficiency mechanism (because it can eliminate

     some

     > time-consuming stack manipulations).

    >

    >

    >

    > Question: Am I right in thinking that this is sufficient to protect Joy's

    > logic? I'm not entirely sure. Since

    >

    >

    >

    >                                 "xyz" 2  ( a b )   [ $a  $b ]

    >

    >

    >

    >

    > (at this point, $a and $b are "xyz" and 2, respectively)

    >

    > would be equivalent to:

    >

    >

    >

    > "xyz" 2  swap [] cons swap dup

    >

    >

    >

    > it would seem to be okay, but I haven't tried to perform an exhaustive

    > analysis of what allowing this sort of thing could lead to).

    >

    >

    >

    > (And, obviously, we don't save any on coding in this case, but both $a

     and

     > $b could be used many times after "[ $a $b ]" in the first example, at

    > widely-spaced locations in the code for the function it occurs in,

     thereby

     > gaining back more than the coding cost of defining them initially -- and,

    > even if all they do is make things *easier* for the programmer by

     removing

     > some of the stack-hassle from his mind, they could worth using).

    >

    >

    >

    > The stack is one-dimensional, like a stack of plates. The use of local

    > variables in the way described above is analogous in some ways to taking

    > some of the items off the stack and laying them out on a table so they

     can

     > be accessed more easily. Even though we continue to do operations on the

    > stack, we don't have to figure out where our accumulator is and then drag

     it

     > back to the top of the stack (or near enough for a dip).

    >

    >

    >

    > Sanfilippo has some examples of the use of local variables in his TCL

    > version of Joy (which he calls Apathy). Although I find much of his Joy

     code

     > nearly as opaque as regular Joy (because of my lack of sufficient

     practice

     > in following what's happening in it), it still shows how local variables

     can

     > be used to reduce programmer overhead. I think my suggested extension

     would

     > lead to further simplifications for the programmer.

    >

    >

    >

    > Other Ideas for Reducing Stack-Fiddling:

    >

    >

    >

    > I see the large amount of stack manipulation, which is the cost of doing

    > without variables, as being a drawback to the regular use of Joy, so I'm

    > also considering other mechanisms besides the one above that might make

     Joy

     > a little easier to use (especially for novices). Some ideas:

    >

    >

    >

    > Peek and Poke with top-relative and bottom-relative indexing (i.e.,

     indexing

     > from the top of the stack or its bottom by means of negative indices).

     See:

     > "The Theory of Concatenative Combinators," by Brent Kerby

    > (http://tunes.org/~iepos/joy.html)

    >

    >   1.. Peek and Poke with top-relative and/or bottom-relative indexing

     (i.e.,

     > indexing from the top of the stack or its bottom). Inspired by "The

     Theory

     > of Concatenative Combinators," by Brent Kerby (iepos@...). Kerby's

    > piece was itself inspired by Joy.

    >   2.. Dig and Bury (with an index). Like Peek and Poke, but the items are

    > moved, not merely copied. Indexes, again, could be top-relative (positive

    > numbers) or bottom-relative (negative numbers). (ibid.) Kerby builds the

    > index into the functions, but I think I would prefer them to be kept

    > separate, so "3 peek" would first remove the 3 from the top of the stack

     and

     > then copy the third item down to the top. "3 dig" would be like rolldown.

    > The proposal for the use of negative (stack-bottom-relative indexing) for

    > the four functions above is my own, so don't blame it on Kerby.

    >

    >   Also, we might allow the programmer to set a "base" for negative

     indexing

     > that would not be the bottom of the stack, but would be initially set

    > relative to the top of the stack. Once set, the base would stay at that

    > absolute location in the stack (within the function). This way, the

    > programmer would not have to know where the top items are relative to the

    > bottom of the stack in order to set things up for using this kind of

     stack

     > accessing. If, for example the programmer knew that he was only going to

     be

     > interested in the top five items, he could set the base at, say, 5 down

     from

     > the top at the start of the function and then use negative indexes that

    > would be based on that location.

    >

    >   As always, we'd want to restrict the scope of such settings to the

    > function they occur in.

    >   3.. Named locations in the stack, which, once set, would stay pointed

     to

     > the same spot until set again (within the same function and at the same

    > nesting level). This would be combined with a mechanism for getting and

    > setting the value at that point in the stack (peek and poke). This would

     be

     > another form of local variable, and, because it's a reference mechanism,

     we

     > would want to restrict the scope enough to prevent it from causing

     problems

     > with Joy's theory or practice.

    >   4.. Objects: Structures with named parts. If we want to avoid

     variables,

     > we could allow the values of the components to be set only once. But, we

    > could also allow them to be changed. These structures would be like lists

    > (or trees, etc.) but with named parts for ease in programming. In fact,

     we

     > might implement such a structure as a tree with some sort of naming

    > mechanism laid over to give names to the locations in the list. By using

    > names to reference parts of a list, we can get at them with less explicit

    > list-fiddling, thereby reducing programmer-overhead. These structures,

     like

     > anything else, would be worked with on the stack.

    >   5.. Classes. I think Manfred said once that we didn't need classes,

    > because we don't have variables. I think this view rests on a too-narrow

    > view of what a class is. I'd say, for example, that the set of functions

     for

     > defining, manipulating, and working with trees amount to a class, even if

     we

     > don't necessarily think of them that way. But, we can make this

     class-hood

     > explicit, define objects by means of classes, and manipulate their data

     (and

     > code) by means of their various members. This is really merely an

     expansion

     > of the idea for objects above. In this case, the names of the parts would

     be

     > determined by a kind of "template" (if "class" is not a good term), as

     would

     > any default values of these parts.

    >   6.. Rearranging by rearranging indices. What I have in mind here is a

    > means of listing the top n items of the stack (below the list) in a new

    > order and having those items rearranged in that order. Thus, if you have

     the

     > following as the top seven items on the stack,

    >

    >                         "jumps" "brown" "quick" "the" "over" "fox" "The"

    >

    >   . . . you could rearrange them by something with perhaps the following

    > syntax:

    >

    >                         (1 5 6 2 7 3 4)

    >

    >   . . . to rearrange these items in this order

    >

    >                          "The" "quick" "brown" "fox" "jumps" "over" "the"

    >

    >   (I think something like this would also be useful in working with

     lists,

     > and neither usage would be hard to implement).

    >

    >   This kind of mechanism might be easier to use than some of the usual

    > mechanisms, especially if there are more than a very few items to

     rearrange.

     > And, it could easily be used to define more-specialized stack

     manipulators:

     >

    >                       swap == (2 1) ;

    >

    >                       rolldown == (2 1 3) ;

    >                          mystackfiddler  == ( 12 3 5 7 8 10 6 9 2 1 4

     11);

     > (* perhaps for some highly-specialized use *)

    >

    >

    >

    > That's it for now.

    >

    >

    >

    > --Chris Cogan

    >

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

## Slava Pestov — 2004-09-13 04:51:08

    Chris Cogan wrote:

     > Because the stack is the only place where we can put things (not counting

    > files, for the moment),

     If you feel this is a problem, then you can drop this restriction, and

    introduce named variables. It is not practical to hold the entire

    'world' on the stack, in my opinion.

     > we have the problem of managing the stack so that,

    > when a function is invoked, it finds what it needs in the right places in

    > the stack. This means, unless we have some special tools, that we end up

    > doing a lot of stack manipulation.

     My general thoughts on this are that it takes some practice to write

    short, simple definitions that access at most 2 or 3 stack elements.

    Once this skill has been mastered, local variables and other

    complications of the stack semantics become mostly unnecessary.

     > Sanfilippo restricts local variables to the level of the quoted program they

    > occur in, to avoid breaking Joy's theoretical principles. However, I'm

    > thinking of treating them like "by value" substitutions, so if "( a )"

    > captures the top item on the stack in a variable named "a", then "[ $a ]"

    > (following Sanfilippo's convention) following it in the code would make a

    > list on the stack with the *value* of that variable at the time of the push,

    > so there would be no "behind-the-scenes" changing of the value of the

    > element in the list if another capture was done after the push.

     Forth implementations usually implement local variables using a 'locals

    stack'. There are several syntaxes in use, but one possible form would

    look like so:

    : formula ( a b c -- d )

         LOCALS| c b a |

         b c + a * . ;

    It is transformed into the threaded-code equivalent of:

    : formula

          >l >l >l

          2 l@ 1 l@ + 0 l@ * . l> drop l> drop l> drop ;

    Where >l/l> push/pop the locals stack, and l@ takes an index and returns

    that value from the top of the local stack.

    (Of course the above example can be written as : formula + * ;, but

    that's besides the point.)

     > The stack is one-dimensional, like a stack of plates. The use of local

    > variables in the way described above is analogous in some ways to taking

    > some of the items off the stack and laying them out on a table so they can

    > be accessed more easily. Even though we continue to do operations on the

    > stack, we don't have to figure out where our accumulator is and then drag it

    > back to the top of the stack (or near enough for a dip).

     If you find your definitions 'dragging' values up and down, it means the

    argument orders need more thought.

     > I see the large amount of stack manipulation, which is the cost of doing

    > without variables, as being a drawback to the regular use of Joy, so I'm

    > also considering other mechanisms besides the one above that might make Joy

    > a little easier to use (especially for novices).

     When doing Factor, I don't find stack manipulation to be a drawback. In

    fact, I avoid using variables unless absolutely necessary, since

    definitions that only use the stack tend to be shorter and simpler.

     >   1.. Peek and Poke with top-relative and/or bottom-relative indexing (i.e.,

    > indexing from the top of the stack or its bottom). Inspired by "The Theory

    > of Concatenative Combinators," by Brent Kerby (iepos@...). Kerby's

    > piece was itself inspired by Joy.

    >   2.. Dig and Bury (with an index). Like Peek and Poke, but the items are

    > moved, not merely copied. Indexes, again, could be top-relative (positive

    > numbers) or bottom-relative (negative numbers).

     This way lies madness. I'd rather see small succint definitions than ones

    taking 8 parameters and accessing them with 7 poke, 4 peek, or worse,

    peek/poke with computed indices.

     >   Also, we might allow the programmer to set a "base" for negative indexing

    > that would not be the bottom of the stack, but would be initially set

    > relative to the top of the stack.

     ....

     >  As always, we'd want to restrict the scope of such settings to the

    > function they occur in.

     This is ambiguous. What if you have a situation like this:

    f1 == 4 set-base  [ 4 < ] [ -4 bury swons ] f2.

    f2 == 3 set-base i.

    What is the 'base' set to when the quotation [ -4 bury swons ] is

    executed by the call to 'i' in f2? If the base inside the quotation is

    4, you have lexical scope of the base variable, and your quotations are

    no longer simple lists, but rather <environment,list> pairs. If the base

    is 3 inside the quotation, you have dynamic scope, and this breaks

    encapsulation. Factor uses dynamic scope for variables, however this is

    generally not a problem since combinators that fiddle with scope are

    usually clearly marked as such. However, with this dig/bury deal,

    potentially *any* combinator can change the stack base for its own

    internal use, and side-effect the quotations it executes in an

    unpredicatable way.

     >                       swap == (2 1) ;

    >

    >                       rolldown == (2 1 3) ;

     The Java implementation of Factor supports 'shuffle words' defined as

    follows:

    ~<< dup A -- A A >>~

    ~<< swap A B -- B A >>~

    etc.

    However, I noticed that the handful of cases where I defined specialized

    shuffle words (other than the core set of rot, swap, 2drop, and so on),

    was because of unclear thinking and design. In the C implementation of

    Factor, I hardcoded a small set of stack manipulators that expand to a

    handful of assembly language instructions each:

    drop ( x -- )

    dup  ( x -- x x )

    swap ( x y -- y x )

    over ( x y -- x y x )

    pick ( x y z -- x y z x )

    nip  ( x y -- y )

    tuck ( x y -- y x y )

    rot  ( x y z -- y z x )

    A few others are defined in terms of these, eg : 2drop drop drop ; and :

    2dup over over ;.

    Slava

## William Tanksley, Jr — 2004-09-13 15:04:43

    On Mon, 13 Sep 2004 00:51:08 -0400, Slava Pestov <slava@...> wrote:

     > The Java implementation of Factor supports 'shuffle words' defined as

    > follows:

    > ~<< dup A -- A A >>~

    > ~<< swap A B -- B A >>~

    > etc.

    > However, I noticed that the handful of cases where I defined specialized

    > shuffle words (other than the core set of rot, swap, 2drop, and so on),

    > was because of unclear thinking and design. In the C implementation of

     Do you find that the unclarity is native to the larger set of

    shufflings, or is it possible that the unclarity is due to unfamiliar

    names for the individual shuffles?

    I speculate that the best way to handle stack shufflings is by stack

    pictures; rather than using the word "rot", for example, you use the

    picture "abc--bca", and the compiler or interpreter can generate the

    correct stack manipulation.  I wrote a limited version of this which

    generated x86 machine code directly for Pygmy Forth; it worked very

    well. (I don't have the code anymore, unfortunately.)

     > Slava

     -Billy

## phimvt@lurac.latrobe.edu.au — 2004-09-17 04:35:36

    On Tue, 7 Sep 2004, Chris Cogan wrote:

    [..]

    > To start, I'm implementing something like Salvatore Sanfilippo's

    local

    > "variables" (http://wiki.tcl.tk/10870 and

    > http://www.hping.org/tclsbignum/joy.tcl) to simplify coding.

    >

    > Sanfilippo restricts local variables to the level of the quoted program they

    > occur in, to avoid breaking Joy's theoretical principles.

    If you can read this, Salvatore, would you be interested to write

    a contribution to the joint paper about concatenative languages

    that we are writing? Your implementation seems to be significantly

    different from others, and your contribution to the paper would

    be most welcome.

      - Manfred