What is Functional Programming?

We are used to imperative programming.

Recall — Imperative Programming:

• Programs are structured as a sequence of instructions.
• Uses destructive updates for computations.

Remember — All programs transform data into something else.

Functional Programming:

• Programs are structured as function compositions.
• Destructive updates aren’t allowed.

Functions

Example — You can’t do x = 1 + y, instead you have to use functions.

Definition — Mathematical Function: A special type of relation.

• Relation: A subset of the cross product of two sets.

Related Notes — CS1300: Relations

tl;dr we are creating pairs, where the order matters.

If you cross a set with itself ???, you can define special properties like (e.g., int cross int, take a subset (relation)):

• Reflexivity:
• Symmetric:
• Transitive: A B C A
• Antisymmetry: A relation is antisymmetric when if A \to B and B \to A, they have to be equal. e.g., \le is antisymmetric.

e.g., prof. is his daughter’s Dad (symmetric), prof. is his wife’s spouse and his wife is his spouse (reflexive),

To add: Injective is another word for one-to-one. Surjectivity is when ???. If an ?? is both injective and surjective, we have a bijective relation. Bijectives have inverses, and the inverses are also functions.

Function are injective. They can be one-to-one or many-to-one.

Functional Equations

This is only a function if you provide domain and codomain.

f(x) = x + 1

Z \to Z

Z: Set of all integers.

Notice how this doesn’t change anybody. It keeps everything the same.

• FLs don’t do destructive updates. All a program does is take the input, transforms it without changing it. We just call functions on functions and functions and functions.

A program, rather than being a list, now just looks like

