8
$\begingroup$

In a concatenative programming language, two subprograms can be composed by appending one to the other. One effect of this is that function calls are directly equivalent to their bodies. This trait provides a potential way of executing the program, while a more typical recursive execution also works.


To contextualise, a user-defined function in these languages can just be a series of function-call terms, here written in a pseudocode postfix stack-based concatenative language:

twice-plus-1: 2 mul 1 add

When called, this function will just perform those four operations with the available arguments (consuming one value and producing one value), and so the effect will be the same as if its body were written inline. That is, these two lines have the same effect:

5 2 mul 1 add
5 twice-plus-1

The ability to abstract a function cleanly from code by splicing out any consecutive series of terms, giving a name to it, and replacing those terms with the name is one of the key value propositions of concatenative languages.


In reverse it is also an execution model: evaluating the program starts with a list of the terms in the entry point (top level, main function) of the source, to be processed from start to finish. For each term:

  • If it is a call to a user function, expand it into the body of that function and continue. The single function call entry in the list is replaced by as many entries as there are terms in the function body, in order, with the rest of the program still there after the last term.
  • If it is a built-in, constant, quote, etc, apply it directly however is appropriate and remove it from the list.

(This might use a stack or cyclic buffer for efficiency, or some other approach, but that's not core to the question.) When the remaining program is empty or cannot evaluate any further, the program is finished.

The other obvious execution model is a more conventional recursive call-stack approach. A function call jumps into that function, and returns to the call site afterwards. When the last function returns, the program is finished. A variation on this model is to take the expected number of arguments and pass only those to the function.

In theory, both mechanisms seem to give the same results. Is one approach more appropriate in practice, and why? Is this merely an implementation detail, or are there liable to be semantic effects as well? If so, what will be noticeable by the programmer?

Although I have used a postfix stack-based model in the example, prefix or non-stack-based concatenative models may be relevant to the answer as well (or may not make a difference).

$\endgroup$
2
  • $\begingroup$ I find your execution model surprisingly similar to that of lambda calculus, especially combinator machines. A combinator machine takes the top combinator and its argument(s) from the "spine", evaluates it, and pushes the result back onto the spine. The difference would be that data and code are separate in concatenative model, but quote is also data, so... $\endgroup$
    – Bubbler
    May 22, 2023 at 5:14
  • $\begingroup$ Yes, and there are concatenative models that do operate in that fashion, with values manifest within the program (Om is probably the major one). Those may be specifically relevant too, but the evaluation model here works for any concatenative approach by nature, and this is the right user base for someone having had real experience doing that. $\endgroup$
    – Michael Homer
    May 22, 2023 at 6:25

1 Answer 1

4
$\begingroup$

This question appears superficially similar to Pros and cons of reifying the stack in an interpreter, because evaluating a term in a concatenative language is analogous to calling a function in an imperative language. However, the "expansion" execution model is not analogous to using a call stack, because it represents the terms in the program which have yet to be evaluated, whereas a call stack represents functions which are currently being evaluated. The "expansion" model can be implemented using a stack of terms, as opposed to a stack of activation frames.

The term stack initially contains the program's terms in reverse order, so that the first term is on the top of the stack. The program is executed by iteratively popping the term from the top of the stack and evaluating it. When the term to be evaluated is a quote, simply push the terms from the quote into the term stack in reverse order. (If quotes are stored in reverse order then it's even simpler.)

The main advantage of using a term stack over recursive evaluation is that it's simpler. Your interpreter already has a data structure to represent terms, so you just need a stack of them, and now your whole interpreter is a dispatch loop instead of a recursive tree walker ─ like what you'd use for a bytecode interpreter, except there is no need to compile the AST into a bytecode first.

Using a term stack also opens up the possibility of applying optimisations at runtime. The term stack has the same structure as a program ─ it's just a sequence of terms, to be evaluated in order ─ so any reductions you are able to statically apply to a program's source code, can in principle also be applied at runtime to the terms in the stack. This could for instance be done in a separate thread so that the program doesn't have to be paused to do it.


The question asks for a comparison between two implementations, but I would like to add a third: maintain an explicit, reified call stack. Each stack frame is simply a reference to a quote and an index to the next term in that quote to be evaluated. (The interpreter for my toy concatenative language fffff is implemented this way.)

Having a reified call stack makes it easy to report stack traces when an error occurs, and (compared to recursive evaluation) allows for tail-call optimisation of recursive quotes.


Since they are just different implementation choices, I don't see that the choice has any direct impact on the language's semantics. That said, it may have knock-on effects due to what other language features become feasible to implement. For example, using recursive evaluation or a reified call stack might make it easier to implement lexical scope and lexical closures.

$\endgroup$
1
  • $\begingroup$ related terminology: recursive "implicit control evaluators" effectively use the host language's stack, inheriting any limitations the host language has (tail-calls being a good example); "explicit control evaluators" manage their own stack however they want. $\endgroup$ Jul 4, 2023 at 20:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .