CS 11 Haskell track: lecture 1nThis week:nIntroduction/motivation/pep talknBasics of HaskellPrerequisitenKnowledge of basic functional programmingne.g. Scheme, Ocaml, ErlangnCS 1, CS 4n"permission of instructor"nWithout this, course will be pretty hardQuote"Any programming language that doesn't change the way you think about programming is not worth learning." -- Alan PerlisWhy learn Haskell? (1)nPound for pound, Haskell has more novel concepts than any programming language I've ever seennand I've seen 'em allnVery powerful and innovative type systemnExtremely high-level languagenWill make you smarternFun to program in!Why learn Haskell? (2)nVery elegant and concise code:quicksort :: (Ord a) => [a] -> [a]quicksort [] = []quicksort (x:xs) = quicksort lt ++ [x] ++ quicksort ge where lt = [y | y <- xs, y < x] ge = [y | y <- xs, y >= x]nWorks for any orderable typenAny problem that can be characterized as a transformationnCompilersnDSLs (Domain-Specific Languages)nImplementing mathematical/algebraic conceptsnTheorem proversWhat Haskell is good atnAny problem that requires extreme speednunless you use Haskell to generate C codenAny problem that is extremely statefulne.g. simulationsnthough monads can get around this to some extentWhat Haskell is not good atnHaskell is a programming languagenduhnA functional programming languagenyou all know what that isnA lazy functional programming languagenHas strong static typingnevery expression has a typenall types checked at compile timeWhat is Haskell, anyway?nNamed after Haskell Currynpioneer in mathematical logicndeveloped theory of combinatorsnS, K, I and fun stuff like thatWhat is Haskell, anyway?nLazy evaluation means expressions (e.g. function arguments) are only evaluated when needednAs opposed to strict evaluation, where arguments to a function are always evaluated before applying the functionnWhat does this mean in practice?Laziness (1)nLazy evaluation can do anything strict evaluation can donand will get the same answernLazy evaluation can also do things strict evaluation cannot donSeems like a minor point, but...nHas a profound impact on the way programs are writtenLaziness (2)nExample:let f x = 10f (1/0)nIn strict language, this causes an errornIn lazy language this returns 10n1/0 is never evaluated, because it wasn't needednBig deal, right?Laziness (3)nFinite list of integers:let one_to_ten = [1..10]nCan do this in either lazy or strict languagenInfinite list of integers:let positive_ints = [1..]nCan only do in lazy languageLaziness (4)nWhat can we do with this?let positive_ints = [1..]let one_to_ten = take 10 positive_intsnNow the first ten positive_ints are evaluatednbecause we needed them to compute one_to_tennThe rest are still in unevaluated formnDetails of this are handled by the systemLaziness (5)nAllows many programs to be written in a more elegant/concise manner than would otherwise be the casenCan be costly (wrap closures around each expression to delay evaluation)nMeans evaluation order cannot be specifiednbecause we don't know which arguments of a function call will be evaluated ahead of timeWhy lazy evaluation?nLazy evaluation is a "side effect" (pun intended) of having a pure functional languagenScheme, Lisp, Ocaml are impure functional languagesnalso support side-effecting computationsnPure functional languages support "equational reasoning"nMeans substitution model of evaluation holdsnrecall CS 4nno messy environment model to worry aboutWhy lazy evaluation?nEquational reasoning means programs are much easier to reason aboutne.g. to prove correctnessnFunctions are "referentially transparent"ni.e. they're black boxesna given input will always produce same outputnlarge classes of bugs that cannot happen!nNo side effects!Equational reasoningnNo side effects means:nNo assignment statementsnNo mutable variablesnNo mutable arraysnNo mutable recordsnNo updatable state at all!n"How do you guys live like this?"nNeed alternative ways of doing thingsNo side effects!nHaskell, like Lisp/Scheme and ML (Ocaml, Standard ML), is based on Church's lambda (λ) calculusnUnlike those languages, Haskell is pure (no updatable state)nHaskell uses "monads" to handle stateful effectsncleanly separated from the rest of the languagenHaskell "enforces a separation between Church and State"Haskell vs. Scheme/MLnFunctional data structures are automatically persistentnMeans that can't change a data structurenbut can produce a new version based on old versionnnew and old versions co-existPersistence (1)nPersistence eliminates large classes of bugs...n... but also means that many standard data structures are unusablenarrays, doubly-linked lists, hash tablesnPersistent data structuresnsingly-linked lists, trees, heapsnCan be less efficientnbut generally no worse than log(n) hitPersistence (2)nPure FP is kind of a programming "religion"nRequires learning new ways to do things, new disciplinesnRewards: nfewer bugsngreater productivitynhigher level of abstractionnmore fun!Pure functional programmingnWe'll see concrete examples of all these vague points as we go alongnNow, on to practical matters...End of pep talknHaskell is a compiled language like C, java, or ocamlnCompiler we'll use is ghcnthe Glorious Glasgow Haskell Compilernstate-of-the-art, many language extensionsnmostly written in Haskell (some C)nInitially, mainly use interactive interpreternghci (for "ghc interactive")Using Haskellnghci is a very useful learning/debugging toolnBut can't write everything in ghci that could be written in a Haskell programne.g. definitions of new typesnBetter approach: write code in files and load into ghci, then experiment with functions interactivelyghcinNow will give a whirlwind introduction to most basic features of HaskellnMuch will not be covered until future weeksIntroduction to the languagenTopicsnbasic types, literals, operators, and expressionsntype annotationsnaggregate types: tuples, listsnlet bindings, conditionalsnfunctions and function typesnpatterns, guardsIntroduction to the languagenFirst: how to write comments?-- This is a