ทดลอง Implement Search Library ด้วย clisp, java, ruby

ช่วงนี้กำลังอ่าน Paradigms of Artificial Intelligence Programming อยู่
เล่มนี้เขาเขียนอธิบายดี มี code ประกอบชัดเจน
(ผมเป็นพวกประเภทอ่านหลักการล้วนๆไม่ได้ ต้องเห็น code จึงจะเข้าใจ)
code ที่เขาใช้ก็คือ clisp
เห็นวิธีเขียน code เขาแล้ว
คนที่มี background java อย่างผม ก็เลยอื้งไป (อึ้งเพราะทึ่ง)
ลองดูตัวอย่าง
code นี้คัดมาจาก search.lisp ที่อยู่ใน www.norvig.com (web ของ คนแต่งหนังสือ)

(defconstant fail nil "Indicates pat-match failure")

(defun tree-search (states goal-p successors combiner)
  "Find a state that satisfies goal-p. Start with states.
   and search according to successors and combiner."
  (dbg :search "~&;; Search: ~a" states)
  (cond ((null states) fail)
        ((funcall goal-p (first states)) (first states))
        (t (tree-search
            (funcall combiner
                     (funcall successors (first states))
                     (rest states))
            goal-p successors combiner))))

(defun depth-first-search (start goal-p successors)
  "Search new sates first until goal is reach."
  (tree-search (list start) goal-p successors #'append))

(defun prepend (x y) (append y x))

(defun breadth-first-search (start goal-p successors)
  (tree-search (list start) goal-p successors #'prepend))

ลอง implement เป็น java ดู

public abstract class TreeSearch<T> {
        
        IGoalPredicate<T> goalPredicate;
        ISuccessor<T> successor;
        public static boolean DEBUG = true;
        
        public TreeSearch(IGoalPredicate<T> goalPredicate, 
                        ISuccessor<T> successor) {
                this.goalPredicate = goalPredicate;
                this.successor = successor;
        }

        public T search (List<T> states) {
                
                if (states.size() == 0) {
                        return null;
                }
                
                if (DEBUG) {
                        for (Iterator<T> iter = states.iterator(); iter.hasNext();) {
                                T element = iter.next();
                                System.out.print(element + ", ");
                                
                        }
                        System.out.println();
                }
                
                T curState = states.remove(0);
                
                if (goalPredicate.isGoalState(curState)) {
                        return curState;
                }               
                return search(
                                combine(states, successor.createSuccessors(curState)));
        }
        
        public abstract List<T> combine (List<T> oldList, List<T> newList);
}

public interface IGoalPredicate<T> {
        public boolean isGoalState(T state);
}

public interface ISuccessor<T> {
        public List<T> createSuccessors(T state);
}

public class BreadthFirstSearch<T> extends TreeSearch<T> {
                
        public BreadthFirstSearch(IGoalPredicate<T> goalPredicate, ISuccessor<T> successor) {
                super(goalPredicate, successor);
        }

        @Override
        public List<T> combine(List<T> oldList, List<T> newList) {
                ArrayList<T> list = new ArrayList<T>();
                list.addAll(oldList);
                list.addAll(newList);
                return list;
        }

}

ก็ไม่เลวนะ ถ้าเป็นเมื่อก่อนต้องรู้สึก "แหมดูดีจัง"

ลอง implement แบบ ruby บ้าง
ruby implement ได้ 2 แบบ คือ
เป็น object style หรือ standalone method style
เลือกวิธีหลังดีกว่า

module Search
  @@debug = false;
  require 'pp'
  
  def tree_search(states, goal_p, successors, combiner)
    
    pp states if @@debug
    
    return nil if states.empty?  
    return states.first if goal_p.call(states.first)
    
    tree_search(combiner.call(successors.call(states.shift), states),
                goal_p, successors, combiner)                
  end

  def breadth_first_search(start, goal_p, successors)
    combiner = lambda { |x, y|  y + x }
    tree_search([]<<start, goal_p, successors, combiner)  
  end
  
  def depth_first_search(start, goal_p, successors)
    combiner = lambda { |x, y|  x + y }
    tree_search([]<<start, goal_p, successors, combiner)      
  end

end

อืมม์ ruby ก็ใช้ได้ สั้นสู้ lisp ได้เหมือนกัน

เปรียบเทียบ code ที่เรียกใช้ดูบ้าง
โดย search binary tree
เพื่อหา node ที่มีค่า = 12



เริ่มด้วย lisp

(defun is (value) 
  #'(lambda (x) (eql x value)))

(defun binary-tree (n)
  (list (* 2 n) (+ (* 2 n) 1)))

(breadth-first-search 1 (is 12) #'binary-tree)

ส่วน java ยาวเหมือนเดิม

public static void main(String[] args) {

    ISuccessor<Integer> suc = new ISuccessor<Integer>() {
        
        public List<Integer> createSuccessors(Integer state) {
            ArrayList<Integer> list = new ArrayList<Integer>();
            list.add(2 * state);
            list.add(2 * state + 1);
            return list;
        }
        
    };
    
    IGoalPredicate<Integer> goal_p = new IGoalPredicate<Integer>() {
        
        public boolean isGoalState(Integer state) {
            if (state == 12) {
                return true;
            }
            return false;
        }
        
    };
    
    BreadthFirstSearch<Integer> bs = new BreadthFirstSearch<Integer>(goal_p, suc);
    ArrayList<Integer> start = new ArrayList<Integer>();
    start.add(1);
    bs.search(start);
}

ของ ruby สั้นดีมาก

include Search
gp = lambda {|state| state == 12}
successors = lambda {|x| [x*2, x*2+1]}
breadth_first_search(1, gp, successors)

การเรียน lisp ก็ดีอย่างหนึ่งนะ
เพราะถ้าเป็นเมื่อก่อน case นี้ ผมคงจะเลือก implmenet แบบ Object Style
(เพราะทำเป็นอยู่แบบเดียว)
แต่พอเริ่มเขียน lisp เป็น
มันก็เลยมีทางเลือกอื่นๆเพิ่มขึ้นมา