On the degeneration of program generators by program composition View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1998-03

AUTHORS

Robert Glück, Andrei Klimov

ABSTRACT

One of the main discoveries in the seventies was that the concept of a generating extension covers a very wide class of apparently different program generators. Program specialization, or partial evaluation, is powerful because it provides uniform techniques for the automatic implementation of generating extensions from ordinary programs. The Futamura projections stand as the cornerstone of the development of program specialization. This paper takes the idea of the Futamura projections further. Threedegeneration projections are formulated which tell us how to achieve the reverse goal by program composition, namely turning a generating extension into an ordinary program. The fact that program composition can invert the effect of program specialization shows that these projections are dual in a sense. The degeneration projections complete a missing link between programs and generating extensions and allow for novel applications of program transformation. More... »

PAGES

75-95

References to SciGraph publications

  • 1983. Partial computation of programs in RIMS SYMPOSIA ON SOFTWARE SCIENCE AND ENGINEERING
  • 1996. On the mechanics of metasystem hierarchies in program transformation in LOGIC PROGRAM SYNTHESIS AND TRANSFORMATION
  • 1996. Metacomputation: Metasystem transitions plus supercompilation in PARTIAL EVALUATION
  • 1995. Efficient multi-level generating extensions for program specialization in PROGRAMMING LANGUAGES: IMPLEMENTATIONS, LOGICS AND PROGRAMS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bf03037321

    DOI

    http://dx.doi.org/10.1007/bf03037321

    DIMENSIONS

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


    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/0803", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computer Software", 
            "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": [
                "Department of Computer Science, University of Copenhagen, Universitets parken 1, 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"
          }, 
          {
            "affiliation": {
              "alternateName": "Russian Academy of Sciences", 
              "id": "https://www.grid.ac/institutes/grid.4886.2", 
              "name": [
                "Keldysh Institute of Applied Mathematics, Russian Academy of Sciences, Miusskaya Square 4, RU-125047, Moscow, Russia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Klimov", 
            "givenName": "Andrei", 
            "id": "sg:person.015026406676.39", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015026406676.39"
            ], 
            "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": "https://doi.org/10.1016/0167-6423(91)90035-v", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006712362"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/s0956796800000757", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016061186"
            ], 
            "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.1080/02604027.1995.9972561", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016815952"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(90)90147-a", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019824477"
            ], 
            "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/3-540-60939-3_18", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031899271", 
              "https://doi.org/10.1007/3-540-60939-3_18"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/355598.362740", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035463867"
            ], 
            "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.1145/224164.224221", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043643384"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/366199.366249", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050810962"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-61580-6_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052100186", 
              "https://doi.org/10.1007/3-540-61580-6_24"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1998-03", 
        "datePublishedReg": "1998-03-01", 
        "description": "One of the main discoveries in the seventies was that the concept of a generating extension covers a very wide class of apparently different program generators. Program specialization, or partial evaluation, is powerful because it provides uniform techniques for the automatic implementation of generating extensions from ordinary programs. The Futamura projections stand as the cornerstone of the development of program specialization. This paper takes the idea of the Futamura projections further. Threedegeneration projections are formulated which tell us how to achieve the reverse goal by program composition, namely turning a generating extension into an ordinary program. The fact that program composition can invert the effect of program specialization shows that these projections are dual in a sense. The degeneration projections complete a missing link between programs and generating extensions and allow for novel applications of program transformation.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/bf03037321", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1053619", 
            "issn": [
              "0288-3635", 
              "1882-7055"
            ], 
            "name": "New Generation Computing", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "16"
          }
        ], 
        "name": "On the degeneration of program generators by program composition", 
        "pagination": "75-95", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "c9050d78a92ab6568a3d9276071be55beac04806db6e8b239bd0dc954e1386c6"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf03037321"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1042200080"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf03037321", 
          "https://app.dimensions.ai/details/publication/pub.1042200080"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T09:07", 
        "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/0000000338_0000000338/records_47956_00000001.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007%2FBF03037321"
      }
    ]
     

    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/bf03037321'

    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/bf03037321'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf03037321'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf03037321'


     

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

    114 TRIPLES      21 PREDICATES      40 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf03037321 schema:about anzsrc-for:08
    2 anzsrc-for:0803
    3 schema:author N9545a443ae0b405ea512a7a9dea8fa22
    4 schema:citation sg:pub.10.1007/3-540-11980-9_13
    5 sg:pub.10.1007/3-540-60939-3_18
    6 sg:pub.10.1007/3-540-61580-6_24
    7 sg:pub.10.1007/bfb0026825
    8 https://doi.org/10.1016/0167-6423(91)90035-v
    9 https://doi.org/10.1016/0304-3975(90)90147-a
    10 https://doi.org/10.1017/s0956796800000757
    11 https://doi.org/10.1017/s0956796800001167
    12 https://doi.org/10.1080/02604027.1995.9972561
    13 https://doi.org/10.1145/224164.224221
    14 https://doi.org/10.1145/355598.362740
    15 https://doi.org/10.1145/366199.366249
    16 https://doi.org/10.1145/5956.5957
    17 schema:datePublished 1998-03
    18 schema:datePublishedReg 1998-03-01
    19 schema:description One of the main discoveries in the seventies was that the concept of a generating extension covers a very wide class of apparently different program generators. Program specialization, or partial evaluation, is powerful because it provides uniform techniques for the automatic implementation of generating extensions from ordinary programs. The Futamura projections stand as the cornerstone of the development of program specialization. This paper takes the idea of the Futamura projections further. Threedegeneration projections are formulated which tell us how to achieve the reverse goal by program composition, namely turning a generating extension into an ordinary program. The fact that program composition can invert the effect of program specialization shows that these projections are dual in a sense. The degeneration projections complete a missing link between programs and generating extensions and allow for novel applications of program transformation.
    20 schema:genre research_article
    21 schema:inLanguage en
    22 schema:isAccessibleForFree false
    23 schema:isPartOf N2e29082725c549bd8ac7e72ce1a58d24
    24 N93bd35e518c54f119390894527c0a5ac
    25 sg:journal.1053619
    26 schema:name On the degeneration of program generators by program composition
    27 schema:pagination 75-95
    28 schema:productId N1abd15f63fee498587b66dcb6669f27e
    29 N46e7a0873e1b4806a27990bb74756543
    30 Ne73d50a633a0438fbc5bd22b2b5f1d33
    31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042200080
    32 https://doi.org/10.1007/bf03037321
    33 schema:sdDatePublished 2019-04-11T09:07
    34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    35 schema:sdPublisher Nf67e39fe56d74b6f8837574797a2124f
    36 schema:url http://link.springer.com/10.1007%2FBF03037321
    37 sgo:license sg:explorer/license/
    38 sgo:sdDataset articles
    39 rdf:type schema:ScholarlyArticle
    40 N1abd15f63fee498587b66dcb6669f27e schema:name readcube_id
    41 schema:value c9050d78a92ab6568a3d9276071be55beac04806db6e8b239bd0dc954e1386c6
    42 rdf:type schema:PropertyValue
    43 N2e29082725c549bd8ac7e72ce1a58d24 schema:volumeNumber 16
    44 rdf:type schema:PublicationVolume
    45 N3be92f43b26345d59f5def4a8a5f196f rdf:first sg:person.015026406676.39
    46 rdf:rest rdf:nil
    47 N46e7a0873e1b4806a27990bb74756543 schema:name doi
    48 schema:value 10.1007/bf03037321
    49 rdf:type schema:PropertyValue
    50 N93bd35e518c54f119390894527c0a5ac schema:issueNumber 1
    51 rdf:type schema:PublicationIssue
    52 N9545a443ae0b405ea512a7a9dea8fa22 rdf:first sg:person.010754010217.31
    53 rdf:rest N3be92f43b26345d59f5def4a8a5f196f
    54 Ne73d50a633a0438fbc5bd22b2b5f1d33 schema:name dimensions_id
    55 schema:value pub.1042200080
    56 rdf:type schema:PropertyValue
    57 Nf67e39fe56d74b6f8837574797a2124f schema:name Springer Nature - SN SciGraph project
    58 rdf:type schema:Organization
    59 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    60 schema:name Information and Computing Sciences
    61 rdf:type schema:DefinedTerm
    62 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
    63 schema:name Computer Software
    64 rdf:type schema:DefinedTerm
    65 sg:journal.1053619 schema:issn 0288-3635
    66 1882-7055
    67 schema:name New Generation Computing
    68 rdf:type schema:Periodical
    69 sg:person.010754010217.31 schema:affiliation https://www.grid.ac/institutes/grid.5254.6
    70 schema:familyName Glück
    71 schema:givenName Robert
    72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010754010217.31
    73 rdf:type schema:Person
    74 sg:person.015026406676.39 schema:affiliation https://www.grid.ac/institutes/grid.4886.2
    75 schema:familyName Klimov
    76 schema:givenName Andrei
    77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015026406676.39
    78 rdf:type schema:Person
    79 sg:pub.10.1007/3-540-11980-9_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001337766
    80 https://doi.org/10.1007/3-540-11980-9_13
    81 rdf:type schema:CreativeWork
    82 sg:pub.10.1007/3-540-60939-3_18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031899271
    83 https://doi.org/10.1007/3-540-60939-3_18
    84 rdf:type schema:CreativeWork
    85 sg:pub.10.1007/3-540-61580-6_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052100186
    86 https://doi.org/10.1007/3-540-61580-6_24
    87 rdf:type schema:CreativeWork
    88 sg:pub.10.1007/bfb0026825 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021776056
    89 https://doi.org/10.1007/bfb0026825
    90 rdf:type schema:CreativeWork
    91 https://doi.org/10.1016/0167-6423(91)90035-v schema:sameAs https://app.dimensions.ai/details/publication/pub.1006712362
    92 rdf:type schema:CreativeWork
    93 https://doi.org/10.1016/0304-3975(90)90147-a schema:sameAs https://app.dimensions.ai/details/publication/pub.1019824477
    94 rdf:type schema:CreativeWork
    95 https://doi.org/10.1017/s0956796800000757 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016061186
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1017/s0956796800001167 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038404271
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1080/02604027.1995.9972561 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016815952
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1145/224164.224221 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043643384
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1145/355598.362740 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035463867
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1145/366199.366249 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050810962
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1145/5956.5957 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016193336
    108 rdf:type schema:CreativeWork
    109 https://www.grid.ac/institutes/grid.4886.2 schema:alternateName Russian Academy of Sciences
    110 schema:name Keldysh Institute of Applied Mathematics, Russian Academy of Sciences, Miusskaya Square 4, RU-125047, Moscow, Russia
    111 rdf:type schema:Organization
    112 https://www.grid.ac/institutes/grid.5254.6 schema:alternateName University of Copenhagen
    113 schema:name Department of Computer Science, University of Copenhagen, Universitets parken 1, DK-2100, Copenhagen, Denmark
    114 rdf:type schema:Organization
     




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


    ...