f_n ( f(_{n-1} ( f_{n-2} ( ... f_2 ( f_1 (\text{input} ) ) ) )

There are no variables. Functional programming languages like Prolog let you use let, which simply binds symbols to value, which cannot change. Variables can change, and functional languages don’t support them.

You can technically program functionally in Java, but it’s not designed for it.

Why do This?

The root of all evil: Destructive updates.

• Destructive updates create dependencies and make reasoning hard.
• Destructive updates could propagate changes.

If there are no changes, all computation is local.

• In other words, you can look at a single instruction and you don’t need to look at what else changes this value (because nothing else updates this).

Problems

There are parts of a program that need to do destructive updates.

• For example, printing to the screen. This means you can’t do anything visual, you can’t use arrays.

So, most functional languages provide some imperative features like printing to the screen that give you arrays, printing, etc.

• For example, sorting a list can only be quadratic. The clever stuff requires arrays.

TODO What is a function? What arhe relations?

What is SML?

Now, we’ll talk about functional programming in the context of SML for some concrete examples.

SML: A functional language.

Etymology — Stands for Standard ML, because it’s a modern version of ML (Meta-Language) a functional lang. made by Robin Milner in 1973. ML was made to talk about languages.

• One of the few fully formal language specifications (it’s literally all math).

There are several industrial-strength compilers.

• SML/NJ: TODO Install SML New Jersey
• Moscow ML
• TODO

“If your task is to write a compiler, bam. SML. It’s delicious.” professor then recommends “Practical Compilers in SML” for the third time. He has done like one for every language, but his SML one is “the best”

Overview

Functions are first-class citizens.

• They’re like any other value and can be bound to variables.
• Function values are closures.

Everything is built from expressions.

Powerful static type system:

• Also has a strong type interference.
  • If there’s an ambiguous type, it can assign a polymorphic type.

Advanced module system.

• Lets you do parametric, polymorphic, and abstract data types.

TODO Exception handling and Garbage collection.

Simple Types

There are four general purpose types: Integers (int), floating points (real), strings (string), booleans (biol), and characters (char).

Operators

Arithmetic Operators:

• Integers: +, -, *, div
• Reals: +, -, *, /

Why div? — We save / for reals because integer and floating-point division are different operations.

• Don’t mismatch types!

Unary Negation: ~

TODO Unary negation is different from subtraction??? TODO 47 - 5; versus ~5 + 47 ??? TODO So to make negative numbers, don’t use the subtraction operator, use unary.

Logical Operators:

• >, >=, <, <=, =, <>

Example: TODO

String Concatenation: ^

"Hello" ^ " World"

Declarations

Bindings between names and values.

Don’t forget, they’re NOT assignments!

Functions

Functions are defined using the fun keyword.

- fun f(x) = x+42;
val f = fn : int -> int

Functions are pure (they have no side-effects), aka: it doesn’t modify any memory.

Lambda Functions

Lambda functions are created with fn and =>

x => x * x

Multiple Parameters

You can declare multiple parameters as a tuple or in Curried form.

Definition — Curried Form: TODO

fun add(x,y) = x + y;
val add = fn : int * int -> int

- fun add x y = x + y;
val add = fn : int -> int -> int
- add 3 4;

---

**Using Curried Form**: 
```sml
- val plusFour = add 4;
val plusFour - fn : int -> int
- plusFour 3;
val it = 7 : int

Recursive Function

fun fac(x) = if (x=0) then 1 else x * fac(x-1);

Iteration v. Recursion — They both perform an action over-and-over. The difference is, in recursion, you repeat by calling the same function again; while in iteration you repeatedly jump until a condition is true.

The short of it: Recursion consumes more memory, but is easier to reason about.

Polymorphic Function

Definition — Polymorphism: The ability of an element to appear to have multiple forms or behaviors depending on context.

If the type engine can’t determine a type, the name gets a polymorphic type.

- fun toList x = [x];
val toList = fn : 'a -> 'a list
- toList 42;
val it = [42] : int list
- toList "hello";
val it = ["hello"] : string list

Tuples

Values from cross-products of different sets.

• They’re effectively groups of various elements, of potentially different types.
• We can use tuples to return multiple values.

Example: TODO use # to use a number from a tuple

Lists

Sequences of value of the same type.

• Represented as comma-separates lists delimited by brackets.
• Empty List: [] or nil

Operations

• ::: Prepend value (constant time)
• @: Concatenate two lists (linear time)
• hd: Return head
• tl: Return tail

Aside — SML does have arrays, but you want to avoid them as much as possible.

Example: TODO do an example of all of these. I also don’t fully understand head and tail.

Pattern Matching

SML features a powerful pattern-matching mechanism.

• It’s super useful for multi-part and recursive functions.

Example:

- fun fact 0 = 1
= | fact x = x * fact(x-1);
val fact = fn : int -> int

TODO Fibonacci example

<!– take a list of integers and compute their sum

fun sum()

Base Case: Empty list -> 0 fun sum nil = 0

Inductive Case: Add head to “rest of list” | sum l = hd(l) + sum (tl(l));

Pro:

fun sumV2 nil = 0 | sum(x::xs) = x + sum xs

Can’t see the projector. He does something with pattern matching and skips using the tail and head functions.

This style aids a lot with more complex code.

Q: Instead of the sum, compute th length of the list

A:

fun len nil = 0 | len x = 1 + len(tl(x));

Q: Now, return the reverse of the input of the list

A:

fun rev nil = nil | rev (x::xs) = (rev xs)@[x];

(x::xs)

• x: The front
• xs: The rest of the list

We reverse the rest of the list, and append the front

example trace suppose it it called on [1,2,3]

x will be bound to 1 xs will be bound to [2,3]

---

recursive

x will be bound to 2 xs will be bound to 3

---

recursive

x will be bound to 3 xs will be bound to []

---

recursive

base case hit, begin returning upwards

---

why does this program suck? because of the @, which is linear (this makes the algorithm quadratic).

Additionally, the stack of activiation records will explode.

So, here is a version that will tackle both problems.

fun tailrev [] acc = acc
| tailrev (x::xs) acc = tailrev xs (x::acc);

tailrev takes a list and an accumulator. we’ll use it.

fun brev l = tailrev l [];

A good SML programmer always programs like this, and never the first way!

• We don’t use the @

How does this work?

We have our list, and all we’re doing is taking the first element and putting it in the accumulator, until nothing is left.

We are doing Tail Recursion, the last action is takes in the inductive case is the recursive call.

• Tail recursion is special because it can be optimized. We don’t have to return in this case, which means the stack doesn’t explode. The compiler will deallocate and keep the stack constant in size.
  • The function behaves like a loop. TODO cleanup this massive blob.

Related Note: Recursion (CS2400) –>

GOAL: Write a function that computes the sum of a list, using Tail recursion

fun tailadd [] acc = acc | tailadd (x::xs) acc = tailadd xs (x+acc);

fun wrapadd l = tailadd l 0;

Avoiding Stack Overflow

Stack overflow is when the stack collides with the heap.

To avoid stack overflow, do tail recursion so that the stack doesn’t grow.

Recall — Recall that memory is organized into four sections:

1. Stack: Activation Records
2. Heap: Dynamically Allocated Data
3. Data: Statically Allocated Data
4. Text: Program Data

Definition — Activation Record: Stores everything you need for a function (local variables, arguments, etc.)

Let Expressions

We can create local bindings to simplify function definitions.

TODO
let
 value h1
 value h2
in
 (h1,h2)

Higher-Order Functions

Functions can be passed to other functions easily.

fun plusOne x = x+1
fun apply f [] = []
| apply f (x::xs) = f(x)::(apply f xs);
apply plusOne [41,41,41]

Notice how we did not do anything special to pass the function.

Because we use f like a function, SML knows it must be a function.

Example:

Q: Write a version of the apply function, that is tail recursive

:

A:

fun plusOne x = x+1;

fun tailapply f [] acc = acc
| tailapply f (x::xs) acc = tailapply f xs ((f(x))::acc);

fun wrapapply f l = rev (tailapply f l [] );