Towards a Reversible Functional Language View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2012

AUTHORS

Tetsuo Yokoyama , Holger Bock Axelsen , Robert Glück

ABSTRACT

We identify concepts of reversibility for a functional language by means of a set of semantic rules with specific properties. These properties include injectivity along with local backward determinism, an important operational property for an efficient reversible language. We define a concise reversible first-order functional language in which access to the backward semantics is provided to the programmer by inverse function calls. Reversibility guarantees that in this language a backward run (inverse interpretation) is as fast as the corresponding forward run itself. By adopting a symmetric first-match policy for case expressions, we can write overlapping patterns in case branches, as is customary in ordinary functional languages, and also in leaf expressions, unlike existing inverse interpreter methods, which enables concise programs. In patterns, the use of a duplication/equality operator also simplifies inverse computation and program inversion. We discuss the advantages of a reversible functional language using example programs, including run-length encoding. Program inversion is seen to be as lightweight as for imperative reversible languages and realized by recursive descent. Finally, we show that the proposed language is r-Turing complete. More... »

PAGES

14-29

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-29517-1_2

DOI

http://dx.doi.org/10.1007/978-3-642-29517-1_2

DIMENSIONS

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


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/20", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Language, Communication and Culture", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/2004", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Linguistics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Software Engineering, Nanzan University, Japan", 
          "id": "http://www.grid.ac/institutes/grid.444385.a", 
          "name": [
            "Department of Software Engineering, Nanzan University, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yokoyama", 
        "givenName": "Tetsuo", 
        "id": "sg:person.015342016423.59", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015342016423.59"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "DIKU, Department of Computer Science, University of Copenhagen, Denmark", 
          "id": "http://www.grid.ac/institutes/grid.5254.6", 
          "name": [
            "DIKU, Department of Computer Science, University of Copenhagen, Denmark"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Axelsen", 
        "givenName": "Holger Bock", 
        "id": "sg:person.015546427711.73", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015546427711.73"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "DIKU, Department of Computer Science, University of Copenhagen, Denmark", 
          "id": "http://www.grid.ac/institutes/grid.5254.6", 
          "name": [
            "DIKU, Department of Computer Science, University of 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"
      }
    ], 
    "datePublished": "2012", 
    "datePublishedReg": "2012-01-01", 
    "description": "We identify concepts of reversibility for a functional language by means of a set of semantic rules with specific properties. These properties include injectivity along with local backward determinism, an important operational property for an efficient reversible language. We define a concise reversible first-order functional language in which access to the backward semantics is provided to the programmer by inverse function calls. Reversibility guarantees that in this language a backward run (inverse interpretation) is as fast as the corresponding forward run itself. By adopting a symmetric first-match policy for case expressions, we can write overlapping patterns in case branches, as is customary in ordinary functional languages, and also in leaf expressions, unlike existing inverse interpreter methods, which enables concise programs. In patterns, the use of a duplication/equality operator also simplifies inverse computation and program inversion. We discuss the advantages of a reversible functional language using example programs, including run-length encoding. Program inversion is seen to be as lightweight as for imperative reversible languages and realized by recursive descent. Finally, we show that the proposed language is r-Turing complete.", 
    "editor": [
      {
        "familyName": "De Vos", 
        "givenName": "Alexis", 
        "type": "Person"
      }, 
      {
        "familyName": "Wille", 
        "givenName": "Robert", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-29517-1_2", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-29516-4", 
        "978-3-642-29517-1"
      ], 
      "name": "Reversible Computation", 
      "type": "Book"
    }, 
    "keywords": [
      "reversible functional language", 
      "functional language", 
      "reversible languages", 
      "first-match policy", 
      "first-order functional language", 
      "important operational properties", 
      "language", 
      "backward determinism", 
      "backward semantics", 
      "program inversion", 
      "concise programs", 
      "case branches", 
      "semantic rules", 
      "equality operator", 
      "backward runs", 
      "concept of reversibility", 
      "recursive descent", 
      "cases expression", 
      "leaf expression", 
      "example programs", 
      "semantics", 
      "determinism", 
      "calls", 
      "concept", 
      "descent", 
      "function calls", 
      "programmers", 
      "policy", 
      "inverse computation", 
      "program", 
      "rules", 
      "encoding", 
      "access", 
      "specific properties", 
      "means", 
      "use", 
      "patterns", 
      "expression", 
      "run-length encoding", 
      "Complete", 
      "set", 
      "branches", 
      "inversion", 
      "run", 
      "advantages", 
      "method", 
      "properties", 
      "operational properties", 
      "operators", 
      "computation", 
      "reversibility", 
      "injectivity", 
      "local backward determinism", 
      "efficient reversible language", 
      "concise reversible first-order functional language", 
      "reversible first-order functional language", 
      "inverse function calls", 
      "symmetric first-match policy", 
      "ordinary functional languages", 
      "inverse interpreter methods", 
      "interpreter methods", 
      "duplication/equality operator", 
      "imperative reversible languages", 
      "Turing complete"
    ], 
    "name": "Towards a Reversible Functional Language", 
    "pagination": "14-29", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1029572889"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-29517-1_2"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-29517-1_2", 
      "https://app.dimensions.ai/details/publication/pub.1029572889"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:55", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_312.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-29517-1_2"
  }
]
 

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-642-29517-1_2'

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-642-29517-1_2'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-29517-1_2'

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-642-29517-1_2'


 

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

