Michael S. Paterson
ABSTRACT
While we may have the intuitive idea of one programming language having greater power than another, or of some subset of a language being an adequate 'core' for that language, we find when we try to formalize this notion that there is a serious theoretical difficulty. This lies in the fact that even quite rudimentary languages are nevertheless 'universal' in the following sense. If the language allows us to program with simple arithmetic or list-processing functions then any effective control structure can be simulated, traditionally by encoding a Turing machine computation in some way. In particular, a simple language with some basic arithmetic can express programs for any partial recursive function. Such an encoding is usually quite unnatural and impossibly inefficient. Thus in order to carry on a practical study of the comparative power of different languages we are led to banish explicit functions and deal instead with abstract, uninterpreted programs, or <u>schemas</u>. What follows is a brief report on some preliminary exploration in this area.
- D. C. Luckham, D. M. R. Park and M. S. Paterson, On formalized computer programs. To appear in the Journal of Computer and Systems Sciences, June 1970.Google Scholar
- M. S. Paterson, Equivalence Problems in a Model of Computation. Ph.D. Thesis, Cambridge University, 1967.Google Scholar
- H. R. Strong, Translating Recursion Equations into Flow Charts. Parts 1 and 2. Reports RC 2834 (March 1970) and RC 2859 (April 1970), IBM Research Center, Yorktown Heights, New York.Google Scholar
Index Terms
- Comparative schematology
Recommendations
Comparative language fuzz testing: programming languages vs. fat fingers
PLATEAU '12: Proceedings of the ACM 4th annual workshop on Evaluation and usability of programming languages and toolsWe explore how programs written in ten popular programming languages are affected by small changes of their source code. This allows us to analyze the extend to which these languages allow the detection of simple errors at compile or at run time. Our ...
Comparative evaluation of performance-boosting tools for Python
The Python programming language has a number of advantages, such as simple and clear syntax, concise and readable code, and open source implementation with a lot of extensions available, that makes it a great tool for teaching programming to students. ...
Layout-sensitive language extensibility with SugarHaskell
Haskell '12: Proceedings of the 2012 Haskell SymposiumProgrammers need convenient syntax to write elegant and concise programs. Consequently, the Haskell standard provides syntactic sugar for some scenarios (e.g., do notation for monadic code), authors of Haskell compilers provide syntactic sugar for more ...
Comments