mixed compilation -> partial evaluation

In article 92-01-131 I wrote:
>Does anyone have any references for A.P.Ershov's work in the late 60's or
>early 70's on "mixed compilation", or on any modern work ...


The general response is: the "mixed compilation" work to which I was
referring is now called "partial evaluation", and can be found in the
functional programming literature for the most part. Thanks also to
ressler@cs.cornell.edu (Gene Ressler), Ralph Johnson
<johnson@cs.uiuc.edu>, and jvitek@csr.UVic.CA (Jan Vitek).


------------------------------------------------------------------------------
Organization: School of Computer Science, Carnegie Mellon
Date: Fri, 31 Jan 92 17:14:28 EST
Reply-To: mleone@REYNARD.FOX.CS.CMU.EDU


These days its called "partial evaluation", and it's become a "hot"
research topic in the last two or three years. In fact there was recently
an entire conference devoted to it: the Symposium on Partial Evaluation
and Semantics-Based Program Manipulation (PEPM). The proceedings were
published by the ACM.


Mark Leone <mleone@cs.cmu.edu>
Computer Science, Carnegie Mellon University
Pittsburgh, PA 15213 USA




------------------------------------------------------------------------------
Date: Fri, 31 Jan 92 14:22:43 PST
Reply-To: nigelh@csr.UVic.CA (R. Nigel Horspool)


Nowadays, this is called ``partial evaluation''.


