[stack] Re: unary functions from X to Y?

--- In [email protected], 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