[Caml-list] queasiness about Exit

[Caml-list] queasiness about Exit

[William Harold Newman]

When I'm searching for something in an array, the idiom seems to be
to raise Exit when I find it. E.g.
  let is_critical critical_outputs results =
    try
      for i = 0 to Array.length results - 1 do
        let r = results.(i).loc in
        for j = 0 to Array.length critical_outputs - 1 do
          if critical_outputs.(j).loc = r then raise Exit
        done
      done;
      false
    with Exit ->
      true

What if I'm searching for something in a complex data structure, using
a mapping function where, in STL or in a more object-oriented system,
I'd use an iterator? I could do something like
  let exists_in_complex_datastructure predicate complex_data_structure
    try 
      map_for_effect_on_complex_data_structure
        (fun element -> if predicate element then raise Exit)
        complex_data_structure;
      false
    with Exit -> true
But I'm having trouble convincing myself that this won't get me into
trouble with obscure bugs later as things get complicated and
"predicate" or "map_for_effect_on_complex_data_structure" might themselves
be implemented in terms of "try .. raise Exit .. with Exit -> .."
constructs.

I've mostly programmed in Common Lisp for the last few years, and I'm
accustomed to nonlocal exits with lexical scoping, so I've never had
to think about this. Is there some nice nesting reason why this turns
out not to be a problem? Or do careful OCaml programmers declare a new
exception type for every nonlocal exit when opaque mappings or
predicates are involved? Or am I missing the point somehow and asking
the wrong question?

(Of course, if I'm just searching for something in a complex data
structure, probably the right way is to implement
exists_in_complex_data_structure or a better search function as part
of the interface to the data structure, instead of trying to improvise
one as part of the map-over-all-elements function. In fact, I'm really
not so much concerned with pure searching as with other operations
which have a possibility of terminating early.)

(And by the way, thanks for the answers about narrowing objects!)

-- 
William Harold Newman <william.newman@airmail.net>
PGP key fingerprint 85 CE 1C BA 79 8D 51 8C  B9 25 FB EE E0 C3 E5 7C
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] queasiness about Exit

[Andreas Rossberg]

William Harold Newman wrote:
> 
> What if I'm searching for something in a complex data structure, using
> a mapping function where, in STL or in a more object-oriented system,
> I'd use an iterator? I could do something like
>   let exists_in_complex_datastructure predicate complex_data_structure
>     try
>       map_for_effect_on_complex_data_structure
>         (fun element -> if predicate element then raise Exit)
>         complex_data_structure;
>       false
>     with Exit -> true

As an aside: As you only want to "map for effect" you better use
iteration, i.e. an "iter" function.

Also note that searching actually is neither mapping nor iteration, but
a fold operation. For example, you could define exists for arrays as
follows:

	let exists p = Array.fold_left (fun b x -> b || p x) true

But it always walks the whole array.

> But I'm having trouble convincing myself that this won't get me into
> trouble with obscure bugs later as things get complicated and
> "predicate" or "map_for_effect_on_complex_data_structure" might themselves
> be implemented in terms of "try .. raise Exit .. with Exit -> .."
> constructs.

Yes, I don't like that idiom either - although I use it myself
sometimes.

> (Of course, if I'm just searching for something in a complex data
> structure, probably the right way is to implement
> exists_in_complex_data_structure or a better search function as part
> of the interface to the data structure, instead of trying to improvise
> one as part of the map-over-all-elements function. In fact, I'm really
> not so much concerned with pure searching as with other operations
> which have a possibility of terminating early.)

For real mapping (as opposed to iteration) terminating early makes
little sense. For iteration and folds it does. It is not too difficult
to provide variations of iter and folds for your data structures that
allow early breaks. For example, consider:

	iter' : ('a -> bool) -> 'a array -> unit

Unlike the standard version of iter, the argument function returns a
boolean saying whether iteration should continue. Similarly for folds:

	fold_left' : ('a -> 'b -> 'a * bool) -> 'a -> 'b array -> 'a

With this version, you could do linear search efficiently:

	let exists p = fold_left' (fun b x -> let b' = b || p x in (b', not
b')) true

The somewhat redundant pair is a bit annoying in this particular case,
but should not really matter.

BTW, this is one of the few problems where lazy evaluation can play out
its strengths: in a lazy language you do not need variations of
iteration with early termination - you will always "terminate early"
automatically.

Hope this helps,

	- Andreas

-- 
Andreas Rossberg, rossberg@ps.uni-sb.de

"Computer games don't affect kids; I mean if Pac Man affected us
 as kids, we would all be running around in darkened rooms, munching
 magic pills, and listening to repetitive electronic music."
 - Kristian Wilson, Nintendo Inc.
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] queasiness about Exit

[John Prevost]

