Type-directed partial evaluation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Type-directed partial evaluation

Full text

Pdf (1.59 MB)

Source

Annual Symposium on Principles of Programming Languages archive
Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages table of contents

St. Petersburg Beach, Florida, United States

Pages: 242 - 257

Year of Publication: 1996

ISBN:0-89791-769-3

Author

Olivier Danvy

Computer Science Department, Aarhus University, Ny Munkegade, Building 540, DK-8000 Aarhus C, Denmark

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 41, Citation Count: 33

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/237721.237784 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Thorsten Altenkirch, Martin Hofmann, and Thomas Streicher. Categorical reconstruction of a reduction free reduction proof. In Peter Dybjer and Randy Pollack, editors, Informal Proceedings of the Joint CLICS- TYPES Workshop on Categomes and Type Theory, Ggteborg, Sweden, May 1995. Report 85, Programming Methodology Group, Chalmers University and the University of GSteborg.
	2	Henk Barendregt. The Lambda Calculus Its Syntax and Semantics. North-Holland, 1984.
	3	Ulrich Berger and Helmut Schwichtenberg. An inverse of the evaluation functional for typed )#-calculus. In Proceedings of the S#xth Annual IEEE Symposium on Logic in Computer Science, pages 203-2tl, Amsterdam, The Netherlands, July 1991. IEEE Computer Society Press.
	4	Lars Birkedal and Morten Welinder. Partial evaluation of Standard ML. Master's thesis, D1KU, Computer Science Department, University of Copenhagen, August 1993. DIKU report 93/22.
	5	Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, February 1994
	6	Anders Bondorf. Self-Applicable Partial Evaluation. PhD thesis, DtKU, Computer Science Department, University of Copenhagen, Copenhagen, Denmark, 1990. DIKU Report 90-17.
	7	Anders Bondorf, Improving binding times without explicit CPS-conversion, ACM SIGPLAN Lisp Pointers, v.V n.1, p.1-10, Jan. 1992
	8	Anders Bondorf , Olivier Danvy, Automatic autoprojection of recursive equations with global variable and abstract data types, Science of Computer Programming, v.16 n.2, p.151-195, Sept. 1991 [doi>10.1016/0167-6423(91)90002-F]
	9	Anders Bondorf and Jesper Jorgensen. Efficient analyses for realistic off-line partial evaluation. Journal of Functional Programming, 3(3):315-346, 1993.
	10	H. Abelson , R. K. Dybvig , C. T. Haynes , G. J. Rozas , N. I. Adams, IV , D. P. Friedman , E. Kohlbecker , G. L. Steele, Jr. , D. H. Bartley , R. Halstead , D. Oxley , G. J. Sussman , G. Brooks , C. Hanson , K. M. Pitman , M. Wand , William Clinger , Jonathan Rees, Revised report on the algorithmic language scheme, ACM SIGPLAN Lisp Pointers, v.IV n.3, p.1-55, July, 1991 [doi>10.1145/382130.382133]
	11	Charles Consel. Analyse de Programmes, Evaluation Partielle et Gdndrat#on de Comp#lateurs. PhD thesis, Universit# Pierre et Marie Curie (Paris VI), Paris, France, June 1989.
	12	Charles Consel, Polyvariant binding-time analysis for applicative languages, Proceedings of the 1993 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.66-77, June 14-16, 1993, Copenhagen, Denmark [doi>10.1145/154630.154638]
	13	C. Consel , O. Danvy, From interpreting to compiling binding times, Proceedings of the third European symposium on programming on ESOP '90, p.88-105, May 1990, Copenhagen, Denmark
	14	Charles Consel , Olivier Danvy, Static and dynamic semantics processing, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.14-24, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99588]
	15	Charles Consel , Olivier Danvy, Tutorial notes on partial evaluation, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.493-501, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158707]
	16	Olivier Danvy , Andrzej Filinski, Abstracting control, Proceedings of the 1990 ACM conference on LISP and functional programming, p.151-160, June 27-29, 1990, Nice, France [doi>10.1145/91556.91622]
	17	Olivier Danvy and Andrzej Filinski. Representing control, a study of the CPS transformation. Mathematical Structures in Computer Science, 2(4):361-391, December 1992.
	18	Olivier Danvy , Karoline Malmkjær , Jens Palsberg, The essence of eta-expansion in partial evaluation, Lisp and Symbolic Computation, v.8 n.3, p.209-227, Sept. 1995 [doi>10.1007/BF01019004]
	19	Olivier Danvy, Karoline Malmkjaer, and Jens Palsberg. Eta-expansion does The Trick. Technical report BRICS RS-95-41, DAIMI, Computer Science Department, Aarhus University, Aarhus, Denmark, August 1995.
	20	Rowan Davies , Frank Pfenning, A modal analysis of staged computation, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.258-270, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237788]
	21	M. Felleisen, The theory and practice of first-class prompts, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.180-190, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73576]
	22	Andrzej Filinski, Representing monads, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.446-457, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.178047]
	23	Andrzej FiIinski. Controlling Effects. PhD thesis, School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania, 1995.
	24	Daniel P. Friedman , Christopher T. Haynes , Mitchell Wand, Essentials of programming languages, MIT Press, Cambridge, MA, 1992
	25	Yoshihito Futamura. Partial evaluation of computation process - an approach to a compiler-compiler. Systems, Computers, Controls 2, 5, pages 45-50, 1971.
	26	Robert Glück , Jesper Jørgensen, Efficient Multi-level Generating Extensions for Program Specialization, Proceedings of the 7th International Symposium on Programming Languages: Implementations, Logics and Programs, p.259-278, September 20-22, 1995
	27	Mayer Goldberg, Recursive application-survival in the lambda calculus, 1996
	28	John Hatcliff , Olivier Danvy, A generic account of continuation-passing styles, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.458-471, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.178053]
	29	Fritz Henglein, Dynamic typing: syntax and proof theory, Science of Computer Programming, v.22 n.3, p.197-230, June 1994
	30	G#rard Huet. R#solution d'fiquations dans les tangages d'ordre 1, 2, ..., w. Th#se d't#tat, Universit# de Paris VII, Paris, France, 1976.
	31	C. Barry Jay and Neil Ghani. The virtues of eta-expansion. Journal of Functional Programming, 5(3):135- 154, 1995.
	32	Neil D. Jones, editor. Semant, cs-D,rected Compiler Generation, number 94 in Lecture Notes in Computer Science, Aarhus, Denmark, 1980.
	33	Nell D. Jones. Challenging problems in partial evaluation and mixed computation. In Partial Evaluation and M,xed Computation, pages 1-14. North-Holland, 1988.
	34	Neil D. Jones, Mix ten years later, Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.24-38, June 21-23, 1995, La Jolla, California, United States [doi>10.1145/215465.215468]
	35	Neil D. Jones, Carsten K. Gomard, Anders Bondorf, Olivier Danvy, and Torben #. Mogensen. A selfapplicable partial evaluator for the lambda calculus. In K. C. Tai and Alexander L. Wolf, editors, Proceedings of the 1990 IEEE International Conference on Computer Languages, pages 49-58, New Orleans, Louisiana, March 1990.
	36	Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
	37	John Launchbury, Projection factorisations in partial evaluation, Cambridge University Press, New York, NY, 1991
	38	Julia L. Lawall , Olivier Danvy, Continuation-based partial evaluation, ACM SIGPLAN Lisp Pointers, v.VII n.3, p.227-238, July-Sept. 1994
	39	Ralph Loader. Normalisation by translation. Technical report, Computing Laboratory, Oxford University, April 1995.
	40	Karoline Malmkjaer, Nevin Heintze, and Olivier Danvy. ML partial evaluation using set-based analysis. In John Reppy. editor, Record of the 199# A CM SIG- PLAN Workshop on ML and its Apphcat#ons, Rapport de recherche N~ 2265, INR{A, pages 112-119, Orlando, Florida, June 1994. Also appears as Technical report CMU-CS-94-129.
	41	Torben }E. Mogensen. B#nding Time Aspects of Part, al Evatuat,on. PhD thesis, DIKU, Computer Science Department, University of Copenhagen, Copenhagen, Denmark, March 1989.
	42	Eugenio Moggi, Notions of computation and monads, Information and Computation, v.93 n.1, p.55-92, July 1991 [doi>10.1016/0890-5401(91)90052-4]
	43	Peter D. Mosses. SIS -- semantics implementation system, reference manual and user guide. Technical Report MD-30, DAIMI, Computer Science Department, Aarhus University, Aarhus, Denmark, 1979.
	44	Flemming Nielson , Hanne Riis Nielson, Two-level functional languages, Cambridge University Press, New York, NY, 1992
	45	Lawrence Paulson, Compiler generation from denotational semantics, Methods and tools for compiler construction, Cambridge University Press, New York, NY, 1984
	46	Frank Pfenning, Logic programming in the LF logical framework, Logical frameworks, Cambridge University Press, New York, NY, 1991
	47	John C. Reynolds. The essence of Algol. In van Vliet, editor, International Symposium on Algorithmic Languages, pages 345-372, Amsterdam, 1982. North- Holland.
	48	Erik Steven Ruf, Topics in online partial evaluation, Stanford University, Stanford, CA, 1993
	49	Guy L. Steele, Jr., Rabbit: A Compiler for Scheme, Massachusetts Institute of Technology, Cambridge, MA, 1978
	50	Philip Wadler, The essence of functional programming, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-14, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143169]
	51	Daniel Weise , Roland Conybeare , Erik Ruf , Scott Seligman, Automatic online partial evaluation, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.165-191, June 1991, Cambridge, Massachusetts, United States

