🚀 go-pugleaf

In article <86438@lll-winken.LLNL.GOV> you write that you want to
know how to accomplish the following in a functional language:

>Example: (plus (div a 0) (plus b c))	;;; [ (a/0) + (b+c) ]
>	 
>	 The value of (div a 0) is ERROR.
>	 Therefore the value of (plus (div a 0) (plus b c))
>	 is also ERROR.
>

   This is pretty straightforward in Miranda.

result ::= Val num | ERROR

   In otherwords, result is a variant type (union type, etc.; a rose
by any name...)  You can get pretty specific with your errors, and
can handle them in a fairly free manner, as in :

divide (Val x) (Val 0) = ERROR
divide (Val x) (Val y) = Val (x/y)
divide x y = ERROR

   which means, the result of dividing by zero or dividing two items
which aren't both values is ERROR.
       

--- Emery Berger (emery@cs.utexas.edu)
--- Applied Research Laboratories
--- University of Texas at Austin

In article <86438@lll-winken.LLNL.GOV> miller@lll-crg.llnl.gov (Patrick Miller) writes:

>   I'm looking for pointers to papers about implementing error values in
>   functional languages (or other styles).  By error values, I mean that
>   the value of a calculation is replaced by a placeholder denoting the
>   error.  This allows some form of error handling without invoking the
>   concept of global state.

From what I remember, John Backus' FP has just such an idea. It has a
value called bottom which is returned when there has been an error.

>   Example: (plus (div a 0) (plus b c))	;;; [ (a/0) + (b+c) ]

In FP would be:
	{func +@[/@[1 %0] +@[2 3]]}
where the args to func are equivalent a, b and c.

>	    The value of (div a 0) is ERROR.
>	    Therefore the value of (plus (div a 0) (plus b c))
>	    is also ERROR.

Calling:
	func:<1 2 3>

gives back:
	?
Which is bottom --- cute!

I think it says that any function whose arguments contain a ? will
return a ?.

>   What I'm especially looking for is info on implementations of these
>   values.

I pulled an implementation of FP by Andy Valencia from the Sources
Archive here at Imperial. You may find useful stuff there.

>   Pat Miller				     Professional Student
Frank Taylor, another Professional Student

Major Disclaimer: The author disclaims all responsibility for any loss
or damage incurred by use of the software or knowledge given above. In
other words I don't know that much about FP :-)

In article <88@syrian.cs.utexas.edu> emery@cs.utexas.edu (Emery Berger) writes:
>In article <86438@lll-winken.LLNL.GOV> you write that you want to
>know how to accomplish the following in a functional language:
>
>>Example: (plus (div a 0) (plus b c))	;;; [ (a/0) + (b+c) ]
>>	 
>>	 The value of (div a 0) is ERROR.
>>	 Therefore the value of (plus (div a 0) (plus b c))
>>	 is also ERROR.
>>
>
>   This is pretty straightforward in Miranda.
>
>result ::= Val num | ERROR
>
[stuff deleted]

However, this solution won't allow you to propagate errors through 
arbitrary function calls (because of the type system). In standard 
ML there is an exception mechanism that allows errors to be raised
and handled, and lets them carry values if you wish.

> 1 div 0; (* exceptions can be raised *)
Exception- Div raised
Exception failure raised
>  (1 div 0) + (3 div 4) ;  (* exceptions propagate *)
Exception- Div raised
Exception failure raised
> ((1 div 0) handle Div => 1000) + (3 div 4) ;(* exceptions can be handled *)
val it = 1000 : int   
> ( (1 div 0) + (3 div 4) ) handle Div => 42 ;(* exceptions can be handled later *)
val it = 42 : int   
> real ;
val it = fn : int -> real   
> real ( 1 div 0 ); (* exceptions propagate even when types change *)
Exception- Div raised
Exception failure raised


--
Prof. Michael P. Fourman                      email        mikef@lfcs.ed.ac.uk
Dept. of Computer Science                     'PHONE (+44) (0)31-650 5198 (sec)
JCMB, King's Buildings                               (+44) (0)31-650 5197
Mayfield Road, Edinburgh EH9 3JZ, Scotland, UK FAX   (+44) (0)31 667 7209

In article <2437@skye.cs.ed.ac.uk>, mikef@cs.ed.ac.uk (Mike Fourman) writes:
> >   This is pretty straightforward in Miranda.
> >
> >result ::= Val num | ERROR
> >
> [stuff deleted]
> 
> However, this solution won't allow you to propagate errors through 
> arbitrary function calls (because of the type system). In standard 
> ML there is an exception mechanism that allows errors to be raised
> and handled, and lets them carry values if you wish.

