Functional pearl: implicit configurations--or, type classes reflect the values of types

ABSTRACT

The configurations problem is to propagate run-time preferences throughout a program, allowing multiple concurrent configuration sets to coexist safely under statically guaranteed separation. This problem is common in all software systems, but particularly acute in Haskell, where currently the most popular solution relies on unsafe operations and compiler pragmas.We solve the configurations problem in Haskell using only stable and widely implemented language features like the type-class system. In our approach, a term expression can refer to run-time configuration parameters as if they were compile-time constants in global scope. Besides supporting such intuitive term notation and statically guaranteeing separation, our solution also helps improve the program's performance by transparently dispatching to specialized code at run-time. We can propagate any type of configuration data-numbers, strings, IO actions, polymorphic functions, closures, and abstract data types. No previous approach to propagating configurations implicitly in any language provides the same static separation guarantees.The enabling technique behind our solution is to propagate values via types, with the help of polymorphic recursion and higher-rank polymorphism. The technique essentially emulates local type-class instance declarations while preserving coherence. Configuration parameters are propagated throughout the code implicitly as part of type inference rather than explicitly by the programmer. Our technique can be regarded as a portable, coherent, and intuitive alternative to implicit parameters. It motivates adding local instances to Haskell, with a restriction that salvages principal types.

REFERENCES

