Wikipedia

Program Inversion, Interpretation, and Injectivization

Central to reversible computing are the concepts of running computations backward and handling functions that are not inherently bijective. Program inversion, inverse interpretation, and injectivization are key techniques and theoretical constructs addressing these aspects.

Theory of Program Inversion in Reversible Languages

edit

Program inversion refers to the process of deriving, from a given program P that computes an injective function f, a new program P−1 that computes the inverse function f−1.[1] In the context of programming languages designed for reversibility, this inversion process is often facilitated by the language structure itself.

A core principle enabling straightforward program inversion in many reversible languages is local inversion (or local invertibility).[2] This property means that the inverse of a composite program construct can be systematically derived from the inverses of its constituent parts. For sequential composition, if a program consists of steps s1 followed by s2, its inverse consists of the inverse of s2 followed by the inverse of s1: (s1; s2)−1 = s2−1; s1−1.[3] This allows program inversion to be performed via a recursive descent over the program's abstract syntax tree.[4]

Janus provides a clear example. Every Janus statement is designed to be locally invertible.[5] The inverse of call id is uncall id; the inverse of x += e is x -= e; the inverse of skip is skip.[6] Control flow constructs also have well-defined inverses: if e1 then s1 else s2 fi e2 inverts to if e2 then s1−1 else s2−1 fi e1, and similarly for loops, where the roles of entry/exit predicates are swapped and the bodies are inverted.[7] Because of this systematic local invertibility, a program inverter for Janus can be automatically constructed.[8] This built-in or easily derivable inversion is a significant advantage of reversible languages over conventional languages, where program inversion is generally a much harder problem, often requiring complex analysis and transformations that may fail or only work for restricted program classes.[9] Challenges can still arise, for instance, in handling tail recursion within certain inversion frameworks. [10]

Inverse Interpretation

edit

Inverse interpretation offers a different way to achieve backward computation. Instead of generating a separate inverse program P−1, inverse interpretation involves executing the semantics of the original program P backward, starting from an output state to recover the corresponding input state.[11]

In Janus, the uncall id statement provides a direct mechanism for inverse interpretation.[12] While call id executes the procedure id forward, mapping an input store to an output store, uncall id invokes the inverse semantics, mapping the output store back to the input store.[13] This allows the same procedure definition to be used for computation in both directions.[14]

The following fibpair procedure in Janus calculates a pair of consecutive Fibonacci numbers.[15] Given an input n, it sets x1 to F(n) and x2 to F(n+1), assuming x1 and x2 are initially 0: 

int n x1 x2 // variable declarations

procedure fibpair
    if n=0 then x1 += 1
                x2 += 1
    else n -= 1
         call fibpair
         x1 += x2
         x1 <=> x2
fi x1=x2

For calling and uncalling the Fibonacci-pair procedure we use 

procedure main_fwd 
    n += 2
    call fibpair 

prodecure main_bwd
    x1 += 2
    x2 += 3
    uncall fibpair

The trace below demonstrates the execution of the fibpair procedure.[16] The "Forward run" starts with n=2, x1=0, x2=0 and calculates the Fibonacci pair, resulting in x1=2, x2=3. The "Backward run" (an uncall fibpair) starts with these results and correctly reverses the computation, returning the variables to their initial state. The indentation in the statement column visualizes recursive calls and returns. The values of n, x1, and x2 are shown after the execution of the statement on that line. 

            Forward run: call fibpair                        
