[Caml-list] Exceptions as datatypes

[Caml-list] Exceptions as datatypes

[Patrick M Doane]

It seems possible to use exceptions as datatypes with some
(potentially useful) changes to the typing discipline. For example:

module M1 = struct
  type t = Int of int | Float of float
  let to_string = function
  | Int n -> string_of_int n
  | Float f -> string_of_float f
end

module M2 = struct
  exception Int of int
  exception Float of float
  let to_string = function
  | Int n -> string_of_int n
  | Float f -> string_of_float f
  | _ -> "<unknown>"
end

let test () =
  print_endline (M1.to_string (M1.Int 5));
  print_endline (M2.to_string (M2.Int 5));

Since the 'exn' type is not polymoprhic, there are no concerns about a
top-level structure failing to generalize a type variable.  It's also
extensible:  For example, a syntax tree could include annotations without
changing its type:

type t =
  | Int of int
  | Binary of op * t * t
  | Annotation of exn
  | ...

For most applications, the traditional or polymorphic variants work fine -
but I can think of several examples where these exception datatypes could
be extremely useful.

Looking at the assembly output, it appears that the the matching is linear
with two memory reads per comparison.  I think that the code generation
for exception matching can be improved though.  Is the following
strategy sound?

Each module reserves a chunk of memory in its data section of the same
size as the number of exceptions declared.  Whenever an exception is
created, it would include a pointer into that chunk (with an offset based
on its ordering in the file).  Pattern matching on exception values
subtracts that pointer from the head of the chunk and then use a
logarithmic search or jump table depending on the number of cases.  If the
pattern matching was performed on exception values from more than one
module, then the subtraction (and subsequent comparisons) is done for each
module.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Exceptions as datatypes

[Jacques Garrigue]

From: Patrick M Doane <patrick@watson.org>

> It seems possible to use exceptions as datatypes with some
> (potentially useful) changes to the typing discipline. For example:
> 
> type t =
>   | Int of int
>   | Binary of op * t * t
>   | Annotation of exn
>   | ...
> 
> For most applications, the traditional or polymorphic variants work fine -
> but I can think of several examples where these exception datatypes could
> be extremely useful.

I've heard of some discussion in the SML world about having
exception-like types, that is not having only exn, but being able to
create new ones. This would avoid the evident pitfall in your example:
Not_found or Exit would be valid annotations, which you probably do
not intend.

However, remember that any "_ ->" match case in your program is a
potential bug when you start adding cases to your type, so handle with
care.

> Looking at the assembly output, it appears that the the matching is linear
> with two memory reads per comparison.  I think that the code generation
> for exception matching can be improved though.  Is the following
> strategy sound?
> 
> Each module reserves a chunk of memory in its data section of the same
> size as the number of exceptions declared.  Whenever an exception is
> created, it would include a pointer into that chunk (with an offset based
> on its ordering in the file).  Pattern matching on exception values
> subtracts that pointer from the head of the chunk and then use a
> logarithmic search or jump table depending on the number of cases.  If the
> pattern matching was performed on exception values from more than one
> module, then the subtraction (and subsequent comparisons) is done for each
> module.

In order to avoid the linear search, you would need to know the
ordering of constructors at compile time (when you generate code for
pattern matching). This works nicely with polymorphic variants because
tags have a global meaning, and we can decide in advance which integer
we are going to assign to each tag, and be sure there will be no
conflict (that's why we cannot safely add extensible polymorphic
variants). However, exception constructors are named inside a module,
so your numbering has to be local to your module.

I'm afraid your approach does not work, because you don't want to
increase the cost of exception creation. Or did I read you wrong, and
you were really talking about exception declaration?
What can be done is to associate a global hashtable to each
exception declaration, and have every module that uses this exception
add its local index in the table. Then each time you do pattern
matching against an exception, you would have to get the local index in
the table, based on a dynamically assigned module number.
Alternatively the table could be local to the module, and contain all
exceptions used in the module, and you would search it according to a
dynamically assigned global exception number.
In both cases, that means that you have to do a search, and then a
pattern matching, and it's going to be efficient only for rather big
matches.

Note that I use the hashtable approach in the LablGL binding, on the C
side, but I don't really care about performance there.

Jacques Garrigue
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Exceptions as datatypes

[Patrick M Doane]

On Wed, 22 May 2002, Jacques Garrigue wrote:

> From: Patrick M Doane <patrick@watson.org>
>
> > For most applications, the traditional or polymorphic variants work fine -
> > but I can think of several examples where these exception datatypes could
> > be extremely useful.
>
> I've heard of some discussion in the SML world about having
> exception-like types, that is not having only exn, but being able to
> create new ones. This would avoid the evident pitfall in your example:
> Not_found or Exit would be valid annotations, which you probably do
> not intend.

Yes, that would make it more useful.  Without that, the "_ ->" match
should probably raise the exception so that higher levels have a chance to
catch the error conditions.

> > Looking at the assembly output, it appears that the the matching is linear
> > with two memory reads per comparison.  I think that the code generation
> > for exception matching can be improved though.  Is the following
> > strategy sound?
> >
> > Each module reserves a chunk of memory in its data section of the same
> > size as the number of exceptions declared.  Whenever an exception is
> > created, it would include a pointer into that chunk (with an offset based
> > on its ordering in the file).  Pattern matching on exception values
> > subtracts that pointer from the head of the chunk and then use a
> > logarithmic search or jump table depending on the number of cases.  If the
> > pattern matching was performed on exception values from more than one
> > module, then the subtraction (and subsequent comparisons) is done for each
> > module.
>
> In order to avoid the linear search, you would need to know the
> ordering of constructors at compile time (when you generate code for
> pattern matching). This works nicely with polymorphic variants because
> tags have a global meaning, and we can decide in advance which integer
> we are going to assign to each tag, and be sure there will be no
> conflict (that's why we cannot safely add extensible polymorphic
> variants). However, exception constructors are named inside a module,
> so your numbering has to be local to your module.

Right - but there is still an ordering, and this information could be
exported in the .mli file correct?

> I'm afraid your approach does not work, because you don't want to
> increase the cost of exception creation. Or did I read you wrong, and
> you were really talking about exception declaration?

I don't know Ocaml's representation of exceptions, but my thought was that
one of the exception's fields could be a value used to determine which
exception it was for a particular module.

I'll make a more concrete example:

module A has 3 exceptions, so it allocates a 3 byte chunk in its
data segment.  We'll assume the pointer to this chunk is 100.  Module B
has 2 exceptions with its chunk at 200.  As mentioned, the
ordering of the exceptions needs to be known in the .mli file.

Then, any exception in A will have a data-field containing values from
100-102 that can be used for pattern matching.  If the matching occurs on
a set of exceptions that are all from the same module, it seems that the
search time can be improved.

Perhaps this requires an additional field to exceptions, increasing the
overall cost of construction and memory use.


> Note that I use the hashtable approach in the LablGL binding, on the C
> side, but I don't really care about performance there.

Using a hashtable can still be an improvement in the current situation,
and probably the best compromise.

Patrick

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners