comments - 6

phimvt@lurac.latrobe.edu.au — 2000-07-27 09:28:00

NOTE: I am calling this "Comments - 6" because my posting

"Comments - 4" from 20-JULY should have been called "Comments - 5".

I have apologised already.



Some time ago I read a book in which the author moaned in

the preface "it was like a practical demonstration of Zeno's paradox".

That's what I feel like trying to catch up with the "concatenative"

mail.



"Digest 28"

    This was slow reading because much of the material was very thought

provoking to me.



1.    "Type checking written in its own language". In some languages

(Lisp, Joy, ..?) there are type predicates that can be used to ensure

that appropriate actions are taken depending on the type of the actual

parameters of a function. If the wrong type is given, a suitable error

message can be given. If no such checking is written by the programmer,

then the canned error message from the interpreter will be given. If

the interpreter doesn't do its checking, the operating system will

(typically) come up with a cryptic error message. Of these three possi-

bilities only the first is of interest here. At best it gives dynamic,

run-time checking - even if the checking could have been done at compile

time.

    If the implementation is by a compiler, then that compiler can be

written in its own language. For example, at least the early Pascal

compilers were all written in their own language, and they already did

all the required type checking. However, it would be possible to write

the first few generations of bootstrapping compilers in such a way that

a) they are written in a type-correct way, but b) do not do any type

checking. Then one of them adds type checking, and that is retained

henceforth. This now is static, compile time checking.

    The drift of the discussion seemed to be a desire for a methodology

that straddles the two extremes in the two paragraphs above. It would

be for a way of writing, in the language, a collection of type checking

routines and then using them from then on in the same program. That

of course should be without going through a bootstrapping of a new

compiler. 

    I suspect it cannot be done in the weakly typed languages such

as Lisp, Scheme (and probably Erlang). I know it cannot be done in Joy.

I do not know enough about Forth to say whether it might be done there.

In an "extended Joy" a type checked definition of list reversal might

look like this:

    DEF  reverse  ==

             |:|top of stack is a list|:|

             here usual definition.

The idea is that the test inside |:| is to be applied at compile time

whenever reverse is called:

    DEF  foo  ==  [1 2 3]  reverse   (is OK)

    DEF  bar  ==   1 2 3   reverse   (type error detected at compile time)

The error is detected by using the |:| test at compile time.

There is no way in which this sort of thing can be implemented in

Joy as she is now. Now doubt one could extend Joy in some appropriate way.

    Question to the Forth wizards: can you do it? How in detail?

Is this what IMMED (or something) is used for? Clarification

would be most useful.



2.  There was also some good discussion about GC (for a high level

part of a language), how to implement it (in a low level part of the

same(?) language), and how to break the GC (by using the low level part

maliciously). 

    I don't think there is a way out of that. You can certainly write

a GC in, say, Pascal or C or any other procedural language (you do need

mutable arrays - assignment etc). You then need the _discipline_ to

stick to exactly the memory management functions that you have implemented.

One bad move ruins the lot. I've done mark-sweep GC once in a Pascal

program, and stop-copy GC in a C program. (Both happen to be Joy interpreters.)

Its an experience rather different from the sort of programming

I had done before.

    As far as I can see there is _no way_ that one could implement

any kind of GC in a purely functional language. So if GC is to be

written in the language itself, then there needs to be assignment.

    Do we now have a low level language, without GC but with assignment,

and also a high level language with GC (maybe purely declarative,

but maybe with assignment)? Or do we have just one language with two

individually useful sublanguages? I don't know how to jump here.

But unless there is a way to prevent the high level language from

using the low level part to ruin the GC, the GC will not be safe

from malice or mistakes. It should be quite easy to have two brackets

      BEGIN-GC-SAFE

      ...

      END-GC-SAFE

such that anything in the ... part is checked by the compiler,

and the programmer can treat is as being written in the high level

portion of the language.



3.  There was a short discussion on what to do after e.g

            [dup 3 +]  first

which leaves  dup  on top of the stack. What can one do with it?

You cannot execute it with _any_ of the Joy combinators, of course,

but you can do this:

          [] cons   ...   i

this first turns the  dup  into  [dup]  which is a quotation that can

be executed any time by, say,  i.  If that sort of thing is needed

often, one might define "interpret just one":

        i1  ==  [] cons i

But I have not seen much use for it, except for the Joy-in-Joy

interpreter.



4.  There seems to be some demand for being able to manipulate

lists ins very general way. In Joy there is the  infra  combinator:

    [..somelist..]   [..someprog..]   infra

will temporarily take ..somelist.. to become the stack, execute

..someprog.. to yield a different stack, and finally push  that

as a list onto the previous stack:

    10  11  12  [13 14]  [dup dup]  infra    ==

    10  11  12  [13 13 13 14]

This happens at run time, of course. In the discussion there

seemed to be a demand for doing this at compilee time, so that

the declaration

    mylist  ==  !! [13 14]  [dup dup]  infra !!

would be the same as

    mylist  ==  [13 13 14]

because the !! part was executed at compile time (when storing

the definition).

    It would be possible to add such a feature, essentially making

Joy its own macro expansion language. The early IBM language PL1

did that sort of thing. But I remain to be convinced about the

usefulness of such a facility. I prefer not to add more and more

features and make Joy bloated for the sake of making it bigger.

But it might be persuaded that such compile time macros are a good idea.

Try me.



    Manfred