A stack-based programming language: Cat

Ngôn ngữ lập trình stack-based (hay stack-oriented) là loại ngôn ngữ sử dụng stack để thực hiện các thao tác và tính toán. Một ví dụ cụ thể mà bạn có thể tìm thấy trong blog này là ngôn ngữ MSIL (CIL) mà tôi đã có một số bài hướng dẫn về nó tại đây.  Trong bài viết này tôi sẽ giới thiệu một ngôn ngữ stack-based đơn giản kèm mã nguồn C#. Đây sẽ là cơ sở để ta tạo ra một trình thông dịch đơn giản cho một ngôn ngữ lập trình của riêng bạn.

Giới thiệu

Có một vài ngôn ngữ lập trình sử dụng cơ chế stack-based này ngoài CIL như mã bytecode của Java, ForthRPLPostScript. Trong bài viết này, tôi sẽ sử dụng ngôn ngữ Cat. Xin trích dẫn một phần giới thiệu về ngôn ngữ này. Bạn có thể xem đầy đủ tại đây. Tôi không có ý định biến bài viết này thành một bài hướng dẫn mà chỉ đơn giản là giới thiệu để bạn có thể biết và hiểu được những cơ chế và khái niệm cơ bản của một ngôn ngữ stack-based. Để dễ hiểu bạn cũng thể liên tưởng đến kĩ thuật tương tự sử dụng stack để tính toán như ký pháp nghịch đảo Ba Lan, cơ chế của chúng là như nhau.

Cat is a high-level intermediate language that can also be used as a stand-alone language for simple application development. In this way it occupies a similar niche to PostScript. Cat is also an appropriate language for teaching of basic programming concepts.

Cat is designed and being developed by Christopher Diggins, who studies at the University of Montreal with Marc Feeley and Stefan Monnier.

Để làm các ví dụ mà tôi sẽ trình bày bên dưới, bạn có thể dùng trình thông dịch Online Cat Interpreter (v 1.3) được cài đặt bằng javascript hoặc tải về phiên bản stand-alone Cat interpreter 1.0 beta 4 kèm mã nguồn C#.

Ví dụ đầu tiên

Một ví dụ đơn giản mà bạn có thể đã quen thuộc là tính toán một biểu thức được viết dưới dạng hậu tố (hay RPG – Reverse Polish notation). Ví dụ biểu thức sau được viết dưới dạng trung tố:

3 * (2 + 1)

Dưới dạng RPN, biểu thức trên có dạng:

3 2 1 +  *

(Đối với các biểu thức toán học phức tạp, bạn có thể tham khảo bài viết Chuyển biểu thức trung tố sang tiền tố và hậu tố bằng Stack hoặc chuyển đổi trực tuyến tại http://scriptasylum.com/tutorials/infix_postfix/infix_postfix.html).

Sau khi gõ biểu thức RPN trên vào trình thông dịch Cat, bạn có thể thấy ngay kết quả là 9. Bây giờ trong stack chỉ có một giá trị là 9, bạn có thể tiếp tục nhập thêm các giá trị và toán tử khác để tính toán. Ví dụ tôi nhập thêm 2 và * để thực hiện phép toán 9* 2, và kết quả như hình dưới:

Cat Interpreter Example

Cat Interpreter Example

Xin giải thích ngắn gọn cơ chế tính toán dựa trên stack nếu như bạn chưa hiểu rõ: chuỗi kí tự mà bạn nhập vào dòng lệnh trên sẽ được push vào stack theo cơ chế LIFO (Last In First Out). Sau khi push ba số 3, 2, 1 vào stack, đến kí tự ‘+’, chương trình sẽ lấy hai số từ đỉnh stack ra (1 và 2)  và thực hiện phép cộng; kết quả là 3 sẽ được trả về stack. Như thế trong stack hiện có hai giá trị là 3 và 3. Tiếp tục phép nhân ‘*’ sẽ lấy hai giá trị này ra và thực hiện phép nhân, ta được kết quả 9 và push lại vào stack. Cuối cùng trong stack chỉ còn lại giá trị 9 như bạn thấy.

Các lệnh điều khiển (command) của Stand-alone Cat interpreter

Các lệnh điều khiển (command) mà phiên bản stand-alone Cat interpreter hỗ trợ được bắt đầu với kí tự “#”. Để xem danh sách các lệnh này, bạn gõ lệnh #help trong cửa sổ dòng lệnh của chương trình:

“filename” #load – loads a source file

[…] #trace – runs a function in trace mode

#test_all – runs all unit tests

[…] #type – shows the type of a function

[…] #metacat – optimizes a function by applying rewriting rules

#defs – lists all loaded commands

“instruction” #def – detailed help on an instruction

“prefix” #defmatch – describes all instructions starting with prefix

“tag” #deftag – outputs all instructions tagged with given tag

#exit – exits the Cat interpreter

Một lệnh hữu ích mà bạn có thể cần sử dụng để xem cơ chế làm việc của trình thông dịch này là #trace. Ví dụ để coi lại các bước mà trình thông dịch tính toán biểu thức 3 2 1 + *, bạn gõ vào dòng lệnh sau:

[3 2 1 + *] #trace

Output:

trace: 3
trace: 2
trace: 1
trace: +
trace: tail-call of ‘add’ function
trace: [[add_int] int_type [add_dbl] double_type [add_byte] byte_type [add_bit]
bit_type [add_str] string_type]
trace: list
trace: dispatch2
trace: add_int
trace: tail-call of ‘*’ function
trace: tail-call of ‘mul’ function
trace: [[mul_int] int_type [mul_dbl] double_type [mul_byte] byte_type [mul_bit]
bit_type]
trace: list
trace: dispatch2
trace: mul_int
stack: 9

Một số lệnh (instruction) cơ bản của Cat

Bạn có thể dùng #defs để hiển thị danh sách các lệnh và dùng “instruction” #def để xem mô tả lệnh tương ứng. Dưới đây là danh sách các lệnh cơ bản trong Cat:

Name Type Description
add_int (int int -> int) Adds the top two values on the stack.
and (bool bool -> bool) Computes the boolean ‘and’ operator.
apply (‘A (‘A -> ‘B) -> ‘B) Applies a function on the stack to the rest of the stack.
compose ((‘A -> ‘B) (‘B -> ‘C) -> (‘A -> ‘C)) Composes two functions.
cons (list ‘a -> list) Add an item to the beginning of a list.
dec (int -> int) Decrements an integer.
dip (‘A ‘b (‘A -> ‘C) -> ‘C ‘b) Executes a function, temporarily removing the next item on the stack.
div_int (int int -> int) Divides top value from the second value.
dup (‘a -> ‘a ‘a) Duplicates top item on the stack.
eq (‘a ‘a -> bool) Compares two items for equality.
empty (list -> list bool) Returns true if the list is empty.
false ( -> bool) Pushes the boolean value true onto the stack.
if (‘A bool (‘A -> ‘B) (‘A -> ‘B) -> ‘B) Conditionally executes one of two functions.
inc (int -> int) Increments an integer.
list (‘a -> ( -> ‘a)) Quotes a value, creating a constant generating function.
mod_int (int int -> int) Computes the remainder of dividing the top value from the second value.
mul_int (int int -> int) Multiplies the top two values on the stack.
not (bool -> bool) Negates a boolean value.
or (bool bool -> bool) Computes the boolean ‘or’ of top value.
papply (‘a (‘B ‘a -> ‘C) -> (‘B -> ‘C)) Performs partial application.
pop (‘a -> ) Removes top item from the stack.
quote (‘a -> ( -> ‘a)) Quotes a value, creating a constant generating function.
sub_int (int int -> int) Subtract the top value on the stack from the second.
swap (‘a ‘b -> ‘b ‘a)) Swaps the top two values on the stack.
true ( -> bool) Pushes the boolean value true onto the stack.
uncons (list -> list var) Returns the first item of a list, and the rest of the list

