it-ebooks - Functional Systems In Haskell Lecture Notes(Stanford CS240h)

From: CS240h lecture notes

• I'm David Mazires
  • Spent most of my career working on OSes, Systems, and Security
  • Previously used C++ and C, but started using Haskell 5 years ago
  • Course partly inspired by my experience learning Haskell
• Other instructor: Bryan O'Sullivan
  • Has implemented many key Haskell libraries in widespread use today
  • Co-wrote Real World Haskell, a great non-theoretical intro book
  • Also plenty of systems experience (e.g., Linux early userspace code)
• Course assistant: David Terei
  • Member of the Haskell standards committee!
  • Implemented Safe Haskell and GHC LLVM backend

• Haskell's expressive power can improve productivity
  • Small language core provides big flexibility
  • Code can be very concise, speeding development
  • Get best of both worlds from compiled and interpreted languages
• Haskell makes code easier to understand and maintain
  • Can dive into complex libraries and understand what the code is doing
    (why may be a different story, but conciseness leaves room for comments...)
• Haskell can increase the robustness of systems
  • Strong typing catches many bugs at compile time
  • Functional code permits better testing methodologies
  • Can parallelize non-concurrent code without changing semantics
  • Concurrent programming abstractions resistant to data races
• Haskell lets you realize new types of functionality (DIFC, STM, ...)

• Learn to build systems in Haskell with reduced upfront cost
  • Historically, Haskell was a vehicle for language research.
    The history is reflected in how the language is usually taught
  • CS240h will present the language more from a systems perspective
• Learn new, surprising, and effective programming techniques
  • Some are applicable to other languages (though returning to other languages after Haskell can be frustrating)
• You enjoy programming
  • With Haskell, you will think about programming in new ways
• You sometimes get frustrated with other languages
  • Maybe you've wanted to design a new language, or tend to "max-out" existing language features (macros, templates, overloading, etc.)
  • Things that require changes to most languages can be done in a library with Haskell

• We assume some of you may have toyed with Haskell, others not
• First week cover Haskell basics
  • If you haven't used Haskell, you should supplement by reading parts of Bryan's book and/or on-line tutorials (such as http://www.haskell.org/tutorial/ or http://learnyouahaskell.com/chapters).
  • If you have used Haskell, you may still learn some things from these lectures
• Rest of term covers more advanced techniques
• Final grade will be based on several factors
  1. Class attendance and participation -- bring your laptop to class
  2. Scribing one of the lectures -- need a volunteer for today
     • We plan to collect all the notes and distribute them freely on web
  3. Three small warm-up solo programming exercises
  4. A large final project & presentation

• Implement a project of your choice in Haskell
  • Projects may be done in teams of 1-3 people
  • Meet with one of the instructors to discuss project
  • Complete and evaluate project and turn in short paper
  • Final exam will be mini-conference where you present your work
  • Attending exam Tuesday, June 10th, 7:00pm-10:00pm is mandatory
    But by unanimous consent we could move this to Thursday June 5, 12:15-3:15pm. (And we would serve lunch...)

• We encourage overlap of CS240h project with your research
  • The programming techniques you learn in CS240h are likely orthogonal to whatever research you are doing
• We are okay with CS240h project also serving as another class project,
  provided the other instructor and all teammates (from both classes) approve

• Install Haskell Platform or cabal (sometimes cabal-install) + GHC

• Create a file called hello.hs with the following contents:

  main = putStrLn "Hello, world!"

• Compile your program to a native executable like this:

  $ ghc --make hello [1 of 1] Compiling Main ( hello.hs, hello.o ) Linking hello ... $ ./hello Hello, world!

• Or run it in the GHCI interpreter like this:

  $ ghci hello.hs GHCi, version 7.6.3: http://www.haskell.org/ghc/ :? for help ... Ok, modules loaded: Main. *Main> main Hello, world! *Main>

• Haskell uses the = sign to declare bindings:

  x = -- Two hyphens introduce a comment y = -- ...that continues to end of line. main = let z = x + y -- let introduces local bindings in print z -- program will print 5
  • Bound names cannot start with upper-case letters
  • Bindings are separated by ";", which is usually auto-inserted by a layout rule
• A binding may declare a function of one or more arguments
  • Function and arguments are separated by spaces (when defining or invoking)
  add arg1 arg2 = arg1 + arg2 -- defines function add five = add -- invokes function add

• Parentheses can wrap compound expressions, must do so for arguments

  bad = print add -- error! (print should have only 1 argument)main = print (add ) -- ok, calls print with 1 argument, 5

• Unlike variables in imperative languages, Haskell bindings are
  • immutable - can only bind a symbol once in a give scope (bound symbols still called "variables" since function arguments can vary across invocations)
  x = x = -- error, cannot re-bind x
  • order-independent - order of bindings in source code does not matter
  • lazy - definitions of symbols are evaluated only when needed
  safeDiv x y = let q = div x y -- safe as q never evaluated if y == 0 in if y == then else q main = print (safeDiv ) -- prints 0
  • recursive - the bound symbol is in scope within its own definition
  x = -- this x is not used in main main = let x = x + -- introduces new x, defined in terms of itself in print x -- program "diverges" (i.e., loops forever)

• In C, we use mutable variables to create loops:

  long factorial ( int n) { long result = ; while (n > ) result *= n--; return result; }

• In Haskell, use recursion to "re-bind" argument symbols in new scope

  factorial n = if n > then n * factorial (n - ) else
  • Recursion often fills a similar need to mutable variables
  • But the above Haskell factorial is inferior to the C one--why?

• Each recursive call may require a stack frame

  • This Haskell code requires n stack frames

    factorial n = if n > then n * factorial (n - ) else
  • By contrast, our C factorial ran in constant space