• 1: J. Adriano. Re: I need some help. Message to the Haskell mailing list; http://www.mail-archive.com/[e-mail]/msg10565.html, 26 Mar.2002.
• 2: M. Blume. No-longer-foreign: Teaching an ML compiler to speak C "natively". In P. N. Benton and A. Kennedy, editors, BABEL'01: 1st International Workshop on Multi-Language Infrastructure and Interoperability, number 59(1) in Electronic Notes in Theoretical Computer Science, Amsterdam, Nov. 2001. Elsevier Science.
• 3: A. Bromage. Dealing with configuration data. Message to the Haskell mailing list; http://www.haskell.org/pipermail/haskell-cafe/2002-September/003411.html, Sept. 2002.
• 4: M. Chakravarty, S. Finne, F. Henderson, M. Kowalczyk, D. Leijen, S. Marlow, E. Meijer, S. Panne, S. L. Peyton Jones, A. Reid, M. Wallace, and M. Weber. The Haskell 98 foreign function interface 1.0: An addendum to the Haskell 98 report. http://www.cse.unsw.edu.au/~chak/haskell/ffi/, 2003.
• 5: K. Claessen. Dealing with configuration data. Message to the Haskell mailing list; http://www.haskell.org/pipermail/haskell-cafe/2002-September/003419.html, Sept. 2002.
• 6: Cordelia V. Hall , Kevin Hammond , Simon L. Peyton Jones , Philip L. Wadler, Type classes in Haskell, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.2, p.109-138, March 1996 [doi>10.1145/227699.227700]
• 7: L. Hu et al. Dealing with configuration data. Messages to the Haskell mailing list; http://www.haskell.org/pipermail/haskell-cafe/2002-September/thread.html, Sept. 2002.
• 8: J. Hughes. Restricted datatypes in Haskell. In E. Meijer, editor, Proceedings of the 1999 Haskell Workshop, number UU-CS-1999-28 in Tech. Rep. Department of Computer Science, Utrecht University, 1999.
• 9: John Hughes, Global variables in Haskell, Journal of Functional Programming, v.14 n.5, p.489-502, September 2004 [doi>10.1017/S0956796802004471]
• 10: M. P. Jones. Dictionary-free overloading by partial evaluation. In Proceedings of the 1994 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, New York, 1994. ACM Press.
• 11: Mark P. Jones, Type Classes with Functional Dependencies, Proceedings of the 9th European Symposium on Programming Languages and Systems, p.230-244, April 02, 2000
• 12: W. Kahan. How Java's floating-point hurts everyone everywhere. Invited talk, ACM 1998 Workshop on Java for High-Performance Network Computing; http://www.cs.ucsb.edu/conferences/java98/papers/javahurt.pdf, 1 Mar. 1998.
• 13: W. Kahl and J. Scheczyk. Named instances for Haskell type classes. In R. Hinze, editor, Proceedings of the 2001 Haskell Workshop, number UU-CS-2001-23 in Tech. Rep., pages 71--99. Department of Computer Science, Utrecht University, 2 Sept. 2001.
• 14: O. Kiselyov. Pure file reading (was: Dealing with configuration data). Message to the Haskell mailing list; http://www.haskell.org/pipermail/haskell-cafe/2002-September/003423.html, Sept. 2002.
• 15: O. Kiselyov and C.-c. Shan. Functional pearl: Implicit configurations-or, type classes reflect the values of types. Technical Report TR-15-04, Harvard University, Cambridge, 2004.
• 16: Israel Koren, Computer Arithmetic Algorithms, A. K. Peters, Ltd., Natick, MA, 2001
• 17: John Launchbury , Simon L. Peyton Jones, Lazy functional state threads, ACM SIGPLAN Notices, v.29 n.6, p.24-35, June 1994
• 18: John Launchbury , Simon L. Peyton Jones, State in Haskell, Lisp and Symbolic Computation, v.8 n.4, p.293-341, Dec. 1995 [doi>10.1007/BF01018827]
• 19: Jeffrey R. Lewis , John Launchbury , Erik Meijer , Mark B. Shields, Implicit parameters: dynamic scoping with static types, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.108-118, January 19-21, 2000, Boston, MA, USA [doi>10.1145/325694.325708]
• 20: Sheng Liang , Paul Hudak , Mark Jones, Monad transformers and modular interpreters, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.333-343, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199528]
• 21: Conor McBride, Faking it Simulating dependent types in Haskell, Journal of Functional Programming, v.12 n.5, p.375-392, July 2002 [doi>10.1017/S0956796802004355]
• 22: P. L. Montgomery. Modular multiplication without trial division. Mathematics of Computation, 44(170):519--521, Apr. 1985.
• 23: Chris Okasaki, From fast exponentiation to square matrices: an adventure in types, ACM SIGPLAN Notices, v.34 n.9, p.28-35, Sept. 1999
• 24: OpenSSL. The open source toolkit for SSL TLS. Version 0.9.7d; http://www.openssl.org/, 17 Mar. 2004.
• 25: Behrooz Parhami, Computer arithmetic: algorithms and hardware designs, Oxford University Press, Oxford, 1999
• 26: S. L. Peyton Jones. Solution to the monomorphism restriction implicit parameter problem. Message to the Haskell mailing list; http://www.haskell.org/pipermail/haskell/2003-August/012412.html, 5 Aug. 2003.
• 27: S. L. Peyton Jones and M. B. Shields. Lexically-scoped type variables, Mar. 2002. To be submitted to Journal of Functional Programming.
• 28: Christian Queinnec , Kathleen Callaway, Lisp in small pieces, Cambridge University Press, New York, NY, 1996
• 29: G. Russell. Initialisation without unsafePerformIO. Message to the Haskell mailing list; http://www.haskell.org/pipermail/haskell/2004-June/014104.html, June 2004.
• 30: Michael A Soderstrand , W Kenneth Jenkins , Graham A Jullien , Fred J Taylor, Residue number system arithmetic: modern applications in digital signal processing, IEEE Press, Piscataway, NJ, 1986
• 31: D. Thurston. Modular arithmetic. Messages to the Haskell mailing list; http://www.haskell.org/pipermail/haskell-cafe/2001-August/002132.html; http://www.haskell.org/pipermail/haskell-cafe/2001-August/002133.html, 21 Aug. 2001.
• 32: Valery Trifonov, Simulating quantified class constraints, Proceedings of the 2003 ACM SIGPLAN workshop on Haskell, p.98-102, August 28-28, 2003, Uppsala, Sweden [doi>10.1145/871895.871906]
• 33: P. Wadler , S. Blott, How to make ad-hoc polymorphism less ad hoc, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.60-76, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75283]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.1 Applicative (Functional) Programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
      D.3.3 Language Constructs and Features
          Subjects: Polymorphism; Abstract data types; Recursion

General Terms:
Design, Languages

Keywords:
existential types, higher-rank polymorphism, implicit parameters, polymorphic recursion, type classes