It's mostly used by the functional programming crowd and people (e.g.
Niel Jones' group in Denmark) have been building compilers based on it.
(The key to that trick is to ``partially evaluate'' an interpreter given
that you know what the interpreter's input is.)


Try looking through POPL and Springer-Verlag LNCS and you will come across
lots of mentions of partial evaluation. It is closely related to abstract
interpretation and denotational semantics by the way.


------------------------------------------------------------------------------
Date: Fri, 31 Jan 92 14:28:06 -0800
Reply-To: pattis@cs.washington.edu (Richard Pattis)
Organization: Computer Science & Engineering, U. of Washington, Seattle


You might check out "abstract interpretation" which I think includes the
kind of stuff you are looking for. There is a book edited by Abramsky and
Hankin: Abstract Interpretation of Declarative Programs. It includes
hundreds of bibliographic entries, but none for Ershov.


I have two books by Ershov; The first is A.P. Ershov: The British Lectures
published by Heyden. On page 52 he talks about mixed computation and the
example you mention, although that section is not long (it is lecture 4,
17 pages). His other book, Origins of Programming, published by
Springer_Verlag does not mention those terms.


------------------------------------------------------------------------------
Reply-To: Anurag Acharya <acha@DRAVIDO.SOAR.CS.CMU.EDU>
Date: Fri, 31 Jan 92 19:18:48 EST


This is currently called partial evaluation. There has been quite a bit of
work - two powerful systems are currently available -- Schism from Yale
(an almost complete Scheme partial evaluator) and a system from DIKU
copenhagen whose name escapes me at the moment. Some of the active
researchers are Neil Jones (DIKU copenhagen), charles consel (yale), Peter
Sestoft (DIKU). Peter Sestoft has an online bib for this, send him mail at
sestoft@diku.dk. or let me know (I have an old copy).


------------------------------------------------------------------------------
Date: Fri, 31 Jan 92 16:32:29 -0500
Reply-To: William Pippin <pippin@cis.ohio-state.edu>
Organization: The Ohio State University, Department of Computer and Information Science


Mixed programming is also sometimes referred to as partial evaluation, and
G.L. Burn has done recent work in this area. I've provided references to
some of his papers.


@article{BURN91b,
author = "G.L. Burn",
title = "Implementing the Evaluation Transformer Model of Reduction on
Parallel Machines",
journal = "Journal of Functional Programming",
volume = "2",
number = 1,
year = 1991,
note = "To appear. Also appears as Department of Computing Report Number
90/24, Imperial College, LONDON SW7 2BZ."
}


@inproceedings{BURN91c,
author = "G.L. Burn",
title = "The Evaluation Transformer Model of Reduction and Its Correctness",
booktitle = "Proceedings of {TAPSOFT}'91, Volume 2",
editor = "S. Abramsky and T.S.E. Maibaum",
publisher = "Springer-Verlag LNCS 494",
address = "Brighton, {UK}",
month = "8--12 April",
year = 1991,
pages = "458--482"
}




\bibitem[Aug87]{AUGUSTSSON87a}
L.~Augustsson.
\newblock {\em Compiling Lazy Functional Languages, Part II}.
\newblock PhD thesis, Chalmers Tekniska H\"{o}gskola, G\"{o}teborg, Sweden,
    1987.


\bibitem[Bar84]{BARENDREGT84a}
H.P. Barendregt.
\newblock {\em The Lambda Calculus}, volume 103 of {\em Studies in Logic and
    the Foundations of Mathematics}.
\newblock Elsevier Science Publishers B.V., P.O. Box 1991, 1000 BZ Amsterdam,
    The Netherlands, 2nd edition, 1984.


\bibitem[Bar91]{BARENDREGT91a}
H.P. Barendregt.
\newblock Lambda calculi with types.
\newblock In S.~Abramsky, D.M. Gabbai, and T.S.E. Maibaum, editors, {\em
    Handbook of Logic in Computer Science}, volume~2. Oxford University Press,
    1991.
\newblock To appear.


\bibitem[BW88]{BIRD88a}
R.~Bird and P.L. Wadler.
\newblock {\em An Introduction to Functional Programming}.
\newblock Prentice-Hall Series in Computer Science. Prentice-Hall International
    (UK) Ltd., Hemel Hempstead, Hertfordshire, England, 1988.


\bibitem[FH88]{FIELD88a}
A.J. Field and P.G. Harrison.
\newblock {\em Functional Programming}.
\newblock Addison-Wesley International Computer Science Series, 1988.


\bibitem[Gor88]{GORDON88a}
M.J.C. Gordon.
\newblock {\em Programming Language Theory and Its Implementation: Applicative
    and Imperative Paradigms}.
\newblock Prentice-Hall International Series in Computer Science, 1988.
\newblock ISBN 0-13-730417-X.


\bibitem[GS90]{GUNTER90a}
G.A. Gunter and D.S. Scott.
\newblock Semantic domains.
\newblock In J.~van Leeuwen, editor, {\em Handbook of Theoretical Computer
    Science}, volume B: Formal Models and Semantics. North-Holland, 1990.


\bibitem[HMT88]{HARPER88a}
R.~Harper, R.~Milner, and M.~Tofte.
\newblock The definition of standard {ML} (version 2).
\newblock Technical Report {ECS-LFCS}-88-62, LFCS, Department of Computer
    Science, University of Edinburgh, The King's Buildings, Edinburgh EH9 3JZ,
    UK, August 1988.


\bibitem[HWe90]{HUDAK90a}
P.~Hudak and P.~Wadler~(editors).
\newblock Report on the programming language {H}askell, a non-strict purely
    functional language ({V}ersion 1.0).
\newblock Technical Report YALEU/DCS/RR777, Yale University, Department of
    Computer Science, April 1990.


\bibitem[Mos90]{MOSSES90a}
P.D. Mosses.
\newblock Denotational semantics.
\newblock In J.~van Leeuwen, editor, {\em Handbook of Theoretical Computer
    Science}, volume B: Formal Models and Semantics. North-Holland, 1990.


\bibitem[MTH90]{MILNER90a}
R.~Milner, M.~Tofte, and R.~Harper.
\newblock {\em The Definition of Standard ML}.
\newblock {MIT} {P}ress, Cambridge, {M}ass., 1990.


\bibitem[Per87]{PERRY87a}
N.~Perry.
\newblock Hope+.
\newblock Technical Report IC/FPR/LANG/2.5.1/7, Functional Programming Section,
    Department of Computing, Imperial College, 180 Queen's Gate, LONDON SW7\ 2BZ,
    UK, 1987.


\bibitem[{Pey}87]{PEYTON-JONES87a}
S.L. {Peyton Jones}.
\newblock {\em The Implementation of Functional Programming Languages}.
\newblock Prentice-Hall International Series in Computer Science. Prentice-Hall
    International (UK) Ltd, London, 1987.


\bibitem[Rea89]{READE89a}
C.~Reade.
\newblock {\em Elements of Functional Programming}.
\newblock International Computer Science Series. Addison-Wesley, 1989.


\bibitem[Sch86]{SCHMIDT86a}
D.A. Schmidt.
\newblock {\em Denotational Semantics}.
\newblock Allyn and Bacon, Inc., 7 Wells Avenue, Newton, Massachusetts, 1986.


\bibitem[Sto77]{STOY77a}
J.E. Stoy.
\newblock {\em Denotational Semantics: The Scott-Strachey Approach to
    Programming Language Theory}.
\newblock The MIT Press Series in Computer Science. MIT Press, Cambridge,
    Massachusetts, 1977.


\bibitem[Tur85]{TURNER85a}
D.A. Turner.
\newblock Miranda: A non-strict functional language with polymorphic types.
\newblock In {J.-P.} Jouannaud, editor, {\em Proceedings of the Functional
    Programming Languages and Computer Architecture Conference}, pages 1--16.
    Springer-Verlag LNCS 201, September 1985.


\bibitem[Tur86]{TURNER86a}
D.A. Turner.
\newblock An overview of {M}iranda.
\newblock {\em SIGPLAN Notices}, December 1986.


\bibitem[Wik87]{WIKSTROM87a}
A.~Wikstr\"{o}m.
\newblock {\em Functional Programming Using Standard {ML}}.
\newblock Prentice-Hall International Series in Computer Science, Hemel
    Hempstead, UK, 1987.
--

Return to the comp.compilers page.
Search the comp.compilers archives again.