Way back when I implemented a functional language for my Ph.D., I had
a polymorphic type system (ML-like, essentially), but I had error values
as well. These carried the same types as ordinary values, but were
distinguished from them for the purposes of the primitive operations
(arithmetic and so on) and decomposition for pattern matching. Thus
(assuming modern ML syntax):

	- val x = 1/0;
	  x = <error: DIV> : int

	- val y = x + 1;
	  y = <error: ADD, DIV> : int

	- val z =
	    let val x :: y = nil in x end;
	  z = <error: MATCH> : 'a

	- fun isError <error: _> = true
	    | isError _ = false;
	  isError = fn : 'a -> bool

	- (isError z, isError 3);
	  (true, false) : bool * bool

The only problem I could see with the scheme (and didn't have time to
investigate) was that normally complete pattern matches (such as nil vs.
hd :: tl) were no longer so, and it wasn't clear that termination of
sensible functions could be guaranteed (a length-of-list function called
with an error value would probably loop indefinitely, for example...)

-- 
Nick Rothwell,	Laboratory for Foundations of Computer Science, Edinburgh.
		nick@lfcs.ed.ac.uk    <Atlantic Ocean>!mcsun!ukc!lfcs!nick
~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~
 "You ain't seen nothing yet. I can take this floor out too, no trouble."

In article <86438@lll-winken.LLNL.GOV>, miller@lll-crg.llnl.gov (Patrick
Miller) writes:
>I'm looking for pointers to papers about implementing error values in
>functional languages (or other styles).  By error values, I mean that
>the value of a calculation is replaced by a placeholder denoting the
>error.  This allows some form of error handling without invoking the
>concept of global state.

As other posters have pointed out this is a fairly simple thing to do. More
complicated is to handle the propagation of exceptions in a lazy functional
language.

A while ago I was one of the authors of a couple of papers on exception 
handling in lazy functional languages [2, 3]. Our major interest was to handle
(the propagation of) exceptions in a way that preserved lazy semantics and 
commutativity of operators.

i.e. we wanted 

	hd (x : exception) <=> hd (x : ~exception)

and

	exception1 + exception2 <=> exception2 + exception1

exception, exception1 and exception2 are arbitrarily complex expressions whose 
evaluation causes the raising of exceptions. exception1 and exception2 raise
two different exceptions.

We based the work on the failure sets model of [4] which was first (as far as
I know) applied to functional languages in [1].

Although we mangaged to achieve the aim of preserving lazy semantics and
commutativity we had to restrict the power of the exception signalling,
propagation and handling mechanism so much that what we ended up with could be 
expressed relatively straight forwardly in a lazy functional language such as 
Miranda. In fact, as far as I remember, we actually wrote the Miranda functions
required.

I have doubts that an alternative approach would do any better, though
obviously I can't prove it. My belief is that it is more or less impossible to 
produce an exception mechanism that significantly enhances the
expressive power of a language without losing "normal" lazy evaluation 
semantics.

Dave

[1] "An exception handling construct for functional languages"
    M. Bretz & J. Ebert
    Proceedings ESOP88, 2nd Europeand Symposium on Programming,
    Spriger-Verlag LNCS 300

[2] "Gerald : An exceptional lazy functional programming language"
    A.C. Reeves, D.A. Harrison, A.F. Sinclair, P. Williamson
    Functional Programming: Proceedings of the 1989 Glasgow Workshop,
    21-23 August 1989, Fraserburgh Scotland.
    Eds: K. Davis and J. Hughes.
    Springer Workshops in Computing 1990

[3] "How to make a lazy functional language exceptional"
    A.C. Reeves, D.A. Harrison, A.F. Sinclair, P. Williamson
    Proceedings TENCON '89 (IEEE Region 10 conference) on Functional
    Programming Languages : Theory & Applications
    Bombay November 1989

[4] "An axiomatic treatment of exception handling in an expression-oriented
    langauge"
    S. Yemini & D.M. Berry
    ACM TOPLAS Vol 9, NO 3 1987

---------------------------------

Dave Harrison				JANET: D.A.Harrison@uk.ac.newcastle
Computing Laboratory			PHONE: +44 91 222 7784
University of Newcastle upon Tyne
Newcastle upon Tyne NE1 7RU
U.K.

	"A proton is the same as a neutron, only coloured in differently."

