# positional postfix evaluation

## Robbert van Dalen — 2013-05-27 19:30:51

    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 — 2013-05-27 23:59:01

    On 05/27/2013 03:30 PM, Robbert van Dalen wrote:

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

     > 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 — 2013-05-28 05:50:10

    > 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

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

     > 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