unary functions from X to Y?

[John Nowak]

In my email prior to this one, I suggested that the definition of  
concatenative languages should be limited such that all functions are  
unary functions from some aggregate X to some aggregate Y where X and  
Y are both the same "type" (e.g. a stack or a stack/queue tuple). This  
definition covers all existing concatenative languages. More  
importantly however, it rules out languages like FP where functions  
can do things like take a list and return a number.

My first question then is if anyone agrees that this is a useful  
restriction.

Should we agree it's useful, the next thing I'd want to try is to  
determine an aggregate type that would be valid for all existing  
concatenative languages. To start, all existing concatenative  
languages include a stack. Some include more than a stack however, so  
our aggregate type must be a tuple of a stack and something else.

XY offers a queue representing the future of a computation, but really  
all concatenative languages can be viewed in terms of having such a  
queue; some languages simply don't make it programmer-accessible. I  
think it therefore reasonable to add a queue to our tuple.

Factor offers a retain stack (the direct use of which is nearly  
eliminated at this point I think). We do not need to add this to our  
tuple however because we can simply view it as being passed around on  
the top of the stack. After all, the retain stack can only represent  
the "past" in terms of the current computation, so it makes sense to  
group it in with the "main" stack which holds the sum of past  
computation.

Forth offers a return stack. It may be possible to formulate this as  
part of the queue, but it's not clear to me exactly how this would  
work. I wonder if it may be cleaner to add the return stack to our  
tuple. In this scenario, the "main" stack is the past of the  
computation, the queue is the future, and the return stack is the  
"present" of the computation. The utility of separating the "present"  
from the "future" is that Forth can manipulate the present using r>  
and >r. It cannot, as far as I know, manipulate the "future" in any way.

Alright. So very, very tentatively, I'm going to propose we look at  
functions in a concatenative language as taking a past/present/future  
tuple and returning a new past/present/future tuple. Alternatively, we  
could say concatenative languages take a tuple of things "already  
done", things "currently in progress", and things "yet to start". We  
could then classify concatenative languages by which elements of that  
tuple are made user-accessible: Joy would make only the past  
accessible, Forth would make the past and present accessible, and XY  
would make the past and future accessible.

This is just a very rough idea. Any thoughts would be much  
appreciated. Specifically, I am unsure if separating the "present" and  
the "future" is a valid approach. I do not, however, have a way of  
removing the need for the "present" in the case of Forth at the  
moment; viewing the return stack as part of the queue seems  
inappropriate. More precisely, it would mean that only part of the  
queue would be user-accessible. Having to deal with "parts" would make  
the classification system less useful. Perhaps Forth's return stack  
access is a unique property we can avoid dealing with and could  
therefore reclassify Forth as a "mostly concatenative" language or  
somehow "pre-concatenative". Then again, perhaps not, and we'd have to  
find a way of dealing with it.

- John

[zallambo]

--- In concatenative@..., John Nowak <john@...> wrote:

>
> In my email prior to this one, I suggested that the definition of  
> concatenative languages should be limited such that all functions are  
> unary functions from some aggregate X to some aggregate Y where X and  
> Y are both the same "type" (e.g. a stack or a stack/queue tuple). This  
> definition covers all existing concatenative languages. More  
> importantly however, it rules out languages like FP where functions  
> can do things like take a list and return a number.
>
> My first question then is if anyone agrees that this is a useful  
> restriction.
>
> Should we agree it's useful, the next thing I'd want to try is to  
> determine an aggregate type that would be valid for all existing  
> concatenative languages. To start, all existing concatenative  
> languages include a stack. Some include more than a stack however, so  
> our aggregate type must be a tuple of a stack and something else.
>
> XY offers a queue representing the future of a computation, but really  
> all concatenative languages can be viewed in terms of having such a  
> queue; some languages simply don't make it programmer-accessible. I  
> think it therefore reasonable to add a queue to our tuple.
>
> Factor offers a retain stack (the direct use of which is nearly  
> eliminated at this point I think). We do not need to add this to our  
> tuple however because we can simply view it as being passed around on  
> the top of the stack. After all, the retain stack can only represent  
> the "past" in terms of the current computation, so it makes sense to  
> group it in with the "main" stack which holds the sum of past  
> computation.
>
> Forth offers a return stack. It may be possible to formulate this as  
> part of the queue, but it's not clear to me exactly how this would  
> work. I wonder if it may be cleaner to add the return stack to our  
> tuple. In this scenario, the "main" stack is the past of the  
> computation, the queue is the future, and the return stack is the  
> "present" of the computation. The utility of separating the "present"  
> from the "future" is that Forth can manipulate the present using r>  
> and >r. It cannot, as far as I know, manipulate the "future" in any way.
>
> Alright. So very, very tentatively, I'm going to propose we look at  
> functions in a concatenative language as taking a past/present/future  
> tuple and returning a new past/present/future tuple. Alternatively, we  
> could say concatenative languages take a tuple of things "already  
> done", things "currently in progress", and things "yet to start". We  
> could then classify concatenative languages by which elements of that  
> tuple are made user-accessible: Joy would make only the past  
> accessible, Forth would make the past and present accessible, and XY  
> would make the past and future accessible.
>
> This is just a very rough idea. Any thoughts would be much  
> appreciated. Specifically, I am unsure if separating the "present" and  
> the "future" is a valid approach. I do not, however, have a way of  
> removing the need for the "present" in the case of Forth at the  
> moment; viewing the return stack as part of the queue seems  
> inappropriate. More precisely, it would mean that only part of the  
> queue would be user-accessible. Having to deal with "parts" would make  
> the classification system less useful. Perhaps Forth's return stack  
> access is a unique property we can avoid dealing with and could  
> therefore reclassify Forth as a "mostly concatenative" language or  
> somehow "pre-concatenative". Then again, perhaps not, and we'd have to  
> find a way of dealing with it.
>
> - John
>

