宣告式編程風味模型化指令式編程程式碼 - 陳立凡

我真的想不太到適當的標題 QQ，不用太在意上面那個標題 (?)

在這場議程中，我會分享我於去年專研課所做的研究。研究中我用一些方式，在 Functional Programming 的框架下嚴格定義了日常我們看到的一些語法的行為，例如變數指定、if else、for loop 等。 我會盡量使用平易近人的方式講解，讓先備知識降到最低。

先備知識

必備： 對程式語言有基礎了解者 (知道條件判斷、迴圈等)

有很好，沒有也沒關係：接觸過程式語言理論相關者

tags: SITCON 2020 共筆 SITCON 2020 2020 共筆 R3

請從這裡開始

About me

telegram、FB、IG - koru1130

研究背景

• 班上原來要做專研
• 將 IP 轉換成 FP
• 原本想投科展
• 剛好遇到 CFP

Programing Paradigm

• Imperative
• Declarative

IP 與 FP

• Imperative
  • 由指令所構成
  • statement
  • 有狀態
  • 變數可變
• Functional
  • 由函數所構成
  • expression
  • 無狀態
  • 變數不可變

Syntax & Semantic

• Syntax 語法
• Semantic 語義
  • 雙方括號
  • [_]

BNF

一種表示語法的方式
<symbol>::expression
<symbol>

<digit> ::= 1|2|3|4|5|6|7|8|9|0
<number>::=<digit>|<number><digit>
- 3
- 42
<expr>::=<number>
<expr>+<expr>
<expr>-<expr>
15 1符合number5符合digit

Function type

• 參數 -> 函數值
• int add1(int x){…}
• add1: int -> int
  第一個參數->第二個參數->函數值

max: int -> int -> int
max: int -> (int -> int)

對 IP 的另一種想像

S1: a <- 1
S2: b <- 2
S3: a <- a+b

S3(S2(S1(st)))

P:=O|S;P
P 遞迴

[[_]] Statement ->(State ->State)
[[O]] st=st
[[S;P]] st = ([[S]]。[[P]]) st

Evaluate

e:=v|a|f(e,e…e)
v 值
a 變數
f(e,e…e) 函數呼叫
E:(Expression, State) -> Value
E(v, st) = v
E(a, st) = get a st
E(f(e0, e1 … en), st) = f(E(e1, st), E(e2,st) … , E(en, st))

st =

get : Name -> State -> Value
get owo st = 3

Variable assignment

S := a <- e
[[a <- e]] st = set a E(e, st) st

state

set : name -> value

if statement

s := if e then s else s
ifte(true,e1,e2) = e1
ifte(false, e1, e2) = e2

[[if c then s1 else s2]] st
= ifte(E(c, st), [[s1]], [[s2]]) st

for lop statement

[[for i in ls do s]] st
= (foldl(λf.x.([[s[i:=x]]])))

fold function

fold : (a -> b -> a) ->a -> [b] -> a
fold fz[1,2,3,4,5]

fold (+) 0 [1,2,3,4,5]
= ((((0 + 1) + 2) + 3) + 4) + 5

[[for i in ls do s]] st
= (fold _z ls) st

z = id
_ = λf . x . ([[s[i := x]]] 。 f)

for i in ls do
a <- a + i

[[for i in ls do a <- g(a, i)]] st
= [[a <- (foldl g a xs)]] st

f(foldl g a xs) = foldl h b xs
<= (f a=b) ^ (f (g x y) = h(f x)y)

proof of theorem 2:

reference

Q&A

為什麼變數不可變
和一般語言有變數的概念不同，function 沒有變數的概念，不能更改它
所以 function programming 什麼時候會用到呢？ 有什麼適合的程式語言支持嗎？
React is function programming
Haskell is function programming
為什麼會想到用 functional model imperative
oop 也可以用 functional 遞迴啊
變數不可變 -> 只能遍歷 array 取值而已
他的概念是有點像 lisp 類型的語言嗎？
Haskell 有什麽缺陷嗎？
io 複雜
可以介紹你個人學習資訊的經歷嗎？

wiki

推坑 Haskell X)

flolac 邏輯 語言與計算暑期研習營
偶數年 functional
奇數年 …