about · lately · live · notes · talks · writing · contact · thanks · support ·


Functional Programming

Overview

While LISP by McCarthy in 1958 was one of the first functional programming languages, it all started back with Alonzo Church in the 1930s who wanted to prove the foundations of mathematics. His creation of lambda calculus (also written as λ-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution.

Any program that can be authored can be done so using these three constructs:

exp -> var                         - variables
           | λvar. exp)            - abstraction
           | (exp1, exp2)       - applicatiopn

LISP

(lambda (arg) (+ arg 1))

(defun factorial (n)
      (if (= n 0) 1
      (* n (factorial (-n 1)))))

;; recursive
(defun factorial (n &optional (acc 1))
             (if (=n 0) acc
                   (factorial (- n 1) (* acc n))))

Scheme (1975)

Racket (1994)

Erlang (1986)

Elixir (2011)

Standard ML (1973)

Developed by a group (Miller/Tofte/Harper) that were interested in theorem proving and ways to automate their proofs.

fun fact (0 : int) : int = 1
     |  fact (n: int) : int = n * fact (n - 1)

OCaml (1996)

Miranda (1985)

fact :: num -> num || optional
fact 0 = 1
fact (n+1) = (n+1) * fact n

primes = sieve [2..]
sieve (p:x) = p : sieve [n |n <- x ; n mod [ ~= 0]

Haskell (1990)

fact :: Num a => a -> a	-- type signature is optional
fact 0 =n 1
factn = n * fact (n-1)

Agda (1999)

Idris (2011)

Teaching Functional Programming