Maximally-Polyvariant Partial Evaluation in Polynomial Time View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2016

AUTHORS

Robert Glück

ABSTRACT

Maximally-polyvariant partial evaluation is a strategy for program specialization that propagates static values as accurate as possible. The online partial evaluator presented here achieves this precision in time polynomial in the number of partial-evaluation configurations. This is a significant improvement because a conventional partial evaluator can take exponential time, and no fast algorithm was known for maximally-polyvariant specialization. For an important class of quasi-deterministic specialization problems, our algorithm performs in linear time, even for linear-time specialization of a naive string matcher into a linear-time matcher, which was Futamura’s long-standing open challenge. Our results are presented using a recursive flowchart language. More... »

PAGES

130-148

Book

TITLE

Perspectives of System Informatics

ISBN

978-3-319-41578-9
978-3-319-41579-6

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-41579-6_11

DOI

http://dx.doi.org/10.1007/978-3-319-41579-6_11

DIMENSIONS

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


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/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure 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": "University of Copenhagen", 
          "id": "https://www.grid.ac/institutes/grid.5254.6", 
          "name": [
            "DIKU, Department of Computer Science, University of Copenhagen"
          ], 
          "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/bf03037260", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000035698", 
          "https://doi.org/10.1007/bf03037260"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1003866047", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-0-387-68954-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003866047", 
          "https://doi.org/10.1007/978-0-387-68954-8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-0-387-68954-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003866047", 
          "https://doi.org/10.1007/978-0-387-68954-8"
        ], 
        "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": "https://doi.org/10.1002/spe.1086", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005085336"
        ], 
        "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/3-540-51237-3_11", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007169098", 
          "https://doi.org/10.1007/3-540-51237-3_11"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/963778.963784", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010449995"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(83)90124-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012264779"
        ], 
        "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.1016/s0019-9958(68)91087-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013914005"
        ], 
        "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": "https://doi.org/10.1016/0020-0190(89)90113-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028126397"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(77)90022-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033910504"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/154630.154637", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034160022"
        ], 
        "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/s0956796800002008", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042426034"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-40946-7_10", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046041225", 
          "https://doi.org/10.1007/978-3-319-40946-7_10"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/568173.568174", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046476890"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1146809.1146812", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050414528"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/zamm.19790590233", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052840008"
        ], 
        "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"
      }, 
      {
        "id": "https://doi.org/10.1137/0206024", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841363"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2016", 
    "datePublishedReg": "2016-01-01", 
    "description": "Maximally-polyvariant partial evaluation is a strategy for program specialization that propagates static values as accurate as possible. The online partial evaluator presented here achieves this precision in time polynomial in the number of partial-evaluation configurations. This is a significant improvement because a conventional partial evaluator can take exponential time, and no fast algorithm was known for maximally-polyvariant specialization. For an important class of quasi-deterministic specialization problems, our algorithm performs in linear time, even for linear-time specialization of a naive string matcher into a linear-time matcher, which was Futamura\u2019s long-standing open challenge. Our results are presented using a recursive flowchart language.", 
    "editor": [
      {
        "familyName": "Mazzara", 
        "givenName": "Manuel", 
        "type": "Person"
      }, 
      {
        "familyName": "Voronkov", 
        "givenName": "Andrei", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-41579-6_11", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-41578-9", 
        "978-3-319-41579-6"
      ], 
      "name": "Perspectives of System Informatics", 
      "type": "Book"
    }, 
    "name": "Maximally-Polyvariant Partial Evaluation in Polynomial Time", 
    "pagination": "130-148", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-41579-6_11"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "d569815334364c3c8dbdc7e9047df1354daa728aab388ecb32849e9d31cd2316"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1044803080"
        ]
      }
    ], 
    "publisher": {
      "location": "Cham", 
      "name": "Springer International Publishing", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-41579-6_11", 
      "https://app.dimensions.ai/details/publication/pub.1044803080"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T00:51", 
    "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/0000000001_0000000264/records_8700_00000271.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-319-41579-6_11"
  }
]
 

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-319-41579-6_11'

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-319-41579-6_11'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-41579-6_11'

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-319-41579-6_11'


 

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

