A functional-logic library for wired

ABSTRACT

We develop a Haskell library for functional-logic programming, motivated by the implementation of Wired, a relational embedded domain-specific language for describing and analysing digital circuits at the VLSI-layout level. Compared to a previous library for logic programming by Claessen and Ljunglöf, we support residuation, easier creation of logical data types, and pattern matching. We discuss other applications of our library, including test-data generation, and various extensions, including lazy narrowing.

REFERENCES

• 1: Emil Axelsson, Koen Claessen, and Mary Sheeran. Wired: Wire-aware circuit design. In Proc. of Conference on Correct Hardware Design and Verification Methods (CHARME), volume 3725 of Lecture Notes in Computer Science. Springer Verlag, October 2005.
• 2: Koen Claessen and Peter Ljunglöf. Typed logical variables in Haskell. In Proc. of Haskell Workshop. ACM SIGPLAN, 2000.
• 3: Koen Claessen , David Sands, Observable Sharing for Functional Circuit Description, Proceedings of the 5th Asian Computing Science Conference on Advances in Computing Science, p.62-73, December 10-12, 1999
• 4: Koen Claessen , Mary Sheeran , Satnam Singh, The Design and Verification of a Sorter Core, Proceedings of the 11th IFIP WG 10.5 Advanced Research Working Conference on Correct Hardware Design and Verification Methods, p.355-369, September 04-07, 2001
• 5: Michael Hanus, Herbert Kuchen, and Jose Moreno-Navarro. Curry: A Truly Functional Logic Language. In Proceedings of the ILPS'95 Workshop on Visions for the Future of Logic Programming, 1995.
• 6: Ralf Hinze, Deriving backtracking monad transformers, Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, p.186-197, September 2000
• 7: Ralf Hinze. An algebra of scans. In Mathematics of Program Construction, volume 3125 of Lecture Notes in Computer Science, pages 186--210. Springer, 2004.
• 8: Geraint Jones and Mary Sheeran. Circuit design in Ruby. In J. Staunstrup, editor, Formal Methods for VLSI Design., Elsevier, 1990.
• 9: Oleg Kiselyov , Chung-chieh Shan , Daniel P. Friedman , Amr Sabry, Backtracking, interleaving, and terminating monad transformers: (functional pearl), Proceedings of the tenth ACM SIGPLAN international conference on Functional programming, September 26-28, 2005, Tallinn, Estonia
• 10: Daan Leijen , Erik Meijer, Domain specific embedded compilers, Proceedings of the 2nd conference on Domain-specific languages, p.109-122, October 03-06, 1999, Austin, Texas, United States
• 11: Fredrik Lindblad. Property directed generation of first-order test data. The Eigth Symposium on Trends in Functional Programming, New York, 2007, to appear.
• 12: Rita Loogen , Francisco Javier López-Fraguas , Mario Rodríguez-Artalejo, A Demand Driven Computation Strategy for Lazy Narrowing, Proceedings of the 5th International Symposium on Programming Language Implementation and Logic Programming, p.184-200, August 25-27, 1993
• 13: Matthew Naylor , Colin Runciman, Finding Inputs that Reach a Target Expression, Proceedings of the Seventh IEEE International Working Conference on Source Code Analysis and Manipulation, p.133-142, September 30-October 01, 2007 [doi>10.1109/SCAM.2007.11]
• 14: Mary Sheeran. Generating Fast Multipliers Using Clever Circuits. In Formal Methods in Computer-Aided Design, 5th International Conference, LNCS 3312. Springer-Verlag, 2004.
• 15: Michael Spivey and Silvija Seres. Embedding Prolog in Haskell. In Haskell Workshop, Paris, September 1999.
• 16: Philip Wadler. Monads for functional programming. In M. Broy, editor, Program Design Calculi: Proceedings of the 1992 Marktoberdorf International Summer School. Springer-Verlag, 1993.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.6 Logic Programming

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

General Terms:
Design, Languages