Ví dụ về lệnh dip dùng khi muốn thao tác với các phần tử không nằm ở đỉnh stack:

Giả sử trong stack có ba phần tử 1 2 3, tôi có thể pop phần tử 2 ra khỏi stack như sau:

>> 1 2 3

stack: 1 2 3

>> [pop] dip

stack: 1 3

Cặp ngoặc vuông [ ] dùng để chỉ cho trình thông dịch biết lệnh nằm trong cặp ngoặc này sẽ không được tính như một lệnh mà sẽ được thêm vào stack.

Cấu trúc điều kiện

Cat cung cấp lệnh các lệnh so sánh hai phần tử ở đỉnh stack và trả về true hoặc false vào stack tùy theo điều kiện:

eq: equals

gt: greater than

gteq: greater than or equal

lt: lower than

lteq: lower than or equal

Để kiểm tra điều kiện, bạn dùng lệnh if như ví dụ sau:

1 1 +

2 eq

[“As I expected!”]

[“I need to be repaired!”]

if

Copy đoạn code trên vào 1 file trong thư mục của chương trình Cat và lưu với tên test.txt (hoặc bất kì tên gì), sau đó dùng các lệnh “test.txt” #load để thực thi. Bạn cũng có thể viết các lệnh trên thành một dòng trực tiếp vào cửa sổ dòng lệnh nhưng như thế sẽ khiến biểu thức khó hiểu. Kết quả:

>> “test.txt” #load

stack: “As I expected!”

>>

Cấu trúc lặp

Ví dụ: In mười số ra màn hình từ 1 đến 10

1

[dup writeln inc]

[dup 10 lteq]

while

Đoạn mã trên sẽ thực thi [dup writeln inc] cho đến khi điều kiện [dup 10 lteq] thỏa mãn.

Cơ chế thực thi như sau:

–          Sao chép phần tử ở đỉnh stack và in phần tử đó ra .

–          Tăng giá trị của phần tử ở đỉnh stack lên 1 bằng lệnh inc.

–          Sao chép phần tử đỉnh stack và dùng để so sánh với 10, lệnh while sau đó sẽ dựa vào giá trị true/false trong đỉnh stack để quyết định có thực thi tiếp hay không.

Phần kết

Trên đây chỉ giới thiệu một vài tính năng và đặc điểm của Cat, chi tiết về các kiểu dữ liệu, lệnh, đệ quy, ngữ pháp,… trong Cat bạn có thể xem chi tiết tại Cat Specification.

https://yinyangit.wordpress.com

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s