[stack] positional postfix evaluation

[Robbert van Dalen]

positional postfix evaluation

- please set the font to mono-spaced for better readability -

this short post describes a novel (postfix) computational model that may interest you.
it has the following properties:

1) atoms in (sub)expressions take position and are evaluated in-position
2) an atom can be a subexpression, syntactically surrounded by parenthesis
3) parenthesis are transparent, while evaluating an expression
4) expressions are evaluated in parallel

let me present the canonical example:

1 2 + 3 4 + * =>
3 7 * =>
21

.. demonstrating property 1 and 4.

so why the need for positions?
it allows the data flow of a program to be easily eyeballed.

here is another example:

(1 2) + 3 (4 (+ *)) =>
3 ( (7 *)) =>
( (21))

.. which demonstrates property 2 and 3.
it also demonstrates that parenthesis - which are transparent - retain their position after evaluation.

but notice that the postfix evaluation of subexpressions are less easily eyeballed.
so why the need for subexpressions and parenthesis?

solely because of efficiency reasons.
the following example shows the efficient in-place substitution and evaluation of subexpressions:

e1 == 1 2 +
e1 => 3

e2 == 3 4 +
e2 => 7

e3 == e1 e2 *
e3 == (1 2 +) (3 4 +) *
e3 => ( 3) ( 7) *
e3 => 21

here is an 'explicit' positional representation of the same substitutions:

e1 == 0=1 1=2 2=+
e1 => 2=3

e2 == 0=3 1=4 2=+
e2 => 2=7

e3 == e1 e2 *
e3 => 0=(0=1 1=2 2=+) 1=(0=3 1=4 2=+) 2=*
e3 => 0=( 2=3) 1=( 2=7) 2=*
e3 => 2=21

note that all this is implemented in the spread programming language v0.2.

care to comment?
please do!

cheers,
robbert




[Non-text portions of this message have been removed]

[John Nowak]

Post by Robbert van Dalen
so why the need for positions?
it allows the data flow of a program to be easily eyeballed.

Only when you're writing expressions that compute to values. Most of the
time, however, you're defining functions and your technique will be of
no use. For example, suppose I want to write a simple function that
computes the length of a list in a Joy:

length == [null] [drop 0] [uncons [drop] dip length 1 +] ifte

As can be clearly seen, there's no obvious way to group any of this.

Post by Robbert van Dalen
so why the need for subexpressions and parenthesis?
solely because of efficiency reasons.

Why would this make any difference in terms of efficiency? So long as
your compiler knows the arity of the words involved before it compiles
them, it can do whatever optimizations you have in mind automatically.

If you're interested in allowing the programmer to get a better handle
on the stack effects of functions, I would suggest applying a typing
discipline. Not only would this work properly in the presence of (higher
order) functions, it would also allow information regarding stack
effects to be computed automatically via type inference.

For example, we can assume the following primitive types:

null : ∀ R a. R (list a) -> R bool
drop : ∀ R a. R a -> R
uncons : ∀ R a. R (list a) -> R a (list a)
dip : ∀ R S a. R a [R -> S] -> S a
+ : ∀ R. R int int -> R int
ifte : ∀ R S T. R [R -> S bool] [R -> T] [R -> T] -> T

Above, the uppercase type variables represent stacks. The lowercase type
variables and lowercase types represent single elements consed onto
stacks. Types like '(list a)' denote the type of a single element equal
to the type constructor 'list' applied to the type 'a'.

With all this in place, we can compute the following type of 'length'
via Hindley–Milner type inference:

length : ∀ R a. R (list a) -> R int

The fact that all this is precise and automatic is of tremendous benefit
to the programmer. We can tell from the type that only the top element
will be inspected (because the function is parametrically polymorphic
with respect to 'R'). We also can tell the function has an arity of '1
-> 1'. Finally, we can tell it works for all lists (because the function
is parametrically polymorphic with respect to 'a') and that the result
will be an integer on top of the stack.

- jn

[Robbert van Dalen]

Post by John Nowak
length == [null] [drop 0] [uncons [drop] dip length 1 +] ifte
As can be clearly seen, there's no obvious way to group any of this.

that's because it's a joy program, not a spread program

Post by John Nowak

Post by Robbert van Dalen
so why the need for subexpressions and parenthesis?
solely because of efficiency reasons.

Why would this make any difference in terms of efficiency? So long as
your compiler knows the arity of the words involved before it compiles
them, it can do whatever optimizations you have in mind automatically.

spread programs are pretty much free of form, so they resist static compilation.
optimisation is achieved via efficient multi(set/map) operations,
similar to how array languages have their array operations optimised.

Post by John Nowak
If you're interested in allowing the programmer to get a better handle
on the stack effects of functions, I would suggest applying a typing
discipline.

i don't like to be disciplined ;)
seriously: i find hindley-milner type inference pretty boring.
i've implemented the spread interpreter in scala, which has a much more interesting type system.
(see for example: https://github.com/rapido/spread/blob/master/src/spread/OrderedTreapSet.scala)

- robbert