Wikipedia

Lập trình hàm

(Đổi hướng từ Functional programming)

Trong ngành khoa học máy tính, lập trình hàm là một mô hình lập trình xem việc tính toán là sự đánh giá các hàm toán học và tránh sử dụng trạng thái và các dữ liệu biến đổi. Lập trình hàm nhấn mạnh việc ứng dụng hàm số, trái với phong cách lập trình mệnh lệnh, nhấn mạnh vào sự thay đổi trạng thái.[1] Lập trình hàm xuất phát từ phép tính lambda, một hệ thống hình thức được phát triển vào những năm 1930 để nghiên cứu định nghĩa hàm số, ứng dụng của hàm số, và đệ quy. Nhiều ngôn ngữ lập trình hàm có thể được xem là những cách phát triển giải tích lambda.[1]

Trong thực tế, sự khác biệt giữa hàm số toán học và cách dùng từ "hàm" trong lập trình mệnh lệnh đó là các hàm mệnh lệnh có thể tạo ra hiệu ứng lề, làm thay đổi giá trị của một phép tính trước đó. Vì vậy các hàm kiểu này thiếu tính trong suốt tham chiếu, có nghĩa là cùng một biểu thức ngôn ngữ lại có thể tạo ra nhiều giá trị khác nhau vào các thời điểm khác nhau tùy thuộc vào trạng thái của chương trình đang thực thi. Ngược lại, trong lập trình hàm, giá trị xuất ra của một hàm chỉ phụ thuộc vào các tham số đầu vào của hàm, vì thế gọi hàm f hai lần với cùng giá trị tham số x sẽ cho ra cùng kết quả f(x). Việc loại bỏ hiệu ứng lề có thể làm cho chương trình dễ hiểu hơn rất nhiều và người ta có dự đoán được hành vi của một chương trình, đó chính là một trong các động lực chính cho sự phát triển của lập trình hàm.[1]

Các ngôn ngữ lập trình hàm, đặc biệt là các loại thuần lập trình hàm, có ảnh hưởng lớn trong giới học thuật hơn là dùng để phát triển các phần mềm thương mại. Tuy vậy, các ngôn ngữ lập trình hàm nổi bật như Scheme,[2][3][4][5] Erlang,[6][7][8] Objective Caml,[9][10] và Haskell[11][12] đã được nhiều tổ chức khác nhau sử dụng trong các ứng dụng công nghiệp và thương mại. Lập trình hàm cũng được sử dụng trong công nghiệp thông qua các ngôn ngữ lập trình chuyên biệt như R (thống kê),[13][14] Mathematica (toán học hình thức),[15] J và K (phân tích tài chính)[cần dẫn nguồn], F# trong Microsoft.NET và XSLT (XML).[16][17] Các ngôn ngữ chuyên biệt dạng khai báo được sử dụng rộng rãi hiện nay như SQL và Lex/Yacc, cũng sử dụng một số thành phần của lập trình hàm, đặc biệt để tránh các giá trị biến đổi.[18] Các bảng tính (spreadsheet) cũng có thể được xem là các ngôn ngữ lập trình hàm.[19]

Lập trình theo phong cách lập trình hàm cũng có thể thực hiện ở các ngôn ngữ không được thiết kế riêng cho lập trình hàm. Ví dụ, ngôn ngữ lập trình mệnh lệnh Perl đã có một cuốn sách viết về cách áp dụng các khái niệm lập trình hàm vào đó.[20] JavaScript, một trong các ngôn ngữ được dùng nhiều hiện nay, có khả năng lập trình hàm.[21]

Các khái niệm

sửa

Một số khái niệm và mô hình chỉ có ở lập trình hàm, và thường xa lạ với kiểu lập trình mệnh lệnh (bao gồm cả lập trình hướng đối tượng). Tuy nhiên, các ngôn ngữ lập trình thường lai tạp nhiều hình thái lập trình khác nhau để lập trình viên sử dụng các ngôn ngữ "mệnh lệnh nhất" cũng có thể tận dụng một số các khái niệm này.[22]

Hàm hạng nhất và hàm bậc cao

sửa
Bài chi tiết: hàm hạng nhất và hàm bậc cao

