Programming Languages

Module 10: Functional Programming

Xingang (Ian) Fang

Functional Programming Languages

Overview

Programming paradigm based on mathematical functions
Pure functional languages don’t use variables or assignment statements
Evaluation control through recursion and conditional expressions
Functions can be arguments and return values (higher-order functions)
Pioneered by Lisp (1959), continues with Scheme, ML, Haskell, F#

Mathematical Functions

Mapping from domain set to range set
Evaluation order controlled by recursion and conditional expressions
Referential transparency - expression can be replaced by its value without changing program behavior
No side effects - no changes to program state
Pure function - same input always produces same output
No concept of state or variables as in imperative languages
Higher-order functions (functional forms)
- Function composition: h = f ∘ g where h(x) = f(g(x))
- e.g. Apply-to-all higher-level function: applies function to each element in list
```
map(lambda x: x*x, [1, 3, 5, 7, 9])
// gives  [1, 9, 25, 49, 81]
```

Fundamentals

Mimics mathematical functions rather than von Neumann architecture
Programs are function definitions and applications
Referential transparency - function execution produces same result with same parameters
Primitives + functional forms + function application + data structures
Most functional languages include some imperative features for practicality

Lisp

First functional programming language (1959)
Originally pure functional but added imperative features
S-expressions for both code and data
Central to AI research and development
Dynamic typing and garbage collection
Lists as primary data structure (CAR, CDR, CONS)

(defun factorial (n)
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))
(factorial 5)
// gives 120

Scheme

Small dialect of Lisp developed at MIT (1970s)
Static scoping exclusively
Functions as first-class entities
Simple syntax and semantics
Used for educational applications
Core primitives: list operations, conditionals, predicates

Common Lisp

Amalgamation of several 1980s Lisp dialects
Large and complex with extensive features
Supports both static and dynamic scoping
Packages for modularization and access control
Macros for language extension
Used in AI applications, knowledge representation

ML

Static-scoped, strongly typed functional language
Type inference system - automatically determines types
No type coercions, no function overloading
Pattern matching for parameter forms
Syntax closer to imperative languages than Lisp
Influenced many later languages

fun factorial 0 = 1
  | factorial n = n * factorial (n - 1)
factorial 5
// gives 120

Haskell

Pure functional language with strong static typing
Three key differences from ML:
- Function overloading
- Nonstrict (lazy) evaluation
- No side effects
List comprehensions for set creation
Elegant and concise code
Supports infinite data structures through lazy evaluation

factorial 0 = 1
factorial n = n * factorial (n - 1)
factorial 5
-- gives 120

F#

.NET functional programming language based on OCaml
Combines functional, imperative, and object-oriented programming
Interoperability with other .NET languages
Full-featured IDE and extensive utility library
Type inference and pattern matching
Sequence values with lazy evaluation capability

let rec factorial n =
  if n = 0 then 1
  else n * factorial (n - 1)
factorial 5
// gives 120

Functional Features in Imperative Languages

Anonymous functions/lambda expressions in JavaScript, Python, Ruby, Java, C#
Higher-order functions (map, filter) in Python, Java, JavaScript
Partial function application in Python
Collection operations in C#, Java
Growing trend toward functional programming concepts

Comparison with Imperative Languages

Advantages:
- Simpler semantics
- More concise code (10-25% size of imperative equivalents)
- Improved readability (focus on logic rather than state management)
- Easier concurrent programming
- Better testability through referential transparency
Disadvantages:
- Generally slower execution (approximately 2x)
- Steeper learning curve for imperative programmers
- Less efficiency on von Neumann architecture

Functional Programming Topics Not Covered In Textbook

Real-world Applications

WhatsApp’s Erlang-based server
Facebook’s React framework
Sparks and Flink’s Scala-based engines
Twitter’s Scala-based server
Netflix’s Clojure-based services

Clojure

Clojure is a dialect of Lisp, and shares with Lisp the code-as-data philosophy and a powerful macro system.
A JVM-based language

 (defn factorial [n]
   (if (zero? n)
     1
     (* n (factorial (dec n)))))

(factorial 5)

Elixir

Elixir is a functional, concurrent, general-purpose programming language that runs on the Erlang virtual machine (BEAM).
Elixir builds on top of Erlang and shares the same abstractions for building distributed, fault-tolerant applications.

defmodule Factorial do
  def factorial(0), do: 1
  def factorial(n), do: n * factorial(n - 1)
end

Factorial.factorial(5)

JavaScript

JavaScript is a multi-paradigm language that supports functional programming.
Functions are first-class objects, and can be passed as arguments to other functions.

function factorial(n) {
  if (n === 0) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}
factorial(5)

