Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] Efficiency of 'a list
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2003-05-04 (07:35)
From: John Max Skaller <skaller@o...>
Subject: Re: [Caml-list] Two types of efficiency (Was Efficiency of 'a list)
Mattias Waldau wrote:

> Languages like PHP have more advanced built-in datastructures with
> language syntax to support them. In Ocaml, we can create the same
> program, however, there is no syntax support, and we have to add
> declarations like
> module StringSet = Set.Make(struct 
>       type t = string
>       let compare = compare
>     end) ;;
> It would be nice if the typechecker could deduce the type of the set and
> add the above declaration automatically to the program. That would make
> it easier for beginners to use the advanced datastructures of Ocaml.

The problem is worse than that. There are places you need such
an animal but CANNOT have it. This occurs when there is type
recursion involved and the lack of orthogonality in Ocaml syntax
prevents you actually declaring the functor instance
at the point you need it.

This occurs in a class where for example you have a set
of references to that class passed to one of the
methods of the class: the functor instantiation
requires the class type to be complete, but it
cannot be completed until the functor is instantiated.

[You need to declare the functor inside the class
but before the object]

Result: dont use functors, they're not properly

I found this really annoying. It applies in
other parts of the language too, for example
polymorphic variants. Here again, the very
feature functional languages are supposed to
understand best -- recursion -- is actually
handled better in C++.

I need variants whose arguments include the variant

type, and I can't have them together with subtyping.
Yet for someone representing
a programming language recursion is natural.

type x = [`A | `B of y]
and y = [x | `C of x]

There is no problem doing this with textual substitution:

type x = [`A | `B of y]
and y = [`A | `B of y | `C of x]

Similarly, subtyping of polymorphic variants is invariant
in the arguments, when covariance is sound and more useful.
This is a real pain for me, since it destroys the main use
I hoped to obtain for polymorphic variants:

type x = [`A | `B of x]
type y = [`A | `B of y | `C]

x *is* a subtype of y, but the type system
disallows it, failing to recognise that every `B x
of type x is also a `B y of y. Typically I have
say a term for an expression and I want to eliminate
some cases by say a term reduction, but I can't restrict
the resultant type as desired because there's no way
to 'narrow' the type recursion.

So here are two cases where

(a) syntax


(b) loss of semantic expressivity

reduce the utility of the language.

Luckily, the ocaml team is working on such things:
local modules, for example, help considerably.
Its somewhat unfortunate that the syntactic constraints
often make a clean solution difficult, for example:

type x = ...
and class ..

woops: you cant inter-recurse classes and types.
You have to use a trick: make the class parametric,
then inter-recurse the type x and the instantiation
passing x as the argument: ugg. The restriction appears
to be entirely a matter of syntax: to distinguish
classes and types you'd need the 'type' and 'class'
keyword on each conjunct which breaks:

	type x = .. and y = ..

It would appear that the diverse nature of things
to be declared indicates this syntax, along with

	let x = .. and y = ..

is in fact wrong: better to have required:

	let type x = .. and val y = .. and class z = ..

As we see in C++, historically sound syntax soon
breaks with language extensions :(

John Max Skaller,
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.

To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: