Mọi thứ đều là hàm: Cảm nhận sau khóa học SICP với David Beazley
(ezzeriesa.notion.site)Cảm nhận sau khóa học SICP với David Beazley: trải nghiệm trong 1 tuần
Chia sẻ trải nghiệm tham gia khóa học SICP của David Beazley vào cuối năm 2022. Dù có nhiều tài liệu miễn phí, khóa học của Dave đặc biệt hiệu quả nhờ chọn lọc các chủ đề cụ thể và giải thích chúng một cách sâu sắc.
Điểm khởi đầu
Khóa học SICP được giảng dạy bằng ngôn ngữ Scheme, và tại đây người học triển khai một trình thông dịch Scheme đơn giản bằng Python để giải thích mô hình thế (substitution), một khái niệm nền tảng.
Cơ bản về ngôn ngữ Scheme
- Primitive: các giá trị cơ bản (ví dụ: số nguyên)
- Toán tử: dùng các phép toán cơ bản như
+,-,*,/dưới dạng ký pháp tiền tố - define: định nghĩa biến
> (define x 2)
> (+ x 3) ; kết quả: 5
- if: câu lệnh điều kiện
- lambda: định nghĩa hàm ẩn danh
> ((lambda (x) (* x x)) 3) ; kết quả: 9
Trình thông dịch Scheme trong Python
Triển khai một trình thông dịch đơn giản để đánh giá mã Scheme bằng Python. Các phép toán cơ bản được định nghĩa bằng hàm Python.
definitions = {
"+": lambda x, y: x + y,
"*": lambda x, y: x * y,
}
Ví dụ:
> evaluate(("+", 2, 3)) # kết quả: 5
Ngoài ra còn bao gồm việc hiện thực define, lambda, và cả xử lý câu điều kiện if.
Mô hình thế (Substitution Model)
Mô hình thế là cách diễn giải chương trình đơn giản, trong đó chương trình được đánh giá bằng cách thay biến bằng giá trị. Tuy nhiên, khi có gán giá trị (assignment) thì mô hình này không còn đúng nữa.
Trạng thái (State)
Một ví dụ cho việc mô hình thế bị phá vỡ là gán giá trị (assignment). Chẳng hạn, khi mô hình hóa số dư tài khoản ngân hàng, ta cập nhật biến bằng set!.
(define balance 100)
(define (withdraw amount)
(set! balance (- balance amount))
balance)
Trong trường hợp này, mô hình thế không thể phân biệt được trạng thái số dư trước và sau đó.
Khi ấy cần đến mô hình môi trường (Environment). Biến được định nghĩa trong môi trường, và mỗi thủ tục có môi trường riêng của nó.
Stream
Một cách khác để mô hình hóa trạng thái là dùng stream. Stream có thể mô hình hóa cả các giá trị trong tương lai thông qua đánh giá trì hoãn (lazy evaluation).
Vòng lặp vô hạn và thứ tự đánh giá
Sự khác biệt về thứ tự đánh giá: hầu hết ngôn ngữ dùng applicative-order evaluation, tức là đánh giá đối số trước.
> (square (+ 1 2)) ; kết quả: 9
Tuy nhiên, normal-order evaluation trì hoãn việc đánh giá cho đến khi đối số thực sự cần thiết. Nhờ đó có thể tránh được vòng lặp vô hạn.
> (define (p) (p))
> (define (test x y) (if (= x 0) 0 y))
> (test 0 (p)) ; với normal-order trả về 0, với applicative-order thì lặp vô hạn
Lambda calculus và số Church
Thông qua Church encoding, có thể biểu diễn số dưới dạng thủ tục (procedure). Đây là một khái niệm quan trọng trong lập trình hàm.
(define (zero f) (lambda (x) x))
(define (increment n) (lambda (f) (lambda (x) (f ((n f) x)))))
zerolà hàm trả nguyên đối số (identityfunction).incrementáp dụng thêm một lần gọi hàm.
Ví dụ
> ((zero (lambda (x) (+ x 1))) 0) ; kết quả: 0
> (((increment zero) (lambda (x) (+ x 1))) 0) ; kết quả: 1
Lặp vs đệ quy
Scheme dùng đệ quy thay cho vòng lặp for để thực hiện các tác vụ lặp lại.
Ví dụ đệ quy: giai thừa
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
Lời gọi đệ quy này có thể dùng stack và tiêu tốn khá nhiều bộ nhớ.
Tối ưu tail-call
Scheme giảm mức sử dụng bộ nhớ thông qua tối ưu tail-call. Nhờ vậy, nó hoạt động giống một tiến trình lặp (iterative) hơn.
(define (factorial n)
(define (iter product counter)
(if (> counter n)
product
(iter (* product counter) (+ counter 1))))
(iter 1 1))
Kết luận
Khóa học của David Beazley chọn ra các khái niệm cốt lõi của SICP và đào sâu chúng. Đặc biệt, nó giúp hiểu rõ hơn nhiều mô hình lập trình khác nhau như lập trình hàm, lambda calculus và thứ tự đánh giá.
Trích dẫn của Knuth
Nếu chỉ học lý thuyết, điều đó có nghĩa là đã đến lúc tập trung vào phần thực hành; còn nếu chỉ làm thực hành, điều đó có nghĩa là đã đến lúc tập trung vào phần lý thuyết.
1 bình luận
Ý kiến trên Hacker News
Bài giảng SICP có mật độ thông tin cao, nhưng cũng tốn nhiều thời gian do phần hỏi đáp của sinh viên và việc sử dụng bảng. Thứ tự bài giảng cũng có thể được sắp xếp lại. Cá nhân tôi đang dự định thực hiện một loạt video mới
Giới thiệu cách mã hóa trạng thái thành hàm thuần. Có nhiều kiểu mã hóa hàm thuần cho các loại dữ liệu khác nhau
Do anchor/hash trong URL của bài blog nên tôi bị chuyển thẳng đến phần tái bút, khá khó hiểu
Lần đầu thấy cons/car/cdr được triển khai bằng lambda, tôi cảm giác như phép thuật. Điều này cho thấy runtime của ngôn ngữ cần phải triển khai từ điển khóa/giá trị
David Beazley là một nhân vật huyền thoại trong thế giới Python, và bài giảng này lúc đầu khá bất ngờ nhưng rồi tôi thấy đó là một sự kết hợp hoàn hảo. Tôi đã đăng ký bài giảng tiếp theo
Tôi đã tiếp cận khái niệm rằng cần có kiểu dữ liệu quy nạp. Chỉ riêng Church encoding thì không thể chứng minh các mệnh đề như
0 != 1Bản thân bài viết khá thú vị, nhưng việc điều hướng trang lại khó khăn. Không thể cuộn bằng phím mũi tên trên bàn phím
Có lỗi gõ nhầm trong đoạn mã ở mục "mô hình thay thế". Cần dùng
fibonaccithay vìfib. Mã trong kho lưu trữ GitHub là đúngCó một liên kết nơi đang diễn ra thảo luận về cuốn sách. Tôi thắc mắc vì sao liên kết lại dẫn thẳng đến phần thảo luận ở cuối trang. Cũng tò mò liệu nó có thể được gộp vào thảo luận khác hay không
Có cung cấp liên kết YouTube