A Program Inverter for a Functional Language with Equality and Constructors View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2003

AUTHORS

Robert Glück , Masahiko Kawabe

ABSTRACT

We present a method for automatic program inversion in a first-order functional programming language. We formalize the transformation and illustrate it with several examples including the automatic derivation of a program for run-length decoding from a program for run-length encoding. This derivation is not possible with other automatic program inversion methods. One of our key observations is that the duplication of values and testing of their equality are two sides of the same coin in program inversion. This leads us to the design of a new self-inverse primitive function that considerably simplifies the automatic inversion of programs. More... »

PAGES

246-264

References to SciGraph publications

  • 1989. InvX: An automatic function inverter in REWRITING TECHNIQUES AND APPLICATIONS
  • 1996. Program transformation with metasystem transitions: Experiments with a supercompiler in PERSPECTIVES OF SYSTEM INFORMATICS
  • 1981. The Science of Programming in NONE
  • 1979. Program inversion in PROGRAM CONSTRUCTION
  • 2002. Inverting Functions as Folds in MATHEMATICS OF PROGRAM CONSTRUCTION
  • 2002. Principles of Inverse Computation and the Universal Resolving Algorithm in THE ESSENCE OF COMPUTATION
  • Book

    TITLE

    Programming Languages and Systems

    ISBN

    978-3-540-20536-4
    978-3-540-40018-9

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-540-40018-9_17

    DOI

    http://dx.doi.org/10.1007/978-3-540-40018-9_17

    DIMENSIONS

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


    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": "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, 169-8555, Tokyo, 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": [
                "Graduate School of Science and Engineering, Waseda University, 169-8555, Tokyo, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kawabe", 
            "givenName": "Masahiko", 
            "id": "sg:person.07742561737.94", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07742561737.94"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-62064-8_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007045901", 
              "https://doi.org/10.1007/3-540-62064-8_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/spe.4380170703", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010678908"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0167-6423(02)00023-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015470010"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/s0956796800000757", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016061186"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0014657", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017699924", 
              "https://doi.org/10.1007/bfb0014657"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0004-3702(81)90014-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019380670"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0004-3702(81)90014-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019380670"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/115865.115868", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024461452"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/347823.347828", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028820328"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/5001.5005", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029409176"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45442-x_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030504036", 
              "https://doi.org/10.1007/3-540-45442-x_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/777388.777391", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041853059"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/s0956796800002008", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042426034"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/96877.96953", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043736510"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4612-5983-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045860299", 
              "https://doi.org/10.1007/978-1-4612-5983-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4612-5983-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045860299", 
              "https://doi.org/10.1007/978-1-4612-5983-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-36377-7_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051401164", 
              "https://doi.org/10.1007/3-540-36377-7_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-51081-8_139", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053186517", 
              "https://doi.org/10.1007/3-540-51081-8_139"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2003", 
        "datePublishedReg": "2003-01-01", 
        "description": "We present a method for automatic program inversion in a first-order functional programming language. We formalize the transformation and illustrate it with several examples including the automatic derivation of a program for run-length decoding from a program for run-length encoding. This derivation is not possible with other automatic program inversion methods. One of our key observations is that the duplication of values and testing of their equality are two sides of the same coin in program inversion. This leads us to the design of a new self-inverse primitive function that considerably simplifies the automatic inversion of programs.", 
        "editor": [
          {
            "familyName": "Ohori", 
            "givenName": "Atsushi", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-540-40018-9_17", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-20536-4", 
            "978-3-540-40018-9"
          ], 
          "name": "Programming Languages and Systems", 
          "type": "Book"
        }, 
        "name": "A Program Inverter for a Functional Language with Equality and Constructors", 
        "pagination": "246-264", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1012065324"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-540-40018-9_17"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "397c1f214116ffecab081e92fcc4ef9e37ae79f61d49b2b1a6674b8bbace384d"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-540-40018-9_17", 
          "https://app.dimensions.ai/details/publication/pub.1012065324"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T08:17", 
        "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/0000000362_0000000362/records_87083_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-540-40018-9_17"
      }
    ]
     

    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-540-40018-9_17'

    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-540-40018-9_17'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-40018-9_17'

    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-540-40018-9_17'


     

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

    127 TRIPLES      23 PREDICATES      43 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-540-40018-9_17 schema:about anzsrc-for:08
    2 anzsrc-for:0803
    3 schema:author N0da4ba077f684728acb88897b05e8dd6
    4 schema:citation sg:pub.10.1007/3-540-36377-7_13
    5 sg:pub.10.1007/3-540-45442-x_13
    6 sg:pub.10.1007/3-540-51081-8_139
    7 sg:pub.10.1007/3-540-62064-8_21
    8 sg:pub.10.1007/978-1-4612-5983-1
    9 sg:pub.10.1007/bfb0014657
    10 https://doi.org/10.1002/spe.4380170703
    11 https://doi.org/10.1016/0004-3702(81)90014-x
    12 https://doi.org/10.1016/s0167-6423(02)00023-0
    13 https://doi.org/10.1017/s0956796800000757
    14 https://doi.org/10.1017/s0956796800002008
    15 https://doi.org/10.1145/115865.115868
    16 https://doi.org/10.1145/347823.347828
    17 https://doi.org/10.1145/5001.5005
    18 https://doi.org/10.1145/777388.777391
    19 https://doi.org/10.1145/96877.96953
    20 schema:datePublished 2003
    21 schema:datePublishedReg 2003-01-01
    22 schema:description We present a method for automatic program inversion in a first-order functional programming language. We formalize the transformation and illustrate it with several examples including the automatic derivation of a program for run-length decoding from a program for run-length encoding. This derivation is not possible with other automatic program inversion methods. One of our key observations is that the duplication of values and testing of their equality are two sides of the same coin in program inversion. This leads us to the design of a new self-inverse primitive function that considerably simplifies the automatic inversion of programs.
    23 schema:editor Nf2daa917598d425aa4355f8359248f10
    24 schema:genre chapter
    25 schema:inLanguage en
    26 schema:isAccessibleForFree true
    27 schema:isPartOf N548355ba36ba44538fca49da63f9bc9e
    28 schema:name A Program Inverter for a Functional Language with Equality and Constructors
    29 schema:pagination 246-264
    30 schema:productId N2838ba1a5d3c4b859229b596f2f55dbc
    31 N5060bfe60b964bf9bdf254489b7d380c
    32 Nb67db03fb05045c2b00834f97a9fb888
    33 schema:publisher N6f1f947bc30e44f7aa9a95276e15a258
    34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012065324
    35 https://doi.org/10.1007/978-3-540-40018-9_17
    36 schema:sdDatePublished 2019-04-16T08:17
    37 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    38 schema:sdPublisher Nd5872636302d4cb097619aecc1040932
    39 schema:url https://link.springer.com/10.1007%2F978-3-540-40018-9_17
    40 sgo:license sg:explorer/license/
    41 sgo:sdDataset chapters
    42 rdf:type schema:Chapter
    43 N0da4ba077f684728acb88897b05e8dd6 rdf:first sg:person.010754010217.31
    44 rdf:rest N160693a316f8487e98c88e67981fe72c
    45 N160693a316f8487e98c88e67981fe72c rdf:first sg:person.07742561737.94
    46 rdf:rest rdf:nil
    47 N2838ba1a5d3c4b859229b596f2f55dbc schema:name dimensions_id
    48 schema:value pub.1012065324
    49 rdf:type schema:PropertyValue
    50 N5060bfe60b964bf9bdf254489b7d380c schema:name doi
    51 schema:value 10.1007/978-3-540-40018-9_17
    52 rdf:type schema:PropertyValue
    53 N548355ba36ba44538fca49da63f9bc9e schema:isbn 978-3-540-20536-4
    54 978-3-540-40018-9
    55 schema:name Programming Languages and Systems
    56 rdf:type schema:Book
    57 N6f1f947bc30e44f7aa9a95276e15a258 schema:location Berlin, Heidelberg
    58 schema:name Springer Berlin Heidelberg
    59 rdf:type schema:Organisation
    60 Na2a46f76db324f21940a183b173080bc schema:familyName Ohori
    61 schema:givenName Atsushi
    62 rdf:type schema:Person
    63 Nb67db03fb05045c2b00834f97a9fb888 schema:name readcube_id
    64 schema:value 397c1f214116ffecab081e92fcc4ef9e37ae79f61d49b2b1a6674b8bbace384d
    65 rdf:type schema:PropertyValue
    66 Nd5872636302d4cb097619aecc1040932 schema:name Springer Nature - SN SciGraph project
    67 rdf:type schema:Organization
    68 Nf2daa917598d425aa4355f8359248f10 rdf:first Na2a46f76db324f21940a183b173080bc
    69 rdf:rest rdf:nil
    70 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    71 schema:name Information and Computing Sciences
    72 rdf:type schema:DefinedTerm
    73 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
    74 schema:name Computer Software
    75 rdf:type schema:DefinedTerm
    76 sg:person.010754010217.31 schema:affiliation https://www.grid.ac/institutes/grid.5290.e
    77 schema:familyName Glück
    78 schema:givenName Robert
    79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010754010217.31
    80 rdf:type schema:Person
    81 sg:person.07742561737.94 schema:affiliation https://www.grid.ac/institutes/grid.5290.e
    82 schema:familyName Kawabe
    83 schema:givenName Masahiko
    84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07742561737.94
    85 rdf:type schema:Person
    86 sg:pub.10.1007/3-540-36377-7_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051401164
    87 https://doi.org/10.1007/3-540-36377-7_13
    88 rdf:type schema:CreativeWork
    89 sg:pub.10.1007/3-540-45442-x_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030504036
    90 https://doi.org/10.1007/3-540-45442-x_13
    91 rdf:type schema:CreativeWork
    92 sg:pub.10.1007/3-540-51081-8_139 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053186517
    93 https://doi.org/10.1007/3-540-51081-8_139
    94 rdf:type schema:CreativeWork
    95 sg:pub.10.1007/3-540-62064-8_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007045901
    96 https://doi.org/10.1007/3-540-62064-8_21
    97 rdf:type schema:CreativeWork
    98 sg:pub.10.1007/978-1-4612-5983-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045860299
    99 https://doi.org/10.1007/978-1-4612-5983-1
    100 rdf:type schema:CreativeWork
    101 sg:pub.10.1007/bfb0014657 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017699924
    102 https://doi.org/10.1007/bfb0014657
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1002/spe.4380170703 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010678908
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1016/0004-3702(81)90014-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1019380670
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1016/s0167-6423(02)00023-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015470010
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1017/s0956796800000757 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016061186
    111 rdf:type schema:CreativeWork
    112 https://doi.org/10.1017/s0956796800002008 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042426034
    113 rdf:type schema:CreativeWork
    114 https://doi.org/10.1145/115865.115868 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024461452
    115 rdf:type schema:CreativeWork
    116 https://doi.org/10.1145/347823.347828 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028820328
    117 rdf:type schema:CreativeWork
    118 https://doi.org/10.1145/5001.5005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029409176
    119 rdf:type schema:CreativeWork
    120 https://doi.org/10.1145/777388.777391 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041853059
    121 rdf:type schema:CreativeWork
    122 https://doi.org/10.1145/96877.96953 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043736510
    123 rdf:type schema:CreativeWork
    124 https://www.grid.ac/institutes/grid.5290.e schema:alternateName Waseda University
    125 schema:name Graduate School of Science and Engineering, Waseda University, 169-8555, Tokyo, Japan
    126 PRESTO, JST & Institute for Software Production Technology, Waseda University, School of Science and Engineering, 169-8555, Tokyo, Japan
    127 rdf:type schema:Organization
     




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


    ...