Let's start with the definition:
"A concatenative programming language is one in which all terms denote functions and the juxtaposition of functions denotes function composition."

Assuming any two terms can be juxtaposed, then any two functions can be composed, so as you said the domain and range of every function must be of the same "type".

By this definition Cat is concatenative, but Joy and XY are not. The trouble is that while function composition forms a monoid (it has an identity and is associative), it is more specific than a monoid. Specifically, it has the following property:

If a function g maps all values to the same value (say v), then for every function f, f.g maps all values to v. (here '.' denotes composition)

Joy's 'abort' term breaks this property, as does '=>' in XY.

For instance, suppose 'two!' takes any stack and produces a stack with just one element, '2'. Then 'f two!' should produce the stack '2' for all terms f. But:

3 abort two!   ==   3
3 => two!      ==   2 3.

I have yet to find a problem with pushing onto the "future" if it is considered a stack rather than a queue.

If the concatenation of terms is to denote function composition, you have to be very careful which mutations you allow on the "future". From a mathematical perspective, it doesn't make sense to talk about composing "functions" that are allowed to act on each other.

I'll have more to say in a couple days, after my finals.

Justin

[John Nowak]

On Mar 6, 2009, at 1:30 AM, Justin Pombrio wrote:

> If a function g maps all values to the same value (say v), then for  
> every function f, f.g maps all values to v. (here '.' denotes  
> composition)

Aye.

> Joy's 'abort' term breaks this property, as does '=>' in XY.

I was not aware of 'abort'; you are certainly right it seems. As I  
know very little about XY, I'll have to take your word for it  
regarding '=>'.

> I have yet to find a problem with pushing onto the "future" if it is  
> considered a stack rather than a queue.

I believe you're correct. To be honest, I always thought it *was* a  
stack, and was simply called the queue because it held the rest of the  
program "in queue". I now see that the "next" function is at the  
opposite end from where you're operating. Not at all what I expected.  
I can't even fathom what I'd do with that.

I suppose I should actually use XY one of these days... at least  
before I make any more claims about it. Until then, please consider my  
proposal void.

- John

[Chris Double]

On Fri, Mar 6, 2009 at 8:02 PM, John Nowak <john@...> wrote:
> I was not aware of 'abort'; you are certainly right it seems. As I
> know very little about XY, I'll have to take your word for it
> regarding '=>'.

'=>' is a it like >r in factor except it doesn't use a separate retain
stack. It takes 1 item off the stack and places it at the tail of the
queue. If it's not popped off later with '<=' it gets executed when
the queue reaches that point.

> I suppose I should actually use XY one of these days... at least
> before I make any more claims about it. Until then, please consider my
> proposal void.

I have mostly working JS implementation:

http://tech.groups.yahoo.com/group/concatenative/message/4305

It doesn't do the projection thing mentioned above however.

Chris.
--
http://www.bluishcoder.co.nz

[Chris Double]

On Fri, Mar 6, 2009 at 7:30 PM, Justin Pombrio <zallambo@...> wrote:
> For instance, suppose 'two!' takes any stack and produces a stack with just
> one element, '2'. Then 'f two!' should produce the stack '2' for all terms
> f. But:
>
> 3 abort two! == 3
> 3 => two! == 2 3.
>

I'm not sure this is correct for XY. 'f two!' for XY, where f is any
term,  will always produce a stack '2'. The example you give is
effectively:

> two! 3 == 2 3

This is because the '3' is appended to the tail of the queue. Which
then gets executed. The function 'two!' is still give a stack (which
is empty) and returns a stack containing 2.

Chris.
--
http://www.bluishcoder.co.nz

[Chris Double]

