NREVERSAL of fortune — The thermodynamics of garbage collection View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1992

AUTHORS

Henry G. Baker

ABSTRACT

The need to reverse a computation arises in many contexts—debugging, editor undoing, optimistic concurrency undoing, speculative computation undoing, trace scheduling, exception handling undoing, database recovery, optimistic discrete event simulations, subjunctive computing, etc. The need to analyze a reversed computation arises in the context of static analysis—liveness analysis, strictness analysis, type inference, etc. Traditional means for restoring a computation to a previous state involve checkpoints; checkpoints require time to copy, as well as space to store, the copied material. Traditional reverse abstract interpretation produces relatively poor information due to its inability to guess the previous values of assigned-to variables. We propose an abstract computer model and a programming language—Ψ-Lisp—whose primitive operations are injective and hence reversible, thus allowing arbitrary undoing without the overheads of checkpointing. Such a computer can be built from reversible conservative logic circuits, with the serendipitous advantage of dissipating far less heat than traditional Boolean AND/OR/NOT circuits. Unlike functional languages, which have one “state” for all times, Ψ-Lisp has at all times one “state”, with unique predecessor and successor states. Compiling into a reversible pseudocode can have benefits even when targeting a traditional computer. Certain optimizations, e.g., update-in-place, and compile-time garbage collection may be more easily performed, because the information may be elicited without the difficult and time-consuming iterative abstract interpretation required for most non-reversible models. In a reversible machine, garbage collection for recycling storage can always be performed by a reversed (sub)computation. While this “collection is reversed mutation” insight does not reduce space requirements when used for the computation as a whole, it does save space when used to recycle at finer scales. This insight also provides an explanation for the fundamental importance of the push-down stack both for recognizing palindromes and for managing storage. Reversible computers are related to Prolog, linear logic and chemical abstract machines. More... »

PAGES

507-524

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bfb0017210

DOI

http://dx.doi.org/10.1007/bfb0017210

DIMENSIONS

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


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/0803", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computer Software", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Nimble Computer Corporation, 16231 Meadow Ridge Way, 91436, Encino, California, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Nimble Computer Corporation, 16231 Meadow Ridge Way, 91436, Encino, California, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Baker", 
        "givenName": "Henry G.", 
        "type": "Person"
      }
    ], 
    "datePublished": "1992", 
    "datePublishedReg": "1992-01-01", 
    "description": "The need to reverse a computation arises in many contexts\u2014debugging, editor undoing, optimistic concurrency undoing, speculative computation undoing, trace scheduling, exception handling undoing, database recovery, optimistic discrete event simulations, subjunctive computing, etc. The need to analyze a reversed computation arises in the context of static analysis\u2014liveness analysis, strictness analysis, type inference, etc. Traditional means for restoring a computation to a previous state involve checkpoints; checkpoints require time to copy, as well as space to store, the copied material. Traditional reverse abstract interpretation produces relatively poor information due to its inability to guess the previous values of assigned-to variables. We propose an abstract computer model and a programming language\u2014\u03a8-Lisp\u2014whose primitive operations are injective and hence reversible, thus allowing arbitrary undoing without the overheads of checkpointing. Such a computer can be built from reversible conservative logic circuits, with the serendipitous advantage of dissipating far less heat than traditional Boolean AND/OR/NOT circuits. Unlike functional languages, which have one \u201cstate\u201d for all times, \u03a8-Lisp has at all times one \u201cstate\u201d, with unique predecessor and successor states. Compiling into a reversible pseudocode can have benefits even when targeting a traditional computer. Certain optimizations, e.g., update-in-place, and compile-time garbage collection may be more easily performed, because the information may be elicited without the difficult and time-consuming iterative abstract interpretation required for most non-reversible models. In a reversible machine, garbage collection for recycling storage can always be performed by a reversed (sub)computation. While this \u201ccollection is reversed mutation\u201d insight does not reduce space requirements when used for the computation as a whole, it does save space when used to recycle at finer scales. This insight also provides an explanation for the fundamental importance of the push-down stack both for recognizing palindromes and for managing storage. Reversible computers are related to Prolog, linear logic and chemical abstract machines.", 
    "editor": [
      {
        "familyName": "Bekkers", 
        "givenName": "Yves", 
        "type": "Person"
      }, 
      {
        "familyName": "Cohen", 
        "givenName": "Jacques", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/bfb0017210", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "3-540-55940-X"
      ], 
      "name": "Memory Management", 
      "type": "Book"
    }, 
    "keywords": [
      "garbage collection", 
      "abstract interpretation", 
      "compile-time garbage collection", 
      "discrete event simulation", 
      "Chemical Abstract Machine", 
      "programming language", 
      "traditional computers", 
      "database recovery", 
      "traditional Boolean", 
      "abstract machine", 
      "primitive operations", 
      "event simulation", 
      "functional language", 
      "certain optimizations", 
      "type inference", 
      "space requirements", 
      "computer", 
      "reversible computers", 
      "strictness analysis", 
      "Lisp", 
      "computation", 
      "trace scheduling", 
      "linear logic", 
      "machine", 
      "reversible machine", 
      "language", 
      "traditional means", 
      "computing", 
      "overhead", 
      "pseudocode", 
      "scheduling", 
      "information", 
      "Prolog", 
      "collection", 
      "poor information", 
      "computer model", 
      "logic circuits", 
      "Boolean", 
      "logic", 
      "space", 
      "requirements", 
      "storage", 
      "update", 
      "optimization", 
      "time one", 
      "inference", 
      "need", 
      "model", 
      "operation", 
      "stack", 
      "advantages", 
      "simulations", 
      "time", 
      "context", 
      "circuit", 
      "previous values", 
      "state", 
      "fundamental importance", 
      "fine scale", 
      "checkpoint", 
      "one", 
      "predecessors", 
      "benefits", 
      "analysis", 
      "means", 
      "insights", 
      "interpretation", 
      "whole", 
      "undoing", 
      "variables", 
      "place", 
      "importance", 
      "successor states", 
      "scale", 
      "values", 
      "inability", 
      "palindrome", 
      "recovery", 
      "explanation", 
      "less heat", 
      "fortunes", 
      "materials", 
      "thermodynamics", 
      "mutations", 
      "heat", 
      "editor undoing", 
      "optimistic concurrency undoing", 
      "concurrency undoing", 
      "speculative computation undoing", 
      "computation undoing", 
      "exception handling undoing", 
      "handling undoing", 
      "optimistic discrete event simulations", 
      "subjunctive computing", 
      "reversed computation", 
      "static analysis\u2014liveness analysis", 
      "analysis\u2014liveness analysis", 
      "previous state involve checkpoints", 
      "state involve checkpoints", 
      "involve checkpoints", 
      "Traditional reverse abstract interpretation", 
      "reverse abstract interpretation", 
      "abstract computer model", 
      "arbitrary undoing", 
      "reversible conservative logic circuits", 
      "conservative logic circuits", 
      "serendipitous advantage", 
      "unique predecessor", 
      "reversible pseudocode", 
      "time-consuming iterative abstract interpretation", 
      "iterative abstract interpretation", 
      "most non-reversible models", 
      "non-reversible models", 
      "NREVERSAL of fortune", 
      "NREVERSAL"
    ], 
    "name": "NREVERSAL of fortune \u2014 The thermodynamics of garbage collection", 
    "pagination": "507-524", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1030791058"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bfb0017210"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/bfb0017210", 
      "https://app.dimensions.ai/details/publication/pub.1030791058"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:07", 
    "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/chapter/chapter_359.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/bfb0017210"
  }
]
 

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/bfb0017210'

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/bfb0017210'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bfb0017210'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bfb0017210'


 

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

