迴圈轉遞迴（稿）-文字檔

導航：首頁 > 程式語言、邏輯學> 迴圈轉遞迴（稿）-文字檔

使用Typst撰寫，生成PDF檔。

#import "algo.typ" : *


#set par(
  justify: true,
  leading: 1em,
)

#let CJKNonCJKSpacing = 0.2em

#let RegExCJK = "[\p{Han}\p{Hiragana}\p{Katakana}\p{Hangul}\p{Bopomofo}]"
#let RegExNonCJK = "[^\p{Han}\p{Hiragana}\p{Katakana}\p{Hangul}\p{Bopomofo}]"

#let RegExNonCJK = "[^\p{Han}\p{Hiragana}\p{Katakana}\p{Hangul}\p{Bopomofo}]"


#show regex(RegExCJK+RegExNonCJK) : it => {
    text[#it.text.first()#box(width: CJKNonCJKSpacing,"")#it.text.last()]
}

#show regex(RegExNonCJK+RegExCJK) : it => {
    text[#it.text.first()#box(width: CJKNonCJKSpacing,"")#it.text.last()]
}

#set page(
  numbering: "1 / 1",
)

#set text(
    size: 12pt,
    font: ("Linux Libertine", "Noto Serif CJK TC"),// "Linux Libertine Mono O"
    )

#let hd1(txt) = box[
    #set text(
    font: ("FreeSans", "Noto Sans CJK TC"),// "Linux Libertine Mono O"
    )
    = #txt ]

#let hd2(txt) = box[
    #set text(
    font: ("FreeSans", "Noto Sans CJK TC"),// "Linux Libertine Mono O"
    )
    == #txt ]
#let remark(txt, number) = box(width:100%,
fill: rgb("#EBFAEF"), [
#v(1em)
#align(center,[#txt~~#sub([[#number]])])
#v(1em)])

#hd1("迴圈轉遞迴（稿）")

_2022-07-20 by Yoxem_

迴圈和遞迴其實習習相關，最近略讀論文 _Transforming Programs into Recursive Functions_ (Myreen & Gordon, 2008)，提到迴圈如何轉換成遞迴的方法。我在這邊想到一些思路。

一個迴圈可以理解為條件(cond)和滿足條件即執行的程式本體(body)，即：
```python 
while (cond):
    body
```

其中一些while外的變數，被body處理之後，在body的最後就會變。假設輸入到body改變數值的變數為$x_i space (i=0, 1,dots)$，輸出的結果是$x^prime_i$，那我們可以假設$bold(accent(x,->))$是$x_i$組成的向量，$bold(accent(x,->)^prime)$是是$x^prime_i$組成的向量，則body可以視為函數，且$bold(accent(x,->)^prime) = "body"(bold(accent(x,->)))$。

舉下列求除法商數的$"Quotient"(a, b) = a$除以$b$的商數"為例，為求簡化，$a, b$均為自然數：

#link("Transforming Programs into Recursive Functions")[http://1111.com]

#algo(
  title: "Quotient",
  parameters: ("a","b"),
  strong-keywords: true     // display keywords in bold
)[
  let q = 0 #comment[商數] \ 
  while $a gt.eq b$:#i#comment[cond]\            // 
    $a <- a - b$ #comment[body的第1行]\       
    $ q <- q + 1$ #comment[body的第2行]:#d\
return q
]

其中 $a, b$ 和 $q$ 是body外的變數，$"body"(a, b, q)$ $= (a-b, b, q+1)$，比較下，$bold(accent(x,->)) = (a, b, q)$，$bold(accent(x,->)^prime) = (a-b, b, q+1)$然後可以把`while(cond){body}`組合$bold(accent(x,->))$想成這樣的OCaml函數：

```ML
(* 以下括號非必要則略 *)
WHILE cond body XVec= 
if cond then
    let NewXVec = body XVec in (* NewXVec = body XVec *)
    WHILE cond body NewXVec (* 帶 NewXVec 重新進去WHILE函數，做if判斷的手續 *)
else
    XVec (* XVec 不變 *)
    
    
```

另可以這樣改寫，其中cond視為輸入$bold(accent(x,->))$的函數：

```ML
let WHILE cond body XVec =
if (cond XVec)  then
  WHILE cond (body XVec)
else
  XVec
```

那麼這個除法可以這樣寫成類OCaml風格：

```ML
……

let q = 0 in
(*原樣*)
while a >= b do
    let a = a - b
    let q = q + 1

```
但是要找出while外變數，可以找出a, b, q，且把狀態更新改為 let…in 模式，則
```ML
……

let q = 0 in

let cond = fun a b q -> a >= b in
WHILE cond
      (fun a b q ->(
         let a = b - a in 
         let q = q + 1 in
          (WHILE cond [a; b; q] )))
    a b q (* XVec*)
```

用let的規約規則轉換一下變成尾遞迴

```ML
……

let q = 0 in

let cond = fun a b q -> a >= b in
WHILE cond
      (fun a b q ->(
          (WHILE cond [b - a; b; q + 1] )))
    a, b, q
```

最後修改：

```ML
……

let cond = fun a b q -> a >= b in
letrec WHILE cond  =
   (if (cond X) then
   (WHILE cond (b - a) b (q + 1))
   else
   [a; b; q]) in
WHILE cond a b q (* 執行 LOOP *)
```