Hàm bậc cao là các hàm số hoặc có thể nhận các hàm số khác làm tham số hoặc có thể trả về kết quả là hàm số (phép toán vi phân   để tính vi phân của hàm   là một ví dụ của hàm bậc cao trong giải tích).

Các hàm bậc cao có liên hệ chặt chẽ với hàm hạng nhất, ở chỗ các hàm bậc cao và hàm hạng nhất đều cho phép nhận hàm số làm tham số và trả về các hàm khác. Sự khác biệt giữa hai loại này rất mờ nhạt: "bậc cao" mô tả một khái niệm hàm trong toán học tính toán trong các hàm khác, còn "hàm hạng nhất" là một thuật ngữ của ngành khoa học máy tính mô tả các thực thể của ngôn ngữ lập trình trong đó không có giới hạn về việc sử dụng (vì vậy các hàm hạng nhất có thể xuất hiện ở bất cứ đâu trong chương trình, giống như các thực thể hạng nhất khác nhau con số, trong đó có cả việc làm tham số cho các hàm khác và làm giá trị trả về của hàm khác).

Các hàm bậc cao cho phép áp dụng bán phần hoặc currying, một kỹ thuật trong đó hàm lần lượt sử dụng từng tham số của nó, mỗi lần sử dụng lại trả về một hàm mới và chấp nhận tham số tiếp theo. Việc làm này cho phép người lập trình biểu diễn một cách súc tích hàm số kế thừa, tương tự như toán tử cộng sẽ lần lượt cộng từng số tự nhiên lại với nhau.

Hàm thuần túy

sửa

Các hàm (hoặc biểu thức) thuần túy hàm không có bộ nhớ hoặc các hiệu ứng lề nhập/xuất. Điều này có nghĩa là các hàm thuần túy có một số đặc tính hữu ích, mà đa số trong chúng có thể dùng để tối ưu mã nguồn:

  • Nếu kết quả của một biểu thức thuần túy không được sử dụng, ta có thể xóa nó đi mà không ảnh hưởng đến các biểu thức khác.
  • Nếu một hàm thuần túy được gọi cùng với các tham số không tạo ra hiệu ứng lề, kết quả sẽ là hằng số tương ứng với danh sách tham số cụ thể (có khi gọi là trong suốt tham chiếu), tức là hàm thuần túy nếu được gọi lần nữa với cùng bộ tham số, kết quả trả về cũng sẽ y hệt như trước (điều này cho phép tối ưu hóa lưu đệm như memoization).
  • Nếu không có sự phụ thuộc về dữ liệu giữa hai biểu thức thuần túy, thì thứ tự của chúng có thể đảo cho nhau, hoặc chúng có thể thực hiện song song mà không ảnh hưởng đến nhau (hay nói cách khác, đánh giá một biểu thức thuần túy bất kỳ là an toàn về luồng (thread-safe)).
  • Nếu toàn bộ ngôn ngữ không cho phép hiệu ứng lề, thì chiến thuật đánh giá hàm nào cũng dùng được; việc này trao cho trình biên dịch quyền tự do sắp xếp lại hoặc phối hợp việc đánh giá biểu thức trong một chương trình (ví dụ, dùng kỹ thuật loại bỏ cây).

Trong khi đa số trình biên dịch dành cho các ngôn ngữ lập trình mệnh lệnh có thể nhận dạng hàm thuần túy, và thực hiện các phép khử biểu thức con thường gặp trong các lệnh gọi hàm thuẫn túy, chúng không thể lúc nào cũng làm như vậy đối với các thư viện đã dịch sẵn, thường không tiết lộ thông tin này, vì thế làm cản trở sự tối ưu hóa liên quan đến các hàm bên ngoài như vậy. Một số trình biên dịch, như gcc, thêm từ khóa bổ sung để giúp lập trình viên đánh dấu hàm nào là hàm thuần túy, để cho phép tối ưu hóa kiểu như vậy. Fortran 95 cho phép hàm được chỉ định "thuần túy".

Đệ quy

sửa
Bài chi tiết: Đệ quy (khoa học máy tính)

