The language they introduce, Π, is essentially a simple concatenative programming language where all of the primitive combinators happen to be reversible; the graphical depiction is essentially the same as graphical linear algebra¹, which is no coincidence. Concatenative combinator calculus is related to combinatory logic—specifically, it’s a variation that replaces application of combinators with composition, leading to a bunch of nice mathematical properties. Both of these logics have the nice feature that you can syntactically restrict the substructural rules of contraction (dropping), exchange (swapping), and weakening (copying): for example, a well-formed program that doesn’t use the K combinator to drop a value is guaranteed to be linear, i.e., not destroy any information. This isn’t true in ordinary lambda calculus, where you can use a variable zero or many times, so you need additional checks on the uses of a variable to determine whether a function is linear, affine, &c.
I like the theory of concatenative programming languages because they provide an elegant compositional/dataflow-oriented style of programming, have deep connections to linear logic, Hughes’ “arrows”, effects & coeffects, and quantum/reversible computation, while also admitting very efficient implementation on classical hardware.
I’m (very slowly) working on a statically typed low-level concatenative language that’s meant to provide all the nice high-level typed functional language features like higher-order functions, pipeline-style programming, and effects tracked in the types, while requiring no runtime support such as a tracing garbage collector—the ultimate goal is to allow a restricted subset that doesn’t even require a heap allocator, so you could use it to implement e.g. a kernel or device firmware. I hope that concatenative languages find their way to the mainstream as the basis for programming quantum and extremely low-power computing devices (which we will need in order to reduce emissions).
>>Proposition IV.
That axiom of metaphysicians which is termed the principle of contradiction,
and which affirms that it is impossible for any being to possess a quality, and at the same time
not to possess it, is a consequence of the fundamental law of thought, whose expression is x^2=x
>This “law” is reasonable in a classical world but is violated by the postulates of quantum mechanics
I think this might be a little bit of a stretch, if a particle is in a superposition of states it's not contradictory about which state it is in, it's just in a superposition of both. I think a good analogy for that would be your keyboard, which is located at the Q key as well as the M key.
No: Reversible Computing embraces the (quantum mechanical) notion that information cannot ever be lost (cfr the “Black Hole Information Paradox”), and that therefore the output of a computation can only be a reshuffled but complete permutation of the input. Nix (for example) allows you to delete stuff and/or initialise a variable by zeroing it out and thus obliterating information. A reversible computing paradigm would not allow this. (In practical terms this information is dissipated as heat when memory deletes information.)
I am confused by the downvotes. The above post is correct even if not using the clearest of phrasings.
But I would like to nitpick: You really do not need to involve quantum mechanics. These effects are present in classical thermodynamics. They are just more explicit in quantum mechanics.
" both these fundamental physical theories imply that information is a conserved quantity of physical
processes and hence of primitive computational operations."
No, actually they do not. Jayzus. Peer review is obviously dead.
Like classical reversible computing (which theoretically can mean P=NP), quantum computation fails to exist in the actual world; probably for the same reasons.
I think it's not quite true anyone can post on arxiv, and I wager 10 quatloos that this goes into some non-obscure physics journal and is presented to great acclaim, despite being as dumb as a bag of hammers.
I like the theory of concatenative programming languages because they provide an elegant compositional/dataflow-oriented style of programming, have deep connections to linear logic, Hughes’ “arrows”, effects & coeffects, and quantum/reversible computation, while also admitting very efficient implementation on classical hardware.
I’m (very slowly) working on a statically typed low-level concatenative language that’s meant to provide all the nice high-level typed functional language features like higher-order functions, pipeline-style programming, and effects tracked in the types, while requiring no runtime support such as a tracing garbage collector—the ultimate goal is to allow a restricted subset that doesn’t even require a heap allocator, so you could use it to implement e.g. a kernel or device firmware. I hope that concatenative languages find their way to the mainstream as the basis for programming quantum and extremely low-power computing devices (which we will need in order to reduce emissions).
¹ https://graphicallinearalgebra.net/
>This “law” is reasonable in a classical world but is violated by the postulates of quantum mechanics
I think this might be a little bit of a stretch, if a particle is in a superposition of states it's not contradictory about which state it is in, it's just in a superposition of both. I think a good analogy for that would be your keyboard, which is located at the Q key as well as the M key.
https://www.scribd.com/doc/52657907/Feynman-Lectures-on-Comp...
https://en.wikipedia.org/wiki/Reversible_computing
https://en.wikipedia.org/wiki/Fredkin_gate
https://en.wikipedia.org/wiki/Toffoli_gate
But I would like to nitpick: You really do not need to involve quantum mechanics. These effects are present in classical thermodynamics. They are just more explicit in quantum mechanics.
No, actually they do not. Jayzus. Peer review is obviously dead.
Quantum computation is reversible in terms of applying unitary gates to qubits.
However doing IO - breaking entangled states, or interacting with the outside world, is not reversible in a practical sense.
I think it's not quite true anyone can post on arxiv, and I wager 10 quatloos that this goes into some non-obscure physics journal and is presented to great acclaim, despite being as dumb as a bag of hammers.