State Pattern: Object-oriented Finite State Machine

Alan Turing :: 23 June 1912 – 7 June 1954 (aged 41)

Finite State Machine (FSM) được sử dụng rất rộng rãi trong software, nhất là khi chúng ta hay phải làm công việc sau:

Khi xảy ra event E, mà đang ở state S, thì thực hiện action A, rồi có thể chuyển sang state X (*)

Một implementation của FSM được gọi là tốt nếu nó thỏa mãn những yếu tố sau:

  • Logic chuyển đổi state phải dễ hiểu và đập vào mắt người đọc ngay sau vài nốt nhạc.
  • Chạy nhanh! FSM chủ yếu chậm ở khâu nhận diện event đang xảy ra là event nào, và state hiện tại là state nào. Thời gian chạy action không tính vì nó không thuộc FSM.
  • Dễ tái sử dụng và mở rộng. FSM chỉ nên chứa logic mà thôi, action nên được tách ra, và phải tách một cách linh hoạt để có thể thay thế action, ví dụ ta có thể dùng function pointer (C/C++), delegate (C#) hoặc interface / abstract class (Java).

Chúng ta sẽ xem xét những cách implementation FSM phổ biến.

Switch/case với enum

Đây là cách thường gặp nhất.

class FSM
{
private:
	enum State { STATE_A, ... };
	State m_currentState;

public:
	enum Event { EVENT_1, ... };

	void onEvent(Event e)
	{
		switch (m_currentState)
		{
			case STATE_A:
			{
				switch (e)
				{
					case EVENT_1: // gọi action, chuyển state nếu cần
				}
			}
			// và một đống tương tự
		}
	}
};

Ưu điểm của cách này là dễ code và nó chạy nhanh. Nếu hàm onEvent() có thể viết trên một trang màn hình, thì viết switch/case như vậy là đủ xài, vì logic của cả FSM vẫn có thể được nhận ra dễ dàng trên một trang.

Nhược điểm là nó không phù hợp với FSM lớn. Hàm onEvent() rất dễ bị phình ra và dàn trải trên nhiều trang. Tệ hơn (rất hay gặp) là action được code thẳng vào đây, khiến hàm onEvent() thành một đống bầy nhầy.

Data-driven với Transition Table

Switch/case có thể được loại bỏ nếu chúng ta biểu diễn các logic dưới dạng data (data-driven). Event, state được biểu diễn bằng enum; đối với action, có thể dùng pointer function, delegate, hoặc object với Command pattern.

Mỗi một phát biểu (*) được lưu trữ trong một struct gọi là Transition. FMS chỉ đơn giản chứa một dach sách các Transition và một biến state hiện tại. Khi một event xảy ra, FSM sẽ tìm trong danh sách để lấy ra transition tương ứng, gọi action, rồi chuyển sang state được lưu trong transition đó nếu có; không có ngoại lệ cho transition nào.

void action_1() { ... }

class FSM
{
public:
	enum Event { EVENT_1, ... };

private:
	enum State { STATE_NONE, STATE_A, STATE_B, ... };

	typedef void (*Action)();

	struct Transition
	{
		State currentState;
		Event event;
		State nextState;
		Action action;
	};

	enum { MAX = 1024 };
	Transition transitions[MAX];

	int m_count;
	State m_currentState;

public:
	void init()
	{
		m_count = 0;

		addTransition(STATE_A, EVENT_1, STATE_B, &action_1);
		addTransition(...);
		addTransition(...);
		...

		m_currentState = STATE_A;
	};

private:
	void addTransition(State currentState, Event event,
			State nextState, Action action)
	{
		Transition& t = transition[m_count];
		t.currentState = currentState;
		t.event = event;
		t.nextState = nextState;
		t.action = action;
		m_count++;
	}

public:
	void onEvent(Event e)
	{
		for (int i = 0; i < m_count; i++)
		{
			Transition& t = transition[i];
			if (t.event == e && t.currentState == m_currentState)
			{
				(*(t.action))();
				if (t.nextState != STATE_NONE)
					m_currentState = t.nextState;
			}
		}
	}
};

Cách này có nhiều ưu điểm do nó tổng quát. Logic của cả FSM được tập trung trong hàm init() nên rất dễ nắm bắt. Muốn sửa transition thì cứ vào init() mà sửa, thậm chí việc sửa này có thể diễn ra vào lúc run-time nếu muốn (hot swap).

Nhược điểm dễ thấy là nó chạy chậm vì cái vòng for.

Object-oriented với State Pattern

State pattern giải quyết việc xác định state hiện tại là state nào bằng tính đa hình của OOP. Các state lúc này không còn là enum nữa mà là các object cùng hiện thực một interface gọi là State. FSM giữ một tham chiếu kiểu State đại diện cho state hiện tại, mỗi khi event xảy ra, FSM sẽ bàn giao lại cho tham chiếu ấy.

State Pattern

Ưu điểm của State Pattern là nhanh (như switch/case) và dễ tái sử dụng FSM cho object Action khác. Các state và logic được tách vào các class riêng biệt, vừa hay lại vừa dở. Hay vì nó thỏa mãn Single Responsibility. Dở vì logic của FSM bị phân tán, nhưng đây là điều cần chấp nhận.

Advertisements

One thought on “State Pattern: Object-oriented Finite State Machine

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s