Vòng lặp trong các ngôn ngữ hàm thường được thực hiện thông qua đệ quy. Hàm đệ quy sẽ tự gọi chính nó, cho phép thực hiện đi thực hiện lại một tác vụ. Việc đệ quy có thể đòi hỏi phải sử dụng một chồng (stack), nhưng đệ quy đuôi vẫn có thể được trình biên dịch nhận ra và tối ưu hóa nó thành cùng đoạn mã được dùng để hiện thực vòng lặp trong ngôn ngữ mệnh lệnh. Tiêu chuẩn của ngôn ngữ Scheme là phải nhận diện và tối ưu hóa được đệ quy đuôi. Một trong những cách tối ưu hóa đệ quy đuôi là chuyển chương trình thành kiểu truyền liên tiếp trong quá trình dịch.

Các mẫu đệ quy phổ biến đều có thể được khử đệ quy bằng các hàm bậc cao, catamorphism và anamorphism (hay "fold" và "unfold" - gấp và mở gấp) là những ví dụ rõ nhất. Các hàm bậc cao như vậy đóng vai trò tương tự như các cấu trúc điều khiển có sẵn như vòng lặp trong ngôn ngữ mệnh lệnh.

Đa số các ngôn ngữ lập trình hàm đa mục đích đều cho phép đệ quy không giới hạn và là Turing complete, khiến cho bài toán dừng trở nên không quyết định được, có thể gây ra sự thiếu căn cứ cho việc suy diễn công thức, và nói chung đòi hỏi phải có khái niệm không nhất quán trong logic do hệ thống kiểu của ngôn ngữ quy định. Một vài ngôn ngữ lập trình với mục đích đặc biệt như Coq chỉ cho phép đệ quy well-founded và chuẩn hóa mạnh (tính toán không dừng chỉ có thể biểu diễn bằng dòng giá trị vô hạn gọi là codata). Kết quả là, những ngôn ngữ như vậy không phải Turing complete và một số hàm không thể biểu diễn trong ngôn ngữ, dù ngôn ngữ đó vẫn có thể biểu diễn được rất nhiều cách tính toán thú vị mà tránh được vấn đề do đệ quy không giới hạn gây ra. Lập trình hàm giới hạn trong việc đệ quy well-founded với một số ràng buộc khác được gọi là lập trình hàm hoàn toàn (total). Xem Turner 2004 để biết thêm.[23]

Tính toán chặt và không chặt

sửa

Có thể chia các ngôn ngữ hàm làm hai loại tùy vào việc chúng sử dụng cách tính toán biểu thức chặt (tham lam) hay không chặt (lười biếng), là những khái niệm chỉ cách xử lý thông số của hàm khi tính toán một biểu thức. Sự khác biệt về các cách tính toán này xuất hiện ở ngữ nghĩa biểu thị của biểu thức khi chúng có chứa phép toán lỗi hoặc có vấn đề. Khi tính toán chặt, việc tính toán số hạng có chứa lỗi cũng sẽ dẫn đến lỗi. Ví dụ, biểu thức:

print length([2+1, 3*2, 1/0, 5-4])

sẽ không tính được theo tính toán chặt vì phép chia không tại phần tử thứ ba của danh sách. Còn với tính toán không chặt, hàm length sẽ trả về giá trị 4, vì khi tính toán hàm, nó không cố gắng tính toán các phần tử trong danh sách. Nói một cách ngắn gọn, tính toán chặt luôn luôn tính toán tất cả cấc số hạng của hàm trước khi xử lý hàm. Tính toán không chặt không tính toán tham số của hàm trừ khi nó cần giá trị đó để tính toán hàm.

Cách hiện thực thông thường của tính toán không chặt trong ngôn ngữ hàm là thu giảm đồ thị. Cách tính toán không chặt được dùng mặc định trong vài ngôn ngữ lập trình hàm thuần túy, như Miranda, Clean và Haskell.

Hughes vào năm 1984 đã phản bác việc dùng tính toán không chặt làm cơ chế để tăng tính module hóa của chương trình thông qua quá trình chia nhỏ bài toán, bằng cách làm cho việc hiện thực độc lập giữa nhà sản xuất và khách hàng dễ dàng hơn.[24] Launchbury 1993 mô tả một số khó khăn mà đánh giá lười biếng tạo ra, cụ thể trong việc phân tích yêu cầu lưu trữ của chương trình, và đề xuất ngữ nghĩa hoạt động để hỗ trợ cho việc phân tích này.[25] Harper 2009 đề xuất đưa cả tính toán chặt lẫn không chặt vào một ngôn ngữ, bằng cách dùng hệ thống kiểu của ngôn ngữ để phân biệt chúng.[26]