178 TRIPLES      23 PREDICATES      141 URIs      134 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bfb0017210 schema:about anzsrc-for:08
2 anzsrc-for:0803
3 schema:author N8d302193133a4fff9e8c7f38b31bac77
4 schema:datePublished 1992
5 schema:datePublishedReg 1992-01-01
6 schema:description The need to reverse a computation arises in many contexts—debugging, editor undoing, optimistic concurrency undoing, speculative computation undoing, trace scheduling, exception handling undoing, database recovery, optimistic discrete event simulations, subjunctive computing, etc. The need to analyze a reversed computation arises in the context of static analysis—liveness analysis, strictness analysis, type inference, etc. Traditional means for restoring a computation to a previous state involve checkpoints; checkpoints require time to copy, as well as space to store, the copied material. Traditional reverse abstract interpretation produces relatively poor information due to its inability to guess the previous values of assigned-to variables. We propose an abstract computer model and a programming language—Ψ-Lisp—whose primitive operations are injective and hence reversible, thus allowing arbitrary undoing without the overheads of checkpointing. Such a computer can be built from reversible conservative logic circuits, with the serendipitous advantage of dissipating far less heat than traditional Boolean AND/OR/NOT circuits. Unlike functional languages, which have one “state” for all times, Ψ-Lisp has at all times one “state”, with unique predecessor and successor states. Compiling into a reversible pseudocode can have benefits even when targeting a traditional computer. Certain optimizations, e.g., update-in-place, and compile-time garbage collection may be more easily performed, because the information may be elicited without the difficult and time-consuming iterative abstract interpretation required for most non-reversible models. In a reversible machine, garbage collection for recycling storage can always be performed by a reversed (sub)computation. While this “collection is reversed mutation” insight does not reduce space requirements when used for the computation as a whole, it does save space when used to recycle at finer scales. This insight also provides an explanation for the fundamental importance of the push-down stack both for recognizing palindromes and for managing storage. Reversible computers are related to Prolog, linear logic and chemical abstract machines.
7 schema:editor N0f4ef56ad60d4febbe131e8fcacabc17
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N6c2a51d510014e39877a232df7df339b
12 schema:keywords Boolean
13 Chemical Abstract Machine
14 Lisp
15 NREVERSAL
16 NREVERSAL of fortune
17 Prolog
18 Traditional reverse abstract interpretation
19 abstract computer model
20 abstract interpretation
21 abstract machine
22 advantages
23 analysis
24 analysis—liveness analysis
25 arbitrary undoing
26 benefits
27 certain optimizations
28 checkpoint
29 circuit
30 collection
31 compile-time garbage collection
32 computation
33 computation undoing
34 computer
35 computer model
36 computing
37 concurrency undoing
38 conservative logic circuits
39 context
40 database recovery
41 discrete event simulation
42 editor undoing
43 event simulation
44 exception handling undoing
45 explanation
46 fine scale
47 fortunes
48 functional language
49 fundamental importance
50 garbage collection
51 handling undoing
52 heat
53 importance
54 inability
55 inference
56 information
57 insights
58 interpretation
59 involve checkpoints
60 iterative abstract interpretation
61 language
62 less heat
63 linear logic
64 logic
65 logic circuits
66 machine
67 materials
68 means
69 model
70 most non-reversible models
71 mutations
72 need
73 non-reversible models
74 one
75 operation
76 optimistic concurrency undoing
77 optimistic discrete event simulations
78 optimization
79 overhead
80 palindrome
81 place
82 poor information
83 predecessors
84 previous state involve checkpoints
85 previous values
86 primitive operations
87 programming language
88 pseudocode
89 recovery
90 requirements
91 reverse abstract interpretation
92 reversed computation
93 reversible computers
94 reversible conservative logic circuits
95 reversible machine
96 reversible pseudocode
97 scale
98 scheduling
99 serendipitous advantage
100 simulations
101 space
102 space requirements
103 speculative computation undoing
104 stack
105 state
106 state involve checkpoints
107 static analysis—liveness analysis
108 storage
109 strictness analysis
110 subjunctive computing
111 successor states
112 thermodynamics
113 time
114 time one
115 time-consuming iterative abstract interpretation
116 trace scheduling
117 traditional Boolean
118 traditional computers
119 traditional means
120 type inference
121 undoing
122 unique predecessor
123 update
124 values
125 variables
126 whole
127 schema:name NREVERSAL of fortune — The thermodynamics of garbage collection
128 schema:pagination 507-524
129 schema:productId N6aba2db7728244f2974b82b63fc3ecd9
130 Nb29cd36db0994b56aa7cf50ed9ebb8d6
131 schema:publisher N84d25b6fcab74f08a7843ede0e21af6b
132 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030791058
133 https://doi.org/10.1007/bfb0017210
134 schema:sdDatePublished 2021-12-01T20:07
135 schema:sdLicense https://scigraph.springernature.com/explorer/license/
136 schema:sdPublisher Ne2898937c75c4ff288bc2f5f338a787f
137 schema:url https://doi.org/10.1007/bfb0017210
138 sgo:license sg:explorer/license/
139 sgo:sdDataset chapters
140 rdf:type schema:Chapter
141 N00c0e53fa28341628b840f8a4da3b102 rdf:first Nb70d5ea3668749abafb0d7025ab4be42
142 rdf:rest rdf:nil
143 N0f4ef56ad60d4febbe131e8fcacabc17 rdf:first Na6350e078f8d45999f3b65f5a107805f
144 rdf:rest N00c0e53fa28341628b840f8a4da3b102
145 N6aba2db7728244f2974b82b63fc3ecd9 schema:name dimensions_id
146 schema:value pub.1030791058
147 rdf:type schema:PropertyValue
148 N6c2a51d510014e39877a232df7df339b schema:isbn 3-540-55940-X
149 schema:name Memory Management
150 rdf:type schema:Book
151 N77d2dd6b81b243218c86eb3cc4100598 schema:affiliation grid-institutes:None
152 schema:familyName Baker
153 schema:givenName Henry G.
154 rdf:type schema:Person
155 N84d25b6fcab74f08a7843ede0e21af6b schema:name Springer Nature
156 rdf:type schema:Organisation
157 N8d302193133a4fff9e8c7f38b31bac77 rdf:first N77d2dd6b81b243218c86eb3cc4100598
158 rdf:rest rdf:nil
159 Na6350e078f8d45999f3b65f5a107805f schema:familyName Bekkers
160 schema:givenName Yves
161 rdf:type schema:Person
162 Nb29cd36db0994b56aa7cf50ed9ebb8d6 schema:name doi
163 schema:value 10.1007/bfb0017210
164 rdf:type schema:PropertyValue
165 Nb70d5ea3668749abafb0d7025ab4be42 schema:familyName Cohen
166 schema:givenName Jacques
167 rdf:type schema:Person
168 Ne2898937c75c4ff288bc2f5f338a787f schema:name Springer Nature - SN SciGraph project
169 rdf:type schema:Organization
170 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
171 schema:name Information and Computing Sciences
172 rdf:type schema:DefinedTerm
173 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
174 schema:name Computer Software
175 rdf:type schema:DefinedTerm
176 grid-institutes:None schema:alternateName Nimble Computer Corporation, 16231 Meadow Ridge Way, 91436, Encino, California, USA
177 schema:name Nimble Computer Corporation, 16231 Meadow Ridge Way, 91436, Encino, California, USA
178 rdf:type schema:Organization
 




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


...