วันพุธที่ 24 ธันวาคม พ.ศ. 2551

basic lambda calculus - Part 1

basic definition ของ lambda calculus เหมือนเอาเรื่องเก่ามาเล่าใหม่

ตามความเห็นส่วนตัว เหมือน เรื่องฟังก์ชั่น ที่เปลี่ยน annotation เท่านั้นเอง

ดูตัวอย่างก่อน แล้วค่อยดู definition จะเข้าใจง่าย

Basic


- f(x) = x + 2 เขียนได้เป็น λ x. x + 2
เนื่องจากในฟังก์ชั่น อาจจะไม่ใช้ชื่อตัวแปรเป็น x ก็ได้ เช่น f(y) = y + 2 ดังนั้นเราอาจเขียนเป็น
λ y. y + 2;

- f(3) เขียนได้เป็น x. x + 2) 3 หรือ (λ x. x + 2)(3)

- มาดูพวกฟังก์ชั่นสองตัวแปรกันบ้าง f(x, y) = x - y เขียนได้เป็น λ x. λ y. x - y หรือจะเขียนย่อๆ ก็ได้ λ x y. x - y


- argument นอกจากจะเป็นตัวเลขแล้วยังสามารถส่งเป็นฟังก์ชั่น ได้ด้วย

เช่น λ f. f 3 รับพารามิเตอร์เป็นฟังก์ชั่น แล้วหา f(3)


ประโยคข้างล่างนี้เราส่ง f(x) = x + 2 เข้าไป

ทั้งสามประโยคนี้ เหมือนกัน

f. f 3) (λ x. x + 2)
x. x + 2) 3
3 + 2

------------------------

Definition

Lambda expressions ประกอบด้วย

ตัวแปร v1, v2, . . . vn
λ และ .
วงเล็บ ( )

ให้ Λ = เซตของ lambda expressions ซึ่งมีสมาชิกดังนี้

  1. ตัวแปร v ( v ∈ Λ )
  2. λ v . M เมื่อ v = ตัวแปร และ M ∈ Λ ( λ v . M ∈ Λ )
  3. M N เมื่อ M, N ∈ Λ ( M N ∈ Λ )
ข้อ 2 คือ abstractions
ข้อ 3 คือ applications

Notation
  • ไม่เขียนวงเล็บนอกสุด: เขียน M N แทนที่จะเขียน (M N)
  • left associative: M N P หมายความว่า (M N) P
  • body of abstraction extends as far right as possible: λ x . M N หมายถึง λ x . (M N) ไม่ใช่ (λ x . M) N
  • sequence of abstractions are contracted: λ x . λ y . λ z . N ย่อได้เป็น λ x y z . N

ref : en.wiki

ไม่มีความคิดเห็น:

LinkWithin

Related Posts Plugin for WordPress, Blogger...