Friday, September 22, 2006

Java กับ Tail-Recursive

คุณสมบัติอย่างหนึ่ง ของภาษาคอมพิวเตอร์ในตระกูล Functional language (lisp, haskell, erlang)
ก็คือ ต้องสามารถ optimize tail-recursive ได้
โดยการ call แบบนี้ จะไม่มีการใช้ stack
เพื่อป้องกันการเกิดปัญหา stack overflow
(เนื่องจาก nature ของ Functional Language
มันส่งเสริมให้ใช้ recursive)

พึ่งรู้ว่า IBM JRE สามารถทำ optimize tail-recursive ได้เหมือนกัน
โดยทำ ณ ขณะ runtime (ไม่ได้ทำตอน compile)
ทดลองเขียนโปรแกรมทดสอบง่ายๆดู
public class TestRecursive {

public int run(int i) {
return run(i);
}

public static void main(String[] args) {
new TestRecursive().run(10);
}

}

ทดลอง run ใน jre ของ IBM มันจะ run ไปเรื่อยๆไม่รู้จบ
แต่ถ้าเป็นเจ้าอื่น จะเกิด Stack overflow ในพริบตา

เท่าที่ทดลองดู ยังเห็นแค่มี jre (1.4) ของ IBM เท่านั้นที่ทำได้
ของ Sun (1.5), BEA (1.4), Mac (1.5) ทำแบบนี้ไม่ได้

Related link from Roti

4 comments:

bact' said...

ลองค้นต่อ เจออันนี้

http://www-128.ibm.com/developerworks/java/library/j-diag8.html

แบบนี้นี่ จะมีผลกระทบต่อการพยายามใช้ภาษาตระกูลนั้น บน JVM รึเปล่า ?

แล้ว .NET CLR เป็นยังไงบ้าง ?

bact' said...

ลองโค้ด(เกือบจะ)เดียวกัน ด้วย C# บน .NET 2.0
(ใช้ SharpDevelop)

ตายเหมือนกัน

Exception System.StackOverflowException was thrown in debuggee:
<null reference>

bact' said...

(เปลี่ยนแค่ main เป็น Main
กะ String เป็น string :P)

polawat phetra said...

ตอน bact' ตั้งคำถาม
ก็ตั้งท่าว่าจะหาเครื่องลองอยู่เหมือนกัน

ตอนแรกที่ผมเดา ว่าคิดว่า CLR น่าจะทำ optimize tail recursive ได้นะ
เพราะมี feature ใหม่ๆของ C# หลายตัวที่มี
แนวโน้มไปทาง functional language

ไว้รอ test กับ C# version ถัดไป

Note: เปลี่ยนแค่ main->Main, String->string,
หึๆ ง่ายกว่าที่คิดไว้เยอะแฮะ