Students know that the flow of a program is a combination of sequential processing, branches, and loops. The introduction of exceptions and their handling, as well as of parallel threads, gives a more fine-grained view on the variations in a program’s execution. There is one last variation, of critical impact, that won’t be treated in the CS2440 lecture: reversibility. Indeed, recently emerged a completely different way of handling the flow of a program, by allowing the computation to go back and forth.
This requires every operation, i.e., statement, in the program to be invertible, so that any function, for instance, can seamlessly go from the input to the output, and from the output to the input. Allowing a program to go back and forth offers several advantages:
I will provide a quick tour of the motivations and fundamentals of reversible computing and sketch one of my contribution during ~30 minutes, and will happily answer your questions for the rest of the lecture. Some material will be posted at https://lacl.fr/~caubert/ASU/cp.html.
Monday, February 6, 2017, 10:00 PM – 10:50 PM
Appalachian State University, Anne Belk Hall, Room 325
The Fibonacci Pairs code, written in
Janus, is a canonical example:
procedure fib(int x1, int x2, int n) if n=0 then x1 += 1 x2 += 1 else n -= 1 call fib(x1, x2, n) x1 += x2 x1 <=> x2 fi x1=x2
|Step 1||0||0||4||(call fib(0, 0 4))|
|Step 2||0||0||3||(call fib(0, 0, 3))|
|Step 3||0||0||2||(call fib(0, 0, 2))|
|Step 4||0||0||1||(call fib(0, 0, 1))|
|Step 5||0||0||0||(call fib(0, 0, 0))|
|Step 6||1||1||0||(terminate call fib(0, 0, 0))|
|Step 7||1||2||0||(terminate call fib(0, 0, 1))|
|Step 8||2||3||0||(terminate call fib(0, 0, 2))|
|Step 9||3||5||0||(terminate call fib(0, 0, 3))|
|Step 10||5||8||0||(terminate call fib(0, 0, 4))|
Janusis probably the oldest and most robust reversible programming language. Its playground is unfortunately broken, but should be fixed soon.
Jouleis an object-oriented variation on
rfunis an experimental, functional and reversible programming language, with an interpreter for
Boomerangis a ‘bidirectional programming language for ad-hoc, textual data’.
JsonGrammaris a bidirectional ‘
Haskelllibrary for converting between
Code for reversible programming languages is hard to find, with one notable exception: Sarah Vang Nøhr, published the
Janus code that resulted from her Master’s thesis (Reversible Graph Algorithms, January 2015). Her pioneer work in the adaptation of graph algorithms for reversible computation is well-documented, solid, and enlightening.
Holger Bock Axelsen, from the University of Copenhagen, gave an excellent 10-minutes introduction to Reversible Computing.
The same author gave a tutorial in 2014, that gives a rough idea of the extend of the topic, along with some useful references.
Janusthrough simple examples (but you should probably skip Section 2.3, which is a bit difficult).
Januswith object-oriented features.
Make sure to submit your work to the international conference Reversible Computation, whose next edition will take place in India!