Re: [stack] Is this language concatenative?

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

> Conversely another family exists where "functional composition is
>  represented by SOME TRIVIAL OPERATION ON FAMILIAR PRIMITIVE
>  DATATYPE". eg. List append, tree join...
> 
> Of course the whole thing can be generalized in both directions to
>  create families of languages where "BASIC MATHEMATICAL OPERATIONS
>  are represented by TRIVIAL OPERATIONS on FAMILIAR PRIMITIVE
>  DATATYPES".

Your wide-ranging posting was so suggestive that I have another reply to
make. This was in part prompted by a discussion, mainly between Chris, Billy
and Michael about regular expressions. My methodology for the day: start
with regular expressions, define some sort of a language, what do you get?

Most programmers probably know regular expressions from various
unix utilities in which regular expressions serve to describe searches
and matches. The impression one might get is that they are particularly
concerned with strings of characters. But this is not so. Here is my expo:

A string or word or list or vector or n-tuple or sequence consists on zero
or more discrete entities, with repetitions allowed. For example a line of
boy and girl ducklings following their mother is a sequence of boy/girl
bits. (Here: fantasy about a biological computer using 2^32 lines of 32
ducklings..) More commonly the entities are characters, numbers, words of a
language. I shall use < and > to enclose sequences,  to avoid any suggestion
that we are dealing with sequences of linguistic things. Inside the < and >
I write the names or other referring expressions which denote the items, so
that <London Paris Rome> is a sequence of cities and not a sequence of
names. Sequences can be concatenated, and I shall use an infix underscore
for that. So, <a b> _ <c d e>  = <a b c d e >. There is also the empty
sequence <> which is the left and right unit element of concatenation.

A language is a set of sequences (and the word ³language² is particularly
misleading here, but everybody uses it). Since languages are sets, one can
form their union. Use an infix vertical bar | for union. Thus if L and M are
languages, the L|M is their union. Since the members of languages are
sequences and hence concatenable, one can define an operation of
concatenation for languages, again using infix underscore _. Thus if L and M
are languages, then L_M is the set of all those sequences that can be formed
by taking a member from L and one from M and concatenating them in that
order. There are two very special languages. One is {}, the empty language
that hhas no members at all. The other is {<>}, the language whose sole
member is the empty sequence. {} is the unit element for language union, and
the (left and right) zero element for language concatenation. {<>} is the
(left and right) unit element for language concatenation.

A language can be concatenated with itself any number of times. Write the
number as an exponent: so L^2 = L_L, L^3 = L_L_L. Call these the powers of
the language. Normal exponent arithmetic applies: (L^m)_(L^n) = L^(m+n). L^1
= L, L^0 = {<>}. (Q: negative exponents? fractional exponents?). Three
postfix operators: L+ = the union of all positive (1,2..) powers, L* = the
union of all (0,1,2..) powers, L? = the union of {<>} with L.

The two binary infix operators _ and | and the three unary postfix operators
can be used to build arbitrarily complex expressions, using ordinary
parentheses
( and ) to disambiguate for the infix operators. But the operators need some
basic operands, which have to be languages ­ simple languages from which
all else is to be constructed.

In regular expressions a basic operand is a language that is a set of
just one sequence which in turn contains just one basic element. So, using
this overly explicit notation, we should write

({<a>} | {<b>})  _ ({<c>} | {<d>})

But for good reasons the concatenation operator is generally not written at
all, and the operand languages are also given a useful abbreviation which
looks obvious but is in fact quite involved:

(a | b) (c | d)

The two notations denote the same language: {<ac> <bc> <ad> <bd> },
or if the letters are actually characters, the language {³ac² ³ad² ³bc²
³bd²}.

The three postfix operators do not need any special treatment.

A language which is the extension of a regular expression is called a
regular language. Definitions of regular expressions can be allowed, and if
they do not use recursion then they do not extend the class of regular
languages.

What we have here is that concatenation of regular expressions denote
concatenations of  sets of sequences, of languages. But that is not all that
interesting. However, the sequences themselves could be endowed with
meaning, which could be commands as in a procedural language, or they could
be unary functions as in a concatenative language. And what are we to make
of the union operator | that does not occur explicitly or implicitly in
procedural or concatenative languages?

The answer must be that we should not assume that a program is a sequence as
described above, but that it is a set of sequences. To use a really awful
and confusing pun: program must be a language as described above. And the
programming language must be a set of languages.

That is not as silly as it sounds. In procedural and in concatenative
languages the atomic programs (factors in my terminology) denote changes to
complex entities, a von Neumann store or a stack. Changes are just unary
functions from such thing to another. Unary functions are many-one relations
­ binary relations which can hold between several things and one other, what
we call the value of the function. Concatenations of programs map onto
composition of many-one relations. What else can we do with relations? Given
any two relations of the same arity we can form their disjunction, or
technically their union. So given two binary many-one relations we can form
their disjunction, which will generally be a many-many binary relation.

What then might a programming language look like if its basic programs
denote not
unary functions from stacks to stacks but (many-many) binary relations
between
stack? Or instead of stacks some other entity? It is really quite obvious:
the program

(2 | 3) *

denotes the relation that holds between a stack whose top element is an
integer, and another stack whose top element is instead twice or thrice that
integer. An implementation would first put 2 on top of the stack and then
continue, and when told to backtrack would put 3 on top of the stack and
then continue. There may be various ways in which the backtracking could be
controlled. Prolog does this sort of thing very well. It should be easy to
see what

(2 | 3) (+ | *)

does ­ it gives four results. Even the three unary postfix operators from
regular expressions find a place here, and note the potential ambiguity of
the star *  symbol:

1 (2 * )*

produces all the powers (0,1,2,3..) of 2, which are 1,2,4 8,16...
Of course, many choices have to be made between in the implementation,
and one of these concerns backtracking: depth first is easy to do but
can be tricky for the user.

What does all this amount to: First there is the syntax, the expressions
which denote languages. In turn the languages denote binary relations.
A double homomorphism, I very tentatively propose.

A programming language in which binary alternation or union (and the three
unary operators) are available can be grafted onto a concatenative language
by using various exotic combinators. I have done some experiments with
my Joy-in-Prolog. But this is only an awkward grafting.

A programming language in which concatenation and alternation are really on
a par would be very different from what I am used to. I have to say this
even though I am quite comfortable now with Prolog, in which the two
operations are indeed on a par. However Prolog of course uses (so-called
logical) variables that serve as parameters, which are precisely what the
stack languages aim to eliminate. So, I would find it easy to implement a
relational stack language in Prolog, but I cannot yet see any uses. Possibly
this is just lack of familiarity.

Any ideas?

  - Manfred







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