程序代写代做代考 Haskell javascript compiler Lambda Calculus Java FIT2102

FIT2102
Programming Paradigms Workshop 3
Functional Programming Pure functions TypeScript
Faculty of Information Technology

Learning Outcomes
● Create programs in JavaScript in a functional style
● Explain the role of pure functional programming style in managing side effects
● Create programs in TypeScript using the types to ensure correctness at
compile time
● Explain how Generics allow us to create type safe but general and reusable
code
● Compare and contrast strongly, dynamically and gradually typed languages
● Describe how compilers that support type inference assist us in writing type
safe code
● Create linked-lists and functions that operate over them, using:
○ Objects and classes
○ Only functions (Church encoded lists)

Recap: Creating Objects from Classes
class Person {
constructor(name, occupation) {
this.name = name
this.occupation = occupation
}
sayHello() {
console.log(`Hi, my name’s ${this.name} and I ${this.occupation}!`)
} }
const tim = new Person(“Tim”,”lecture Programming Paradigms”)
tim.sayHello()
> Hi, my name’s Tim and I lecture Programming Paradigms!

Recap: Object-Oriented Polymorphism
class LoudPerson extends Person {
sayHello() {
console.log(this.greeting.toUpperCase())
}
}
const tims = [
new Person(“Tim”,”lecture Programming Paradigms”),
new LoudPerson(“Tim”,”shout about Programming Paradigms”)
]
tims.forEach(t => t.sayHello())
Hi, my name’s Tim and I lecture Programming Paradigms!
HI, MY NAME’S TIM AND I SHOUT ABOUT PROGRAMMING PARADIGMS!
Classic OO using subtyping to achieve polymorphism
A single interface for different types.
Later today we will be introducing another way of creating functions that operate over different types: parametric polymorphism

Recap: Dependency Injection with Functions
class Person {
constructor(name, occupation, voiceTransform = g => g) {
this.name = name
this.occupation = occupation
this.voiceTransform = voiceTransform
}
sayHello() {
console.log(this.voiceTransform(this.greeting))
}
}
const tims = [
new Person(“Tim”, “lecture Programming Paradigms”),
new Person(“Tim”, “shout about Programming Paradigms”, g => g.toUpperCase())
]
tims.forEach(t => t.sayHello())
Hi, my name’s Tim and I lecture Programming Paradigms!
HI, MY NAME’S TIM AND I SHOUT ABOUT PROGRAMMING PARADIGMS!
Default to “identity” function
We “inject” a dependency on toUpperCase from outside the Person class

Recap: Closures and higher-order functions
A function and the set of variables it accesses from its enclosing scope is called a closure
const multiply = =>
const double = multiply(2) [5,8,3,1,7,6,2].map(double)
> [ 10, 16, 6, 2, 14, 12, 4 ]
e.g., the closure returned by multiply(2) includes x=2
x
y=> *y
x
Functions that take other functions as parameters
or that return functions are called higher-order functions.

Recap: Arrow Function Syntax
A function is a transform from one set of things to another:
Input Set
Output Set
function(x) {
return x / 3
}
x => x/3
This function is a transform from number to number
In math we would be more precise: e.g. the set of integers Z
to (a subset of) rationals Q

Arrow function syntax – don’t panic
const multiply = x=> y=> x*y
function multiply(x) { return y => y * x;
}
function multiply(x) { return function(y) {
return x * y; }
}
Semantically all the same! (unless they refer to this)

const operationOnTwoNumbers = f => x => y => f(x,y)
function operationOnTwoNumbers(f) {
return function(x) {
return function(y) {
return f(x,y);
} }
}
Semantically the same!

const operationOnTwoNumbers = f => x => y => f(x,y)
const multiply = operationOnTwoNumbers((x,y) => x*y)
const double = multiply(2)
[5,8,3,1,7,6,2].map(double)

Currying
translating a function that takes multiple arguments into a sequence of unary functions.
const operationOnTwoNumbers = f => x => y => f(x,y)
const multiply = operationOnTwoNumbers((x,y) => x*y)
const double = multiply(2)
[5,8,3,1,7,6,2].map(double)
Named after the mathematician Haskell Curry.
Multiply is a curried function

