wtanksley@... wrote:
>Well I do abstract interpretation: this is just like normal
> 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?
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 toSo essentially, is this just lexical preprocessing, or does Forth
> 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.
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-likeI do plan on setting up a website at some point with some documentation,
>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.
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 inPerhaps your thinking of Lucid? I think it works that way. There is a
> 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.
website at http://www.csl.sri.com/Lucid.html .
--
Louis.
----- 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
> can you step through the evaluation for me? i would think that theby 5 - where's that second cup of coffee?
> result is the program which multiples its argument by 6
stevan apter wrote:
>2 2
> ----- 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 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 howsemantically, there is no difference. In fact the partial evaluator has
> is that different from the program [2 3 + *]; i.e., from
>
> [2 3 + *]
>
> ?
the same semantics as 'id'. However, the resulting program will usually
be more efficient (and never less efficient).
>Languages without PE make you pay a generalisation penalty; you pay that
> > 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.)
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 wrote:
> 2 2Sorry, I meant 5. Looks like I need a cup of coffee too :-)
> 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.
Louis.