วันนี้ลองนั่งเขียนโปรแกรมที่ solve algebra equation ดู
พวกที่เป็นโจทย์แบบนี้ ->
(x + 2)/ 10 = 8ลอกวิธีการมาจาก
code ในหนังสือ
Paradigms of AI Programmingของ
Peter Norvigโดยเนื้อหาที่เขาพูดถึง ก็คือวิธีการ implement program Student
ที่
Daniel Bobrow ทำ Research Project ไว้ในปี 1964
ตัวโปรแกรม Student ออกแบบมาให้ solve โจทย์แบบนี้
(student '(If the number of customers tom gets is twice the square of
20 % of the number of advertisements he run |.|
and then number of advertisements is 45 |.|
then what is the number of customers Tom gets ?))
;; ที่เขียนข้างบนนี้เป็นโปรแกรมจริงๆนะ run ได้ ไม่ใช่ description
ผมตัดมาให้ดูเฉพาะส่วน solve equation (เฉพาะที่มีตัวแปรเดียว)
หลักการ ก็คือ แปลงโจทย์ให้อยู่ในรูป tree structure ให้ได้ก่อน
=
/ \
(/) 8
/ \
+ 10
/ \
x 2
ตรงนี้ lisp ได้เปรียบในการ represent
เพราะพวก tree structure สามารถเขียนในรูป list ได้ตรงๆเลย
กรณีข้างบน ก็เขียนได้ดังนี้
'(= (/ (+ x 2) 10) 8)
ส่วน ruby ผมลองใช้ class ดู
ซึ่งเขียนแล้ว ก็รู้สึกเยิ่นเย้อนิดๆ (ขนาดมี attr_accessor ช่วย)
class Exp
include ExpHelper
attr_accessor :op, :lhs, :rhs
def initialize(lhs, op, rhs)
@lhs = lhs
@op = op
@rhs = rhs
end
...
end
ที่รู้สึกเยิ่นเย้อ ก็เพราะ lisp จะเขียนแค่นี้
(defstruct (exp (:type list)
(:constructor mkexp (lhs op rhs)))
op lhs rhs)
ขั้นถัดไป ก็คือก็ทำการย้ายข้างให้ ด้านซ้าย มีแต่ตัวแปรอย่างเดียว
กรณีโจทย์ข้างบน ก็จะถูกแปลงเป็น
x = (8 * 10) - 2ใน lisp ที่ norvig เขียน จะมีหน้าตาแบบนี้
(defun isolate (e x)
"Isolate the lone x in e on the left-hand side of e."
(cond ((eq (exp-lhs e) x)
e)
((in-exp x (exp-rhs e))
(isolate (mkexp (exp-rhs e) '= (exp-lhs e)) x))
((in-exp x (exp-lhs (exp-lhs e)))
(isolate (mkexp (exp-lhs (exp-lhs e)) '=
(mkexp (exp-rhs e)
(inverse-op (exp-op (exp-lhs e)))
(exp-rhs (exp-lhs e)))) x))
((commutative-p (exp-op (exp-lhs e)))
(isolate (mkexp (exp-rhs (exp-lhs e)) '=
(mkexp (exp-rhs e)
(inverse-op (exp-op (exp-lhs e)))
(exp-lhs (exp-lhs e)))) x))
(t (isolate (mkexp (exp-rhs (exp-lhs e)) '=
(mkexp (exp-lhs (exp-lhs e))
(exp-op (exp-lhs e))
(exp-rhs e))) x))))
ซึ่งผมชอบที่เขาเขียนตรงที่
- เขียนแบบไม่มี side-effect (ไม่มี assign statement เลย)
- Recursive สวยดี
อันนี้ตอนแปลงเป็น ruby ก็นึกอยู่ว่า
จะเขียนแบบ
imperative ดีไหม จะได้เปรียบเทียบกันดู
แต่สุดท้าย ก็รู้สึกว่า โจทย์แบบนี้ไม่ควรเขียนแบบนั้น ก็เลยเขียนตาม lisp
โดยให้ method isolate เป็น method ของ class Exp
def isolate(var)
case
when @lhs == var
self
when var.in(@rhs)
Exp.new(@rhs, @op, @lhs).isolate(var)
when var.in(@lhs.lhs)
Exp.new(@lhs.lhs,
"=",
Exp.new(@rhs, self.inverse(@lhs.op), @lhs.rhs)).isolate(var)
when ["*", "+"].include?(@lhs.op)
Exp.new(@lhs.rhs,
"=",
Exp.new(@rhs, inverse(@lhs.op), @lhs.lhs)).isolate(var)
else
Exp.new(@lhs.rhs,
"=",
Exp.new(@lhs.lhs, @lhs.op, @rhs)).isolate(var)
end
end
ตรงเงื่อนไขที่ check ว่า ตัวแปรอยู่ผั่งไหน (จะได้สลับด้านได้ถูก)
ผมอาศัยว่า class ของ ruby เป็น class แบบเปิด (แก้ไขได้)
ก็เลยใช้วิธี modify
Symbol Class (ผมใช้ Symbol represent variable)
class Symbol
def in(exp)
to_sym == exp ||
(exp.is_a?(Exp) &&
(to_sym.in(exp.lhs) || to_sym.in(exp.rhs)))
end
end
พอจัด tree เสร็จ
สุดท้ายก็ evaluate ด้านที่อยู่ด้านขวา
ใน ruby ก็ใช้คำสั่ง
eval
def solve()
Exp.new(@lhs, '=', eval_equation(@rhs))
end
def eval_equation(exp)
return case
when exp.is_a?(Numeric): return exp
else
eval("#{eval_equation(exp.lhs)} #{exp.op} #{eval_equation(exp.rhs)}")
end
end
ตอน run ก็เขียนดังนี้ (ยังไม่ได้เขียน parser ก็เลยดูไม่ค่อยสวย)
e = Exp.new(Exp.new(Exp.new(:x, '+', 2), '/', 10), '=', 8)
puts "Equation -> #{e}"
puts "Solve -> #{e.isolate(:x).solve()}"
# output
# ------
# Equation -> x + 2 / 10 = 8
# Solve -> x = 78
#
