Trong lập trình máy tính, hàm lồng nhau [hoặc thủ tục lồng nhau hoặc chương trình con] là một hàm được định nghĩa bên trong một hàm khác, hàm kèm theo. Do các quy tắc phạm vi đệ quy đơn giản, một hàm lồng nhau tự nó ẩn bên ngoài hàm kèm theo ngay lập tức của nó, nhưng có thể thấy [truy cập] tất cả các đối tượng cục bộ [dữ liệu, hàm, loại, v.v. ] của chức năng kèm theo ngay lập tức của nó cũng như của bất kỳ [các] chức năng nào bao hàm chức năng đó. Việc lồng ghép về mặt lý thuyết có thể thực hiện được với độ sâu không giới hạn, mặc dù chỉ có một số mức độ thường được sử dụng trong các chương trình thực tế
Các hàm lồng nhau được sử dụng trong nhiều cách tiếp cận lập trình có cấu trúc, bao gồm cả những cách tiếp cận ban đầu, chẳng hạn như ALGOL, Simula 67 và Pascal, cũng như trong nhiều ngôn ngữ động và ngôn ngữ hàm hiện đại. Tuy nhiên, theo truyền thống, chúng không được hỗ trợ trong họ ngôn ngữ C [đơn giản ban đầu]
Hiệu ứng[sửa]
Các hàm lồng nhau giả định phạm vi chức năng hoặc phạm vi khối. Phạm vi của một hàm lồng nhau nằm bên trong hàm kèm theo, tôi. e. bên trong một trong các khối cấu thành của chức năng đó, có nghĩa là nó không nhìn thấy bên ngoài khối đó và cả bên ngoài chức năng kèm theo. Một hàm lồng nhau có thể truy cập các hàm cục bộ khác, biến, hằng, kiểu, lớp, v.v. trong cùng một phạm vi hoặc trong bất kỳ phạm vi kèm theo nào mà không truyền tham số rõ ràng, giúp đơn giản hóa rất nhiều việc truyền dữ liệu vào và ra khỏi hàm lồng nhau. Điều này thường được phép cho cả đọc và viết
Các chức năng lồng nhau trong một số trường hợp [và ngôn ngữ] nhất định có thể dẫn đến việc tạo ra một bao đóng. Nếu hàm lồng nhau có thể thoát khỏi hàm bao quanh, ví dụ: nếu các hàm là đối tượng hạng nhất và một hàm lồng nhau được truyền cho một hàm khác hoặc được trả về từ hàm bao quanh, thì một bao đóng được tạo và các lệnh gọi đến hàm này có thể truy cập . Khung của hàm bao quanh ngay lập tức phải tiếp tục tồn tại cho đến khi lần đóng tham chiếu cuối cùng chết và do đó, các biến tự động không cục bộ được tham chiếu trong các lần đóng không thể được cấp phát ngăn xếp. Đây được gọi là vấn đề funarg và là lý do chính khiến các hàm lồng nhau không được triển khai trong một số ngôn ngữ đơn giản hơn vì nó làm phức tạp đáng kể việc tạo và phân tích mã, đặc biệt là khi các hàm được lồng vào nhiều cấp độ khác nhau, chia sẻ các phần khác nhau trong môi trường của chúng
Các ví dụ[sửa]
Một ví dụ sử dụng cú pháp Pascal [với ALGOL, Modula 2, Oberon, Ada, v.v. giống]
function E[x: real]: real;
function F[y: real]: real;
begin
F := x + y
end;
begin
E := F[3] + F[4]
end;
Hàm F được lồng trong E. Lưu ý rằng tham số của E x cũng hiển thị trong F [vì F là một phần của E] trong khi cả x và
fun e [x : real] =
let
fun f y = x+y
in
f 3 + f 4
end;
4 đều vô hình bên ngoài E và F tương ứngTương tự, trong Standard ML
fun e [x : real] =
let
fun f y = x+y
in
f 3 + f 4
end;
Một cách để viết ví dụ tương tự trong cú pháp Haskell
e :: Float -> Float e x = f 3 + f 4 where f y = x + y
Ví dụ tương tự trong cú pháp GNU C [C được mở rộng với các hàm lồng nhau]
float E[float x]
{
float F[float y]
{
return x + y;
}
return F[3] + F[4];
}
Sắp xếp nhanh[sửa]
Một ví dụ thực tế hơn là việc triển khai quicksort này
void sort[int *items, int size] {
void quickSort[int first, int last] {
void swap[int p, int q] {
int tmp = items[p];
items[p] = items[q];
items[q] = tmp;
}
int partition[] {
int pivot = items[first], index = first;
swap[index, last];
for [int i = first; i < last; i++]
if [items[i] < pivot]
swap[index++, i];
swap[index, last];
return index;
}
if [first < last] {
int pivotIndex = partition[];
quickSort[first, pivotIndex - 1];
quickSort[pivotIndex + 1, last];
}
}
quickSort[0, size - 1];
}
Một ví dụ khác là việc thực hiện sau đây của việc sử dụng
template
auto Sort[RandomAccessIterator Begin, RandomAccessIterator End]->void {
auto Partition = [&][] {
//Hoare partition scheme
auto &Pivot = *Begin;
auto ForwardCursor = Begin;
auto BackwardCursor = End - 1;
auto PartitionPositionFound = false;
auto LocatePartitionPosition = [&][] {
while [*ForwardCursor < Pivot]
++ForwardCursor;
while [Pivot < *BackwardCursor]
--BackwardCursor;
if [ForwardCursor >= BackwardCursor]
PartitionPositionFound = true;
else
Swap[*ForwardCursor, *BackwardCursor];
};
//Trivial helper function
auto MoveOnAndTryAgain = [&][] {
++ForwardCursor;
--BackwardCursor;
};
//Brief outline of the actual partition process
while [true] {
LocatePartitionPosition[];
if [PartitionPositionFound]
return BackwardCursor + 1;
else
MoveOnAndTryAgain[];
}
};
//Brief outline of the quicksort algorithm
if [Begin < End - 1] {
auto PartitionPosition = Partition[];
Sort[Begin, PartitionPosition];
Sort[PartitionPosition, End];
}
}
Mục đích[sửa]
Các định nghĩa hàm lồng nhau theo từ vựng là một hình thức che giấu thông tin và rất hữu ích để phân chia các nhiệm vụ thủ tục thành các nhiệm vụ con chỉ có ý nghĩa cục bộ. Điều này tránh làm lộn xộn các phần khác của chương trình với các hàm và biến không liên quan đến các phần đó
Chúng thường được sử dụng làm hàm trợ giúp hoặc hàm đệ quy bên trong một hàm khác [như trong ví dụ sắp xếp nhanh ở trên]. Điều này có lợi ích về cấu trúc trong việc tổ chức mã, tránh làm ô nhiễm phạm vi và cũng cho phép các chức năng chia sẻ trạng thái dễ dàng. Vì hàm lồng nhau có thể truy cập các biến cục bộ của hàm kèm theo, nên có thể chia sẻ trạng thái mà không cần truyền tham số cho hàm lồng nhau hoặc sử dụng biến toàn cục, giúp đơn giản hóa mã
Trong các ngôn ngữ có các hàm lồng nhau, các hàm thông thường cũng có thể chứa các hằng cục bộ và các kiểu [ngoài các biến, tham số và hàm cục bộ], được đóng gói và ẩn theo cùng một cách lồng nhau, ở bất kỳ mức độ sâu nào. Điều này có thể nâng cao hơn nữa khả năng cấu trúc mã
Sử dụng khác [ chỉnh sửa ]
Luồng điều khiển[sửa]
Các hàm lồng nhau cũng có thể được sử dụng cho luồng điều khiển phi cấu trúc, bằng cách sử dụng câu lệnh return cho luồng điều khiển phi cấu trúc chung. Điều này có thể được sử dụng để kiểm soát chi tiết hơn khả năng có thể với các tính năng tích hợp sẵn khác của ngôn ngữ – ví dụ: nó có thể cho phép kết thúc sớm vòng lặp for nếu không có sẵn
fun e [x : real] =
let
fun f y = x+y
in
f 3 + f 4
end;
7 hoặc kết thúc sớm vòng lặp for lồng nhau nếu có Hàm bậc cao[sửa]
Vì trong hầu hết các ngôn ngữ, các hàm là các kiểu trả về hợp lệ, có thể tạo một hàm lồng nhau truy cập một tập hợp các tham số từ hàm bên ngoài và có hàm đó là giá trị trả về của hàm bên ngoài. Do đó, có thể trả về một hàm được đặt để hoàn thành một tác vụ nhất định với ít hoặc không có thêm tham số nào được cung cấp cho nó, điều này có thể làm tăng hiệu suất khá đáng kể
Các lựa chọn thay thế[sửa]
Giải pháp thay thế chính cho các hàm lồng nhau trong các ngôn ngữ thiếu hỗ trợ cho chúng là đặt tất cả các hàm và biến có liên quan trong một mô-đun [tệp] riêng biệt và chỉ hiển thị công khai hàm bao bọc cấp cao nhất. Trong C, điều này thường sẽ được thực hiện bằng cách sử dụng các hàm tĩnh để đóng gói và các biến tĩnh để liên lạc. Điều này đạt được sự đóng gói và chia sẻ trạng thái, mặc dù không phải là tổ chức hợp lý được cung cấp bởi việc lồng các hàm từ vựng và phải trả giá bằng việc có một tệp riêng biệt. Nó cũng không thể ở nhiều hơn một cấp độ
Một cách khác là chia sẻ trạng thái giữa các hàm thông qua các tham số hàm, thường xuyên nhất là chuyển các tham chiếu dưới dạng đối số để tránh chi phí sao chép. Trong C, điều này thường được thực hiện bởi một con trỏ tới cấu trúc chứa ngữ cảnh. Điều này làm tăng đáng kể độ phức tạp của các lệnh gọi hàm
Trong PHP và các ngôn ngữ khác, chức năng ẩn danh là giải pháp thay thế duy nhất. hàm lồng nhau được khai báo không phải như hàm thông thường, mà theo tham chiếu, như một biến cục bộ. Để sử dụng các biến cục bộ trong hàm ẩn danh, hãy sử dụng bao đóng
Ngôn ngữ[sửa]
Các ngôn ngữ nổi tiếng hỗ trợ các chức năng lồng nhau từ vựng bao gồm
Ngôn ngữ chức năng [ chỉnh sửa ]
Trong hầu hết các ngôn ngữ lập trình hàm, chẳng hạn như Scheme, các hàm lồng nhau là một cách phổ biến để triển khai các thuật toán có vòng lặp trong đó. Một hàm bên trong đệ quy [đuôi] đơn giản được tạo, hoạt động như vòng lặp chính của thuật toán, trong khi hàm bên ngoài thực hiện các hành động khởi động chỉ cần thực hiện một lần. Trong các trường hợp phức tạp hơn, một số hàm đệ quy lẫn nhau có thể được tạo dưới dạng các hàm bên trong
Một số ngôn ngữ không có hỗ trợ trực tiếp[sửa | sửa mã nguồn]
Một số ngôn ngữ không có hỗ trợ cú pháp và ngữ nghĩa đơn giản để triển khai các hàm lồng nhau. Tuy nhiên, đối với một số người trong số họ, ý tưởng về các hàm lồng nhau có thể được mô phỏng với một số mức độ khó khăn thông qua việc sử dụng các cấu trúc ngôn ngữ khác. Các ngôn ngữ sau có thể xấp xỉ các hàm lồng nhau thông qua các chiến lược tương ứng
- C++
- trước C++11. cho phép định nghĩa các lớp bên trong các lớp, cung cấp khả năng sử dụng các phương thức của lớp theo cách tương tự như các hàm lồng nhau ở một mức [xem phần ]
- kể từ C++11. bằng cách sử dụng biểu thức lambda như ví dụ sắp xếp nhanh ở trên
- Eiffel rõ ràng không cho phép lồng các thói quen. Điều này là để giữ cho ngôn ngữ đơn giản và cũng cho phép quy ước sử dụng một biến đặc biệt, Kết quả, để biểu thị kết quả của một hàm [trả về giá trị]
- Visual Basic, bằng cách sử dụng các phương thức ẩn danh hoặc biểu thức lambda
- Java, bằng cách sử dụng các biểu thức lambda [xem ] [kể từ Java 8] hoặc thông qua một giải pháp thay thế bao gồm một lớp ẩn danh chứa một phương thức duy nhất. Một lớp được đặt tên được khai báo cục bộ cho một phương thức cũng có thể được sử dụng
Thực hiện[sửa]
Việc triển khai các hàm lồng nhau có thể liên quan nhiều hơn so với vẻ ngoài của nó, vì tham chiếu đến hàm lồng nhau tham chiếu đến các biến không cục bộ sẽ tạo ra một bao đóng. Vì lý do này, các hàm lồng nhau không được hỗ trợ trong một số ngôn ngữ như C, C++ hoặc Java vì điều này làm cho trình biên dịch khó triển khai hơn. Tuy nhiên, một số trình biên dịch hỗ trợ chúng, như một phần mở rộng dành riêng cho trình biên dịch. Một ví dụ nổi tiếng về điều này là việc triển khai GNU C của C chia sẻ mã với trình biên dịch cho các ngôn ngữ như Pascal, Ada và Modula
Truy cập các đối tượng không cục bộ[sửa | sửa mã nguồn]
Có một số cách để thực hiện các thủ tục lồng nhau trong ngôn ngữ có phạm vi từ vựng, nhưng cách cổ điển như sau
Bất kỳ đối tượng không cục bộ nào, X, được tiếp cận thông qua các liên kết truy cập trong các khung kích hoạt trên ngăn xếp máy. Người gọi, C, hỗ trợ thủ tục được gọi, P, bằng cách đẩy một liên kết trực tiếp tới lần kích hoạt mới nhất của đóng gói từ vựng tức thì của P, [P], trước chính cuộc gọi đó. Sau đó, P có thể nhanh chóng tìm ra cách kích hoạt phù hợp cho một X nhất định bằng cách lần theo một số cố định [P. độ sâu – X. độ sâu] của các liên kết [thường là một số lượng nhỏ]. Người gọi tạo liên kết trực tiếp này bằng [chính nó] sau C. độ sâu – P. độ sâu + 1 liên kết cũ hơn, dẫn đến kích hoạt mới nhất của [P], sau đó tạm thời kết nối các liên kết này với liên kết trực tiếp đến kích hoạt đó; . Lưu ý rằng P hiển thị cho và do đó có thể được gọi bởi C nếu [P] = C / [C] / [[C]] / v.v.Phương pháp ban đầu này nhanh hơn vẻ ngoài của nó, tuy nhiên nó thường được tối ưu hóa trong các trình biên dịch hiện đại thực tế [sử dụng hoặc các kỹ thuật tương tự]
Một cách khác để triển khai các hàm lồng nhau được một số trình biên dịch sử dụng là chuyển đổi ["nâng"] các hàm lồng nhau thành các hàm không lồng nhau [trong đó các tham số bổ sung, ẩn, thay thế các liên kết truy cập] bằng cách sử dụng quy trình được gọi là nâng lambda trong giai đoạn trung gian
Chức năng như giá trị[sửa]
Để các hàm cục bộ có các thuộc tính không cục bộ có phạm vi từ vựng được chuyển thành kết quả, mã thời gian chạy ngôn ngữ cũng phải hoàn toàn chuyển môi trường [dữ liệu] mà hàm nhìn thấy bên trong hàm đóng gói của nó, để nó cũng có thể truy cập được khi kích hoạt hiện tại của phần bao quanh . Điều này có nghĩa là môi trường phải được lưu trữ trong một vùng bộ nhớ khác với [các phần được lấy lại sau đó của] ngăn xếp thực thi dựa trên trình tự thời gian, do đó, ngụ ý một số loại cấp phát bộ nhớ động tự do. Do đó, nhiều ngôn ngữ dựa trên Algol cũ hơn [hoặc phương ngữ của chúng] không cho phép các hàm cục bộ truy cập các giá trị không phải là ngôn ngữ cục bộ được truyền dưới dạng giá trị trả về hoặc chúng hoàn toàn không cho phép các hàm làm giá trị trả về, mặc dù vẫn có thể truyền các hàm đó dưới dạng đối số
Ngăn xếp không thực thi[sửa]
Ít nhất một lần triển khai các hàm lồng nhau gây ra mất ngăn xếp Không thực thi [ngăn xếp NX]. Việc triển khai hàm lồng nhau của GCC gọi các hàm lồng nhau thông qua lệnh nhảy được đặt trong ngăn xếp máy khi chạy. Điều này yêu cầu ngăn xếp phải được thực thi
Không có ngăn xếp thực thi và các chức năng lồng nhau loại trừ lẫn nhau trong GCC. Nếu một hàm lồng nhau được sử dụng trong quá trình phát triển chương trình, thì Ngăn xếp NX sẽ bị mất một cách âm thầm. GCC đưa ra cảnh báo
fun e [x : real] =
let
fun f y = x+y
in
f 3 + f 4
end;
9 để cảnh báo về tình trạngPhần mềm được thiết kế bằng Vòng đời phát triển an toàn thường không cho phép sử dụng các hàm lồng nhau trong trình biên dịch [GCC] cụ thể này do mất Ngăn xếp NX