miller@lll-crg.llnl.gov (Patrick Miller) (11/21/90)
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. 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. What I'm especially looking for is info on implementations of these values. Thanks, Pat -- Pat Miller Professional Student miller@lll-crg.llnl.gov Amateur Politician "If I knew what I was doing, I wouldn't be running" Fight Apathy! Vote Early, Vote Often
emery@cs.utexas.edu (Emery Berger) (11/21/90)
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
fst@doc.ic.ac.uk (Frank Taylor) (11/23/90)
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 :-)
mikef@cs.ed.ac.uk (Mike Fourman) (11/24/90)
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
nick@cs.edinburgh.ac.uk (Nick Rothwell) (11/24/90)
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."
D.A.Harrison@newcastle.ac.uk (Dave Harrison) (11/24/90)
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."
E.Ireland@massey.ac.nz (Evan Ireland) (11/26/90)
> 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. I don't have pointers to papers (some have already been posted), but I have just started modifying a Lazy FAM (Functional Abstract Machine) implementation for use with a Haskell compiler, and I was planning to replace the ML-style exception handling operations with error values, because ML-style exception handling seems inappropriate for lazy languages. Haskell as it stands has no exception handling or error values, but I think I may find use for error values within the implementation, even if they are not directly manipulable by the language. This implementation uses header/tag fields in all heap objects, so error values simply require reserving another tag value. I intend to have polymorphic, parameterised, error values, so that I can have Error "divide by zero", Error "unexpected case" etc. The other idea I have been tinkering with is allowing pattern-matching factorial n | n < 0 = Error "factorial of negative number" -- I won't bother you with the other cases! f e@(Error _) = 0 f 0 = 1 f n = 2 isError (Error _) = True isError _ = False > 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...) My idea for solving this problem is to specify that any pattern-match that doesn't specify an error alternative has an error alternative implicitly introduced. Function definitions and conditionals would be length [] = 0 length (_:xs) = 1 + length xs length l = case l of [] -> 0 (_:xs) -> 1 + length xs length l = case l of e@(Error _) -> e -- propagate error [] -> 0 (_:xs) -> 1 + length xs If the length function had been written using a predicate and selector functions, we would expect a similar result (as long as the `null' predicate returns an error value when given an error value as argument). length l = if null l then 0 else 1 + length (tail l) length l = case null l of True -> 0 False -> 1 + length (tail l) length l = case null l of e@(Error _) -> e -- propagate error True -> 0 False -> 1 + length (tail l) Please forgive me if this is all old hat. I haven't chased up any of the references yet so I don't know how much of this has been covered before. Still I hope it is useful to someone (Patrick in particular)! Evan Ireland (E.Ireland@massey.ac.nz), School of Information Sciences, Massey University, Palmerston North, NZ.
fs@caesar.cs.tulane.edu (Frank Silbermann) (11/26/90)
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
jgk@osc.COM (Joe Keane) (11/29/90)
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.
D.A.Harrison@newcastle.ac.uk (Dave Harrison) (12/03/90)
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"
dnsurber@lescsse.uucp (Douglas Surber) (12/07/90)
>>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
straub@jogger.cs.umd.edu (Pablo A. Straub) (12/07/90)
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