+------------------------+-------+-------+-------+     
| Statement              |   n   |  x1   |  x2   |     
+------------------------+-------+-------+-------+     
| (initial state)        |   2   |   0   |   0   |     
| if n=0                 |   2   |   0   |   0   |     
|   n -= 1               |   1   |   0   |   0   |     
|   call fibpair         |   1   |   0   |   0   |     
|     if n=0             |   1   |   0   |   0   |     
|       n -= 1           |   0   |   0   |   0   |     
|       call fibpair     |   0   |   0   |   0   |     
|         if n=0         |   0   |   0   |   0   |      
|           x1 += 1      |   0   |   1   |   0   |     
|           x2 += 1      |   0   |   1   |   1   |     
|         fi x1=x2       |   0   |   1   |   1   |     
|       x1 += x2         |   0   |   2   |   1   |     
|       x1 <=> x2        |   0   |   1   |   2   |     
|     fi x1=x2           |   0   |   1   |   2   |     
|   x1 += x2             |   0   |   3   |   2   |     
|   x1 <=> x2            |   0   |   2   |   3   |     
| fi x1=x2               |   0   |   2   |   3   |     
+------------------------+-------+-------+-------+     

           Backward run: uncall fibpair      
+------------------------+-------+-------+-------+
| Statement              |   n   |  x1   |  x2   |
+------------------------+-------+-------+-------+
| (initial state)        |   0   |   2   |   3   |
| if x1=x2               |   0   |   2   |   3   |
|   x1 <=> x2            |   0   |   3   |   2   |
|   x1 -= x2             |   0   |   1   |   2   |
|   uncall fibpair       |   0   |   1   |   2   |
|     if x1=x2           |   0   |   1   |   2   |
|       x1 <=> x2        |   0   |   2   |   1   |
|       x1 -= x2         |   0   |   1   |   1   |
|       uncall fibpair   |   0   |   1   |   1   |
|         if x1=x2       |   0   |   1   |   1   |
|           x2 -= 1      |   0   |   1   |   0   |
|           x1 -= 1      |   0   |   0   |   0   |
|         fi n=0         |   0   |   0   |   0   |
|       n += 1           |   1   |   0   |   0   |
|     fi n=0             |   1   |   0   |   0   |
|   n += 1               |   2   |   0   |   0   |
| fi n=0                 |   2   |   0   |   0   |
+------------------------+-------+-------+-------+

Inverse interpretation is closely related to the concept of invertible self-interpreters. A self-interpreter for a reversible language R, written in R itself (R-intR), can perform forward interpretation when called normally. If this self-interpreter is itself invertible (which is possible if R supports local inversion), then applying the inverse interpretation mechanism (like uncall) to the self-interpreter (uncall R-intR(program, output)) effectively performs inverse interpretation of the object program without needing an explicit computation history.[17]

Injectivization Techniques and Examples

edit

Reversible computation models, like RTMs, inherently compute bijective (injective and surjective) functions.[18] However, many useful computations correspond to functions that are not injective (many-to-one), meaning information is lost. Injectivization is the fundamental technique used to embed such non-injective computations within a reversible framework.[19]

The core idea is to transform a non-injective function f: X → Y into a related injective function f': X → Y × Z by adding extra outputs, often derived from the input or computation context (g(x)), such that the original input x can be uniquely recovered from the augmented output pair (f(x), g(x)).[20]

A straightforward and common injectivization technique is simply to preserve the input alongside the output, transforming f(x) into the injective function f'(x) = (x, f(x)).[21] While simple and universally applicable, this method often leads to significant "garbage" output (the preserved input x might not be needed after f(x) is computed).

Other injectivization approaches aim to be more ungenerous. Glück and Yokoyama described an "Injectivisation process" that adds necessary auxiliary information to the output to ensure invertibility.[22]

In the context of Term Rewriting Systems (TRSs), which model rule-based computations, specific injectivization transformations have been developed.[23] Given an irreversible TRS R, an injective version Rf can be constructed. This often involves adding information about the applied rewrite rule and the position of application to the output term, effectively embedding the computation history or context into the result.[24] This transformed system Rf computes an injective function, allowing it to be modeled within a reversible framework. Correspondingly, an inverse system Rb can also be generated.[25]

