283
edits
Pipe-calculus: Difference between revisions
→An informal example
KalmanKeri (talk | contribs) No edit summary |
KalmanKeri (talk | contribs) |
||
| Line 18: | Line 18: | ||
On the practical side pipe-calculus is inspired by shell programming, which is largely based on text streams and stream processing tools. Indeed the idea of the ''pipe'' combinator comes from shell scripting. | On the practical side pipe-calculus is inspired by shell programming, which is largely based on text streams and stream processing tools. Indeed the idea of the ''pipe'' combinator comes from shell scripting. | ||
=== An | === An example === | ||
To get a taste of pipe-calculus, consider a program that adds two natural numbers encoded in [[wikipedia:Unary_numeral_system|unary numeral system]]. Suppose that we send both numbers over a stream as a series of <code> | To get a taste of pipe-calculus, consider a program that adds two natural numbers encoded in [[wikipedia:Unary_numeral_system|unary numeral system]]. Suppose that we send both numbers over a stream as a series of <code>1</code>s terminated by an <code>end</code> symbol. Our example language consists of the following expressions. | ||
* <code>match s</code> expects that the next symbol of the input stream is <code>s</code>. On failure the current branch of the program is aborted. | * <code>match s</code> expects that the next symbol of the input stream is <code>s</code>. On failure the current branch of the program is aborted. | ||
* <code>write s</code> | * <code>write s</code> appends the symbol <code>s</code> to the output stream. | ||
* <code>run x</code> runs a program given its name. | * <code>run x</code> runs a program given its name. | ||
* <code>p ; q</code> runs <code>p</code> then runs <code>q</code> unless <code>p</code> fails. | * <code>p ; q</code> runs <code>p</code> then runs <code>q</code> unless <code>p</code> fails. | ||
| Line 30: | Line 30: | ||
Start writing a routine that copies a natural number from the input to the output. | Start writing a routine that copies a natural number from the input to the output. | ||
passNat = match | passNat = match 1; write 1; run passNat | match end; write end | ||
Now we can write the program that writes the sum of two numbers to the output. | Now we can write the program that writes the sum of two numbers to the output. | ||
addNat = match | addNat = match 1; write 1; run addNat | match end; run passNat | ||
The program terminates after matching and writing out the second <code> | The program terminates after matching and writing out the second <code>end</code> symbol. It skips the first <code>end</code> that terminates the first number and copies everything else. | ||
Effectively it concatenates two <code> | Effectively it concatenates two <code>end</code>-terminated sequences of <code>1</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 | This language is obviously too weak. We can write simple filters, but we can't even check the equality of two 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. | ||