Abstract
We consider the design of a circuit description library for a pure functional language where circuits are defined as functions and connected together by writing applicative expressions. Just like the return value of any other function in a functional program, the output of a circuit can be bound to a variable and referred to many times. Usually it is the programmer’s intention that such references represent sharing of a circuit’s output, implying a fanout structure. However, in a pure functional language, references are transparent and the circuit description library can only view finite graph-shaped circuit structures as infinitely expanded regular trees. To overcome this problem, we introduce expressible sharing, a technique in which the programmer expresses the fork-points present in a circuit in the same way that they express other circuit components like and-gates and or-gates. We define a library for circuit description which uses expressible sharing and demonstrate it on a small case-study.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Claessen, K.: Embedded languages for describing and verifying hardware. PhD Thesis, Chalmers University of Technology (2001)
Claessen, K., Sands, D.: Observable sharing for functional circuit description. In: Advances in Computing Science ASIAN’99; 5th Asian Computing Science Conference. LNCS, vol. 1742, pp. 62–73. Springer, Berlin (1999)
Knuth, D.E.: The Art of Computer Programming. Sorting and Searching, vol. 3. Addison-Wesley, Reading (1973)
O’Donnell, J.: Generating netlists from executable circuit specifications in a pure functional language. In: Functional Programming, Glasgow 1992, Workshops in Computing, pp. 178–194. Springer, Berlin (1992)
O’Donnell, J.: Embedding a hardware description language in Template Haskell. In: Domain-Specific Program Generation, pp. 143–164 (2003)
Sheeran, M.: Hardware design and functional programming: a perfect match. J. Univers. Comput. Sci. 11(7), 1135–1158 (2005)
Wadler, P.: Monads for functional programming. In: Broy, M. (ed.) Program Design Calculi: Proceedings of the 1992 Marktoberdorf International Summer School. Springer, Berlin (1993)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Naylor, M., Runciman, C. Expressible sharing for functional circuit description. Higher-Order Symb Comput 22, 67–80 (2009). https://doi.org/10.1007/s10990-009-9043-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10990-009-9043-y