Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

On Jones-Optimal Specialization for Strongly Typed Languages

Henning MakholmContact Information

(5)  DIKU, University of Copenhagen, Universitetsparken 1, DK-2100 København Ø, Denmark
Abstract
The phrase “optimal program specialization” was defined by Jones et al. in 1993 to capture the idea of a specializer being strong enough to remove entire layers of interpretation. As it has become clear that it does not imply “optimality” in the everyday meaning of the word, we propose to rename the concept “jones-optimality”. We argue that the 1993 definition of Jones-optimality is in principle impossible to fulfil for strongly typed languages due to necessary encodings on the inputs and outputs of a well-typed self-interpreter. We propose a technical correction of the definition which allows Jones-optimality to remain a meaningful concept for typed languages. We extend recent work by Hughes and by Taha and Makholm on the long-unsolved problem of Jones-optimal specialization for strongly typed languages. The methods of Taha and Makholm are enhanced to allow “almost optimal” results when a self-interpreter is specialized to a typeincorrect program; how to do this has been an open problem since 1987. Neither Hughes’ nor Taha—Makholm’s methods are by themselves suffi- cient for Jones-optimal specialization when the language contains primitive operations that produce or consume complex data types. A simple postprocess is proposed to solve the problem. An implementation of the proposed techniques has been produced and used for the first successful practical experiments with truly Jones-optimal specialization for strongly typed languages.
Supported in part by the Danish National Science Research Council via project PLT (Programming Language Technology)

Contact Information Henning Makholm
Email: henning@makholm.net
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Referenced by
3 newer articles

  1. CARETTE, JACQUES (2009) Finally tagless, partially evaluated: Tagless staged interpreters for simpler typed languages. Journal of Functional Programming
    [CrossRef]
  2. Glück, Robert (2008) An investigation of Jones optimality and BTI-universal specializers. Higher-Order and Symbolic Computation
    [CrossRef]
  3. Barker, Steve (2008) Efficient and flexible access control via Jones-optimal logic program specialisation. Higher-Order and Symbolic Computation 21(1-2)
    [CrossRef]
Remote Address: 38.107.191.107 • Server: mpweb18
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)