Describing and optimizing reversible logic using a functional language

Michael Kirkedal Thomsen

doi:10.1007/978-3-642-34407-7_10

Describing and optimizing reversible logic using a functional language

Michael Kirkedal Thomsen

Datalogisk Institut

7 Citationer (Scopus)

Abstract

This paper presents the design of a language for the description and optimisation of reversible logic circuits. The language is a combinator-style functional language designed to be close to the reversible logical gate-level. The combinators include high-level constructs such as ripples, but also the recognisable inversion combinator f^-1, which defines the inverse function of f using an efficient semantics. It is important to ensure that all circuits descriptions are reversible, and furthermore we must require this to be done statically. This is ensured by the type system, which also allows the description of arbitrary sized circuits. The combination of the functional language and the restricted reversible model results in many arithmetic laws, which provide more possibilities for term rewriting and, thus, the opportunity for good optimisation.

Originalsprog	Engelsk
Titel	Implementation and Application of Functional Languages, IFL 2011 : 23rd International Symposium, IFL 2011, Lawrence, Kansas, USA, October 2011, Revised Papers
Redaktører	Andy Gill, Jurriaan Hage
Antal sider	16
Forlag	Springer
Publikationsdato	2012
Sider	148–163
ISBN (Trykt)	978-3-642-34406-0
ISBN (Elektronisk)	978-3-642-34407-7
DOI	https://doi.org/10.1007/978-3-642-34407-7_10
Status	Udgivet - 2012
Begivenhed	23rd Symposium on Implementation and Application of Functional Languages - Lawrence, KS, USA Varighed: 3 okt. 2011 → 5 okt. 2011 Konferencens nummer: 23

Konference

Konference	23rd Symposium on Implementation and Application of Functional Languages
Nummer	23
Land/Område	USA
By	Lawrence, KS
Periode	03/10/2011 → 05/10/2011

Navn	Lecture notes in computer science
Vol/bind	7257

Adgang til dokumentet

10.1007/978-3-642-34407-7_10

Citationsformater

Thomsen, M. K. (2012). Describing and optimizing reversible logic using a functional language. I A. Gill, & J. Hage (red.), Implementation and Application of Functional Languages, IFL 2011: 23rd International Symposium, IFL 2011, Lawrence, Kansas, USA, October 2011, Revised Papers (s. 148–163). Springer. Lecture notes in computer science Bind 7257 https://doi.org/10.1007/978-3-642-34407-7_10

Describing and optimizing reversible logic using a functional language. / Thomsen, Michael Kirkedal.

Implementation and Application of Functional Languages, IFL 2011: 23rd International Symposium, IFL 2011, Lawrence, Kansas, USA, October 2011, Revised Papers. red. / Andy Gill; Jurriaan Hage. Springer, 2012. s. 148–163 (Lecture notes in computer science, Bind 7257).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Thomsen, MK 2012, Describing and optimizing reversible logic using a functional language. i A Gill & J Hage (red), Implementation and Application of Functional Languages, IFL 2011: 23rd International Symposium, IFL 2011, Lawrence, Kansas, USA, October 2011, Revised Papers. Springer, Lecture notes in computer science, bind 7257, s. 148–163, 23rd Symposium on Implementation and Application of Functional Languages, Lawrence, KS, USA, 03/10/2011. https://doi.org/10.1007/978-3-642-34407-7_10

Thomsen MK. Describing and optimizing reversible logic using a functional language. I Gill A, Hage J, red., Implementation and Application of Functional Languages, IFL 2011: 23rd International Symposium, IFL 2011, Lawrence, Kansas, USA, October 2011, Revised Papers. Springer. 2012. s. 148–163. (Lecture notes in computer science, Bind 7257). doi: 10.1007/978-3-642-34407-7_10

Thomsen, Michael Kirkedal. / Describing and optimizing reversible logic using a functional language. Implementation and Application of Functional Languages, IFL 2011: 23rd International Symposium, IFL 2011, Lawrence, Kansas, USA, October 2011, Revised Papers. red. / Andy Gill ; Jurriaan Hage. Springer, 2012. s. 148–163 (Lecture notes in computer science, Bind 7257).

@inproceedings{6422343ad1454bad95fb263808cbb20b,

title = "Describing and optimizing reversible logic using a functional language",

abstract = "This paper presents the design of a language for the description and optimisation of reversible logic circuits. The language is a combinator-style functional language designed to be close to the reversible logical gate-level. The combinators include high-level constructs such as ripples, but also the recognisable inversion combinator f-1, which defines the inverse function of f using an efficient semantics. It is important to ensure that all circuits descriptions are reversible, and furthermore we must require this to be done statically. This is ensured by the type system, which also allows the description of arbitrary sized circuits. The combination of the functional language and the restricted reversible model results in many arithmetic laws, which provide more possibilities for term rewriting and, thus, the opportunity for good optimisation.",

author = "Thomsen, {Michael Kirkedal}",

year = "2012",

doi = "10.1007/978-3-642-34407-7_10",

language = "English",

isbn = "978-3-642-34406-0",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "148–163",

editor = "Gill, {Andy } and Jurriaan Hage",

booktitle = "Implementation and Application of Functional Languages, IFL 2011",

note = "23rd Symposium on Implementation and Application of Functional Languages ; Conference date: 03-10-2011 Through 05-10-2011",

}

TY - GEN

T1 - Describing and optimizing reversible logic using a functional language

AU - Thomsen, Michael Kirkedal

N1 - Conference code: 23

PY - 2012

Y1 - 2012

N2 - This paper presents the design of a language for the description and optimisation of reversible logic circuits. The language is a combinator-style functional language designed to be close to the reversible logical gate-level. The combinators include high-level constructs such as ripples, but also the recognisable inversion combinator f-1, which defines the inverse function of f using an efficient semantics. It is important to ensure that all circuits descriptions are reversible, and furthermore we must require this to be done statically. This is ensured by the type system, which also allows the description of arbitrary sized circuits. The combination of the functional language and the restricted reversible model results in many arithmetic laws, which provide more possibilities for term rewriting and, thus, the opportunity for good optimisation.

AB - This paper presents the design of a language for the description and optimisation of reversible logic circuits. The language is a combinator-style functional language designed to be close to the reversible logical gate-level. The combinators include high-level constructs such as ripples, but also the recognisable inversion combinator f-1, which defines the inverse function of f using an efficient semantics. It is important to ensure that all circuits descriptions are reversible, and furthermore we must require this to be done statically. This is ensured by the type system, which also allows the description of arbitrary sized circuits. The combination of the functional language and the restricted reversible model results in many arithmetic laws, which provide more possibilities for term rewriting and, thus, the opportunity for good optimisation.

U2 - 10.1007/978-3-642-34407-7_10

DO - 10.1007/978-3-642-34407-7_10

M3 - Article in proceedings

SN - 978-3-642-34406-0

T3 - Lecture notes in computer science

SP - 148

EP - 163

BT - Implementation and Application of Functional Languages, IFL 2011

A2 - Gill, Andy

A2 - Hage, Jurriaan

PB - Springer

T2 - 23rd Symposium on Implementation and Application of Functional Languages

Y2 - 3 October 2011 through 5 October 2011

ER -

Describing and optimizing reversible logic using a functional language

Abstract

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater