From 1624ef3baf638776108ab974fa392035d6f387f8 Mon Sep 17 00:00:00 2001 From: simonpj Date: Mon, 4 Feb 2002 12:14:50 +0000 Subject: [PATCH] [project @ 2002-02-04 12:14:50 by simonpj] Add a bit of documentation on implicit params --- ghc/docs/users_guide/glasgow_exts.sgml | 79 +++++++++++++++++++++++++++++++- 1 file changed, 77 insertions(+), 2 deletions(-) diff --git a/ghc/docs/users_guide/glasgow_exts.sgml b/ghc/docs/users_guide/glasgow_exts.sgml index 0fbb00b..ff05c45 100644 --- a/ghc/docs/users_guide/glasgow_exts.sgml +++ b/ghc/docs/users_guide/glasgow_exts.sgml @@ -1210,10 +1210,85 @@ J Lewis, MB Shields, E Meijer, J Launchbury, 27th ACM Symposium on Principles of Programming Languages (POPL'00), Boston, Jan 2000. +(Most of the following, stil rather incomplete, documentation is due to Jeff Lewis.) + +A variable is called dynamically bound when it is bound by the calling +context of a function and statically bound when bound by the callee's +context. In Haskell, all variables are statically bound. Dynamic +binding of variables is a notion that goes back to Lisp, but was later +discarded in more modern incarnations, such as Scheme. Dynamic binding +can be very confusing in an untyped language, and unfortunately, typed +languages, in particular Hindley-Milner typed languages like Haskell, +only support static scoping of variables. + + +However, by a simple extension to the type class system of Haskell, we +can support dynamic binding. Basically, we express the use of a +dynamically bound variable as a constraint on the type. These +constraints lead to types of the form (?x::t') => t, which says "this +function uses a dynamically-bound variable ?x +of type t'". For +example, the following expresses the type of a sort function, +implicitly parameterized by a comparison function named cmp. + + sort :: (?cmp :: a -> a -> Bool) => [a] -> [a] + +The dynamic binding constraints are just a new form of predicate in the type class system. + + +An implicit parameter is introduced by the special form ?x, +where x is +any valid identifier. Use if this construct also introduces new +dynamic binding constraints. For example, the following definition +shows how we can define an implicitly parameterized sort function in +terms of an explicitly parameterized sortBy function: + + sortBy :: (a -> a -> Bool) -> [a] -> [a] + sort :: (?cmp :: a -> a -> Bool) => [a] -> [a] + sort = sortBy ?cmp + +Dynamic binding constraints behave just like other type class +constraints in that they are automatically propagated. Thus, when a +function is used, its implicit parameters are inherited by the +function that called it. For example, our sort function might be used +to pick out the least value in a list: + + least :: (?cmp :: a -> a -> Bool) => [a] -> a + least xs = fst (sort xs) + +Without lifting a finger, the ?cmp parameter is +propagated to become a parameter of least as well. With explicit +parameters, the default is that parameters must always be explicit +propagated. With implicit parameters, the default is to always +propagate them. + -There should be more documentation, but there isn't (yet). Yell if you need it. +An implicit parameter differs from other type class constraints in the +following way: All uses of a particular implicit parameter must have +the same type. This means that the type of (?x, ?x) +is (?x::a) => (a,a), and not +(?x::a, ?x::b) => (a, b), as would be the case for type +class constraints. + + +An implicit parameter is bound using an expression of the form +expr with binds, +where with is a new keyword. This form binds the implicit +parameters arising in the body, not the free variables as a let or +where would do. For example, we define the min function by binding +cmp. + + min :: [a] -> a + min = least with ?cmp = (<=) + +Syntactically, the binds part of a with construct must be a +collection of simple bindings to variables (no function-style +bindings, and no type signatures); these bindings are neither +polymorphic or recursive. + +Note the following additional constraints: You can't have an implicit parameter in the context of a class or instance @@ -1227,8 +1302,8 @@ you invoke a function. But the ``invocation'' of instance declarations is done behind the scenes by the compiler, so it's hard to figure out exactly where it is done. Easiest thing is to outlaw the offending types. - + -- 1.7.10.4