An Automatic Program Generator for Multi-Level Specialization View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1997-07

AUTHORS

Robert Glück, Jesper Jørgensen

ABSTRACT

Program specialization can divide a computation into several computation stages. This paper investigates the theoretical limitations and practical problems of standard specialization tools, presents multi-level specialization, and demonstrates that, in combination with the cogen approach, it is far more practical than previously supposed. The program generator which we designed and implemented for a higher-order functional language converts programs into very compact multi-level generating extensions that guarantee fast successive specialization. Experimental results show a remarkable reduction of generation time and generator size compared to previous attempts of multi-level specialization by self-application. Our approach to multi-level specialization seems well-suited for applications where generation time and program size are critical. More... »

PAGES

113-158

References to SciGraph publications

  • 1996. Fast binding-time analysis for multi-level specialization in PERSPECTIVES OF SYSTEM INFORMATICS
  • 1996. BTA Algorithms to ensure termination of off-line partial evaluation in PERSPECTIVES OF SYSTEM INFORMATICS
  • 1995. Mechanically verifying the correctness of an offline partial evaluator in PROGRAMMING LANGUAGES: IMPLEMENTATIONS, LOGICS AND PROGRAMS
  • 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
  • 1994. Generating transformers for deforestation and supercompilation in STATIC ANALYSIS
  • 1994. Hand-writing program generator generators in PROGRAMMING LANGUAGE IMPLEMENTATION AND LOGIC PROGRAMMING
  • 1990. From interpreting to compiling binding times in ESOP '90
  • 1991. Efficient type inference for higher-order binding-time analysis in FUNCTIONAL PROGRAMMING LANGUAGES AND COMPUTER ARCHITECTURE
  • 1995-09. Binding-time analysis for Standard ML in HIGHER-ORDER AND SYMBOLIC COMPUTATION
  • 1989-02. Mix: A self-applicable partial evaluator for experiments in compiler generation in HIGHER-ORDER AND SYMBOLIC COMPUTATION
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1023/a:1007763000430

    DOI

    http://dx.doi.org/10.1023/a:1007763000430

    DIMENSIONS

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


    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/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "DIKU, Department of Computer Science, University of Copenhagen, Universitetsparken 1, DK-2100, Copenhagen, Denmark", 
              "id": "http://www.grid.ac/institutes/grid.5254.6", 
              "name": [
                "DIKU, Department of Computer Science, University of Copenhagen, Universitetsparken 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": "Department of Mathematics and Physics, Royal Veterinary and Agricultural University, Thorvaldsensvej 40, DK-1871, Frederiksberg C, Denmark", 
              "id": "http://www.grid.ac/institutes/grid.5254.6", 
              "name": [
                "Department of Mathematics and Physics, Royal Veterinary and Agricultural University, Thorvaldsensvej 40, DK-1871, Frederiksberg C, Denmark"
              ], 
              "type": "Organization"
            }, 
            "familyName": "J\u00f8rgensen", 
            "givenName": "Jesper", 
            "id": "sg:person.014706352727.82", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014706352727.82"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "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/3-540-58402-1_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021084016", 
              "https://doi.org/10.1007/3-540-58402-1_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-52592-0_57", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004069314", 
              "https://doi.org/10.1007/3-540-52592-0_57"
            ], 
            "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-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": "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/3-540-62064-8_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008856040", 
              "https://doi.org/10.1007/3-540-62064-8_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0026826", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005994428", 
              "https://doi.org/10.1007/bfb0026826"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01019003", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019723585", 
              "https://doi.org/10.1007/bf01019003"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3540543961_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024172582", 
              "https://doi.org/10.1007/3540543961_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-62064-8_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007002321", 
              "https://doi.org/10.1007/3-540-62064-8_23"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1997-07", 
        "datePublishedReg": "1997-07-01", 
        "description": "Program specialization can divide a computation into several computation stages. This paper investigates the theoretical limitations and practical problems of standard specialization tools, presents multi-level specialization, and demonstrates that, in combination with the cogen approach, it is far more practical than previously supposed. The program generator which we designed and implemented for a higher-order functional language converts programs into very compact multi-level generating extensions that guarantee fast successive specialization. Experimental results show a remarkable reduction of generation time and generator size compared to previous attempts of multi-level specialization by self-application. Our approach to multi-level specialization seems well-suited for applications where generation time and program size are critical.", 
        "genre": "article", 
        "id": "sg:pub.10.1023/a:1007763000430", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1273809", 
            "issn": [
              "0892-4635", 
              "2212-0793"
            ], 
            "name": "Higher-Order and Symbolic Computation", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "10"
          }
        ], 
        "keywords": [
          "program generator", 
          "automatic program generator", 
          "higher-order functional language", 
          "computation stages", 
          "program specialization", 
          "functional language", 
          "program size", 
          "cogen approach", 
          "experimental results", 
          "practical problems", 
          "computation", 
          "language", 
          "successive specialization", 
          "previous attempts", 
          "theoretical limitations", 
          "generator", 
          "tool", 
          "applications", 
          "extension", 
          "generation time", 
          "time", 
          "limitations", 
          "generator size", 
          "specialization", 
          "program", 
          "size", 
          "results", 
          "combination", 
          "remarkable reduction", 
          "attempt", 
          "stage", 
          "reduction", 
          "approach", 
          "paper", 
          "problem", 
          "standard specialization tools", 
          "specialization tools", 
          "multi-level specialization", 
          "compact multi-level generating extensions", 
          "multi-level generating extensions", 
          "generating extensions", 
          "fast successive specialization"
        ], 
        "name": "An Automatic Program Generator for Multi-Level Specialization", 
        "pagination": "113-158", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1038704478"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1023/a:1007763000430"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1023/a:1007763000430", 
          "https://app.dimensions.ai/details/publication/pub.1038704478"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2021-12-01T19:09", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/article/article_268.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1023/a:1007763000430"
      }
    ]
     

    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.1023/a:1007763000430'

    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.1023/a:1007763000430'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/a:1007763000430'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/a:1007763000430'


     

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

    153 TRIPLES      22 PREDICATES      79 URIs      60 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1023/a:1007763000430 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Nf31e86e1202b439f826153d39389f6da
    4 schema:citation sg:pub.10.1007/3-540-52592-0_57
    5 sg:pub.10.1007/3-540-58402-1_15
    6 sg:pub.10.1007/3-540-58485-4_57
    7 sg:pub.10.1007/3-540-62064-8_22
    8 sg:pub.10.1007/3-540-62064-8_23
    9 sg:pub.10.1007/3540543961_22
    10 sg:pub.10.1007/bf00271642
    11 sg:pub.10.1007/bf01019003
    12 sg:pub.10.1007/bf01806312
    13 sg:pub.10.1007/bfb0026825
    14 sg:pub.10.1007/bfb0026826
    15 schema:datePublished 1997-07
    16 schema:datePublishedReg 1997-07-01
    17 schema:description Program specialization can divide a computation into several computation stages. This paper investigates the theoretical limitations and practical problems of standard specialization tools, presents multi-level specialization, and demonstrates that, in combination with the cogen approach, it is far more practical than previously supposed. The program generator which we designed and implemented for a higher-order functional language converts programs into very compact multi-level generating extensions that guarantee fast successive specialization. Experimental results show a remarkable reduction of generation time and generator size compared to previous attempts of multi-level specialization by self-application. Our approach to multi-level specialization seems well-suited for applications where generation time and program size are critical.
    18 schema:genre article
    19 schema:inLanguage en
    20 schema:isAccessibleForFree false
    21 schema:isPartOf N744dfa7a921c4093ab4b1937bce7b00a
    22 N7b94a2a6880a4245bbbd5fe52921f5ca
    23 sg:journal.1273809
    24 schema:keywords applications
    25 approach
    26 attempt
    27 automatic program generator
    28 cogen approach
    29 combination
    30 compact multi-level generating extensions
    31 computation
    32 computation stages
    33 experimental results
    34 extension
    35 fast successive specialization
    36 functional language
    37 generating extensions
    38 generation time
    39 generator
    40 generator size
    41 higher-order functional language
    42 language
    43 limitations
    44 multi-level generating extensions
    45 multi-level specialization
    46 paper
    47 practical problems
    48 previous attempts
    49 problem
    50 program
    51 program generator
    52 program size
    53 program specialization
    54 reduction
    55 remarkable reduction
    56 results
    57 size
    58 specialization
    59 specialization tools
    60 stage
    61 standard specialization tools
    62 successive specialization
    63 theoretical limitations
    64 time
    65 tool
    66 schema:name An Automatic Program Generator for Multi-Level Specialization
    67 schema:pagination 113-158
    68 schema:productId N82305fccc590492599c450cb0747c53a
    69 Ne012e8bc81a8483fb63a50bb843a5280
    70 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038704478
    71 https://doi.org/10.1023/a:1007763000430
    72 schema:sdDatePublished 2021-12-01T19:09
    73 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    74 schema:sdPublisher N87fbeef64b1a4400a7ad712d2d74d40e
    75 schema:url https://doi.org/10.1023/a:1007763000430
    76 sgo:license sg:explorer/license/
    77 sgo:sdDataset articles
    78 rdf:type schema:ScholarlyArticle
    79 N22b9c975ee4248ff81e669ca53a0f611 rdf:first sg:person.014706352727.82
    80 rdf:rest rdf:nil
    81 N744dfa7a921c4093ab4b1937bce7b00a schema:issueNumber 2
    82 rdf:type schema:PublicationIssue
    83 N7b94a2a6880a4245bbbd5fe52921f5ca schema:volumeNumber 10
    84 rdf:type schema:PublicationVolume
    85 N82305fccc590492599c450cb0747c53a schema:name dimensions_id
    86 schema:value pub.1038704478
    87 rdf:type schema:PropertyValue
    88 N87fbeef64b1a4400a7ad712d2d74d40e schema:name Springer Nature - SN SciGraph project
    89 rdf:type schema:Organization
    90 Ne012e8bc81a8483fb63a50bb843a5280 schema:name doi
    91 schema:value 10.1023/a:1007763000430
    92 rdf:type schema:PropertyValue
    93 Nf31e86e1202b439f826153d39389f6da rdf:first sg:person.010754010217.31
    94 rdf:rest N22b9c975ee4248ff81e669ca53a0f611
    95 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    96 schema:name Information and Computing Sciences
    97 rdf:type schema:DefinedTerm
    98 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    99 schema:name Computation Theory and Mathematics
    100 rdf:type schema:DefinedTerm
    101 sg:journal.1273809 schema:issn 0892-4635
    102 2212-0793
    103 schema:name Higher-Order and Symbolic Computation
    104 schema:publisher Springer Nature
    105 rdf:type schema:Periodical
    106 sg:person.010754010217.31 schema:affiliation grid-institutes:grid.5254.6
    107 schema:familyName Glück
    108 schema:givenName Robert
    109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010754010217.31
    110 rdf:type schema:Person
    111 sg:person.014706352727.82 schema:affiliation grid-institutes:grid.5254.6
    112 schema:familyName Jørgensen
    113 schema:givenName Jesper
    114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014706352727.82
    115 rdf:type schema:Person
    116 sg:pub.10.1007/3-540-52592-0_57 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004069314
    117 https://doi.org/10.1007/3-540-52592-0_57
    118 rdf:type schema:CreativeWork
    119 sg:pub.10.1007/3-540-58402-1_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021084016
    120 https://doi.org/10.1007/3-540-58402-1_15
    121 rdf:type schema:CreativeWork
    122 sg:pub.10.1007/3-540-58485-4_57 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007111166
    123 https://doi.org/10.1007/3-540-58485-4_57
    124 rdf:type schema:CreativeWork
    125 sg:pub.10.1007/3-540-62064-8_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008856040
    126 https://doi.org/10.1007/3-540-62064-8_22
    127 rdf:type schema:CreativeWork
    128 sg:pub.10.1007/3-540-62064-8_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007002321
    129 https://doi.org/10.1007/3-540-62064-8_23
    130 rdf:type schema:CreativeWork
    131 sg:pub.10.1007/3540543961_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024172582
    132 https://doi.org/10.1007/3540543961_22
    133 rdf:type schema:CreativeWork
    134 sg:pub.10.1007/bf00271642 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053177031
    135 https://doi.org/10.1007/bf00271642
    136 rdf:type schema:CreativeWork
    137 sg:pub.10.1007/bf01019003 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019723585
    138 https://doi.org/10.1007/bf01019003
    139 rdf:type schema:CreativeWork
    140 sg:pub.10.1007/bf01806312 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007653765
    141 https://doi.org/10.1007/bf01806312
    142 rdf:type schema:CreativeWork
    143 sg:pub.10.1007/bfb0026825 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021776056
    144 https://doi.org/10.1007/bfb0026825
    145 rdf:type schema:CreativeWork
    146 sg:pub.10.1007/bfb0026826 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005994428
    147 https://doi.org/10.1007/bfb0026826
    148 rdf:type schema:CreativeWork
    149 grid-institutes:grid.5254.6 schema:alternateName DIKU, Department of Computer Science, University of Copenhagen, Universitetsparken 1, DK-2100, Copenhagen, Denmark
    150 Department of Mathematics and Physics, Royal Veterinary and Agricultural University, Thorvaldsensvej 40, DK-1871, Frederiksberg C, Denmark
    151 schema:name DIKU, Department of Computer Science, University of Copenhagen, Universitetsparken 1, DK-2100, Copenhagen, Denmark
    152 Department of Mathematics and Physics, Royal Veterinary and Agricultural University, Thorvaldsensvej 40, DK-1871, Frederiksberg C, Denmark
    153 rdf:type schema:Organization
     




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


    ...