The Genesis of Mix: Early Days of Self-Applicable Partial Evaluation (Invited Contribution)
Pages 1 - 13
Abstract
Forty years ago development started on Mix, a partial evaluator designed specifically for the purpose of self-application. The effort, led by Neil D. Jones at the University of Copenhagen, eventually demonstrated that non-trivial compilers could be generated automatically by applying a partial evaluator to itself. The possibility, in theory, of such self-application had been known for more than a decade, but remained unrealized by the start of 1984. We describe the genesis of Mix, including the research environment, the challenges, and the main insights that led to success. We emphasize the critical role played by program annotation as a pre-processing step, later automated in the form of binding-time analysis.
References
[1]
L. O. Andersen. 1993. Binding-Time Analysis and the Taming of C Pointers. In Partial Evaluation and Semantics-Based Program Manipulation, Copenhagen, Denmark, June 1993. ACM Publ., 47–58. https://doi.org/10.1145/154630.154636
[2]
Lennart Beckman, Anders Haraldson, Östen Oskarsson, and Erik Sandewal. 1976. A Partial Evaluator, and Its Use as a Programming Tool. Artificial Intelligence, 7, 4 (1976), 319–357. https://doi.org/10.1016/0004-3702(76)90011-4
[3]
1988. Partial Evaluation and Mixed Computation. Proceedings of the IFIP TC2 Workshop, Gammel Avernæ s, Denmark, October 1987, D. Bjørner, A. P. Ershov, and N. D. Jones (Eds.). North-Holland.
[4]
Corrado Böhm. 1954. Calculatrices digitales. Du déchiffrage de formules logico-mathématiques par la machine même dans la conception du programme. Annali di Matematica Pura ed Applicata, 37 (1954), 175–217. English translation at https://www.itu.dk/people/sestoft/boehmthesis/
[5]
A. Bondorf. 1991. Automatic Autoprojection of Higher Order Recursive Equations. Science of Computer Programming, 17 (1991), 3–34. https://doi.org/10.1016/0167-6423(91)90035-v
[6]
A. Bondorf and O. Danvy. 1991. Automatic Autoprojection of Recursive Equations with Global Variables and Abstract Data Types. Science of Computer Programming, 16 (1991), 151–195. https://doi.org/10.1016/0167-6423(91)90002-f
[7]
M. A. Bulyonkov. 1984. Polyvariant Mixed Computation for Analyzer Programs. Acta Informatica, 21, 5 (1984), 473–484. https://doi.org/10.1007/bf00271642
[8]
Martin Davis. 2012. The Universal Computer: The Road from Leibniz to Turing. CRS Press. https://doi.org/10.1201/b11441
[9]
2023. Obituary for professor emeritus Neil Jones. https://di.ku.dk/english/news/2023/obituary-for-professor-emeritus-at-diku-neil-jones/ 13 April 2023.
[10]
Hans Dybkjæ r. 1985. Parsers and Partial Evaluation: An Experiment. DIKU Student Project Report 85-7-15.
[11]
Pär Emanuelson and Anders Haraldsson. 1980. On Compiling Embedded Languages in Lisp. In 1980 Lisp Conf. ACM Publ., 208–215. https://doi.org/10.1145/800087.802808
[12]
A. Ershov. 1980. About Futamura’s Projections. Bit (Japan), 12, 14 (1980), 4–5. (In Japanese).
[13]
A. P. Ershov. 1978. On the Essence of Compilation. In Formal Description of Programming Concepts, E. J. Neuhold (Ed.). North-Holland, 391–418.
[14]
A. P. Ershov. 1982. Mixed Computation: Potential Applications and Problems for Study. Theoretical Computer Science, 18 (1982), 41–67. https://doi.org/10.1016/0304-3975(82)90111-6
[15]
Yoshihiko Futamura. 1971. Partial Evaluation of Computation Process—An Approach to a Compiler-Compiler. Systems, Computers, Controls, 2, 5 (1971), 45–50.
[16]
Yoshihiko Futamura. 1999. Partial Evaluation of Computation Process, Revisited. Higher-Order and Symbolic Computation, 12 (1999), 377–380. Question/answer style background information about Futamura’s early work.
[17]
1986. Programs as Data Objects. Copenhagen, Denmark, October 1985, Harald Ganzinger and Neil D. Jones (Eds.) (LNCS, Vol. 217). https://doi.org/10.1007/3-540-16446-4
[18]
C. K. Gomard. 1992. A Self-Applicable Partial Evaluator for the Lambda Calculus: Correctness and Pragmatics. ACM Transactions on Programming Languages and Systems, 14, 2 (1992), April, 147–172. https://doi.org/10.1145/128861.128864
[19]
Anders Haraldsson. 1977. A Program Manipulation System Based on Partial Evaluation. Ph.D. Dissertation. Linköping University, Sweden. Linköping Studies in Science and Technology Dissertations 14.
[20]
Anders Haraldsson. 1978. A Partial Evaluator, and Its Use for Compiling Iterative Statements in Lisp. In Proceedings of the Fifth ACM Symposium on Principles of Programming Languages. ACM, 195–202. https://doi.org/10.1145/512760.512781
[21]
T. Hart and M. Levin. 1962. Memo 39—The New Compiler. MIT Computation Center memo.
[22]
Neil D. Jones. 1984. Datalogi 2 Notes: Functions, Expressions, Programming Languages, Computability. DIKU, University of Copenhagen. https://di.ku.dk/forskning/Publikationer/tekniske_rapporter/1980-1984/Jones_Dat2Notes_1984.pdf
[23]
Neil D. Jones, Carsten K. Gomard, and Peter Sestoft. 1993. Partial Evaluation and Automatic Program Generation. Prentice-Hall. https://www.itu.dk/people/sestoft/pebook/
[24]
Neil D. Jones, Peter Sestoft, and Harald Søndergaard. 1985. An Experiment in Partial Evaluation: The Generation of a Compiler Generator. In Rewriting Techniques and Applications, J.-P. Jouannaud (Ed.) (LNCS, Vol. 202). Springer-Verlag, 124–140. https://doi.org/10.1007/3-540-15976-2_6
[25]
Neil D. Jones, Peter Sestoft, and Harald Søndergaard. 1985. An Experiment in Partial Evaluation: The Generation of a Compiler Generator. DIKU, The University of Copenhagen.
[26]
Neil D. Jones, Peter Sestoft, and Harald Søndergaard. 1989. Mix: A Self-Applicable Partial Evaluator for Experiments in Compiler Generation. Lisp and Symbolic Computation, 2, 1 (1989), 9–50. https://doi.org/10.1007/BF01806312
[27]
S. C. Kleene. 1938. On Notation for Ordinal Numbers. Journal of Symbolic Logic, 3, 4 (1938), dec, 150–155. https://doi.org/10.2307/2267778
[28]
L. A. Lombardi. 1967. Incremental Computation. In Advances in Computers, F. L. Alt and M. Rubinoff (Eds.). 8, Academic Press, 247–333.
[29]
L. A. Lombardi and B. Raphael. 1964. Lisp as the Language for an Incremental Computer. In The Programming Language Lisp: Its Operation and Applications, E. C. Berkeley and D. G. Bobrow (Eds.). MIT Press, 204–219.
[30]
Torben Mogensen. 1986. The Application of Partial Evaluation to Ray-Tracing. Master’s thesis. DIKU. University of Copenhagen, Denmark.
[31]
Torben Mogensen. 1988. Partially Static Structures in a Self-Applicable Partial Evaluator. In Partial Evaluation and Mixed Computation, D. Bjørner, A. P. Ershov, and N. D. Jones (Eds.). North-Holland, 325–347.
[32]
T. Mogensen and A. Bondorf. 1993. Logimix: A Self-Applicable Partial Evaluator for Prolog. In Logic Program Synthesis and Transformation: Proceedings of LOPSTR 92, K.-K. Lau and T. Clement (Eds.). Springer-Verlag, 214–227. https://doi.org/10.1007/978-1-4471-3560-9_15
[33]
Peter Naur. 1970. Project Activity in Computer Science Education. Consiglio Nazionale delle Richerche, I. E. I., Pisa, Italy. 13 pages.
[34]
Politiken. 1971. Institutbestyrer studerer. 19 October 1971 issue, page 18.
[35]
Peter Sestoft. 1985. The Structure of a Self-Applicable Partial Evaluator. DIKU, The University of Copenhagen. https://di.ku.dk/forskning/Publikationer/tekniske_rapporter/1985-1989/Sestoft-DIKU-report-85-11.pdf
[36]
Peter Sestoft. 1986. The Structure of a Self-Applicable Partial Evaluator. In Programs as Data Objects, H. Ganzinger and N. D. Jones (Eds.) (LNCS, Vol. 217). Springer-Verlag, 236–256. https://doi.org/10.1007/3-540-16446-4_14
[37]
Peter Sestoft. 1987. Mix Takes Three Arguments. Handwritten note, 6 pages, 4 November 1987.
[38]
Peter Sestoft. 1988. Automatic Call Unfolding in a Partial Evaluator. In Partial Evaluation and Mixed Computation, D. Bjørner, A. P. Ershov, and N. D. Jones (Eds.). North-Holland, 485–506.
[39]
Peter Sestoft and Alexander V. Zamulin. 1988. Annotated Bibliography on Partial Evaluation and Mixed Computation. New Generation Computing, 6, 2, 3 (1988), 309–354. https://doi.org/10.1007/bf03037145 Bibtex file at
[40]
Harald Søndergaard. 1984. A Primitive Autoprojector for a Simple Applicative Language. DIKU Student Project Report 84-2-4, 83 pages.
[41]
1977. Basic Refal and Its Implementation on Computers, Valentin F. Turchin (Ed.). Moscow: GOSSTROI SSSR, TsNIPIASS. (In Russian).
[42]
A. M. Turing. 1936. On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42 (1936), 230–265. https://doi.org/10.1112/plms/s2-42.1.230
[43]
[n.d.]. UCPH Department of Computer Science. https://en.wikipedia.org/wiki/UCPH_Department_of_Computer_Science Accessed 17 November 2023.
Index Terms
- The Genesis of Mix: Early Days of Self-Applicable Partial Evaluation (Invited Contribution)
Index terms have been assigned to the content through auto-classification.
Recommendations
A self-applicable partial evaluator for the lambda calculus: correctness and pragmatics
We describe theoretical and a few practical aspects of an implemented self-applicable partial evaluator for the untyped lambda calculus with constants, conditionals, and a fixed point operator.
The purpose of this paper is first to announce the existence ...
The Second Futamura Projection for Type-Directed Partial Evaluation
A generating extension of a program specializes the program with respect to part of the input. Applying a partial evaluator to the program trivially yields a generating extension, but specializing the partial evaluator with respect to the program often ...
A self-applicable online partial evaluator for recursive flowchart languages
This paper describes a self-applicable online partial evaluator for a flowchart language with recursive calls. Self-application of the partial evaluator yields generating extensions that are as efficient as those reported in the literature for offline ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2024 Copyright held by the owner/author(s).
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s).
Sponsors
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 11 January 2024
Check for updates
Author Tags
Qualifiers
- Invited-talk
Conference
PEPM '24
Sponsor:
PEPM '24: 2024 ACM SIGPLAN International Workshop on Partial Evaluation and Program Manipulation
January 16, 2024
London, UK
Acceptance Rates
Overall Acceptance Rate 66 of 120 submissions, 55%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 49Total Downloads
- Downloads (Last 12 months)49
- Downloads (Last 6 weeks)3
Reflects downloads up to 24 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in