283
edits
Pipe-calculus: Difference between revisions
→Overview
KalmanKeri (talk | contribs) |
KalmanKeri (talk | contribs) |
||
| Line 10: | Line 10: | ||
Development of pipe-calculus stemmed from the idea that syntax should be a first class element of programming languages the same way as formation rules are integral part of logical systems. A language that complies with this principle is able to recognize the syntax of input data without using a parser library. Pipe-calculus is a very minimal language with this capability. | Development of pipe-calculus stemmed from the idea that syntax should be a first class element of programming languages the same way as formation rules are integral part of logical systems. A language that complies with this principle is able to recognize the syntax of input data without using a parser library. Pipe-calculus is a very minimal language with this capability. | ||
The first attempt to implement this idea resulted in a logical system which is referred to as ''well-typed parsing''. Later it was realised that well-typed parsing can be translated to a calculus that uses combinators and rewriting rules instead of inference rules, and this is the basis of the current formalisation. | The first attempt to implement this idea resulted in a logical system which is referred to as ''well-typed parsing''. Later it was realised that well-typed parsing can be translated to a calculus that uses combinators and rewriting rules instead of axioms and inference rules, and this is the basis of the current formalisation. | ||
On the practical side pipe-calculus is motivated by shell programming, streams and operating system processes. Indeed the idea of the ''pipe'' combinator comes from shell scripting. | |||
=== Connection to other fields === | === Connection to other fields === | ||
| Line 16: | Line 18: | ||
Pipe-calculus is inspired by logical programming, substructural logic, process calculus, formal grammars, automata theory, type theory (up to the lambda-cube) and the study of algebraic effects. | Pipe-calculus is inspired by logical programming, substructural logic, process calculus, formal grammars, automata theory, type theory (up to the lambda-cube) and the study of algebraic effects. | ||
In certain cases the connection can be made more precise. | |||
* Programs written in pipe-calculus can recognize and generate words of formal languages encoded as terms. The author is interested in finding correspondence between variants of the pipe-calculus and classes of formal languages. | |||
* Untyped lambda calculus can be translated to a subset of higher-order pipe-calculus. | |||
=== Variants === | === Variants === | ||
| Line 27: | Line 30: | ||
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 and with a stack. | 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 and with a stack. | ||
== Zero-order calculus == | == Zero-order calculus == | ||