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