$Id: README 78 2005-01-25 11:44:04Z jim $ O'Caml Dynamic Types Extensions ******************************* This is an experimental hack for O'Caml which adds dynamic run-time typing. Copyright (C) 2004-5 Jim Farrand This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA As a special exception to the GNU Library General Public License, you may link, statically or dynamically, a "work that uses the Library" with a publicly distributed version of the Library to produce an executable file containing portions of the Library, and distribute that executable file under terms of your choice. For copyright details see the file LGPL-2.1 included in this distribution. Web-page: http://farrand.net/dynaml.shtml O'Caml Dynamic Types Extensions Tutorial **************************************** For a more serious reference manual, see the MANUAL file in the docs directory. 1. Lets play In the distribution directory, build dynaml: make all Then in the same directory, run O'Caml: $ rlwrap ocaml Objective Caml version 3.08.3 # #use "docs/ocamlinit.tutorial" ;; - : unit = () Camlp4 Parsing version 3.08.3 # let l0 = [1] ;; val l0 : int list = [1] # let l1 = ["foo"] ;; val l1 : string list = ["foo"] # let l2 = [1;"foo"] ;; This expression has type string but is here used with type int Normally, you can't have a list containing both an int and a string. Dynaml allows create dynamic values. As far as O'Caml is concerned, all dynamic values have the same type, so you can put a dynamic int and a dynamic string into the same list. # let l2 = [1 => dynamic int; "foo" => dynamic string] ;; val l2 : Dynaml.Dynamic.t list = [(1 => dynamic int); ("foo" => dynamic string)] # The cast (foo => dynamic int) takes the O'Caml value foo, which has type int, and turns it into a dynamic value. A lot of things can be made dynamic, including polymorphic functions. Here is a silly function: # let f = (fun a b -> (b,[(1,true)])) => dynamic 'a -> 'b -> ('b * (int * bool) list) ;; val f : Dynaml.Dynamic.t = ( => dynamic ('a25 -> ('b16 -> (tuple2 'b16 (list (tuple2 int bool)))))) At the moment, types displayed by dynaml are in revised syntax, that is type variables follow a type, they don't preceed it. (list 'a as opposed to 'a list). I may change this, or make it configurable. Also, a pair is displayed as (tuple2 'a 'b) rather than ('a * 'b). You can apply a list of dynamic values to a dynamic function Here we give it an int and string: # apply_l f [1 => dynamic int; "foo" => dynamic string] ;; - : Dynaml.Dynamic.t = (("foo", [(1, True)]) => dynamic (tuple2 string (list (tuple2 int bool)))) Note that apply_l cannot be written in plain old O'Caml, as the return type of apply_l depends on the length of the list of paramters it is given. 2. Getting back to normal Sooner or later, you will want to get the normal static value out of a dynamic value. We'll demonstrate with x, a dynamic int: # let x = 1 => dynamic int ;; val x : Dynaml.Dynamic.t = (1 => dynamic int) To get the static value out of x, you use another cast: # let y = x => static int ;; val y : Dynaml.StdTypes.int = 1 If you like to break things, you probably already tried to cheat, and cast the value to something other than what it is. Here is what happened: # let y = x => static string ;; Exception: Dynamic.Type_error _. That type error isn't very helpful. You can get a more helpful one, you just won't see it by default because it takes a bit of CPU time to format. (Not a huge amount, but sometimes you will want to catch Type_error and deal with it, and the user will never see the message.) The function display_type_error takes a function, and returns a function. The returned function is the same as the given function, except that any Type_error exceptions are turned into Type_error' exceptions which are a bit more helpful: # display_type_error ;; - : ('a -> 'b) -> 'a -> 'b = # display_type_error (fun () -> x => static string) () ;; Exception: Dynamic.Type_error' "casting to incorrect type: expected value of type string but value has type int". Dynaml knows the type of x is really int, so it can't be fooled into casting it to string. The key difference between static and dynamic typing is that static typing is done at compile time, and dynamic typing at runtime. When you cast to a dynamic value, dynaml tags the value with a runtime representation of the values type. When you cast to a static value, dynaml checks that the type you are casting to is compatible with the the value that is being cast. The static type you cast to can be more specific than the actual type: # let id x = x ;; val id : 'a -> 'a = # let idd = id => dynamic 'a -> 'a ;; val idd : Dynaml.Dynamic.t = ( => dynamic ('a26 -> 'a26)) # idd => static 'a -> 'a ;; - : '_a -> '_a = # idd => static int -> int ;; - : Dynaml.StdTypes.int -> Dynaml.StdTypes.int = Dynaml.StdTypes.int is just an alias for the standard type int. Any type that is going to be made dynamic needs a special declaration. Standard types like int don't have that special declaration, so they are provided in Dynaml.StdTypes. The next section will explain how you declare types that can be made dynamic. 3. Rolling your own A type that is going to be made dynamic needs a special anotation in it's type declaration. # type dynamic foo = Bar | Qux ;; type foo = Bar | Qux val __dynamic_type_foo : Dynaml.Type.type_meta = foo The word "dynamic" before the type name is all you need to allow the type to be made dynamic. If you need to "retrofit" a type in a module you don't own, you can just use a type alias. # type dynamic dynamic_wib = Wib.wib ;; type dynamic_wib = Wib.wib val __dynamic_type_dynamic_wib : Dynaml.Type.type_meta = dynamic_wib In casts, you must mention the name of the type alias (dynamic_wib), NOT the name of the actual type. Indeed, even if the actual type is also dynamic, type aliases are not compatible by default: # type dynamic fooo = foo ;; type fooo = foo val __dynamic_type_fooo : Dynaml.Type.type_meta = fooo # display_type_error (fun () -> (Bar => dynamic foo) => static foo) () ;; - : foo = Bar # display_type_error (fun () -> (Bar => dynamic foo) => static fooo) () ;; Exception: Dynamic.Type_error' "casting to incorrect type: expected value of type fooo but value has type foo". This may be a bit surprising, but it is to stop you breaking encapsulation. A module might export an abstract type, and implement it as a type alias. Without this restriction you could cast the abstract value to it's actual type, thus exposing the implementation. If you want a type alias to be compatible, use the alias anotation, instead of dynamic: # type alias fooo = foo ;; type fooo = foo val __dynamic_type_fooo : Dynaml.Type.type_meta = foo # display_type_error (fun () -> (Bar => dynamic foo) => static fooo) () ;; - : fooo = Bar Unlike types declared with the "dynamic" anotation, when a type is declared with "alias", the target type must also be dynamic.` You are probably wondering what those __dynamic__type values are that pop up whenever you declare a dynamic type. These are the run-time representation of the type. When you to a to dynamic cast, dynaml grabs the __dynamic_type value and bundles it together with the actual value. That is why you will get slightly confusing error messages if you forget a "dynamic" annotation: # type foooo = Bar | Qux ;; type foooo = Bar | Qux # Bar => dynamic foooo ;; Unbound value __dynamic_type_foooo Dynaml compile time error messages are, by and large, rubbish. For reference, this is what happens if you supply the wrong type in a dynamic cast: # 1 => dynamic string ;; Signature mismatch: Modules do not match: sig val dynamic_value : int end is not included in sig val dynamic_value : Dynaml.StdTypes.string end Values do not match: val dynamic_value : int is not included in val dynamic_value : Dynaml.StdTypes.string 4. Naval Gazing You can inspect the type of a value at runtime, and therefore write a function that has different behaviour depending upon the type of it's parameter. # open Dynaml.Type ;; # let show d = let t = get_type d in if type_meta_equivelent t (typerep int) then print_endline (string_of_int (d => static int)) else if type_meta_equivelent t (typerep string) then print_endline (d => static string) else print_endline "" ;; val show : Dynaml.Dynamic.t -> unit = # show (1 => dynamic int) ;; 1 - : unit = () foo - : unit = () # show (true => dynamic bool) ;; - : unit = () As you can see, this function can print ints and strings. There are a couple of new things here. First of all, a typerep expression allows you create a runtime type representation without doing a cast: # typerep int ;; - : Dynaml.Type.type_meta = int It's important you understand the different between Dynaml.Dynamic.t and Dynaml.Type.type_meta. The first is a dynamic value (consisting of the value and the type of that value), the second is just a type, with NO value. If you have a dynamic value, you can get it's type with get_type: # let x = 1 => dynamic int ;; val x : Dynaml.Dynamic.t = (1 => dynamic int) # get_type x ;; - : Dynaml.Type.type_meta = int Types can be compared with the function type_meta_equivelent in the module Dynaml.Type: # type_meta_equivelent (typerep int) (typerep int) ;; - : bool = true # type_meta_equivelent (typerep int) (typerep 'a list) ;; - : bool = false # type_meta_equivelent (typerep 'a list) (typerep 'b list) ;; - : bool = true Notice the last example, 'a list and 'b list compare equivelent, because they are the same type with different variables. There is another comparision function which returns true only if it's paramaters are exactly the same, including type variables. However, this still may not work exactly as you expect: # type_meta_equal (typerep 'a list) (typerep 'b list) ;; - : bool = false # type_meta_equal (typerep 'a list) (typerep 'a list) ;; - : bool = false The second example returns false, because the 'a on the left is not the same 'a as the one on the right. Type variables in different type expressions are different, even if they have the same name. # let t = typerep 'a list ;; val t : Dynaml.Type.type_meta = (list 'a31) # type_meta_equal t t ;; - : bool = true To convince yourself that type variables in different expressions are different, grab the type of 'a list a couple more times: # typerep 'a list ;; - : Dynaml.Type.type_meta = (list 'a32) # typerep 'a list ;; - : Dynaml.Type.type_meta = (list 'a33) Notice that each time you get a new variable (here 'a32 and 'a33, but yours may be different). 4. Systems Overload This example above effectively demonstrates overloading is possible, but it is a pretty simple example. Dynaml has some modules to help with more complex overloading. We'll use Dynaml.DynamicEquality. This helps with comparing dynamic values for equality. # open Dynaml.DynamicEquality ;; # dynamic_equal (1 => dynamic int) (1 => dynamic int) ;; Exception: DynamicEquality.Not_comparable. This failed, because DynamicEquality doesn't yet know how to compare and int with an int (or any other values, for that matter). To make it work, we will register an equality function. The simplist functions that dynamic equality uses take a pair of values, and return true if they are the same, false otherwise, so our equality function will have type (int * int) -> bool. # register ((fun (a,b) -> a = b) => dynamic (int * int) -> bool) ;; - : unit = () # dynamic_equal (1 => dynamic int) (1 => dynamic int) ;; - : Dynaml.DynamicEquality.OverloadedEquality.ret = true # dynamic_equal (1 => dynamic int) (2 => dynamic int) ;; - : Dynaml.DynamicEquality.OverloadedEquality.ret = false Of course, an overloaded equality function is no good if it can only compare one type, so lets register another equality function. # register ((fun (a,b) -> a = b) => dynamic (string * string) -> bool) ;; - : unit = () # dynamic_equal ("foo" => dynamic string) ("foo" => dynamic string) ;; - : Dynaml.DynamicEquality.OverloadedEquality.ret = true # dynamic_equal ("foo" => dynamic string) ("bar" => dynamic string) ;; - : Dynaml.DynamicEquality.OverloadedEquality.ret = false When you call dynamic_equal, it automatically selects an appropriate function according to what types it is called with. # dynamic_equal (1 => dynamic int) ("foo" => dynamic string) ;; Exception: DynamicEquality.Not_comparable. It should be obvious why this fails, neither function we registered can deal with an int and a string. If you really want to compare ints and strings, you can: # register ((fun (a,b) -> string_of_int a = b) => dynamic (int * string) -> bool) ;; - : unit = () # dynamic_equal (1 => dynamic int) ("foo" => dynamic string) ;; - : Dynaml.DynamicEquality.OverloadedEquality.ret = false # dynamic_equal (1 => dynamic int) ("1" => dynamic string) ;; - : Dynaml.DynamicEquality.OverloadedEquality.ret = true # dynamic_equal ("foo" => dynamic string) (1 => dynamic int) ;; Exception: DynamicEquality.Not_comparable. (This is not the smartest way to implement this function, as 0 and "00" will compare not equal, but we are just playing, so it will do.) The final example above fails, because we have registered a function to compare int and string, but no function to compare string and int. Dynamic equality is not (yet) smart enough to try flipping the arguments. Equality functions can be polymorphic: # register ((fun (a,b) -> a == b) => dynamic ('a * 'a) -> bool) ;; - : unit = () This function can be called on any two values, so long as they have the same type. # dynamic_equal (true => dynamic bool) (true => dynamic bool) ;; - : Dynaml.DynamicEquality.OverloadedEquality.ret = true # dynamic_equal (true => dynamic bool) (false => dynamic bool) ;; - : Dynaml.DynamicEquality.OverloadedEquality.ret = false What will happen now if we call dynamic_equal with two ints? There are two functions which could be applied. One has type ((int * int) -> bool) and the other (('a * 'a) -> bool). DynamicEquality chooses the former, as this has the most specific type. (To work out if type a is more specific then type b, ask yourself if you can substitute the type variables in b to make it equal to a. If you can, a is more specific than b.) Next, we want to compare lists. With what you have learnt so far, you could register functions for comparing (int list), (string list), (bool list) etc. Or you could register a function that compares ('a list). This function would have to compare the elements of the list somehow, probably with (=) or (==). You might prefer to have a list equality function which uses dynamic_equal to compare elements. If you try to implement this you will be disappointed to discover that you can't. Equality functions receive static values, not dynamic ones, and there is no way to make a dynamic value containing an element of the list, without knowing the type of the list. But being able to do this is incredibly useful, so DynamicEquality provides another mechanism to achieve the same. The recursion is just moved out of the equality function into dynamic_equal. Instead of the list equality function calling dynamic_equal to get a comparison function for comparing it's elements, it is provided with this function as a parameter. Things will be clearer if we look at the type of a possible list equality function: (('a * 'b) -> bool) -> ('a list * 'b list) -> bool ; Notice that the right hand side of this type looks like the simple equality functions from before (it takes a pair and returns bool). Also notice that the left hand side also looks like a simple equality function. This function takes a helper function which can compare type 'a and 'b, and returns an equality function that can compare 'a list and 'b list. The implementation looks like this: let rec list_equal helper = function ([],[]) -> true | (h0::t0, h1::t1) -> if helper (h0, h1) then list_equal helper (t0,t1) else false | _ -> false ;; Lets register this function and try it out: # let rec list_equal helper = function ([],[]) -> true | (h0::t0, h1::t1) -> if helper (h0, h1) then list_equal helper (t0,t1) else false | _ -> false ;; val list_equal : ('a * 'b -> bool) -> 'a list * 'b list -> bool = # register (list_equal => dynamic ('a * 'b -> bool) -> 'a list * 'b list -> bool) ;; - : unit = () # dynamic_equal ([1] => dynamic int list) (["1"] => dynamic string list) ;; - : Dynaml.DynamicEquality.OverloadedEquality.ret = true # dynamic_equal ([1] => dynamic int list) (["foo"] => dynamic string list) ;; - : Dynaml.DynamicEquality.OverloadedEquality.ret = false It's important to understand what happened here. dynamic_equal looked up the equality function for comparing (int list) and (string list). ('a * 'b -> bool) -> 'a list * 'b list -> bool When the function is called, the final parameter will have type (int list * string list). That type is "plugged into" the type of the function, giving the following type: (int * string -> bool) -> int list * string list -> bool The first parameter is a helper function. A recursive call occurs to lookup the equality function with type (int * string -> bool). The list equality function is then called with the helper function and the values to compare. We still have a problem when comparing lists. If we call dynamic_equal with two lists of the same type, the equality function seems to break: # dynamic_equal ([1] => dynamic int list) ([1] => dynamic int list) ;; - : Dynaml.DynamicEquality.OverloadedEquality.ret = false # dynamic_equal ([true] => dynamic bool list) ([true] => dynamic bool list) ;; - : Dynaml.DynamicEquality.OverloadedEquality.ret = false At first this seemed to me like a bug. It turns out, our list comparison function is not even being called. We have registered two equality functions, with types ('a * 'b -> bool) -> 'a list * 'b list -> bool ('a * 'a) -> bool These functions work on values with types ('a list * 'b list) ('a * 'a) Neither of these types is more specific. To make ('a * 'a) equal to ('b list * 'c list), we would have to substitute 'a for both ('b list) and ('c list). As neither equality function is more specific, dynamic_equal arbitrarily choose ('a * 'a). We can easily fix this: # register (list_equal => dynamic ('a * 'a -> bool) -> 'a list * 'a list -> bool) ;; - : unit = () # dynamic_equal ([1] => dynamic int list) ([1] => dynamic int list) ;; - : Dynaml.DynamicEquality.OverloadedEquality.ret = true We have just registered the same function again, but with a more specific type. This type is more specific than ('a * 'a), so it is given priority. 5. Coming soon to a Dynaml tutorial near you In the future, this tutorial will tell you how to make your own overloaded function. In the meantime, you might be able to work it out from the API docs.