On Fri, Mar 6, 2009 at 8:15 PM, Chris Double <chris.double@...> wrote:
>
> It doesn't do the projection thing mentioned above however.

Which I didn't actually mention, so ignore :-)

Chris.

[John Nowak]

On Mar 6, 2009, at 2:57 AM, Chris Double wrote:

> On Fri, Mar 6, 2009 at 8:15 PM, Chris Double <chris.double@...
> > wrote:
>>
>> It doesn't do the projection thing mentioned above however.
>
> Which I didn't actually mention, so ignore :-)

Projection doesn't make any sense to me in a stack-based language.  
It's clear how it works and why you'd want it in something like J  
where you have dyadic functions. In a stack-based language however,  
all functions are unary. Adding projection would seem to complicate  
the semantics for very little benefit. If someone thinks otherwise,  
I'd be glad to hear why.

- John

[spir]

Le Thu, 5 Mar 2009 19:44:23 -0500,
John Nowak <john@...> s'exprima ainsi:

> In my email prior to this one, I suggested that the definition of  
> concatenative languages should be limited such that all functions are  
> unary functions from some aggregate X to some aggregate Y where X and  
> Y are both the same "type" (e.g. a stack or a stack/queue tuple). This  
> definition covers all existing concatenative languages. More  
> importantly however, it rules out languages like FP where functions  
> can do things like take a list and return a number.

Now I tend to see concatenative programming as expressing
        a process where each stage's output is the input of the next stage.

Rather close to pipeline. In this definition, the data format is unspecified, if not irrelevant, as well as the relative format of several stages' data.
Following John's "unary functions from X to Y", pipelines seem not far away. Or do I misinterpret the intent?

Denis
------
la vita e estrany

[John Nowak]

On Mar 6, 2009, at 4:14 AM, spir wrote:

> Following John's "unary functions from X to Y", pipelines seem not  
> far away. Or do I misinterpret the intent?

That's correct. Concatenative languages are similar to unix pipes.

- John

[zallambo]

--- In concatenative@..., Chris Double <chris.double@...> wrote:

>
> On Fri, Mar 6, 2009 at 7:30 PM, Justin Pombrio <zallambo@...> wrote:
> > For instance, suppose 'two!' takes any stack and produces a stack with just
> > one element, '2'. Then 'f two!' should produce the stack '2' for all terms
> > f. But:
> >
> > 3 abort two! == 3
> > 3 => two! == 2 3.
> >
>
> I'm not sure this is correct for XY. 'f two!' for XY, where f is any
> term,  will always produce a stack '2'. The example you give is
> effectively:
>
> > two! 3 == 2 3
>
> This is because the '3' is appended to the tail of the queue. Which
> then gets executed. The function 'two!' is still give a stack (which
> is empty) and returns a stack containing 2.
>
> Chris.
> --
> http://www.bluishcoder.co.nz
>

Do you agree that the following two equivalences hold?
3 => two!   ==   two! 3   ==   2 3

I'm not saying that this is nonsensical or a contradiction, it's just not how *function composition* works. If this were actually function composition, then *any* program ending with the term 'two!' would produce the stack '2'.

I should have been more specific. I meant that 'P two!' should always produce the stack '2' for *any* program P.

Justin

[Chris Double]

On Sat, Mar 7, 2009 at 5:47 AM, Justin Pombrio <zallambo@...> wrote:
> Do you agree that the following two equivalences hold?
> 3 => two! == two! 3 == 2 3

These hold for your original definition of 'two!', yes.

> I should have been more specific. I meant that 'P two!' should always
> produce the stack '2' for *any* program P.

Then 'two!' should be written to do this, and it can be:

; two! [2] -> ;

3 => two! == 2

Chris.

[stevan apter]

XY went through several versions.  i'm not sure which one chris
has implemented.  the version i was most satisfied with is what
i called "XY 0".  a precis of the languages is written up here:

http://www.nsl.com/k/xy/xy.txt

XY 0 has:

        ->      queue           [X^z Y] -> [X z]
        <-      stack           [X^z Y] -> [z Y]

        =>      cache           [X^z Y] -> [X Y^z]
        <=      uncache         [X Y^z] -> [X^z Y]

        /       use             [X^z Y] -> [X z,Y]
        \       mention         [X z^Y] -> [X^z Y]

        `       enclose         [X^z Y] -> [X^{z} Y]
                disclose        [X^{z} Y] -> [X^z Y]

        (       stack*          [X Y] -> [X^[X] Y]
        )       queue*          [X Y] -> [X^[Y] Y]

in particular, note enclose/disclose, which makes a function from
a quotation and vice-versa:

    2 [+]`
2 `[+]
    `
2 [+]

