On Deforesting Parameters of Accumulating Maps View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2002

AUTHORS

Kazuhiko Kakehi , Robert Glück , Yoshihiko Futamura

ABSTRACT

Deforestation is a well-known program transformation technique which eliminates intermediate data structures that are passed between functions. One of its weaknesses is the inability to deforest programs using accumulating parameters. We show how intermediate lists built by a selected class of functional programs, namely ‘accumulating maps’, can be deforested using a single composition rule. For this we introduce a new function dmap, a symmetric extension of the familiar function map. While the associated composition rule cannot capture all deforestation problems, it can handle accumulator fusion of functions defined in terms of dmap in a surprisingly simple way. The rule for accumulator fusion presented here can also be viewed as a restricted composition scheme for attribute grammars, which in turn may help us to bridge the gap between the attribute and functional world. More... »

PAGES

46-56

References to SciGraph publications

  • 1999. Declarative Program Transformation: A Deforestation Case-Study in PRINCIPLES AND PRACTICE OF DECLARATIVE PROGRAMMING
  • 1999. Comparison of Deforestation Techniques for Functional Programs and for Tree Transducers in FUNCTIONAL AND LOGIC PROGRAMMING
  • 1988-05. Composition and evaluation of attribute coupled grammars in ACTA INFORMATICA
  • 1999-06. Calculating accumulations in NEW GENERATION COMPUTING
  • 2001. Relating Accumulative and Non-accumulative Functional Programs in REWRITING TECHNIQUES AND APPLICATIONS
  • Book

    TITLE

    Logic Based Program Synthesis and Transformation

    ISBN

    978-3-540-43915-8
    978-3-540-45607-0

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-45607-4_3

    DOI

    http://dx.doi.org/10.1007/3-540-45607-4_3

    DIMENSIONS

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


    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/1109", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Neurosciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/11", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Medical and Health Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Tokyo", 
              "id": "https://www.grid.ac/institutes/grid.26999.3d", 
              "name": [
                "Graduate School of Information Science and Technology, The University of Tokyo, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kakehi", 
            "givenName": "Kazuhiko", 
            "id": "sg:person.012530056042.57", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012530056042.57"
            ], 
            "type": "Person"
          }, 
          {
            "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, Tokyo\u00a0169-8555, 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"
          }, 
          {
            "affiliation": {
              "alternateName": "Waseda University", 
              "id": "https://www.grid.ac/institutes/grid.5290.e", 
              "name": [
                "Institute for Software Production Technology, Waseda University, School of Science and Engineering, Tokyo\u00a0169-8555, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Futamura", 
            "givenName": "Yoshihiko", 
            "id": "sg:person.016641004255.43", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016641004255.43"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf03037434", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008443130", 
              "https://doi.org/10.1007/bf03037434"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf03037434", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008443130", 
              "https://doi.org/10.1007/bf03037434"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/5956.5957", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016193336"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45127-7_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019075739", 
              "https://doi.org/10.1007/3-540-45127-7_13"
            ], 
            "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/10704567_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021960452", 
              "https://doi.org/10.1007/10704567_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/10704567_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021960452", 
              "https://doi.org/10.1007/10704567_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/267959.267960", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026272973"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/322169.322183", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026827486"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/227699.227716", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027084717"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/10705424_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039244083", 
              "https://doi.org/10.1007/10705424_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/10705424_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039244083", 
              "https://doi.org/10.1007/10705424_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02737108", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039434342", 
              "https://doi.org/10.1007/bf02737108"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02737108", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039434342", 
              "https://doi.org/10.1007/bf02737108"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0167-6423(83)90021-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043873783"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/321992.321996", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046318040"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2002", 
        "datePublishedReg": "2002-01-01", 
        "description": "Deforestation is a well-known program transformation technique which eliminates intermediate data structures that are passed between functions. One of its weaknesses is the inability to deforest programs using accumulating parameters. We show how intermediate lists built by a selected class of functional programs, namely \u2018accumulating maps\u2019, can be deforested using a single composition rule. For this we introduce a new function dmap, a symmetric extension of the familiar function map. While the associated composition rule cannot capture all deforestation problems, it can handle accumulator fusion of functions defined in terms of dmap in a surprisingly simple way. The rule for accumulator fusion presented here can also be viewed as a restricted composition scheme for attribute grammars, which in turn may help us to bridge the gap between the attribute and functional world.", 
        "editor": [
          {
            "familyName": "Pettorossi", 
            "givenName": "Alberto", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-45607-4_3", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-43915-8", 
            "978-3-540-45607-0"
          ], 
          "name": "Logic Based Program Synthesis and Transformation", 
          "type": "Book"
        }, 
        "name": "On Deforesting Parameters of Accumulating Maps", 
        "pagination": "46-56", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-45607-4_3"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "b039734c470d1ebdd41462fda615216217a1f75835ebccf377d21cb85c1d69d0"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1036993509"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-45607-4_3", 
          "https://app.dimensions.ai/details/publication/pub.1036993509"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T14:26", 
        "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_8669_00000266.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/3-540-45607-4_3"
      }
    ]
     

    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/3-540-45607-4_3'

    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/3-540-45607-4_3'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-45607-4_3'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-45607-4_3'


     

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

    124 TRIPLES      23 PREDICATES      39 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-45607-4_3 schema:about anzsrc-for:11
    2 anzsrc-for:1109
    3 schema:author N7e4b710cfbe440f3b63cb4cd7da051a8
    4 schema:citation sg:pub.10.1007/10704567_22
    5 sg:pub.10.1007/10705424_8
    6 sg:pub.10.1007/3-540-45127-7_13
    7 sg:pub.10.1007/bf02737108
    8 sg:pub.10.1007/bf03037434
    9 https://doi.org/10.1016/0167-6423(83)90021-7
    10 https://doi.org/10.1016/0304-3975(90)90147-a
    11 https://doi.org/10.1145/227699.227716
    12 https://doi.org/10.1145/267959.267960
    13 https://doi.org/10.1145/321992.321996
    14 https://doi.org/10.1145/322169.322183
    15 https://doi.org/10.1145/5956.5957
    16 schema:datePublished 2002
    17 schema:datePublishedReg 2002-01-01
    18 schema:description Deforestation is a well-known program transformation technique which eliminates intermediate data structures that are passed between functions. One of its weaknesses is the inability to deforest programs using accumulating parameters. We show how intermediate lists built by a selected class of functional programs, namely ‘accumulating maps’, can be deforested using a single composition rule. For this we introduce a new function dmap, a symmetric extension of the familiar function map. While the associated composition rule cannot capture all deforestation problems, it can handle accumulator fusion of functions defined in terms of dmap in a surprisingly simple way. The rule for accumulator fusion presented here can also be viewed as a restricted composition scheme for attribute grammars, which in turn may help us to bridge the gap between the attribute and functional world.
    19 schema:editor Nd93abed6f58f48ba8deaf336f98fd24b
    20 schema:genre chapter
    21 schema:inLanguage en
    22 schema:isAccessibleForFree false
    23 schema:isPartOf N0c89d43826504e338a91771d18e2d40d
    24 schema:name On Deforesting Parameters of Accumulating Maps
    25 schema:pagination 46-56
    26 schema:productId N02119744a1104f1da9d5d07ed6c38c2c
    27 N345f8a7796634a4e9929fc727c2c38b0
    28 Ncfa47e8e8c1549d790837fe76d267475
    29 schema:publisher N5135887a8cbb4925aab3932dc4770473
    30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036993509
    31 https://doi.org/10.1007/3-540-45607-4_3
    32 schema:sdDatePublished 2019-04-15T14:26
    33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    34 schema:sdPublisher N81d9ccf74815470983f95eed2264931f
    35 schema:url http://link.springer.com/10.1007/3-540-45607-4_3
    36 sgo:license sg:explorer/license/
    37 sgo:sdDataset chapters
    38 rdf:type schema:Chapter
    39 N02119744a1104f1da9d5d07ed6c38c2c schema:name dimensions_id
    40 schema:value pub.1036993509
    41 rdf:type schema:PropertyValue
    42 N0c89d43826504e338a91771d18e2d40d schema:isbn 978-3-540-43915-8
    43 978-3-540-45607-0
    44 schema:name Logic Based Program Synthesis and Transformation
    45 rdf:type schema:Book
    46 N345f8a7796634a4e9929fc727c2c38b0 schema:name readcube_id
    47 schema:value b039734c470d1ebdd41462fda615216217a1f75835ebccf377d21cb85c1d69d0
    48 rdf:type schema:PropertyValue
    49 N5135887a8cbb4925aab3932dc4770473 schema:location Berlin, Heidelberg
    50 schema:name Springer Berlin Heidelberg
    51 rdf:type schema:Organisation
    52 N5ea9e4674e81428f846d8c94e403225c rdf:first sg:person.010754010217.31
    53 rdf:rest Nbf0a0e62ae1f4897a371c9d623caa347
    54 N7e4b710cfbe440f3b63cb4cd7da051a8 rdf:first sg:person.012530056042.57
    55 rdf:rest N5ea9e4674e81428f846d8c94e403225c
    56 N81d9ccf74815470983f95eed2264931f schema:name Springer Nature - SN SciGraph project
    57 rdf:type schema:Organization
    58 Nbf0a0e62ae1f4897a371c9d623caa347 rdf:first sg:person.016641004255.43
    59 rdf:rest rdf:nil
    60 Nc32bcbfb0e064b498eedbc06a6299713 schema:familyName Pettorossi
    61 schema:givenName Alberto
    62 rdf:type schema:Person
    63 Ncfa47e8e8c1549d790837fe76d267475 schema:name doi
    64 schema:value 10.1007/3-540-45607-4_3
    65 rdf:type schema:PropertyValue
    66 Nd93abed6f58f48ba8deaf336f98fd24b rdf:first Nc32bcbfb0e064b498eedbc06a6299713
    67 rdf:rest rdf:nil
    68 anzsrc-for:11 schema:inDefinedTermSet anzsrc-for:
    69 schema:name Medical and Health Sciences
    70 rdf:type schema:DefinedTerm
    71 anzsrc-for:1109 schema:inDefinedTermSet anzsrc-for:
    72 schema:name Neurosciences
    73 rdf:type schema:DefinedTerm
    74 sg:person.010754010217.31 schema:affiliation https://www.grid.ac/institutes/grid.5290.e
    75 schema:familyName Glück
    76 schema:givenName Robert
    77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010754010217.31
    78 rdf:type schema:Person
    79 sg:person.012530056042.57 schema:affiliation https://www.grid.ac/institutes/grid.26999.3d
    80 schema:familyName Kakehi
    81 schema:givenName Kazuhiko
    82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012530056042.57
    83 rdf:type schema:Person
    84 sg:person.016641004255.43 schema:affiliation https://www.grid.ac/institutes/grid.5290.e
    85 schema:familyName Futamura
    86 schema:givenName Yoshihiko
    87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016641004255.43
    88 rdf:type schema:Person
    89 sg:pub.10.1007/10704567_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021960452
    90 https://doi.org/10.1007/10704567_22
    91 rdf:type schema:CreativeWork
    92 sg:pub.10.1007/10705424_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039244083
    93 https://doi.org/10.1007/10705424_8
    94 rdf:type schema:CreativeWork
    95 sg:pub.10.1007/3-540-45127-7_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019075739
    96 https://doi.org/10.1007/3-540-45127-7_13
    97 rdf:type schema:CreativeWork
    98 sg:pub.10.1007/bf02737108 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039434342
    99 https://doi.org/10.1007/bf02737108
    100 rdf:type schema:CreativeWork
    101 sg:pub.10.1007/bf03037434 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008443130
    102 https://doi.org/10.1007/bf03037434
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1016/0167-6423(83)90021-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043873783
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1016/0304-3975(90)90147-a schema:sameAs https://app.dimensions.ai/details/publication/pub.1019824477
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1145/227699.227716 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027084717
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1145/267959.267960 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026272973
    111 rdf:type schema:CreativeWork
    112 https://doi.org/10.1145/321992.321996 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046318040
    113 rdf:type schema:CreativeWork
    114 https://doi.org/10.1145/322169.322183 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026827486
    115 rdf:type schema:CreativeWork
    116 https://doi.org/10.1145/5956.5957 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016193336
    117 rdf:type schema:CreativeWork
    118 https://www.grid.ac/institutes/grid.26999.3d schema:alternateName University of Tokyo
    119 schema:name Graduate School of Information Science and Technology, The University of Tokyo, Japan
    120 rdf:type schema:Organization
    121 https://www.grid.ac/institutes/grid.5290.e schema:alternateName Waseda University
    122 schema:name Institute for Software Production Technology, Waseda University, School of Science and Engineering, Tokyo 169-8555, Japan
    123 PRESTO, JST & Institute for Software Production Technology, Waseda University, School of Science and Engineering, Tokyo 169-8555, Japan
    124 rdf:type schema:Organization
     




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


    ...