A concrete example arises in the Rabin-Karp string matching algorithm, which uses a polynomial hash function updated via modular arithmetic.[26] Modular operations like addition (+q), subtraction (−q), and multiplication (*q) are generally non-injective. However, they become injective in one argument under specific conditions (e.g., x *q d is injective in x if d and q are coprime).[27] Analyzing these conditions allows for the design of an injective (and thus reversible) version of the hash update function H', enabling a reversible implementation of the algorithm[28]

The general principle is that to compute non-injective functions reversibly, the information that would normally be lost must be explicitly preserved or encoded in the output. Ideally, this injectivization is applied at the level of the problem specification rather than simply applying a generic embedding like input preservation, potentially leading to more efficient reversible algorithms.[29] Injectivization forms the theoretical basis allowing reversible computation models, which are fundamentally bijective, to encompass the full range of computable functions, albeit at the cost of potentially producing additional output information.

Reversible Interpreters

edit

Interpreters are programs that execute other programs written in a specific object language. In the context of reversible computing, the concept extends to reversible interpreters, which not only execute object programs but do so in a reversible manner.

Design Principles and Implementation Challenges

edit

A reversible interpreter executes a program written in an object language L using a host language R. For the entire system to be truly reversible, both the object language L and the host language R should ideally support reversibility, and the interpreter program itself must be a reversible program within R.[30] This means each step performed by the interpreter, like fetching instructions, decoding them, updating the simulated state of the object program, and handling control flow, must correspond to a reversible operation in the host language R.

