From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id FAA31369; Wed, 22 May 2002 05:00:22 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id FAA31482 for ; Wed, 22 May 2002 05:00:21 +0200 (MET DST) Received: from kurims.kurims.kyoto-u.ac.jp (kurims.kurims.kyoto-u.ac.jp [130.54.16.1]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id g4M30EL02248 for ; Wed, 22 May 2002 05:00:15 +0200 (MET DST) Received: from localhost (suiren.kurims.kyoto-u.ac.jp [130.54.16.25]) by kurims.kurims.kyoto-u.ac.jp (8.9.3/3.7W) with ESMTP id LAA13109; Wed, 22 May 2002 11:59:57 +0900 (JST) To: patrick@watson.org Cc: caml-list@inria.fr Subject: Re: [Caml-list] Exceptions as datatypes In-Reply-To: <20020521081525.R80985-100000@fledge.watson.org> References: <20020521081525.R80985-100000@fledge.watson.org> X-Mailer: Mew version 1.94.2 on Emacs 20.7 / Mule 4.0 (HANANOEN) Mime-Version: 1.0 Content-Type: Text/Plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-Id: <20020522115957P.garrigue@kurims.kyoto-u.ac.jp> Date: Wed, 22 May 2002 11:59:57 +0900 From: Jacques Garrigue X-Dispatcher: imput version 20000228(IM140) Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk From: Patrick M Doane > 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