Re: [stack] Is this language concatenative?

On 1/5/07 2:41 PM, "John Carter" <[email protected]> wrote:

> [..]
> * Chris says, "The semantics of a concatenative language are that
>  each term is a state function (e.g. from a set of stacks to a set
>  of stacks), and the concatenation of two terms implies the
>  composition of those functions."
> 
> I'm not convinced the word "stack" needs to appear in the
>  definition at all.
> 
> Any fragment of a concatenative language is a function mapping a
>  set X onto itself. In Joy X is the set of stacks. I'm not convinced
>  that is the only valid domain for concatenative languages.

Entirely agree. Stacks seem to be particularly good for implementing
unary, binary, n-ary operators of fixed arity. I did fool around once with
a queue machine instead, but did not pursue it further. Also, as John
Cowan first pointed out explicitly, in the presence of ³get² and ³put²
IO, Joy really uses a stack and a file system. As the Lisps have shown,
sequences containing sequences containing sequences ... are a truly
remarkable data structure. This is true irrespective of whether sequences
are implemented as linked lists (of one kind or another), or as arrays
in consecutive memory locations. The difference in the implementation
implies a difference in the efficiency of various operations. The Lisps
and Joy use simply linked lists, Stevan Apter¹s X and XY languages use
arrays borrowed from K (Stevan?). Anyhow, the Joy stack is of course
just a sequence.

> I would also hypothesize a family of languages where "string
>  concatenation represents XXX" where XXX is some other useful
>  mathematical operation apart from functional composition.
> 
I have tried this, but got nowhere. Do you have anything more explicit?
> 
> [..]
> So one could compile..
>  * a long list of all basic and interesting  mathematical operations
>  * and there algebraic properties
>  and then
>  * another list of primitive datatypes and
>  * basic operations on those datatypes and
>  the algebraic properties
>  and overlay the two wherever the algebras match and create a new language.
> 
And importantly, ³overlay² means ³homomorphism² - the semantic meaning
function maps a syntactic algebra onto a semantic algebra. In very
non-technical language, a conjunction ³p and q² is true in the intersection
of the set of worlds in which p is true with the set of worlds in which q is
true. This maps ³and² onto ³intersection². This is possible because the
sentential operators and the set operators form Boolean algebras. In Joy
the meaning function maps the syntactic operation of concatenation onto
the semantic operation of function composition. This possible because
syntax and semantics form algebras called monoids.

I did once toy around with the far more general notion of function
composition
which is used in recursive function theory: Given a bunch of m functions
f1 f2 ...fm which all take n parameters, and one other function g which
takes
m parameters, define another function h of n parameters: Take the n
parameters
of h and feed them (concurrently, in any order) to the various f1 f2..fm.
This gives m intermediate results. Feed these into g to get the final value.
Useful? for theoretical purposes, yes, tremendously. For practical
programming,
probably not. The familiar composition of unary functions is just m=n=1.
(This general composition is definable in Joy, of course. But I have never
seen any use for it.)
> 
> [..]
> Is "string concatenation" or "functional composition" or the
>  representation by one of the other the fundamental thing about
>  concatenative languages? Or is the broader concept "isomorphisms
>  between algebras of higher mathematical constructs and algebras of
>  primitive computer datatypes lead to
>  (deceptive?|interesting?|useful?) simplifications"
> 
I think you mean ³homomorphism². Certainly all meaning functions that I know
of seem to map (abstract) syntax homomorphically onto semantics.
> 
> Question 1b :
> 
> Can you propose an interesting "non-von thunnian" language (like a
>  non-euclidean space) where we either....

Blush. von Neumann ...
> 
> [..]
> Are stacks the only meaningful domain and range for the functions we
>  are composing?

The plain old ³store² (indexed by addresses) is another possibility.

  - Manfred
> 



[Non-text portions of this message have been removed]