The Translation Power of the Futamura Projections View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2004

AUTHORS

Robert Glück

ABSTRACT

Despite practical successes with the Futamura projections, it has been an open question whether target programs produced by specializing interpreters can always be as efficient as those produced by a translator. We show that, given a Jones-optimal program specializer with static expression reduction, there exists for every translator an interpreter which, when specialized, can produce target programs that are at least as fast as those produced by the translator. This is not the case if the specializer is not Jones-optimal. We also examine Ershov’s generating extensions, give a parameterized notion of Jones optimality, and show that there is a class of specializers that can always produce residual programs that match the size and time complexity of programs generated by an arbitrary generating extension. This is the class of generation universal specializers. We study these questions on an abstract level, independently of any particular specialization method. More... »

PAGES

133-147

References to SciGraph publications

  • 2001-06-01. On Jones-Optimal Specialization for Strongly Typed Languages in SEMANTICS, APPLICATIONS, AND IMPLEMENTATION OF PROGRAM GENERATION
  • 1996. ML pattern match compilation and partial evaluation in PARTIAL EVALUATION
  • 2003-02-28. Tagging, Encoding, and Jones Optimality in PROGRAMMING LANGUAGES AND SYSTEMS
  • 1996. Evolution of partial evaluators: Removing inherited limits in PARTIAL EVALUATION
  • 2000-11-24. Combining Semantics with Non-standard Interpreter Hierarchies in FST TCS 2000: FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE
  • 1990. Partial evaluation, self-application and types in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1986. The structure of a self-applicable partial evaluator in PROGRAMS AS DATA OBJECTS
  • 2001. Tag Elimination and Jones-Optimality in PROGRAMS AS DATA OBJECTS
  • 1994. Generating transformers for deforestation and supercompilation in STATIC ANALYSIS
  • Book

    TITLE

    Perspectives of System Informatics

    ISBN

    978-3-540-20813-6
    978-3-540-39866-0

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-540-39866-0_16

    DOI

    http://dx.doi.org/10.1007/978-3-540-39866-0_16

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1048960688


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Numerical and Computational Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Waseda University", 
              "id": "https://www.grid.ac/institutes/grid.5290.e", 
              "name": [
                "PRESTO, JST & Institute for Software Production Technology, Waseda University, School of Science and Engineering, 169-8555, Tokyo, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Gl\u00fcck", 
            "givenName": "Robert", 
            "id": "sg:person.010754010217.31", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010754010217.31"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-16446-4_14", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000053549", 
              "https://doi.org/10.1007/3-540-16446-4_14"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0020-0190(97)00055-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000980817"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/568173.568175", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001092670"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-58485-4_57", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007111166", 
              "https://doi.org/10.1007/3-540-58485-4_57"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/568173.568177", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009624065"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45350-4_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012278693", 
              "https://doi.org/10.1007/3-540-45350-4_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45350-4_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012278693", 
              "https://doi.org/10.1007/3-540-45350-4_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(77)90078-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016252608"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0032064", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028626654", 
              "https://doi.org/10.1007/bfb0032064"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-44978-7_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031192844", 
              "https://doi.org/10.1007/3-540-44978-7_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-36575-3_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033644800", 
              "https://doi.org/10.1007/3-540-36575-3_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-36575-3_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033644800", 
              "https://doi.org/10.1007/3-540-36575-3_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-61580-6_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036259674", 
              "https://doi.org/10.1007/3-540-61580-6_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/s0956796800001167", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038404271"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(86)90173-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038643339"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(86)90173-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038643339"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/99370.99372", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039267274"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-44450-5_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040007835", 
              "https://doi.org/10.1007/3-540-44450-5_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-44450-5_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040007835", 
              "https://doi.org/10.1007/3-540-44450-5_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/143165.143220", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051821774"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-61580-6_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053155927", 
              "https://doi.org/10.1007/3-540-61580-6_22"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2004", 
        "datePublishedReg": "2004-01-01", 
        "description": "Despite practical successes with the Futamura projections, it has been an open question whether target programs produced by specializing interpreters can always be as efficient as those produced by a translator. We show that, given a Jones-optimal program specializer with static expression reduction, there exists for every translator an interpreter which, when specialized, can produce target programs that are at least as fast as those produced by the translator. This is not the case if the specializer is not Jones-optimal. We also examine Ershov\u2019s generating extensions, give a parameterized notion of Jones optimality, and show that there is a class of specializers that can always produce residual programs that match the size and time complexity of programs generated by an arbitrary generating extension. This is the class of generation universal specializers. We study these questions on an abstract level, independently of any particular specialization method.", 
        "editor": [
          {
            "familyName": "Broy", 
            "givenName": "Manfred", 
            "type": "Person"
          }, 
          {
            "familyName": "Zamulin", 
            "givenName": "Alexandre V.", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-540-39866-0_16", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-20813-6", 
            "978-3-540-39866-0"
          ], 
          "name": "Perspectives of System Informatics", 
          "type": "Book"
        }, 
        "name": "The Translation Power of the Futamura Projections", 
        "pagination": "133-147", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1048960688"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-540-39866-0_16"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "e93db6115360433fc3a604a194c28544304d77a6f5a82a0b01defd2930e8d121"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-540-39866-0_16", 
          "https://app.dimensions.ai/details/publication/pub.1048960688"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T08:25", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000363_0000000363/records_70053_00000002.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-540-39866-0_16"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-39866-0_16'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-39866-0_16'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-39866-0_16'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-39866-0_16'


     

    This table displays all metadata directly associated to this object as RDF triples.

    130 TRIPLES      23 PREDICATES      44 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-540-39866-0_16 schema:about anzsrc-for:01
    2 anzsrc-for:0103
    3 schema:author N1b494ff849ea497eb679c7c3ab28e47b
    4 schema:citation sg:pub.10.1007/3-540-16446-4_14
    5 sg:pub.10.1007/3-540-36575-3_23
    6 sg:pub.10.1007/3-540-44450-5_16
    7 sg:pub.10.1007/3-540-44978-7_15
    8 sg:pub.10.1007/3-540-45350-4_11
    9 sg:pub.10.1007/3-540-58485-4_57
    10 sg:pub.10.1007/3-540-61580-6_15
    11 sg:pub.10.1007/3-540-61580-6_22
    12 sg:pub.10.1007/bfb0032064
    13 https://doi.org/10.1016/0020-0190(77)90078-3
    14 https://doi.org/10.1016/0304-3975(86)90173-8
    15 https://doi.org/10.1016/s0020-0190(97)00055-0
    16 https://doi.org/10.1017/s0956796800001167
    17 https://doi.org/10.1145/143165.143220
    18 https://doi.org/10.1145/568173.568175
    19 https://doi.org/10.1145/568173.568177
    20 https://doi.org/10.1145/99370.99372
    21 schema:datePublished 2004
    22 schema:datePublishedReg 2004-01-01
    23 schema:description Despite practical successes with the Futamura projections, it has been an open question whether target programs produced by specializing interpreters can always be as efficient as those produced by a translator. We show that, given a Jones-optimal program specializer with static expression reduction, there exists for every translator an interpreter which, when specialized, can produce target programs that are at least as fast as those produced by the translator. This is not the case if the specializer is not Jones-optimal. We also examine Ershov’s generating extensions, give a parameterized notion of Jones optimality, and show that there is a class of specializers that can always produce residual programs that match the size and time complexity of programs generated by an arbitrary generating extension. This is the class of generation universal specializers. We study these questions on an abstract level, independently of any particular specialization method.
    24 schema:editor N54cf5fed7bcc43489ff920b726887721
    25 schema:genre chapter
    26 schema:inLanguage en
    27 schema:isAccessibleForFree false
    28 schema:isPartOf N8e62f87ba0ac431d8b51d0b02b5f14cf
    29 schema:name The Translation Power of the Futamura Projections
    30 schema:pagination 133-147
    31 schema:productId N09906be0e0d34e8daf1199f372c54561
    32 N18fe391df28544e095e40a5ee8ad9522
    33 Nb167aa2b474e4272b2b622c2ef01bb1a
    34 schema:publisher N51247ff9500b44e090ff7721a3329fd7
    35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048960688
    36 https://doi.org/10.1007/978-3-540-39866-0_16
    37 schema:sdDatePublished 2019-04-16T08:25
    38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    39 schema:sdPublisher N8e5e6462b2fb422f8038a53afedec4d7
    40 schema:url https://link.springer.com/10.1007%2F978-3-540-39866-0_16
    41 sgo:license sg:explorer/license/
    42 sgo:sdDataset chapters
    43 rdf:type schema:Chapter
    44 N0883466e55164fe783d30e0fb69ac4f0 rdf:first N2dbcdaa02ad8494a8d9d106a476f4343
    45 rdf:rest rdf:nil
    46 N09906be0e0d34e8daf1199f372c54561 schema:name doi
    47 schema:value 10.1007/978-3-540-39866-0_16
    48 rdf:type schema:PropertyValue
    49 N18fe391df28544e095e40a5ee8ad9522 schema:name dimensions_id
    50 schema:value pub.1048960688
    51 rdf:type schema:PropertyValue
    52 N1b494ff849ea497eb679c7c3ab28e47b rdf:first sg:person.010754010217.31
    53 rdf:rest rdf:nil
    54 N2dbcdaa02ad8494a8d9d106a476f4343 schema:familyName Zamulin
    55 schema:givenName Alexandre V.
    56 rdf:type schema:Person
    57 N51247ff9500b44e090ff7721a3329fd7 schema:location Berlin, Heidelberg
    58 schema:name Springer Berlin Heidelberg
    59 rdf:type schema:Organisation
    60 N54cf5fed7bcc43489ff920b726887721 rdf:first Nd298b1ec7a3c45409d1d92818354f36f
    61 rdf:rest N0883466e55164fe783d30e0fb69ac4f0
    62 N8e5e6462b2fb422f8038a53afedec4d7 schema:name Springer Nature - SN SciGraph project
    63 rdf:type schema:Organization
    64 N8e62f87ba0ac431d8b51d0b02b5f14cf schema:isbn 978-3-540-20813-6
    65 978-3-540-39866-0
    66 schema:name Perspectives of System Informatics
    67 rdf:type schema:Book
    68 Nb167aa2b474e4272b2b622c2ef01bb1a schema:name readcube_id
    69 schema:value e93db6115360433fc3a604a194c28544304d77a6f5a82a0b01defd2930e8d121
    70 rdf:type schema:PropertyValue
    71 Nd298b1ec7a3c45409d1d92818354f36f schema:familyName Broy
    72 schema:givenName Manfred
    73 rdf:type schema:Person
    74 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    75 schema:name Mathematical Sciences
    76 rdf:type schema:DefinedTerm
    77 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
    78 schema:name Numerical and Computational Mathematics
    79 rdf:type schema:DefinedTerm
    80 sg:person.010754010217.31 schema:affiliation https://www.grid.ac/institutes/grid.5290.e
    81 schema:familyName Glück
    82 schema:givenName Robert
    83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010754010217.31
    84 rdf:type schema:Person
    85 sg:pub.10.1007/3-540-16446-4_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000053549
    86 https://doi.org/10.1007/3-540-16446-4_14
    87 rdf:type schema:CreativeWork
    88 sg:pub.10.1007/3-540-36575-3_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033644800
    89 https://doi.org/10.1007/3-540-36575-3_23
    90 rdf:type schema:CreativeWork
    91 sg:pub.10.1007/3-540-44450-5_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040007835
    92 https://doi.org/10.1007/3-540-44450-5_16
    93 rdf:type schema:CreativeWork
    94 sg:pub.10.1007/3-540-44978-7_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031192844
    95 https://doi.org/10.1007/3-540-44978-7_15
    96 rdf:type schema:CreativeWork
    97 sg:pub.10.1007/3-540-45350-4_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012278693
    98 https://doi.org/10.1007/3-540-45350-4_11
    99 rdf:type schema:CreativeWork
    100 sg:pub.10.1007/3-540-58485-4_57 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007111166
    101 https://doi.org/10.1007/3-540-58485-4_57
    102 rdf:type schema:CreativeWork
    103 sg:pub.10.1007/3-540-61580-6_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036259674
    104 https://doi.org/10.1007/3-540-61580-6_15
    105 rdf:type schema:CreativeWork
    106 sg:pub.10.1007/3-540-61580-6_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053155927
    107 https://doi.org/10.1007/3-540-61580-6_22
    108 rdf:type schema:CreativeWork
    109 sg:pub.10.1007/bfb0032064 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028626654
    110 https://doi.org/10.1007/bfb0032064
    111 rdf:type schema:CreativeWork
    112 https://doi.org/10.1016/0020-0190(77)90078-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016252608
    113 rdf:type schema:CreativeWork
    114 https://doi.org/10.1016/0304-3975(86)90173-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038643339
    115 rdf:type schema:CreativeWork
    116 https://doi.org/10.1016/s0020-0190(97)00055-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000980817
    117 rdf:type schema:CreativeWork
    118 https://doi.org/10.1017/s0956796800001167 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038404271
    119 rdf:type schema:CreativeWork
    120 https://doi.org/10.1145/143165.143220 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051821774
    121 rdf:type schema:CreativeWork
    122 https://doi.org/10.1145/568173.568175 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001092670
    123 rdf:type schema:CreativeWork
    124 https://doi.org/10.1145/568173.568177 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009624065
    125 rdf:type schema:CreativeWork
    126 https://doi.org/10.1145/99370.99372 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039267274
    127 rdf:type schema:CreativeWork
    128 https://www.grid.ac/institutes/grid.5290.e schema:alternateName Waseda University
    129 schema:name PRESTO, JST & Institute for Software Production Technology, Waseda University, School of Science and Engineering, 169-8555, Tokyo, Japan
    130 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...