In article <1990Nov24.121432.29282@newcastle.ac.uk> D.A.Harrison@newcastle.ac.uk (Dave Harrison) writes:
>    ...more complicated is to handle the propagation of exceptions
>	in a lazy functional language.
>	I was one of the authors of a couple of papers on exception 
>	handling in lazy functional languages. 
>	Our major interest was to handle (the propagation of) exceptions
>	in a way that preserved lazy semantics and commutativity of operators.
>    ...
>	Although we mangaged to achieve the aim of preserving
>	lazy semantics and commutativity, we had to restrict
>	the power of the exception signalling, propagation
>	and handling mechanism so much that what we ended up with
>	could be expressed relatively straight forwardly
>	in a lazy functional language such as Miranda.
>
>	I have doubts that an alternative approach would do any better,
>	though obviously I can't prove it. My belief is that it is
>	more or less impossible to produce an exception mechanism
>	that significantly enhances the expressive power of a language
>	without losing "normal" lazy evaluation semantics.

I agree.  If exception-handling is powerful, then there
is no longer anything "exceptional" about exceptions
-- they merely become new data objects to be added to the domain
(objects whose presence tends to sequentialize operators
which would otherwise be commutative).

If you don't care about handling exceptions,
but want only to report them to the user,
then one might move these messages to the meta-level
--- viewing them as the comments of a default runtime-debugger.
The base language itself can then ignore the distinctions
in the kinds and causes of errors, and treat "error"
analogously to the way it treats "bottom" (i.e. undefined).
In fact, if one omits exception-handling completely,
it becomes reasonable to map exceptions to "undefined" (bottom)
in the semantics, and leave more detailed explanations
to the language environment.

	Frank Silbermann	fs@cs.tulane.edu
	Tulane University	New Orleans, Louisianna  USA

In article <1990Nov24.121432.29282@newcastle.ac.uk>
D.A.Harrison@newcastle.ac.uk (Dave Harrison) writes:
>Although we mangaged to achieve the aim of preserving lazy semantics and
>commutativity we had to restrict the power of the exception signalling,
>propagation and handling mechanism so much that what we ended up with could
>be expressed relatively straight forwardly in a lazy functional language such
>as Miranda. In fact, as far as I remember, we actually wrote the Miranda
>functions required.

>I have doubts that an alternative approach would do any better, though
>obviously I can't prove it. My belief is that it is more or less impossible
>to produce an exception mechanism that significantly enhances the expressive
>power of a language without losing "normal" lazy evaluation semantics.

Yikes, i have to disagree with that last statement.  I'd be interested in
seeing a quick description of the major problems between exception handling
and lazy evaluation.

There is a question of whether functions should be `strict in exceptions'.
Clearly if a function is strict in the value of some argument, it should also
be strict in an exception in that argument.  Otherwise, it could go either
way.  I'm convinced that you want both possibilities at different times, and
therefore a good functional language should support both.

In article <4043@osc.COM>, jgk@osc.COM (Joe Keane) writes:
>In article <1990Nov24.121432.29282@newcastle.ac.uk>
>D.A.Harrison@newcastle.ac.uk (Dave Harrison) writes:

DH: I have doubts that an alternative approach would do any better, though
DH: obviously I can't prove it. My belief is that it is more or less impossible
DH: to produce an exception mechanism that significantly enhances the
expressive
DH: power of a language without losing "normal" lazy evaluation semantics.

JK: Yikes, i have to disagree with that last statement.  I'd be interested in
JK: seeing a quick description of the major problems between exception handling
JK: and lazy evaluation.

JK: There is a question of whether functions should be `strict in exceptions'.
JK: Clearly if a function is strict in the value of some argument,it
should also
JK: be strict in an exception in that argument.  Otherwise, it could go either
JK: way.  I'm convinced that you want both possibilities at different
times, and
JK: therefore a good functional language should support both.

DH :

Consider the following (psuedo-Miranda) function :

	inclist :: [ num ] -> [ num ]

	inclist []
	  = []

	inclist (x : xs)
	  = x + 1 : inclist xs,			if x >= 0
	  = (signal Bad_num x) : inclist xs,	otherwise

This works on lazy lists; only the head of the argument list needs be forced to
increment the next element.

Consider the expression :

	hd (inclist [100,99,-1])

The result of this expression is

	101

If the inclist function is strict in exceptions then it must evaluate the whole
of its argument to determine that its last element will indeed cause an
exception to be raised. 

	=> inclist is strict in its argument

The raising of an exception is a possible consequence of the evaluation of an
expression. Thus, if the evaluation of an argument may raise an exception then
a function which is strict in exception must evaluate that argument to
catch any exceptions

	=> A function which is strict in exceptions will be strict in any
	   arguments which may raise exceptions.

The reverse is also true : If a function is lazy in some of its arguments then
it will be lazy on any exceptions that those arguments raise.

As usual the strict case is easy to handle : just evaluate everything. To
handle the lazy case you have to ensure that exceptions do not propagate "out
of" lazy operations.

For example in the inclist function the exception (signal Bad_num x) must be
handled and a recovery value substituted for the signal at that point; then the
(lazy) cons can take place. If there is no exception handler for the Bad_num
exception at that point then tough : the program crashes. To allow the
exception to propagate "out of" the cons would make cons a strict operator.

