Concatenative language

From Esolang
Jump to navigation Jump to search

A concatenative programming language can compose multiple programs into one program by juxtaposition of syntax. Whether a language is concatenative is a property of both syntax and semantics in combination.

Background

One of the basic principles of software engineering and formal logic is composition: build large things from combinations of small things. For example, many popular languages like C, Haskell, or Python have composition of arithmetic and applicative expressions.

2 + 3

This expression is built from two smaller expressions, and the result of evaluating this expression — its meaning under the semantics of the language — is built from the result of evaluating those expressions. To be technical, the expression is built by juxtaposition of strings, which means that the strings were placed next to each other and glued together into one string. A juxtaposition of many strings is called a concatenation.

C, Haskell, and Python also have composition of module fragments. Under common conditions, code can be moved from one module to another with only minor refactoring.

Suppose that a language has only one major syntactic form; this is sometimes known as the slogan, "every program is an expression." Then it could be the case that the semantic meaning of every program is composed from the semantic composition of its syntactic elements.

Classical theory

There is a long-standing tradition of concatenative languages which starts with Forth. A common feature of all dialects of Forth is the ability to call two subroutines in a row by placing their words in sequence. For example, the Python example from last section would be written in Forth as:

   2 3 +

This runs the builtin subroutines for numbers 2 and 3, and then adds the results of the previous two subroutines. This notation is called wikipedia:reverse Polish notation and is useful for calculators because it does not require parentheses.

As language designers generalized Forth, this principle became a maxim: the concatenation of two Forth-like programs should be the composition of their stack effects.

Categorical theory

Von Thun gives a definition of concatenative languages using the language of category theory. Abstractly, let juxtaposition of syntax give a monoid, and also let composition of programs give a monoid. Then the concatenative rule is a monoid homomorphism from syntax to semantics.

To explain in more detail, a wikipedia:monoid is an inhabited set with a unit element and an associative binary operation. In general, an element of a monoid is like a sequence; the unit element is the empty sequence and the binary operation is concatenation of sequences. Monoids capture the idea of doing things in sequence, including doing nothing. A homomorphism is a function from a source monoid to a target monoid which sends the source's unit element to the target's unit element and preserves the binary operation.

This is what Von Thun means when they say:

"…the meaning of Joy programs is shown to be a homomorphism from a syntactic monoid to a semantic monoid."

Von Thun gave a bridge from the classical theory to this one:

"The concatenation of two programs denotes the composition of the functions denoted by the two programs."

Other definitions