A simpler approach to exceptions as means of avoiding computation?

Ecosystem
1

Exceptions can be useful to make programs more efficient. In this particular example, a recursive multiplication function is made efficient by preventing it from returning “endlessly” once the answer is known:

Inefficient ( think of a 1 million element list with a 0 at the end )

let rec multl = function
  | [] -> 1
  | a::rest -> if a = 0 then 0 else a * (multl rest)
;;

Efficient ( use exceptions to return as soon as we see a zero )

exception Zero;;

let multlexc l = 
  let rec aux = function 
    | [] -> 1
    | a::rest -> if a = 0 then raise Zero else a * (aux rest)
  in
  try aux l with Zero -> 0;;

Could it be possible to have a special keyword for this common situation in order to get rid of exceptions?

let rec multl = function
      | [] -> 1
      | a::rest -> if a = 0 then (grandparent 0) else a * (multl rest)
    ;;

If the compiler isn’t smart enough to detect this situations, then I think a special keyword could be useful to prevent extra code.

2

Actually, in this particular case, I’d say you can get very much the same effect (or even better, since there is no exception handler to setup) if you use a tail-recursive function with some accumulator:

let mult l =
  let rec aux acc = function
    | [] -> acc
    | 0 :: _ -> 0
    | x :: r -> aux (x * acc) r
  in
  aux 1 l

Of course in practice, it is not always possible to use that strategy; and local (or at least very localised) exceptions are often used in such cases. However, I don’t think there is any need to change anything to better support these cases: the current way with exceptions is clear enough in my opinion. In the simplest cases, using tail-rec functions with accumulators is better, and in complex cases, exception handlers give much clearer information and mastery over the control flow (compared to your example with “grandparent”, where it’s not actually clear what happens, at least to me).

Lastly, the optimization you propose would not change much the way the pattern is compiled: if I understand correctly, the "grandparent’ call would jump in the callstack using the same ideas as exceptions. In that case, it would be more some possibly confusing syntactic sugar than an optimization.

1 Like
3

I guess you would like PR 638 too.

4

Syntactic sugar seems derogatory term, as if it wasn’t a valid abstraction. All programming constructs are abstractions because they hide details of implementation.

I know some abstractions are more useful than others. However, in this case, the keyword is preventing:

  • defining an exception type
  • defining a functional expression
  • defining an let ... in expresion
  • raising an exception
  • defining an exception handler

Also, I think exceptions seem to be more suited to describe an unexpected problems in computation rather than as control structures.

Either way, both ways of doing it stem from the fact that the compiler cannot recognize this optimization and make the program jump to the beginning.

5

I don’t see the problem, your first implementation stops as soon as we see a zero:

let rec multl = function
  | [] -> 1
  | 0 :: _ -> print_endline "end of loop."; 0
  | x :: xs -> Printf.printf "recursive call with %i.\n" x; x * multl xs

multl [0; 1; 2; 3];;
end of loop.
- : int = 0

multl [4; 5; 6; 0; 1; 2; 3];;
recursive call with 4.
recursive call with 5.
recursive call with 6.
end of loop.
- : int = 0

The only problem I see is that your recursive call is not a tail call, but that’s all.

1 Like