# Comments - 8

## phimvt@lurac.latrobe.edu.au — 2000-08-02 07:56:53

    How poerful is this purely

    functional subset? Do you _think_ in terms of substitutions

    and algebraic manipulations?

       On a different note: Louis, since you mentioned experience

    with Haskell.

    More comments

    1. "Dynamic functions (and intensional typing)"

         Louis presented proposals for allowing re-definitions of functions,

    which - to some extent at least - has the effect (good and bad) of

    assignment. There are two possibilities:

        a) allow redefinitions to occur anywhere inside a Joy expression

    being evaluated. In a fantasy syntax, with redefinitions in parentheses:

    report ==

        ... (year==2000) ...year...year... (year=2001) ..year...year..

    Here the first two uses of year will give 2000, the last two give 2001,

    of course. This is straight assignment, my understanding is that this

    is possible in Forth (check?). It also makes the language referentially

    opaque (= not purely functional).

        b) allow redefinitions to occur only at the top level (in Joy

    currently signaled by LIBRA, in Lisp also at the top level by (define..).

    Generally this sort of thing is a bad idea, because the function or

    whatever does not have the same meaning throughout the program.

    In fully block structured languages (Pascal, but not C) there is

    the hiding of previous definitions inside a new block when a

    re-definition occurs, followed at the end of the block by re-emergence

    of the old definitions. But even this creates some problems.

    On the other hand the technique is used in large C programs

    for the pre-processor with the #define and #undef directives

    to manipulate macros. I may be convinced that it is a good idea,

    but not so far. I'll listen to the arguments.

    2. "Partial evaluation"

        A nice discussion. I had often thought that somebody ought to

    write an optimiser for Joy - well, maybe in Prolog. Better still,

    make it part of the Joy system - so, write it in C. And why not

    write a partial evaluator at the same time - produce specialised

    functions where possible.

        But then a radical thought occurred to me. Maybe it has been

    discussed in the literature already, I would be glad for some pointers.

    Instead of writing interpreters, one should only write partial evaluators.

    An interpreter handles just the special case where all the arguments

    are known, and that surely is just a special case of partial evaluation.

    In the case of a functional language this just means: simplify

    the given expression in accordance with the reduction rules as

    far as possible - with some luck it is possible all the way down

    to a single value.

       Trivial? Obvious? Silly? Comments welcome.

    3. "conk - concatenated k"

        It seems that Stevan had already done (for k) what I was

    discussing in my "comments - 7 (sect 1)" of 2-AUG, yesterday,

    a translator from a concatenative language (conk) to an existing

    implementation (k) that is semantically identical. (I hope this

    description is correct).

        Can one identify a purely functional subset of k and of conk

    which satisfies the substitutional rule

        if  X == Y then  ...X... == ...Y...

    where the dots represent any extensional context (this blocks

    substitutions into quotations) ? When you think in k or conk,

    do you think algebraically?

        On a different note: Louis, you mentioned experience with Haskell.

    Am I right in believing that the type structure of Haskell requires

    all elements of a list to be of the same type? Is there a universal

    "anything" type? If not does that make it difficult to implement

    Joy in Haskell?  Some comments would be most welcome.

        Still from the same thread: thanks for pointing out the

    error concerning "while" in the "atomic programs" paper. I shall

    fix that shortly. I shall also add to the library the definition

    of fold which somehow got lost some time ago - this was pointed out

    already.

            fold  ==  [swap] dip step

                  ==  swapd step

    And while I'm at it, I have added to the Joy page a reference

    to the concat egroup.

    4. "ASM rules in Joy"

        I was reading about concurrency for some time, but stopped

    years ago when the field became so large that it really becomes

    a full time occupation to stay abreast.

        The idea of executing Joy concurrently had occurred to me,

    but I knew from the outset that I just lack the skills to implement

    it that way.

        From the discussion it ws clear to me that you see as the ideal

    the case where parallel execution is commutative. My first attempt at

    formulating this was  the following:

        [ [p1] [p2] ]  parallel   ==   [ [p2] [p1] ]  parallel

    But that is the wrong requirement. Suppose the results of the

    parallel computations are to be given as a list which has the

    same structure as the list of programs that produce the results.

    The the requirement is

        [ [p1] [p2] ]  parallel  ==  [ [r1] [r2] ]  if and only if

        [ [p2] [p1] ]  parallel  ==  [ [r2] [r1] ]

    Now (as pointed out in the discussion already), map already

    come close to that, because each item of the mapped list

    is pushed onto the same original stack. Even if the mapping

    functions consumes several arguments from the stack, including

    an item from the mapped list, the earlier stack is always

    restored for the next item to be mapped. So one way is to

    write

        ...some stack items...  [ [p1] [p2] ]  [i]  map

    where those stack items will be available to both p1 and p2.

    This was easy to do because the Joy stack in my implementation

    is a linked list, and by saving and restoring a pointer

    to it the original stack can be presented to p2.

    So - it is only necessary to implement a parallel map that

    does the mappinng in parallel. have neither the hardware nor

    the expertise to write that. As far as _simulated_ parallelism

    is concerned, I even suspect that doing the mapping serially

    and without concurrenncy is more efficient (if that is a consideration).

    But let us not forget that in a functional language _nothing_

    is required about the order of execution - except for the

    availability of actual parameters for the functions. (Louis -

    check me on this: this is how monads in Haskell implement

    sequencing ?) At any rate, in any functional language an

    expression can be evaluated in several orders:

      2 3 + 1 2 + *                       2 3 + 1 2 + *

          5 1 2 + *                       2 3 +     3 *

          5     3 *                           5     3 *

                  15                                  15

    Bye for now - Manfred