อุปกรณ์ของเจนเซ่น
อุปกรณ์ของ Jensenเป็นเทคนิคการเขียนโปรแกรมคอมพิวเตอร์ที่ใช้ประโยชน์จากการเรียกใช้ตามชื่อคิดค้นโดยนักวิทยาศาสตร์คอมพิวเตอร์ชาวเดนมาร์กJørn Jensenซึ่งทำงานร่วมกับPeter Naurที่Regnecentralenพวกเขาทำงานเกี่ยวกับคอมไพเลอร์ GIER ALGOLซึ่งเป็นหนึ่งในการใช้งานALGOL 60 ที่ถูกต้องในยุคแรกๆ ALGOL 60 ใช้การเรียกใช้ตามชื่อ[ 1 ] [ 2 ] [ 3 ]ในระหว่างสุนทรพจน์รับรางวัล Turing Award ของเขา Naur ได้กล่าวถึงงานของเขากับ Jensen ใน GIER ALGOL
คำอธิบาย
อุปกรณ์ของ Jensen ใช้ประโยชน์จากการเรียกใช้ฟังก์ชันโดยระบุชื่อ (call by name)และผลข้างเคียง (side effects ) การเรียกใช้ฟังก์ชันโดยระบุชื่อเป็นข้อกำหนดในการส่งผ่านอาร์กิวเมนต์ที่ชะลอการประเมินอาร์กิวเมนต์จนกว่าจะถูกนำไปใช้จริงในขั้นตอนการทำงาน ซึ่งเป็นผลมาจากกฎการคัดลอกสำหรับขั้นตอนการทำงาน ภาษา ALGOL ได้นำการเรียกใช้ฟังก์ชันโดยระบุชื่อมาใช้
ตัวอย่างคลาสสิกของอุปกรณ์ของเจนเซ่นคือขั้นตอนการคำนวณผลรวมของอนุกรม: [ 4 ] [ 5 ] [ 6 ]
ขั้นตอนการคำนวณค่าจริง Sum(k, l, u, ak) ค่า l, u; จำนวนเต็ม k, l, u; จำนวนจริง ak; หมายเหตุ k และ ak ถูกส่งผ่านโดยชื่อ; เริ่มต้นจำนวนจริง s; s := 0; สำหรับ k := l ขั้นตอนที่ 1 จนกว่าคุณจะ ทำ s := s + ak; ผลรวม := s จบ ;
ในขั้นตอนการทำงาน ตัวแปรดัชนีkและเทอมผลรวมakจะถูกส่งผ่านโดยใช้ชื่อ การเรียกใช้โดยใช้ชื่อช่วยให้ขั้นตอนการทำงานสามารถเปลี่ยนค่าของตัวแปรดัชนีได้ในระหว่างการทำงานของforลูป นอกจากนี้ การเรียกใช้โดยใช้ชื่อยังทำให้akค่าอาร์กิวเมนต์ถูกประเมินใหม่ในแต่ละรอบของลูป โดยทั่วไปแล้วakจะขึ้นอยู่กับการเปลี่ยนแปลง (ผลข้างเคียงk)
ตัวอย่างเช่น โค้ดสำหรับคำนวณผลรวมของ 100 พจน์แรกของอาร์เรย์จำนวนจริงV[]จะเป็นดังนี้:
ผลรวม(i, 1, 100, V[i])
ในระหว่างการดำเนินการSumอาร์กิวเมนต์จริงiจะเพิ่มขึ้นในแต่ละขั้นตอนของforลูป และการประเมินค่าของในแต่ละขั้นตอนakจะใช้ค่าปัจจุบันของiเพื่อเข้าถึงองค์ประกอบอาร์เรย์ถัดV[i]ไป
วิธีการของเจนเซ่นเป็นแบบทั่วไป การรวมสองชั้นสามารถทำได้ดังนี้:
ผลรวม(i, l, m, ผลรวม(j, l, n, A[i,j]))
สามารถใช้ฟังก์ชัน นี้Sumกับฟังก์ชันใดๆ ก็ได้ เพียงแค่ใช้นิพจน์ที่เหมาะสม หากต้องการผลรวมของจำนวนเต็ม นิพจน์ก็จะเป็นSum(i,1,100,i);ถ้าผลรวมของกำลังสองของจำนวนเต็ม ก็จะเป็นSum(i,1,100,i*i);และอื่นๆ[ 7 ]การเปลี่ยนแปลงเล็กน้อยจะเหมาะสมสำหรับการเริ่มต้นการอินทิเกรตเชิงตัวเลขของนิพจน์ด้วยวิธีการที่คล้ายคลึงกับSumของ
การประเมินค่าของฟังก์ชันนั้นakดำเนินการโดยใช้thunkซึ่งโดยพื้นฐานแล้วเป็นซับรูทีนที่มีสภาพแวดล้อม thunk เป็นโคลเชอร์ที่ไม่มีอาร์กิวเมนต์ ทุกครั้งที่โปรซีเดอร์ต้องการค่าของอาร์กิวเมนต์อย่างเป็นทางการ ก็เพียงแค่เรียก thunk thunk จะประเมินค่าอาร์กิวเมนต์จริงในขอบเขตของโค้ดที่เรียก (ไม่ใช่ขอบเขตของโปรซีเดอร์)
หากไม่มีฟังก์ชันการส่งผ่านชื่อโดยตรง จำเป็นต้องกำหนดฟังก์ชันที่รวบรวมนิพจน์ที่จะส่งผ่านตามโปรโตคอลของภาษาคอมพิวเตอร์ หรือสร้างฟังก์ชันรวบรวมข้อมูลพร้อมกับกลไกบางอย่างเพื่อเลือกนิพจน์ที่ต้องการสำหรับการใช้งานแต่ละครั้ง
จีเอส
อีกตัวอย่างหนึ่งคือ GPS (General Problem Solver) ซึ่งอธิบายไว้ในALGOL 60 confidentialของ DE Knuth และ JN Merner [ 8 ]
ขั้นตอนจริง GPS(I, N, Z, V); จริง I, N, Z, V; เริ่มต้นสำหรับ I := 1 ก้าวที่ 1 จนถึง N ทำ Z := V; GPS := 1 สิ้นสุด ;
ต่อไปนี้เป็นคำสั่งเดียวที่ใช้ค้นหาจำนวนเฉพาะลำดับที่ m โดยใช้ GPS
I := GPS(I, ถ้า I=0 แล้ว -1.0 มิฉะนั้น I, P, ถ้า I=1 แล้ว 1.0 มิฉะนั้นถ้า GPS(A, I, Z, ถ้า A=1 แล้ว 1.0 มิฉะนั้นถ้า entier(A)×(entier(I)÷entier(A))=entier(I) ∧ A<I แล้ว 0.0 มิฉะนั้น Z) = Z แล้ว ( ถ้า P<m แล้ว P+1 มิฉะนั้น I×GPS(A, 1.0, I, -1.0)) มิฉะนั้น P)
(หมายเหตุ: ในเอกสารต้นฉบับ นิพจน์ที่อยู่ใกล้ตอนท้ายคือGPS(A, 1.0. I, 0.0)เนื่องจากเป็นกรณีพิเศษในข้อกำหนดความหมายของ คำสั่ง for ใน ALGOL 60 )
การวิจารณ์
อุปกรณ์ของ Jensen อาศัยการเรียกตามชื่อ แต่การเรียกตามชื่อนั้นซับซ้อนและมีปัญหาอยู่บ้าง ดังนั้น การเรียกตามชื่อจึงไม่สามารถใช้งานได้ในภาษาส่วนใหญ่ Knuth แสดงความคิดเห็นว่า ALGOL 60 ไม่สามารถแสดงincrement(n)ขั้นตอนที่เพิ่มอาร์กิวเมนต์ขึ้นหนึ่งได้ การเรียกincrement(A[i])จะไม่ดำเนินการตามที่คาดหวังหากiเป็นฟังก์ชันที่เปลี่ยนแปลงทุกครั้งที่เข้าถึง[ 9 ] Knuth กล่าวว่า "การใช้สิ่งอำนวยความสะดวกในการกำหนด 'มาโคร' เพื่อขยายภาษา แทนที่จะพึ่งพาขั้นตอนเพียงอย่างเดียวเพื่อจุดประสงค์นี้ ส่งผลให้โปรแกรมทำงานได้น่าพอใจยิ่งขึ้น"
คนอื่นๆ ชี้ให้เห็นว่าขั้นตอนการเรียกตามชื่อที่สลับอาร์กิวเมนต์อาจมีปัญหาเล็กน้อย[ 10 ]ขั้นตอนการสลับที่ชัดเจนคือ:
ขั้นตอนสลับค่า a, b จำนวนเต็ม a, b; เริ่มต้นจำนวนเต็มชั่วคราว; อุณหภูมิ := a; a := b; b := อุณหภูมิ; จบ ;
ขั้นตอนดังกล่าวทำสิ่งที่ถูกต้องสำหรับข้อโต้แย้งหลายประการ แต่การเรียกใช้นั้นswap(i,A[i])มีปัญหา การใช้กฎการคัดลอกนำไปสู่การกำหนดค่าดังนี้:
temp := i; i := A[i]; A[i] := temp;
ปัญหาคือการกำหนดค่าครั้งที่สองมีการเปลี่ยนแปลงiดังนั้นค่าA[i]ในการกำหนดค่าครั้งที่สามจึงอาจไม่ใช่ค่าเดียวกันกับองค์ประกอบในอาร์เรย์ตอนเริ่มต้น ในทางกลับกัน หากเขียนโค้ดขั้นตอนการทำงานในทางกลับกัน (โดยบันทึกค่าb ลงใน ตัวแปรชั่วคราวแทนที่จะเป็นa ) การกระทำที่ต้องการก็จะเกิดขึ้น เว้นแต่จะเรียกใช้ในลักษณะswap(A[i],i). (วิธีที่ปลอดภัยกว่าswap()คือ.)temp1 := a; temp2 := b; a := temp2; b := temp1;
ดูเพิ่มเติม
- สแต็กการเรียก , เฟรมสแต็ก, ลิงก์คงที่ และการแสดงผล (โคลเชอร์รวมถึงลิงก์สภาพแวดล้อม)
- อุปกรณ์ของดัฟฟ์
- ปัญหาของ Funargคือวิธีการส่งและรับฟังก์ชันเป็นค่า
- การทดสอบผู้ชายหรือเด็กชายการทดสอบด้านสิ่งแวดล้อม
ลิงก์ภายนอก
- ความหมายมาตรฐานที่ไม่ต้องเก็บข้อมูลสำหรับโครงสร้างบล็อกแบบ ALGOL และการเรียกใช้ตามชื่อ