เรียนรู้ Clojure ตอน tail recusive

recursive คือหัวใจหลักของภาษาตระกูล functional, ตัว runtime ของภาษาตระกูลนี้ต้องออกแบบมาให้สามารถทำ optimize tail recursive เพื่อหลีกเลี่ยง stack overflow. โชคร้ายที่ jvm ไม่ได้ออกแบบมาเพื่อทำ optimize แบบนั้น (ยกเว้น IBM JVM - Java กับ Tail-Recursive)
เจ้า closure ก็เลยต้องอาศัย syntax พิเศษเพื่อเลียนการทำงานแบบ tail recursive

ลองดูตัวอย่าง code จริง

(defn render-level-layer
  "my, what an insane level representation i have here"
  [target items if-empty if-full]
  (loop [target target
         remain (seq items)]
    (if remain
      (let [x (:x (first remain))
            y (:y (first remain))
            i (level-index x y)
            at (target i)]
        (recur (assoc target i (if (= at \space) if-empty if-full))
               (rest remain)))
      target)))

keyword จะอยู่ที่ loop กับ recur นี่แหล่ะ
loop เป็น syntax แบบเดียวกับ let แต่มันจะกำหนดจุดที่จะเกิดการ recursion
ส่วน recur เป็นการสั่งให้กระโดดกลับไปทำงานที่ loop อีกครั้ง แต่จะมีการเปลี่ยน binding ของตัวแปรที่กำหนดไว้ตอนประกาศ loop

ลองดูตัวอย่างข้างล่าง ซึ่งเป็นการหาค่า factorial โดยใช้วิธี recursive แบบ pass ค่า accumulator
จะเห็นว่าที่ตำแหน่ง loop มีการกำหนด binding ตัวแปร cnt กับ acc
ดังนั้นเมื่อถึงตอนสั่ง recur ก็จะต้องส่ง parameter ที่จะเป็นค่าใหม่ของ cnt และ acc กลับมาด้วย

(def factorial
  (fn [n]
    (loop [cnt n 
           acc 1]
       (if (zero? cnt)
            acc
          (recur (dec cnt) (* acc cnt))))))

เปรียบเทียบกับการเขียนแบบ recursive ใน clisp ก็จะเป็นแบบนี้

(defun factorial (n &optional (acc 1))
   (if (<= n 1)
       acc
       (factorial (- n 1) (* acc n))))

หลังจากที่ Clojure ออกมา ก็มีคนถามประเด็น mutual recursive ว่าจะเขียนอย่างไร
ลองดูตัวอย่าง mutual recursive ก่อน

(declare bar) 

(defn foo [n] 
  (if (pos? n) 
    (bar (dec n)) 
    :done-foo)) 

(defn bar [n] 
  (if (pos? n) 
    (foo (dec n)) 
    :done-bar)) 

(foo 1000000) 
-> java.lang.StackOverflowError 

Note: code แบบข้างบนนี้ ถ้าไปเขียนใน clisp จะ run ได้โดย stack ไม่ overflow

Rich Hickey ก็เลยแก้ code ของ clojure โดยใช้ technique ที่เรียกว่า trampoline

instead of actually making a call in the tail, a function returns the function to be called, and a controlling loop calls it

syntax ของ foo bar ข้างบนก็เลยต้องเขียนแบบนี้แทน

(declare bar) 

(defn foo [n] 
  (if (pos? n) 
    #(bar (dec n)) 
    :done-foo)) 

(defn bar [n] 
  (if (pos? n) 
    #(foo (dec n)) 
    :done-bar))