求講解下列鏈接以及pascal嵌套子程序是如何實現的?

子程序環境:嵌套子程序嵌套子程序


題主需要的是《Programming Language Pragmatics》這本書。或者《Concepts of Programming Languages》

問題里的鏈接就是基於兩者的講義,來自北京大學數學系的課程:程序設計語言 :: 程序設計語言原理 :: 裘宗燕 :: Programming Languages :: Principles of Programming Languages

原講義鏈接:http://www.math.pku.edu.cn/teachers/qiuzy/plan/slides/plan06-2.pdf

把書里相應章節反覆讀讀就好了,這兩本書對概念的講解都相當不錯。

例如說前者里的一張講解Pascal的嵌套函數的圖:

(點擊放大)

按照上圖對first-class, second-class和third-class值的定義方式,Pascal的嵌套函數是second-class的——可以作為參數傳給別的函數,但不能作為返回值或者存到任意變數里。

這種嵌套函數的實現比較容易,仍然可以基於一般的調用棧的實現,只要添加一個「靜態鏈」(static link)即可。

像C語言語義的調用棧,棧幀的典型實現方式可以抽象表述為:

previous frame | [ arguments ] | - incoming arguments
[ return address ] |
frame pointer -&> /[ saved frame pointer ] |
current frame | [ local variables ] |
| [ arguments ] | - outgoing arguments
stack pointer -&> [ return address ] v

圖中調用棧畫為向下增長。此刻表示的是當前棧幀對應的函數執行到正準備調用另外一個函數的時候——參數和返回地址都已經壓到棧上,而控制尚未轉移到被調用的函數一側。

這種畫法里,「當前棧幀」就是位於frame pointer與stack pointer所指位置之間的部分,從上到下依次包括:

  • 保存在棧上的,上一個棧幀的frame pointer值
  • 本棧幀所持有的局部變數
  • 準備傳遞給要調用的函數的參數
  • 準備傳遞給要調用的函數的返回地址

後兩項相對與本棧幀而言叫做傳出參數(outgoing arguments / outgoing parameters);相應的,上一個棧幀的傳出參數對下一個棧幀來說就是輸入參數(incoming arguments / incoming parameters)。

假設從上面的棧狀態繼續執行下去,進入到被調用的下一個函數里,在函數入口處要做的典型步驟是:

1、保存上一個棧幀的frame pointer,將其壓入棧頂:

older frame | [ arguments ] |
[ return address ] |
frame pointer -&> /[ saved frame pointer ] |
previous frame | [ local variables ] |
| [ arguments ] | - incoming arguments
[ return address ] |
stack pointer -&> /[ saved frame pointer ] v

(注意之前的「當前棧幀」現在的身份已經變成了「上一個棧幀」)

2、將frame pointer調整為指向當前棧幀的起始位置,將當前stack pointer值賦值給frame pointer:

older frame | [ arguments ] |
[ return address ] |
/[ saved frame pointer ] |
previous frame | [ local variables ] |
| [ arguments ] | - incoming arguments
[ return address ] |
frame pointer -&> /[ saved frame pointer ] v
stack pointer /

3、給新棧幀分配空間,調整stack pointer所指向的位置:

older frame | [ arguments ] |
[ return address ] |
/[ saved frame pointer ] |
previous frame | [ local variables ] |
| [ arguments ] | - incoming arguments
[ return address ] |
frame pointer -&> /[ saved frame pointer ] |
stack pointer -&>| [ local variables ] v

這種調用棧里,frame pointer把原本扁平的棧串成了一個鏈表:每個棧幀都在(相對於當前frame pointer的)固定位置記錄著上一個棧幀的frame pointer,於是順著這條鏈就可以從棧頂的棧幀一直遍歷到棧底的棧幀。

這種frame pointer叫做「動態鏈」(dynamic link)。動態鏈總是指向上一個棧幀。

要實現Pascal風格的嵌套函數,需要給棧幀添加一個靜態鏈。

與動態鏈不同,靜態鏈不一定總是指向上一個棧幀,而是可能指向更前面的棧幀。

在有嵌套函數的條件下,靜態鏈用於實現詞法(靜態)作用域需要向上尋找外圍詞法作用域對應的棧幀的需求。

用回前面引用的書里的例子,函數B嵌套在函數A里定義。調用到B時,調用棧的樣子是(向下增長的話):

frame for B |
frame for A | (遞歸調用A函數的棧幀)
frame for A |
frame for main v

每個棧幀的動態鏈都指向上一個棧幀,這個沒問題。

但是B的棧幀里存的靜態鏈指向的是前一個A的棧幀,而不是後一個A(圖中標識為A)的棧幀。

這是因為最終被調用的B函數,在後一個A里是通過參數P調用的,而參數P來自前一個A所引用的B函數。所以最終被調用的B函數的外圍環境應該是前一個A的,而前一個A的棧幀里參數I的值為1,所以這個B函數所捕獲到的、來自外圍環境的I的值就是1。

Pascal的嵌套函數比較受限,其活動記錄的生命周期不可能超過其捕獲的外圍環境的活動記錄,因而整體仍然可以用傳統調用棧的方式實現,只要像上面那樣加入靜態鏈。

GCC所支持的C語言擴展的嵌套函數跟Pascal的限制相似,實現方法也相似。

有興趣的可以看看GCC的文檔對此的描述:6.4 Nested Functions - GCC Internals,17.11 Trampolines for Nested Functions - GCC Internals


Free Pascal 的實現是把外層函數的棧幀地址作為第一個隱藏參數傳入內層函數。

譬如這樣的函數:

function IncOut(x : LongInt) : LongInt;
function IncIn(y : LongInt) : LongInt;
begin
exit(x+y);
end;
begin
exit(IncIn(1));
end;

編譯後的結果像是這樣的偽代碼:

function IncIn(pf : PFrameIncOut; y : LongInt) : LongInt;
// type PFrameIncOut = ^TFrameIncOut
// 此處 TFrameIncOut 為表示 IncOut 棧幀布局的虛構類型
// TFrameXXX 不同於真實變數,數據成員的偏移可以為負
begin
exit(pf^.x+y);
end;
function IncOut(x : LongInt) : LongInt;
begin
exit(IncIn(@FRAME, 1));
// 此處 FRAME 為指代 IncOut 棧幀的虛構變數,類型為上面的 TFrameIncOut
// 所有形參和非 const 局部變數都是屬於虛構變數 FRAME 的數據成員
// @FRAME 在 x86 上的實現一般為 bp/ebp/rbp
end;

多層嵌套的情況是內層只傳相對外一層的幀地址,等價於靜態鏈的方法。

=================

更新

多謝題主的資料提醒,我把 R 大介紹的那個東西在 FPC 的對應物寫出來了

{$modeswitch nestedprocvars}
program binding;

type
TNestedProcedure = procedure is nested;

procedure A(I : LongInt; PF : TNestedProcedure);

procedure B;
begin
writeln(I)
end;

begin
if I&>1 then
PF
else
A(2, @B)
end;

function GetC : TNestedProcedure;

procedure C; begin end;

begin exit(@C) end;

begin
A(1, GetC);
end.


推薦閱讀:

關於c前置,後置++,及函數傳參的問題?
已經不在學校了,在軟體專業上,該怎麼制定學習的策略?
國內哪一家公司的編譯隊伍技術最高?
typeid如何得出變數的類型?
最好的編譯器課程

TAG:編程 | 編譯原理 |