TypeScript Type Annotations
TypeScript is a superset of JavaScript that introduces type annotations
Any time you declare a variable, function, parameter, etc you can add a type annotation:
let x : number;
The compiler can often infer types from the context, i.e. type inference.
let x = 1;
Here x is obviously a number so an annotation is redundant.
When a type cannot be inferred, the type is any
Thus, TypeScript’s default approach to type checking is gradually typed.

TypeScript Type Errors
let x = 1; // type number is inferred
x = ‘hello’
> error TS2322: Type ‘”hello”‘ is not assignable to type ‘number’.

TypeScript Foo
const operationOnTwoNumbers =
(f:(x:number, y:number)=>number) =>
(x:number) =>
(y:number) =>
f(x,y)
function operationOnTwoNumbers(f:(x:number, y:number)=>number) {
return function(x:number) {
return function(y:number) {
return f(x,y);
} }
}

Type Aliases
type BinaryNumberFunc = (x:number, y:number) => number
type CurriedNumberFunc = (x:number) => (y:number) => number
const operationOnTwoNumbers: (f:BinaryNumberFunc)=>CurriedNumberFunc
= f=>x=>y=>f(x,y)
function operationOnTwoNumbers(f:BinaryNumberFunc):CurriedNumberFunc {
return function(x) {
return function(y) {
return f(x,y)
} }
}

Generic Types: parametric polymorphism
type BinaryFunction = (x:T, y:T) => T
type CurriedFunction = (x:T) => (y:T) => T
T is a type parameter (or type variable)
const curry: (f:BinaryFunction)=>CurriedFunction
= f=>x=>y=>f(x,y)
function curry(f:BinaryFunction):CurriedFunction {
return function(x) {
return function(y) {
return f(x,y)
} }
}

Generic Types
type BinaryFunction = (x:T, y:T) => T
type CurriedFunction = (x:T) => (y:T) => T
const curry: (f:BinaryFunction)=>CurriedFunction
= f=>x=>y=>f(x,y)
const twoToThe = curry(Math.pow)(2)
twoToThe(8)
> 256
const concat = Array.prototype.concat.bind([]),
curriedConcat = curry(concat)
[[1,2],[1,2],[1,2]].map(curriedConcat([0])))
> [[0,1,2],[0,1,2],[0,1,2]]
⇦ This still type checks This is just creating a standalone concat
function from the concat method on Array
⇦ But now so does this:
It works for numbers or arrays

Generic Types
type BinaryFunction = (x:T, y:U) => V
type CurriedFunction = (x:T) => (y:U) => V
const curry: (f:BinaryFunction)=>CurriedFunction
= f=>x=>y=>f(x,y);
const twoToThe = curry(Math.pow)(2)
twoToThe(8)
> 256
⇦ This still type checks
const repeat = (n: number, s: string) => s.repeat(n)
console.log([‘a’,’b’,’c’].map(curry(repeat)(3)))
> [“aaa”, “bbb”, “ccc”]
⇦ But now so does this! (T ≠ U, T ≠ V)

Lecture Activity 1
… to be announced

Linked Lists
interface IListNode {
data: T;
next?: IListNode;
}
const l:IListNode = {
data: 1,
next: {
data: 2,
next: {
data: 3,
next: null }
} }
function length(l?:IListNode): number {
return !l ? 0 : 1+length(l.next);
}
> length(l)
3
function forEach(f: (_:T)=>void, l?:IListNode): void {
if (l) {
f(l.data);
forEach(f, l.next);
}
}
> forEach(console.log, l);
1
2
3

Linked Lists
interface IListNode {
data: T;
next: List;
}
Union Type
function length(l:List): number {
return !l ? 0 : 1+length(l.next)
}
> length(l)
3
function forEach(f: (_:T)=>void, l:List): void {
if (l) {
f(l.data)
forEach(f, l.next)
}
}
> forEach(console.log, l)
1
2
3
type List = IListNode | null
const l:IListNode = {
data: 1,
next: {
data: 2,
next: {
data: 3,
next: null }
} }

Linked Lists – map
interface IListNode {
data: T;
next: List;
}
type List = IListNode | null
function map(f: (_:T)=>V, l: List) : List {
return l ? > {
data: f(l.data),
next: map(f, l.next)
} : null
}
> forEach(console.log, map(x=>2*x, l))
2
4
6

