Re: Stdlib regularity

From: skaller (skaller@maxtal.com.au)
Date: Fri Oct 08 1999 - 16:56:26 MET DST


Date: Sat, 09 Oct 1999 00:56:26 +1000
From: skaller <skaller@maxtal.com.au>
To: Francisco Valverde Albacete <fva@tsc.uc3m.es>
Subject: Re: Stdlib regularity

Francisco Valverde Albacete wrote:
> But we never got into
> OCaml strictly for time-efficiency reasons, did we?

        In my case, no, but it is still vital, otherwise
I'd use Haskell instead :-)

        In particular, because procedural algorithms can be
implemented in ocaml just like in C++, the same complexity
_should_ be obtainable, and work on optimisation plus
standard library support should allow 'close' to
unit performance factors.

        There are several cases where the core language prevents
this, because it lacks functionality available in C++: the ability
to create uninitialised values, and the ability to destroy them
are two that I've become aware of trying to build a variable length
array module. Both these features seem mandatory. Both are unsafe.
A reasonable compromise might be:

        do not implement the features in the standard bytecode interpreter
        do not allow these features in the compiler unless a special switch is
specified

Unfortunately, I do not think it is 'enough' to provide a variable
length array in the standard library, because that is only one
data structure which cannot be implemented efficiently or cleanly
without these features.

        There is another more serious problem: ocaml doesn't
handle recursive types well. I'm not sure I fully understand this.
When all values are boxed, all recursion of algebraic types is sound.
[Proof: it is sound in C, where all non datum values are represented
by pointers; note that _initialising_ the structure may not be possible
in ocaml unless uninitialised values are permitted]

        It is not clear to me if the result extends to modules.
However, the lack of recursion across module boundaries is also
pain. In trying to implement a variable length array, I found
that I needed to work around the inability to create an uninitialised
array by using a functor whose argument supplied the array value
type and special value of that type to initialise the array with.

        Unfortunately, the type of the instantiated functor's
aggregate component was a variant of the type over which it
needed to be instantiated. So this solution cannot work.
To exhibit the problem more plainly, it is something like:

        type t' = X | Y of G.t
        where module G = V.Make(sig type t = t'; val default = X)

[In the actual code, the type of a python expression, 'expr', includes
a case Initial suitable for initialising an array, and a case
'V of expr varray', where varray is a variable length array of
expressions, this works as is, but I cannot make varray from a
functor that needs t = expr and default = Initial; even if
the recursion could work, there is no syntax for it]
        

-- 
John Skaller, mailto:skaller@maxtal.com.au
1/10 Toxteth Rd Glebe NSW 2037 Australia
homepage: http://www.maxtal.com.au/~skaller
downloads: http://www.triode.net.au/~skaller



This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:26 MET