23 July, 2024

Functional Programming là gì?

Khám phá Functional Programming bằng cách vận dụng nó vào một bài toán thực tế

Available in:

Vietnamese

Reading time: 20 min.

Table of content

Functional Programming (viết tắt là FP, dịch sang tiếng Việt: "lập trình hàm"), là một phương pháp lập trình vận dụng các lý thuyết về hàm số trong toán học. Nghe thì khá là to tát và khó hiểu, nhưng thực tế chúng ta gặp FP ở khắp mọi nơi mà không để ý tới.

Nhiều lập trình viên cho rằng, vì code base của họ hoàn toàn dùng các class, nên họ dùng OOP (Object-oriented Programming - Lập trình hướng đối tượng) chứ không dùng FP. Tuy vậy, không phải ta không dùng, mà chỉ là vô tình dùng nhưng không hiểu rõ.

Vậy Functional Programming thực chất là gì? Trong bài viết này, chúng ta sẽ thử vận dụng cách tư duy theo kiểu toán học để giải một bài toán thực tiễn.

Tôi không sợ người lập trình 10.000 phần mềm chỉ một lần, mà tôi sợ người luyện tập lập trình một phần mềm 10.000 lần

Đề bài: Game Rắn Săn Mồi

Game Rắn Săn Mồi trên Nokia huyền thoại thì không phải giới thiệu nhiều rồi. Đề bài của mình chỉ đơn giản như sau:

Màn hình được chia làm 25x25 ô bằng nhau
Game bắt đầu bằng con rắn với độ dài 3 ô
Mỗi khi ăn được con mồi, số điểm sẽ tăng thêm 1 và rắn cũng dài thêm 1 ô
Nếu chạm vào rìa màn hình, rắn sẽ "quay lại" từ phía đối diện (còn gọi là wrap screen)
Rắn chết nếu tự cắn vào mình

Cách làm "ngây thơ"

Cách làm đơn giản nhất đó là: lên google tìm "simple snake game js"

Mình tìm được khá nhiều các trang khác nhau, nhưng phương pháp chung thì na ná nhau thế này:

var grid = 16; // chiều dài và rộng của một ô, tính bằng pixel

var snake = {
  x: 160,
  y: 160,

  // hướng đi của con rắn
  // có thể đổi dấu dx, dy tùy vào hướng hiện tại
  dx: grid,
  dy: 0,

  // lưu tất cả các ô mà con rắn đang ở
  cells: [],

  // số lượng ô mà con rắn đang có
  maxCells: 3
};

var food = {
  x: 320,
  y: 320
};

Logic nôm na như sau:

Khi con rắn di chuyển, thì các phần tử trong cells sẽ thay đổi, cụ thể là:
- Toạ độ mới của đầu rắn sẽ được thêm vào cells
- Toạ độ cũ nhất (đuôi) sẽ bị xóa bỏ
x và y là tọa độ đầu rắn
food chứa tọa độ của con mồi
Nếu rắn ăn con mồi, thì maxCells tăng
Nếu có nút được bấm, thì dx và dy sẽ thay đổi tùy theo nút bấm là lên, xuống, phải hay trái

Tuy cách này chạy, nhưng nó có các vấn đề sau:

Các tọa độ đều dùng đơn vị pixel, nhưng tọa độ thực của rắn có đơn vị tính bằng ô (một ô bằng nhiều pixel)
Nhiều biến dữ liệu thừa thãi (sẽ giải thích ở phần sau), code phải đồng bộ giữa các biến đó

Sắp xếp lại dữ liệu

Yếu tố quan trọng đầu tiên của Functional Programming, đó là tối giản danh sách các biến đầu vào, tránh sự trùng lặp thông tin.

Cách làm "ngây thơ" ở phần trên có nhiều biến dữ liệu thừa thãi, ví dụ như:

x và y là tọa độ đầu rắn, nhưng rõ ràng cells cũng có thông tin này rồi
maxCells có thể được tính bằng độ dài của cells, hay cells.length
dx và dy thực chất có thể thay thế bằng 1 biến duy nhất snakeDirection, nhận 1 trong 4 giá trị: lên, xuống, phải hoặc trái

Như vậy, bài toán của chúng ta chỉ còn lại 3 biến:

snakeCells: lưu tất cả các ô mà con rắn đang ở
snakeDirection: nhận 1 trong 4 giá trị: lên, xuống, phải hoặc trái
food: lưu tọa độ của con mồi

Lưu ý thêm: Tất cả các tọa độ trong logic tính toán sẽ dùng đơn vị ô (giá trị từ 0 đến 24) thay vì đơn vị pixel. Việc chuyển giữa tọa độ ô sang pixel sẽ được thực hiện bằng một hàm cụ thể (sẽ giải thích ở sau)

Sắp xếp lại logic

Yếu tố tiếp theo cần quan tâm trong Functional Programming, đó là xác định sự phục thuộc lẫn nhau của các phần logic.

Một hàm số toán học cơ bản nhất có thể viết như sau:

y = f(x)

Bây giờ, ta muốn "mô hình hóa" sự phụ thuộc lẫn nhau giữa các dữ liệu theo dạng toán học.

Ví dụ từ phần trước, ta biết rằng điểm số (score) thì luôn phụ thuộc vào độ dài của con rắn:

score = f(cells.length)

Ta biết ban đầu con rắn dài 3 ô, vậy nên ta sẽ không tính 3 ô này. Hàm số f(x) phía trên đơn giản chỉ là:

function f(cells) {
  return cells.length - 3;
}
score = f(cells);

Để dễ nhớ, có thể gọi hàm f(x) phía trên là getScore:

function getScore(snakeCells) {
  return snakeCells.length - 3;
}

LƯU Ý: có thể bạn sẽ tự hỏi, điểm khá biệt giữa cách phía trên so với việc đóc trực tiếp snakeCells ở bên ngoài là gì. Ví dụ:

var snakeCells = ...;

// Cách làm KHÔNG ĐÚNG
// snakeCells được đọc từ bên ngoài, chứ không truyền vào thành đối số
function getScore() {
  return snakeCells.length - 3;
}

Tuy nhiên, đây không phải là một hàm thuần (pure function), vì getScore bị phụ thuộc vào một biến số môi trường, chứ không phải đối số. Nói cách khác, vì getScore phụ thuộc vào snakeCells, nên snakeCells phải là đối số của hàm.

Tuy vậy, nếu biến là một hàm số (const) thì điều này không sao:

const SPAWN_CELLS = 3;
// Đúng, vì SPAWN_CELLS không bao giờ thay đổi
function getScore(snakeCells) {
  return snakeCells.length - SPAWN_CELLS;
}

Logic di chuyển rắn

Tương tự cách suy luận phía trên, ta có thể xây dựng các logic cần cho việc di chuyển con rắn.

Ví dụ như ta có thể lấy tọa độ đầu con rắn bằng cách lấy phần tử cuối cùng của snakeCells:

function getCurrentHead(snakeCells) {
  return snakeCells[snakeCells.length - 1];
}

Sau đó di chuyển đầu con rắn dựa theo snakeDirection, ta tính newHead là vị trí mới của đầu rắn:

function getNewHead(currentHead, snakeDirection) {
  if (snakeDirection == 'r') { // right
    return { x: currentHead.x + 1, y: currentHead.y };
  } else if (snakeDirection == 'l') { // left
    return { x: currentHead.x - 1, y: currentHead.y };
  } else if (snakeDirection == 'u') { // up
    return { x: currentHead.x, y: currentHead.y - 1 };
  } else if (snakeDirection == 'd') { // down
    return { x: currentHead.x, y: currentHead.y + 1 };
  }
}

Nhưng nhỡ đầu rắn đi ra ngoài màn hình thì sao? Đơn giản, ta chỉ cần check xem tọa độ có bị mang dấu âm, hoặc có ra khỏi số ô tối đa không:

