ศึกษา Student (AI Program สมัยแรกๆ)

วันนี้ลองนั่งเขียนโปรแกรมที่ 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."
  ;; This assumes there is exactly one x in e
  ;; and that e is an equation.
  (cond ((eq (exp-lhs e) x)
         ;; case I: X = A -> X = n
         e)
        ((in-exp x (exp-rhs e))
         ;; case II: A = f(x) -> f(x) = A
         (isolate (mkexp (exp-rhs e) '= (exp-lhs e)) x))
        ((in-exp x (exp-lhs (exp-lhs e)))
         ;; Case III: f(x) * A = B  -> f(x) = B/A
         (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)))
         ;; Case IV: A*f(x) = B -> f(x) = B/A
         (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 ;; Case V: A/f(x) = B -> f(x) = A/B
         (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
#