# ASM Rules in Joy [was Re: [stack] conk - concatened k]

## Louis Madon — 2000-06-15 00:50:01

    wtanksley@... wrote:

     >

    > From: Louis Madon [mailto:madonl@...]

    > >wtanksley@... wrote:

    >

    > >> ASMs accurately model execution in the presence of in-place

    > updates,

    > >> so I

    > >> look forward to your language.

    >

    > >> Interestingly, ASM rules fire in parallel while concatenative words

    > >> execute in serial.  How do you plan to resolve the distinction?

    >

    > >Not quite true. ASM rules fire when their guard conditions are

    > >met. This

    > >is just a way to do sequencing without having to introduce a

    > >full-fledged language. In Jel, the guards are unneccesary

    > >since Joy code does the sequencing.

    >

    > Ah, true.  That's what was confusing me.

    >

    > >The only thing that is missing is a way to execute

    > >a bunch of updates in parallel; One possibility is that a special

    > >combinator is provided (like i) except that it takes a quotation

    > >containing only updates and executes them "simultaneously".  Note

    > that,

    > >so far, I've been concentrating on the type system and so haven't

    > >thought these issues through fully.

    >

    > An interesting point is that niladic functions (fns with no stack

    > effect)

    > can be executed in any order.  Because of this, you can model

    > parallelism by

    > using functions which are niladic with respect to the system stack --

    > for

    > example, functions which act on some other stack.

     Yes, this is a good insight. In effect, create a pair (inputs,update) to

    create a niladic update (I hesitate to use the word "function" here,

    since an operation without outputs can't really be called such). In

    Joy, as you illustrated in your example, such a pair can be represented

    by a quotation and we can then execute these in any order (I guess in

    mathematical terms, we could say that niladic updates are commutative).

    This in turn implies that the "parallel" combinator could be defined as:

    parallel == [i] step

    This almost seems like a complete solution, but I can see at least one

    outstanding issue: inputs that have dependencies on prior updates within

    the same rule (see more below).

     >

    > In Forth, this would be cone using some kind of BEGIN word, which set

    > up a

    > state; a task-loader word, which placed the tasks ready to go; and an

    > END

    > word, which executed the tasks in parallel and unloaded the state when

    > they

    > were done.  Thus, only the ordering of the BEGIN and END would be

    > relevant

    > to the Forthlike language.

    >

    > BEGIN Task: 1 oneUpdate Task: 0 anotherUpdate END

    >

    > In Joy, I believe we'd want to use quotations, as you've said: since

    > the

    > language supplies some syntax, we might as well use it.

    >

    > [ [1 oneUpdate] [0 anotherUpdate] ] Parallel

     An important requirement that must be satisified is that the effect of

    the updates must not become visible until the entire rule has executed.

    In your example above, this requirement holds, since the inputs to each

    update are just constants.  However, consider the case where the input

    involves a dependancy on a dynamic function:

    [ [ 1 one:= ] [ one another:= ] ] Parallel

    In other words, the input value for the 'another:=' update is specified

    as the value of the 'one' dynamic function. But that DF was just

    updated, so the second update will "see" the wrong value. I think fixing

    this requires:

    - niladic update construction rule - All occurences of DFs in the inputs

    to any update must first be dereferenced (that is replaced by their

    value).

    Ideally, the compiler could check that this rule isn't violated.

    So the example above would become:

    one [ another:= ] cons [ [ 1 one:= ] ] cons Parallel

    This would now work correctly.

    Or perhaps, (yes this is better - I don't know why I didn't think of it

    in the first place), implement parallel as:

    parallel == [opt] map [i] step

    'opt' is a partial evaluation combinator (same semantics as 'id' except

    that the result is in a maximally evaluated form).  This eliminates any

    special restrictions on the programmer and yet guarantees that there are

    no DF interdependancies between updates.

    It will be interesting to see just what its like reasoning with Joy

    programs containing these extended features, I'm quite optimistic that

    the ASM approach will work well.

    --

    Louis.

## wtanksley@bigfoot.com — 2000-06-20 21:43:09

    From: Louis Madon [mailto:madonl@...]

     >wtanksley@... wrote:

    >> From: Louis Madon [mailto:madonl@...]

    >> >wtanksley@... wrote:

    >> An interesting point is that niladic functions (fns with no stack

    >> effect)

    >> can be executed in any order.  Because of this, you can model

    >> parallelism by

    >> using functions which are niladic with respect to the system stack --

    >> for example, functions which act on some other stack.

    >Yes, this is a good insight. In effect, create a pair

    >(inputs,update) to

    >create a niladic update (I hesitate to use the word "function" here,

    >since an operation without outputs can't really be called such).

     I don't quite remember, but it seems that the ASM literature does in fact

    refer to niladic functions.  Thus you would be quite justified in calling

    them such.

     >In

    >Joy, as you illustrated in your example, such a pair can be represented

    >by a quotation and we can then execute these in any order (I guess in

    >mathematical terms, we could say that niladic updates are commutative).

    >This in turn implies that the "parallel" combinator could be

    >defined as:

    >parallel == [i] step

    >This almost seems like a complete solution, but I can see at least one

    >outstanding issue: inputs that have dependencies on prior

    >updates within the same rule (see more below).

     Exactly.  In other words, your definition is incorrect -- you really do have

    to do it right.

    I would suggest for efficiency's sake that you start (at compile time) by

    doing a topological sort, and generating code for any independant updates

    normally.  Then make copies of dependant updates and generate code to update

    and copy.

    But you don't have to be this fancy; it's sufficient to copy, update, and

    copy back, without first checking for independant updates.

     >An important requirement that must be satisified is that the effect of

    >the updates must not become visible until the entire rule has

    >executed.

    >In your example above, this requirement holds, since the inputs to each

    >update are just constants.  However, consider the case where the input

    >involves a dependancy on a dynamic function:

     You're assuming that I hadn't already thought of that.  :-)

     >Or perhaps, (yes this is better - I don't know why I didn't think of it

    >in the first place), implement parallel as:

    >parallel == [opt] map [i] step

    >'opt' is a partial evaluation combinator (same semantics as 'id' except

    >that the result is in a maximally evaluated form).  This eliminates any

    >special restrictions on the programmer and yet guarantees that

    >there are no DF interdependancies between updates.

     Yes, that would be interesting as well.  It makes sense to not be able to

    specify unordered updates.

     >It will be interesting to see just what its like reasoning with Joy

    >programs containing these extended features, I'm quite optimistic that

    >the ASM approach will work well.

     Same here.

     >Louis.

     -Billy

## Louis Madon — 2000-06-21 00:31:33

    wtanksley@... wrote:

     >

    > From: Louis Madon [mailto:madonl@...]

    > >Yes, this is a good insight. In effect, create a pair

    > >(inputs,update) to

    > >create a niladic update (I hesitate to use the word "function" here,

    > >since an operation without outputs can't really be called such).

    >

    > I don't quite remember, but it seems that the ASM literature does in

    > fact

    > refer to niladic functions.  Thus you would be quite justified in

    > calling

    > them such.

     I'm pretty sure that what they mean by niladic function is different

    though; its a function without inputs but at least one output (eg. a

    variable access is modelled as a niladic function). For example, in

    Haskell I could write:

    	x = 2

    which defines a niladic function 'x' that when invoked returns '2'. I

    have no problem with considering x a function.  However, if a function

    has neither inputs nor outputs, thats when I think its strange to call

    it such. This is just terminology ofcourse, but I'd prefer to use the

    terms 'update' and 'niladic update' to emphasise the fact that they are

    pure state change commands.

     >

    > >In

    > >Joy, as you illustrated in your example, such a pair can be

    > represented

    > >by a quotation and we can then execute these in any order (I guess in

    > >mathematical terms, we could say that niladic updates are

    > commutative).

    > >This in turn implies that the "parallel" combinator could be

    > >defined as:

    >

    > >parallel == [i] step

    >

    > >This almost seems like a complete solution, but I can see at least

    > one

    > >outstanding issue: inputs that have dependencies on prior

    > >updates within the same rule (see more below).

    >

    > Exactly.  In other words, your definition is incorrect -- you really

    > do have

    > to do it right.

     Yes. My last message was more brainstorming than well thought out

    principles.

     >

    > I would suggest for efficiency's sake that you start (at compile time)

    > by

    > doing a topological sort, and generating code for any independant

    > updates

    > normally.  Then make copies of dependant updates and generate code to

    > update

    > and copy.

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

     >

    > But you don't have to be this fancy; it's sufficient to copy, update,

    > and

    > copy back, without first checking for independant updates.

     I'm not sure what you mean by "copy back". The way I'm interpreting this

    solution is:

    parallel == [copy] map [i] step

    where copy is defined as

    copy == unswonsr [i] dip swonsr

    (here unswonsr is the same as unswons except it returns the

    (initial,last) instead of (rest,first) and likewise swonsr adds an

    element to the right of a list instead of the left).

    Is that kind of what you had in mind? (I think its a reasonable

    approach).

     >

    > >An important requirement that must be satisified is that the effect

    > of

    > >the updates must not become visible until the entire rule has

    > >executed.

    > >In your example above, this requirement holds, since the inputs to

    > each

    > >update are just constants.  However, consider the case where the

    > input

    > >involves a dependancy on a dynamic function:

    >

    > You're assuming that I hadn't already thought of that.  :-)

     Sorry, I didn't mean to imply that (although it obviously reads that

    way).

     >

    > >Or perhaps, (yes this is better - I don't know why I didn't think of

    > it

    > >in the first place), implement parallel as:

    >

    > >parallel == [opt] map [i] step

    >

    > >'opt' is a partial evaluation combinator (same semantics as 'id'

    > except

    > >that the result is in a maximally evaluated form).  This eliminates

    > any

    > >special restrictions on the programmer and yet guarantees that

    > >there are no DF interdependancies between updates.

    >

    > Yes, that would be interesting as well.

     Actually, there's a bug in it.  opt will try to invoke the update if all

    its inputs are available. The copy solution above seems ok though.  Like

    I said, I was just brainstorming ...

     > It makes sense to not be able to

    > specify unordered updates.

     I agree. There is still the issue of niladic updates being well formed;

    ie. they must be niladic and the update must be the very last item in

    the quotation. The type system will need to take care of checking this.

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

    --

    Louis.

