283
edits
Pipe-calculus: Difference between revisions
→Motivation
KalmanKeri (talk | contribs) |
KalmanKeri (talk | contribs) Tags: Mobile edit Mobile web edit |
||
| Line 14: | Line 14: | ||
How would a small and well established stream processing language look like? To get a taste, consider a program that adds two natural numbers encoded in [[wikipedia:Unary_numeral_system|unary numeral system]], a popular example in theoretical computer science. Suppose that we send both numbers over a stream as a series of <code>S</code> symbols terminated by a symbol <code>Z</code>. Our example language consists of the following expressions. | How would a small and well established stream processing language look like? To get a taste, consider a program that adds two natural numbers encoded in [[wikipedia:Unary_numeral_system|unary numeral system]], a popular example in theoretical computer science. Suppose that we send both numbers over a stream as a series of <code>S</code> symbols terminated by a symbol <code>Z</code>. Our example language consists of the following expressions. | ||
* <code> | * <code>match s</code> checks if 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> writes the symbol <code>s</code> to the output stream. | * <code>write s</code> writes 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. | ||
| 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. | ||
copyNat = | copyNat = match S; write S; run copyNat | 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 = | addNat = match S; write S; run addNat | match Z; run copyNat | ||
The | 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. | ||
Pipe-calculus can be | 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. | ||
Nevertheless this language is 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. | |||
=== Connection to other fields === | === Connection to other fields === | ||