CITED BY 33

	Olivier Danvy , Nevin Hentze , Karoline Malmkjær, Resource-bounded partial evaluation, ACM Computing Surveys (CSUR), v.28 n.2, p.329-332, June 1996
	Olivier Danvy , Karoline Malmkjær , Jens Palsberg, Eta-expansion does The Trick, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.6, p.730-751, Nov. 1996
	John Hannan , Patrick Hicks, Higher-order arity raising, ACM SIGPLAN Notices, v.34 n.1, p.27-38, Jan. 1999
	Olivier Danvy , Ulrik P. Schultz, Lambda-dropping: transforming recursive equations into programs with block structure, ACM SIGPLAN Notices, v.32 n.12, p.90-106, Dec. 1997
	Zhe Yang, Encoding types in ML-like languages, ACM SIGPLAN Notices, v.34 n.1, p.289-300, Jan. 1999
	Walid Taha , Tim Sheard, Multi-stage programming with explicit annotations, ACM SIGPLAN Notices, v.32 n.12, p.203-217, Dec. 1997
	Eijiro Sumii , Naoki Kobayashi, A Hybrid Approach to Online and Offline Partial Evaluation, Higher-Order and Symbolic Computation, v.14 n.2-3, p.101-142, September 2001
	Tim Sheard, A type-directed, on-line, partial evaluator for a polymorphic language, ACM SIGPLAN Notices, v.32 n.12, p.22-35, Dec. 1997
	Bernd Grobauer , Zhe Yang, The second Futamura projection for type-directed partial evaluation, ACM SIGPLAN Notices, v.34 n.11, p.22-32, Nov. 1999
	Zhong Shao , Christopher League , Stefan Monnier, Implementing typed intermediate languages, ACM SIGPLAN Notices, v.34 n.1, p.313-323, Jan. 1999
	Norman Ramsey , Avi Pfeffer, Stochastic lambda calculus and monads of probability distributions, ACM SIGPLAN Notices, v.37 n.1, p.154-165, Jan. 2002
	Pablo E. Martínez López , John Hughes, Principal type specialisation, Proceedings of the ASIAN symposium on Partial evaluation and semantics-based program manipulation, p.94-105, September 12-14, 2002, Aizu, Japan
	Scott Draves, Implementing bit-addressing with specialization, ACM SIGPLAN Notices, v.32 n.8, p.239-250, Aug. 1997
	Kenichi Asai, Binding-time analysis for both static and dynamic expressions, New Generation Computing, v.20 n.1, p.27-51, January 2002
	Norman Ramsey, Embedding an interpreted language using higher-order functions and types, Proceedings of the 2003 workshop on Interpreters, virtual machines and emulators, p.6-14, June 12-12, 2003, San Diego, California
	Bernd Grobauer , Zhe Yang, The Second Futamura Projection for Type-Directed Partial Evaluation, Higher-Order and Symbolic Computation, v.14 n.2-3, p.173-219, September 2001
	Benjamin Grégoire , Xavier Leroy, A compiled implementation of strong reduction, ACM SIGPLAN Notices, v.37 n.9, p.235-246, September 2002
	Vincent Balat , Roberto Di Cosmo , Marcelo Fiore, Extensional normalisation and type-directed partial evaluation for typed lambda calculus with sums, ACM SIGPLAN Notices, v.39 n.1, p.64-76, January 2004
	Michael Sperber , Peter Thiemann, Two for the price of one: composing partial evaluation and compilation, ACM SIGPLAN Notices, v.32 n.5, p.215-225, May 1997
	Cristiano Calcagno, Two-level languages for program optimization, Theoretical Computer Science, v.315 n.1, p.61-81, 5 May 2004
	Zhe Yang, Encoding types in ML-like languages, Theoretical Computer Science, v.315 n.1, p.151-190, 5 May 2004
	Bruno C. d. S. Oliveira , Jeremy Gibbons, TypeCase: a design pattern for type-indexed functions, Proceedings of the 2005 ACM SIGPLAN workshop on Haskell, p.98-109, September 30-30, 2005, Tallinn, Estonia
	Ik-Soon Kim , Kwangkeun Yi , Cristiano Calcagno, A polymorphic modal type system for lisp-like multi-staged languages, ACM SIGPLAN Notices, v.41 n.1, p.257-268, January 2006
	Yukiyoshi Kameyama, Axioms for control operators in the CPS hierarchy, Higher-Order and Symbolic Computation, v.20 n.4, p.339-369, December 2007
	Chung-Chieh Shan, A static simulation of dynamic delimited control, Higher-Order and Symbolic Computation, v.20 n.4, p.371-401, December 2007
	Oleg Kiselyov , Chung-chieh Shan , Amr Sabry, Delimited dynamic binding, ACM SIGPLAN Notices, v.41 n.9, September 2006
	Vincent Balat, Ocsigen: typing web interaction with objective Caml, Proceedings of the 2006 workshop on ML, September 16-16, 2006, Portland, Oregon, USA
	Nick Benton, Embedded interpreters, Journal of Functional Programming, v.15 n.4, p.503-542, July 2005
	Arun Chauhan , Cheryl McCosh , Ken Kennedy , Richard Hanson, Automatic Type-Driven Library Generation for Telescoping Languages, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.51, November 15-21, 2003
	John Hatcliff , Olivier Danvy, A computational formalization for partial evaluation, Mathematical Structures in Computer Science, v.7 n.5, p.507-541, October 1997
	Peter Thiemann, Program specialization for execution monitoring, Journal of Functional Programming, v.13 n.3, p.573-600, May 2003
	Stefan Monnier , Zhong Shao, Inlining as staged computation, Journal of Functional Programming, v.13 n.3, p.647-676, May 2003
	Sam Lindley, Many holes in hindley-milner, Proceedings of the 2008 ACM SIGPLAN workshop on ML, September 21-21, 2008, Victoria, BC, Canada