CSc 520
Principles of Programming Languages

Christian Collberg

Department of Computer Science

University of Arizona

Functional Programming Languages

1 Functional Programming

In contrast to procedural languages, functional programs don't concern themselves with state and memory locations. Instead, they work exclusively with values, and expressions and functions which compute values.

2 Functional Languages

Common characteristics of functional programming languages:

  1. Simple and concise syntax and semantics.
  2. Repetition is expressed as recursion rather than iteration.
  3. Functions are first class objects. I.e. functions can be manipulated just as easily as integers, floats, etc. in other languages.
  4. Data as functions. I.e. we can build a function on the fly and then execute it. (Some languages).

3 Functional Languages...

  1. Higher-order functions. I.e. functions can take functions as arguments and return functions as results.
  2. Lazy evaluation. Expressions are evaluated only when needed. This allows us to build infinite data structures, where only the parts we need are actually constructed. (Some languages).
  3. Garbage Collection. Dynamic memory that is no longer needed is automatically reclaimed by the system. GC is also available in some imperative languages (Modula-3, Eiffel) but not in others (C, C++, Pascal).

4 Functional Languages...

  1. Polymorphic types. Functions can work on data of different types. (Some languages).
  2. Functional programs can be more easily manipulated mathematically than procedural programs.

Pure vs. Impure FPL


5 Scheme

6 Scheme -- Evaluation Order

7 Scheme -- Metacircular Interpreter

8 Scheme -- Lists


9 Scheme -- Typing

10 Scheme -- Higher-Order Functions


11 What is Haskell?

12 Haskell -- Lazy evaluation

13 Haskell -- Infinite data structures

    countFrom n = n : countFrom (n+1)
    ? countFrom 1
    [1, 2, 3, 4, 5, 6, 7, 8,^C{Interrupted!}]
    (53 reductions, 160 cells)

14 Haskell -- Currying

Referential Transparency

15 Referential Transparency

16 Referential Transparency...

17 Side Effects -- Bad

18 Side Effects -- Good

19 Trivial Update Problem

20 Sisal

21 Sisal...

type OneDim = array [ real ];
type TwoDim = array [ OneDim ];

function generate( n : integer returns TwoDim, TwoDim )
   for i in 1, n cross j in 1, n
   returns array of real(i)/real(j)
           array of real(i)*real(j)
   end for
end function % generate

22 Sisal...

function doit( n : integer; A, B : TwoDim returns TwoDim )
   for i in 1, n cross
       j in 1, n
      c := for k in 1, n
              t := A[i,k] * B[k,j]
            returns value of sum t
            end for
   returns array of c
   end for
end function % doit

function main(  n : integer returns TwoDim )
let A, B := generate( n )
in  doit( n, A, B )
end let
end function % main

23 Sisal...

Lambda Calculus

24 Lambda Calculus

25 Lambda Calculus -- Reductions

26 Lambda Calculus -- Termination

27 Lambda Calculus -- Paths

28 Lambda Calculus -- Application Order

29 Church-Rosser Theorem

30 Church-Rosser Theorem...

31 Church-Rosser Theorem II

32 Church's Theses

The effectively computable functions on the positive integers are precisely those functions definable in the pure lambda calculus.

33 Readings and References

Christian S. Collberg