# RE: ASM Rules in Joy

## wtanksley@bigfoot.com — 2000-06-22 23:38:52

    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.

    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.

    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 prefer the second choice.

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

    Benchamrks on Forth code demonstrate that compilation works -- at least in

    Forth, where your compiler is very simple.

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

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

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

     >> >[BTW, what stage are you at for the type system in your

    >> >implementation?

    >> >Is it still wide open or have you already settled on an overall

    >> >approach?]

    >> It's open, but I'm tending to lean towards Dr. Becher's

    >> system: my first

    >> system is intended to be very Forthlike, in the sense of

    >> simplicity and

    >> transparency.  Your system sounds very powerful, but it does

    >> things for the

    >> programmer without always asking permission; it also sounds

    >> like GC is going

    >> to be essential to it, and my system won't have that (except

    >> _perhaps_ as a user-callable routine).

    >Sounds good. Our implementations will be exploring two quite different

    >points in the design space of Joy-like systems. In that sense they're

    >quite complementary.

     Yes, that was my impression.

     >I'd like to expand a bit on the issue of "not asking

    >permission" though.

     My apologies.  I was using a bit strong language.

     >It really

    >just boils down to delegation of responsibility: giving up some control

    >in order that you can concentrate on bigger things (and let

    >the compiler do a good job on the little things for you).

     Right.  Whereas it's more important to me to make the compiler very small

    and light so that it can be written with fewer bugs -- and theoretically, it

    might be easier to write good programs in, since the programmer can treat

    the runtime itself as part of the conceptual map of his program, not as a

    too-complex area which has to be ignored.

     >Indeed, my number-one goal (I guess its a holy grail ...) is that you

    >can delegate to the compiler without sacrificing efficiency.

     Good goal.

     >Louis.

     -Billy

## Reuben Thomas — 2000-06-23 12:08:21

    > Doing (or being able to do) compilation tasks at runtime is blazingly

    > fast.

     Really?

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

     In the vast majority of languages, and assuming no long loops, I'd rather

    interpret throwaway code.

     > Benchamrks on Forth code demonstrate that compilation works -- at least in

    > Forth, where your compiler is very simple.

     Forth is a most extreme case. Most compilers have loads of extra overheads

    in lexing, parsing, type-checking, building an AST (perhaps) and then code

    generation.

    --

    http://sc3d.org/rrt/ | plagiarism, n.  the mind burgles

## Louis Madon — 2000-06-23 13:05:48

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

## wtanksley@bigfoot.com — 2000-06-23 17:30:13

    From: Reuben Thomas [mailto:rrt@...]

     >> Doing (or being able to do) compilation tasks at runtime is blazingly

    >> fast.

    >Really?

     In my experience.  :-)

    That is, it's better than having to interpret everything.

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

    >In the vast majority of languages, and assuming no long loops,

    >I'd rather interpret throwaway code.

     And assuming no deep nesting, and assuming that it was throwaway code.

    That's a lot of assumptions.  And perhaps the worst one is that we're using

    "the vast majority of languages" -- we're not; we're using a concatenative

    language, and as such we have a huge advantage in simplicity of parsing.

     >> Benchamrks on Forth code demonstrate that compilation works

    >> -- at least in Forth, where your compiler is very simple.

    >Forth is a most extreme case. Most compilers have loads of

    >extra overheads

    >in lexing, parsing, type-checking, building an AST (perhaps)

    >and then code generation.

     We've seen a typechecking system which seems to fit very simply into Forth.

    (We'll have to see how simple it really is.)  None of the other things you

    list are important to a concatenative language, unless you're trying to be

    compatible with an external standard (for example, if you're trying to emit

    SlimBinaries, you'll need to generate an AST); even there, you've got as

    easier job than you would have with a tree-structured language.

    -Billy