$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 For a quick introduction, see the TUTORIAL file in the docs directory. 0. TABLE OF CONTENTS 0. Table of Contents 1. Status 2. Requirements 3. Nomenclature 4. What are dynamic types? 5. Using dynamic types a. Compiling Dynaml b. Compiling your application with Dynaml c. Dynamic type annotation d. Casting static values to dynamic values e. Dynamic values and the O'Caml type system f. Casting dynamic values to static values g. Run-time type information 6. Limitations 7. Known Bugs 8. Note on __dynamic_type_id_type and Dynamic.t 9. FAQs 1. STATUS Dynaml is an experimental hack. The latest tagged version is 0-6-alpha. 2. REQUIREMENTS Tested with O'Caml 3.08.3, but other configurations should work. 3. NOMENCLATURE We will refer to standard "dynamic values", which are "dynamically typed", as opposed to O'Caml's standard "static values" which have are "staticically typed". 4. O'CAML AND DYNAMIC TYPES O'Caml is a statically typed language. The O'Caml compiler determines at compile time the type of values. No type information is stored at runtime. This is generally the preferred way for languages to deal with types, and is considered by some one of the strongest advantages of O'Caml and other functional languages. However, in certain circumstances it can be useful to overide these compile time checks. For this purpose dynaml provides values which are not checked by the compiler at compile time, but can have their types inspected at runtime. 5. HOW IT WORKS The type Dynaml.Dynamic.t is the type of dynamic values. Values of this type may contain values of any pretty much any type. The O'Caml compiler has no idea of the true type of the value - it just sees it as type Dynaml.Dynamic.t. The type of the value is stored with the value. This information is used to prevent at runtime unsafe type operations. It is important to note what is being lost here - this kind of error in a program which does not use dynamic types would be caught at compile time. Unsafe operations are prevented by raising an exception. The border between normal O'Caml values (static values) and dynamic values is controlled by casts. There is one cast for converting a static value to a dynamic one, and one cast for converting a dynamic value to a static one. When using each kind of cast, you must specify the real type of the value being cast. In a cast from a static value to a dynamic one, this allows the compiler to create the runtime representation of the type. In the cast from dynamic value to a dynamic one, this allows the value to be checked at runtime for the correct type. In both cases, the compiler ensures that the value going into or coming out of the dynamic type has the correct static type. 6. USING DYNAMIC TYPES To use dynaml, you must compile the library and extension, compile your application with the extension, and link against the library. 6a. COMPILING DYNAML In the distribution directory, type make all 6b. COMPILING YOUR APPLICATION WITH DYNAML You need to compile using camlp4, and load the pa_dynaml extension, and link against the the dynaml.cma library. Bytecode, old syntax: ocamlc -pp "camlp4o -I /dir/to/dynaml/ pa_dynaml.cmo" -I /path/to/dynaml/ dynaml.cmo file.ml Bytecode, revised syntax: ocamlc -pp "camlp4r -I /dir/to/dynaml/ pa_dynaml.cmo" -I /path/to/dynaml/ dynaml.cmo file.ml Native, old syntax: ocamlopt -pp "camlp4o -I /dir/to/dynaml/ pa_dynaml.cmo" dynaml.cmxa file.ml Native, revised syntax: ocamlopt -pp "camlp4r -I /dir/to/dynaml/ pa_dynaml.cmo" dynaml.cmxa file.ml Dynaml is not yet a nice installable package. If you know how best to do this, please do so and I'll gladly accept your changes. 6c. DYNAMIC TYPE ANNOTATIONS To try these examples in the toplevel, include the dynaml directory when you start ocaml: ocaml -I /dir/to/dynaml In the toplevel, type these commands to load the extension: #load "camlp4o.cma" ;; #load "pa_dynaml.cmo" ;; #load "dynaml.cmo" ;; Declaring types which can be made dynamic is very similar to declaring static types. Simply add the keyword "dynamic" to the type declaration as follows: type dynamic foo = Bar | Qux of int ;; Note that this declaration actually creates a new O'Caml static type. The dynamic annotation simply specifies that "this type CAN be made dynamic". 6d. CASTING STATIC VALUES TO DYNAMIC VALUES To convert a standard O'Caml value to a dynamic value, we use the following cast: let x = Qux 10 ;; let dx = x => dynamic foo ;; The value x declared is a static value. dx however, is dynamic. Notice that the cast includes the the static type we are casting from (foo), and the cast contrains the value being cast to have that type. It would therefore be an error to write let dx = "foo" => dynamic foo ;; (* ERROR! *) as the value being cast ("foo") does not have type foo, but rather type string. It is also an error to apply this cast to a value with a type that has not been annotated with the dynamic keyword. let dx = 1 => dynamic int ;; (* ERROR! *) In this case, the error message given is slightly cryptic: Unbound value __dynamic_type_int This error message refers to the fact that the compiler cannot find the run-time type representation for the type int. 6e. DYNAMIC VALUES AND THE O'CAML TYPE SYSTEM All dynamic value haves the type Dynamic.dynamic. Functions which take dynamic types will therefore at compile time accept any dynamic value, regardless of the type of the value inside. Compile-time type checking is therefore effectively disabled for dynamic values. 6f. CASTING DYNAMIC VALUES TO STATIC VALUES The dynamic cast described above has an opposite to convert dynamic values to static values. It allows you to retrieve a static value from a dynamic value: let x = Qux 10 ;; let dx = x => dynamic foo ;; let sx = dx => static foo ;; (* Cast dx back to static value of type foo. *) As for dynamic casts, the type (foo in this case) must be declared with a dynamic annotation. No type check is performed at compile time. When the cast is actually performed at run-time, a check is done to ensure the value being cast has the same type it is being cast to. If the types do not match, Type_error is raised. It is important to note here what should be obvious: using dynamic types effectively delays type checking which would be performed at compile time, and instead does it at run-time. In most situations, this is undesirable - it is better to catch type errors as early as possible. 6g. Dynamic Function Values If a dynamic value is a function, it can have another dynamic value applied to it, using Dynamic.apply. let bar = function Qux n -> Qux (n + 1) | Bar -> Qux 0 ;; let qux = Bar ;; let d_bar = bar => dynamic foo -> foo ;; let d_qux = qux => dynamic foo ;; let d_wibble = Dynamic.apply d_bar d_qux ;; In this example, d_wibble will be a dynamic value. The static value inside d_wibble will have type foo. Type_error will be raised if: * The first argument is not a function, or * The static type of value inside the second argument is not the type expected by the function inside the first argument. 5h. Polymorphism Polymorphic values work as expected. Note that the type must be correctly grounded to work: let d = [1] => dynamic int list ;; (* Yep *) let d = [1] => dynamic 'a list ;; (* Error! list 'a too general. *) Polymorphic functions can also be made dynamic. The rules which govern polymorphic dynamic functions match those which apply to static functions. open Dynamic.DynamicStdTypes ;; let id x = x ;; let d_id_int = id => dynamic int -> int ;; (* OK to restrict type *) let d_id = id => dynamic 'a -> 'a ;; let d_v0 = Dynamic.apply d_id (1 => dynamic int) ;; let d_v1 = Dynamic.apply d_id_int (1 => dynamic int) ;; let d_v2 = Dynamic.apply d_id ("foo" => dynamic string) ;; let d_v3 = Dynamic.apply d_id_int ("foo" => dynamic string) ;; (* Error! d_id_int only accepts ints*) Values returned from functions will have ungeneralisable types. let d_ref = (ref => dynamic 'a -> 'a ref) ;; let d_v = Dynamic.apply d_ref (None => dynamic 'a option) ;; let v0 = d_v => static ref (int option) ;; let v1 = d_v => static ref (string option) ;; (* Error! Value inside d_v has type option int *) The value inside d_v has type ref (option '_a). When d_v is cast to option int in the fourth line, the type of d_v is fixed to being ref (option int). When d_v is then cast to option string, a type error occurs. It is important to note here, the type of dynamic values is mutable. Casting a dynamic value to a static value can modify the type of the value. The type inside a dynamic value will only ever become more specific. 5i. Examining types at runtime 6. LIMITATIONS Objects and polymorphic variants cannot be dynamic. Dynamic value are inevetably far slower than normal values, as type checking is performed at run-time instead of at compile time. Currently type represenations change with each compilation of a module. Dynaml is NOT thread safe, although it probably could be. 7. KNOWN BUGS There are probably many bugs waiting to be discovered. In theory, it should be impossible to write a cast function 'a -> 'b, which does not raise a Type_error. If you discover a way, please e-mail me. :) See also BUGS file. 8. FUTURE WORK Type reflection: As well as storing information about what type a value has, also store information about what a type is (field, constructors etc). This will allow us to write automatically show/read functions. 9. IMPLEMENTATION There are several modules of interest. Type - this contains the representation of O'Caml types, and functions such as type unification. Dynamic - this contains the type of dynamic values, and (unsafe) functions for casting values to and from dynamic. Pa_dynaml - the camlp4 extension. Dynamic values consist of the a record containing the static value, and information about the type of the value. Because the dynamic value can hold pretty much any value, it is cast to unit. When a value is cast to dynamic, the type information is associated with the value. When the value is cast to static, the type information associated with the value is checked against the type it is being cast to. To be able to create this runtime type information, we associate an extra field with each dynamic type. This is called __dynamic_type_foo, where "foo" is the name of the type. For monomorphic types, this is simply a value which uniquely identifies the type. # type dynamic d_unit = DUnit ;; type d_unit = [ DUnit ] value __dynamic_type_d_unit : Type.type_meta = For polymorhic types, the __dynamic_type field is actually a function. It takes further __dynamic_type values as parameters, and returns a dynamic type. # type dynamic 'a d_option = DNone | DSome of 'a ;; type d_option 'a = [ DNone | DSome of 'a ] value __dynamic_type_d_option : Type.type_meta -> Type.type_meta = 10. FAQS Q1. How can "retrofit" a dynamic annotations to a type? A. With a type alias. type dynamic dint = int ; or even type _int = int ; (* Prevent recursive type. *) type dynamic int = _int ; The module Dynaml.DynamicStdTypes has some standard O'Caml types made dynamicable in this way. Q2. Can't the types in the casts be inferred? It's annoying to have to type them everywhere. A. I'm not an expert on type systems, but I know of no theoretical reason why these types could not be inferred in many cases. In practice, I cannot think of any way this could be done in the current implementation. Dynaml has no access to the types inferred by the compiler. Perhaps it's a good thing that the syntax for dynamic types is annoying, as this will discourage people from using them. Static typing is really better in most situations. Q3. Why can't I make polymorphic values dynamic? E.g. (fun x -> x) => dynamic 'a -> 'a ; A. Now you can! :) The limitations are that when you cast back to a standard type, you will get an ungeneralisable type ('_a -> '_'a) Also, when applying dynamic functions with polymorphic variables, the type of the return value is ungeneralisable, just like it would be in standard O'Caml. Q5. Why can't I make objects or polymorphic variants dynamic? A. This would be useful, especially if we could allow objects to be cast to subtypes. However, it would require big improvements to the runtime typing algorithm. I may add this in future. (Or feel free to send me patches. :) ) Q6. I have made a type dynamic with a dynamic annotation, but I can only cast it to dynamic from the module it is declared in. A. You probably have a "dynamic" annotation in the implementation, but not in the declaration in the interface, so dynaml thinks that you don't want to export the dynamic annotation. Add the annotation to the interface. Q7. I have a type alias like this: type foo = bar ;; Why do I get a type error for ((x => dynamic foo) => static bar) even though the types foo and bar are compatible? A. This behaviour could be changed so that no type error occurs. However, I think this is a Bad Idea, as it would break encapsulation. With this change, it would be possible to cast a value of an abstract data type to a compatible type, thus revealing it's implementation. You can write a function that does what you want, thus avoiding the type error. You can catch the type error and try a different cast: let foobar_to_staic x = try x => static foo with Type_error _ -> x => static bar ;; Alternatively, inspect the type of the value at runtime, and apply the appropriate cast: let foobar_to_static x = if has_type (typerep foo) x then x => static foo else if has_type (typerep bar) x then x => static bar else raise (Type_error (lazy "not foo or bar")) ;; You can now also use the alias keyword: type alias foo = bar ;; This creates a dynamic type that foo is compatible with bar. bar must be a dynamic type. Q8. Can I marshall dynamic values? A. In theory you should be able to marshell dynamic values, and unmarshall them in exactly the same program. However, recompiling the program will cause marshalling to fail. (Because type IDs are allocated randomly at compile time.) A possible future fix would be to write type IDs to a file at compile time, and read them back during future compilations so that they are persistent.