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.)

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
>
>
>
>
>

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.)
>

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
>
>
>
>
>

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

----- 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
>
>
>
>
>

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

----- 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.

> 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

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

--- 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

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

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

the false programming language

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

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

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

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

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

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

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

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

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

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

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

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

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