I've put together this description of the two main innovations in my
version of Joy:
Dynamic functions and Intensional typing. I'd be interested to hear any
comments people might have. BTW, I'm calling the derivative JEL (the
"Joyously Efficient Language" - the name reflects my goal that this be
usable as a systems level language but without sacrificing clean
semantics).

A disclaimer: the syntax of the examples below are very tentative. Right
now I create data structures manually, bypassing any scanning/parsing
and even some analysis. This gives me the flexibility to try out
variations on ideas/algorithms without having to update a front end all
the time. I'll finalize the syntax only after I've got all the
fundamentals worked out. Again, any suggestions regarding syntax (or
anything else) are most welcome.

Dynamic functions
-----------------

A dynamic function is just like a normal function except that it can be
_updated_ at specific inputs. The simplest way to declare such a
function is to name it and specify type constraints for its inputs and
outputs:

(top) foo.dynamic (top)

This declares a dynamic function 'foo' that takes one input and returns
one output. I'll describe how type constraints work shortly but for now
just read '(top)' as 'one value of any type'. Note that in this example
foo has not been given a body; the upshot of this is that it is
initially everywhere undefined. So if we do this:

4 foo

=> error: `foo` not defined at 4

We could have defined foo with a body and this would have the effect of
giving the function an _initial_ value for each input. For example,

(top) foo.dynamic (top) == 2 *

Now if we do:

4 foo

=> 8

For each function declared as dynamic the system implicitly provides an
associated update; it has the same name as the function but with ':='
appended. Moreover, it requires both inputs and outputs to be on the
stack (in that order) when it is invoked; it returns nothing. For
example,

4 21 foo:=

=>

Subsequent invocations of foo will reflect the update:

4 foo

=> 21

That is essentially all there is to declaring and using dynamic
functions [there are some issues regarding fine-tuning the compiler
generated implementions of these functions - I'll come back to this
point after I've introduced the type system].

With this addition, the language offers most of the efficiency benefits
of assignment and pointers but without making formal reasoning
difficult. The ASM literature explores this aspect in detail but
basically the program can be viewed as a state machine; an update
represents a state transition and processing within states is purely
functional.

[In a proper ASM you're supposed to be able to schedule a set of updates
in parallel (this is called a rule). This simplifies proofs since the
program can be modelled with fewer states; for example, when the program
adds a node to a linked list, you might update 4 dynamic functions (say
head, tail, next, prev) atomically. However I haven't worked out how to
implement rules yet ...].

Here's an example: a singly-linked list type:

EXPORT

first rest cons uncons

FROM

(list) first.dynamic (top)

(list) rest.dynamic (list)

cons ==
new -- create a fresh list to hold the new value
swap dupd first:= -- make the value being consed the head of the
new list (leaves list)
dupd swap rest:= -- make the prior list the tail of the new
list and return the new list

uncons ==
dup first swap rest

END

Remarks

The 'new' function used within the body of cons has signature 'new
(top)' - ie. no inputs, returns a single value of some unspecified type.
It is intended to be the standard way of creating new instances of any
type. The subsequent call to first:= places a constraint on the type of
value returned by new; since first:= expects a list at that point on the
stack this allows the compiler to specialise the signature of new to
'new (list)'. There may be other constraints stemming from the context
in which cons is used that further refines the types. Ultimately, the
compiler selects the most-specific implementation available that
satisifes the constraints. In this case though, we can just fall back on
the default implementation (ie. new (top)) since there is no _content_
in the object - its used purely as a key for driving the dynamic
functions.

As a side-note, [] is syntactic sugar for calling new. [a b c] is
syntactic sugar for 'new \c cons \b cons \a cons' (backslash is
quotation for individual items). This means that the [] notation can be
used for any aggregate type that at least supports cons.

[Well without explaining the type system what I've just said is probably
a bit hard to follow]

Intensional Typing
------------------

To be continued ... (I've run out of time so I've decided to continue
this
message tomorrow).

--
Louis.

Dynamic functions and Intensional Typing

Louis Madon — 2000-06-09 07:28:19

Louis Madon — 2000-06-10 06:10:41