CS 345 slide 361 Spring 200529 April 2005An application of get (with more uses of Maybe)A floating-point-numeral parser:> float :: Parser Float> float => do sign <- optional (char '-')> int <- digits> fpart <- optional (do char '.'> ds <- digits> return ('.': ds) )> let mag = case fpart of> Just frac -> read (int ++ frac)> Nothing -> read int> return (case sign of> Nothing -> mag> _ -> - mag)> digits :: Parser String> digits = do d <- digit> ds <- many digit> return (d:ds)> optional :: Parser a -> Parser (Maybe a)> optional p = do x <- p> return (Just x)> +++> return NothingCS 345 slide 362 Spring 200529 April 2005A demonstration function:> double :: IO ()> double = do f <- get "input a number: " float> putStrLn ("2 * " ++ show f ++ " = "> ++ show (2*f))A session:Main> doubleinput a number: 9876,5432 ... syntax errorinput a number: 9876.54322 * 9876.5432 = 19753.0864CS 345 slide 363 Spring 200529 April 2005Maybe and MonadBecause Maybe is an instance of Monad, functions thatreturn Maybe values can be composed using do :Example: Define a function process so thatprocess ns j kfinds the jth and kth elements of the list ns, andreturns their sum. If either of j and k is not a validindex of ns, process should return 0.A straightforward solution:> process :: Num a => [a] -> Int -> Int -> a> process ns j k> | 0 <= j && j < lns &&> 0 <= k && k < lns = ns!!j + ns!!k> | otherwise = 0> where> lns = length ns> (!!) :: [b] -> Int -> b> (x:_) !! 0 = x> (_:xs) !! n | n>0 = xs !! (n-1)> (_:_) !! _ = error "negative index"> [] !! _ = error "index too large"This function• requires 3 traversals of ns• fails when ns is infiniteCS 345 slide 364 Spring 200529 April 2005Using Maybe as a monad:> process :: Num a => [a] -> Int -> Int -> a> process ns j k = case do m <- ns !!! j> n <- ns !!! k> return (m+n)> of Just s -> s> Nothing -> 0> where> infixl 9 !!!> (!!!) :: [a] -> Int -> Maybe a> (x:xs) !!! 0 = Just x> (_:xs) !!! n | n>0 = xs !!! (n-1)> _ !!! _ = NothingThis function• requires only 2 traversals of ns• works even when ns is infiniteMaybeTest> process [1..10] 3 510MaybeTest> process [1..10] 12 50MaybeTest> process [1..10] 3 500Conclusion: Like exceptions, Maybe provides a way todistinguish between “normal” and “exceptional”processing.• In C++ and Java, exceptions provide alternativeexecution sequences (throw catch).• In Haskell, Maybe provides an alternative value(Nothing).CS 345 slide 365 Spring 200529 April 2005The Big Picture: The semester in contextSoftware’s problem: Unmastered ComplexityHow have languages evolved in response?• machine-oriented programmer-orientedThis reflects technological advances:• Computers are fast, inexpensive and abundantMoore’s Law: Transistor density doubles every 18months.—Gordon Moore, 1965Understanding this phenomenal (exponential) growth:If cars had improved at the same rate asinformation technology over the past 35 years,with respect to size, cost, performance, andenergy efficiency, then an automobile would• be the size of a toaster• cost $200• travel 100,000 miles per hour• get 150,000 miles from one gallon of fuelCS 345 slide 366 Spring 200529 April 2005During these 35 years, the “hardware” of the humanbrain hasn’t improved at all.The obvious lessons:• We should make computers do moreso humans can do less.• We should provide the brain with better“software”, i.e., better methods of thinking.How do we apply this conclusion inprogramming?We attack complexity by means of• programming languages that are more abstract(higher-level, simpler)• more and better abstractions to use in buildingsoftware• better programming-language technology forbuilding and using abstractionsCS 345 slide 367 Spring 200529 April 2005Abstraction in Language EvolutionMachine-oriented languages• machine languages, assembly languages• one machine operation per instruction1st-generation imperative languages (1960)• expressions: many machine operations perstatement; readable, modular, and abstract• variables: representing storage locations• procedures (named subprograms withparameters): the first appearance of programmer-defined abstractionsExamples: FORTRAN, ALGOL–60, COBOL2nd-generation imperative languages (early ’70s)• control structures (if, case, for, while) replacethe go-to• programmer-defined data typesExamples: C, Pascal3rd-generation imperative languages (late ’70s)• modules restrict names’ visibility: software getsfirewalls, watertight compartments• abstract data types (not fully baked)• support for defining and coordinating concurrentprocessesExamples: Modula–2, AdaCS 345 slide 368 Spring 200529 April 20054th-generation imperative languages (mid ’80s)• full support for ADTs (auto-initialization, deepcopying)• ad-hoc polymorphism (overloading)• parametric polymorphism (templates)Example: C++5th-generation (object-oriented) imperativelanguages (’90s)• ADTs plus type derivation (extension), dynamicpolymorphism• garbage collection—memory managementbecomes a system responsibility (not C++)Examples: (C++,) Smalltalk, Eiffel, Java, OberonAnother trend: Notational sprawl (the “kitchen-sink”syndrome)• languages grow bigger, more complex• features are added ad hoc• features interact in unexpected waysExamples: C++, Ada, Fortran–90Counterexamples: Oberon, Java,
View Full Document