i think that XY functions are similar to what john has called "function
objects."  the concatenation of two quotations is a quotation whose
parts are the parts of the concatenated quotations, but the concatenation
of two functions is a quotation whose parts are the functions:

  [2 +]` [3 +]` ,   // concatenate two functions
[[2 +]` [3 +]`]
  #:                // count
2

(there are other possibilities, e.g. the concatenation of two functions
is a function which concatenates the results of applying the functions,
&c.)

XY has three reserved names:  _x, _y, and _z, which represents the past,
present, and future of the computation as it is perceived by the executing
pattern:

        _x      the stack minus the elements mapped to the template
        _y      the queue minus the current pattern
        _z      the current pattern

XY 0 disposes of these (and patterns as well) and replaces them with (
and ), which can be used to retrieve the same information (but don't
ask me how.)

i will speculate that it can't be that difficult to modify the evaluator
to produce functions instead of verbs.  e.g. instead of:

    2 [+] *:        // first of [+]
  2 +

we could have:

    2 [+] *:
  2 `+

the main idea behind XY was to find a structure which could be used
to "transcend" the search for alternate bases, e.g. do we use {dup,
dip, pop} or {nip, tuck} or ... ?  in the first place, i could never
remember how the more exotic operations worked.  and there was also
this problem:  although a quotation like [pop dup swap] contains
all the information about the before and after state of the stack,
any program which tries to analyze the meaning of that quotation
will have to look up the stack effects in some table.  stack operation
words are "opaque".

also, it seemed to me that the various forms of shuffle-notation (which
are not opaque if their parts are available) are not quite powerful
enough to define all the stack operations (e.g. dip) without turning into
full-blown lambdas with named arguments.  

once i had introduced the queue as a first-class entity on par with the
stack, these questions became irrelevant, and some new opportunities appeared,
e.g. the ability to define various forms of the continuation control.  
and the idea of having both the past and future of the computation
available to the computation was philosophically appealing.

----- Original Message -----
From: "Chris Double" <chris.double@...>
To: <concatenative@...>
Sent: Friday, March 06, 2009 2:15 AM
Subject: Re: [stack] Re: unary functions from X to Y?

> On Fri, Mar 6, 2009 at 8:02 PM, John Nowak <john@...> wrote:
>> I was not aware of 'abort'; you are certainly right it seems. As I
>> know very little about XY, I'll have to take your word for it
>> regarding '=>'.
>
> '=>' is a it like >r in factor except it doesn't use a separate retain
> stack. It takes 1 item off the stack and places it at the tail of the
> queue. If it's not popped off later with '<=' it gets executed when
> the queue reaches that point.
>
>> I suppose I should actually use XY one of these days... at least
>> before I make any more claims about it. Until then, please consider my
>> proposal void.
>
> I have mostly working JS implementation:
>
> http://tech.groups.yahoo.com/group/concatenative/message/4305
>
> It doesn't do the projection thing mentioned above however.
>
> Chris.
> --
> http://www.bluishcoder.co.nz
>

[stevan apter]

i'd forgotten that XY has both lists (e.g. (2 3 +) -> [5]) and quotations.
but XY 0 has only quotations.


----- Original Message -----
From: "Stevan Apter" <sa@...>
To: <concatenative@...>
Sent: Saturday, March 07, 2009 11:14 AM
Subject: some thoughts on XY [was Re: [stack] Re: unary functions from X to Y?]

> XY went through several versions.  i'm not sure which one chris
> has implemented.  the version i was most satisfied with is what
> i called "XY 0".  a precis of the languages is written up here:
>
> http://www.nsl.com/k/xy/xy.txt
>
> XY 0 has:
>
>        ->      queue           [X^z Y] -> [X z]
>        <-      stack           [X^z Y] -> [z Y]
>
>        =>      cache           [X^z Y] -> [X Y^z]
>        <=      uncache         [X Y^z] -> [X^z Y]
>
>        /       use             [X^z Y] -> [X z,Y]
>        \       mention         [X z^Y] -> [X^z Y]
>
>        `       enclose         [X^z Y] -> [X^{z} Y]
>                disclose        [X^{z} Y] -> [X^z Y]
>
>        (       stack*          [X Y] -> [X^[X] Y]
>        )       queue*          [X Y] -> [X^[Y] Y]
>
> in particular, note enclose/disclose, which makes a function from
> a quotation and vice-versa:
>
>    2 [+]`
> 2 `[+]
>    `
> 2 [+]
>
> i think that XY functions are similar to what john has called "function
> objects."  the concatenation of two quotations is a quotation whose
> parts are the parts of the concatenated quotations, but the concatenation
> of two functions is a quotation whose parts are the functions:
>
>  [2 +]` [3 +]` ,   // concatenate two functions
> [[2 +]` [3 +]`]
>  #:                // count
> 2
>
> (there are other possibilities, e.g. the concatenation of two functions
> is a function which concatenates the results of applying the functions,
> &c.)
>
> XY has three reserved names:  _x, _y, and _z, which represents the past,
> present, and future of the computation as it is perceived by the executing
> pattern:
>
>        _x      the stack minus the elements mapped to the template
>        _y      the queue minus the current pattern
>        _z      the current pattern
>
> XY 0 disposes of these (and patterns as well) and replaces them with (
> and ), which can be used to retrieve the same information (but don't
> ask me how.)
>
> i will speculate that it can't be that difficult to modify the evaluator
> to produce functions instead of verbs.  e.g. instead of:
>
>    2 [+] *:        // first of [+]
>  2 +
>
> we could have:
>
>    2 [+] *:
>  2 `+
>
> the main idea behind XY was to find a structure which could be used
> to "transcend" the search for alternate bases, e.g. do we use {dup,
> dip, pop} or {nip, tuck} or ... ?  in the first place, i could never
> remember how the more exotic operations worked.  and there was also
> this problem:  although a quotation like [pop dup swap] contains
> all the information about the before and after state of the stack,
> any program which tries to analyze the meaning of that quotation
> will have to look up the stack effects in some table.  stack operation
> words are "opaque".
>
> also, it seemed to me that the various forms of shuffle-notation (which
> are not opaque if their parts are available) are not quite powerful
> enough to define all the stack operations (e.g. dip) without turning into
> full-blown lambdas with named arguments.  
>
> once i had introduced the queue as a first-class entity on par with the
> stack, these questions became irrelevant, and some new opportunities appeared,
> e.g. the ability to define various forms of the continuation control.  
> and the idea of having both the past and future of the computation
> available to the computation was philosophically appealing.
>
> ----- Original Message -----
> From: "Chris Double" <chris.double@...>
> To: <concatenative@...>
> Sent: Friday, March 06, 2009 2:15 AM
> Subject: Re: [stack] Re: unary functions from X to Y?
>
>
>> On Fri, Mar 6, 2009 at 8:02 PM, John Nowak <john@...> wrote:
>>> I was not aware of 'abort'; you are certainly right it seems. As I
>>> know very little about XY, I'll have to take your word for it
>>> regarding '=>'.
>>
>> '=>' is a it like >r in factor except it doesn't use a separate retain
>> stack. It takes 1 item off the stack and places it at the tail of the
>> queue. If it's not popped off later with '<=' it gets executed when
>> the queue reaches that point.
>>
>>> I suppose I should actually use XY one of these days... at least
>>> before I make any more claims about it. Until then, please consider my
>>> proposal void.
>>
>> I have mostly working JS implementation:
>>
>> http://tech.groups.yahoo.com/group/concatenative/message/4305
>>
>> It doesn't do the projection thing mentioned above however.
>>
>> Chris.
>> --
>> http://www.bluishcoder.co.nz
>>
>

