# unary functions from X to Y?

## John Nowak — 2009-03-06 00:44:23

    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

## Justin Pombrio — 2009-03-06 06:30:00

    --- In concatenative@yahoogroups.com, 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 — 2009-03-06 07:02:36

    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 — 2009-03-06 07:15:42

    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 — 2009-03-06 07:27:34

    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 — 2009-03-06 07:57:44

    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 — 2009-03-06 08:15:01

    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 — 2009-03-06 09:14:24

    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 — 2009-03-06 09:47:59

    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

## Justin Pombrio — 2009-03-06 16:47:24

    --- In concatenative@yahoogroups.com, 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 — 2009-03-07 07:27:29

    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.

## William Tanksley — 2009-03-08 16:58:11

    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 — 2009-03-08 19:00:29

    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 — 2009-03-08 23:23:58

    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 — 2009-03-09 15:48:31

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

    From: "Chris Double" <chris.double@...>

    To: <concatenative@yahoogroups.com>

    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 — 2009-03-09 19:53:29

    ----- 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 — 2009-03-09 21:16:24

    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@yahoogroups.com>

    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

    >

    >

    >