# the false programming language

## stevan apter — 2004-05-12 21:46:42

    reading through the documentation for wouter van oortmerssen's

    1994 language:

    http://wouter.fov120.com/false/false.txt

    programs monadic function of the stack, can return multiple values,

    &c.  the language appears to be concatenative, or nearly so.  elegant,

    terse, interesting (and see van oortmerssen's list of language credits.)

## sa@dfa.com — 2004-05-14 15:26:30

    i've placed my k implementation of false here:

          http://www.nsl.com/k/false.k

    and made a start at writing up a description of the implementation here:

          http://www.nsl.com/papers/false.htm

    the language is. by design, very small and extremely cryptic.  e.g., the

    factorial function is written:

          [$1=$[\%1\]?~[$1-f;!*]?]f:

    as an obfuscated language hobbyist, i was intrigued to note that one can

    write a pure interpreter for false.  that is, one which operates directly

    on the unprocessed raw code as a stream of characters.  no tokenizing, no

    parsing, no nothing.  i suppose this is possible for languages more

    complex than false, but the point of interest here is that, for false,

    it is arguably the most natural approach.  i can't see that anything is

    gained by first parsing to some internal form, and then executing that.

    my implementation uses two stacks:  a general list for the result, and a

    string for the input.  the 'eval' keeps processing until the input is

    empty.

    enjoy!

    "stevan apter" <sa@...> wrote on 05/12/2004 05:46:42 PM:

     > reading through the documentation for wouter van oortmerssen's

    > 1994 language:

    >

    > http://wouter.fov120.com/false/false.txt

    >

    > programs monadic function of the stack, can return multiple values,

    > &c.  the language appears to be concatenative, or nearly so.  elegant,

    > terse, interesting (and see van oortmerssen's list of language credits.)

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

## Price, Rod (Mission Systems) — 2004-05-14 17:41:43

    I read over the description of FALSE, and I'm still

    wondering:  How are FALSE "programs [a] monadic

    function of the stack"?

    -Rod

    "stevan apter" <sa@...> wrote on 05/12/2004 05:46:42 PM:

     > reading through the documentation for wouter van oortmerssen's

    > 1994 language:

    >

    > http://wouter.fov120.com/false/false.txt

    >

    > programs monadic function of the stack, can return multiple values,

    > &c.  the language appears to be concatenative, or nearly so.  elegant,

    > terse, interesting (and see van oortmerssen's list of language credits.)

    >

## sa@dfa.com — 2004-05-14 18:03:54

    a false program, e.g. the "lambda" which increments an integer [1+], takes

    the

    stack, pushes 1 and replaces the top two elements with their sum.  so [1+]

    is

    stack -> stack.

    "Price, Rod (Mission Systems)" <rod.price@...> wrote on 05/14/2004

    01:41:43 PM:

     > I read over the description of FALSE, and I'm still

    > wondering:  How are FALSE "programs [a] monadic

    > function of the stack"?

    >

    > -Rod

    >

    >

    >

    > "stevan apter" <sa@...> wrote on 05/12/2004 05:46:42 PM:

    >

    > > reading through the documentation for wouter van oortmerssen's

    > > 1994 language:

    > >

    > > http://wouter.fov120.com/false/false.txt

    > >

    > > programs monadic function of the stack, can return multiple values,

    > > &c.  the language appears to be concatenative, or nearly so.  elegant,

    > > terse, interesting (and see van oortmerssen's list of language

     credits.)

     > >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

## phimvt@lurac.latrobe.edu.au — 2004-05-17 04:33:40

    On Fri, 14 May 2004 sa@... wrote:

     > i've placed my k implementation of false here:

    >

    >       http://www.nsl.com/k/false.k

    >

    > and made a start at writing up a description of the implementation here:

    >

    >       http://www.nsl.com/papers/false.htm

    >

    > the language is. by design, very small and extremely cryptic.  e.g., the

    > factorial function is written:

    >

    >       [$1=$[\%1\]?~[$1-f;!*]?]f:

    >

    > as an obfuscated language hobbyist, i was intrigued to note that one can

    > write a pure interpreter for false.  that is, one which operates directly

    > on the unprocessed raw code as a stream of characters.  no tokenizing, no

    > parsing, no nothing.  i suppose this is possible for languages more

    > complex than false, but the point of interest here is that, for false,

    > it is arguably the most natural approach.  i can't see that anything is

    > gained by first parsing to some internal form, and then executing that.

     Consider a language which uses I F T for if, then, else, and similarly

    single characters for other things. Now a program fragment:

        I  if-part  T  long-then-part  E  long-else-part

    Suppose also that this conditional will be executed many times.

    Depending on the test in the if-part, either the then-part or

    the else-part needs to be skipped. If the code is stored as an

    unstructured sequence, to skip the then-part involves finding

    the matching E by reading it symbol by symbol. Compiling into

    tree form and interpreting that will speed things up - in case

    that is important.

     > my implementation uses two stacks:  a general list for the result, and a

    > string for the input.  the 'eval' keeps processing until the input is

    > empty.

     You call the input string a stack and I seem to remember you

    and others speaking of "program stack", which has puzzled me

    although I never mentioned that. Your input string presumably

    comes from a file (disk file or keyboard), and the first and last

    symbols in the file become the first and last symbol in the

    internal representation. The first symbol to be executed is the

    first symbol from the file. Doesn't that make it a queue, if anything?

    During execution there are no pushes and pops to the program,

    are there?

    Puzzled.

      - Manfred

## stevan apter — 2004-05-17 10:46:30

    ----- Original Message -----

    From: <phimvt@...>

    To: <concatenative@yahoogroups.com>

    Sent: Monday, May 17, 2004 12:33 AM

    Subject: Re: [stack] the false programming language

    >

    > On Fri, 14 May 2004 sa@... wrote:

    >

    > > i've placed my k implementation of false here:

    > >

    > >       http://www.nsl.com/k/false.k

    > >

    > > and made a start at writing up a description of the implementation here:

    > >

    > >       http://www.nsl.com/papers/false.htm

    > >

    > > the language is. by design, very small and extremely cryptic.  e.g., the

    > > factorial function is written:

    > >

    > >       [$1=$[\%1\]?~[$1-f;!*]?]f:

    > >

    > > as an obfuscated language hobbyist, i was intrigued to note that one can

    > > write a pure interpreter for false.  that is, one which operates directly

    > > on the unprocessed raw code as a stream of characters.  no tokenizing, no

    > > parsing, no nothing.  i suppose this is possible for languages more

    > > complex than false, but the point of interest here is that, for false,

    > > it is arguably the most natural approach.  i can't see that anything is

    > > gained by first parsing to some internal form, and then executing that.

    >

    > Consider a language which uses I F T for if, then, else, and similarly

    > single characters for other things. Now a program fragment:

    >     I  if-part  T  long-then-part  E  long-else-part

    > Suppose also that this conditional will be executed many times.

    > Depending on the test in the if-part, either the then-part or

    > the else-part needs to be skipped. If the code is stored as an

    > unstructured sequence, to skip the then-part involves finding

    > the matching E by reading it symbol by symbol. Compiling into

    > tree form and interpreting that will speed things up - in case

    > that is important.

    yes, of course you're right that, in general, parsing to an internal

    form will speed things up, and perhaps that would be so for false as

    well.  but i was thinking of how parsing often simplifies the evaluation

    algorithm, and in the case of false, the shortest and simplest 'eval' i

    could think of was one which operated directly on the source.

    >

    > > my implementation uses two stacks:  a general list for the result, and a

    > > string for the input.  the 'eval' keeps processing until the input is

    > > empty.

    >

    > You call the input string a stack and I seem to remember you

    > and others speaking of "program stack", which has puzzled me

    > although I never mentioned that. Your input string presumably

    > comes from a file (disk file or keyboard), and the first and last

    > symbols in the file become the first and last symbol in the

    > internal representation. The first symbol to be executed is the

    > first symbol from the file. Doesn't that make it a queue, if anything?

    > During execution there are no pushes and pops to the program,

    > are there?

    yes, in fact there are.  for example, "apply [2+] to 3"

        3[2+]!

    pushes 3, pushes [2+], then evaluates ! by popping [2+]

    from the result stack and pushing "2+" onto the input

    stack.  then 2 is pushed, then + is evaluated on 3 2:

                : 3[2+]!

              3 : [2+]!

          3[2+] : !

              3 : 2 +

            3 2 : +

              5

    >

    > Puzzled.

    >

    >   - Manfred

    >

    >

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

## phimvt@lurac.latrobe.edu.au — 2004-05-24 06:24:02

    On Mon, 17 May 2004, stevan apter wrote:

     > From: <phimvt@...>

    > > Consider a language which uses I F T for if, then, else, and similarly

    > > single characters for other things. Now a program fragment:

    > >     I  if-part  T  long-then-part  E  long-else-part

    > > Suppose also that this conditional will be executed many times.

    > > Depending on the test in the if-part, either the then-part or

    > > the else-part needs to be skipped. If the code is stored as an

    > > unstructured sequence, to skip the then-part involves finding

    > > the matching E by reading it symbol by symbol. Compiling into

    > > tree form and interpreting that will speed things up - in case

    > > that is important.

    >

    > yes, of course you're right that, in general, parsing to an internal

    > form will speed things up, and perhaps that would be so for false as

    > well.  but i was thinking of how parsing often simplifies the evaluation

    > algorithm, and in the case of false, the shortest and simplest 'eval' i

    > could think of was one which operated directly on the source.

     You are probably right here. Parsing has to be done at some time anyhow,

    and if essentially the same algorithm is used for the evaluation,

    then that will save writing an evaluator for the internal form.

     > > > my implementation uses two stacks:  a general list for the result, and a

    > > > string for the input.  the 'eval' keeps processing until the input is

    > > > empty.

    > >

    > > You call the input string a stack and I seem to remember you

    > > and others speaking of "program stack", which has puzzled me

    > > although I never mentioned that. Your input string presumably

    > > comes from a file (disk file or keyboard), and the first and last

    > > symbols in the file become the first and last symbol in the

    > > internal representation. The first symbol to be executed is the

    > > first symbol from the file. Doesn't that make it a queue, if anything?

    > > During execution there are no pushes and pops to the program,

    > > are there?

    >

    > yes, in fact there are.  for example, "apply [2+] to 3"

    >

    >     3[2+]!

    >

    > pushes 3, pushes [2+], then evaluates ! by popping [2+]

    > from the result stack and pushing "2+" onto the input

    > stack.  then 2 is pushed, then + is evaluated on 3 2:

    >

    >             : 3[2+]!

    >           3 : [2+]!

    >       3[2+] : !               (* from start *)

    >           3 : 2 +             (* to finish *)

    >         3 2 : +

    >           5

     I see, yes indeed, you are using a stack. The Joy interpreter

    of course does something which has the same net effect, but

    without pushing onto the program stack. This is possible

    because the evaluator uses recursion to keep track of all

    oustanding program fragments that are to be executed. So the

    fragments are never combined into a single structure. The

    recursion takes place whenever a combinator executes something.

    The advantage of never combining fragments into a single structure

    becomes very apparent when the fragment is very long, and not

    as short as the [2+] in your example. I am assuming that in your

    trace which I have marked, there are actually two separate pushes

    from "start" to "finish".

    In the implementation of Joy I went for the more efficient

    recursive solution without much thinking about alternatives.

    I find your solution to be rather interesting as a minimalist

    solution - and somewhat embarrassed that I had not seen earlier

    that this is what you are doing. Thanks.

      - Manfred

## stevan apter — 2004-05-24 13:44:40

    ----- Original Message -----

    From: <phimvt@...>

    :

    > > >

    > > > You call the input string a stack and I seem to remember you

    > > > and others speaking of "program stack", which has puzzled me

    > > > although I never mentioned that. Your input string presumably

    > > > comes from a file (disk file or keyboard), and the first and last

    > > > symbols in the file become the first and last symbol in the

    > > > internal representation. The first symbol to be executed is the

    > > > first symbol from the file. Doesn't that make it a queue, if anything?

    > > > During execution there are no pushes and pops to the program,

    > > > are there?

    > >

    > > yes, in fact there are.  for example, "apply [2+] to 3"

    > >

    > >     3[2+]!

    > >

    > > pushes 3, pushes [2+], then evaluates ! by popping [2+]

    > > from the result stack and pushing "2+" onto the input

    > > stack.  then 2 is pushed, then + is evaluated on 3 2:

    > >

    > >             : 3[2+]!

    > >           3 : [2+]!

    > >       3[2+] : !               (* from start *)

    > >           3 : 2 +             (* to finish *)

    > >         3 2 : +

    > >           5

    >

    > I see, yes indeed, you are using a stack. The Joy interpreter

    > of course does something which has the same net effect, but

    > without pushing onto the program stack. This is possible

    > because the evaluator uses recursion to keep track of all

    > oustanding program fragments that are to be executed. So the

    > fragments are never combined into a single structure. The

    > recursion takes place whenever a combinator executes something.

    > The advantage of never combining fragments into a single structure

    > becomes very apparent when the fragment is very long, and not

    > as short as the [2+] in your example. I am assuming that in your

    > trace which I have marked, there are actually two separate pushes

    > from "start" to "finish".

    >

    > In the implementation of Joy I went for the more efficient

    > recursive solution without much thinking about alternatives.

    > I find your solution to be rather interesting as a minimalist

    > solution - and somewhat embarrassed that I had not seen earlier

    > that this is what you are doing. Thanks.

    that was my initial approach as well, but this message from russel

    simmons last year showed me a different way of thinking about things:

    http://groups.yahoo.com/group/concatenative/message/1574

    i'd like to know how his project went.  we haven't heard from russel

    since he left on his trip to overthereistan.

## Paul-V Khuong — 2004-05-24 16:04:09

    >    Date: Mon, 24 May 2004 17:24:02 +1100

    >    From: phimvt@...

    > Subject: Re: the false programming language

    >

    >

    > On Mon, 17 May 2004, stevan apter wrote:

    >

    > > yes, in fact there are.  for example, "apply [2+]

    > to 3"

    > >

    > >     3[2+]!

    > >

    > > pushes 3, pushes [2+], then evaluates ! by popping

    > [2+]

    > > from the result stack and pushing "2+" onto the

    > input

    > > stack.  then 2 is pushed, then + is evaluated on 3

    > 2:

    > >

    > >             : 3[2+]!

    > >           3 : [2+]!

    > >       3[2+] : !               (* from start *)

    > >           3 : 2 +             (* to finish *)

    > >         3 2 : +

    > >           5

    >

    > I see, yes indeed, you are using a stack. The Joy

    > interpreter

    > of course does something which has the same net

    > effect, but

    > without pushing onto the program stack. This is

    > possible

    > because the evaluator uses recursion to keep track

    > of all

    > oustanding program fragments that are to be

    > executed. So the

    > fragments are never combined into a single

    > structure. The

    > recursion takes place whenever a combinator executes

    > something.

    > The advantage of never combining fragments into a

    > single structure

    > becomes very apparent when the fragment is very

    > long, and not

    > as short as the [2+] in your example. I am assuming

    > that in your

    > trace which I have marked, there are actually two

    > separate pushes

    > from "start" to "finish".

    >

     I'm not quite sure of what i am advancing, but if one

    implements stacks as linked lists (� la lisp), doesn't

    this disadvantage disappear? Pushing a link on a stack

    should be a simple matter of alterating a few CDRs and

    updating the stack pointer. Note that i am currently

    working on such a system, where i try to stick as much

    as possible to the linearity of stack languages, so i

    might have some blinders on.

    Paul Khuong

    PS. Pseudo-closures can be created with lambda-lifting

    and tacking arguments in front of the function.

    However, lambda-lifting mkes it impossible for

    different functions to share [mutable] variables. Does

    anyone see a way to allow such shared variables?

    __________________________________

    Do you Yahoo!?

    Yahoo! Domains � Claim yours for only $14.70/year

    http://smallbusiness.promotions.yahoo.com/offer

## phimvt@lurac.latrobe.edu.au — 2004-06-09 05:44:57

    On Mon, 24 May 2004, Paul-V Khuong wrote:

     > >    Date: Mon, 24 May 2004 17:24:02 +1100

    > >    From: phimvt@...

    > > Subject: Re: the false programming language

    > >

    > >

    > > On Mon, 17 May 2004, stevan apter wrote:

     [...]

     > > I see, yes indeed, you are using a stack. The Joy

    > > interpreter

    > > of course does something which has the same net

    > > effect, but

    > > without pushing onto the program stack. This is

    > > possible

    > > because the evaluator uses recursion to keep track

    > > of all

    > > oustanding program fragments that are to be

    > > executed. So the

    > > fragments are never combined into a single

    > > structure. The

    > > recursion takes place whenever a combinator executes

    > > something.

    > > The advantage of never combining fragments into a

    > > single structure

    > > becomes very apparent when the fragment is very

    > > long, and not

    > > as short as the [2+] in your example. I am assuming

    > > that in your

    > > trace which I have marked, there are actually two

    > > separate pushes

    > > from "start" to "finish".

    > >

    > I'm not quite sure of what i am advancing, but if one

    > implements stacks as linked lists (à la lisp), doesn't

    > this disadvantage disappear? Pushing a link on a stack

    > should be a simple matter of alterating a few CDRs and

    > updating the stack pointer.

     That depends. There are several ways of implementing all the

    requisite "push-onto-the-program-stack". Let Q = [x y1 y2 ...yN z]

    be the program fragment to be pushed from the stack back onto

    the program P

    1. Proper concatenation:

    Concatenate Q with the remaining program P. This involves recursion:

    recurse down into Q to find z, link to first node of P, and on

    the way back make newnodes yN .. y2 y1 x. This takes time and

    requires new nodes.

    2. Destructive concatenation:

    Find z, change its nil (cdr, end-of-list) field to point to the beginning

    of P. Finding z is fast, changing the cdr is trivial). BUT: this

    destroys the original structure of Q. If there are other links

    pointing to Q (as there would be if it had been "dup"ed, or something

    similar), this would be disastrous for a language like Joy.

    3. Lazy concatenation:

    Allow "pairing nodes" for the program stack. Replace P by

    a single node "pair(Q,P)" - meaning: these are to be concatenated

    to form a single list (stack). Fast, only needs one new node,

    irrespective of how long Q is. But it is a new concept, and

    the runtime system will need to know how to handle such new nodes.

    4. Recursion in the runtime system:

    Instead if shifting anything from the stack to the program, the

    runtime system recursively calls itself to execute Q (which has been

    popped) and when that is done it returns to executing P. (This

    is the method which the Joy interpreter uses - function "exeterm")

    Hope this helps.

     >                               Note that i am currently

    > working on such a system, where i try to stick as much

    > as possible to the linearity of stack languages, so i

    > might have some blinders on.

     Keep in mind that once nesting to arbitrary depth is allowed,

    even in linear languages, recursion is often an excellent way

    to deal with it.

    [...]

     > PS. Pseudo-closures can be created with lambda-lifting

    > and tacking arguments in front of the function.

    > However, lambda-lifting mkes it impossible for

    > different functions to share [mutable] variables. Does

    > anyone see a way to allow such shared variables?

     could you elaborate on this, please ?

      - Manfred

## paul_virak_khuong — 2004-06-14 17:04:40

    --- In concatenative@yahoogroups.com, phimvt@l... wrote:

     >

    > On Mon, 24 May 2004, Paul-V Khuong wrote:

     [...]

     > > I'm not quite sure of what i am advancing, but if one

    > > implements stacks as linked lists (à la lisp), doesn't

    > > this disadvantage disappear? Pushing a link on a stack

    > > should be a simple matter of alterating a few CDRs and

    > > updating the stack pointer.

    >

    > That depends. There are several ways of implementing all the

    > requisite "push-onto-the-program-stack". Let Q = [x y1 y2 ...yN z]

    > be the program fragment to be pushed from the stack back onto

    > the program P

    >

    > 2. Destructive concatenation:

    > Find z, change its nil (cdr, end-of-list) field to point to the

     beginning

     > of P. Finding z is fast, changing the cdr is trivial). BUT: this

    > destroys the original structure of Q. If there are other links

    > pointing to Q (as there would be if it had been "dup"ed, or

     something

     > similar), this would be disastrous for a language like Joy.

     Unless dup deep-copies everything, that is (only works for a typeful

    language).

     > 3. Lazy concatenation:

    > Allow "pairing nodes" for the program stack. Replace P by

    > a single node "pair(Q,P)" - meaning: these are to be concatenated

    > to form a single list (stack). Fast, only needs one new node,

    > irrespective of how long Q is. But it is a new concept, and

    > the runtime system will need to know how to handle such new nodes.

     It seems to me it also means that we can't simply pass a pointer

    anymore, and that we either have to provide backpointers (like

    double-linked lists), or have O(n) instead of O(n) access time.

     > 4. Recursion in the runtime system:

    > Instead if shifting anything from the stack to the program, the

    > runtime system recursively calls itself to execute Q (which has been

    > popped) and when that is done it returns to executing P. (This

    > is the method which the Joy interpreter uses - function "exeterm")

     Yes, i think this is the standard method, and works very well. The

    only disadvantage i see is that working with continuations might be

    weird. On the other hand, it does seem to provide better performance

    in most cases.

     > >                               Note that i am currently

    > > working on such a system, where i try to stick as much

    > > as possible to the linearity of stack languages, so i

    > > might have some blinders on.

    >

    > Keep in mind that once nesting to arbitrary depth is allowed,

    > even in linear languages, recursion is often an excellent way

    > to deal with it.

     What exactly do you mean?

     > [...]

    >

    > > PS. Pseudo-closures can be created with lambda-lifting

    > > and tacking arguments in front of the function.

    > > However, lambda-lifting makes it impossible for

    > > different functions to share [mutable] variables. Does

    > > anyone see a way to allow such shared variables?

    >

    > could you elaborate on this, please ?

     Sure. This only works if we can easily define functions at runtime

    (here in a lispy language (since that's what i'm most comfortable

    with)).

    (defun plus-x (x)

      (lambda (y) (+ x y)))

    What we have is a function that generates a closure

    (function+environment) that adds a certain number to its input. x is

    free in the lambda, so it must be kept in the environment. What we

    could instead do is have sometihng like this:

    (defun plus-x (x)

      (lambda (y)

        ((lambda (x y) (+ x y)) x)))

    IIRC, http://www.iro.umontreal.ca/~feeley/papers/complang92.ps.gz

    describes a similar process, and it surely is more authoritative on

    the subject than i am (this is all from memory, so the implementation

    might very well be ok, but the explanations not :D). This is lisp, so

    they're probably passing pointers around, not litterals, thus allowing

    variable sharing & mutability.

    In a stack language that could translate into something like this:

    [plus-x 5] returns [5 +]. In short, instead of having free variables,

    we define them as arguments, whose values are passed around with the

    function - this is basically the same as closures in languages that

    don't support this, but in those who do, it means the environment is

    instead compiled as litterals. Since it is compiled in, it also means

    that they can't be modified. The traditional (FP, since pointers do

    the job very well otherwise) way of simulating mutability is to have

    the function return its updated self too, but i don't see how this

    allows the sharing of variables between multiple closures, unless one

    passes around an object representing all the closures that share

    variables together.

    Paul

