An Experiment with the Fourth Futamura Projection View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2010

AUTHORS

Robert Glück

ABSTRACT

We have experimentally validated the theoretical insight, that a compiler generator is an Ershov generating extension of a program specializer, by showing that an existing offline partial evaluator can perform the fourth Futamura projection. Specifically, an online and an offline partial evaluator for an imperative flowchart language were transformed into two new compiler generators by Romanenko’s classical partial evaluator Unmix. The two partial evaluators are described, as is a novel recursive method for polyvariant specialization. The new compiler generators are demonstrated by converting a universal parser into a parser generator. These results strongly indicate that existing partial evaluation techniques can be put to work on several new applications. To date, all previous compiler generators based on partial evaluation were either generated by self-application or handwritten. None of these works considered the generation of one compiler generator by another. More... »

PAGES

135-150

References to SciGraph publications

  • 1990. Arity raiser and its use in program specialization in ESOP '90
  • 1993. Occam's razor in metacomputation: the notion of a perfect process tree in STATIC ANALYSIS
  • 1984-12. Polyvariant mixed computation for analyzer programs in ACTA INFORMATICA
  • 1995. Efficient multi-level generating extensions for program specialization in PROGRAMMING LANGUAGES: IMPLEMENTATIONS, LOGICS AND PROGRAMS
  • 1999. An Introduction to Online and Offline Partial Evaluation Using a Simple Flowchart Language in PARTIAL EVALUATION
  • 2002. WSDFU: Program Transformation System Based on Generalized Partial Computation in THE ESSENCE OF COMPUTATION
  • 2006. On Jones-Optimal Specializers: A Case Study Using Unmix in PROGRAMMING LANGUAGES AND SYSTEMS
  • 1983. Partial computation of programs in RIMS SYMPOSIA ON SOFTWARE SCIENCE AND ENGINEERING
  • 1999-12. Partial Evaluation of Computation Process, Revisited in HIGHER-ORDER AND SYMBOLIC COMPUTATION
  • 2008-06. Imperative-program transformation by instrumented-interpreter specialization in HIGHER-ORDER AND SYMBOLIC COMPUTATION
  • 1989-02. Mix: A self-applicable partial evaluator for experiments in compiler generation in LISP AND SYMBOLIC COMPUTATION
  • 2008-09. An investigation of Jones optimality and BTI-universal specializers in HIGHER-ORDER AND SYMBOLIC COMPUTATION
  • Book

    TITLE

    Perspectives of Systems Informatics

    ISBN

    978-3-642-11485-4
    978-3-642-11486-1

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-642-11486-1_12

    DOI

    http://dx.doi.org/10.1007/978-3-642-11486-1_12

    DIMENSIONS

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


    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/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Copenhagen", 
              "id": "https://www.grid.ac/institutes/grid.5254.6", 
              "name": [
                "DIKU, Dept. of Computer Science, University of Copenhagen, DK-2100, Copenhagen, Denmark"
              ], 
              "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-11980-9_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001337766", 
              "https://doi.org/10.1007/3-540-11980-9_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11924661_25", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003898112", 
              "https://doi.org/10.1007/11924661_25"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11924661_25", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003898112", 
              "https://doi.org/10.1007/11924661_25"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-57264-3_34", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003987904", 
              "https://doi.org/10.1007/3-540-57264-3_34"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01806312", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007653765", 
              "https://doi.org/10.1007/bf01806312"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01806312", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007653765", 
              "https://doi.org/10.1007/bf01806312"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/963778.963784", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010449995"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-52592-0_73", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011836818", 
              "https://doi.org/10.1007/3-540-52592-0_73"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/s0956796800000745", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012505631"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-47018-2_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013466468", 
              "https://doi.org/10.1007/3-540-47018-2_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/5956.5957", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016193336"
            ], 
            "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/3-540-36377-7_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019023069", 
              "https://doi.org/10.1007/3-540-36377-7_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0026825", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021776056", 
              "https://doi.org/10.1007/bfb0026825"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10990-008-9033-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029756061", 
              "https://doi.org/10.1007/s10990-008-9033-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10990-008-9027-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032631334", 
              "https://doi.org/10.1007/s10990-008-9027-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/777388.777391", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041853059"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/a:1010043619517", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044077633", 
              "https://doi.org/10.1023/a:1010043619517"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1480945.1480954", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051792591"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00271642", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053177031", 
              "https://doi.org/10.1007/bf00271642"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00271642", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053177031", 
              "https://doi.org/10.1007/bf00271642"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2010", 
        "datePublishedReg": "2010-01-01", 
        "description": "We have experimentally validated the theoretical insight, that a compiler generator is an Ershov generating extension of a program specializer, by showing that an existing offline partial evaluator can perform the fourth Futamura projection. Specifically, an online and an offline partial evaluator for an imperative flowchart language were transformed into two new compiler generators by Romanenko\u2019s classical partial evaluator Unmix. The two partial evaluators are described, as is a novel recursive method for polyvariant specialization. The new compiler generators are demonstrated by converting a universal parser into a parser generator. These results strongly indicate that existing partial evaluation techniques can be put to work on several new applications. To date, all previous compiler generators based on partial evaluation were either generated by self-application or handwritten. None of these works considered the generation of one compiler generator by another.", 
        "editor": [
          {
            "familyName": "Pnueli", 
            "givenName": "Amir", 
            "type": "Person"
          }, 
          {
            "familyName": "Virbitskaite", 
            "givenName": "Irina", 
            "type": "Person"
          }, 
          {
            "familyName": "Voronkov", 
            "givenName": "Andrei", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-642-11486-1_12", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-642-11485-4", 
            "978-3-642-11486-1"
          ], 
          "name": "Perspectives of Systems Informatics", 
          "type": "Book"
        }, 
        "name": "An Experiment with the Fourth Futamura Projection", 
        "pagination": "135-150", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1008260336"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-642-11486-1_12"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "275a2917b17d9614d09eda886ede0ac07e8b80b8b27bb94bc48c233e5f070631"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-642-11486-1_12", 
          "https://app.dimensions.ai/details/publication/pub.1008260336"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T07:32", 
        "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/0000000356_0000000356/records_57900_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-642-11486-1_12"
      }
    ]
     

    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-642-11486-1_12'

    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-642-11486-1_12'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-11486-1_12'

    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-642-11486-1_12'


     

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

    141 TRIPLES      23 PREDICATES      45 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-642-11486-1_12 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author N5b982c02832d4cd79959aeb6f7669ecd
    4 schema:citation sg:pub.10.1007/11924661_25
    5 sg:pub.10.1007/3-540-11980-9_13
    6 sg:pub.10.1007/3-540-36377-7_16
    7 sg:pub.10.1007/3-540-47018-2_2
    8 sg:pub.10.1007/3-540-52592-0_73
    9 sg:pub.10.1007/3-540-57264-3_34
    10 sg:pub.10.1007/bf00271642
    11 sg:pub.10.1007/bf01806312
    12 sg:pub.10.1007/bfb0026825
    13 sg:pub.10.1007/s10990-008-9027-3
    14 sg:pub.10.1007/s10990-008-9033-5
    15 sg:pub.10.1023/a:1010043619517
    16 https://doi.org/10.1016/0020-0190(77)90078-3
    17 https://doi.org/10.1017/s0956796800000745
    18 https://doi.org/10.1145/1480945.1480954
    19 https://doi.org/10.1145/5956.5957
    20 https://doi.org/10.1145/777388.777391
    21 https://doi.org/10.1145/963778.963784
    22 schema:datePublished 2010
    23 schema:datePublishedReg 2010-01-01
    24 schema:description We have experimentally validated the theoretical insight, that a compiler generator is an Ershov generating extension of a program specializer, by showing that an existing offline partial evaluator can perform the fourth Futamura projection. Specifically, an online and an offline partial evaluator for an imperative flowchart language were transformed into two new compiler generators by Romanenko’s classical partial evaluator Unmix. The two partial evaluators are described, as is a novel recursive method for polyvariant specialization. The new compiler generators are demonstrated by converting a universal parser into a parser generator. These results strongly indicate that existing partial evaluation techniques can be put to work on several new applications. To date, all previous compiler generators based on partial evaluation were either generated by self-application or handwritten. None of these works considered the generation of one compiler generator by another.
    25 schema:editor N6d3c75fbed2e466d88c51533aa398c6c
    26 schema:genre chapter
    27 schema:inLanguage en
    28 schema:isAccessibleForFree false
    29 schema:isPartOf N5ddb9e93d4534ec1bb1713db0b564e58
    30 schema:name An Experiment with the Fourth Futamura Projection
    31 schema:pagination 135-150
    32 schema:productId N3da43592019242f488ac4898d95ae923
    33 N8e338f473ef34dfb86c9f5b6cd7cb234
    34 Ne1e8709d47074e4a9b0c04126dfbbc8d
    35 schema:publisher N39bcd84a1a4a4bb5988a7eb10a12d4bf
    36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008260336
    37 https://doi.org/10.1007/978-3-642-11486-1_12
    38 schema:sdDatePublished 2019-04-16T07:32
    39 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    40 schema:sdPublisher N2b3b8c07c3864e2cb16f412a881067bf
    41 schema:url https://link.springer.com/10.1007%2F978-3-642-11486-1_12
    42 sgo:license sg:explorer/license/
    43 sgo:sdDataset chapters
    44 rdf:type schema:Chapter
    45 N07ac82b035a547aeb85558afb71d5ab2 rdf:first N4efdd44b2be24f9388094f4f34052f5a
    46 rdf:rest N86071402988d42f696448bc94c3c58fa
    47 N2b3b8c07c3864e2cb16f412a881067bf schema:name Springer Nature - SN SciGraph project
    48 rdf:type schema:Organization
    49 N39bcd84a1a4a4bb5988a7eb10a12d4bf schema:location Berlin, Heidelberg
    50 schema:name Springer Berlin Heidelberg
    51 rdf:type schema:Organisation
    52 N3da43592019242f488ac4898d95ae923 schema:name dimensions_id
    53 schema:value pub.1008260336
    54 rdf:type schema:PropertyValue
    55 N4efdd44b2be24f9388094f4f34052f5a schema:familyName Virbitskaite
    56 schema:givenName Irina
    57 rdf:type schema:Person
    58 N5b982c02832d4cd79959aeb6f7669ecd rdf:first sg:person.010754010217.31
    59 rdf:rest rdf:nil
    60 N5ddb9e93d4534ec1bb1713db0b564e58 schema:isbn 978-3-642-11485-4
    61 978-3-642-11486-1
    62 schema:name Perspectives of Systems Informatics
    63 rdf:type schema:Book
    64 N6d3c75fbed2e466d88c51533aa398c6c rdf:first Ne34f845519a34d1185ad6ec8747c0901
    65 rdf:rest N07ac82b035a547aeb85558afb71d5ab2
    66 N86071402988d42f696448bc94c3c58fa rdf:first Nc81ca3b3045f488584a89764dc43161a
    67 rdf:rest rdf:nil
    68 N8e338f473ef34dfb86c9f5b6cd7cb234 schema:name readcube_id
    69 schema:value 275a2917b17d9614d09eda886ede0ac07e8b80b8b27bb94bc48c233e5f070631
    70 rdf:type schema:PropertyValue
    71 Nc81ca3b3045f488584a89764dc43161a schema:familyName Voronkov
    72 schema:givenName Andrei
    73 rdf:type schema:Person
    74 Ne1e8709d47074e4a9b0c04126dfbbc8d schema:name doi
    75 schema:value 10.1007/978-3-642-11486-1_12
    76 rdf:type schema:PropertyValue
    77 Ne34f845519a34d1185ad6ec8747c0901 schema:familyName Pnueli
    78 schema:givenName Amir
    79 rdf:type schema:Person
    80 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    81 schema:name Information and Computing Sciences
    82 rdf:type schema:DefinedTerm
    83 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    84 schema:name Artificial Intelligence and Image Processing
    85 rdf:type schema:DefinedTerm
    86 sg:person.010754010217.31 schema:affiliation https://www.grid.ac/institutes/grid.5254.6
    87 schema:familyName Glück
    88 schema:givenName Robert
    89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010754010217.31
    90 rdf:type schema:Person
    91 sg:pub.10.1007/11924661_25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003898112
    92 https://doi.org/10.1007/11924661_25
    93 rdf:type schema:CreativeWork
    94 sg:pub.10.1007/3-540-11980-9_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001337766
    95 https://doi.org/10.1007/3-540-11980-9_13
    96 rdf:type schema:CreativeWork
    97 sg:pub.10.1007/3-540-36377-7_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019023069
    98 https://doi.org/10.1007/3-540-36377-7_16
    99 rdf:type schema:CreativeWork
    100 sg:pub.10.1007/3-540-47018-2_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013466468
    101 https://doi.org/10.1007/3-540-47018-2_2
    102 rdf:type schema:CreativeWork
    103 sg:pub.10.1007/3-540-52592-0_73 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011836818
    104 https://doi.org/10.1007/3-540-52592-0_73
    105 rdf:type schema:CreativeWork
    106 sg:pub.10.1007/3-540-57264-3_34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003987904
    107 https://doi.org/10.1007/3-540-57264-3_34
    108 rdf:type schema:CreativeWork
    109 sg:pub.10.1007/bf00271642 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053177031
    110 https://doi.org/10.1007/bf00271642
    111 rdf:type schema:CreativeWork
    112 sg:pub.10.1007/bf01806312 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007653765
    113 https://doi.org/10.1007/bf01806312
    114 rdf:type schema:CreativeWork
    115 sg:pub.10.1007/bfb0026825 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021776056
    116 https://doi.org/10.1007/bfb0026825
    117 rdf:type schema:CreativeWork
    118 sg:pub.10.1007/s10990-008-9027-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032631334
    119 https://doi.org/10.1007/s10990-008-9027-3
    120 rdf:type schema:CreativeWork
    121 sg:pub.10.1007/s10990-008-9033-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029756061
    122 https://doi.org/10.1007/s10990-008-9033-5
    123 rdf:type schema:CreativeWork
    124 sg:pub.10.1023/a:1010043619517 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044077633
    125 https://doi.org/10.1023/a:1010043619517
    126 rdf:type schema:CreativeWork
    127 https://doi.org/10.1016/0020-0190(77)90078-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016252608
    128 rdf:type schema:CreativeWork
    129 https://doi.org/10.1017/s0956796800000745 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012505631
    130 rdf:type schema:CreativeWork
    131 https://doi.org/10.1145/1480945.1480954 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051792591
    132 rdf:type schema:CreativeWork
    133 https://doi.org/10.1145/5956.5957 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016193336
    134 rdf:type schema:CreativeWork
    135 https://doi.org/10.1145/777388.777391 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041853059
    136 rdf:type schema:CreativeWork
    137 https://doi.org/10.1145/963778.963784 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010449995
    138 rdf:type schema:CreativeWork
    139 https://www.grid.ac/institutes/grid.5254.6 schema:alternateName University of Copenhagen
    140 schema:name DIKU, Dept. of Computer Science, University of Copenhagen, DK-2100, Copenhagen, Denmark
    141 rdf:type schema:Organization
     




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


    ...