# Dynamic functions and Intensional Typing

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

    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.

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

    Louis Madon wrote:

     > To be continued ... (I've run out of time so I've decided to continue

    > this

    > message tomorrow).

     Actually, I've decided that I should document the language extensions in

    my version of Joy properly (I need to do that anyway as part of the

    project and now seems a pretty good time). This will let people get a

    much better understanding than I could hope to convey in a couple of

    messages to the list.  So that will need a bit more time ... (hopefully

    not too long).

     >

    > --

    > Louis.