Implementing a reversible interpreter presents significant challenges compared to conventional interpreters:

  • Reversible Control Flow: Standard interpreter loops involve updating a program counter (PC) and making branches based on the interpreted instruction. Overwriting the PC is irreversible. Simple history tracing (Landauer embedding) to record previous PC values leads to unacceptable garbage accumulation.[31] Therefore, the interpreter must use the reversible control flow mechanisms of the host language (e.g., Janus's if..fi and from..until constructs with assertions) to manage the flow of interpretation reversibly.[32]
  • Reversible State Management: The interpreter maintains the state of the program being interpreted (e.g., simulated registers, memory). All updates to this state must be performed using reversible operations provided by the host language (e.g., +=, <=>).[33]
  • Reversible Memory Models: If the interpreted language allows memory access, the interpreter needs to interact with a memory model that supports reversible operations. This is particularly complex if the language allows self-modification (which is often disallowed in reversible architectures, e.g., by adopting a Harvard architecture separating code and data).[34] Theoretical models for reversible memory exist (e.g., rotary element[35]), but practical implementation remains an open question.
  • Garbage Avoidance: A key goal is to design the interpreter to be "clean" or garbage-free, meaning it should not accumulate auxiliary data related solely to the interpretation process itself.[36] This requires careful design to ensure that any temporary state used by the interpreter is properly uncomputed or managed.

The Bob architecture is an example of a proposed reversible processor design aiming to address these challenges.[37] It features a simple, locally-invertible instruction set (BobISA) and incorporates reversible control logic and address calculation mechanisms, operating under the assumption of a Harvard architecture and operationally reversible memory.[38]

Self-Interpretation and Towers of Interpreters

edit

A powerful concept in programming language theory is self-interpretation, where an interpreter for a language R is written in R itself (R-intR).[39] If R is a reversible language, it is possible to write a reversible self-interpreter.[40]

A significant property arises if the self-interpreter R-intR is not only reversible but also invertible using the mechanisms of R (e.g., local inversion or an uncall operation). Such an invertible self-interpreter can perform both forward interpretation (call R-intR(program, input)) and inverse interpretation (uncall R-intR(program, output)) without requiring an external computation history.[41] The Janus language, for instance, possesses an invertible self-interpreter.[42]

Self-interpreters naturally lead to the idea of towers of interpreters. This involves a sequence of interpreters, where I1 (written in language L0) interprets program P2 (written in L1), which in turn interprets I3 (in L2), and so on: L0 --I1--> L1 --I2--> L2 --I3--> ... Ln.[43] If the languages Li and interpreters Ii are all reversible, this forms a reversible tower of interpreters. Janus, with its invertible self-interpreter, can form such a tower.[44]

A key challenge with interpreter towers, whether reversible or not, is the significant performance overhead introduced by multiple levels of interpretation. Research has focused on techniques for collapsing such towers into a single, efficient compiler that translates directly from the highest-level language (Ln) to the base language (L0), eliminating all intermediate interpretation steps.[45] Techniques based on multi-level staging and stage polymorphism have been developed for this purpose, even in the presence of reflection (where interpreters can modify themselves or the language semantics dynamically).[46] These concepts are applicable to reversible towers. Collapsing a reversible tower could potentially yield an optimized compiler that generates efficient reversible code in the base language, connecting interpretation, compilation, and optimization within the reversible paradigm.[47]

References

edit
  1. ^ Glück, Robert; Yokoyama, Tetsuo (2023). "Reversible computing from a programming language perspective". Theoretical Computer Science. 953 113429. doi:10.1016/j.tcs.2022.06.010.
  2. ^ Glück, Robert; Yokoyama, Tetsuo (2023). "Reversible computing from a programming language perspective". Theoretical Computer Science. 953 113429. doi:10.1016/j.tcs.2022.06.010.
  3. ^ Yokoyama, Tetsuo (2010). "Reversible Computation and Reversible Programming Languages". In Ulidowski, Irek (ed.). Proceedings of the Workshop on Reversible Computation, RC@ETAPS 2009, York, UK, March 22, 2009. Electronic Notes in Theoretical Computer Science. Vol. 253. Elsevier. pp. 71–81. doi:10.1016/J.ENTCS.2010.02.007. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  4. ^ Glück, Robert; Yokoyama, Tetsuo (2023). "Reversible computing from a programming language perspective". Theoretical Computer Science. 953 113429. doi:10.1016/j.tcs.2022.06.010.
  5. ^ Yokoyama, Tetsuo (2010). "Reversible Computation and Reversible Programming Languages". In Ulidowski, Irek (ed.). Proceedings of the Workshop on Reversible Computation, RC@ETAPS 2009, York, UK, March 22, 2009. Electronic Notes in Theoretical Computer Science. Vol. 253. Elsevier. pp. 71–81. doi:10.1016/J.ENTCS.2010.02.007. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  6. ^ Yokoyama, Tetsuo (2010). "Reversible Computation and Reversible Programming Languages". In Ulidowski, Irek (ed.). Proceedings of the Workshop on Reversible Computation, RC@ETAPS 2009, York, UK, March 22, 2009. Electronic Notes in Theoretical Computer Science. Vol. 253. Elsevier. pp. 71–81. doi:10.1016/J.ENTCS.2010.02.007. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  7. ^ Yokoyama, Tetsuo (2010). "Reversible Computation and Reversible Programming Languages". In Ulidowski, Irek (ed.). Proceedings of the Workshop on Reversible Computation, RC@ETAPS 2009, York, UK, March 22, 2009. Electronic Notes in Theoretical Computer Science. Vol. 253. Elsevier. pp. 71–81. doi:10.1016/J.ENTCS.2010.02.007. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  8. ^ Yokoyama, Tetsuo; Glück, Robert (2007). "A reversible programming language and its invertible self-interpreter". In Ramalingam, G.; Visser, Eelco (eds.). Proceedings of the 2007 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-based Program Manipulation, 2007, Nice, France, January 15-16, 2007. ACM. pp. 144–153. doi:10.1145/1244381.1244404. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  9. ^ Matsuda, Kazutaka; Wang, Meng (2024). "Sparcl: A language for partially invertible computation". Journal of Functional Programming. 34 e2. doi:10.1017/S0956796823000126. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server..
  10. ^ Kristensen, Joachim Tilsted; Kaarsgaard, Robin; Thomsen, Michael Kirkedal (2023). "Tail Recursion Transformation for Invertible Functions". Reversible Computation. Lecture Notes in Computer Science. Vol. 13960. pp. 73–88. arXiv:2302.10049. doi:10.1007/978-3-031-38100-3_6. ISBN 978-3-031-38099-0.
  11. ^ Glück, Robert; Yokoyama, Tetsuo (2023). "Reversible computing from a programming language perspective". Theoretical Computer Science. 953 113429. doi:10.1016/j.tcs.2022.06.010.
  12. ^ Yokoyama, Tetsuo (2010). "Reversible Computation and Reversible Programming Languages". In Ulidowski, Irek (ed.). Proceedings of the Workshop on Reversible Computation, RC@ETAPS 2009, York, UK, March 22, 2009. Electronic Notes in Theoretical Computer Science. Vol. 253. Elsevier. pp. 71–81. doi:10.1016/J.ENTCS.2010.02.007. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  13. ^ Yokoyama, Tetsuo (2010). "Reversible Computation and Reversible Programming Languages". In Ulidowski, Irek (ed.). Proceedings of the Workshop on Reversible Computation, RC@ETAPS 2009, York, UK, March 22, 2009. Electronic Notes in Theoretical Computer Science. Vol. 253. Elsevier. pp. 71–81. doi:10.1016/J.ENTCS.2010.02.007. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  14. ^ Yokoyama, Tetsuo (2010). "Reversible Computation and Reversible Programming Languages". In Ulidowski, Irek (ed.). Proceedings of the Workshop on Reversible Computation, RC@ETAPS 2009, York, UK, March 22, 2009. Electronic Notes in Theoretical Computer Science. Vol. 253. Elsevier. pp. 71–81. doi:10.1016/J.ENTCS.2010.02.007. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  15. ^ Glück, Robert; Yokoyama, Tetsuo (2023). "Reversible computing from a programming language perspective". Theoretical Computer Science. 953 113429. doi:10.1016/j.tcs.2022.06.010.
  16. ^ Glück, Robert; Yokoyama, Tetsuo (2023). "Reversible computing from a programming language perspective". Theoretical Computer Science. 953 113429. doi:10.1016/j.tcs.2022.06.010.
  17. ^ Yokoyama, Tetsuo; Glück, Robert (2007). "A reversible programming language and its invertible self-interpreter". In Ramalingam, G.; Visser, Eelco (eds.). Proceedings of the 2007 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-based Program Manipulation, 2007, Nice, France, January 15-16, 2007. ACM. pp. 144–153. doi:10.1145/1244381.1244404. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  18. ^ Axelsen, Holger Bock; Glück, Robert (2011). "What Do Reversible Programs Compute?". In Hofmann, Martin (ed.). Foundations of Software Science and Computational Structures - 14th International Conference, FOSSACS 2011, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2011, Saarbrücken, Germany, March 26-April 3, 2011. Proceedings. Lecture Notes in Computer Science. Vol. 6604. Springer. pp. 42–56. doi:10.1007/978-3-642-19805-2_4. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  19. ^ Palazzo, Matteo; Roversi, Luca (2025). "Reversible Computation with Stacks and "Reversible Management of Failures"". arXiv:2501.05259 [cs.PL].
  20. ^ Palazzo, Matteo; Roversi, Luca (2025). "Reversible Computation with Stacks and "Reversible Management of Failures"". arXiv:2501.05259 [cs.PL].
  21. ^ "Landauer's Principle, Reversible Computation, and Maxwell's Demon" (PDF). Duke University. Retrieved April 9, 2025.
  22. ^ Glück, Robert; Yokoyama, Tetsuo (2023). "Reversible computing from a programming language perspective". Theoretical Computer Science. 953 113429. doi:10.1016/j.tcs.2022.06.010.
  23. ^ Nishida, Naoki; Palacios, Adrián; Vidal, Germán (2017). "Reversible Computation in Term Rewriting". arXiv:1710.02804 [cs.PL].
  24. ^ Aman, Bogdan; Ciobanu, Gabriel; Glück, Robert; Kaarsgaard, Robin; Kari, Jarkko; Kutrib, Martin; Lanese, Ivan; Mezzina, Claudio Antares; Mikulski, Lukasz; Nagarajan, Rajagopal; Phillips, Iain C. C.; Pinna, G. Michele; Prigioniero, Luca; Ulidowski, Irek; Vidal, Germán (2020). "Foundations of Reversible Computation". In Ulidowski, Irek; Lanese, Ivan; Schultz, Ulrik Pagh; Ferreira, Carla (eds.). Reversible Computation: Extending Horizons of Computing - Selected Results of the COST Action IC1405. Lecture Notes in Computer Science. Vol. 12070. Springer. pp. 1–40. doi:10.1007/978-3-030-47361-7_1. ISBN 978-3-030-47360-0. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  25. ^ Nishida, Naoki; Palacios, Adrián; Vidal, Germán (2017). "Reversible Computation in Term Rewriting". arXiv:1710.02804 [cs.PL].
  26. ^ Glück, Robert; Yokoyama, Tetsuo (2022). "Reversible Programming: A Case Study of Two String-Matching Algorithms". In Hamilton, Geoffrey William; Kahsai, Temesghen; Proietti, Maurizio (eds.). Proceedings 9th Workshop on Horn Clauses for Verification and Synthesis and 10th International Workshop on Verification and Program Transformation, HCVS/VPT@ETAPS 2022, and 10th International Workshop on Verification and Program TransformationMunich, Germany, 3rd April 2022. EPTCS. Vol. 373. pp. 1–13. arXiv:2211.12225. doi:10.4204/EPTCS.373.1. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  27. ^ Glück, Robert; Yokoyama, Tetsuo (2022). "Reversible Programming: A Case Study of Two String-Matching Algorithms". In Hamilton, Geoffrey William; Kahsai, Temesghen; Proietti, Maurizio (eds.). Proceedings 9th Workshop on Horn Clauses for Verification and Synthesis and 10th International Workshop on Verification and Program Transformation, HCVS/VPT@ETAPS 2022, and 10th International Workshop on Verification and Program TransformationMunich, Germany, 3rd April 2022. EPTCS. Vol. 373. pp. 1–13. arXiv:2211.12225. doi:10.4204/EPTCS.373.1. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server..
  28. ^ Glück, Robert; Yokoyama, Tetsuo (2022). "Reversible Programming: A Case Study of Two String-Matching Algorithms". In Hamilton, Geoffrey William; Kahsai, Temesghen; Proietti, Maurizio (eds.). Proceedings 9th Workshop on Horn Clauses for Verification and Synthesis and 10th International Workshop on Verification and Program Transformation, HCVS/VPT@ETAPS 2022, and 10th International Workshop on Verification and Program TransformationMunich, Germany, 3rd April 2022. EPTCS. Vol. 373. pp. 1–13. arXiv:2211.12225. doi:10.4204/EPTCS.373.1. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  29. ^ Glück, Robert; Yokoyama, Tetsuo (2022). "Reversible Programming: A Case Study of Two String-Matching Algorithms". In Hamilton, Geoffrey William; Kahsai, Temesghen; Proietti, Maurizio (eds.). Proceedings 9th Workshop on Horn Clauses for Verification and Synthesis and 10th International Workshop on Verification and Program Transformation, HCVS/VPT@ETAPS 2022, and 10th International Workshop on Verification and Program TransformationMunich, Germany, 3rd April 2022. EPTCS. Vol. 373. pp. 1–13. arXiv:2211.12225. doi:10.4204/EPTCS.373.1. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  30. ^ Yokoyama, Tetsuo; Glück, Robert (2007). "A reversible programming language and its invertible self-interpreter". In Ramalingam, G.; Visser, Eelco (eds.). Proceedings of the 2007 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-based Program Manipulation, 2007, Nice, France, January 15-16, 2007. ACM. pp. 144–153. doi:10.1145/1244381.1244404. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  31. ^ Thomsen, Michael Kirkedal; Axelsen, Holger Bock; Glück, Robert (2011). "A Reversible Processor Architecture and Its Reversible Logic Design". In De Vos, Alexis; Wille, Robert (eds.). Reversible Computation - Third International Workshop, RC 2011, Gent, Belgium, July 4-5, 2011. Revised Papers. Lecture Notes in Computer Science. Vol. 7165. Springer. pp. 30–42. doi:10.1007/978-3-642-29517-1_3. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  32. ^ Thomsen, Michael Kirkedal; Axelsen, Holger Bock; Glück, Robert (2011). "A Reversible Processor Architecture and Its Reversible Logic Design". In De Vos, Alexis; Wille, Robert (eds.). Reversible Computation - Third International Workshop, RC 2011, Gent, Belgium, July 4-5, 2011. Revised Papers. Lecture Notes in Computer Science. Vol. 7165. Springer. pp. 30–42. doi:10.1007/978-3-642-29517-1_3. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  33. ^ Thomsen, Michael Kirkedal; Axelsen, Holger Bock; Glück, Robert (2011). "A Reversible Processor Architecture and Its Reversible Logic Design". In De Vos, Alexis; Wille, Robert (eds.). Reversible Computation - Third International Workshop, RC 2011, Gent, Belgium, July 4-5, 2011. Revised Papers. Lecture Notes in Computer Science. Vol. 7165. Springer. pp. 30–42. doi:10.1007/978-3-642-29517-1_3. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  34. ^ Thomsen, Michael Kirkedal; Axelsen, Holger Bock; Glück, Robert (2011). "A Reversible Processor Architecture and Its Reversible Logic Design". In De Vos, Alexis; Wille, Robert (eds.). Reversible Computation - Third International Workshop, RC 2011, Gent, Belgium, July 4-5, 2011. Revised Papers. Lecture Notes in Computer Science. Vol. 7165. Springer. pp. 30–42. doi:10.1007/978-3-642-29517-1_3. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  35. ^ Thomsen, Michael Kirkedal; Axelsen, Holger Bock; Glück, Robert (2011). "A Reversible Processor Architecture and Its Reversible Logic Design". In De Vos, Alexis; Wille, Robert (eds.). Reversible Computation - Third International Workshop, RC 2011, Gent, Belgium, July 4-5, 2011. Revised Papers. Lecture Notes in Computer Science. Vol. 7165. Springer. pp. 30–42. doi:10.1007/978-3-642-29517-1_3. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  36. ^ Thomsen, Michael Kirkedal; Axelsen, Holger Bock; Glück, Robert (2011). "A Reversible Processor Architecture and Its Reversible Logic Design". In De Vos, Alexis; Wille, Robert (eds.). Reversible Computation - Third International Workshop, RC 2011, Gent, Belgium, July 4-5, 2011. Revised Papers. Lecture Notes in Computer Science. Vol. 7165. Springer. pp. 30–42. doi:10.1007/978-3-642-29517-1_3. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  37. ^ Thomsen, Michael Kirkedal; Axelsen, Holger Bock; Glück, Robert (2011). "A Reversible Processor Architecture and Its Reversible Logic Design". In De Vos, Alexis; Wille, Robert (eds.). Reversible Computation - Third International Workshop, RC 2011, Gent, Belgium, July 4-5, 2011. Revised Papers. Lecture Notes in Computer Science. Vol. 7165. Springer. pp. 30–42. doi:10.1007/978-3-642-29517-1_3. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  38. ^ Thomsen, Michael Kirkedal; Axelsen, Holger Bock; Glück, Robert (2011). "A Reversible Processor Architecture and Its Reversible Logic Design". In De Vos, Alexis; Wille, Robert (eds.). Reversible Computation - Third International Workshop, RC 2011, Gent, Belgium, July 4-5, 2011. Revised Papers. Lecture Notes in Computer Science. Vol. 7165. Springer. pp. 30–42. doi:10.1007/978-3-642-29517-1_3. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  39. ^ Axelsen, Holger Bock; Glück, Robert (2011). "What Do Reversible Programs Compute?". In Hofmann, Martin (ed.). Foundations of Software Science and Computational Structures - 14th International Conference, FOSSACS 2011, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2011, Saarbrücken, Germany, March 26-April 3, 2011. Proceedings. Lecture Notes in Computer Science. Vol. 6604. Springer. pp. 42–56. doi:10.1007/978-3-642-19805-2_4. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  40. ^ Yokoyama, Tetsuo; Glück, Robert (2007). "A reversible programming language and its invertible self-interpreter". In Ramalingam, G.; Visser, Eelco (eds.). Proceedings of the 2007 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-based Program Manipulation, 2007, Nice, France, January 15-16, 2007. ACM. pp. 144–153. doi:10.1145/1244381.1244404. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  41. ^ Yokoyama, Tetsuo; Glück, Robert (2007). "A reversible programming language and its invertible self-interpreter". In Ramalingam, G.; Visser, Eelco (eds.). Proceedings of the 2007 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-based Program Manipulation, 2007, Nice, France, January 15-16, 2007. ACM. pp. 144–153. doi:10.1145/1244381.1244404. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  42. ^ Yokoyama, Tetsuo; Glück, Robert (2007). "A reversible programming language and its invertible self-interpreter". In Ramalingam, G.; Visser, Eelco (eds.). Proceedings of the 2007 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-based Program Manipulation, 2007, Nice, France, January 15-16, 2007. ACM. pp. 144–153. doi:10.1145/1244381.1244404. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  43. ^ Amin, Nada; Rompf, Tiark (2018). "Collapsing towers of interpreters". Proceedings of the ACM on Programming Languages. 2 (POPL): 52:1–52:33. doi:10.1145/3158140. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  44. ^ Yokoyama, Tetsuo (2010). "Reversible Computation and Reversible Programming Languages". In Ulidowski, Irek (ed.). Proceedings of the Workshop on Reversible Computation, RC@ETAPS 2009, York, UK, March 22, 2009. Electronic Notes in Theoretical Computer Science. Vol. 253. Elsevier. pp. 71–81. doi:10.1016/J.ENTCS.2010.02.007. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  45. ^ Amin, Nada; Rompf, Tiark (2018). "Collapsing towers of interpreters". Proceedings of the ACM on Programming Languages. 2 (POPL): 52:1–52:33. doi:10.1145/3158140. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  46. ^ Amin, Nada; Rompf, Tiark (2018). "Collapsing towers of interpreters". Proceedings of the ACM on Programming Languages. 2 (POPL): 52:1–52:33. doi:10.1145/3158140. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
  47. ^ Glück, Robert; Normann, Louis Marott (2024). "Inversion by Partial Evaluation: A Reversible Interpreter Experiment". In Bieniusa, Annette; Degen, Markus; Wehr, Stefan (eds.). A Second Soul: Celebrating the Many Languages of Programming - Festschrift in Honor of Peter Thiemann's Sixtieth Birthday, Freiburg, Germany, 30th August 2024. EPTCS. Vol. 413. pp. 1–14. arXiv:2412.03122. doi:10.4204/EPTCS.413.1. Program Inversion, Interpretation, and Injectivization at DBLP Bibliography Server.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Program_Inversion,_Interpretation,_and_Injectivization&oldid=1307834365"