How about something like:

  let exists_in_complex_datastructure =
    let module M =
      struct
        exception Exit
        let eicd predicate complex_data_structure =
          try 
            map_for_effect_on_complex_data_structure
              (fun element -> if predicate element then raise Exit)
              complex_data_structure;
            false
          with Exit -> true
       end
     in M.eicd

That is, in the scope of your module (or within the function), create
a new exception for your use.  Since it's local to your function,
nobody else will be raising it.

John.
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] queasiness about Exit

[Marcin 'Qrczak' Kowalczyk]

Thu, 15 Nov 2001 17:58:32 +0100, Andreas Rossberg <rossberg@ps.uni-sb.de> pisze:

> It is not too difficult to provide variations of iter and folds for
> your data structures that allow early breaks. For example, consider:
> 
> 	iter' : ('a -> bool) -> 'a array -> unit
> 
> Unlike the standard version of iter, the argument function returns a
> boolean saying whether iteration should continue. Similarly for folds:
> 
> 	fold_left' : ('a -> 'b -> 'a * bool) -> 'a -> 'b array -> 'a

An alternative is

fold_right' : ('a -> (unit -> 'b) -> 'b) -> 'a array -> (unit -> 'b) -> 'b

which can also replace iter (with 'b = unit).

When fold in either direction could be used, fold_left is usually
beter if the folding function is strict, and fold_right if it's lazy.

> let exists p = fold_left' (fun b x -> let b' = b || p x in (b', not b')) true

let exists p xs = fold_right' (fun x bf -> p x || bf ()) xs (fun () -> false)

Wrapping "init" (shouldn't it be called "last" here?) in a closure is
unnecessary for this case but it's important e.g. for concatenation
of lazy lists.

-- 
 __("<  Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/
 \__/
  ^^
QRCZAK

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] queasiness about Exit

[Francois Pottier]

Hi,

> But I'm having trouble convincing myself that this won't get me into
> trouble with obscure bugs later as things get complicated and
> "predicate" or "map_for_effect_on_complex_data_structure" might themselves
> be implemented in terms of "try .. raise Exit .. with Exit -> .."
> constructs.

Indeed, if you use the same exception `Exit' throughout all of your code,
then you might get into this kind of trouble.

I'd suggest using a different exception every time you need one, to avoid the
risk of accidental capture. A module can declare an arbitrary number of
exceptions for internal use; you can even generate new exceptions dynamically
(using local modules, introduced by `let module') if needed (although that's
pretty rare).

-- 
François Pottier
Francois.Pottier@inria.fr
http://pauillac.inria.fr/~fpottier/
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] queasiness about Exit

[Lauri Alanko]

This seems like something where first-class continuations would be
useful. Are there any plans on adding them to O'Caml? SML/NJ at least
seems to have them.

If full continuations are too expensive, even upwards-only continuations
would be a handy alternative to exceptions.


Lauri Alanko
la@iki.fi
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] queasiness about Exit

[Daniel de Rauglaudre]

Hi,

On Fri, Nov 16, 2001 at 02:05:15PM +0200, Lauri Alanko wrote:

> This seems like something where first-class continuations would be
> useful. Are there any plans on adding them to O'Caml? SML/NJ at least
> seems to have them.

This is feasible, I implemented them in Caml Light some years ago. But
in the implementaion of SML/NJ, continuations are "light" and natural
because their execution "stack" is implemented not by a stack but by a
list. To get the continuation, you has just to get the "stack pointer".
In OCaml, you should make a copy of the execution stack.

> If full continuations are too expensive, even upwards-only continuations
> would be a handy alternative to exceptions.

Why not using exceptions, then? Do you mean that you want to be able to
restart the same continuation several times?

-- 
Daniel de RAUGLAUDRE
daniel.de_rauglaudre@inria.fr
http://cristal.inria.fr/~ddr/
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] queasiness about Exit

[Krishnaswami, Neel]

Andreas Rossberg [mailto:rossberg@ps.uni-sb.de] wrote:
> 
> For real mapping (as opposed to iteration) terminating early makes
> little sense. For iteration and folds it does. It is not too difficult
> to provide variations of iter and folds for your data structures that
> allow early breaks. For example, consider:
>
> BTW, this is one of the few problems where lazy evaluation 
> can play out its strengths: in a lazy language you do not need
> variations of iteration with early termination - you will always
> "terminate early" automatically.

I posted a similar question to comp.lang.functional a few months
ago, and Dan Wang showed me how I could use monads to make a
regular fold do that. 

I actually wanted to thread a state through a fold, but IIRC the 
technique will generalize to any monad (such as the exception
or continuation monad). Google reveals that the thread is at:

http://groups.google.com/groups?threadm=slrn9ig78d.gpl.neelk%40brick.cswv.co
m

--
Neel Krishnaswami
neelk@cswcasa.com
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr