ABSTRACT
We use the concept of evaluation up to a given threshold of information to generalize the semantics of call by value and assignment to non-discrete domains, and to define a formal semantics for generic procedures. We then prove the correctness of McCarthy's transformation of iterative programs into recursive ones provided the same threshold is used for assignment and parameter passing.
- J. McCarthy. A basis for a mathematical theory of computation. In Computer Programming and Formal Systems, Braffort and Hirschberg Ed., North Holland, Amsterdam, (1963).Google Scholar
- R. Strong. Translating recursion equations into flow charts. Journal of Computer and System Sciences, Vol.5.No3. (June 1971).Google ScholarDigital Library
- B. Courcelle. Personal communication. To appear in book form.Google Scholar
- D. Scott. Outline of a mathematical theory of computation. Programming Research Group Monograph No.2, Oxford University (1970).Google Scholar
- Z. Manna and J. Vuillemin. Fix point approach to the theory of computation. Communications of the ACM, 15, 528-536, (1972). Google ScholarDigital Library
- J. Vuillemin. Syntax, semantique et axiomatique d'un language de programmation simple. These de Doctorat es-sciences Mathematiques, Université de Paris VII, Paris, (1974). see also Implementation of recursion in a simple programming language. Proc. 5th Annual ACM Symposium on Computing, (1973). Google ScholarDigital Library
- M. Nivat. On the interpretation of recursive program schemes. Symposia Mathematica, Vol, XV, Instituto Nationale di Alta Matematica, Italy, pp. 255-281, (1975).Google Scholar
- D. Park. Fixpoint induction and proofs of program properties. Machine Intelligence 5 (eds. B. Meltzer and D. Michie), Edinburgh: Edinburgh University Press, pp.59-77 (1969).Google Scholar
- W. P. de Roever. Recursion and parameter-machanisms : an axiomatic approach. In Automata, Languages and Programming (ed. J. Loeckz), pp.34-65, Lecture Notes in Computer Science Vol. 14, Springer-Verlag, Berlin, etc., (1974). Google ScholarDigital Library
- J. W. de Bakker, Least fixed points revisited. Proc. of Symposium on λ-Calculus and Computer Science Theory, Roma, pp.1-35, (1975). Google ScholarDigital Library
- G. Boudol, Langages poluadiques algebriques. Theorie des schemas de programmes : semantique de l'appel par valeur. Thèse 3e cycle, Université Paris VII, (1975).Google Scholar
- J. McCarthy et al. LISP 1.5 Programmer's Manual, MIT Press, Cambridge, Mass., (1962). Google ScholarDigital Library
- A. van Wijngaarden et al. Revised report on the algorithmic language ALGOL 68. Acta Informatica, Vol.5, Fasc. 1-3, (1975).Google Scholar
- B. Wegbreit et al. The ECL Programmer's Manual. Harvard University, Center for Research in Computing Technology, 21-72, (1972).Google Scholar
- R. M. Burstall, J. S. Collins and R. J. Popplestone. Programming in POP-2. Edinburgh : Edinburgh University Press, (1971).Google Scholar
- P. J. Landin. The mechanical evaluation of expressions. Computer Journal, Vol.6 No4.Google Scholar
- G. D. Plotkin. Call-by-name, call-by-value and the λ-calculus. J. Theoret. Comp. Sci., 1, 125-159, (1975).Google ScholarCross Ref
- C. P. Wadsworth. Semantics and pragmatics of the lambda-calculus. Ph.D.thesis. University of Oxford, (1971).Google Scholar
- P. Henderson and J. Morris, Jr. A lazy evaluator. 3rd ACM Symp.on Prin. of Prog. Lang., pp. 95-103. Google ScholarDigital Library
- D. P. Friedman and D. S. Wise. CONS should not evaluate its arguments. Proc. of 3rd Coll. on Automata, Languages and Programming. Edinburgh, (1976).Google Scholar
- G. Kahn and D. MacQueen. Coroutines and networks of parallel processes. Submitted for publication.Google Scholar
- E. Wiedmer. Fxaktes Rechnen mit reellen Zchlen. Eidgenössiche Technische Hochschule, Zürich. Bericht nr.20, (1976).Google Scholar
- E. A. Ashcroft and W. Wadge. Proving programs without tears. Proc. Symp. on Proving and improving Progams, IRIA, Rocquencourt, Huet and Kahn Ed., (1975).Google Scholar
- Ph. Jorrands. Contributions au developpement des langages extensible. Thèse d'Etat, Université Scientifique et Médicale de Grenoble, (1975).Google Scholar
- S. A. Schuman. On generic functions. In New Directions in Algorithmic Languages 75 (ed.S.A. Schuman) IRIA, (1976).Google Scholar
- R. Burstall and J. Darlington. Some transformations for developping recursive programs. Proc. of Internat. Conf. on Reliable Software, Los Angeles, Cal., (1975). Google ScholarDigital Library
- H. P. Barendregt. Some extensional term models for combinatory logics and λ-calculi. Ph.D. thesis, University of Utrecht, (1971).Google Scholar
- J. M. Cadiou. Recursive definitions of partial functions and their computations. Ph.D. thesis, Stanford Un., (1972). Google ScholarDigital Library
- R. Bird. On transformations of programs. J. Comput. System Sci., 8, 22-35, (1974).Google ScholarDigital Library
- B. Lang. Transformations Schematiques. Thèse 3e cycle, Université Paris VII, Paris, (to appear).Google Scholar
- Threshold evaluation and the semantics of call by value, assignment and generic procedures
Recommendations
Generic Executable Semantics for D-Clean
D-Clean primitives are first class citizens which allows the coordination of a dynamical work distributions over a cluster. The computations are distributed automatically over the Grid by the middleware system. The programmer controls the computation ...
Comments