Re: [stack] language hierarchy

On 16/1/08 6:03 PM, "Manfred Von Thun" <[email protected]> wrote:

[.. stuff about use before definition..]

> The same trick of using forward declarations could also be used if one
> really wants to have definitions to have first the body and then the name
> (presumably no explicit parameters in a concatenative language). Then a
> simply recursive definition would look like this:
> 
> [] def foo (* the forward declaration with dummy body*)
> 
> [.. foo.. foo..] def foo (* the full definition with recursive calls *)

I must have had a senior moment (that is what some of my retired colleagues
call the phenomenon) when I wrote this. To some extent I was thinking of a
compiled
implementation with compile time type checking, but even that does not work
out.

In an interpreted implementation where all the type checking is done
at run time, the following is possible: when a symbol is first encountered,
enter it into the symbol table. Whenever a body of a definition is given,
enter that body in the table for the symbol. Some symbols might never get
a definition because they are not intended to be executed. This happens
for example in lists: [peter paul mary]. But it could also happen
accidentally
when an attempt is made to execute the body of an undefined symbol.
At any rate it is possible to use a symbol (say: bar) in the body of a
definition of another symbol (say: foo). This is how it looks in Joy

DEFINE foo == 42 bar.

At this point bar is not yet defined, so it cannot be executed. Hence foo
cannot be executed although it is defined.

DEFINE bar == 2 *.

Now both foo and bar are defined and can be executed.

If there is self-recursion.as in the following, then there is not problem:

DEFINE baz == ... baz ... .

The first baz enters the symbol into the table, the second finds its
position in the table, and the final period attaches the body to the
position in the table.

Finally, mutual recursion:

DEFINE zot == ... zot ... wow ... .
DEFINE wow == ... wow ... zot ... .

In the definition of zot, the wow is entered and will be found subsequently,
as on the two occasions in the second definition. So this is just like
the earlier case of foo and bar. In the definition of wow, the zot of
course finds its position in the table, and the wow finds a different one,
just as for self-recursion.

All the above definitions could be written in the reverse style, with body
first and head second. Just the last two:

[... zot ... wow ...] def zot
[... wow ... zot ...] def wow

So the idea of entering a symbol into the table as soon as the symbol
is first encountered makes it possible to have self-recursion and even
mutual recursion without any forward or prototype declarations.

HOWEVER: This is fine if type checking is done at run time, but what
about type checking at compile time? In Pascal the forward declarations
and in  C the prototypes give the user not just the names of the
procedures or functions, but also the types of the parameters and the
the type of the result. In a stack language there will only be one
parameter, a stack, and the result will also be a stack. Both stacks
will have to be typed, and a notation is needed for that. My proposal
would be to borrow some ideas from Prolog. For example, the notation

[  N:num X | R ]

would describe a stack of at least two elements, topmost a number N,
second something of any type,followed by a possibly empty
rest-of-stack R. Similarly the notation

[ M:num N:num | R ]

would desribe a stack of at least two elements, two numbers, not
necessarily distinct. Then the definition

DEFINE f == swap pop dup 10 *

defines f to take as input stack one as described by the first description
above, an yield as output one as described by the second description.
Thus the type of f is given by

f  :  [ N:num X | R] -> [M:num N:num | R]

Note that N and R occur on both sides of the arrow, and this indicates
that the input and result stacks are the same in both positions.

A complete definition of f should then combine the typing and the code:

DEFINE f : [N:num X| R] -> [M:num N:num | R] == swap pop dup 10 *

Similar typing could be given for all definitions, and forward/prototypes
would merely give the typing.

Incidentally, the example also illustrates something else: that pattern
matching can describe arbitrarily complex stack shuffling by swap,
pop, dup and friends (and also list shuffling by cons, first, rest and
friends.
But the implications of that are outside this note.

  - Manfred  
> 
> 



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