Pipe-calculus: Difference between revisions
KalmanKeri (talk | contribs) No edit summary |
KalmanKeri (talk | contribs) (→Syntax) |
||
| Line 1: | Line 1: | ||
Pipe-calculus is a core calculus for programming. | Pipe-calculus is a core calculus for programming. | ||
=== | === Variants === | ||
Atoms and literals are the most basic building blocks. | 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> \mbox{Atoms}~ A, B ::= \mathsf{Foo} ~|~ \mathsf{Bar}</math> | <math> \mbox{Atoms}~ A, B ::= \mathsf{Foo} ~|~ \mathsf{Bar}</math> | ||
| Line 11: | Line 19: | ||
<math> \mbox{Literals}~ l, m ::= A ~|~ \neg A </math> | <math> \mbox{Literals}~ l, m ::= A ~|~ \neg A </math> | ||
Literals are atoms with ''polarity''. | Literals are atoms with '''polarity'''. | ||
We say that a literal of the form <math>A</math> is ''positive'', while <math>\neg A</math> is ''negative''. | We say that a literal of the form <math>A</math> is ''positive'', while <math>\neg A</math> is ''negative''. | ||
See [https://en.m.wikipedia.org/wiki/Literal_(mathematical_logic) Literal (mathematical_logic)] for more information. | See [https://en.m.wikipedia.org/wiki/Literal_(mathematical_logic) Literal (mathematical_logic)] for more information. | ||
Primitive terms | |||
Revision as of 22:05, 3 February 2023
Pipe-calculus is a core calculus for programming.
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