function wrapScreen(cell) {
  // nếu x, y ra ngoài màn hình, ta đưa nó trở lại phía đối diện
  return {
    x: cell.x < 0 ? grid-1 : (cell.x % grid),
    y: cell.y < 0 ? grid-1 : (cell.y % grid),
  };
}

Ngoài ra, chúng ta cũng cần hàm để kiểm tra xem đầu rắn có đang "cắn" phải thân của nó không:

function isEatingSelf(snakeCells, newHead) {
  // i = 1 là để bỏ qua ô cuối cùng ở đuôi con rắn
  for (let i = 1; i < snakeCells.length; i++) {
    if (newHead.x == snakeCells[i].x && newHead.y == snakeCells[i].y) {
      return true;
    }
  }
  return false;
}

Bây giờ, ta cần hàm để thay đổi snakeCells, bằng cách xóa phần tử cuối và thêm phần tử mới (giá trị lấy từ getNewHead):

// Cách làm SAI
function getNewSnake(snakeCells, newHead) {
  snakeCells.shift(); // xóa phần tử ở đuôi rắn
  snakeCells.push(newHead); // thêm phần tử ở đầu rắn
}

Nhưng vì sao cách làm trên là không đúng? Vì các hàm shift và push sẽ thay đổi giá trị của biến snakeCells, vốn là biến đầu vào.

QUAN TRỌNG: Trong FP, hàm không bao giờ được thay đổi trực tiếp giá trị của biến đầu vào. Nếu muốn thay đổi, nó phải tạo bản copy

// Cách làm ĐÚNG
function getNewSnake(snakeCells, newHead) {
  const newSnake = [...snakeCells]; // tạo bản copy
  newSnake.shift(); // xóa phần tử ở đuôi rắn
  newSnake.push(newHead); // add next cell
  return newSnake; // trả lại bản copy đã thay đổi
}

Thực tế, chúng ta sẽ chỉ cần xóa phần tử ở đuôi rắn nếu con rắn đang di chuyển. Nếu rắn ăn con mồi, thì ta không xóa, vậy là rắn tự nhiên sẽ dài thêm một đoạn:

function getNewSnake(snakeCells, newHead, isLonger) {
  const newSnake = [...snakeCells]; // tạo bản copy
  if (!isLonger) {
    // nếu ta KHÔNG muốn rắn dài thêm, ta xóa phần tử ở đuôi rắn
    newSnake.shift();
  }
  newSnake.push(newHead); // add next cell
  return newSnake; // trả lại bản copy đã thay đổi
}

Logic cho con mồi

Bắt đầu bằng hàm đơn giản: check xem đầu con rắn có đang ăn con mồi không:

function isEatingFood(food, newHead) {
  return newHead.x == food.x && newHead.y == food.y;
}

Bây giờ ta cần tạo vị trí ngẫu nhiên cho con mồi. Ở cách làm "ngây thơ" phía trên, người ta chỉ chọn bừa và nếu tọa độ lỡ rơi vào điểm trên thân con rắn, thì chúng ta lấy điểm khác.

Tuy vậy, cách làm "ngây thơ" sẽ gặp vấn đề khi con rắn càng to ra: Tổng số ô còn trống sẽ giảm đi. Tới một lúc nào đó, thuật toán sẽ phải random rất nhiều điểm, nhưng toàn rơi trúng vào ô có chứa thân con rắn. Độ phức tạp sẽ tăng dần thành gần O(N^2), game sẽ có thể bị lag.

Để giải quyết vấn đề này, ta sẽ chủ động tìm tất cả các ô trống trên màn hình. Thuật toán sau của mình dùng từ điển, nên sẽ chỉ có độ phức tạp là O(N*log(N)):

