Hầu hết các ngôn ngữ lập trình đều cung cấp:
- Các biểu thức (expression) để biểu diễn các thành phần đơn giản nhất của ngôn ngữ đó, ví dụ như chuỗi ký tự, số nguyên, số thực (vd: “string”, 12, …).
- Các phương thức để kết hợp các biểu thức (toán tử “+” dùng để cộng 2 số, method built-in trong string để ghép các xâu ký tự …).
- Các phương thức để trừu tượng hóa các biểu thức (ví dụ như phép gán – assignment): nghĩa là gán tên biến để có thể gọi đến các biểu thức này sử dụng tên biến được gán.
Biểu thức được ước lượng hay thực thi (evaluation) để mô tả quá trình chuyển chúng thành giá trị. Vậy biểu thức là gì? Làm cách nào để một biểu thức được đánh giá/ tính toán? Cùng tìm hiểu qua bài viết này cùng HBLAB nhé.
Biểu thức (Expression)
Vậy biểu thức là gì? Trong đại số, một biểu thức nhóm các số (number), ký hiệu (symbol) và toán tử (operator) lại với nhau để tính toán một giá trị.
Giá trị của biểu thức trong ảnh có thể được tính bằng cách thay giá trị của x vào biểu thức.
Biểu thức thường trả về một giá trị, ví dụ như kết quả của một phép tính số học, hoặc kết quả của một hàm trả về, khác với lệnh (statement), không nhất thiết phải trả về một giá trị, mà thường thực hiện một hành động nhất định (ví dụ như lệnh print sẽ in ra màn hình mà không trả về giá trị).
Các ngôn ngữ lập trình có những định nghĩa biểu thức và tập luật liên quan (Python, Scala, ….)
Trong một số ngôn ngữ thuần functional programming như Scala, biểu thức đóng vai trò quan trọng khi hầu hết mọi thứ đều là biểu thức bao gồm cả các câu lệnh khai báo hàm và các biểu thức điều kiện. Chính vì vậy, các kỹ thuật ước lượng/ thực thi biểu thức (expression evaluation strategies) đóng vai trò vô cùng quan trọng.
Thực thi/ đánh giá (evaluation) biểu thức
Các bước ước lượng/ thực thi một biểu thức:
- Xác định toán tử trái nhất (leftmost operator).
- Tính toán giá trị của các toán hạng tương ứng theo thứ tự trái sang phải.
- Áp dụng toán tử lên các toán hạng đã tính được.
Tên biến sẽ được thay thế bởi định nghĩa (right hand side definition). Quá trình đánh giá/ tính toán biểu thức kết thúc khi giá trị được trả về.
Ví dụ, tính toán giá trị biểu thức “( 2 * pi ) * radius”:
| def pi = 3.14159 def radius = 10 ( 2 * pi ) * radius |
Đầu tiên thay pi = 3.14159 vào biểu thức, tiếp theo thực hiện phép nhân (2 * 3.14169), sau đó lặp lại quá trình cho đến khi biểu thức trả về giá trị:
| ( 2 * pi ) * radius > ( 2 * 3.14159 ) * radius > 6.28318 * radius > 6.28318 * 10 > 62.8318 |
Kết thúc (Termination)
Giờ chúng ta đã biết evaluation là gì, vậy một câu hỏi thú vị được đặt ra đó là liệu có phải tất cả mọi biểu thức đều kết thúc và trả về một giá trị (sau một số lượng hữu hạn các bước)? Hay nói cách khác liệu có phải mọi quá trình tính toán / đánh giá (evaluation) của biểu thức đều terminate?
Một ví dụ về một hàm mà quá trình evaluation của hàm này không thể terminate:
| def loop: Int = loop |
Hàm loop sẽ được thay bằng chính nó tạo thành một vòng lặp và quá trình evaluation của hàm này sẽ không thể kết thúc/ trả về giá trị!
Thực thi/ đánh giá hàm (Function Application Evaluation)
Các hàm chứa parameters cũng có thể được ước lượng/ tính toán gần tương tự như các toán tử trong biểu thức đại số:
- Tính toán các arguments của hàm theo thứ tự từ trái sang phải.
- Thay hàm bằng phần thân hàm/ định nghĩa của hàm, đồng thời
- Thay thế các tham số của hàm (parameters) bằng các giá trị truyền vào (arguments).
Ví dụ:
Cho hàm “square” nhận vào một số Double và trả về bình phương của số đó và hàm “sumOfSquares” nhận 2 số x, y và trả về tổng bình phương của x và bình phương của y.
| def square(x: Double) = x * x def sumOfSquares(x: Double, y: Double) = square(x) + square(y) |
Biểu thức “sumOfSquares(3, 2 + 2)” sẽ được evaluate như sau:
| sumOfSquares(3, 2 + 2) >sumOfSquares(3, 4) // tính toán giá trị của các arguments >square(3) + square(4) // thay hàm bằng định nghĩa của hàm >3 * 3 + square(4) // thay thế param của hàm (x) bằng các arguments (3) >9 + square(4) >9 + 4 * 4 >9 + 16 >25 |
Interpreter sẽ tính toán các tham số của hàm thành các giá trị trước khi thay thế định nghĩa hàm, một kỹ thuật evaluation khác đó là thay hàm bằng định nghĩa của hàm với các tham số chưa được tính toán thành các giá trị:
| sumOfSquares(3, 2 + 2) >square(3) + square(2 + 2) // thay hàm bằng định nghĩa của hàm, không tính toán giá trị của param “2 + 2” >3 * 3 + square(2 + 2) // tiếp tục truyền param “2 + 2” xuống các bước sau >9 + square(2 + 2) >9 + (2 + 2) * (2 + 2) >9 + 4 * (2 + 2) >9 + 4 * 4 >25 |
Call-by-value and call-by-name evaluation
Kỹ thuật tính toán/ ước lượng biểu thức đầu tiên được gọi là call-by-value (CBV) và kỹ thuật thứ hai được giới thiệu sau đó được gọi là call-by-name(CBN).
Cả 2 kỹ thuật đều sẽ tính toán biểu thức và trả về giá trị với điều kiện:
- Biểu thức chỉ chứa các hàm thuần (pure functions).
- Cả 2 kỹ thuật cho cùng một biểu thức đều đều terminate (sẽ có những biểu thức không terminate với CBV nhưng lại terminate với CBN).
CBV có điểm mạnh là sẽ tính toán tất cả tham số của hàm duy nhất một lần.
CBN có lợi thế trong trường hợp một tham số được truyền vào nhưng lại không được sử dụng trong quá trình tính toán/ước lượng của hàm.
Hãy cùng xét 2 ví dụ để hiểu rõ hơn về các lợi thế của từng kỹ thuật evaluation
Cho hàm
| def test(x: Int, y: Int) = x * x |
VD1: Tính giá trị của biểu thức “test(3 + 4, 8)”
Sử dụng CBV
| test(3 + 4, 8) > test(7, 8) > 7 * 7 > 49 |
Sử dụng CBN
| test(3 + 4, 8) > (3 + 4) * (3 + 4) > 7 * (3 + 4) > 7 * 7 > 49 |
=> Ta có thể thấy kỹ thuật CBV sẽ nhanh hơn trong trường hợp này
VD2: Tính giá trị của biểu thức “test(7, 2 * 4)”
Sử dụng CBV
| test(7, 2 * 4) > test(7, 8) > 7 * 7 > 49 |
Sử dụng CBN
| test(7, 2 * 4) > 7 * 7 // do tham số y không được sử dụng nên sẽ không tính toán giá trị của “2 * 4” > 49 |
=> Trong trường hợp này khi tham số không được sử dụng, CBN lại là kỹ thuật có thời gian tính toán nhanh hơn.
Hầu hết các ngôn ngữ lập trình thường sẽ sử dụng CBV, một số các ngôn ngữ lập trình functional programming sẽ sử dụng CBN, một số ngôn ngữ ví dụ như Scala, sẽ cho phép người dùng sử dụng cả 2 kỹ thuật.
Call-by-value and call-by-name termination
Nếu CBV evaluation của một biểu thức terminate và trả về một giá trị thì áp dụng kỹ thuật CBN evaluation với biểu thức đó cũng sẽ trả về một giá trị. Vế ngược lại không hoàn toàn luôn đúng.
Để chứng minh vế ngược lại không đúng, ta sẽ tìm một biểu thức có thể terminate sử dụng kỹ thuật CBN nhưng lại không terminate nếu sử dụng kỹ thuật CBV:
Cho hàm
| def first(x: Int, y: Int) = x |
Xét biểu thức “first(1, loop)”, tính giá trị của biểu thức sử dụng hai kỹ thuật CBN và CBV:
- Sử dụng kỹ thuật CBN, biểu thức này sẽ terminate và trả về giá trị 1 bời đối với kỹ thuật CBN, các tham số không được sử dụng sẽ hoàn toàn không được tính toán/ ướng lượng, do đó tham số y tuy là một vòng lặp nhưng không được sử dụng nên sẽ không được ước lượng.
- Sử dụng kỹ thuật CBV, biểu thức này sẽ không terminate được do các tham số truyền vào sẽ được tính toán từ bước đầu và vì thế biểu thức loop khi được ướng lượng sẽ không thể terminate.
Bài viết được tham khảo từ các bài giảng trong course Functional Programming Principles in Scala dạy bởi giáo sư Martin Odersky. Rất mong nhận được các góp ý, phản hồi từ bạn đọc chia sẻ kiến thức cùng HBLAB.
