283
edits
Pipe-calculus: Difference between revisions
→Overview
KalmanKeri (talk | contribs) No edit summary |
KalmanKeri (talk | contribs) |
||
| Line 22: | Line 22: | ||
First we write a routine that copies a natural number from the input to the output. | First we write a routine that copies a natural number from the input to the output. | ||
passNat = match S; write S; run passNat | match Z; write Z | |||
Now we can write a program that writes the sum of two numbers to the output. | Now we can write a program that writes the sum of two numbers to the output. | ||
addNat = match S; write S; run addNat | match Z; run | addNat = match S; write S; run addNat | match Z; run passNat | ||
The program terminates after matching and writing out the second symbol <code>Z</code> it encounters. It skips the first <code>Z</code> that terminates the first number and copies everything else. | The program terminates after matching and writing out the second symbol <code>Z</code> it encounters. It skips the first <code>Z</code> that terminates the first number and copies everything else. | ||
Effectively it concatenates two <code>Z</code>-terminated sequences of <code>S</code>s. If any other symbol occurs in the input stream, the program fails. | Effectively it concatenates two <code>Z</code>-terminated sequences of <code>S</code>s. If any other symbol occurs in the input stream, the program fails. | ||
This language is obviously too weak. We can write simple filters, but we can't even check the equality of two natural numbers. In order to do it, we need a method that allows the first number to be accumulated and read back symbol by symbol as we read the second number. | |||
Pipe-calculus can be seen as a framework to study the required extensions that turn this tiny language into a practical programming language. | Pipe-calculus can be seen as a framework to study the required extensions that turn this tiny language into a practical programming language. | ||
| Line 37: | Line 37: | ||
Pipe-calculus is examined primarily as a process calculus. However it significantly differs from typical process calculi, it still lends itself to this style of presentation. | Pipe-calculus is examined primarily as a process calculus. However it significantly differs from typical process calculi, it still lends itself to this style of presentation. | ||
Its development is also inspired by logic programming | Its development is also inspired by logic programming, formal grammars, automata theory, type theory (up to the lambda-cube) and algebraic effects. | ||
In certain cases the connection with these fields can be made more precise. | In certain cases the connection with these fields can be made more precise. | ||
* Programs written in pipe-calculus can recognize and generate words of formal languages encoded as terms. | * Programs written in pipe-calculus can recognize and generate words of formal languages encoded as terms. I'm interested in finding correspondence between variants of pipe-calculus and classes of formal languages. | ||
* Untyped lambda calculus can be translated to a subset of higher-order pipe-calculus (to be specified later). | * Untyped lambda calculus can be translated to a subset of higher-order pipe-calculus (to be specified later). | ||
| Line 50: | Line 50: | ||
The most simple variant of the calculus that is lacking variables and scoped constructs is called '''zero-order'''. | The most simple variant of the calculus that is lacking variables and scoped constructs is called '''zero-order'''. | ||
Somewhat surprisingly, even the zero-order calculus has a limited computational power. | Somewhat surprisingly, even the zero-order calculus has a limited computational power. | ||
In the '''higher-order''' calculus there are lexically scoped variables that can bind arbitrary terms. Intermediate variants can be constructed by extending the basic calculus with recursion | In the '''higher-order''' calculus there are lexically scoped variables that can bind arbitrary terms. Intermediate variants can be constructed by extending the basic calculus with recursion, among others. The computational power of specific variants of the calculus is also an interesting question. | ||
== Zero-order calculus == | == Zero-order calculus == | ||