[Chris Double]

On Sun, Mar 8, 2009 at 5:14 AM, Stevan Apter <sa@...> wrote:
> XY went through several versions. i'm not sure which one chris
> has implemented. the version i was most satisfied with is what
> i called "XY 0".

It's mostly XY 2.0. It's flat, with markers plus lazy. I didn't
implement projections.

I'm still playing around with the implementation trying things out. I
don't know much about K, but I'm working through 'Q for Mortals' and
adding some of the ideas from Q into it to see what it's like to use.

What attracted me to playing around with XY is the ability to inspect
and modify the queue.

Chris.
--
http://www.bluishcoder.co.nz

[William Tanksley, Jr]

John Nowak wrote:
> In my email prior to this one, I suggested that the definition of  
> concatenative languages should be limited such that all functions are  
> unary functions from some aggregate X to some aggregate Y where X and  
> Y are both the same "type" (e.g. a stack or a stack/queue tuple). This  
> definition covers all existing concatenative languages. More  
> importantly however, it rules out languages like FP where functions  
> can do things like take a list and return a number.
> My first question then is if anyone agrees that this is a useful  
> restriction.

I agree.

> Should we agree it's useful, the next thing I'd want to try is to  
> determine an aggregate type that would be valid for all existing  
> concatenative languages. To start, all existing concatenative  
> languages include a stack. Some include more than a stack however, so  
> our aggregate type must be a tuple of a stack and something else.

I think all of them use more than a stack.

> XY offers a queue representing the future of a computation, but really  
> all concatenative languages can be viewed in terms of having such a  
> queue; some languages simply don't make it programmer-accessible. I  
> think it therefore reasonable to add a queue to our tuple.

Actually, a queue is a bad choice for the future structure. XY uses it
because it wanted an easy to do 'dip', but 'dip' doesn't require a
persistent structure. When used only to view and modify the future, XY
treats its queue as a stack -- which is the correct approach.