146 TRIPLES      23 PREDICATES      90 URIs      83 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-29517-1_2 schema:about anzsrc-for:20
2 anzsrc-for:2004
3 schema:author N721bc80e660749bf872714313b73dd96
4 schema:datePublished 2012
5 schema:datePublishedReg 2012-01-01
6 schema:description We identify concepts of reversibility for a functional language by means of a set of semantic rules with specific properties. These properties include injectivity along with local backward determinism, an important operational property for an efficient reversible language. We define a concise reversible first-order functional language in which access to the backward semantics is provided to the programmer by inverse function calls. Reversibility guarantees that in this language a backward run (inverse interpretation) is as fast as the corresponding forward run itself. By adopting a symmetric first-match policy for case expressions, we can write overlapping patterns in case branches, as is customary in ordinary functional languages, and also in leaf expressions, unlike existing inverse interpreter methods, which enables concise programs. In patterns, the use of a duplication/equality operator also simplifies inverse computation and program inversion. We discuss the advantages of a reversible functional language using example programs, including run-length encoding. Program inversion is seen to be as lightweight as for imperative reversible languages and realized by recursive descent. Finally, we show that the proposed language is r-Turing complete.
7 schema:editor N730b74e7512d4b3eb8c292a40256c345
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Neaf45fe700504a689820bdf97d24ce3a
12 schema:keywords Complete
13 Turing complete
14 access
15 advantages
16 backward determinism
17 backward runs
18 backward semantics
19 branches
20 calls
21 case branches
22 cases expression
23 computation
24 concept
25 concept of reversibility
26 concise programs
27 concise reversible first-order functional language
28 descent
29 determinism
30 duplication/equality operator
31 efficient reversible language
32 encoding
33 equality operator
34 example programs
35 expression
36 first-match policy
37 first-order functional language
38 function calls
39 functional language
40 imperative reversible languages
41 important operational properties
42 injectivity
43 interpreter methods
44 inverse computation
45 inverse function calls
46 inverse interpreter methods
47 inversion
48 language
49 leaf expression
50 local backward determinism
51 means
52 method
53 operational properties
54 operators
55 ordinary functional languages
56 patterns
57 policy
58 program
59 program inversion
60 programmers
61 properties
62 recursive descent
63 reversibility
64 reversible first-order functional language
65 reversible functional language
66 reversible languages
67 rules
68 run
69 run-length encoding
70 semantic rules
71 semantics
72 set
73 specific properties
74 symmetric first-match policy
75 use
76 schema:name Towards a Reversible Functional Language
77 schema:pagination 14-29
78 schema:productId N60e6f88056f5460eb95e7950a5552ecd
79 N9869f5c7006a44649fa61f7f2c3a7196
80 schema:publisher N1b61095cf8914cff97580522032d5a10
81 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029572889
82 https://doi.org/10.1007/978-3-642-29517-1_2
83 schema:sdDatePublished 2021-11-01T18:55
84 schema:sdLicense https://scigraph.springernature.com/explorer/license/
85 schema:sdPublisher Nb975122dd78643778dbc95738b53cbf7
86 schema:url https://doi.org/10.1007/978-3-642-29517-1_2
87 sgo:license sg:explorer/license/
88 sgo:sdDataset chapters
89 rdf:type schema:Chapter
90 N0779ba83a96a4cdb96d5daa7605490e9 rdf:first sg:person.010754010217.31
91 rdf:rest rdf:nil
92 N1a871ab26f2949d5a2a01d531f396dc3 schema:familyName De Vos
93 schema:givenName Alexis
94 rdf:type schema:Person
95 N1b61095cf8914cff97580522032d5a10 schema:name Springer Nature
96 rdf:type schema:Organisation
97 N60e6f88056f5460eb95e7950a5552ecd schema:name doi
98 schema:value 10.1007/978-3-642-29517-1_2
99 rdf:type schema:PropertyValue
100 N721bc80e660749bf872714313b73dd96 rdf:first sg:person.015342016423.59
101 rdf:rest Nc127091baff042ad9dca990264ab8847
102 N730b74e7512d4b3eb8c292a40256c345 rdf:first N1a871ab26f2949d5a2a01d531f396dc3
103 rdf:rest Nbbf6f58120ac44c4add5f6f4b89d55b0
104 N9869f5c7006a44649fa61f7f2c3a7196 schema:name dimensions_id
105 schema:value pub.1029572889
106 rdf:type schema:PropertyValue
107 Nb975122dd78643778dbc95738b53cbf7 schema:name Springer Nature - SN SciGraph project
108 rdf:type schema:Organization
109 Nb9b972b9a011447c8c3955c3ce47f9b0 schema:familyName Wille
110 schema:givenName Robert
111 rdf:type schema:Person
112 Nbbf6f58120ac44c4add5f6f4b89d55b0 rdf:first Nb9b972b9a011447c8c3955c3ce47f9b0
113 rdf:rest rdf:nil
114 Nc127091baff042ad9dca990264ab8847 rdf:first sg:person.015546427711.73
115 rdf:rest N0779ba83a96a4cdb96d5daa7605490e9
116 Neaf45fe700504a689820bdf97d24ce3a schema:isbn 978-3-642-29516-4
117 978-3-642-29517-1
118 schema:name Reversible Computation
119 rdf:type schema:Book
120 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
121 schema:name Language, Communication and Culture
122 rdf:type schema:DefinedTerm
123 anzsrc-for:2004 schema:inDefinedTermSet anzsrc-for:
124 schema:name Linguistics
125 rdf:type schema:DefinedTerm
126 sg:person.010754010217.31 schema:affiliation grid-institutes:grid.5254.6
127 schema:familyName Glück
128 schema:givenName Robert
129 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010754010217.31
130 rdf:type schema:Person
131 sg:person.015342016423.59 schema:affiliation grid-institutes:grid.444385.a
132 schema:familyName Yokoyama
133 schema:givenName Tetsuo
134 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015342016423.59
135 rdf:type schema:Person
136 sg:person.015546427711.73 schema:affiliation grid-institutes:grid.5254.6
137 schema:familyName Axelsen
138 schema:givenName Holger Bock
139 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015546427711.73
140 rdf:type schema:Person
141 grid-institutes:grid.444385.a schema:alternateName Department of Software Engineering, Nanzan University, Japan
142 schema:name Department of Software Engineering, Nanzan University, Japan
143 rdf:type schema:Organization
144 grid-institutes:grid.5254.6 schema:alternateName DIKU, Department of Computer Science, University of Copenhagen, Denmark
145 schema:name DIKU, Department of Computer Science, University of Copenhagen, Denmark
146 rdf:type schema:Organization
 




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


...