Win a copy of Cross-Platform Desktop Applications: Using Node, Electron, and NW.js this week in the JavaScript forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Functional programming, reversibility and non-determinism?  RSS feed

 
Campbell Ritchie
Sheriff
Posts: 55333
157
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I know it is late in the process, but earlier this week you (P‑YS) said functional programming was deterministic. That reminded me of what I read from Baker. He said that a true functional language avoids assignment and is therefore implicitly reversible. I have been working with reversible languages for several years. The original concept of reversibility was from Charles Bennett, (although Penrose came to the same conclusion about the same time and missed out on the publicity): Bennett used the concept of a reversible Turing Machine which allows you to record intermediate program states and revert to a previous state.
Since then, reversible circuitry has been designed; names like Toffoli Fredkin and deVos are associated with it. Also reversible languages. Starting from Janus (Lutz and Derby) several languages being developed, some by Vieri, Michael Frank, Yokoyama, Thomsen, Glück, and Axelsen. Now the thing all these languages have in common is that all their constructs must be reversible, like injective functions. They work but they can be difficult to write.
Our approach at Middlesbrough has been different; we have a simulation of a reversible Turing Machine, and we have languages which run backwards, but will only do so after they have run “forwards”. We believe such languages, which we call “weakly reversible”, permit more constructs than ordinary languages, including “naked guards” and direct implementation of choice. Those are constructs introduced by Dijkstra as theoretical constructs, but we have implementations of them.
I am at present introducing nondeteminism into our languages by randomising choice. I am wondering about the extensibility of a completely deterministic language. Java® is reasonably deterministic until you start threading, when you will need synchronisation or similar because you don't know which threads will access a particular object in which order. I am wondering whether a language requiring determinism would cope with that. I have been going the completely opposite direction, towards nondeterminism. I just have to get it written down and get a bit of publicity for it.

**************************
Henry G Baker. NREVERSAL of Fortune–The Thermodynamics of Garbage Collection. Lecture Notes in Computer Science, 637:507–524, 1992. doi:10.1.1.22.3166
Charles H Bennett. Logical Reversibility of Computation. IBM Journal of Research and Development, 17:525–532, 1973. doi: 10.1147/rd.176.0525
Oliver Penrose. Foundations of Statistical Mechanics: A Deductive Treatment. Pergamon Press, Oxford, 1970. Reprinted in 2005 by Dover Books
 
Pierre-Yves Saumont
Author
Ranch Hand
Posts: 103
17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
When I say that functional programming is deterministic, it should not be understood to strictly. Functional programming tries to be as much deterministic as possible. But the result of program execution still depends on many external conditions, such as the processing power or the available memory. What I mean is that functional programmers try to abstract randomness by making it explicitly part of the program input, rather than an implicit part of the program itself.
 
Campbell Ritchie
Sheriff
Posts: 55333
157
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you. That sounds much less deterministic than what we call strongly reversible languages. A weakly reversible language on the other hand, permits complete non‑determinism in a forward direction, but has to be deterministic when running backwards.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!