147 TRIPLES      23 PREDICATES      50 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-41579-6_11 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Nb52fbc2accc44e73a909b0ebedab10f8
4 schema:citation sg:pub.10.1007/3-540-47018-2_2
5 sg:pub.10.1007/3-540-51237-3_11
6 sg:pub.10.1007/3-540-57264-3_34
7 sg:pub.10.1007/3-540-58485-4_57
8 sg:pub.10.1007/3-540-61580-6_15
9 sg:pub.10.1007/978-0-387-68954-8
10 sg:pub.10.1007/978-3-319-40946-7_10
11 sg:pub.10.1007/bf00271642
12 sg:pub.10.1007/bf03037260
13 https://app.dimensions.ai/details/publication/pub.1003866047
14 https://doi.org/10.1002/spe.1086
15 https://doi.org/10.1002/zamm.19790590233
16 https://doi.org/10.1016/0020-0190(77)90022-9
17 https://doi.org/10.1016/0020-0190(77)90078-3
18 https://doi.org/10.1016/0020-0190(83)90124-2
19 https://doi.org/10.1016/0020-0190(89)90113-0
20 https://doi.org/10.1016/s0019-9958(68)91087-5
21 https://doi.org/10.1017/s0956796800002008
22 https://doi.org/10.1137/0206024
23 https://doi.org/10.1145/1146809.1146812
24 https://doi.org/10.1145/154630.154637
25 https://doi.org/10.1145/568173.568174
26 https://doi.org/10.1145/963778.963784
27 schema:datePublished 2016
28 schema:datePublishedReg 2016-01-01
29 schema:description Maximally-polyvariant partial evaluation is a strategy for program specialization that propagates static values as accurate as possible. The online partial evaluator presented here achieves this precision in time polynomial in the number of partial-evaluation configurations. This is a significant improvement because a conventional partial evaluator can take exponential time, and no fast algorithm was known for maximally-polyvariant specialization. For an important class of quasi-deterministic specialization problems, our algorithm performs in linear time, even for linear-time specialization of a naive string matcher into a linear-time matcher, which was Futamura’s long-standing open challenge. Our results are presented using a recursive flowchart language.
30 schema:editor N7deff2a27cc448849cea77139ff74a43
31 schema:genre chapter
32 schema:inLanguage en
33 schema:isAccessibleForFree false
34 schema:isPartOf N37547433430c4be889c81ca771f890dd
35 schema:name Maximally-Polyvariant Partial Evaluation in Polynomial Time
36 schema:pagination 130-148
37 schema:productId N08fdecb03b7f479185ac875e50003a97
38 N6042ff71440344198412f8f7341889de
39 Ne8b7844e15a44116bfd5c1b701fd2faa
40 schema:publisher N894212fce5ae449288fac08429ec9330
41 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044803080
42 https://doi.org/10.1007/978-3-319-41579-6_11
43 schema:sdDatePublished 2019-04-16T00:51
44 schema:sdLicense https://scigraph.springernature.com/explorer/license/
45 schema:sdPublisher N7f1b935934514c1eaca4098605ec5f9f
46 schema:url http://link.springer.com/10.1007/978-3-319-41579-6_11
47 sgo:license sg:explorer/license/
48 sgo:sdDataset chapters
49 rdf:type schema:Chapter
50 N08fdecb03b7f479185ac875e50003a97 schema:name dimensions_id
51 schema:value pub.1044803080
52 rdf:type schema:PropertyValue
53 N37547433430c4be889c81ca771f890dd schema:isbn 978-3-319-41578-9
54 978-3-319-41579-6
55 schema:name Perspectives of System Informatics
56 rdf:type schema:Book
57 N6042ff71440344198412f8f7341889de schema:name readcube_id
58 schema:value d569815334364c3c8dbdc7e9047df1354daa728aab388ecb32849e9d31cd2316
59 rdf:type schema:PropertyValue
60 N60fff7c5d6e24db9b9746dda42a79e17 schema:familyName Mazzara
61 schema:givenName Manuel
62 rdf:type schema:Person
63 N7deff2a27cc448849cea77139ff74a43 rdf:first N60fff7c5d6e24db9b9746dda42a79e17
64 rdf:rest N97cdf89e7a7a47edbe150fa850a7df18
65 N7f1b935934514c1eaca4098605ec5f9f schema:name Springer Nature - SN SciGraph project
66 rdf:type schema:Organization
67 N894212fce5ae449288fac08429ec9330 schema:location Cham
68 schema:name Springer International Publishing
69 rdf:type schema:Organisation
70 N97cdf89e7a7a47edbe150fa850a7df18 rdf:first Nff070d5daecd4174ad42d073bcce5174
71 rdf:rest rdf:nil
72 Nb52fbc2accc44e73a909b0ebedab10f8 rdf:first sg:person.010754010217.31
73 rdf:rest rdf:nil
74 Ne8b7844e15a44116bfd5c1b701fd2faa schema:name doi
75 schema:value 10.1007/978-3-319-41579-6_11
76 rdf:type schema:PropertyValue
77 Nff070d5daecd4174ad42d073bcce5174 schema:familyName Voronkov
78 schema:givenName Andrei
79 rdf:type schema:Person
80 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
81 schema:name Mathematical Sciences
82 rdf:type schema:DefinedTerm
83 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
84 schema:name Pure Mathematics
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/3-540-47018-2_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013466468
92 https://doi.org/10.1007/3-540-47018-2_2
93 rdf:type schema:CreativeWork
94 sg:pub.10.1007/3-540-51237-3_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007169098
95 https://doi.org/10.1007/3-540-51237-3_11
96 rdf:type schema:CreativeWork
97 sg:pub.10.1007/3-540-57264-3_34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003987904
98 https://doi.org/10.1007/3-540-57264-3_34
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/978-0-387-68954-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003866047
107 https://doi.org/10.1007/978-0-387-68954-8
108 rdf:type schema:CreativeWork
109 sg:pub.10.1007/978-3-319-40946-7_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046041225
110 https://doi.org/10.1007/978-3-319-40946-7_10
111 rdf:type schema:CreativeWork
112 sg:pub.10.1007/bf00271642 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053177031
113 https://doi.org/10.1007/bf00271642
114 rdf:type schema:CreativeWork
115 sg:pub.10.1007/bf03037260 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000035698
116 https://doi.org/10.1007/bf03037260
117 rdf:type schema:CreativeWork
118 https://app.dimensions.ai/details/publication/pub.1003866047 schema:CreativeWork
119 https://doi.org/10.1002/spe.1086 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005085336
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1002/zamm.19790590233 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052840008
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1016/0020-0190(77)90022-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033910504
124 rdf:type schema:CreativeWork
125 https://doi.org/10.1016/0020-0190(77)90078-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016252608
126 rdf:type schema:CreativeWork
127 https://doi.org/10.1016/0020-0190(83)90124-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012264779
128 rdf:type schema:CreativeWork
129 https://doi.org/10.1016/0020-0190(89)90113-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028126397
130 rdf:type schema:CreativeWork
131 https://doi.org/10.1016/s0019-9958(68)91087-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013914005
132 rdf:type schema:CreativeWork
133 https://doi.org/10.1017/s0956796800002008 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042426034
134 rdf:type schema:CreativeWork
135 https://doi.org/10.1137/0206024 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841363
136 rdf:type schema:CreativeWork
137 https://doi.org/10.1145/1146809.1146812 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050414528
138 rdf:type schema:CreativeWork
139 https://doi.org/10.1145/154630.154637 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034160022
140 rdf:type schema:CreativeWork
141 https://doi.org/10.1145/568173.568174 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046476890
142 rdf:type schema:CreativeWork
143 https://doi.org/10.1145/963778.963784 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010449995
144 rdf:type schema:CreativeWork
145 https://www.grid.ac/institutes/grid.5254.6 schema:alternateName University of Copenhagen
146 schema:name DIKU, Department of Computer Science, University of Copenhagen
147 rdf:type schema:Organization
 




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


...