หากเราดู code ของโปรแกรม เราอาจจะเห็นว่ามันเป็น คำสั่ง ตัวแปร ค่าคงที่ คลาส ออบเจค .. ลองนึกๆ ดูแล้ว สิ่งเหล่านี้เป็นแค่ ตัวเลข หรือ ตัวหนังสือ เท่านั้นเอง ..บางคนอาจจะว่ามันเป็นสายของตัวอักษรรหัส ASCII … ก็ OK ถือไม่ผิด.. แต่ถ้ามองลึกๆ อีกสักนิด..เราจะรู้ว่าที่จริงแล้วมันคือ “สัญญลักษณ์” อะไรบางอย่าง ที่แทนหรือสื่อถึงความหมายบางอย่าง หรืออาจจะเรียกได้ว่ามันบรรจุ information อยู่ข้างใน .. ถ้าเรามองทุกอย่างเป็นสัญญลักษณ์..งั้นคอมพิวเตอร์ที่แท้จริงแล้วก็คือตัว ประมวลผลสัญญลักษณ์นั่นเอง .. นี่อาจจะดูเป็น concept ไปหน่อย .. แต่ความสำคัญของมันอยู่ที่ว่า สัญญลักษณ์เหล่านี้มันทำงานได้ มันนำไปประมวลผลได้ ให้คำตอบกับเราได้ .. อืมมม.. ทำได้ยังไงกัน .. เรื่องนี้ต้องย้อนอดีตกันซักเล็กน้อย..
ย้อนไปช่วงที่ใกล้ๆ จะมีคอมพิวเตอร์เครื่องแรกเกิดขึ้นมาบนโลก นักคณิตศาสตร์ต่างสงสัยว่าอะไรเป็นตัวกำหนดว่าฟังก์ชัน หรือการประมวลผลเพื่อหาคำตอบๆ นึงสามารถทำได้จริง ทำไมมันถึงคำนวณได้ อะไรคือสิ่งที่คำนวณได้ อะไรที่คำนวณไม่ได้ และพื้นฐานที่สุดในการคำนวณคืออะไร .. ดูจะยากๆ ยังไงชอบกลนะครับ คิดอะไรกันก็ไม่รู้.. แต่สุดท้ายก็มีคำตอบออกมาจนได้ …หนึ่งในคำตอบนั้นคือ “Turing Machine” ของ Alan Turing ซึ่งเป็น Store-program computer ในอุดมคติ เขียนบนกระดาษนี่ล่ะครับ (ส่วน “Touring” Machine ของ Alan Turing เวลานั้นคือจักรยานครับ ว่ากันว่า Turing รักจักรยานเป็นชีวิตจิตใจ ^^”) .. เครื่องคอมพิวเตอร์เครื่องแรกที่นำทฤษฎีของ Turing Machine ไปใช้ก็คือ Von Neumann Machine ซึ่งเป็นต้นแบบของคอมพิวเตอร์ทุกเครื่องบนโลกนั่นเอง .. ไม่นานหลังจาก Alan Turing คิด Turing Machine ได้ เขาก็เสียชีวิต แต่ด้วยความที่ Turing Machine ถือเป็นก้าวสำคัญของวงการคอมพิวเตอร์ จึงมีการตั้ง Turing Award สำหรับผู้ที่ทำคุณประโยชน์ทางวิชาการคอมพิวเตอร์ .. Turing Award นี่ถือว่ามีศักดิ์ศรีเท่ากับรางวัลโนเบลเลยทีเดียว
นอกเหนือจาก Turing Machine แล้ว..อีกคำตอบนึงก็คือ “Lambda Calculus” … Lambda Calculus พัฒนาขึ้นมาโดย Alonzo Church ในปี 1941 ที่เรียกว่าเป็น calculus เพราะมันคือคณิตศาสตร์อันนึงเลยล่ะครับ สามารถพิสูจน์ย้อนกลับไปถึงคณิตศาสตร์พื้นฐานที่เราเรียนๆ อยู่ได้เลย .. ว่ากันว่าตัวที่เป็นแกนจริงๆ ของ “computing science” ที่เป็น pure science มีอยู่สามส่วนคือ Lambda Calculus, Combinatory Logic, และ Types (มีนักเรียนสาขาคอมพิวเตอร์ ซักกี่คนที่รู้จักสามตัวนี้ ??) ประมาณว่าเป็นก้าวแรกออกจากคณิตศาสตร์เข้ามาเป็นศาสตร์ทางคอมพิวเตอร์ .. ทั้งสามส่วนนี้สำคัญยิ่งกว่า full adder, half adder ที่วิศวกรอย่างเราเรียนด้วยซ้ำ เพราะงานทางวิศวกรรมเปลี่ยนแปลงได้เสมอ ต่อไปมันอาจจะไม่ใช่อิเล็กทรอนิกส์ก็ได้ แต่สิ่งที่ยังคงเหมือนเดิมก็คือ Lambda Calculus, Combinatory Logic, และ Types .. ที่จริงครั้งแรกที่ Church คิด Lambda Calculus ขึ้นมา ตั้งใจเอามาใช้เป็นพื้นฐานเกี่ยวกับการพิสูจน์ปัญหาทางคณิตศาสตร์ แต่กลับกลายเป็นว่าสิ่งที่ Church คิดนั้นก้าวหน้าจนเกิดสาขาทางตรรกศาสตร์อันนึงที่สำคัญมากสำหรับคอมพิวเตอร์ นั่นก็คือ Theory of Computation .. ประโยคนึงที่อธิบายความสำคัญของ Lamda Calculus ได้ดีมากก็คือ “Everything that can be computed can be computed by Lambda Calculus” – หากทฤษฎีระบุว่าการประมวลผลนั้นมีความเป็นไปได้ Lambda Calculus จะสามารถนำมาใช้ประมวลผลหาคำตอบได้อย่างแน่นอน .. ในทางกลับกัน Lambda Calculus ก็คือขีดจำกัดของการประมวลผลข้อมูลทุกอย่างในคอมพิวเตอร์ เพราะถ้า Lambda Calculus ประมวลผลไม่ได้ นั่นแสดงว่าคอมพิวเตอร์ประมวลผลข้อมูลนั้นไม่ได้เหมือนกัน
Pure Lambda Calculus
Pure Lambda Calculus มีไวยากรณ์หลักอยู่สามอันครับ คือ
..แค่ นี้ล่ะครับที่ทฤษฎีบอกว่าสามารถเขียนโปรแกรมได้หมดทุกโปรแกรม แปลกแต่จริงครับ อย่างที่บอกว่าทุกอย่างคือสัญญลักษณ์ และไวยากรณ์สามตัวนี้คือไวยากรณ์ที่ใช้ประมวลผลสัญญลักษณ์ โดยมีคณิตศาสตร์เป็นพื้น เอาล่ะครับเรามาดูกันทีละตัว นี่อาจจะลงรายละเอียดซักหน่อย แต่อยากให้ลองคิดตามครับ E คือ expression, v คือ variable
Assignment เป็นไวยากรณ์สำหรับกำหนดว่า expression E กับ v เป็นตัวเดียวกัน (ถ้าในคณิตศาสตร์ก็คือ E “มีค่าเท่ากับ” v แต่กรณีนี้มันเป็นสัญญลักษณ์ก็เลยไม่มีค่า ไม่รู้จะให้เท่ากับอะไร)
Application เป็นไวยากรณ์สำหรับที่บอกว่า apply expression E1 ด้วย expression E2 .. หาก (E1 E2) อยู่รูป Redex มันจะสามารถลดรูปลงเหลือ expression เดียวได้.. อืมม redex นี่หน้าตาเป็นอย่างนี้ครับ
โดยที่ทั้ง M และ N ก็คือ expression อันนึง.. ตามหลักใน Lambda Calculus redex สามารถลดรูปได้เป็น
หมายความ ว่าแทนที่ตัวแปร x ทั้งหมดที่อยู่ใน M ด้วย N .. การแทนที่ตัวแปรนี้เรียกว่า Beta reduction ครับ redex ถือว่าเป็นกลไกที่ทำให้เกิดการ execute โปรแกรมใน Lambda Calculus
Abstraction เป็นไวยากรณ์สำหรับระบุความหมายในเชิง abstract ของ expression E สมมติว่าเราจะหานิยามของ y := 2x+3 เราอยากรู้ว่ามันเกิดอะไรขึ้นกับ x ในเชิง abstract (หมายถึงไม่มีการคำนวณใดๆ ไม่มีการหาค่า เป็นเพียงสัญญลักษณ์อันนึง) เราอาจจะใช้ประโยค “เอ็กซ์คุณสอง บวกสาม” หรือในคณิตศาสตร์อาจจะเป็น f(x) := 2x + 3 .. แต่ในเชิง abstract ของ Lambda Calculus จะใช้ไวยากรณ์ Abstraction ครับ โดยเขียนเป็น
… ขั้นตอนนี้เรียกว่าเป็น Function Abstraction ถือว่ามีความสำคัญมากที่สุดก็ว่าได้ เพราะทุกๆ expression ใน Lambda Calculus ต้องเขียนในรูป abstraction ที่ถูกต้อง ไม่งั้นมันจะประมวลผลไม่ได้ ..
คราวนี้ลองคิดต่อว่าในเมื่อมันเป็นสัญญลักษณ์ที่แทนความหมายอะไรซักอย่าง ดังนั้นเราอาจจะแทน x ด้วยสัญญลักษณ์อื่นก็ได้ สมมติเป็นว่า
นะครับ อันนี้จะหมายความว่าเรากำลังจะแทนที่ x ด้วย a2 จะเห็นว่ามันเป็น redex พอดี และได้ผลของ beta reduction เป็น
(แทน x ด้วย a^2).. มาถึงตรงนี้หลายคนคงงง.. แล้วไงเหรอ ? มีแค่นี่แล้วทำอะไรได้.. OK งั้นเดี๋ยวเราลองมาดูตัวอย่างที่ work กว่านี้อีกซักหน่อยละกัน ถ้าคิดตามได้จะมันมาก ขอบอก ^^
เริ่มกันที่ประโยค if กับ true false นะครับ ข้างล่างนี่เป็น abstraction ของแต่ละอัน
เรามาลอง if true E1 E2 กันก่อน
ถ้าเป็น if false E1 E2 ล่ะ
หมายความ ว่าไงหนิ ?? if true ได้ผลเป็น E1 if false ได้ผลเป็น E2 ?? คุ้นๆ มั้ยครับ .. อืมมม… ใช่แล้วมันก็คือ if-then-else นั่นเอง รูปของมันจริงๆ ก็คือ if M E1 E2 ถ้า M เป็น true จะได้ผลเป็น E1 ถ้า M เป็น false จะได้ผลเป็น E2 .. สังเกตุเห็นอะไรมั้ยครับเห็นมั้ย .. ทั้งหมดนี่ ไม่มีค่า ไม่มีอะไรเลย ทั้งหมดเป็นเพียงสัญญลักษณ์ และเราแค่แทนที่สัญญลักษณ์ตามกฏ.. แต่มันกลับประมวลผลได้ และตีความได้ ลองดูเด็ดๆ อีกอัน อันนี้ยากขึ้นไปอีกหน่อย operator and เขียนได้เป็น
ลองดูว่า and true false จะเกิดอะไรขึ้น
ลองสลับที่ เป็น and false true
ถ้าเป็น and true true
บ๊ะ.. ถูกซะด้วย เป็นไงครับ (มึนไปเลย @_@) ..การประมวลผล ยังคงเป็นเพียงการแทนที่สัญญลักษณ์ตามกฏ แต่ประมวลผลได้อย่างถูกต้อง ที่จริงอยากทำบวกตัวเลขให้ดู แต่เดี๋ยวจะมึนกว่านี้ (^^”)
Functional Languages
ว่า กันว่า.. หากเราล้าง “เครื่องสำอางค์” ของภาษาคอมพิวเตอร์ต่างๆ ออกให้หมด สุดท้ายทุกภาษาจะมีหน้าตาเหมือนกัน..ซึ่งก็คือ Lambda Calculus นั่นเอง จากพื้นฐานการประมวลผลสัญลักษณ์นี้ล่ะครับที่ภายหลังก็กลายมาเป็นภาษา คอมพิวเตอร์ที่เรียกกันว่าเป็น Functional Languages .. อืมม.. ต้องเกริ่นซักนิด เราแบ่งภาษาคอมพิวเตอร์ออกเป็นสองประเภทนะครับคือ Functional Languages กับ Procedural หรือ Imperative Languages .. สองอันนี้ต่างกันที่จุดที่เป็นกลไกของภาษา กล่าวคือ Imperative Language เช่น C/C++, Pascal อย่างที่เราใช้กันจะเน้นที่การเปลี่ยนแปลงค่าในหน่วยความจำซึ่งเราทำกันโดย ตรงด้วย assignment statement ของภาษานั้นๆ .. โปรแกรมที่เขียนด้วย Imperative Language จึงดำเนินไปได้ด้วยการเปลี่ยนค่าในหน่วยความจำเป็นส่วนใหญ่ ทำให้เราต้องแปลงอัลกอริทึมมาเป็นคำสั่งในการจัดการตัวแปร ค่าคงที่ ฯลฯ ก่อน เพื่อให้โปรแกรมทำงานได้ตามต้องการ การแปลงอัลกอริทึมมาเป็นคำสั่งนี่เองที่ทำให้มีโอกาสที่จะเขียนโปรแกรมพลาด ไม่ตรงกับอัลกอริทึม แถมการทำอะไรกับหน่วยความจำโดยตรงก็เป็นสิ่งที่อันตราย ทุกคนคงเคยลืม initialize variable หรือเผลอสร้าง infinite loop เพราะลืมเปลี่ยน loop index variable ใช่มั้ยครับ.. เหตุการณ์เหล่านี้จะไม่เกิดถ้าเขียนโปรแกรมด้วย Functional Languages ครับ … Functional Languages ทุกๆ ภาษามีความใกล้ชิดกับ Lambda Calculus ค่อนข้างมาก ดังนั้นมันจึงมี concept คล้ายกับ Lambda Calculus คือเป็นการประมวลผลสัญญลักษณ์ จึงไม่ต้องกังวลเรื่องการจัดการหน่วยความจำ หรือเรื่องปลีกย่อยอื่น .. การเขียนโปรแกรมจึงสามารถเน้นไปที่อัลกอริทึมในการแก้ปัญหาได้โดยตรง
Functional Languages ที่ใกล้ชิดกับ Lambda Calculus มากที่สุด ก็คือภาษา LISP (List Processing) และ ML (Meta Language) ทั้งสองภาษานี่ใช้กันค่อนข้างแพร่หลาย ไม่น่าเชื่ออีกแล้วแต่ก็เป็นอย่างนั้นจริงๆ ครับ อย่าง ML นี่บริษัท Nortel, Motorola ก็ใช้พัฒนาซอฟต์แวร์ มีประสบการณ์ที่น่าสนใจหลายๆ อย่าง เพราะมันปลอดภัยมากกว่า C/C++ ส่วน LISP นั่นคนที่เรียน AI หนีไม่พ้นครับ หลายๆ คนที่ใช้ ML เป็นประจำจะชอบมันและบอกว่ามันดีกว่า C, Java เป็นไหนๆ แถมปลอดภัยกว่าด้วย นั่นเพราะตัวภาษามัน bug free ครับ ..
Functional Language ที่จะแนะนำให้รู้จักในวันนี้คือภาษา OCaml ครับ .. OCalm เป็นภาษาที่พัฒนามาจากภาษา Caml ซึ่งเป็น dialect ของภาษา ML อีกที .. ML/Caml/OCaml นิยมใช้ในการเรียนการสอนวิชา computer programming ในหลายมหาวิทยาลัยดังๆ เช่น MIT, Standford, Cornell, UPenn. และ UC เกือบทุก campus (UCLA, UC-Berkeley, UC-Davis, etc.) โดยเอามาสอนให้นักศึกษาสาขาคอมพิวเตอร์แทน Imperative Languages อย่าง Pascal .. ปัจจุบันมีงานวิจัยจำนวนมากที่ใช้ภาษา Caml ในการ implement เนื่องจากโปรแกรมจะแสดงถึง logic การทำงานของโปรแกรมได้ดีกว่า มั่นใจได้ว่าโปรแกรมจะตรงกับอัลกอริทึมที่ใช้แก้ปัญหาจริงๆ นอกจากนี้ความที่ภาษาตระกูล ML เป็นภาษาที่ใกล้กับ Lambda Calculus จึงมีการนำไปใช้ในทาง Formal Verification กันอย่างแพร่หลาย (Formal Verification เป็นการตรวจสอบการทำงานตามหลักเหตุผลด้วยคณิตศาสตร์) อย่าง Secure Socket Layer version 3 (SSLv3) protocol ก็ verify โดยใช้ภาษา ML เพื่อดูว่าการทำงานของ protocol สามารถรับรองความปลอดภัยได้จริงหรือไม่ OCaml ถูกพัฒนาที่ INRIA (The French National Institute of Research for Computer Science and Control) เป็นภาษาที่มีจุดเด่นที่ความเป็น Functional Language และสามารถ compile เป็น native binary และ bytecode ได้ เหมือนกับ Java (ทำ applet ก็ได้) จึงมี portability และ mobility สูง OCaml มีความสามารถด้าน object orientation เหมือน Java จึงใช้งานได้อย่างแพร่หลายพอๆ กับ Java เลยล่ะครับ รายละเอียดของ OCaml/Caml สามารถพบได้ที่ Caml Homepage ครับ .. ลองดาวน์โหลดมาใช้ดูแล้วจะรู้ว่าภาษา functional language มันดียังไง .. มีเวอร์ชันบน MS Windows ด้วย ตอนแรกอาจจะงงๆ เพราะภาษามันไม่เหมือน Pascal หรือ C เลยซักนิด แต่ถ้าเข้าใจหลักการจะพบว่า ML/Caml/OCaml เขียนโปรแกรมได้ง่ายมาก ใช้เวลาพัฒนาโปรแกรมน้อย ไม่มี bugs มากวนใจ แถมเอาหลักการในการเขียนโปรแกรมนี้ไปใช้ได้กับภาษาอย่าง LISP หรือ ADA ได้อีกเยอะเลย ลองเริ่มต้นได้ที่ Objective-Caml Tutorial มีเอกสารอธิบายการเขียนโปรแกรมขั้นต้นให้ดู .. ขอให้สนุกครับ ^^
References
- Kanchana Kanchanasut, Assoc. Prof., Foundation of Programming, Lecture notes, Asian Institute of Technology, May 1997.
- INRIA, Caml Homepage, http://caml.inria.fr
- Kitt Tientanopajai, Doctoral Student, Objective-Caml Tutorial, Lecture notes, Asian Institute of Technology, May 1999. URL: http://www.cs.ait.ac.th/~kitt