GIÁO TRÌNH LẬP TRÌNH HÀM
TS. PHAN HUY KHÁNH
NHÀ XUẤT BẢN KHOA HỌC VÀ KỸ THUẬT
LỜI NÓI ĐẦU
Cuốn
sách này trình bày cơ sở lý thuyết và những kỹ thuật lập trình cơ bản
theo phong cách «lập trình hàm» (Functional Programming). Đây là kết quả
biên soạn từ các giáo trình sau nhiều năm giảng dạy bậc đại học và sau
đại học ngành công nghệ thông tin của tác giả tại Đại học Đà Nẵng. Cuốn
sách gồm sáu chương có nội dung như sau:
Chương 1 giới thiệu quá trình phát triển và phân loại các ngôn ngữ lập
trình, những đặc điểm cơ bản của phong cách lập trình mệnh lệnh. Phần
chính của chương trình bày nhữngnguyên lý lập trình hàm sử dụng ngôn ngữ
minh hoạ Miranda.
Chương 2 trình bày những kiến thức mở đầu về ngôn ngữ Scheme: Các khái
niệm và các kiểu dữ liệu cơ sở, cách định nghĩa hàm, biểu thức, kỹ thuật
sử dụng đệ quy và phép lặp.
Chương 3 trình bày các kiểu dữ liệu phức hợp của Scheme như chuỗi,
vectơ, danh sách và cách vận dụng các kiểu dữ liệu trừu tượng trong định
nghĩa hàm.
Chương 4 trình bày những kiến thức nâng cao về kỹ thuật lập trình hàm,
định nghĩa hàm nhờ phép tính lambda, ứng dụng thuật toán quay lui,
truyền thông điệp...
Chương 5 trình bày chi tiết hơn kỹ thuật lập trình nâng cao với Scheme
sử dụng các cấu trúc dữ liệu: Tập hợp, ngăn xếp, hàng đợi, cây và tệp.
Chương 6 trình bày khái niệm môi trường, cách tổ chức và cấp phát bộ
nhớ, cách vào/ Ra dữ liệu của Scheme với thế giới bên ngoài.
Phần phụ lục giới thiệu vắn tắt ngôn ngữ lập trình WinScheme48, hướng
dẫn cách cài đặt và sử dụng phần mềm này. Cuốn sách này làm tài liệu t
khảo cho sinh viên các ngành công nghệ thông tin và những bạn đọc muốn
tìm hiểu thêm về kỹ thuật lập trình cho lĩnh vực trí tuệ nhân tạo, giao
tiếp hệ thống, xử lý ký hiệu, tính toán hình thức, các hệ thống đồ
hoạ... Trong suốt quá trình biên soạn, tác giả đã nhận được từ các bạn
đồng nghiệp nhiều đóng góp bổ ích về mặt chuyên môn, những động viên
khích lệ về mặt tinh thần, sự giúp đỡ tận tình về biên tập để cuốn sách
được ra đời. Do mới xuất bản lần đầu tiên, tài liệu tham khảo chủ yếu là
tiếng nước ngoài, chắc chắn rằng nội dung của cuốn sách vẫn còn bộc lộ
nhiều thiếu sót, nhất là các thuật ngữ dịch ra tiếng Việt. Tác giả xin
được bày tỏ ở đây lòng biết ơn sâu sắc về mọi ý kiến phê bình đóng góp
của bạn đọc gần xa. Đà Nẵng, ngày 06/09/2004
Tác giả.
PHAN HUY KHÁNH
CHƯƠNG I. NGUYÊN LÝ LẬP TRÌNH HÀM
I. 1 Mở đầu về ngôn ngữ lập trình
I. 1.1. Vài nét về lịch sử
I. 1.2. Định nghĩa một ngôn ngữ lập trình
I. 1.3. Khái niệm về chương trình dịch
I. 1.4. Phân loại các ngôn ngữ lập trình
I. 1.5. Ngôn ngữ lập trình mệnh lệnh
I. 2 Cơ sở của các ngôn ngữ hàm
I. 2.1. Tính khai báo của các ngôn ngữ hàm
I. 2.2. Định nghĩa hàm
I. 2.3. Danh sách
I. 2.4. Phép so khớp
I. 2.5. Phương pháp currying (tham đối hoá từng phần)
I. 2.6. Khái niệm về bậc của hàm
I. 2.7. Kiểu và tính đa kiểu
I. 2.8. Tính hàm theo kiểu khôn ngoan
I. 2.9. Một số ví dụ
1. Loại bỏ những phần tử trùng nhau
2. Sắp xếp nhanh quicksort
3. Bài toán tám quân hậu
4. Bài toán hamming
I. 3 Kết luận
CHƯƠNG II. NGÔN NGỮ SCHEME
II. 1 Giới thiệu Scheme
II. 2 Các kiểu dữ liệu của Scheme
II. 2.1. Các kiểu dữ liệu đơn giản
II. 2.1.1. Kiểu số
II. 2.1.2. Kiểu lôgích và vị từ
II. 2.1.3. Ký hiệu
II. 2.2. Khái niệm về các biểu thức tiền tố
II. 2.3. Sưbiểu thức
II. 3 Các định nghĩa trong Scheme
II. 3.1. Định nghĩa biến
II. 3.2. Định nghĩa hàm
II. 3.2.1. Khái niệm hàm trong Scheme
II. 3.2.2. Gọi hàm sau khi định nghĩa
II. 3.2.3. Sử dụng các hàm bổ trợ
II. 3.2.4. Tính không định kiểu của Scheme
II. 3.3. Cấu trúc điều khiển
II. 3.3.1. Dạng điều kiện if
II. 3.3.2. Biến cục bộ
1. Định nghĩa biến cục bộ nhờ dạng let
2. Phạm vi tự động của dạng let
3. Liên kết biến theo dãy: Dạng let*
II. 3.3.3. Định nghĩa các vị từ
II. 3.4. Sơ đồ đệ quy và sơ đồ lặp
II. 3.4.1. Sơ đồ đệ quy
II. 3.4.2. Ví dụ
1. Tính tổng bình phương các số từ 1 đến n
2. Tính giai thừa
3. Hàm fibonacci
4. Tính các hệ số nhị thức
II. 3.4.3. Tính dừng của lời gọi đệ quy
II. 3.4.4. Chứng minh tính dừng
II. 3.4.5. Sơ đồ lặp
II. 3.5. Vào/ Ra dữ liệu
1. Đọc vào dữ liệu: Read
2. In ra dữ liệu: Write và display
3. Xây dựng vòng lặp có menu
CHƯƠNG III. KIỂU DỮ LIỆU PHỨC HỢP
III. 1 Kiểu chuỗi
III. 2 Kiểu dữ liệu vectơ
III. 3 Kiểu dữ liệu bộ đôi
III. 3.1. Khái niệm trừu tượng hoá dữ liệu
III. 3.2. Định nghĩa bộ đôi
III. 3.3. Đột biến trên các bộ đôi
III. 3.4. Ứng dụng bộ đôi
1. Biểu diễn các số hữu tỷ
2. Biểu diễn hình chữ nhật phẳng
III. 4 Kiểu dữ liệu danh sách
III. 4.1. Khái niệm danh sách
III. 4.2. Ứng dụng danh sách
III. 4.2.1. Các phép toán cơ bản cons, list, car và cdr
III. 4.2.2. Các hàm xử lý danh sách
1. Các hàm length, append và reverse
2. Các hàm tham chiếu danh sách
3. Các hàm chuyển đổi kiểu
4. Các hàm so sánh danh sách
III. 4.2.3. Dạng case xử lý danh sách
III. 4.2.4. Kỹ thuật đệ quy xử lý danh sách phẳng
1. Tính tổng các phần tử của một danh sách
2. Danh sách các số nguyên từ 0 đến n
3. Nghịch đảo một danh sách
4. Hàm append có hai tham đối
5. Loại bỏ các phần tử khỏi danh sách
6. Bài toán tính tổng con
7. Lập danh sách các số nguyên tố
III. 4.2.5. Kỹ thuật đệ quy xử lý danh sách bất kỳ
1. Làm phẳng một danh sách
2. Tính tổng các số có mặt trong danh sách
3. Loại bỏ khỏi danh sách một phần tử ở các mức khác nhau
4. Nghịch đảo danh sách
5. So sánh bằng nhau
III. 4.3. Biểu diễn danh sách
III. 4.3.1. Biểu diễn danh sách bởi kiểu bộ đôi
III. 4.3.2. Danh sách kết hợp
1. Khái niệm danh sách kết hợp
2. Sử dụng danh sách kết hợp
III. 4.3.3. Dạng quasiquote
III. 4.4. Một số ví dụ ứng dụng danh sách
1. Tìm phần tử cuối cùng của danh sách
2. Liệt kê các vị trí một ký hiệu có trong danh sách
3. Tìm tổng con lớn nhất trong một vector
4. Bài toán sắp xếp dãy viên bi ba màu
5. Sắp xếp nhanh quicksort
CHƯƠNG IV. KỸ THUẬT XỬ LÝ HÀM
IV. 1 Sử dụng hàm
IV. 1.1. Dùng tên hàm làm tham đối
IV. 1.2. Áp dụng hàm cho các phần tử của danh sách
IV. 1.3. Kết quả trả về là hàm
IV. 2 Phep tính lambda
IV. 2.1. Giới thiệu phép tính lambda
IV. 2.2. Biễu diễn biểu thức lambda trong Scheme
IV. 2.3. Định nghĩa hàm nhờ lambda
IV. 2.4. Kỹ thuật sử dụng phối hợp lambda
IV. 2.5. Định nghĩa hàm nhờ tích luỹ kết quả
1. Tính tổng giá trị của một hàm áp dụng cho các phần tử danh sách
2. Tính tích giá trị của một hàm áp dụng cho các phần tử danh sách
3. Định nghĩa lại hàm append ghép hai danh sách
4. Định nghĩa lại hàm map cho hàm một biến h
5. Định nghĩa các hàm fold
IV. 2.6. Tham đối hoá từng phần
IV. 2.7. Định nghĩa đệ quy cục bộ
IV. 3 Xử lý trên các hàm
IV. 3.1. Xây dựng các phép lặp
1. Hàm appendưmap
2. Hàm mapưselect
3. Các hàm every và some
IV. 3.2. Trao đổi thông điệp giữa các hàm
IV. 3.3. Tổ hợp các hàm
IV. 3.4. Các hàm có số lượng tham đối bất kỳ
IV. 4 Một số ví dụ
IV. 4.1. Phương pháp xấp xỉ liên tiếp
IV. 4.2. Tạo thủ tục định dạng
IV. 4.3. Xử lý đa thức
IV. 4.3.1. Định nghĩa đa thức
IV. 4.3.2. Biễu diễn đa thức
IV. 4.3.3. Xử lý đa thức
1. Nhân đa thức với một hằng số
2. So sánh hai đa thức
3. Phép cộng đa thức
4. Phép nhân hai đa thức
IV. 4.3.4. Biễu diễn trong một đa thức
IV. 4.3.5. Đưa ra đa thức
IV. 4.4. Thuật toán quay lui
IV. 4.4.1. Bài toán tám quân hậu
IV. 4.4.2. Tìm kiếm các lời giải
IV. 4.4.3. Tổ chức các lời giải
CHƯƠNG V. CẤU TRÚC DỮ LIỆU
V. 1 Tập hợp
1. Phép hợp trên các tập hợp
2. Phép giao trên các tập hợp
3. Phép hiệu của hai tập hợp
4. Tìm các tập hợp con của một tập hợp
V. 2 Ngăn xếp
V. 2.1. Kiểu dữ liệu trừu tượng ngăn xếp
V. 2.2. Xây dựng ngăn xếp
V. 2.3. Xây dựng trình soạn thảo văn bản
V. 2.4. Ngăn xếp đột biến
V. 2.5. Tính biểu thức số học dạng hậu tố
V. 3 Tệp
V. 3.1. Cấu trúc dữ liệu trừu tượng kiểu tệp
V. 3.2. Ví dụ áp dụng tệp
V. 3.3. Tệp đột biến
V. 4 Cây
V. 4.1. Cây nhị phân
V. 4.1.1. Kiểu trừu tượng cây nhị phân
V. 4.1.2. Biểu diễn cây nhị phân
1. Biểu diễn tiết kiệm sử dụng hai phép cons
2. Biểu diễn dạng đầy đủ
3. Biểu diễn đơn giản
V. 4.1.3. Một số ví dụ lập trình đơn giản
1. Đếm số lượng các nút có trong một cây
2. Tính độ cao của một cây
V. 4.1.4. Duyệt cây nhị phân
V. 4.2. Cấu trúc cây tổng quát
V. 4.2.1. Kiểu trừu tượng cây tổng quát
V. 4.2.2. Biểu diễn cây tổng quát
1. Biểu diễn cây nhờ một bộ đôi
2. Biểu diễn cây đơn giản qua các lá
V. 4.2.3. Một số ví dụ về cây tổng quát
1. Đếm số lượng các nút trong cây
2. Tính độ cao của cây
V. 4.2.4. Duyệt cây tổng quát không có xử lý trung tố
V. 4.3. Ứng dụng cây tổng quát
V. 4.3.1. Xây dựng cây cú pháp
V. 4.3.2. Ví dụ: Đạo hàm hình thức
CHƯƠNG VI. MÔI TRƯỜNG VÀ CẤP PHÁT BỘ NHỚ
VI. 1 Môi trường
VI. 1.1. Một số khái niệm
VI. 1.2. Phạm vi của một liên kết
VI. 1.2.1. Phạm vi tĩnh
VI. 1.2.2. Phép đóng = biểu thức lambda + Môi trường
VI. 1.2.3. Thay đổi bộ nhớ và phép đóng
VI. 1.2.4. Nhận biết hàm
VI. 1.2.5. Phạm vi động
VI. 1.3. Thời gian sống của một liên kết
VI. 1.4. Môi trường toàn cục
VI. 2 Cấp phát bộ nhớ
VI. 2.1. Ví dụ 1: Mô phỏng máy tính bỏ túi
VI. 2.2. Ví dụ 2: Bài toán cân đối tài khoản
VI. 3 Mô hình sử dụng môi trường
VI. 4 Vào/ Ra dữ liệu
VI. 4.1. Làm việc với các tệp
VI. 4.2. Đọc dữ liệu trên tệp
1. Các hàm đọc tệp
2. Tệp văn bản
VI. 4.3. Ghi lên tệp
1. Các hàm ghi lên tệp
2. Lệnh sao chép tệp
VI. 4.4. Giao tiếp với hệ thống
PHỤ LỤC
TÀI LIỆU THAM KHẢO
Nhận xét
Đăng nhận xét