> Factor offers a retain stack (the direct use of which is nearly  
> eliminated at this point I think). We do not need to add this to our  
> tuple however because we can simply view it as being passed around on  
> the top of the stack. After all, the retain stack can only represent  
> the "past" in terms of the current computation, so it makes sense to  
> group it in with the "main" stack which holds the sum of past  
> computation.

Yes, the retain stack is part of the past (quite apart from it being
obsolete!) -- although I wouldn't want to model it as being "on" the
main stack.

> Forth offers a return stack. It may be possible to formulate this as  
> part of the queue, but it's not clear to me exactly how this would  
> work. I wonder if it may be cleaner to add the return stack to our  
> tuple. In this scenario, the "main" stack is the past of the  
> computation, the queue is the future, and the return stack is the  
> "present" of the computation. The utility of separating the "present"  
> from the "future" is that Forth can manipulate the present using r>  
> and >r. It cannot, as far as I know, manipulate the "future" in any way.

I don't understand what you're saying at all. The XY queue is
essentially a high-resolution return stack. Forth's return stack plus
its instruction pointer is similar to the queue -- it tells you what's
going to happen in the future.

I could understand you classifying the IP as being the 'present', in
which case XY's queue melds the present with the future -- but I don't
see much use in that, since really everything in the XY queue and
everything after the Forth IP is in the future.

XY lets you manipulate the future at a finer grain than Forth does.

> could then classify concatenative languages by which elements of that  
> tuple are made user-accessible: Joy would make only the past  
> accessible, Forth would make the past and present accessible, and XY  
> would make the past and future accessible.

The first question I think is appropriate would be not which parts are
open to programmer manipulation, but rather what the effects of
manipulations are. Appending stuff to XY's queue behaves very
differently from pushing stuff onto it.

> This is just a very rough idea. Any thoughts would be much  
> appreciated. Specifically, I am unsure if separating the "present" and  
> the "future" is a valid approach. I do not, however, have a way of  
> removing the need for the "present" in the case of Forth at the  
> moment; viewing the return stack as part of the queue seems  
> inappropriate. More precisely, it would mean that only part of the  
> queue would be user-accessible. Having to deal with "parts" would make  
> the classification system less useful. Perhaps Forth's return stack  
> access is a unique property we can avoid dealing with and could  
> therefore reclassify Forth as a "mostly concatenative" language or  
> somehow "pre-concatenative". Then again, perhaps not, and we'd have to  
> find a way of dealing with it.

Forth is hardly the only language to use an IP and a return stack -- it
seems odd to make a classification of languages that share the common
feature of being extremely resource-hungry to implement. It's probably
not a good idea to make the lynchpin of a classification system an
experimental feature of a single language.

With that said, though, I also disagree that having to deal with "parts"
is a problem. This is ALL experimental; we don't know the right way of
looking at the problem. I think Forth's system is terrible, since it
negates the benefits of easy factoring; but XY's system makes it hard to
look as far into the future as Forth's system can. But what about
partial continuations -- neither language provides those, although both
come close.

> - John

-Wm

[William Tanksley, Jr]

William Tanksley wrote:
> > XY offers a queue representing the future of a computation, but really  
> > all concatenative languages can be viewed in terms of having such a  
> > queue; some languages simply don't make it programmer-accessible. I  
> > think it therefore reasonable to add a queue to our tuple.
> Actually, a queue is a bad choice for the future structure. XY uses it
> because it wanted an easy to do 'dip', but 'dip' doesn't require a
> persistent structure. When used only to view and modify the future, XY
> treats its queue as a stack -- which is the correct approach.

On further though, I was wrong.

XY's queue is correctly viewed as the future of the entire program. So
is Forth's return stack. There are two major differences:

1. XY offers the ability to append and remove from the end of the
program. Forth doesn't; you can only modify future behavior for the near
future.

2. XY allows manipulation of functions down to the primitives level: in
other words, XY treats functions as transparent. Forth treats them as
opaque, and only allows you to add or remove them from the return stack
as an entire unit.

Both choices are interesting; but neither one seems to be fundamentally
different from the other. XY offers much easier access to the end of the
program (but you can get that in Forth by picking through the entire
return stack); and Forth offers much easier access to a
function-by-function description of what's about to happen (but you can
get that in XY by picking through the start of the queue). It would be
perfectly possible to add a function to Forth to append a new return
address to the bottom of the stack; it would be a total function change
to make XY treat functions as opaque.

I think the basic lesson is that Forth and XY are doing the same thing,
but using different models of function transparency.

-Wm

[Chris Double]

On Mon, Mar 9, 2009 at 5:58 AM, William Tanksley <wtanksleyjr@...> wrote:
> Actually, a queue is a bad choice for the future structure. XY uses it
> because it wanted an easy to do 'dip', but 'dip' doesn't require a
> persistent structure. When used only to view and modify the future, XY
> treats its queue as a stack -- which is the correct approach.

