呼叫堆疊

呼叫堆疊（英語：Call stack，中國大陸稱調用堆棧）別稱有：執行堆疊（execution stack）、控制堆疊（control stack）、執行時堆疊（run-time stack）與機器堆疊（machine stack），是電腦科學中儲存有關正在執行的子程式的訊息的堆疊。英文有時直接簡稱「堆疊」（the stack），但堆疊中不一定僅儲存子程式訊息。幾乎所有電腦程式都依賴於呼叫堆疊，而高階語言一般將呼叫堆疊的細節隱藏至後台。

呼叫堆疊最經常被用於存放子程式的返回位址。在呼叫任何子程式時，主程式都必須暫存子程式執行完畢後應該返回到的位址。因此，如果被呼叫的子程式還要呼叫其他的子程式，其自身的返回位址就必須存入呼叫堆疊，在其自身執行完畢後再行取回。在遞迴程式中，每一層次遞迴都必須在呼叫堆疊上增加一條位址，因此如果程式出現無限遞迴（或僅僅是過多的遞迴層次），呼叫堆疊就會產生堆疊溢位。

功能

主條目：基於堆疊的主記憶體分配

呼叫堆疊的主要功能是存放返回位址。除此之外，呼叫堆疊還用於存放：

• 局部數據儲存：子程式的本地變數可以存入呼叫堆疊，這樣可以達到不同子程式間變數分離開的作用。
• 參數傳遞：如果暫存器不足以容納子程式的參數，可以在呼叫堆疊上存入參數。
• 包圍子程式上下文：有些語言（如Pascal與Ada）支援巢狀子程式（英語：Nested function），即子程式中可以利用包圍子程式的本地變數，亦稱其為非本地變數（英語：Non-local variable）。這些變數可以通過呼叫堆疊鏈結入子程式。

結構

呼叫堆疊由堆疊框（stack frame）組成，它們也叫做「活動記錄」或「活動訊框」。它們是機器依賴（英語：Machine-dependent software）並且ABI依賴的資料結構，包含了次常式狀態資訊。每個堆疊框對應於一個次常式的仍未通過返回來完成的一次呼叫^[1]。在堆疊頂部的堆疊框對應當前執行常式。例如，一個叫做DrawLine的次常式當前正在執行，它被次常式DrawSquare所呼叫，右側圖示中給出了呼叫堆疊的頂部狀況。

堆疊解繞

麵條式堆疊，突出顯示了「活躍」堆疊框。

從被呼叫函式返回會彈出堆疊的頂部訊框，並可能留下返回的一個值。更一般性的動作是從堆疊彈出一個或多個訊框，從而恢復在程式中其它某處的執行，這叫做堆疊解繞（unwind），並且在使用了非局部控制結構的時候必須進行，比如例外處理。在這種情況下，一個函式的堆疊框包含了指定例外處理器的一個或多個入口（entry）。在一個例外被丟擲的時候，堆疊被解繞直到找到了準備處理（接住）這個丟擲例外類型的一個處理器。

一些語言有要求一般性解繞的其他控制結構。Pascal允許使用全域性的goto語句，將控制從巢狀的函式傳送出來並進入此前呼叫的外面的函式。這個操作要求堆疊被解繞，為了恢復正確的上下文，從而將控制傳送給包圍它的外面函式中的目標語句，需要移除多少堆疊框就移除多少。與之類似，C語言有setjmp與longjmp函式充當非局部跳轉，它們分別儲存和恢復：堆疊指標、程式計數器、被呼叫者儲存的暫存器和ABI要求的任何其他內部狀態。

Common Lisp允許通過使用unwind-protect特殊算子，控制在堆疊被解繞時都要做些什麼。在支援續體的程式語言比如Scheme和新澤西Standard ML中，在應用續體的時候，堆疊（在邏輯上）被解繞並重繞（rewind）上這個續體的堆疊，接著盤繞（wind）上要傳遞的那一個值。Scheme語言提供了對續體呼叫進行「保護」的dynamic-wind，只要控制離開或進入它所界定範圍，包括通過應用續體這種非局部跳轉方式，在分別對控制堆疊「解繞」或「重繞」的特定點上，都會執行任意的thunk（英語：thunk）。

解繞並重饒不是實現續體的唯一方式，例如通過使用多個顯式的堆疊，應用一個續體可以簡單的停用或捨棄當前堆疊並啟用這個續體的堆疊。在支援續體的程式語言和執行堆疊可以在執行時檢查並修改的程式語言比如Smalltalk和Cilk中，由這些堆疊連結起來而實現的實際執行堆疊被稱為麵條式堆疊（英語：Parent pointer tree）^[2]，它包含了變數繫結和其他環境特徵。在必須支援續體的時候，一個函式的局部變數在這個函式返回時不能被銷毀：一個儲存了的續體可以在往後時重入（re-enter）這個函式，並且不僅期望其中的變數不變動，而且期望整個堆疊都存在使得這個函式能再次返回。要解決這個問題，堆疊框可以在麵條式堆疊結構中動態分配，並在不再有續體參照的時候，將其留作垃圾回收。這種類型的結構還解決了上行和下行的函式參數問題（英語：funarg problem），因為在這種基底上很容易實現頭等詞法閉包。

安全性

主條目：堆疊緩衝區溢位

在較底層語言（如組合語言與C語言中），程式控制訊息與資料可能一同被存入呼叫堆疊中，因此造成安全隱患，可能允許惡意程式通過堆疊緩衝區溢位（stack buffer overflow）來獲取程式的控制權。

參見

• 記憶體管理
• 堆疊溢位
• 呼叫約定
• 協程
• 負載 (計算)（英語：Overhead (computing)）
• 麵條式堆疊（英語：Parent pointer tree）
• 基於堆疊的主記憶體分配
• 堆疊結構機器
• 堆疊追蹤