# Functional Programming
> 1. 為什麼 '60 年代就有的 functional programming, 雖然沒有特別適合的底層運算裝置來配合, 在 2000 年以後越來越紅了呢? 它有什麼特性呢? modularization, reuse, easier to read and write, suitable for automatical parallelization (multi-thread, mult-icore, distributed programming), 現在主流的程式語言裡都有 functional programming 的身影, C++ 的 STL、python、Java、JavaScript、Ruby、Swift 等等，當然也有純粹的 functional progreamming language, 例如 Haskel, Idris, 以及其他混合型的語言像是 Closure, Scala, F#, Erlang, OCaml, Lisp, Racket, 和 Scheme。
> 2. 程式寫成一堆 function 的組合就叫做 functional programming 嗎??? (很多同學修過了程式語言 (programming language) 課程以後, 還是說不上來什麼是 functional programming,) 不是喔!! 不是看到 function 這個子八九不離十就是平常看到的函式了, 誤會大了, functional programming 的程式裡的確會有很多滿足**特殊性質**的 function, 但是沒有滿足的話基本上只是程序化的程式設計 procedural programming 而已。這裡的 **functional** 應該是一個數學的名詞, google 一下會看到它是 function of function, 數學領域中有 汎函分析 (functional analysis) 這個領域, 數學上所謂的 functional 是指 **定義域是函式 (function) 值域是實數或是複數**的 mapping (function)。可是有點尷尬的狀況是：functional programming 的中文翻譯是「函數式程式設計」或「函式設計」耶!!
> 3. functional programming 到底是什麼? decompose the program with higher order functions and glue them with function composition and the lazy evaluation mechanism, immutable objects, recursion, referentially transparent, no assignment, no side-effects, no flow of control, lambda functions
> 4. 什麼情況下需要使用這種 programming paradigm?
McCarthy 在 [1960 CACM 的文章](https://www-formal.stanford.edu/jmc/recursive.pdf) 中有證明 LISP 語言是 computational complete, 任意的流程都可以用 mutually recursive function 實現。

參考論文:
1. [John Hughes, Why Functional Programming Matters, 1984](https://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf)
2. [D.A. Turner, Some History of Functional Programming Languages, 2017](https://www.cs.kent.ac.uk

參考影片:
1. [Hughes, Why Functional Programming Matters @ Functional Conf 2016](https://www.youtube.com/watch?v=XrNdvWqxBvA)
2. [初探 Functional Programming：徹底改變程式思維 - 基礎概念篇](https://www.youtube.com/watch?v=qpOcRG3e9Q8&t=0s)
> record by [name=邱葵]
> [name=丁]
> 希望程式可以跟數學式子一樣 immutable 的，每個符號沒有在變的。X+2 就永遠是 X+2 不會改變。沒有東西需要暫時儲存或是更改。
> 所以在 abstract 裡頭談了那個年代他們在看模組化這件事情，但大家認為程序化、immutable 這種模組化很難做。所以在探討有沒有更進一步模組化的工具。所以想出了兩種連結到方法
> 滑鼠是在 '80 年初發明的裝置，在這之前的 input 都是 program control 的 input，程式叫你輸入就乖乖輸入。滑鼠發明之後就變成 user 叫電腦做 A 就做 A。電腦要及時處理 user 的input event，所以慢慢出現了 OOP 來達成物件之間的 event。'85 年左右 windows 原先不是用 OOP 語言實作的，但後來發現 OOP 非常符合視窗人機界面的概念，所以一開始的 Mac Lisa 就用了 Objective C 去寫
> 在 1984 年的時候就會希望程式寫出來的東西可以一直被其他部分使用，不會有太多重複的東西
>
> Functional programming我一直很不喜歡翻成中文，因為"函數化程式語言"那個function真的是"程序化或是物件化程式中的函數"嗎? 不是，是 higher order function，像是 reduce, map, filter，是用來做 composition 的函式
> "Functional programming 中很重要的事情是我們可以把程式、函數、資料當成Function"、"就像 2 這個資料是透過 1+1 而來的，100 是透過 1+1+1+....+1 而來的，所以資料可以是 functional"
>
> [name=煒甯]
> 為什麼沒有新的計算機架構
> [name=丁]
> Lambda calculus by Alonzo Church 是Turing Model 之外的另一種運算模型，可是沒有像 von Neumann 的硬體實作
>
> 

### code from 丁

sum [1, 2, 3]
= reduce add 0 [1, 2, 3]
= add 1 (reduce add 0 [2, 3])
= add 1 (add 2(reduce add0 [3]))
= add 1 (add 2(add 3 (reduce add0 nil)))
= add 1 (add 2(add 3 (0)))
= add 1 (add 2(add 3 0))
= add 1 (add 2(3))
= add 1 (add 2 3)
= add 1 (5)
= add 1 5
= 6

### codes in the paper WFPM
in Turner's [Miranda](https://www.cs.kent.ac.uk/people/staff/dat/miranda/nancypaper.pdf) language, 1985

listof X = nil | cons x (listof X)
note: data is function and function is data

[] = nil
[1] = cons 1 nil
[1, 2, 3] = cons 1 cons 2 cons 3 nil

sum = reduce add 0
add x y = x + y

reduce f x nil = x
reduce f x cons a list = f a reduce f x list

i.e. cons => f and nil => x

note: reduce is intrinsically a recursion function and both listof, treeof are data structures defined in a recursion way

product = reduce mult 1
mult x y = x * y

map f = reduce (cons . f) nil

doubleall = reduce (cons . double) nil = map double 
double a = 2 * a

squareall = reduce (cons . square) nil = map square
square a = a ＊ a

anytrue = reduce or false
or x y = x || y
alltrue = reduce and true
and x y = x && y

maxlist = reduce max -Inf
max a b = a if a>=b
        = b otherwise

append A B = reduce cons B A = 
cons a1 cons a2 ... cons an B = A + B

summatrix = sum . map sum

treeof X = node X subtrees
         = node X cons 1st-subtree rest
         = node X cons node root1 subtrees rest

redtree f g a treeof X
    = redtree f g a node X subtrees
    = f x redtree' f g a subtrees
redtree' f g a subtrees
    = redtree' f g a cons 1st-subtree rest
    = g redtree f g a 1st-subtree
        redtree' f g a rest
redtree' f g a nil = a

i.e. node => f,  cons => g,  nil => a

sumtree = redtree add add 0

maptree f = redtree (node . f) cons nil

list_labels = redtree cons append nil

maxtree = redtree max max nil

e.g.
a list L 

a tree T

# list L
[1, 2, 3] = cons 1 cons 2 cons 3 nil

sum [1, 2, 3]
    = reduce add 0 [1, 2, 3]
    = add 1 add 2 add 3 0
    = add 1 add 2 3
    = add 1 5
    = 6

# tree T
node 1 cons node 2 nil
       cons node 3 cons node 4 nil nil
       nil

sumtree T = redtree add add 0 T
    = add 1 add add 2 0
            add add 3 add add 4 0 0
            0
    = add 1 add add 2 0
            add add 3 add 4 0
            0
    = add 1 add add 2 0
            add add 3 4
            0
    = add 1 add add 2 0
            add 7
            0
    = add 1 add add 2 0
            7
    = add 1 add 2
            7
    = add 1 9
    = 10

repeat f a = cons a repeat f (f a)
           = [a, f(a), f(f(a)), ...]

# f a is a list of children of a
# reptree f a is a tree spanned with function f from root a
reptree f a = node a map (reptree f) (f a)

gametree p = reptree moves p

redtree f a

redtree moves p 

moves position = listof position

reptree f a = node a (map (reptree f) (f a))

gametree p = reptree moves p

static position = number
e.g.  1   if position represents computer has won
     -1   if position represents computer has lost
      0   otherwise

max a b = a  if a>=b
          b  otherwise

maxlist = reduce max -Inf

maximize node n nil = n   # static evaluation
maximize node n subtrees = maxlist (map minimize subtrees)
minimize node n nil = n
minimize node n subtrees = minlist (map maximize subtrees)

prune 0 (node a x) = node a nil
prune n (node a x) = node a (map (prune n-1) x)

evaluate = maximize . maptree static . prune 5 . game tree

maximize = maxlist . maximize'
maximize' node n nil = cons n nil
maximize' node n list
    = map minimize list
    = map (minlist . minimize') list
    = map minlist map minimize' list
    = mapmin map minimize' list

mapmin cons nums rest
    = cons minlist nums minomit (minlist nums) rest

# find minimum of each list but skip the list if minimum <= pot
minomit pot nil = nil
minomit pot cons nums rest
    = minomit pot rest                         if minleq nums pot
      cons (minlist nums) minomit (minlist nums) rest    otherwise

# if minimum of list i less than or equal to pot
minleq nil pot = false
minleq (cons num rest) pot
    = true,              if num<=pot
      minleq rest pot,   otherwise

evaluate = maxlist . maximize' . maptree static . prune 8 . gametree

# arrange the order of subs, which is the list of subtrees 
highfirst (node n subs) = node n (sort higher (map lowfirst subs))

lowfirst (node n subs) = node n (sort (not higher) (map highfirst subs))
higher (node n1 subs1) (node n2 subs2) = n1 > n2

evaluate = maxlist . maximize' . highfirst . maptree static . prune 8 . gametree

>[name=煒甯]
> 1. **immutable 的概念**: 回歸到數學符號的精神，忘掉 von Neumann 的架構(用記憶體空間做運算)=>正確性跟 control flow 沒有關係
參考 [John Backus, Can Programming Be Liberated from the von Neumann Style?, 1977 Turing Award Lecture, ACM Comm 1978](http://worrydream.com/refs/Backus-CanProgrammingBeLiberated.pdf)
> 2. **模組化**:拆解與合成，要如何拆解程式，把程式中共通的部份抽象化出來，和程式語言以及程式設計典範 (programming paradigm) 中提供什麼樣的組合方法密切相關，在傳統的**命令式語言**中，多個函式是依照時序上 CPU 的控制移轉來組合的，一個工具函式將下層某些特定相關的功能寫在一起，提供上層程式來運用；**物件導向設計**中，不再以函式為重用的單位，而是以具有特定功能封裝良好的軟體物件作為下層重用的基本元件，但是也透過繼承和多型提供上層程序與系統的重用；**函數式程式語言**則透過函數合成 (function composition) 來組合 higher-order function 以及特化功能的函數，其中函數合成時的 lazy evaluation 機制使得更彈性的函式拆解方式得以實現。
>>* higher-order function: f(g(x))
>> * lazy evaluation:把產生序列變成一件事，檢查結束了變成一件事，例如牛頓逼近法、微分求斜率。
>> * functional: function of function(higher-order function) ex: Reduce(把共同的部分取出來)
>> function is data; data is function
>> Functional programming: 泛函編程

> [name=育靜]
> 用 Newton-Raphson algorithm for finding
square roots 為例子說明 lazy evaluation 特性:
> 假設今天要找 $\sqrt N$，首先會找到一個初始值 $a_0$，利用下列公式找到 $a_1、a_2...a_n、a_{n+1}$
> $a_{n+1}={(a_{n}+N/a_{n})\over2}$
> 當發現 $a_i$ 的值收斂，便可以知道 $a_i=\sqrt N$
> 原本 procedural 程式設計方法會存在一個變數 $a_{n+1}$ 透過不斷更新 $a_{n+1}$ 的值求出答案，functional programming 設計方法將產生 $a_{n+1}$ 的工作和檢查是否可以輸出答案，這兩件事情分開

# compute approximation from previous one
next N x = (x+N/x)/2
# next N is f(x)=a_{n+1}, x is a_n
# N is the value we want to find the square root

# generate the approximation list [a0, f a0, f(f a0), f(f(f a0)), ..]
repeat f a = cons a (repeat f (f a))
repeat (next N) a0

# square root finder
within eps (cons a(cons b rest)) = 
= b,                        if abs(a-b) <= eps
= within eps (cons b rest), otherwise

# putting the parts together
sqrt a0 eps N = within eps (repeat (next N) a0)

> 上面 repeat f a 會不斷產生 list 的元素，因此 repeat (next N) a0 會是一個無窮序列，在前面加上 within eps 檢查是否該停下來，如此一來就不需要把序列元素全部產生出來才能運算 (lazy evaluation 精神)
>
> 值得注意的是 functional programming 中我們不希望存在會不斷修改狀態的變數，因此絕對不會出現迴圈 (loop)，但是條件判斷的敘述 (if-else) 還是存在的
>
> 如此一來產生序列和檢查答案兩件事就可以分開，如果今天改成計算 $f(x)=x^2+5$ 的平方根，只需要換掉 f 的運算函數，或是檢查的條件想要修改成 $abs(a-b) <= eps*abs b$ 也是可以單獨做替換 :+1:

### 深度學習的框架 Keras/python 裡面常用到的 functional 概念

> 因為我們希望深度學習的訓練以及推理要能夠自動切割在平行化的 CUDA core 上面計算, functional 概念裡很多架構能夠讓編譯器自動分析出是否存在資料相依的關係, 沒有資料依存性的程式就可以分配給不同的執行單元去做，不需要考慮各種同步的問題。

###### generator