Error Checking and Monads
Principles of Programming Languages
Error Checking
Copyright By PowCoder代写 加微信 powcoder
Lecture covers:
Chapter 6 of “Anatomy of Programming
Languages”
http://www.cs.utexas.edu/~wcook/anatomy/ anatomy.htm
Interpreter so far
Our current JavaScript-like interpreter already
supports a number of features:
basic expressions (arithmetic & conditionals) variable declarations
function definitions & first-class functions recursion
Interpreter so far
This allows us to write some programs, such as:
var fact = function(n){
if (n == 0) 1; else n * fact(n-1)
var x = 10;
JavaScript Interpreter so far
However, what happens if we write?
var fact = function(n){
if (n == 0) 1; else n * fatn(n-1)
}; fact(10)
JavaScript Interpreter so far
However, what happens if we write?
var fact = function(n){
if (n == 0) 1; else n * fatn(n-1)
}; fact(10)
If we try in ghci:
*Main> execute fact2
*** Exception: Maybe.fromJust: Nothing
JavaScript Interpreter so far
*Main> execute fact2
*** Exception: Maybe.fromJust: Nothing
Not very helpful or informative as an error message!
Errors are an important aspect of computation.
They are typically a pervasive feature of a language, because they affect the way every expression is evaluated. For example, consider the expression:
If a or b raise errors then we need to deal with this
possibility.
Because errors are so pervasive they are a
notorious problem in programming and programming languages.
When coding in C the convention is to check the However this is often not done.
return codes of all system calls.
Java’s exception handling mechanism provides a more robust way to deal with errors.
During the course so far we have already
encountered some ways to deal with errors:
Our type-checkers have been developed with
Maybe to deal with type-errors
We have implemented variants of the JavaScript
interpreter with a simple Exception mechanism.
to deal with errors:
The Maybe datatype provides a useful mechanism
data Maybe a = Nothing | Just a
Error! Good result!
error message.
However, sometimes we would like to track some For example, perhaps we would like to report an
more information about what went wrong.
The Maybe datatype is limiting in this case,
because Nothing does not track any information.
How to improve the Maybe datatype to allows us to
track more information?
Error checking is a notorious problem in programming la h
everyone agrees that the return codes of all system calls s
that an error did not occur. However, most C programs
Representing Errors
leading to serious problems when things start to go wro
Errors are pervasive because any expression can either
We can create a datatype Checked, provides a
an error. One way to represent this possibility is by defi
constructor Error to be used instead of Nothing two possibilities: either a good value or an error.
data Checked a = Good a | Error String deriving Show
The declaration defines a generic Checked type that has
A good value!
Error with an error
type of the good value. The Checked type has two const Good constructor takes a value of type a and labels it as
Error Checking in Basic Expressio
case lookup x env of
Interpreter that deals with
To keep things simple and focused on errors, this secti with literals, variables, binary operators. This smalle
function to deal with errors.
that was introduced at the beginning of the book. M
Using Checked, we can reimplement the evaluate Although the syntax of expressions does not have to cha
function must be changed to return an Error value: evaluate :: Exp ! Env ! Checked Value
evaluate (Literal v) env = Good v What kind of errors can
Evaluation of a literal can never cause an error. The
we have in the current and returned. interpreter?
A variable can be undefined, so it evaluating a variabl
evaluate (Variable x) env =
Kinds of Errors
Three kinds of errors:
Division by zero
Undefined variable errors
var x = 3; x + y
Type-errors
Implementing Error Handling
function must be changed to return an Error value: evaluate :: Exp ! Env ! Checked Value
evaluate (Literal v) env = Good v Undefined Variables
Evaluation of a literal can never cause an error. The value is marked as a and returned.
Dealing with undefined variables:
A variable can be undefined, so it evaluating a variable may return an erro
evaluate (Variable x) env = case lookup x env of
Nothing ! Error (“Variable ” + x + ” undefined”) Just v ! Good v
Now we can
Error Checking in Multiple Sub-expressions
The case for binary operations is more interesting. Here is the original rule fo binary expressions:
evaluate (Binary op a b) env = binary op (evaluate a env) (evaluate
provide an error message!
b The problem is that either evaluate a env or evaluate b env could return
checked_binary GE (IntV a) Dealing with type errors:
(IntV b) = Good (BoolV (a > b))
checked_binary Div (IntV a) (IntV b) = Good (IntV (a ‘div‘ b))
checked_binary And (BoolV a) (BoolV b) = Good (BoolV (a ^ b
checked _binary Or (BoolV a ) (BoolV b ) = Good (BoolV (a _ b )
checked_binary LT (IntV a) (IntV b) = Good (BoolV (a < b)) Type Errors
checked_binary LE (IntV a) (IntV b) = Good (BoolV (a 6 b))
checked_binary GT (IntV a)
checked_binary EQ a b = Good (BoolV (a ⌘ b)) checked_binary = Error "Type error"
6.1.3 Examples of Errors
We could be more informative if we wanted!
Evaluating an expression may now return an error for unbound variable
execute (parseExp "x") The result of evaluation is:
(IntV b) = Good (BoolV (a > b))
All the other cases are the same as before, so checked_binary calls bi tags the resulting value as Good.
ERROR CHECKING
checked_binary Add (IntV a) (IntV b) = Good (IntV (a + b)) Division by zero:
checked_unary Neg (IntV i) = Good (IntV ( i)) Division by zero
checked_unary = Error “Type error”
checked _binary :: BinaryOp ! Value ! Value ! Checked Value
checked_binary checked_binary checked_binary checked_binary checked_binary checked _binary checked_binary checked_binary checked_binary checked_binary checked _binary checked _binary
Sub (IntV a) (IntV b) = Good (IntV (a b))
Mul (IntV a) (IntV b) = Good (IntV (a ⇤ b))
Div (IntV a) (IntV 0) = Error “Divide by zero” Div (IntV a) (IntV b) = Good (IntV (a ‘div‘ b)) And (BoolV a) (BoolV b) = Good (BoolV (a ^ b))
Or (BoolV a ) (BoolV LT (IntV a) (IntV b) LE (IntV a) (IntV b) GE (IntV a) (IntV b) GT (IntV a) (IntV b) EQab
b ) = = = = = =
= Good (BoolV (a _ b)) Good (BoolV (a < b)) Good (BoolV (a 6 b)) Good (BoolV (a > b)) Good (BoolV (a > b)) Good (BoolV (a ⌘ b)) Error “Type error”
All the other cases are the same as before, so checked_binary calls binary
tags the resulting value as Good.
CHAPTER 6. COMPUTATIONAL STRATEGIES
c is now 8 lines and uses additional temporary variables. When
Propagating errors:
evaluate (Unary op a) env = Propagating errors
case evaluate a env of Error msg ! Error msg
Good av ! checked_unary op av evaluate (Binary op a b) env =
case evaluate a env of Error msg ! Error msg Good av !
case evaluate b env of Error msg ! Error msg Good bv !
checked_binary op av bv
A bit longwinded though!
Now it should be clear why programmers do not always che because it is tedious and requires lots of code! What was orig
A Problem: Tracking Errors is Painful
Evaluating binary operators before errors:
deriving (Eq,Show)
type Env = [(String, Value)]
evaluate :: Exp ! Env ! Value Before errors
evaluate (Literal v) env = v evaluate (Unary op a) env =
unary op (evaluate a env) evaluate (Binary op a b) env =
binary op (evaluate a env) (evaluate b env)
evaluate (If a b c) env =
let BoolV test = evaluate a env in
if test then evaluate b env else evaluate c env
evaluate (Variable x) env = fromJust (lookup x env)
evaluate (Declare x exp body) env = evaluate body new where newEnv = (x , evaluate exp env ) : env
HAPTER 6. COMPUTATIONAL STRATEGIES
evaluate (Unary op a) env =
After errors
Error msg ! Error msg
Evaluating binary operators after errors:
case evaluate a env of
Good av ! checked_unary op av evaluate (Binary op a b) env =
case evaluate a env of Error msg ! Error msg Good av !
case evaluate b env of Error msg ! Error msg Good bv !
checked_binary op av bv
Can we make the code less messy?
w it should be clear why programmers do not always check a ause it is tedious and requires lots of code! What was original
HAPTER 6. COMPUTATIONAL STRATEGIES
evaluate (Unary op a) env =
Spotting the pattern
Error msg ! Error msg
Evaluating binary operators after errors:
case evaluate a env of
Good av ! checked_unary op av evaluate (Binary op a b) env =
case evaluate a env of Error msg ! Error msg Good av !
case evaluate b env of Error msg ! Error msg Good bv !
checked_binary op av bv
There seems to be a repeating pattern here.
w it should be clear why programmers do not always check a ause it is tedious and requires lots of code! What was original
and updating memory) and then evaluating the second ex l
updating memory as appropriate). They both have a simi with the evaluation of a and b. Factoring out the commo
mem let (v , m next-part
Spotting the pattern
part, the core of the pattern is:
We seem to have something like this:
case first-part of
Error msg ! Error msg Good v ! next-part v
This first-part corresponds to evaluate a env or evaluat versions. The second-part represents the remainder of everything that appears after the main pattern, but wit explicit. For the Checked case, the only variable need
How to capture this pattern as reusable code?
These patterns can be made explicit as a special operator t t
where the second part is a function with the appropria concrete, these parts are converted into explicit variables
Use a higher-order function!
Spotting the pattern
and the second-part, which is a function, is named F :
A BS F = mem let (
A BC F = case A of
Error msg ! Error msg Good v ! F v
These generic operators for Checked BC and Stateful BS the core pattern composing two Checked or Stateful co operators are called bind operators, because they bind
Revising the Implementation
Creating auxiliary definitions
The higher-order function capturing error propagation:
(>>=) :: Checked a -> (a -> Checked b) -> Checked b
Error msg -> Error msg
Good v -> f v
A function that creates checked values:
return :: a -> Checked a
return v = Good v
We will call this function bind (since it binds a value v)
Rewriting Evaluation
Here is the new version (4 cases) of evaluation:
evaluateM (Literal v) env = return v
evaluateM (Variable x) env =
case lookup x env of
Nothing -> Error (“Variable ” ++ x ++ ”
undefined”)
Just v -> return v
evaluateM (Unary op a) env =
evaluateM a env >>= checked_unary op
evaluateM (Binary op a b) env =
evaluateM a env >>=
\v1 -> evaluateM b env >>=
\v2 -> checked_binary op v1 v2
Propagating errors
evaluateM (Binary op a b) env =
evaluateM a env >>=
\v1 -> evaluateM b env >>=
\v2 -> checked_binary op v1 v2
HAPTER 6. COMPUTATIONAL STRATEGIES
evaluate (Unary op a) env = Propagating errors
Error msg ! Error msg with
case evaluate a env of
Good av ! checked_unary op av evaluate (Binary op a b) env =
case evaluate a env of Error msg ! Error msg Good av !
case evaluate b env of Error msg ! Error msg Good bv !
checked_binary op av bv
This code is definitely longer.
w it should be clear why programmers do not always check a ause it is tedious and requires lots of code! What was original
Propagating errors
evaluateM (Binary op a b) env =
evaluateM a env >>=
\v1 -> evaluateM b env >>=
\v2 -> checked_binary op v1 v2
Still, the use of bind may not immediately intuitive.
Monads are a structure composed of two basic operations (bind and return), which capture a common pattern that occurs in many types.
Monads in are implemented using type
class Monad m where
(>>=) ::ma->(a->mb)->mb return :: a -> m a
Checked as a Monad
Because Checked can implement return and bind it can be made an instance of Monad
instance Monad Checked where
return v = Good v
Error msg -> Error msg
Good v -> f v
Rewriting Code Again
Using bind and return from the Monad class does
not affect the code:
evaluateM (Binary op a b) env =
evaluateM a env >>=
\v1 -> evaluateM b env >>=
\v2 -> checked_binary op v1 v2
Rewriting Code Again
However, because monads are so pervasive, Haskell notation).
supports a special notation for monads (called the do-
With the do-notation we can re-write the program as
evaluateM (Binary op a b) env =
do v1 <- evaluate a env
v2 <- evaluate b env
checked_binary op v1 v2
Do-notation
In Haskell, code using the do-notation, such as:
do pattern <- exp morelines
Is converted to code using bind:
exp >>= (\pattern -> do morelines)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com