Concatenative Function Calls, without the Bang

Killing the Call Operator

In my last post, I introduced the idea of a concatenative calculus with variables, similar in spirit to the lambda calculus. One of the key differences between lambda and concatenative varieties was the presence of an explicit `calling` word (!). A couple of days after posting, I realized the call operator was not actually necessary, and was an artifact of my tendency to think of concatenative languages in terms of stack-based languages.

The key insight lies in the fact that the two evaluation rules introduced differ not only in the presence of the call operator, but also in the number of arguments each function expects. In the first evaluation rule (Application) the number of arguments to the function must be zero. In the second rule (Substitution) the number of arguments must be greater than zero (one or more).

Using this distinction, we can eliminate the call operator from the language entirely, and all functions that take zero arguments will reduce automatically. I don’t believe this either increases or decreases the power of the language, though I’m not sure. Rather, function calls in this new language could be regarded as `implicit`, rather than `explicit` as in the system with the call operator.

T :=
1. (Empty) => ε ϵ T
2. (Var)   => If v ϵ V and t ϵ T, then tv ϵ T
3. (Abs)   => If v1,...,vn, n >= 0 ϵ V and t1, t2 ϵ T, then t1(v1...vn.t2) ϵ T.

This is the new syntax for our language. There are only three construction rules, rather than the four rules of the previous system. The concatenation operation on terms (++) is similarly modified to remove the case that mentions the call operator. Our reduction rules have changed only in the case of application, where the call operator (!) has been removed:

(Application) t1(.t2) ==> t1 ++ t2
(Substitution.Var) t1v(a1...an.t2) ==> t1 ++ (a1...an-1.t2[an/(εv)]
(Substitution.Abs) t1(b1...bn.t2)(a1...an.t3) ==> t1 ++ (a1...an-1.t3[an/(ε(b1...bn.t2))

This seems better all around! Is it possible that we might ever want a language with an explicit call operator when this simpler formulation exists? My hypothesis is that `pure` languages would not need an explicit call operator due to the lack of side effects. However, a language with side effects should arguably keep the explicit call operator. For example, say there is a function which generates random numbers. This function takes no input, but produces output. In the new system, any mention of this function will be reduced only once. If we pass the function as an argument to another function, it will generate the random number, and then proceed to use only that number in all other calls in that function, which is clearly not what is intended!

Evaluation Order Curiosities

When I discovered the concatenative mailing this, there was a tiny language called `Peg` that had been discussed. Peg was unique because it claimed to be a lazy concatenative language. The developer seems to have changed the name since then, and the new language includes some strange semantics that I confess I don’t fully understand, but the idea of a lazy concatenative language remains tantalizing to me.
In a strict concatenative language, we try to apply an evaluation rule at the left-most possible step each time. How might a lazy concatenative language be different? One possible idea is to only apply only substitutions at each left-most possible step until no more substitutions can be done, then apply the rightmost thunk which has no arguments. We can see this difference in action in an example. Imagine that the language has been extended with numbers and a division operator:
Left-to-Right:
  2 1 (a.a 0 /) (c.)
  ==> 2 (.1 0 /) (c.)
  ==> error! attempted division by zero
Right-to-Left:
  2 1 (a.a 0 /) (c.)
  ==> 2 1 (a.a 0 /) (c.)
  ==> 2 (.1 0 /) (c.)
  ==> 2 (.)
  ==> 2

In the first example,  we try to apply an evaluation rule at the left-most possible spot at each step. So first we substitute 1 for a, then try to evaluate (.1 0 /), which means we must evaluate the function body. This leads to a division by zero error.

But in the second example, we first substitute at the left-most possible spot at each step, then do an application at the very end. So 1 gets substituted for a, then (.1 0 /) gets substituted for c, then we try to evaluate (.) which succeeds, leaving only 2.

Again, I haven’t thought too much about these ideas yet, so take everything with a grain of salt, but at the very least this evaluation order seems to point in a promising direction for adding lazy semantics in a concatenative language.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s