# Re: [stack] Abstract state machines and Joy

## Louis Madon — 2000-06-08 10:22:23

    wtanksley@... wrote:

     >

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

    > >If I really needed to embed another language I would rather just

    > >parse strings, eg:

    > >  "For x in <10,20,30> do Print x;" mylang_call

    > >  => 10 20 30

    >

    > >Here, the mylang_call function takes a string, compiles it into a

    > >program and executes it. There is a clear separation between the core

    > >language and the embedded syntax thanks to the quotes. Moreover, at

    > >least in my version of Joy which will support partial evaluation, the

    > >mylang_call function will get executed at compile time since all its

    > >inputs are available; so there is no additional runtime cost.

    > That's really interesting.  It's also interesting that you're able to

    > determine what parameters are and are not available; my guess is that you do

    > that similarly to how Dr. Betcher carries out static type checking, correct?

     Well I do abstract interpretation: this is just like normal

    interpretation except that any time the stack underflows you place a new

    symbol on the stack to act as a proxy for the missing input. Whenever a

    primitive is encountered, if all its inputs are non-symbolic then it

    just executes normally [some operations can be performed even if some of

    their inputs are symbolic though, eg: dup, swap, dip, choice].

    Otherwise, an expression node of the form

    [inputs--primitiveOp--outputs] is created to model the computation

    symbolically - the inputs are then removed from the stack and replaced

    by references to the outputs in the expression. Once interpretation is

    complete whatever is left on the stack is the result [as in normal

    execution]. That result can then easily be mapped back into code to

    create a new specialised program that is _equivalent_ to the original.

    As an example, assume we have defined the function:

    (* n m -- n^m    fast computation of the mth power of n *)

    fast-pow ==

      [dup zero?]

       [pop2 1]

       [ [dup even?]

          [2 / fast-pow dup *]

          [pred dupd fast-pow *]

          ifte]

      ifte;

    if we gave [5 fast-pow] to the partial evaluator, the result would be

    [dup 1 * dup * dup * *]

    if the abstract interpretation is augmented with some rewrite rules,

    eg. a 1 * => a, then the result further simplifies to

    [dup dup * dup * *]

    which does indeed compute the 5th power of its input.  Notice that

    despite the heavy use of quotations in the original function, its

    specialisation is essentially just three multiplications.

    An important issue which I should mention is that this approach appears

    to _require_ that all functions be either monomorphic or at most

    parametrically polymorphic (ie. each function has only one

    implementation but nonetheless can be instantiated for different types,

    eg. via runtime types and polymorphic primitives). For overloading

    polymorphism (several implementations per function possible,

    discriminated by types) it doesn't work because the abstract interpreter

    cannot choose the correct branch to follow unless it knows the types of

    all parameters. If a parameter is symbolic this information may not be

    available.

    Therefore, in my system (which is designed to support overloading with

    subtyping), abstract interpretation occurs  only after type analysis.

    The type analysis itself is done through constraint satisfaction (see

    the paper  "Constrained Types: A Personal Perspective" by Scott Smith at

    http://www.cs.jhu.edu/hog - this is not quite the same as what I'm doing

    but the notion of inferring types by satisfying the constraints implied

    by the operations in the program is).

    In regards to how similar this might be to Dr. Betchers' work, I don't

    know. I'd be interested to know more about his type system, but I

    suspect from his recent post that more information isn't available just

    yet.

     > As I've mentioned before, Forth adds an additional element to

    > concatenativity: Forth words can also access the source code which follows

    > their invocation, so that you can define words which arbitrarily manipulate

    > source.  This is safe, because none of the source they manipulate has been

    > seen by the compiler or parser.

     So essentially, is this just lexical preprocessing, or does Forth

    precompile into symbols (as in lisp) and then you operate on those?

    (sorry I don't know Forth).  In Joy, since programs can be generated on

    the fly from data, I see no need for anything more.

     >In my Joy-like

    >language, the fundamental association primitive is the dynamic function

    >(aka updatable, variable or mutable functions, a notion from Abstract

    >State Machine

    >theory - see http://www.eecs.umich.edu/gasm and in particular take a

    >look at Martin Odersky's paper "Programming with variable functions" at

    >http://www.eecs.umich.edu/gasm/papers.html#varfun).

    > Wow, a combination of GASMs and Joy -- now I'm really happy.  I've been

    > impressed with ASMs since I first read about them.  I look forward to

    > hearing more about your work.

     I do plan on setting up a website at some point with some documentation,

    but right now I want to concentrate on finishing the prototype. However,

    I'll post another message on dynamic functions as well as an example

    that uses them to implement a singly-linked list type tomorrow.

     > There's one other language I've seen which attempts to model mutability in

    > the context of a purely functional language; it uses series.  Your functions

    > are allowed to access future and past elements of any series (and that

    > access, of course, forces them to be computed).  I was impressed with how

    > elegantly the language worked, but I've been unable to find it ever since.

     Perhaps your thinking of Lucid?  I think it works that way. There is a

    website at http://www.csl.sri.com/Lucid.html .

    --

    Louis.

## stevan apter — 2000-06-08 12:41:18

    ----- Original Message -----

    From: Louis Madon <madonl@...>

    To: <concatenative@egroups.com>

    Sent: Thursday, June 08, 2000 6:22 AM

    Subject: Re: [stack] Abstract state machines and Joy

    hi louis - welcome to the group.

    >

    > Well I do abstract interpretation: this is just like normal

    > interpretation except that any time the stack underflows you place a new

    > symbol on the stack to act as a proxy for the missing input. Whenever a

    > primitive is encountered, if all its inputs are non-symbolic then it

    > just executes normally [some operations can be performed even if some of

    > their inputs are symbolic though, eg: dup, swap, dip, choice].

    > Otherwise, an expression node of the form

    > [inputs--primitiveOp--outputs] is created to model the computation

    > symbolically -

    i follow you up to here.  for example, suppose we have

        2 3 + *

    can you step through the evaluation for me?  i would think that the

    result is the program which multiples its argument by 6, but how

    is that different from the program [2 3 + *]; i.e., from

        [2 3 + *]

    ?

    > the inputs are then removed from the stack and replaced

    > by references to the outputs in the expression. Once interpretation is

    > complete whatever is left on the stack is the result [as in normal

    > execution]. That result can then easily be mapped back into code to

    > create a new specialised program that is _equivalent_ to the original.

    can you explain why partial evaluation is useful?

    (i'm thinking of timeslicing parallel computations,

    but i'm certain there's more to it than this.)

    thanks

    sa

## stevan apter — 2000-06-08 12:43:07

    > can you step through the evaluation for me?  i would think that the

    > result is the program which multiples its argument by 6

     by 5 - where's that second cup of coffee?

## Louis Madon — 2000-06-08 22:40:40

    stevan apter wrote:

     >

    > ----- Original Message -----

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

    > To: <concatenative@egroups.com>

    > Sent: Thursday, June 08, 2000 6:22 AM

    > Subject: Re: [stack] Abstract state machines and Joy

    >

    > hi louis - welcome to the group.

    >

    > >

    > > Well I do abstract interpretation: this is just like normal

    > > interpretation except that any time the stack underflows you place a

    > new

    > > symbol on the stack to act as a proxy for the missing input.

    > Whenever a

    > > primitive is encountered, if all its inputs are non-symbolic then it

    > > just executes normally [some operations can be performed even if

    > some of

    > > their inputs are symbolic though, eg: dup, swap, dip, choice].

    > > Otherwise, an expression node of the form

    > > [inputs--primitiveOp--outputs] is created to model the computation

    > > symbolically -

    >

    > i follow you up to here.  for example, suppose we have

    >

    >     2 3 + *

    >

    > can you step through the evaluation for me?  i would think that the

    > result is the program which multiples its argument by 6,

     2               2

    2 3             3

    6               +  (evaluate normally since all inputs are there)

    b               *  (where b refers into the expression node [a 6 --> *

    --> b]

    In the last step, the stack underflowed so a new symbol 'a' was added to

    the bottom of the stack to represent the missing input (at this point

    the stack contents are: a 6 ) Then the result is represented by a

    symbolic expression:

        b

        |

        *

       / \

      a   6

    So [a 6] are removed from the stack and replaced by b (the symbol that

    was created to represent the output of the expression). Since we've now

    reached the end of the program that is also the result. In a more

    complex program b may

    in turn get consumed within yet another expression thus the final result

    expression can be arbitrarily complex.

    Then, these expression graph(s) get traversed in postfix order to

    convert them back into code (this may result in the insertion of some

    dups and swaps to maintain the constraint that input symbols may only

    appear on the very left and in their originally encountered order). In

    this example, we have [b] on the stack so after traversal of the

    expression it references we are left with [a 6 *]. Finally, the input

    symbols are just discarded leaving [6 *].

     > but how

    > is that different from the program [2 3 + *]; i.e., from

    >

    >     [2 3 + *]

    >

    > ?

     semantically, there is no difference. In fact the partial evaluator has

    the same semantics as 'id'. However, the resulting program will usually

    be more efficient (and never less efficient).

     >

    > > the inputs are then removed from the stack and replaced

    > > by references to the outputs in the expression. Once interpretation

    > is

    > > complete whatever is left on the stack is the result [as in normal

    > > execution]. That result can then easily be mapped back into code to

    > > create a new specialised program that is _equivalent_ to the

    > original.

    >

    > can you explain why partial evaluation is useful?

    > (i'm thinking of timeslicing parallel computations,

    > but i'm certain there's more to it than this.)

     Languages without PE make you pay a generalisation penalty; you pay that

    penalty in one of two ways

    1  Your program runs slower because of redundant computation that could

    have been done at compile time (eg. repeatedly doing 2 3 + in the

    example above).

    2  You _manually_ eliminate the redundancy be specialising the code

    yourself. For example, you write a 3x3 matrix multiply routine rather

    than using that general purpose nxn multiply in the library. Ok, your

    program now runs fast but you lost productivity doing it.

    --

    Louis.

## Louis Madon — 2000-06-08 22:48:19

    Louis Madon wrote:

     > 2               2

    > 2 3             3

    > 6               +  (evaluate normally since all inputs are there)

    > b               *  (where b refers into the expression node [a 6 --> *

    > --> b]

    >

    > In the last step, the stack underflowed so a new symbol 'a' was added

    > to

    > the bottom of the stack to represent the missing input (at this point

    > the stack contents are: a 6 ) Then the result is represented by a

    > symbolic expression:

    >

    >     b

    >     |

    >     *

    >    / \

    >   a   6

    >

    > So [a 6] are removed from the stack and replaced by b (the symbol that

    > was created to represent the output of the expression). Since we've

    > now

    > reached the end of the program that is also the result. In a more

    > complex program b may

    > in turn get consumed within yet another expression thus the final

    > result

    > expression can be arbitrarily complex.

     Sorry, I meant 5. Looks like I need a cup of coffee too :-)

    Louis.