Chapter 3: Functional Programming

3.1 Programs as Functions

  • In mathematics, variables always stand for actual values, while in imperative programming languages, variable refer to memory locations that store values. Therefore, x = x + 1 make no sense in mathematics.
  • In functional programming, once a variable is bound to a value, the variable cannot be change. Thus, there is no assignment.
  • Lack of assignment mean no notion of the internal state of a function.
  • Referential transparency mean the value of the function is not depend on the order of evaluation of its arguments. Thus, function must be view as value as well.

3.2 Scheme: A Dialect of Lisp

  • Syntax
    • expression → atom | ‘(‘ {expression} ‘)’
    • atom → number | string | symbol | character | boolean
  • Expression
    • #T mean true
    • #\a mean the character ‘a’
    • (2.1 2.2 2.3) is a list of numbers
    • (+ 2 3) is 2 + 3
  • Evaluation rule
    • atomic literal evaluate to themselves
    • symbol are treat as identifier.
    • parenthesized expression or list is evaluated as follow:
      • if first term is keyword, special rule applied.
      • otherwise, first term must evaluate to a function.
    • Scheme uses prefix form (+ 2 3) is 2 + 3.
    • quote will return the expression without evaluation. (quote (2.1 2.2 2.3)) or ‘(2.1 2.2 2.3) return (2.1 2.2 2.3)
    • (if exp1 exp2 exp3) evaluate exp2 if exp1 is true, otherwise exp3 is evaluated. (similar to if-then statement)
    • (cond exp1 … expn) where each expi is a pair (first second) where second expression will be evaluated if first is true. (similar to switch statement)
    • (let ((a 2) (b 3)) (+ a b)) will allows variable names to be bound to values within an expression. Result is 5 for this expression.
    • (lambda param-list body) create a function without name to reference it. Use let to bind the function to a name but let cannot use to define recursive function, which letrec will. However let and letrec only introduce variables that are visible within the scope and for the lifetime of the let or letrec.
    • To make a new, global binding of a variable visible in the top-level environment, use define.
  • Dynamic or latent type checking means two things:
    • only values, not variables, have data types.
    • types of values are not checked until it is absolutely necessary to do so at runtime.
  • Tail and Non-Tail Recursion
    • To avoid inefficiency with recursion, make any recursive steps the last steps in any functions (or tail recursive).
  • Data Structures in Scheme
    • a list representation of binary tree could be (“horse” (“cow” () (“dog” () ())) where a node in this tree is a list of three items (name left right).
    • If L is (1, 2, 3), then (car L) give the head element 1 and (cdr L) give a list without its head element, (2, 3). (cons 4 L) will add the element 4 at the head of list L, (4, 1, 2, 3).
    • (car (cdr L))) equals to (cadr L), (cdr (cdr L)) equals to (cddr L) and (car (cdr (cdr L))) equals to (caddr L).
    • null? return true if its list argument is empty
    • (list a) is equal to (cons a ‘())
  • Programming Techniques in Scheme
    • Use recursion to perform loops
    • Use accumulating parameter to turn a non-tail-recursive procedure into a tail-recursive procedure
  • HIgher-Order Functions
    • using lambda to define a function. f is a function with two parameters. We can define new function that uses make-double
      • (define make-double (lambda f) (lambda (x) (f x x)))
      • (define square (make-double *))
  • Static (Lexical) Scoping
    • In static scoping, the meaning or value of a given variable can be determined just by reading the text of the program.
    • In dynamic scoping, the meaning of a variable depends on the runtime context.
  • Symbolic Information Processing and Metalinguistic Power

3.3 ML: Functional Programming with Static Typing

3.4 Delayed Evaluation

  • Pass by name delayed evaluation is helpful in that it allows parameters to remain uncomputed if not needed and permits special forms similar to if and cond to be defined as ordinary functions.
  • Lazy Evaluation
    • All arguments to user defined functions are delayed
    • All bindings of local names in let and letrec expressions are delayed
    • All arguments to constructor functions (such as cons) are delayed
    • All arguments to other predefined functions, such as the arithmetic functions “1”, “*”, and so on, are forced
    • All function-valued arguments are forced
    • All conditions in selection forms such as if and cond are forced

3.5 Haskell – A Fully Curried Lazy Language with Overloading

  • Elements of Haskell
    • ++ operator for list concatenation
    • plus2 = (2 +) define a function that add 2 to its argument
    • (\X -> X * X) 3 is an anonymous function or lambda.
    • [1, 2, 3] is a list of 1, 2 and 3. The type must match for all elements.
    • (1, 2, 3) is a tuple of 1, 2 and 3.  The type does not have to match for all elements.
    • : corresponding to concatenating an element to the front of a list
  • HIgher-Order Functions and List Comprehensions
    • function composition operator (.)
    • ((*3) . (2+)) 5 gives 21 by doing function composition of 2+5 and then times 3.
    • List comprehensions
      • square_list lis = [x * x| x <- lis] is the same as (\x -> x * x)
  • Lazy Evaluation and Infinite Lists
    • [n..] stands for the list of integers beginning with n.
    • [2,4..] for even list of integer
    • take x will take x number of elements from the beginning of the list
    • drop x will drop x number of elements from the beginning of the list
  • Type Classes and Overloaded Functions
    • square x = x* x where square 2 will give 4 but square 3.5 will give 12.25. Thus, the function overloaded using type class Num. Int, Float and Double are instance of Num.
    • Class Eq requires for == and /=.
    • Class Ord requires for < or > …
    • Class Integral requires for div and mod operations.

3.6 The Mathematics of Functional Programming: Lambda Calculus

Additional Notes


Other Resources