Fuctional Programming Day1

1. Function programs 
2. Methods to construct Function programs
3. Ways to reason about Function programs 

Functional programming is a paradigm

Migration path from a more concise java language to full-functional programming

A paradigm describes distinct concepts / thought patterns in some scientific discipline

Main programming paradigms

1. Imperative java C current
2. Functional 
3. Logic 

Orthogonal to these 3 paradigm

OOP. Combine 3

Imperative 

1. Modify mutable variables 
2. Using assignments
3. Control structures 

3. e.g if-then-else, loops breaks continue return

VN computer model:

processor 

Memory 

Bus reads both instructions and data 

Width of the bus of 1 machine 32/64bits nowadays

Strong correspondence between the memory cells in VN machine and mutable variables in programming language

变量

Mutable variables —> memory cells

Variable dereferences —> load instructions

变量法则

Variable assignments —> store instructions

Control structures—> jumps 

(Sequence of loops)

Avoid conceptualizing the programs (data structure) word by wordRather, to scale up 

                                 higher level abstraction

                                 ⬇️

We need to reason in larger structures

Ideally，collections; polynomials; geometric shapes; strings documents

Theory:

Data types + operations +laws describing the relationships bwt value & operations

But it does not describe mutations!

Change sth while keeping the identity of the thing the same

Theories without mutation:

(a*x +b ) +(c*x +d) = (a+c)*x +(b+d)

2 coefficient of the same degree & the sum of coefficients…

Mutation— define an operator to change a coefficient while keeping the polynomial the same

Imperative program one can write:

Class Polynomial {double [] coefficient; }

Polynomial p = …;

p.coefficient[0] = 42;

Here we can set coefficient, but keep the p same

Mathematically unavailable

Strings defines a concatenation operator ++ which is associative

(a++b) ++c = a++(b++c)

Not define an operator to change a sequence element while keeping the sequence the same

java, type of string is immutable 

If we want to implement high-level concepts following the mathematical theories, there’s no place for mutation 

Theories don’t admit it—don’t have mutation operator

Mutation can destroy useful laws in the theories

So FP

Concentrate on defining theories for operators expressed as functions

Avoid mutations

Have powerful and new ways to abstract and compose functions

Restrictedly, FP means programming without  mutable variables, assignments, loops and other imperative control structures

Widely, it means focusing on the functions, which can be values that are produced, consumed and composed

Can be done in any programming language, but much easier in FP

FP enables the constructions of elegant programs that focus on functions 

Can be defined anywhere even inside other functions

Like other values, they can be passed as parameters to functions, returned as results

As for other values, there exists a set of operators to compose functions

Restricted 

Pure lisp, XSLT, XPath, XQuery (XML domain)FP

Haskell

Wider 

Lisp scheme Racket…

SCala, Ruby!(OOL) Smalltalk

Javascript

Book Structure and Interpretation of Computer Programs MIT