We present a method based on Mealy machines for constructing reversible circuitry for multiplying integers by arbitrary integer constants. The circuits generate no garbage and use no ancillae. The circuits are quite compact for small constants and are, in the worst case, bounded by O( n 2 ) multi-control Toffoli gates per bit-slice, where n is the number of bits in the constant. These gates will have O( n ) inputs, so the total number of pass-transistors needed to implement the circuit is O( n 3 ) transistors per bit slice, and the quantum cost (which is exponential in the number of inputs to a Toffoli gate) is O(2 n ). For some interesting cases, the cost can be reduced to O( n ) gates per bit-slice, reducing the cost to O( n 2 ) transistors per bit slice. The quantum cost is still O(2 n ), as the remaining gates have O( n ) inputs. We also look at an alternative construction that, at the cost of adding O( n ) ancillae, reduces the cost for arbitrary constants to O( n ) gates, O( n 2 ) transistors, though still with O(2 n ) quantum cost.

Discrete linear transformations are important tools in information processing. Many such transforms are injective and therefore prime candidates for a physically reversible implementation into hardware. We present here reversible integer cosine transformations on n input integers. The resulting reversible circuit is able to perform both the forward transform and the inverse transform. The detailed structure of such a reversible design strongly depends on the odd prime factors of the determinant of the transform: whether those are of the form 2 k ± 1 or of the form 2 k ± 2 l ± 1 or neither of these forms.

A reversible programming language is a programming language in which you can only write reversible programs, i.e., programs that can be run both forwards (computing outputs from inputs) and backwards (computing inputs from outputs). It is interesting to study reversible programs and languages because computations on reversible computers (computers that only allow reversible programs) in theory can be done using less energy than computations on traditional irreversible computers. Janus is a reversible, structured imperative programming language.

Semi-inversion is a generalisation of inversion: A semi-inverse of a program takes some of the inputs and outputs of the original programand returns the remaining inputs and outputs.

In previous papers we have looked at self-interpretation and show examples of partial evaluation and self-application and evaluate the results.

In the section on “challenging problems” in the proceedings from the first international workshop on partial evaluation and mixed computation [BEJ88] a question is stated: “Can PE be used to generate new specialized data types, in a way analogous to generating specialized functions”. Since then little has been done to address this problem. In [Lau89], new types are indeed generated, but they are all simpler versions of the types in the original program. It is, e.g. not possible to have types with more constructors than the types in the original program.

Abstract We start by giving a compact representation schema for λ-terms, and show how this leads to an exceedingly small and elegant self-interpreter. We then define the notion of a self-reducer , and show how this too can be written as a small λ-term. Both the self-interpreter and the self-reducer are proved correct. We finally give a constructive proof for the second fixed point theorem for the representation schema. All the constructions have been implemented on a computer, and experiments verify their correctness. Timings show that the self-interpreter and self-reducer are quite efficient, being about 35 and 50 times slower than direct execution using a call-by-need reductions strategy