Hệ thống kiểu, tính đa hình, kiểu dữ liệu đại số và so trùng mẫu

sửa

Đặc biệt kể từ sự phát triển của luận kiểu Hindley–Milner trong thập niên 1970, các ngôn ngữ lập trình hàm có khuynh hướng sử dụng phép tính lambda định kiểu, chống lại phép tính lambda bất định kiểu đã được dùng trong Lisp và các biến thể của nó (như Scheme). Việc sử dụng các kiểu dữ liệu đại số và so trùng mẫu làm cho việc thao tác các cấu trúc dữ liệu phức tạp trở nên thuận tiện và rõ ràng hơn; sự tồn tại của việc kiểm tra kiểu mạnh mẽ trong thời gian biên dịch làm cho các chương trình trở nên đáng tin cậy hơn, trong khi đó luận kiểu giải phóng lập trình viên khỏi việc cần phải khai báo thủ công các kiểu để biên dịch.

Một số ngôn ngữ lập trình hàm định hướng nghiên cứu như Coq, Agda, Cayenne, và Epigram dựa trên lý thuyết kiểu intuitionistic, thuyết này cho phép các kiểu phụ thuộc vào các term. Các kiểu như vậy được gọi là các kiểu phụ thuộc. Các hệ thống kiểu này không có các luận kiểu khả định và rất khó để hiểu và lập trình với chúng. Nhưng các kiểu phụ thuộc này có thể mô tả các mệnh đề tự do trong logic mệnh đề. Thông qua Curry–Howard isomorphism, sau đó, các chương trình định kiểu tốt trong những ngôn ngữ này sẽ trở thành các phương tiện cho việc viết các chứng minh toán học hình thức mà từ đó một trình biên dịch có thể sinh ra mã được chứng nhận. Trong khi những ngôn ngữ này chủ yếu được quan tâm trong nghiên cứu học thuật (kể cả trong toán học hình thức hóa), chúng cũng bắt đầu được sử dụng trong kĩ thuật. Compcert là một trình biên dịch cho một tập con của ngôn ngữ lập trình C được viết bằng Coq và đã được chứng thực chính thức.[27]

Một dạng giới hạn của các kiểu phụ thuộc được gọi là kiểu dữ liệu đại số được khái quát hóa (GADT). Dạng này có thể được thực hiện theo cách cung cấp một vài trong số các lợi ích của lập trình phụ thuộc kiểu trong khi tránh hầu hết sự bất tiện của nó.[28] GADT có sẵn trong Trình biên dịch Glasgow Haskell và trong Scala (như "case classes"), và được cho là phần bổ sung vào các ngôn ngữ khác bao gồm cả Java và C#.[29]

Lập trình hàm trong các ngôn ngữ phi hàm

sửa

Có thể sử dụng phong cách hàm của việc lập trình trong các ngôn ngữ mà theo truyền thống không được xem là ngôn ngữ hàm.[30] Một số ngôn ngữ phi hàm đã mượn nhiều đặc điểm như các hàm bậc cao hơn, và các quan niệm danh sách từ các ngôn ngữ lập trình hàm. Điều này làm cho việc chấp nhận phong cách hàm dễ dàng hơn khi sử dụng những ngôn ngữ này. Các cấu trúc hàm như các "hàm bậc cao hơn" và các "danh sách lười" có thể lấy được trong C++ qua các thư viện.[31] Trong C, các con trỏ hàm có thể được dùng để đạt được một vài trong số các hiệu quả của các hàm bậc cao hơn. Ví dụ hàm chung map có thể được thực thi bằng cách dùng các con trỏ hàm. Trong Visual Basic 9 và C# 3.0 và cao hơn, các hàm lambda có thể được dùng để viết các chương trình theo phong cách hàm. [32] Trong Java, các lớp nặc danh đôi khi được sử dụng để mô phỏng các sự đóng,[cần dẫn nguồn] tuy nhiên các lớp nặc danh không phải luôn luôn là các thay thế chính xác cho các sự đóng bởi vì chúng có nhiều khả năng bị hạn chế hơn.