Linked Lists – map with a class constructor
interface IListNode {
data: T;
next: ListPtr;
}
type List = IListNode | null
}
class ListNode implements IListNode {
constructor(
public data: T,
public next: List) {}
}
const list = new ListNode(1,new ListNode(2, new ListNode(3, null)))
function map(f: (_:T)=>V, l: List) : List
{
return l ? new ListNode(f(l.data), map(f, l.next))
: null
> forEach(console.log, map(x=>2*x, l))
2
4
6

Linked Lists – concat
interface IListNode {
data: T;
next: List;
}
type List = IListNode | null;
? = Optional parameter

function concat(a:List, b?:List): List {
return a ? new ListNode(a.data, concat(a.next, b))
class ListNode implements IListNode {
constructor(
🙁
b ? concat(b)
: undefined )
}
public data: T,
public next: List) {}
> forEach(console.log, concat(l,map(x=>3+x, l)))
1
2
3
4 5 6
}

Cons Lists (Church encoding)
Can we create lists with only lambda (anonymous) functions?
const cons = (head, rest) =>
const head = => list((head, rest)=> head)
const rest = list => list((head, rest)=> rest)
const aList = cons(‘Lists’, cons(“don’t”, cons(“get”, cons(‘any’,
cons(‘simpler’, cons(‘than’, cons(‘this’,
null))))))) head(rest(rest(aList))) ⇨ “get”
f
=> f(head, rest)
list

Types for Cons Lists
Make the shapes of functions we expect on the previous slide explicit
/**
* A ConsList is either a function created by cons, or empty (null)
*/
type ConsList = Cons | null;
/**
* The return type of the cons function, is itself a function
* which can be given a selector function to pull out either the head or rest
*/
type Cons = (selector: Selector) => T | ConsList;
/**
* a selector will return either the head or rest
*/
type Selector = (head:T, rest:ConsList)=> T | ConsList;

Typed Cons List Functions
/**
* cons “constructs” a list node, if no second argument is specified it is the last node in the list */
function cons(head:T, rest: ConsList): Cons {
return (selector: Selector) => selector(head, rest);
}
/**
* head returns the first element in the list
* @param list is a Cons (note, not an empty ConsList) */
function head(list:Cons):T {
return list((head, rest) => head);
}
/**
* rest everything but the head
* @param list is a Cons (note, not an empty ConsList) */
function rest(list:Cons):ConsList {
return >list((head, rest) => rest);
}

How do we get stuff out?
const aList = cons(‘Lists’, cons(“don’t”, cons(“get”,
cons(‘any’, cons(‘simpler’,
cons(‘than’, cons(‘this’)))))))
function listToString(l:ConsList): string {
if (!l) {
return ”
} else {
return head(l) + ‘ ‘ + listToString(rest(l))
}
}

How do we get stuff out?
const aList = cons(‘Lists’, cons(“don’t”, cons(“get”,
cons(‘any’, cons(‘simpler’,
cons(‘than’, cons(‘this’)))))))
const listToString: (l:ConsList) => string
= l => l ? head(l) + ‘ ‘ + listToString(rest(l)) : ”
console.log(listToString(aList));
> Lists don’t get any simpler than this!

Lecture Activity 2
… to be announced

Conclusions: Avoid hand-coded loops
for ([initialization]; [condition]; [final-expression]) statement
The initialization can initialise to the wrong value (e.g. n instead of n-1, 1 instead of 0) or initialise the wrong variable.
The condition test can use = instead of ==, <= instead of < or test the wrong variable, etc. The final-expression can (again) increment the wrong variable. The statement body might change the state of variables being tested in the termination condition since they are in scope. Conclusions: Function Purity Every function that we’ve looked at today (except console.log) has been pure. A pure function does not change the state of the surrounding program, or the world. More than that, within the functions we did not reassign variables. We say that these functions had referential transparency. Referential transparency gives simple, reusable, safe functions. Conclusions: Functions as a model of computation The cons lists created only through functions are an example of “Church Encoding” In the 1930s Alonzo Church created a model of computation which used only anonymous functions. This model of computation became known as the “Lambda Calculus” We will meet the lambda calculus properly in coming weeks.