function getEmptyCells(snakeCells) {
  const cells = {};
  // liệt kê tất cả các ô có thể trên màn hình
  for (let y = 0; y < grid; y++) {
    for (let x = 0; x < grid; x++) {
      cells[`${x}_${y}`] = { x, y };
    }
  }
  // xóa các ô đã bị chiếm bởi con rắn
  for (const cell of snakeCells) {
    delete cells[`${cell.x}_${cell.y}`];
  }
  // các ô còn lại là các ô trống, ta quy đổi từ điển thành một mảng (array)
  return Object.values(cells);
}

Và sau đó, ta chỉ đơn giản là chọn ngẫu nhiên một trong các ô trống:

function getNewFood(emptyCells) {
  // lấy random một ô từ mảng
  return emptyCells[Math.floor(Math.random()*emptyCells.length)];
}

Logic cho phần render

Trong lập trình đồ họa, thuật ngữ "render" có thể hiểu như động tác quy đổi "dữ liệu" thành dạng "hiển thị". Việc tách biệt dữ logic "dữ liệu" và logic "hiển thị" giúp cho cấu trúc phần mềm phân hóa hơn, dễ khoanh vùng khi có lỗi xảy ra.

Ví dụ trong bài toán này, vì mọi logic tính toán đều dùng tọa độ theo ô (giá trị từ 0 đến 24), ta cần hàm render để quy đổi ra đơn vị pixel và vẽ ra ngoài canvas:

function render(snakeCells, food) {
  context.clearRect(0, 0, canvas.width, canvas.height);
  // vẽ con mồi
  context.fillStyle = 'red';
  context.fillRect(food.x*pixelPerCell, food.y*pixelPerCell, pixelPerCell - 1, pixelPerCell - 1);
  // vẽ con rắn, từng ô một
  for (const cell of snakeCells) {
    context.fillStyle = 'green';
    context.fillRect(cell.x*pixelPerCell, cell.y*pixelPerCell, pixelPerCell - 1, pixelPerCell - 1);
  }
}

Với pixelPerCell có thể chỉnh sửa tùy ý mà không ảnh hưởng gì tới logic còn lại của game.

Lắp ráp tất cả lại

Sau khi lắp ráp tất cả các phần phía trên lại, ta được một logic dễ hiểu ngay từ trong code:

const currentHead = getCurrentHead(snakeCells);
const newHead = getNewHead(currentHead, snakeDirection);

// check xem rắn có đang tự cắn mình không
if (isEatingSelf(snakeCells, newHead)) {
  alert(`Game over! Score: ${getScore(snakeCells)}`);
  snakeCells = null; // reset game
  return;
}

if (isEatingFood(food, newHead)) {
  // nếu rắn đang ăn con mồi, nối dài nó thêm một đoạn
  snakeCells = getNewSnake(snakeCells, newHead, true);
  const emptyCells = getEmptyCells(snakeCells);
  food = getNewFood(emptyCells);
} else {
  // nếu rắn không ăn con mồi, ta chỉ di chuyển rắn
  snakeCells = getNewSnake(snakeCells, newHead, false);
}

// gọi hàm render để vẽ rắn và con mồi ra màn hình
render(snakeCells, food);

Để xem code đầy đủ, hãy bấm vào đây

Chơi thử dưới này:

Nâng cao hơn

Không chỉ dừng lại ở việc "làm cho nó chạy". Khi bạn đã thuần thục lối tư duy này, có rất nhiều thứ bạn có thể áp dụng để làm đơn giản hóa các phần mềm phức tạp:

Testing

Đối với việc kiểm thử (testing), do các hàm luôn luôn trả lại một tập giá trị cố định, nên các bạn có thể test từng hàm riêng biệt mà không cần phải "dựng lại" tất cả các biến dữ liệu. Ví dụ:

assert(isEatingFood({ x: 7, y: 8 }, { x: 7, y: 8 }) === true);
assert(isEatingFood({ x: 1, y: 2 }, { x: 7, y: 8 }) === false);

Với các hàm mang tính ngẫu nhiên như getNewFood, bạn có thể tự thêm một hàm fake random (tức nó luôn trả lại một giá trị xác định), và đưa nó vào thành một input của getNewFood

function realRandom() {
  return Math.random();
}