Nhiều mẫu thiết kế hướng đối tượng có thể biểu đạt bằng các thuật ngữ lập trình hàm: ví dụ, mẫu chiến lược đơn giản chỉ ra cách dùng của hàm bậc cao hơn, và mẫu khách viếng thăm gần như tương ứng với một catamorphism, hoặc fold.

Các ích lợi của dữ liệu bất biến có thể được thấy ngay cả trong các chương trình mệnh lệnh, vì thế các lập trình viên thường xuyên cố gắng làm cho một số dữ liệu bất biến ngay cả trong các chương trình mệnh lệnh.[33]

Xem thêm

sửa

Tham khảo

sửa
  1. ^ a b c Hudak, Paul (1989). “Conception, evolution, and application of functional programming languages” (PDF). ACM Computing Surveys. 21 (3): 359–411. doi:10.1145/72551.72554. Bản gốc (PDF) lưu trữ ngày 20 tháng 3 năm 2009. Truy cập ngày 21 tháng 10 năm 2010.
  2. ^ Clinger, Will (1987). “MultiTasking and MacScheme”. MacTech. 3 (12). Truy cập ngày 28 tháng 8 năm 2008.
  3. ^ Hartheimer, Anne (1987). “Programming a Text Editor in MacScheme+Toolsmith”. MacTech. 3 (1). Bản gốc lưu trữ ngày 29 tháng 6 năm 2011. Truy cập ngày 28 tháng 8 năm 2008.
  4. ^ Kidd, Eric. Terrorism Response Training in Scheme. CUFP 2007. Bản gốc lưu trữ ngày 21 tháng 12 năm 2010. Truy cập ngày 26 tháng 8 năm 2009.
  5. ^ Cleis, Richard. Scheme in Space. CUFP 2006. Bản gốc lưu trữ ngày 27 tháng 5 năm 2010. Truy cập ngày 26 tháng 8 năm 2009.
  6. ^ “Who uses Erlang for product development?”. Frequently asked questions about Erlang. Truy cập ngày 5 tháng 8 năm 2007.
  7. ^ Armstrong, Joe (tháng 6 năm 2007). A history of Erlang. Third ACM SIGPLAN Conference on History of Programming Languages. San Diego, California. Truy cập ngày 29 tháng 8 năm 2009.
  8. ^ Larson, Jim (tháng 3 năm 2009). “Erlang for concurrent programming”. Communications of the ACM. 52 (3): 48. doi:10.1145/1467247.1467263. Truy cập ngày 29 tháng 8 năm 2009.
  9. ^ Minsky, Yaron; Weeks, Stephen (2008). “Caml Trading - experiences with functional programming on Wall Street”. Journal of Functional Programming. Cambridge University Press. 18 (4): 553–564. doi:10.1017/S095679680800676X. Truy cập ngày 27 tháng 8 năm 2008.
  10. ^ Leroy, Xavier. Some uses of Caml in Industry (PDF). CUFP 2007. Bản gốc (PDF) lưu trữ ngày 8 tháng 10 năm 2011. Truy cập ngày 26 tháng 8 năm 2009.
  11. ^ “"Haskell in industry - Haskell Wiki”. Truy cập ngày 26 tháng 8 năm 2009. Haskell has a diverse range of use commercially, from aerospace and defense, to finance, to web startups, hardware design firms and lawnmower manufacturers.
  12. ^ Hudak, Paul (tháng 6 năm 2007). A history of Haskell: being lazy with class. Third ACM SIGPLAN Conference on History of Programming Languages. San Diego, California. Truy cập ngày 29 tháng 8 năm 2009. Đã bỏ qua tham số không rõ |otherses= (trợ giúp)
  13. ^ The useR! 2006 conference schedule includes papers on the commercial use of R
  14. ^ Chambers, John M. (1998). Programming with Data: A Guide to the S Language. Springer Verlag. tr. 67–70. ISBN 978-0387985039.
  15. ^ Department of Applied Math, University of Colorado. “Functional vs. Procedural Programming Language”. Bản gốc lưu trữ ngày 13 tháng 11 năm 2007. Truy cập ngày 28 tháng 8 năm 2006.
  16. ^ Dimitre Novatchev. “The Functional Programming Language XSLT - A proof through examples”. TopXML. Bản gốc lưu trữ ngày 18 tháng 5 năm 2006. Truy cập ngày 27 tháng 5 năm 2006.
  17. ^ David Mertz. “XML Programming Paradigms (part four): Functional Programming approached to XML processing”. IBM developerWorks. Truy cập ngày 27 tháng 5 năm 2006.
  18. ^ Donald D. Chamberlin và Raymond F. Boyce (1974). “SEQUEL: A structured English query language”. Proceedings of the 1974 ACM SIGFIDET: 249–264.. In this paper, one of the first formal presentations of the concepts of SQL (and before the name was later abbreviated), Chamberlin and Boyce emphasize that SQL was developed "Without resorting to the concepts of bound variables and quantifiers".
  19. ^ Simon Peyton Jones, Margaret Burnett, Alan Blackwell (2003). “Improving the world's most popular functional language: user-defined functions in Excel”.Quản lý CS1: nhiều tên: danh sách tác giả (liên kết)
  20. ^ Dominus, Mark J. (2005). Higher-Order Perl. Morgan Kaufmann. ISBN 1558607013.
  21. ^ Crockford, Douglas (2001). “JavaScript: The World's Most Misunderstood Programming Language”. "JavaScript's C-like syntax, including curly braces and the clunky for statement, makes it appear to be an ordinary procedural language. This is misleading because JavaScript has more in common with functional languages like Lisp or Scheme than with C or Java. It has arrays instead of lists and objects instead of property lists. Functions are first class. It has closures. You get lambdas without having to balance all those parens." (For discussion on JavaScript as a functional programming language, see Talk:JavaScript#Function-level vs. functional programming).
  22. ^ Dick Pountain. “Functional Programming Comes of Age”. BYTE.com (August 1994). Bản gốc lưu trữ ngày 27 tháng 8 năm 2006. Truy cập ngày 31 tháng 8 năm 2006.
  23. ^ Turner, D.A. (ngày 28 tháng 7 năm 2004). “Total Functional Programming”. Journal of Universal Computer Science. 10 (7): 751–768. doi:10.3217/jucs-010-07-0751.
  24. ^ John Hughes. “Why Functional Programming Matters”. Bản gốc lưu trữ ngày 8 tháng 12 năm 2006. Truy cập ngày 21 tháng 10 năm 2010.
  25. ^ John Launchbury (1993). “A Natural Semantics for Lazy Evaluation”.
  26. ^ Robert W. Harper (2009). Practical Foundations for Programming Languages (PDF). (in preparation), section XIV.
  27. ^ “The Compcert verified compiler”.
  28. ^ Simon Peyton Jones, Dimitrios Vytiniotis, Stephanie Weirich, and Geoffrey Washburn. “Simple unification-based type inference for GADTs”. ICFP 2006. tr. 50–61.Quản lý CS1: nhiều tên: danh sách tác giả (liên kết)
  29. ^ Andrew Kennedy and Claudio Russo (tháng 10 năm 2005). “Generalized Algebraic Data Types and Object-Oriented Programming” (PDF). OOPSLA. San Diego, California. source of citation
  30. ^ Pieter Hartel & Henk Muller and Hugh Glaser (2004). “The Functional C experience” (PDF). The Journal of Functional Programming. 14 (2): 129–135. doi:10.1017/S0956796803004817. Bản gốc (PDF) lưu trữ ngày 19 tháng 7 năm 2011. Truy cập ngày 21 tháng 10 năm 2010.Quản lý CS1: sử dụng tham số tác giả (liên kết); David Mertz. “Functional programming in Python, Part 3”. IBM developerWorks. Truy cập ngày 17 tháng 9 năm 2006.(Part 1, Part 2)
  31. ^ McNamara, B. “FC++: Functional Programming in C++”. Bản gốc lưu trữ ngày 14 tháng 6 năm 2006. Truy cập ngày 28 tháng 5 năm 2006.
  32. ^ Miller, Jeremy (2009). “Functional Programming for Everyday.NET Development”. The Language Integrated Query (LINQ) feature in all of its many incarnations is an obvious and powerful use of functional programming in.NET, but that's just the tip of the iceberg.
  33. ^ See Item 15 in the book Effective Java, Second Edition by Joshua Bloch

Đọc thêm

sửa

Liên kết ngoài

sửa
Lấy từ “https://vi.wikipedia.org/w/index.php?title=Lập_trình_hàm&oldid=71891321”