Pipe-calculus

Pipe-calculus is a core calculus for programming.

Overview

Motivation

Development of pipe-calculus stemmed from the author's conviction that syntax should be a first class element of programming languages the same way as formation rules are integral part of logical calculi. A language that complies with this principle is able to recognize the syntax of input data without using a parser library. Pipe-calculus is a very minimal language with this property.

The first attempt to construct such a language resulted in a logical system, which is referred to as well-typed parsing.

Variants

Pipe-calculus is meant to be an extensible framework. Extensions add various features to the basic calculus. One such important feature is the inclusion of variables. Variants without variables and any kind of scoped construction are called zero-order. Somewhat surprisingly, even the zero-order calculus has a limited computational power. On the other end of the scale there are higher-order variants where variables can hold arbitrary terms. Intermediate variants can be constructed by extending the basic calculus with recursion and with a stack.

When used as recognizers, extended variants of the calculus can generally recognize more expressive formal languages.

Zero-order calculus

Syntax

Atoms and literals are the most basic building blocks.

[math]\displaystyle{ \mbox{Atoms}~ A, B ::= \mathsf{Foo} ~|~ \mathsf{Bar} }[/math]

[math]\displaystyle{ \mbox{Literals}~ l, m ::= A ~|~ \neg A }[/math]

Literals are atoms with polarity. We say that a literal of the form [math]\displaystyle{ A }[/math] is positive, while [math]\displaystyle{ \neg A }[/math] is negative. See Literal (mathematical_logic) for more information.

Primitive terms