XY doesn't need access to the end of the queue for dip either. It
could implement it using patterns:

; pdip { [a f] f / a } ;
1 2 4 [ + ] pdip
=> 3 4

Once you have dip is there any need for a retain stack or the ability
to modify the end of the queue?

> I think Forth's system is terrible, since it
> negates the benefits of easy factoring; but XY's system makes it hard to
> look as far into the future as Forth's system can. But what about
> partial continuations -- neither language provides those, although both
> come close.

XY provides partial continuations in the library. Since XY allows
complete control of the queue any sort of control structure becomes
possible. F is similar in that it provides an operator $. It expects a
quotation on the stack with stack effect ( stack queue -- stack queue
). It calls it with the current stack and queue, and replaces the
existing stack and queue with the result. The other queue/stack
manipulations are built on that. Too much flexibility?

Chris.

[stevan apter]

----- Original Message -----
From: "Chris Double" <chris.double@...>
To: <concatenative@...>
Sent: Sunday, March 08, 2009 6:23 PM
Subject: Re: [stack] unary functions from X to Y?

> On Mon, Mar 9, 2009 at 5:58 AM, William Tanksley <wtanksleyjr@...> wrote:
>> Actually, a queue is a bad choice for the future structure. XY uses it
>> because it wanted an easy to do 'dip', but 'dip' doesn't require a
>> persistent structure. When used only to view and modify the future, XY
>> treats its queue as a stack -- which is the correct approach.
>
> XY doesn't need access to the end of the queue for dip either. It
> could implement it using patterns:
>
> ; pdip { [a f] f / a } ;
> 1 2 4 [ + ] pdip
> => 3 4
>
> Once you have dip is there any need for a retain stack or the ability
> to modify the end of the queue?

well, you need patterns for dip, and i eventually decided that i preferred
the tradeoffs embodied in XY 0 - eliminate patterns, enhance shuffle notation,
and add the ( and ) primitives.  the little example i give in the doc is:

        10 20 30 {x ([x])} 40 50
    10 20 [10 20] [30] [40 50] 40 50

{x ([x])} is a shuffle, not a pattern, and ( quotes the stack and ) quotes the
queue.

in XY 0 (www.nsl.com/k/xy/xy0.xy) i define dip as:

; swap          {ab ba} ;
; slip          => / <= ;
; dip           swap slip ;

so i guess the question is, can one define dip in XY 0 without => or <=?  i
don't know the answer to this.

but as i said, i wasn't thinking specifically of dip, but more generally, of
what it means to "cache" something in a framework where the computation can
access "all of time".  my thought was that placing something at the farthest
point in the future (i.e. at the end of the queue) comes closest to the naive
idea of a cache.  

>
>> I think Forth's system is terrible, since it
>> negates the benefits of easy factoring; but XY's system makes it hard to
>> look as far into the future as Forth's system can. But what about
>> partial continuations -- neither language provides those, although both
>> come close.
>
> XY provides partial continuations in the library. Since XY allows
> complete control of the queue any sort of control structure becomes
> possible. F is similar in that it provides an operator $. It expects a
> quotation on the stack with stack effect ( stack queue -- stack queue
> ). It calls it with the current stack and queue, and replaces the
> existing stack and queue with the result. The other queue/stack
> manipulations are built on that. Too much flexibility?
>
> Chris.
>

[stevan apter]

----- Original Message -----
From: "William Tanksley" <wtanksleyjr@...>
It would be
> perfectly possible to add a function to Forth to append a new return
> address to the bottom of the stack; it would be a total function change
> to make XY treat functions as opaque.

