# Re: [stack] Re: Another implemenatation of Joy.

## Martin Young — 2000-08-09 11:49:24

    On Aug 8, 10:32pm, ghoul6@... wrote:

     > Subject: [stack] Re: Another implemenatation of Joy.

    >

    > Louis Madon <madonl@...> wrote:

    > > f [P] [Q] fork

    > >

    > > fork expects three values on the stack, a flag and two quotations. The

    > > flag can have one of three values:

    > >

    > > Left

    > > Right

    > > Both

    > >

    > > If Left, the left quotation P is executed.  If Right, the right

    > > quotation Q is executed.  If Both, then both P and Q are executed

    > > simultaenously.  In this case, execution resumes after the fork only

    > > when P and Q have both completed. Stack results will be presented as if

    > > P and then Q had been executed sequentially on the same input stack.

     This is *really* difficult.  You're saying that the stack after P and Q have

    executed concurrently must be identical to the stack as it would appear if P

    and Q had executed sequentially.  This is difficult because P and Q will

    actually execute entirely asynchronously but, logically at least, on the same

    data.

    If there are actually executing on the *same* stack then the resultant stack

    will depend on the temporal nature of their asynchronisity whilst if they

    execute on separate stacks the system is required to "merge" them which, again,

    requires knowledge of their exact temporal interactions.  Automatically

    producing a result which is a combination of several threads' work is really

    tricky.

    There's an algebra of concurrently called CSP, largely the work of C.A.R.

    Hoare.  It attempts to describe how concurrent processes can interact in a well

    specified manner.

     On Aug 8, 10:32pm, ghoul6@... wrote:

    > It seems to me the simplest mechanism of concurrency is futures.  Say you

    > could write:

    [snip convincing description of futures]

    I'm not sure this is the simplest.  Would it not be simply to have a word such

    as split (or fork) such that:

    P1 P2 fork -> L1 L2

    Which P1 and P2 are concurrently executed on separate copies of the stack.

     When they have both finished their final stacks are left (that's L1 and L2).

    Both of these mechanism would make it difficult to implement concurrent

    producer-consumer which is a mainstay of concurrent design.  Both futures and

    "fork" require a thread to finish executing thus leaving a result.

    You *could* extend futures so that the future will eventually be a list, and

    certain operations (most notably uncons) are allowed on a future list without

    forcing the whole list to be computed.  This is the rudiment of lazy

    evaluation, but explicitly expressed in the langauge.

    [snip description of lazy evaluation]

    Adding laziness to a Joy-like system would be interesting.  I'm concerned that

    it might be doomed from the outset because for laziness to be useful requires

    the language to be pure (i.e. no side effects, and no dependence on order of

    execution).  Having the whole stack passed from word to word makes the order of

    execution pretty rigid which limits how much laziness can be employed.  I

    think.

    --

    Martin Young  working for  STMicroelectronics at     `(o)_(o)' The fat wise /

    1000 Aztec West, Almondsbury, Bristol, BS32 4SQ.      (  V  ) owl eats only >

    +44 1454 462 523    `v'      Martin.Young@...      `.___,' clean mice.  /

                       _(_)_                             -="==="=============='

## Louis Madon — 2000-08-09 12:35:21

    Mark van Gulik wrote:

     > It seems to me the simplest mechanism of concurrency is futures.  Say you

    > could write:

    >

    >     [100 factorial] future [50 factorial] future +

    >

    > This mechanism would push two futures on the stack, and arrange for

    > processes to be created to start computing their results.  The futures turn

    > into their results when the computation completes (indirection objects work

    > well for this).

    >

    > An alternative variant of futures would make conversion from a future to its

    > value more explicit:

    >

    >     [100 factorial] future [50 factorial] future force swap force +

    >

    > Again, as soon as the future is constructed a process starts computing its

    > result.  The force operation waits for the computation to complete (if it

    > hasn't already) and then extracts the result.

     Yes, nice. I guess that an unforced future can act as a handle to the

    thread and this may open up the possibility of inter-thread

    communications (among other things).  On the other hand ...

     > Consider a function "race" that takes a list of futures and returns the

    > future that completed first (or maybe its result).  A general rendezvous

    > mechanism can probably be constructed from this.

    >

    > One can also imagine such operations as finished (to test for completion)

    > and lazy-future (the work process is only created when forced).

     It seems that all these functions {future, lazy-future, forced,

    finished, race} would have to be primitives. Moreover it is not clear

    even with this set how additional capabilites like access to shared

    resources could be provided without adding even more primitives.

    I wonder what the "minimal complete" basis for concurrency in Joy might

    be. By "complete" I mean that you could in principle specify any

    parallel algorithm.

     >

    > > Another approach I've heard of for reducing copying is to maintain a

    > > history of changes, ie. a list of deltas. The idea is that whenever a

    > > change is made that must not be visible to other references, you simple

    > > insert a delta (eg. (delete 2) -> [3] -> [2] -> [1] -> []) and then take

    > > those into account when accessing the structure.  I think it can be done

    > > quite efficiently for lists, but I can't remember where I read it.

    >

    > You may want to look at a really incredible book titled "Purely Functional

    > Data Structures" by Chris Okasaki (Cambridge, ISBN 0 521 63124 6).  He

    > presents an interesting collection of data structures.  At first the data

    > structures have amortized bounds on their operations.  He then refines this

    > for precise worst-case costs on the operations.

     Yes its a great book, though its been a while since I lasted looked at

    it.

     >

    > The main "trick" to narrowing worst-case bounds is to use lazy evaluation to

    > do things like gradually producing the reverse of a list or some other

    > rebalancing activity.  As "pseudo-destructive" changes are made to the main

    > data structure (e.g., cons), a small increment of work is performed, forcing

    > one or more suspended lazy computations to be converted to non-lazy objects.

    > This is vaguely similar to some schemes for incremental garbage collection.

    > Note that converting the lazy-evaluation nodes into "real" nodes isn't

    > really a side-effect, other than its influence on performance of later

    > operations.

     Indeed the breadth of possibilities for implementing data structures

    (even "basic" types like lists) is enourmous. I think this is more

    reason to _not_ have lists as primitives.  If a particular context can't

    benefit from a particular implementation strategy (like lazy

    computation) I'd prefer having the choice to specify a different

    strategy.

    --

    Louis.

## Louis Madon — 2000-08-09 13:16:21

    Martin Young wrote:

     >

    > On Aug 8, 10:32pm, ghoul6@... wrote:

    > > Subject: [stack] Re: Another implemenatation of Joy.

    > >

    > > Louis Madon <madonl@...> wrote:

    > > > f [P] [Q] fork

    > > >

    > > > fork expects three values on the stack, a flag and two quotations.

    > The

    > > > flag can have one of three values:

    > > >

    > > > Left

    > > > Right

    > > > Both

    > > >

    > > > If Left, the left quotation P is executed.  If Right, the right

    > > > quotation Q is executed.  If Both, then both P and Q are executed

    > > > simultaenously.  In this case, execution resumes after the fork

    > only

    > > > when P and Q have both completed. Stack results will be presented

    > as if

    > > > P and then Q had been executed sequentially on the same input

    > stack.

    >

    > This is *really* difficult.  You're saying that the stack after P and Q have

    > executed concurrently must be identical to the stack as it would

    > appear if P and Q had executed sequentially.  This is difficult because P and Q

    > will actually execute entirely asynchronously but, logically at least, on

    > the same data.

     I wasn't really thinking about ease of implementation (although

    efficient implementation is important to me). From a use perspective, it

    seems simple.

     >

    > If there are actually executing on the *same* stack then the resultant

    > stack will depend on the temporal nature of their asynchronisity whilst if

    > they execute on separate stacks the system is required to "merge" them

    > which, again, requires knowledge of their exact temporal interactions.

     The join point after the fork is an implicit synchronisation point, the

    idea being that (maybe!) we can do away with explicit synchronisation

    primitives. For example,

    [[P] [Q] fork] while

    Here, you could get a string of invocations of P and Q and each time

    around the loop the two processes could exchange data.  If this style of

    concurrency isn't too unintuitive or limited (a big if), it would not be

    neccesary to introduce inter-thread communication or synchronisation at

    all.

     > Automatically producing a result which is a combination of several threads' work is

    > really tricky.

     Can you elaborate? I don't see any problem at all. There are _exactly_

    two threads and their results are presented in order (P then Q). A

    simple implementation would be:

    P-num-inputs, P-num-outputs <- arity P    (analysis of P to determine

    arity)

    Q-num-inputs, Q-num-outputs <- arity Q    (ditto for Q)

    P-stack <- copy P-num-inputs from input stack

    Q-stack <- copy Q-num-inputs  "  "

    exec P on P-init-stack

    exec Q on Q-init-stack

    wait for _both_ P and Q to finish

    append P-num-outputs from final P-stack to input stack

    append Q-num-outputs "   "

    Perhaps you're thinking that this can't be done efficiently. However, I

    don't see that fork introduces any fundamentally new problems that don't

    already come up in writing an optimising compiler. In other words, if

    you do sufficient static analysis to do good optimisation you also have

    sufficient information to "merge" the threads efficiently (as well as

    avoid unnecesary copying from the input stack).

     >

    > There's an algebra of concurrently called CSP, largely the work of

    > C.A.R.

    > Hoare.  It attempts to describe how concurrent processes can interact

    > in a well

    > specified manner.

     Thanks, I'll have a look. If its algebraic it may fit in well with the

    rest of Joy.

     >

    > [snip description of lazy evaluation]

    >

    > Adding laziness to a Joy-like system would be interesting.  I'm concerned that

    > it might be doomed from the outset because for laziness to be useful requires

    > the language to be pure (i.e. no side effects, and no dependence on order of

    > execution).

     Joy currently is pure (well - 'get' and 'put' are exceptions)

     > Having the whole stack passed from word to word makes the order of

    > execution pretty rigid which limits how much laziness can be

    > employed.  I think.

     Its not rigid, a compiler can easily ignore the explicit order if it

    determines that no data dependencies will be violated.

    --

    Louis.

## Martin Young — 2000-08-09 13:54:18

    On Aug 9, 11:16pm, madonl@... wrote:

     > > Automatically producing a result which is a combination of several threads'

     work is

     > > really tricky.

    >

    > Can you elaborate? I don't see any problem at all. There are _exactly_

    > two threads and their results are presented in order (P then Q). A

    > simple implementation would be:

    >

    > P-num-inputs, P-num-outputs <- arity P    (analysis of P to determine

    > arity)

    > Q-num-inputs, Q-num-outputs <- arity Q    (ditto for Q)

    >

    > P-stack <- copy P-num-inputs from input stack

    > Q-stack <- copy Q-num-inputs  "  "

    >

    > exec P on P-init-stack

    > exec Q on Q-init-stack

    >

    > wait for _both_ P and Q to finish

    >

    > append P-num-outputs from final P-stack to input stack

    > append Q-num-outputs "   "

     Ah.  <the light dawns>  I read your original statement as saying that the

    program [ [P1] [P2] fork ] would be defined as yielding the same result as the

    program [ P1 P2 ], which is not the case.  I tried to write a sequential

    program which yields the same result but I couldn't see how.

    The "analysis if P to determine arity" is provably non-computable, btw.  It's a

    special case of the halting problem.  I can write a program which pops a number

    of values off the stack and then either finishes (i.e. halts), or loops around

    and pops some more.  How can you tell, statically, when (and if) it will halt

    and thus its arity?  You can't, and there's a proof of this.

    Here's a reference I've just dug up on the 'net.  I assume it's a correct

    description of the HP.

    http://faculty.juniata.edu/rhodes/intro/theory2.htm

    Of course this doesn't stop your scheme working - you just have to copy the

    whole stack.

    <thinks>  It makes detemining how to construct the eventual stack difficult

    because you need to define "num outputs" for each process.  Normally in Joy the

    result is the whole stack but in this case I understand you to mean some upper

    subset of the stack, but what subset?  We're back to a non-computable problem

    :-(

     > Perhaps you're thinking that this can't be done efficiently. However, I

    > don't see that fork introduces any fundamentally new problems that don't

    > already come up in writing an optimising compiler.

     I think the compiler gets a relatively easy ride because all the clever stuff

    is explicit (other than analysis for arity).  The programmer has a harder time

    because they have to decide which words can usefully be executed concurrently,

    and to collect the results.

     > Joy currently is pure (well - 'get' and 'put' are exceptions)

     Indeed.

     > > Having the whole stack passed from word to word makes the order of

    > > execution pretty rigid which limits how much laziness can be

    > > employed.  I think.

    >

    > Its not rigid, a compiler can easily ignore the explicit order if it

    > determines that no data dependencies will be violated.

     ...and that's the difficult bit.

    The stack is effectively a big piece of global data which is passed to every

    word.  Because almost every word alters the stack, there is dependence between

    most words.  The most obviously helpful word here is 'dip' but you need to know

    the arity of all the preceeding words to safely execute it out-of-order.

    I suspect that stack based languages are inherently strict, rather than lazy,

    but this is bare-faced assertion on my part and I'd be pleased to be shown to

    be incorrect.

    --

    Martin Young  working for  STMicroelectronics at     `(o)_(o)' The fat wise /

    1000 Aztec West, Almondsbury, Bristol, BS32 4SQ.      (  V  ) owl eats only >

    +44 1454 462 523    `v'      Martin.Young@...      `.___,' clean mice.  /

                       _(_)_                             -="==="=============='

## wtanksley@bigfoot.com — 2000-08-09 16:33:18

    From: Mark van Gulik [mailto:ghoul6@...]

     >Louis Madon <madonl@...> wrote:

    >> Speaking of concurrency, I'm interested in this too. One way

    >> it might be

    >> added to Joy is as a generalisation of ifte (I'll call it 'fork'):

    >> f [P] [Q] fork

    >> fork expects three values on the stack, a flag and two

    >> quotations. The flag can have one of three values:

    >> Left

    >> Right

    >> Both

    >> If Left, the left quotation P is executed.  If Right, the right

    >> quotation Q is executed.  If Both, then both P and Q are executed

    >> simultaenously.

     Why would you want that instead of a more typical fork:

     [process] fork

    ?

     >> This is just a start, practical concurrency would also need

    >> to provide a means of communication between threads.

     True and vital.

     >It seems to me the simplest mechanism of concurrency is

    >futures.

     Hmm...  It does provide semaphores and such in a transparent way.  I

    wouldn't call it the simplest _mechanism_, but it might be the mechanism

    which fits Joy best.

    -Billy

## wtanksley@bigfoot.com — 2000-08-09 16:47:14

    From: Martin Young [mailto:martin.young@...]

     >Adding laziness to a Joy-like system would be interesting.

    >I'm concerned that

    >it might be doomed from the outset because for laziness to be

    >useful requires

    >the language to be pure (i.e. no side effects, and no

    >dependence on order of

    >execution).  Having the whole stack passed from word to word

    >makes the order of

    >execution pretty rigid which limits how much laziness can be

    >employed.  I think.

     It certainly does limit the amount of laziness.  However, it does so in a

    very predictable way, and the compiler can analyse and remove the

    limitations.  Someone here -- my memory fails me -- is working on exactly

    this system.

    It's also possible to categorise side-effects; for example, the word 'put'

    causes a side effect, yet its side effect is precise and measurable.  A

    compiler which knew about all of the words which could cause side effects

    would be able to optimise them.

     >Martin Young  working for  STMicroelectronics at     `(o)_(o)'

     -Billy

## Louis Madon — 2000-08-09 21:40:37

    Martin Young wrote:

     >

    > On Aug 9, 11:16pm, madonl@... wrote:

    > > > Automatically producing a result which is a combination of several

    > threads'

    > work is

    > > > really tricky.

    > >

    > > Can you elaborate? I don't see any problem at all. There are

    > _exactly_

    > > two threads and their results are presented in order (P then Q). A

    > > simple implementation would be:

    > >

    > > P-num-inputs, P-num-outputs <- arity P    (analysis of P to

    > determine

    > > arity)

    > > Q-num-inputs, Q-num-outputs <- arity Q    (ditto for Q)

    > >

    > > P-stack <- copy P-num-inputs from input stack

    > > Q-stack <- copy Q-num-inputs  "  "

    > >

    > > exec P on P-init-stack

    > > exec Q on Q-init-stack

    > >

    > > wait for _both_ P and Q to finish

    > >

    > > append P-num-outputs from final P-stack to input stack

    > > append Q-num-outputs "   "

    >

    > Ah.  <the light dawns>  I read your original statement as saying that the

    > program [ [P1] [P2] fork ] would be defined as yielding the same result as the

    > program [ P1 P2 ], which is not the case.  I tried to write a sequential

    > program which yields the same result but I couldn't see how.

    >

    > The "analysis if P to determine arity" is provably non-computable, btw.

     That actually depends on how you define arity. I didn't want to

    complicate my original explanation too much, but all that the compiler

    really needs to know is the "shape" of the arity, not neccesarily the

    concrete number.  For example,

    	[pop] [[pop] times] ifte

    has "shape"  pop (pop | pop*)

    | means alternation

    * means zero or more

    * indicates the presence of a "region" - a part of the stack that can

    grow to an arbitrary size, but for the purpose of something like fork,

    you treat the whole region as a single "value".

    This is just control flow analysis and it is definetly computable.

     > It's a special case of the halting problem.  I can write a program which pops

    > a number of values off the stack and then either finishes (i.e. halts), or

    > loops around and pops some more.  How can you tell, statically, when (and if) it

    > will halt and thus its arity?  You can't, and there's a proof of this.

     Right I can't, but I don't need to go that far.

     >

    > Here's a reference I've just dug up on the 'net.  I assume it's a

    > correct description of the HP.

    >

    > http://faculty.juniata.edu/rhodes/intro/theory2.htm

    >

    > Of course this doesn't stop your scheme working - you just have to copy the

    > whole stack.

    > <thinks>  It makes detemining how to construct the eventual stack difficult

    > because you need to define "num outputs" for each process.  Normally in Joy the

    > result is the whole stack but in this case I understand you to mean some upper

    > subset of the stack, but what subset?  We're back to a non-computable problem

    > :-(

     No, the regexp scheme above is quite precise. "num-outputs" can include

    some hierarchy of regions.

     >

    > Perhaps you're thinking that this can't be done efficiently.

    > However, I don't see that fork introduces any fundamentally new problems that

    > don't already come up in writing an optimising compiler.

    >

    > I think the compiler gets a relatively easy ride because all the

    > clever stuff is explicit (other than analysis for arity).  The programmer has a

    > harder time because they have to decide which words can usefully be executed

    > concurrently, and to collect the results.

     Right, it could be unintuitive.

     >

    > > Joy currently is pure (well - 'get' and 'put' are exceptions)

    >

    > Indeed.

    >

    > > > Having the whole stack passed from word to word makes the order of

    > > > execution pretty rigid which limits how much laziness can be

    > > > employed.  I think.

    > >

    > > Its not rigid, a compiler can easily ignore the explicit order if it

    > > determines that no data dependencies will be violated.

    >

    > ...and that's the difficult bit.

    >

    > The stack is effectively a big piece of global data which is passed to every

    > word.  Because almost every word alters the stack, there is dependence between

    > most words.  The most obviously helpful word here is 'dip' but you need to know

    > the arity of all the preceeding words to safely execute it

    > out-of-order.

     Not at all, again you need to think in terms of "shape" and you'll see

    that the stack can always be delineated into reachable and unreachable

    parts.  Moreover, most words have a very small dependance.

     >

    > I suspect that stack based languages are inherently strict, rather than lazy,

    > but this is bare-faced assertion on my part and I'd be pleased to be shown to

    > be incorrect.

     I think side-effects are a much more serious issue here (especially

    foreign functions which the compiler has to treat as black boxes).

    --

    Louis.