283
edits
Pipe-calculus: Difference between revisions
→Motivation
KalmanKeri (talk | contribs) |
KalmanKeri (talk | contribs) |
||
| Line 8: | Line 8: | ||
=== Motivation === | === Motivation === | ||
Development of pipe-calculus | Development of pipe-calculus started with the idea that syntax should be a first class element of programming languages as well as formation rules are integral part of logical systems. A language like that is able to interpret complex input without using a parser library. Pipe-calculus is a minimal language with this capability. | ||
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. Shell programming is a proved and efficient way of problem solving and task automation, although it is not famous about its clarity and simplicity. | 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. Shell programming is a proved and efficient way of problem solving and task automation, although it is not famous about its clarity and simplicity. | ||
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 | 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>read s</code> | * <code>read s</code> checks if the next symbol of the input stream is <code>s</code>. On failure aborts the current branch of the program. | ||
* <code>write s</code> | * <code>write s</code> writes the symbol <code>s</code> to the output stream. | ||
* <code>run x</code> | * <code>run x</code> runs a program given its name. | ||
* <code>p ; q</code> | * <code>p ; q</code> runs <code>p</code> then runs <code>q</code> unless p fails. | ||
* <code>p | q</code> | * <code>p | q</code> forks the execution of the program so that one branch runs <code>p</code>, another branch runs <code>q</code>, sharing the same input and output stream. | ||
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. | ||
| Line 24: | Line 24: | ||
copyNat = read S; write S; run copyNat | read Z; write Z | copyNat = read S; write S; run copyNat | read Z; write Z | ||
Now we can write | Now we can write a program that writes the sum of two numbers to the output. | ||
addNat = read S; write S; run addNat | read Z; run copyNat | addNat = read S; write S; run addNat | read Z; run copyNat | ||
The idea is simple. We | The idea is simple. We skip the symbol <code>Z</code> that terminates the first number and pass on everything else. 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 used as a framework to study the required extensions that turn this tiny language into a practical programming language. | Pipe-calculus can be used as a framework to study the required extensions that turn this tiny language into a practical programming language. | ||