A new notation for arrows

ABSTRACT

The categorical notion of monad, used by Moggi to structure denotational descriptions, has proved to be a powerful tool for structuring combinator libraries. Moreover, the monadic programming style provides a convenient syntax for many kinds of computation, so that each library defines a new sublanguage. Recently, several workers have proposed a generalization of monads, called variously "arrows" or Freyd-categories. The extra generality promises to increase the power, expressiveness and efficiency of the embedded approach, but does not mesh as well with the native abstraction and application. Definitions are typically given in a point-free style, which is useful for proving general properties, but can be awkward for programming specific instances. In this paper we define a simple extension to the functional language Haskell that makes these new notions of computation more convenient to use. Our language is similar to the monadic style, and has similar reasoning properties. Moreover, it is extensible, in the sense that new combining forms can be defined as expressions in the host language.

References

1. K. Batcher. Sorting networks and their applications. In AFIPS Spring Joint Conference, pages 307-314, 1968.]]
2. G. Berry and G. Gonthier. The Esterel synchronous programming language: Design, semantics, implementation. Science of Computer Programming, 19(2):87-152. 1992.]]
3. P. Bjesse, K. Claessen, M. Sheeran, and S. Singh. Lava: Hardware design in Haskell. In International Conference on Functional Programming. ACM, 1998.]]
4. R. Blute, J. Cockett, and R. Seely. Categories for computation in context and unified logic. Journal of Pure and Applied Algebra, 116:49-98, 1997.]]
5. M. Carlsson and T. Hallgren. Fudgets - a graphical user interface in a lazy functional language. In FPCA, pages 321-330. ACM Press, 1993.]]
6. P. Caspi, D. Pilaud, N. Halbwachs, and J. Plaice. LUSTRE: A declarative language for programming synchronous systems. In 14th ACM Symposium on Principles of Programming Languages, pages 178-188, Munich, 1987.]]
7. R. Douence and P. Fradet. Towards a taxonomy of functional language implementations. In Programming Languages: Implementations, Logics and Programs, volume 982 of Lecture Notes in Computer Science, pages 34-45, 1995.]]
8. L. Erkk and J. Launchbury. Recursive monadic bindings. In ICFP. 2000.]]
9. M. Hasegawa. Decomposing typed lambda calculus into a couple of categorical programming languages. In CTCS, volume 953 of Lecture Notes in Computer Science. Springer, 1995.]]
10. M. Hasegawa. Recursion from cyclic sharing: Traced monoidal categories and models of cyclic lambda calculi. Jo Proceedings, Third International Conference on Typed Lambda Calculi and Applications (TLC'A '97), volume 1210 of Lecture Notes in Computer Science. Springer, 1997.]]
11. P. Hudak. Modular domain specific languages and tools. In International Conference on Software Reuse, 1998.]]
12. J. Hughes. Generalising monads to arrows. Science of Computer Programming, 37:67-ill, May 2000.]]
13. G. Hutton and E. Meijer. Monadic parsing in Haskell. Journal of Functional Programming. 8(4):437-444, 1998.]]
14. G. Jones and M. Sheeran. Collecting butterflies. Technical Monograph PRC-91, Oxford University Computing Laboratory, Programming Research Group. Feb. 1991.]]
15. G. Jones and M. Sheeran. Designing arithmetic circuits by refinement in Ruby. In R. Bird, C. Morgan, and 3. Woodcock, editors, Mathematics of Program Construction, volume 669 of Lecture Notes in Computer Science, pages 208-232. Springer, 1993.]]
16. A. Joyal, R. Street, and D. Verity. Traced monoidal categories. Mathematical Proceedings of the Cambridge Philosophical Society. 119(3):447-468, 1996.]]
17. G. Kahn. The semantics of a simple language for parallel programming. In IFIP 74. North Holland, 1974.]]
18. R. Ladner and M. Fischer. Parallel prefix computation. J. ACM, 27:831-838, 1980.]]
19. P. J. Landin. The next 700 programming languages. Communications of the ACM, 9(3):157-164, 1966.]]
20. J. Launchbury, J. Lewis, and B. Cook. On embedding a niicroarchitecture design language within Haskell. In International Conference on Functional Programming. ACM, 1999.]]
21. J. Misra. Powerlist: A structure for parallel recursion. ACM Trans. Ping. Lang. Syst., 16(6):1737-1767, Nov. 1994.]]
22. E. Moggi. Computational lambda-calculus and monads. In Logic in Computer Science. IEEE, 1989.]]
23. J. Nordlander. Reactive Objects and Functional Programming. PhD thesis, Dept. of Computing Science, Chalmers University of Technology, 1999.]]
24. S. Peyton Jones, J. Hughes, et al. Haskell 98: A non-strict, purely functional language, Feb. 1999.]]
25. A. Power. Elementary control structures. In CONCUR'96: Concurrency Theory, volume 1119 of Lecture Notes in Computer Science, pages 115-130. Springer, 1996.]]
26. J. Power and E. Robinson. Premonoidal categories and notions of computation. Mathematical Structures in Computer Science, 7(5):453-468, Oct. 1997.]]
27. J. Power and H. Thielecke. Closed Freyd- and kappa-categories. In ICALP, volume 1644 of LNCS. Springer, 1999.]]
28. S. D. Swierstra and L. Duponcheel. Deterministic, error-correcting combiriator parsers. In J. Launchhury, E. Meijer, and T. Sheard, editors, Advanced Functional Programming, volume 1129 of Lecture Notes in Computer Science, pages 184-207. Springer, 1996.]]
29. W. Wadge and E. Ashcroft. Lucid, the Dataflow Programming Language. Academic Press, 1985.]]
30. P. Wadler. The essence of functional programming. In 19th ACM Symposium on Principles of Programming Languages, pages 1-14, Albuquerque, NM, Jan. 1992.]]

Index Terms

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language features

      • Language types

        • Functional languages