> wtanksley@... wrote:
>
> From: Louis Madon [mailto:madonl@...]
> >> >This could work but the topo-sort would need to be a part of the
> >> >definition of parallel since the inputs may not be knowable until
> >> >runtime (as a result of Joys' metaprogramming support). Partial
> >> >evaluation can still be used to move the overhead to the earliest
> >> >possible stage (which may well be compile-time in most cases).
>
> >> Honestly, I'd rather require them to be known at compile-time.
>
> >Ok, its always easier to compile a language by only supporting some
> >(less dynamic) subset of it. I'm interested in preserving the full
> >dynamism of Joy though.
>
> I'm not clear on how it's possible to have something that's not known at
> compile-time inside an update -- the update's stack is supposed to be empty.
Simply, if it isn't known at compile time - do it at runtime - rather
than restricting the language (you still do it at compile time when
possible).
> Oh, I suppose you could be calling a dynamic function which returns another
> dynamic function which in turn is one of the things being updated. That
> makes sense.
Um no! In ASM theory, dynamic functions are meant to be first order.
This means that under no circumstances can a function appear in the
signature of any DF. (This restriction does not apply to normal
functions which can be higher order).
I forgot to mention that.
>
> Whew. I don't see any way out of this: you're either going to have to copy
> EVERYTHING that's being updated (and it's quite possible that everything in
> the system will be updated, so this means you have to copy everything); or
> you're going to have to disallow simultaneous updates (or otherwise restrict
> them).
I think the key will be to 'dereference' the input values (ie. eliminate
all occurences of DFs from the input value expressions). The result will
then be independant of the global state [DFs can never appear in a DF
signature so it follows that a dereferenced expression will be DF free].
Therefore copying can be done like in any functional language: by
reference.
> >> If you want
> >> to play around with runtime, it's very easy to do
> >> compilation tasks at runtime.
>
> >"doing compilation tasks at runtime" is also called "interpreting" :-)
> >And you're right, it is easy, but its also inefficient.
>
> That's not the definition I'm familiar with. Interpretation is the process
> of parsing and then executing the parse tree. Doing (or being able to do)
> compilation tasks at runtime is blazingly fast. For example, given a
> quotation which you've built at runtime, would you rather interpret it
> directly, or would you rather compile it and then run the compiled result?
Your phrase "interpret it directly" acknowledges the fact that
interpretation can be more general than in your definition. I'm using
the term in the sense that your doing _all_ the work at runtime.
Splitting that work into two stages might be an improvement but doesn't
solve the problem. (I elaborate on this a bit further down).
> Benchamrks on Forth code demonstrate that compilation works -- at least in
> Forth, where your compiler is very simple.
I haven't used Forth but I have the impression that Forth programmers
don't use meta-programming pervasively: do you know for example any
Forth programs that are more than 10 meta-levels deep? how many use even
3 meta-levels? In Joy it is one of the fundamental features of the
language (concatenation is the other). Forth and Joy are quite different
in this regard. In Joy, programs can easily involve deep meta-level
hierarchies - thus creating a unique challenge to efficient compilation.
I don't think Forth benchmarks will tell us much about this.
>
> >This touches on what I see as a key issue with the efficiency of Joy
> >programs: namely how do you handle quotations?
>
> My language, being built for utter simplicity, won't have them in its native
> syntax (although it'll be easy to define a word to help you build them, so
> maybe I'll do that). They'll be constructed as arrays rather than lists,
> and no automatic memory management will be done.
I think I understand. You're essentially doing the same thing that
Scheme, Lisp, Python and some other languages do by providing an 'eval'
type function. This means meta programming is no longer a primitive
facility and that has the effect of discouraging its use.
Here's an example to help clarify: in Joy you could write a function to
scale a vector, possibly as:
scale == [*] cons map
scale has signature: Vector n -- Vector.
Here a vector is just an aggregate of numbers each of which will be
multiplied by n to create the result.
Now in your language, scale must be implemented differently since
execution of constructed quotations won't be native to the language. One
possibility is to use your 'eval' function:
scale == [*] cons eval map
Here, eval takes the constructed quotation and returns a reference to a
compilation of it. However, even if the compiler is "blazingly fast", I
_dont_ want to compile code every time I need to scale a vector! (this
is what I mean by 'eval' discouraging metaprogramming - its too
heavyweight).
The next possibility is to refactor the code so that the calls to eval
are minimised (ideally happen only once). For example, if I wanted to
scale one million vectors by 3.9 then I could do the eval just before
entering the loop. I can then just reuse the same bit of eval'd code
each time round. The problem now is that the implementation of scale has
effectively become distributed (loss of modularity).
Imagine having 1000 small functions like scale used in over 5000 call
sites. You need to figure out _where_ to do the evals (so their overhead
is minimised) and you need to figure out _how_ to supply each call site
with the correct bit of eval'd code. Thats a lot of stack juggling, very
poor modularity and a general maintenance nightmare. It just isn't
practical to use eval that widely. So once again, metaprogramming is
being discouraged.
In your language, the only practical solution I can see is to introduce
new primitives so that functions like 'scale' can be coded efficiently
without meta-programming.
Now, I'm _not_ saying that discouraging meta-programming is a bad thing.
But it is a very different style of programming than in Joy - its moving
back to more conventional styles. From my point of view, Joy offers a
brave new world that I'm keen to explore.
>
> >I see them more as a way of expressing semantics to the compiler rather
> >than being fully explicit at runtime (similar to the way that the stack
> >can be seen as a logical entity that does not have to be fully realised
> >in the executable code).
>
> I'm not sure what you mean.
Hopping back to the vector scaling example:
scale == [*] cons map
If this is translated literally, a new quotation is built, compiled and
then executed several times for each call to scale. But we don't need to
compile _literally_ - just preserve the semantics. For example, the
target code for scale might be (shown as a snippet of pseudo-assembler):
move r1, TopOfStack
move r2, NextOnStack ( pointer to vector )
move r3, [r2++] ( size of vector )
move r4, ... ( address of result buffer )
l1: multiply [r4++] <= r1, [r2++]
loop r3, l1
Although the original function was expressed in terms of a constructed
quotation, the target code has no trace of it. Essentially thats all
that I was trying to say (and I see PE as the key to making this
optimisation possible).
> >Its a key issue because, in Joy, its not only possible but
> >quite natural
> >to have programs constructing programs constructing programs ... to an
> >arbitrary number of levels (eg. when using program construction in lieu
> >of closures). If you do the construction at runtime, the
> >total overhead
> >will be the _product_ (not the sum) of the overheads for each level.
> >For example, say a constructed program effectively runs at half the
> >speed of a pre-generated equivalent. If there are 5 levels of
> >construction, then the overall program will run 2^5 or 32 times slower
> >(this is a very simplistic and rather unrealistic calculation ofcourse,
> >but I'm just trying to emphasise the multiplicative nature of the total
> >overhead).
>
> This makes complete sense, and is why I would insist on including the
> compiler as part of the runtime system.
There seems to be a major misunderstanding here ...
Doing the compilation at runtime will not help you, thats my point.
Using the 'eval' approach does not eliminate (but in fact introduces)
inefficiency into Joys' metaprogramming style. Your approach is fine if
you want to deemphasise that style, but as I said that makes the
language quite different than Joy.
>
> >I want to eliminate the in-efficiency incurred in a straight-forward
> >interpretative implementation without restricting the
> >language. To that
> >end I see partial evaluation playing a very critical role. Conversely,
> >it seems that having an efficient implementation of Joy without PE is
> >only possible if you restrict or at least encourage less use
> >of its meta capabilities.
>
> Actually, it's also sufficient to ignore compiler enforcement of
> correctness. I can see that this is not acceptable in your system, but it
> is in mine -- I would not have a simultaneous update construct, since doing
> so implicitly makes a claim which I am not willing to enforce. Instead, I
> would expect the user to execute sequential updates, if necessary making
> copies of needed structures before updating. The result would have the same
> capabilities, but require just a bit more work from the user -- but that's
> not terrible.
Yes, I agree with this. Rules do not have to be part of the initial
implementation (my system included) but I will strive to add them at
some point. Keep in mind though that the efficiency issue being
discussed is not specifically with updates but for quotations in
general.
--
Louis.