# Re: [stack] Comments - 8

## stevan apter — 2000-08-02 12:41:29

    ----- Original Message -----

    From: <phimvt@...>

    To: <CONCATENATIVE@...>

    Sent: Wednesday, August 02, 2000 3:56 AM

    Subject: [stack] Comments - 8

    > 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?

    i don't think so.  k is a procedural language, with side-effects

    and global variables.  it lacks pattern-matching a la haskell,

    it isn't object-oriented, and evaluation is strict.  the interpreter

    does no optimization.

    of course, it is always possible to write k using just a subset

    of its capabilities, restricting oneself to side-effect free

    programs.  ken iverson promoted this approach to APL back in

    the 70s, with his 'direct definition' interpreter.

    by the way, here's a cute programming problem which surfaced

    a few days ago.

    given two lists old and new, where new is the result of taking

    one element of old and moving it to a new position in the list,

    find the index in new of the moved element.  for example,

        old == [10 20 30 40 50]

        new == [10 30 40 20 50]

        old new find-index-of-moved-element

     3

    in the case where the element has been moved just one position

    to the left or right, there is an ambiguity, so let left-moves

    dominate right-moves:

        [10 20 30 40 50][10 30 20 40 50] find-index-of-moved-element

     1

## Louis Madon — 2000-08-04 12:51:07

    >

    >  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).

     It isn't function redefinition exactly but redefinition at a specific

    point in a functions domain. Ofcourse, in the case of niladic functions

    this looks the same as assignment. However, dynamic function usage is

    derived via one or more ASM specifications (at different levels of

    abstraction) and this is what makes them fundamentally different than ad

    hoc assignment.  In other words, its not just dynamic functions

    themselves but the methodology and proof-style that goes with them.

    I'm still however in the process of learning ASM theory and figuring out

    how it can be usefully integrated into a Joy-like language. I'm pursuing

    that because:

    1 - purely functional languages do not seem to be good for implementing

    highly interactive applications (eg. GUIs).

    2 - Some algorithms can only be implemented efficiently if you have

    in-place update. For example, depth first search on general graphs.

    3 - I'd like to avoid making lists a priveledged data structure.

    Languages that do that  tend to encourage the use of list-based

    solutions even though other data structures are available and might be

    more suitable/efficient.

    There are numerous ways a purely functional language could address

    points 1 and 2.  For example, Haskell has monads and Clean has

    uniqueness types. I'm most familiar with Haskells monadic style in this

    regard. However I find that monads tend to obscure the code with extra

    "syntactic noise" and so reduce readability. Moreover, if you decide it

    would be beneficial to add some stateful computation to a purely

    functional component without changing its interface (eg. you have a

    binary tree and would like to add some caching to speed up the common

    cases) you can't do it. You're forced to change the interface anyway and

    this can have a serious ripple through effect in the client code.

    Ofcourse, I can't absolutely claim that the ASM approach is better, but

    it does look promising to me.  I recommend taking a look at Martin

    Oderskys' paper on the ASM website http://www.eecs.umich.edu/gasm/

    (select "compiler correctness" under "applications" on the left hand

    side menu and then select "variable functions").

     >     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.

     I'll try to come up with some good arguments when I understand ASM

    theory better myself.

     > 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.

     Ok, I volunteer :-)

    A super-optimising Joy-like is my personal goal. Its being written in

    Haskell, though in the long term I'd like to rewrite it in its own

    language.

    Speaking of Prolog, I've never really had an indepth look at the logic

    languages, they do seem interesting. Some day ...

     >     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.

     I think that rewrite rules alone will not be sufficient. The tricky bit

    is detecting and propagating partial information effectively.  For

    example, consider this case:

    foo == [0 <] [bar] [] ifte

    bar == [5 >] [100] [200] ifte

    Lets say we know nothing about foo's input initially.  However, inside

    the true clause of ifte we do know that the input must have been less

    than zero.  Therefore, we could evaluate bar to 200.

    I believe the most effective way to do PE is to first do a whole-program

    analysis (say via abstract interpretation). The additional information

    gathered then makes it possible to ferret out the static parts of the

    program much more aggressively.

    A good book on this topic is by Neil Jones, et. al "Partial Evaluation

    and Automatic

      Program Generation"  See

    http://www.dina.dk/~sestoft/pebook/pebook.html

     >     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.

     All lists in Haskell must be homogeneous, but you can define sum types

     (eg. Mixed = Integer | Char | String).

    Also a common extension of Haskell is existential types. These are

    ordinary polymorphic types (ie. they take type parameters, as in Array

    Int and Array Char). However, they can hide part or all of their

    parameterisation so that different instantiations can be used as if

    they're a single type.  For example,

      data Any = forall a. Any a

    defines a type that can act as a container for any type. Now I can

    create a mixed list like this:

      [Any 1, Any 'c', Any "hello", Any [4, 5, 6]]

    unlike a sum type I don't have to declare all the possible branches up

    front.

    Regarding writing a Joy interpreter in Haskell, I did that a few months

    ago. It was very easy to do since most of the basics (function

    composition, garbage collection, lists, higher order functions) are

    already there.

     > 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 ?)

     Thats my understanding. If you just want to sequence unary functions you

    could use the identity monad (its just function composition). For more

    complex functions, you would define some kind of state monad to carry

    the values between consecutive functions (eg. a stack). The fundamental

    mechanism these kinds of monads rely on is as you say availability of

    parameters.

    Note that, some monads in Haskell are implemented outside the language,

    eg the IO monad. Obviously they could be relying on a different

    mechanism to 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

     Yes, although I like Joy because there is a completely unambiguous

    sequence that evaluation is imagined to follow.

    --

    Louis.

## Massimo Dentico — 2000-08-04 14:39:35

    phimvt@... wrote:

     > [...]

    > 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.

    > [...]

     mmm .. this seems more term rewriting (or equational programming)

    than partial evaluation (PE). Give a look at this:

    "Q - Equational Programming Language"

    - http://www.musikwissenschaft.uni-mainz.de/~ag/q/

    --

    Massimo Dentico