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
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
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
(.1 0 /) gets substituted for
c, then we try to evaluate
(.) which succeeds, leaving only
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.