function fakeRandom() {
  return 0;
}

function getNewFood(emptyCells, randomFunction) {
  return emptyCells[Math.floor(randomFunction()*emptyCells.length)];
}

// in game
getNewFood(emptyCells, realRandom);

// in test
getNewFood(emptyCells, fakeRandom);

Hàm thứ bậc cao (higher-order function)

Thực ra thì phía trên mình vừa mới lỡ tay giải thích luôn Higher-Order Function (HOF) là gì rồi.

Hàm getNewFood chấp nhận đối số là một hàm khác, randomFunction. Vậy nên, getNewFood là hàm bậc cao hơn so với randomFunction.

Ý tưởng này thường được sử dụng rộng rãi trong array.map hay array.filter, vốn có chấp nhận một hàm từ phía người dùng làm đối số.

Hàm hợp (composed function)

Đây là một ý tưởng khá mạnh mẽ trong toán học, nhưng mãi về sau mình mới biết là nó có áp dụng vào trong FP. Ví dụ nếu bạn có 2 hàm f(x) và g(x), thì tồn tại một hàm h(x) thỏa mãn:

h(x) = (f ∘ g)(x)

Ý tưởng này thoạt đầu nghe vô nghĩa, nhưng thực ra nó rất hữu dụng nếu f(x) và g(x) đều là 2 hàm tính toán nhiều bước (ví dụ 2 vòng lặp chẳng hạn). Gộp chúng lại thì có thể sẽ chỉ còn một vòng lặp (có thể: là chỉ khi bạn tìm ra cách tối ưu).

Một ví dụ điển hình cho tối ưu này là ở các thư viện Machine Learning hiện đại. Đôi khi, việc tính toán ma trận A nhân ma trận B thì sẽ cần phải tính chuyển vị (transpose) của B. Mình lấy ví dụ với thư viện ggml trên ngôn ngữ C:

// C = A nhân chuyển vị của B
C = ggml_mul_mat_slow(A, ggml_transpose(B));

Tuy cách này chạy ổn, nhưng về lâu dài nó tốn rất nhiều thời gian, vì 10 lần thì đến 9 lần người dùng cần chuyển vị trước khi nhân. Vậy nên thực tế, ta có thể tìm ra một hàm mới ggml_mul_mat nhận luôn đối số là ma trận B chưa chuyển vị:

// f = ggml_mul_mat_slow
// g = ggml_transpose
// h = (f ∘ g) = ggml_mul_mat
// B không cần chuyển vị nữa
C = ggml_mul_mat(A, B);

Điểm đặc biệt là, bên trong ggml_mul_mat KHÔNG HỀ gọi ggml_transpose, mà nó chỉ đơn giản là đảo thứ tự các phép tính. Vậy nên, độ phức tạp giảm đi còn một nửa, code chạy nhanh hơn nhiều.

Kết lại

Như vậy, qua bài viết, chúng ta đã tìm hiểu về Functional Programming, hướng tư duy lập trình dùng hàm số toán học.

Trên thực tế, không có một phần mềm nào là thuần FP hay thuần OOP cả. Một phần mềm mạnh mẽ là phần mềm biết sử dụng điểm mạnh của cả FP lẫn OOP.

Ví dụ, với thư viện Angular, class được dùng để lưu trữ trạng thái (view state), sau đó khi cần hiển thị ra ngoài màn hình, thì quá trình render sẽ được thực hiện. Quá trình render này dựa trên tư duy FP khá nhiều.

Một ví dụ khác, khi bạn chơi game, thực ra bộ đổ bóng của GPU (shader) lấy một hàm và thực hiện song song hàm đó trên nhiều dữ liệu cùng một lúc. Điều này giúp thực hiện các phép tính toán ma trận nhanh hơn nhiều so với dùng CPU, nhờ đó mà ta sử dụng được đồ họa 2D/3D một cách mượt mà. Các hàm này đều được thiết kế theo tư duy FP.

Hy vọng các bạn thấy bài viết này hữu ích!