in XY, a quotation is made opaque by enclosing it with `.  this turns a
quotation into a function atom.  i added enclose/disclose because (if you
recall) i wanted to be able to build and manipulate trees of programs.
but if trees and programs are both quotations, it isn't possible to
know purely on the basis of type when descent has reached a program.
this may seem too farfetched to bother about, but i do it quite often.

>
> I think the basic lesson is that Forth and XY are doing the same thing,
> but using different models of function transparency.
>
> -Wm
>
>
>

[stevan apter]

in XY, X is the stack and Y is the queue, but X and Y will contain
references to the environment (name-value bindings) which can be
altered with ; ... ; definitions.  i think i started work on what
i was calling XYZ, in which functions were maps from X, Y, and an
environment Z, a map from symbols to values.  my plan was to get
rid of ; definitions, and use <~ and ~> to move items between the stack
and the environment.  i still think this is a good idea, at least
for reasons of theoretical purity.  either that or eliminate run-
time changes to the environment, so that the meaning of a name is
eternal.

----- Original Message -----
From: "William Tanksley" <wtanksleyjr@...>
To: <concatenative@...>
Sent: Sunday, March 08, 2009 11:58 AM
Subject: Re: [stack] unary functions from X to Y?

> John Nowak wrote:
>> In my email prior to this one, I suggested that the definition of  
>> concatenative languages should be limited such that all functions are  
>> unary functions from some aggregate X to some aggregate Y where X and  
>> Y are both the same "type" (e.g. a stack or a stack/queue tuple). This  
>> definition covers all existing concatenative languages. More  
>> importantly however, it rules out languages like FP where functions  
>> can do things like take a list and return a number.
>> My first question then is if anyone agrees that this is a useful  
>> restriction.
>
> I agree.
>
>> Should we agree it's useful, the next thing I'd want to try is to  
>> determine an aggregate type that would be valid for all existing  
>> concatenative languages. To start, all existing concatenative  
>> languages include a stack. Some include more than a stack however, so  
>> our aggregate type must be a tuple of a stack and something else.
>
> I think all of them use more than a stack.
>
>> XY offers a queue representing the future of a computation, but really  
>> all concatenative languages can be viewed in terms of having such a  
>> queue; some languages simply don't make it programmer-accessible. I  
>> think it therefore reasonable to add a queue to our tuple.
>
> Actually, a queue is a bad choice for the future structure. XY uses it
> because it wanted an easy to do 'dip', but 'dip' doesn't require a
> persistent structure. When used only to view and modify the future, XY
> treats its queue as a stack -- which is the correct approach.
>
>> Factor offers a retain stack (the direct use of which is nearly  
>> eliminated at this point I think). We do not need to add this to our  
>> tuple however because we can simply view it as being passed around on  
>> the top of the stack. After all, the retain stack can only represent  
>> the "past" in terms of the current computation, so it makes sense to  
>> group it in with the "main" stack which holds the sum of past  
>> computation.
>
> Yes, the retain stack is part of the past (quite apart from it being
> obsolete!) -- although I wouldn't want to model it as being "on" the
> main stack.
>
>> Forth offers a return stack. It may be possible to formulate this as  
>> part of the queue, but it's not clear to me exactly how this would  
>> work. I wonder if it may be cleaner to add the return stack to our  
>> tuple. In this scenario, the "main" stack is the past of the  
>> computation, the queue is the future, and the return stack is the  
>> "present" of the computation. The utility of separating the "present"  
>> from the "future" is that Forth can manipulate the present using r>  
>> and >r. It cannot, as far as I know, manipulate the "future" in any way.
>
> I don't understand what you're saying at all. The XY queue is
> essentially a high-resolution return stack. Forth's return stack plus
> its instruction pointer is similar to the queue -- it tells you what's
> going to happen in the future.
>
> I could understand you classifying the IP as being the 'present', in
> which case XY's queue melds the present with the future -- but I don't
> see much use in that, since really everything in the XY queue and
> everything after the Forth IP is in the future.
>
> XY lets you manipulate the future at a finer grain than Forth does.
>
>> could then classify concatenative languages by which elements of that  
>> tuple are made user-accessible: Joy would make only the past  
>> accessible, Forth would make the past and present accessible, and XY  
>> would make the past and future accessible.
>
> The first question I think is appropriate would be not which parts are
> open to programmer manipulation, but rather what the effects of
> manipulations are. Appending stuff to XY's queue behaves very
> differently from pushing stuff onto it.
>
>> This is just a very rough idea. Any thoughts would be much  
>> appreciated. Specifically, I am unsure if separating the "present" and  
>> the "future" is a valid approach. I do not, however, have a way of  
>> removing the need for the "present" in the case of Forth at the  
>> moment; viewing the return stack as part of the queue seems  
>> inappropriate. More precisely, it would mean that only part of the  
>> queue would be user-accessible. Having to deal with "parts" would make  
>> the classification system less useful. Perhaps Forth's return stack  
>> access is a unique property we can avoid dealing with and could  
>> therefore reclassify Forth as a "mostly concatenative" language or  
>> somehow "pre-concatenative". Then again, perhaps not, and we'd have to  
>> find a way of dealing with it.
>
> Forth is hardly the only language to use an IP and a return stack -- it
> seems odd to make a classification of languages that share the common
> feature of being extremely resource-hungry to implement. It's probably
> not a good idea to make the lynchpin of a classification system an
> experimental feature of a single language.
>
> With that said, though, I also disagree that having to deal with "parts"
> is a problem. This is ALL experimental; we don't know the right way of
> looking at the problem. I think Forth's system is terrible, since it
> negates the benefits of easy factoring; but XY's system makes it hard to
> look as far into the future as Forth's system can. But what about
> partial continuations -- neither language provides those, although both
> come close.
>
>> - John
>
> -Wm
>
>
>