Unsatisfactory, but at least it preserves lazy semantics. I can't think of a
better solution but if anyone else can I'd love to see it (how about a joint
paper, I could use the publications :-)).

Dave

---------------------------------

Dave Harrison				JANET: D.A.Harrison@uk.ac.newcastle
Computing Laboratory			PHONE: +44 91 222 7784
University of Newcastle upon Tyne
Newcastle upon Tyne NE1 7RU
U.K.

"Some of your men have taken seeds of truth, 
 And planted fields of hate" 			- RunRig "Eirinn"
"Failte gu Tir an Airm"				- RunRig "Tir an Airm"

>>I have doubts that an alternative approach would do any better, though
>>obviously I can't prove it. My belief is that it is more or less impossible
>>to produce an exception mechanism that significantly enhances the expressive
>>power of a language without losing "normal" lazy evaluation semantics.

>Yikes, i have to disagree with that last statement.  I'd be interested in
>seeing a quick description of the major problems between exception handling
>and lazy evaluation.

Well, here goes. . .

Assume that exceptions are added to the domain just above bottom and that they
are indistinguishable from bottom except by a special function catch

	catch h e
	 = "if val is an exception" -> h "the info encoded in the exception"
	   val
	   WHERE
	       val = e

so that h is a handler and e is an expression.  Then if the evaluation of e
yields an exception, the value of catch is h applied the whatever info is
part of the exception, otherwise the value of catch is the value of e.

Now consider the following

    E1
    WHERE
	E1 = catch h ( (3/0) + (ln 0) )
	h "log of zero"    = 1
	h "divide by zero" = 0

The value of E1 seems to depend on the order of evaluation of the arguments
to the addition.  If the left operand is evaluated first, then the value of 
E1 is 0;  if the right operand is evaluated first then the value of E1 is 1.
This is bad.

In order to fix this we assume that even after generating an exception,
the evaluator presses on collecting exceptions until it has evaluated every
strict argument and that the order in which exceptions are raised is ignored.
Then we have the following:

    E2
    WHERE
	E2 = catch h ( (3/0) + (ln 0) )
	h "divide by zero, log of zero" = 2
	h "log of zero"    = 1
	h "divide by zero" = 0

Now the value of E2 does not depend on the order of evaluation of the operands
but the evaluator is required to press on with the evaluation of an expression
even after it has encountered and exception.  This seems wasteful.

   E3
   WHERE
       E3 = catch H ( (3/x) + (f x) )
       x = 0
       f 1 = 1
       f n = (f (n-1)) * n
       h "divide by zero, log of zero" = 2
       h "log of zero"    = 1
       h "divide by zero" = 0

The value of E3 is bottom.  Even though the evaluator has determined that
there is at least one error present, it must press on until it finds a really
bad error, that is bottom.  This does not seem like a good property for an
exception handling mechanism.

Summary:

Either the evaluator must continue to evaluate as long as possible, collecting
errors until it has evaluated all of the strict args of a function or it hits
bottom, or there will be order dependencies introduced.  Order dependencies 
complicate the semantics and/or reduce the utility of the language.

Clearly this is a superficial explaination of the problem, but it raises
the major issues as I understand them.

-- 
Douglas Surber                 Internet: lobster!lescsse!dnsurber@menudo.uh.edu
Lockheed (LESC)                UUCP:     lobster!lescsse!dnsurber
SSE SSFP                       NASAmail: dnsurber/jsc/nasa
Houston, Texas                 Phone:    713-283-5195

-- 
Douglas Surber                 Internet: lobster!lescsse!dnsurber@menudo.uh.edu
Lockheed (LESC)                UUCP:     lobster!lescsse!dnsurber
SSE SSFP                       NASAmail: dnsurber/jsc/nasa
Houston, Texas                 Phone:    713-283-5195

In article <1990Dec6.205610.1022@lescsse.uucp> dnsurber@lescsse.uucp (Douglas Surber) writes:
   . . .
  Assume that exceptions are added to the domain just above bottom and that they
  are indistinguishable from bottom except by a special function catch
   . . . [several examples and ideas]
     E3
     WHERE
         E3 = ... [expression with a divide by zero and an infinite recursion]
  
  The value of E3 is bottom.  Even though the evaluator has determined that
  there is at least one error present, it must press on until it finds a really
  bad error, that is bottom.  This does not seem like a good property for an
  exception handling mechanism.

I see nothing wrong with collecting all errors: it preserves determinism.
If exceptions are really exceptional there is little waste.  The value of
E3 above is indeed bottom (you should not expect your exception handling
mechanism to help you with the halting problem).

Pablo Straub