## stevan apter — 2004-06-14 22:08:13

    in my false interpreter, i adapted a technique i used in the second of a

    sequence of tiny concatenative array languages, which is to make each operator

    a function of two stacks.  the tck2 implementation of linrec,

        linrec	[i] [t] [e] [f] ->		if i then t else: e, recurse, f

    uses the input stack to avoid explicit recursion (which is the technique i

    use in tck1, and also in cK).  for example, tck2 for manfred's linrec-

    implementation of factorial is:

        fact:d[((0;=);(1;+);(dup;-1;+);,(*);linrec)]

    [i] is (0;=), [t] is (1;+), [e] is (dup;-1;+), and [f] is ,(*) (a singleton

    list).  fact is a K function, viz.,

      fact

    {(y;x,z)}[((0;=)

     (1;+)

     ({f[(-n)_ x;y].(-n)#x};-1;+)

     ,*

     {f[(-n)_ x;y].(-n)#x})]

    linrec and its companion linrec_, which simulates recursion, are:

        linrec:n[4]{[x;y;i;t;e;f](x;i,(i;t;e;f;x;`linrec_),y)}

        linrec_:n[6]{[x;y;b;i;t;e;f;s](s;:[b;t;e,(i;t;e;f;`linrec),f],y)}

    x and y are the result and input stacks.

    linrec pushes i, unquoted, onto the input stack, so that it's the next thing

    to be evaluated, after which come (i;t;e;f;x;`linrec_),y.

    linrec_ implements the recursion part of the combinator:  b is the result

    of evaluating i, and if it's true, then t is pushed onto the input stack,

    else e, then (i;t;e;f;`linrec),f.

    it looks complicated, but that's only because we need to keep track of

    six or seven items.  the execution-trace is on the long side, but you can

    get a sense of what's going on, especially if you look at the end:

       t(5;fact)                        / trace 5 fact

    ((()                                / result stack

      (5;{(y;x,z)}[((0;=)               / input stack

        (1;+)

        ({f[(-n)_ x;y].(-n)#x};-1;+)

        ,*

        {f[(-n)_ x;y].(-n)#x})]))

     (,5                                / result stack

      ,{(y;x,z)}[((0;=)                 / input stack

        (1;+)

        ({f[(-n)_ x;y].(-n)#x};-1;+)

        ,*

        {f[(-n)_ x;y].(-n)#x})])

     (,5                                / etc.

      ((0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       {f[(-n)_ x;y].(-n)#x}))

     ((5

       (0;=))

      ((1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       {f[(-n)_ x;y].(-n)#x}))

     ((5

       (0;=)

       (1;+))

      (({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       {f[(-n)_ x;y].(-n)#x}))

     ((5

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+))

      (,*

       {f[(-n)_ x;y].(-n)#x}))

     ((5

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*)

      ,{f[(-n)_ x;y].(-n)#x})

     (,5

      (0

       =

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       ,5

       `linrec_))

     (5 0

      (=

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       ,5

       `linrec_))

     (,0

      ((0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       ,5

       `linrec_))

     ((0

       (0;=))

      ((1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       ,5

       `linrec_))

     ((0

       (0;=)

       (1;+))

      (({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       ,5

       `linrec_))

     ((0

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+))

      (,*

       ,5

       `linrec_))

     ((0

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*)

      (,5

       `linrec_))

     ((0

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       ,5)

      ,`linrec_)

     (,5

      ({f[(-n)_ x;y].(-n)#x}

       -1

       +

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *))

     (5 5

      (-1

       +

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *))

     (5 5 -1

      (+

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *))

     (5 4

      ((0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *))

     ((5

       4

       (0;=))

      ((1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *))

     ((5

       4

       (0;=)

       (1;+))

      (({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *))

     ((5

       4

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+))

      (,*

       `linrec

       *))

     ((5

       4

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*)

      (`linrec;*))

     (5 4

      (0

       =

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4

       `linrec_

       *))

     (5 4 0

      (=

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4

       `linrec_

       *))

     (5 0

      ((0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4

       `linrec_

       *))

     ((5

       0

       (0;=))

      ((1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4

       `linrec_

       *))

     ((5

       0

       (0;=)

       (1;+))

      (({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4

       `linrec_

       *))

     ((5

       0

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+))

      (,*

       5 4

       `linrec_

       *))

     ((5

       0

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*)

      (5 4

       `linrec_

       *))

     ((5

       0

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4)

      (`linrec_;*))

     (5 4

      ({f[(-n)_ x;y].(-n)#x}

       -1

       +

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *

       *))

     (5 4 4

      (-1

       +

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *

       *))

     (5 4 4 -1

      (+

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *

       *))

     (5 4 3

      ((0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *

       *))

     ((5

       4

       3

       (0;=))

      ((1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *

       *))

     ((5

       4

       3

       (0;=)

       (1;+))

      (({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *

       *))

     ((5

       4

       3

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+))

      (,*

       `linrec

       *

       *))

     ((5

       4

       3

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*)

      (`linrec;*;*))

     (5 4 3

      (0

       =

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4 3

       `linrec_

       *

       *))

     (5 4 3 0

      (=

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4 3

       `linrec_

       *

       *))

     (5 4 0

      ((0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4 3

       `linrec_

       *

       *))

     ((5

       4

       0

       (0;=))

      ((1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4 3

       `linrec_

       *

       *))

     ((5

       4

       0

       (0;=)

       (1;+))

      (({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4 3

       `linrec_

       *

       *))

     ((5

       4

       0

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+))

      (,*

       5 4 3

       `linrec_

       *

       *))

     ((5

       4

       0

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*)

      (5 4 3

       `linrec_

       *

       *))

     ((5

       4

       0

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4 3)

      (`linrec_;*;*))

     (5 4 3

      ({f[(-n)_ x;y].(-n)#x}

       -1

       +

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *

       *

       *))

     (5 4 3 3

      (-1

       +

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *

       *

       *))

     (5 4 3 3 -1

      (+

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *

       *

       *))

     (5 4 3 2

      ((0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *

       *

       *))

     ((5

       4

       3

       2

       (0;=))

      ((1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *

       *

       *))

     ((5

       4

       3

       2

       (0;=)

       (1;+))

      (({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *

       *

       *))

     ((5

       4

       3

       2

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+))

      (,*

       `linrec

       *

       *

       *))

     ((5

       4

       3

       2

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*)

      (`linrec;*;*;*))

     (5 4 3 2

      (0

       =

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4 3 2

       `linrec_

       *

       *

       *))

     (5 4 3 2 0

      (=

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4 3 2

       `linrec_

       *

       *

       *))

     (5 4 3 0

      ((0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4 3 2

       `linrec_

       *

       *

       *))

     ((5

       4

       3

       0

       (0;=))

      ((1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4 3 2

       `linrec_

       *

       *

       *))

     ((5

       4

       3

       0

       (0;=)

       (1;+))

      (({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4 3 2

       `linrec_

       *

       *

       *))

     ((5

       4

       3

       0

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+))

      (,*

       5 4 3 2

       `linrec_

       *

       *

       *))

     ((5

       4

       3

       0

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*)

      (5 4 3 2

       `linrec_

       *

       *

       *))

     ((5

       4

       3

       0

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4 3 2)

      (`linrec_;*;*;*))

     (5 4 3 2

      ({f[(-n)_ x;y].(-n)#x}

       -1

       +

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *

       *

       *

       *))

     (5 4 3 2 2

      (-1

       +

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *

       *

       *

       *))

     (5 4 3 2 2 -1

      (+

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *

       *

       *

       *))

     (5 4 3 2 1

      ((0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *

       *

       *

       *))

     ((5

       4

       3

       2

       1

       (0;=))

      ((1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *

       *

       *

       *))

     ((5

       4

       3

       2

       1

       (0;=)

       (1;+))

      (({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *

       *

       *

       *))

     ((5

       4

       3

       2

       1

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+))

      (,*

       `linrec

       *

       *

       *

       *))

     ((5

       4

       3

       2

       1

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*)

      (`linrec;*;*;*;*))

     (5 4 3 2 1

      (0

       =

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4 3 2 1

       `linrec_

       *

       *

       *

       *))

     (5 4 3 2 1 0

      (=

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4 3 2 1

       `linrec_

       *

       *

       *

       *))

     (5 4 3 2 0

      ((0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4 3 2 1

       `linrec_

       *

       *

       *

       *))

     ((5

       4

       3

       2

       0

       (0;=))

      ((1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4 3 2 1

       `linrec_

       *

       *

       *

       *))

     ((5

       4

       3

       2

       0

       (0;=)

       (1;+))

      (({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4 3 2 1

       `linrec_

       *

       *

       *

       *))

     ((5

       4

       3

       2

       0

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+))

      (,*

       5 4 3 2 1

       `linrec_

       *

       *

       *

       *))

     ((5

       4

       3

       2

       0

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*)

      (5 4 3 2 1

       `linrec_

       *

       *

       *

       *))

     ((5

       4

       3

       2

       0

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4 3 2 1)

      (`linrec_;*;*;*;*))

     (5 4 3 2 1

      ({f[(-n)_ x;y].(-n)#x}

       -1

       +

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *

       *

       *

       *

       *))

     (5 4 3 2 1 1

      (-1

       +

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *

       *

       *

       *

       *))

     (5 4 3 2 1 1 -1

      (+

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *

       *

       *

       *

       *))

     (5 4 3 2 1 0

      ((0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *

       *

       *

       *

       *))

     ((5

       4

       3

       2

       1

       0

       (0;=))

      ((1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *

       *

       *

       *

       *))

     ((5

       4

       3

       2

       1

       0

       (0;=)

       (1;+))

      (({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       `linrec

       *

       *

       *

       *

       *))

     ((5

       4

       3

       2

       1

       0

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+))

      (,*

       `linrec

       *

       *

       *

       *

       *))

     ((5

       4

       3

       2

       1

       0

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*)

      (`linrec;*;*;*;*;*))

     (5 4 3 2 1 0

      (0

       =

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4 3 2 1 0

       `linrec_

       *

       *

       *

       *

       *))

     (5 4 3 2 1 0 0

      (=

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4 3 2 1 0

       `linrec_

       *

       *

       *

       *

       *))

     (5 4 3 2 1 1

      ((0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4 3 2 1 0

       `linrec_

       *

       *

       *

       *

       *))

     ((5

       4

       3

       2

       1

       1

       (0;=))

      ((1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4 3 2 1 0

       `linrec_

       *

       *

       *

       *

       *))

     ((5

       4

       3

       2

       1

       1

       (0;=)

       (1;+))

      (({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4 3 2 1 0

       `linrec_

       *

       *

       *

       *

       *))

     ((5

       4

       3

       2

       1

       1

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+))

      (,*

       5 4 3 2 1 0

       `linrec_

       *

       *

       *

       *

       *))

     ((5

       4

       3

       2

       1

       1

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*)

      (5 4 3 2 1 0

       `linrec_

       *

       *

       *

       *

       *))

     ((5

       4

       3

       2

       1

       1

       (0;=)

       (1;+)

       ({f[(-n)_ x;y].(-n)#x};-1;+)

       ,*

       5 4 3 2 1 0)

      (`linrec_;*;*;*;*;*))

     (5 4 3 2 1 0

      (1;+;*;*;*;*;*))

     (5 4 3 2 1 0 1

      (+;*;*;*;*;*))

     (5 4 3 2 1 1

      (*;*;*;*;*))

     (5 4 3 2 1

      (*;*;*;*))

     (5 4 3 2

      (*;*;*))

     (5 4 6

      (*;*))

     (5 24

      ,*)

     (,120            <-- final result

      ()))            <-- nothing left to evaluate

    the code for all this is at

        http://www.nsl.com/k/tck

    at some point, i'd like to rewrite cK to use this technique.  although it's

    less intuitive than explicit recursion, it makes the totality of program,

    past and future, available to every operator at every point.

     ----- Original Message -----

    From: "paul_virak_khuong" <paul_virak_khuong@...>

    To: <concatenative@yahoogroups.com>

    Sent: Monday, June 14, 2004 1:04 PM

    Subject: [stack] Re: the false programming language

    --- In concatenative@yahoogroups.com, phimvt@l... wrote:

    >

    > On Mon, 24 May 2004, Paul-V Khuong wrote:

    [...]

    > > I'm not quite sure of what i am advancing, but if one

    > > implements stacks as linked lists (à la lisp), doesn't

    > > this disadvantage disappear? Pushing a link on a stack

    > > should be a simple matter of alterating a few CDRs and

    > > updating the stack pointer.

    >

    > That depends. There are several ways of implementing all the

    > requisite "push-onto-the-program-stack". Let Q = [x y1 y2 ...yN z]

    > be the program fragment to be pushed from the stack back onto

    > the program P

    >

    > 2. Destructive concatenation:

    > Find z, change its nil (cdr, end-of-list) field to point to the

    beginning

    > of P. Finding z is fast, changing the cdr is trivial). BUT: this

    > destroys the original structure of Q. If there are other links

    > pointing to Q (as there would be if it had been "dup"ed, or

    something

    > similar), this would be disastrous for a language like Joy.

    Unless dup deep-copies everything, that is (only works for a typeful

    language).

    > 3. Lazy concatenation:

    > Allow "pairing nodes" for the program stack. Replace P by

    > a single node "pair(Q,P)" - meaning: these are to be concatenated

    > to form a single list (stack). Fast, only needs one new node,

    > irrespective of how long Q is. But it is a new concept, and

    > the runtime system will need to know how to handle such new nodes.

    It seems to me it also means that we can't simply pass a pointer

    anymore, and that we either have to provide backpointers (like

    double-linked lists), or have O(n) instead of O(n) access time.

    > 4. Recursion in the runtime system:

    > Instead if shifting anything from the stack to the program, the

    > runtime system recursively calls itself to execute Q (which has been

    > popped) and when that is done it returns to executing P. (This

    > is the method which the Joy interpreter uses - function "exeterm")

    Yes, i think this is the standard method, and works very well. The

    only disadvantage i see is that working with continuations might be

    weird. On the other hand, it does seem to provide better performance

    in most cases.

    > >                               Note that i am currently

    > > working on such a system, where i try to stick as much

    > > as possible to the linearity of stack languages, so i

    > > might have some blinders on.

    >

    > Keep in mind that once nesting to arbitrary depth is allowed,

    > even in linear languages, recursion is often an excellent way

    > to deal with it.

    What exactly do you mean?

    > [...]

    >

    > > PS. Pseudo-closures can be created with lambda-lifting

    > > and tacking arguments in front of the function.

    > > However, lambda-lifting makes it impossible for

    > > different functions to share [mutable] variables. Does

    > > anyone see a way to allow such shared variables?

    >

    > could you elaborate on this, please ?

    Sure. This only works if we can easily define functions at runtime

    (here in a lispy language (since that's what i'm most comfortable

    with)).

    (defun plus-x (x)

      (lambda (y) (+ x y)))

    What we have is a function that generates a closure

    (function+environment) that adds a certain number to its input. x is

    free in the lambda, so it must be kept in the environment. What we

    could instead do is have sometihng like this:

    (defun plus-x (x)

      (lambda (y)

        ((lambda (x y) (+ x y)) x)))

    IIRC, http://www.iro.umontreal.ca/~feeley/papers/complang92.ps.gz

    describes a similar process, and it surely is more authoritative on

    the subject than i am (this is all from memory, so the implementation

    might very well be ok, but the explanations not :D). This is lisp, so

    they're probably passing pointers around, not litterals, thus allowing

    variable sharing & mutability.

    In a stack language that could translate into something like this:

    [plus-x 5] returns [5 +]. In short, instead of having free variables,

    we define them as arguments, whose values are passed around with the

    function - this is basically the same as closures in languages that

    don't support this, but in those who do, it means the environment is

    instead compiled as litterals. Since it is compiled in, it also means

    that they can't be modified. The traditional (FP, since pointers do

    the job very well otherwise) way of simulating mutability is to have

    the function return its updated self too, but i don't see how this

    allows the sharing of variables between multiple closures, unless one

    passes around an object representing all the closures that share

    variables together.

    Paul

    Yahoo! Groups Links

## phimvt@lurac.latrobe.edu.au — 2004-06-16 06:39:28

    On Mon, 14 Jun 2004, paul_virak_khuong wrote:

     > --- In concatenative@yahoogroups.com, phimvt@l... wrote:

     [..]

     > > 2. Destructive concatenation:

    > > Find z, change its nil (cdr, end-of-list) field to point to the

    > beginning

    > > of P. Finding z is fast, changing the cdr is trivial). BUT: this

    > > destroys the original structure of Q. If there are other links

    > > pointing to Q (as there would be if it had been "dup"ed, or

    > something

    > > similar), this would be disastrous for a language like Joy.

    >

    > Unless dup deep-copies everything, that is (only works for a typeful

    > language).

     Yes, you are quite right of course. I was assuming that if the

    stack uses links, and any lists in it and in the program stack are

    linked, then dup woud just duplicate a single pointer, and not the deep

    structure. The assumption is probably true in most implementations,

    but, as you point out, it need not be.

     >

    > > 3. Lazy concatenation:

    > > Allow "pairing nodes" for the program stack. Replace P by

    > > a single node "pair(Q,P)" - meaning: these are to be concatenated

    > > to form a single list (stack). Fast, only needs one new node,

    > > irrespective of how long Q is. But it is a new concept, and

    > > the runtime system will need to know how to handle such new nodes.

    > It seems to me it also means that we can't simply pass a pointer

    > anymore, and that we either have to provide backpointers (like

    > double-linked lists), or have O(n) instead of O(n) access time.

     The pairing node will have to have some sort of identification

    to say that it is a paring node (several possible methods), and

    two pointers - one to P, one to Q. To execute a pairing node,

    execute the P part and then the Q part (maybe as in 4. below,

    but then nothing is gained by having the pairing node). I don't

    think double linking will be necessary. Incidentally, what I called

    pairing node is just the cons-node of Lisp.

    [..]

     > > >                               Note that i am currently

    > > > working on such a system, where i try to stick as much

    > > > as possible to the linearity of stack languages, so i

    > > > might have some blinders on.

    > >

    > > Keep in mind that once nesting to arbitrary depth is allowed,

    > > even in linear languages, recursion is often an excellent way

    > > to deal with it.

    > What exactly do you mean?

     For example [[[[2 3 +] i] i] i] i] i  or any nested program.

    Or ifte's inside ifte's inside ifte's.

     > > [...]

    > >

    > > > PS. Pseudo-closures can be created with lambda-lifting

    > > > and tacking arguments in front of the function.

    > > > However, lambda-lifting makes it impossible for

    > > > different functions to share [mutable] variables. Does

    > > > anyone see a way to allow such shared variables?

    > >

    > > could you elaborate on this, please ?

    > Sure. This only works if we can easily define functions at runtime

    > (here in a lispy language (since that's what i'm most comfortable

    > with)).

    >

    > (defun plus-x (x)

    >   (lambda (y) (+ x y)))

    >

    > What we have is a function that generates a closure

    > (function+environment) that adds a certain number to its input. x is

    > free in the lambda, so it must be kept in the environment. What we

    > could instead do is have sometihng like this:

    >

    > (defun plus-x (x)

    >   (lambda (y)

    >     ((lambda (x y) (+ x y)) x)))

    >

    > IIRC, http://www.iro.umontreal.ca/~feeley/papers/complang92.ps.gz

    > describes a similar process, and it surely is more authoritative on

    > the subject than i am (this is all from memory, so the implementation

    > might very well be ok, but the explanations not :D). This is lisp, so

    > they're probably passing pointers around, not litterals, thus allowing

    > variable sharing & mutability.

     If the familiar Lisp-in-Lisp is a guide, then a closure is indeed

    a pair of pointers, one to the current environment, an one to the

    lambda expression.

     >

    > In a stack language that could translate into something like this:

    > [plus-x 5] returns [5 +]. In short, instead of having free variables,

    > we define them as arguments, whose values are passed around with the

    > function - this is basically the same as closures in languages that

    > don't support this, but in those who do, it means the environment is

    > instead compiled as litterals. Since it is compiled in, it also means

    > that they can't be modified. The traditional (FP, since pointers do

    > the job very well otherwise) way of simulating mutability is to have

    > the function return its updated self too, but i don't see how this

    > allows the sharing of variables between multiple closures, unless one

    > passes around an object representing all the closures that share

    > variables together.

     Thank you for the long clarification. I was familiar with closures

    (I have used them a lot in backtracking programmes in Pascal, and

    also in my Joy implementation of minimal Lisp). It was the term

    "lambda lifting" which threww me. Thanks.

      - Manfred