## wtanksley@bigfoot.com — 2000-06-21 16:25:22

    From: Louis Madon [mailto:madonl@...]

     >wtanksley@... wrote:

    >> From: Louis Madon [mailto:madonl@...]

    >I'm pretty sure that what they mean by niladic function is different

    >though; its a function without inputs but at least one output (eg. a

    >variable access is modelled as a niladic function). For example, in

    >Haskell I could write:

     Whoops!  You're right.  'Update' is a better term.

    Note that updating is a very nice term to have -- input and output are also

    'updates', although not niladic.

     >> I would suggest for efficiency's sake that you start (at

    >> compile time)

    >> by

    >> doing a topological sort, and generating code for any independant

    >> updates

    >> normally.  Then make copies of dependant updates and generate code to

    >> update

    >> and copy.

    >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.  If you want

    to play around with runtime, it's very easy to do compilation tasks at

    runtime.  This is one very confusing thing about Forth which I'm now

    completely used to.  :-)

     >> But you don't have to be this fancy; it's sufficient to copy, update,

    >> and copy back, without first checking for independant updates.

    >I'm not sure what you mean by "copy back". The way I'm

    >interpreting this solution is:

     I'm sorry, I don't know of any other way to express it, aside from the

    statement "It's the only way to solve the problem you're looking at."

     >Is that kind of what you had in mind? (I think its a reasonable

    >approach).

     I honestly couldn't read your code.  Must be all the sugar today.  Sorry.

    However, to the best of my knowledge there's only one possible way to handle

    concurrent updates: make copies and work from the copies.

     >Actually, there's a bug in it.  opt will try to invoke the

    >update if all

    >its inputs are available. The copy solution above seems ok

    >though.  Like I said, I was just brainstorming ...

     Hmm.  Perhaps opt needs to recognise updates as such -- when you

    destructively modify something you can't do that at compile-time (unless

    you're instructed to).

     >> It makes sense to not be able to

    >> specify unordered updates.

    >I agree. There is still the issue of niladic updates being well formed;

    >ie. they must be niladic and the update must be the very last item in

    >the quotation. The type system will need to take care of checking this.

     It's not hard to make it niladic: simply have it operate on its own stack.

    I don't see the need for making the update be the last item, either.

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

     >Louis.

     -Billy