val factorial = (n: Int) => {
  if (n == 0) 1
  else n * factorial(n - 1)
}
factorial(5)

val factorial: Int => Int = n => if (n == 0) 1 else n * factorial(n - 1)
factorial(5)

Scala

Scala is a hybrid functional programming language that combines object-oriented and functional programming.
It runs on the Java Virtual Machine (JVM).

def factorial(n: Int): Int = {
  if (n == 0) 1
  else n * factorial(n - 1)
}
factorial 5

val factorial: Int => Int = n => if (n == 0) 1 else n * factorial(n - 1)
factorial 5

val factorial: Int => Int = (n: Int) => {
  if (n == 0) 1
  else n * factorial(n - 1)
}
factorial 5

Introduction to Haskell

A purely functional programming language
Named after logician Haskell Curry
Developed by a committee in the late 1980s
Current standard: Haskell 2010
Statically typed with type inference
Lazy evaluation by default
Emphasizes mathematical purity

Key Characteristics of Haskell

Pure functions: No side effects
Immutability: Data cannot be changed after creation
Type inference: Compiler can deduce types
Lazy evaluation: Expressions evaluated only when needed
Pattern matching: Destructure data based on its shape
Type classes: A form of interface/trait system
Strong focus on abstraction

Why Learn Haskell?

Encourages a different way of thinking about problems
Makes concurrent programming easier through immutability
Produces highly reliable code (if it compiles, it often works)
Many ideas from Haskell influence other languages
Builds strong foundations in computer science concepts
Elegant solutions to complex problems

Hello World in Haskell

main :: IO ()
main = putStrLn "Hello, World!"

Simple, but there’s a lot to unpack:

main :: IO () is a type signature
IO is a type that handles side effects
The function definition uses = not return

Pure Functions

A pure function:

Always returns the same output for the same input
Has no side effects
Does not modify state

-- Pure function
add :: Int -> Int -> Int
add x y = x + y
-- The type Int -> Int -> Int means it takes two Ints and returns an Int
-- This is considered a curried function in Haskell

-- This will always return 7
result = add 3 4

Higher-Order Functions

Functions that:

Take other functions as arguments
Return functions as results

-- map is a higher-order function
-- it takes a function and a list, and applies the function to each element
doubleAll :: [Int] -> [Int]
doubleAll numbers = map (\x -> x * 2) numbers
-- doubleAll = map (*2)  -- Equivalent to the above

-- filter is another higher-order function
-- it takes a predicate function and a list, and returns elements that satisfy the predicate
evenNumbers :: [Int] -> [Int]
evenNumbers numbers = filter even numbers

Function Composition

Combining functions to create new functions:

-- Using the composition operator (.)
processData :: [Int] -> [Int]
processData = filter even . map (*2)

-- Equivalent to:
processData' :: [Int] -> [Int]
processData' numbers = filter even (map (*2) numbers)

Function composition makes code:

More readable
More modular
Easier to reason about

Tail Recursion

A form of recursion where the recursive call is the last operation:

-- Non-tail recursive factorial (builds up computation)
factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)

-- Tail recursive factorial (uses accumulator)
factorialTail :: Integer -> Integer
factorialTail n = helper n 1
  where
    helper 0 acc = acc
    helper n acc = helper (n - 1) (n * acc)

Tail recursion can be optimized by the compiler into iteration (loop)!
where clause defines a local helper function
acc parameter accumulates the result as the recursion progresses
n * acc is done before the recursive call
The last line of helper is the recursive call which does nothing but call itself, nothing to do after that

Algebraic Data Types (FYI)

Custom data structures defined by their shape:

-- Sum type (OR)
data Bool = True | False

-- Product type (AND)
data Person = Person String Int  -- name and age

-- Recursive type
data List a = Empty | Cons a (List a)

-- Pattern matching with algebraic data types
getName :: Person -> String
getName (Person name _) = name

Lazy Evaluation

Expressions are only evaluated when their results are needed:

-- Infinite list definition
naturalNumbers = [1..]

-- Takes only the first 10 elements
first10 = take 10 naturalNumbers  -- [1,2,3,4,5,6,7,8,9,10]

Benefits:

Can work with infinite data structures
Improved performance in some cases
Enables more compositional programming style

The CodeWorld Environment

https://code.world/haskell

Browser-based Haskell environment
No installation required
Great for learning and experimentation
Features: * Code editor with syntax highlighting * Immediate execution * Visual output capabilities * Share your code with others * Save your work locally

Using CodeWorld

Open https://code.world/haskell in your browser
Write your Haskell code in the editor
Click “Run” to execute
See the results in the output area
Use “Save” to download your code as a .hs file