## Louis Madon — 2000-06-22 06:42:04

    > From: Louis Madon [mailto:madonl@...]

    > >wtanksley@... wrote:

    > >> I would suggest for efficiency's sake that you start (at

    > >> compile time)

    > >> by

    > >> doing a topological sort, and generating code for any independant

    > >> updates

    > >> normally.  Then make copies of dependant updates and generate code to

    > >> update

    > >> and copy.

    >

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

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

    This touches on what I see as a key issue with the efficiency of Joy

    programs: namely how do you handle quotations?

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

    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 issue is not related to Joy being a concatenative language but

    stems from its pervasive programs-as-data model (even lisp doesn't go as

    far; macros must be fully expandable at compile-time and 'eval' is not

    defined as a language primitive).

    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.

     > However, to the best of my knowledge there's only one possible way to handle

    > concurrent updates: make copies and work from the copies.

     Right. Its just a matter of deciding on the most efficient way to do

    that. I think all the solutions presented so far are just expressing

    this basic strategy in different forms.

     >

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

    I'd like to expand a bit on the issue of "not asking permission" though.

    My system will have well defined semantics and so it wont do anything

    mysteriously (if it does, thats a bug).  These semantics are more

    abstract than what a low level system offers thus giving the compiler

    more implementational freedom. It follows that the programmer has less

    control over very low level details (though in principle you could still

    inspect the low level stuff with a browse tool of some sort).  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).

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

    can delegate to the compiler without sacrificing efficiency.

    --

    Louis.