## Literate progamming
This repository uses literate programming. The ultimate source for all documents including this *readme* is an [emacs](https://www.gnu.org/software/emacs/) [org-mode](http://orgmode.org/) file in the root directory. It utilizes the [babel](http://orgmode.org/worg/org-contrib/babel/) tooling.
## Text presentation of source code
The literate presentation of this project is available as a *Github page* at https://brudgers.github.io/cl-search/.<<:TODO:-auto-generated-note>> <<:TODO:-tree-search>> <<:TODO:-successors>> <<:TODO:-depth-first>> <<:TODO:-breadth-first>> <<:TODO:-helpers>>
<<:TODO:-inifinite-binary-tree>> <<:TODO:-finite-binary-tree>>
<<:TODO:-is>> <<:TODO:-prepend>>
This file was autogenerated using org-babel-tangle on the literate programming document located in the root directory of the git repository.
Back in 2014, I tried taking Pascal Van Hentenryck’s Coursera course on Discreet Optimization. It was well over my head, but I feel like I learned a lot watching the videos and trying unsuccessfully to complete the early assignments. Later I came across {Norvig’s Book}.
create link for {Norvig’s Book}.END Much of Van Hentenryck’s course is what was once artificial intelligence. The first important topic is search. Although I had written depth first and breadth first search algorithms in Racket for Tim Roughgarden’s Alogorithms Design and Analysis course on Coursera, I didn’t understand how to manipulate the implementation. {Norvig’s Book} has a very clear modular approach to search and provides several techniques to potentially improve its performance.Search can be described as [see {Norvig’s Book} section 6.4]:
- A start state
- A goal state
- The successors, or states that can be reached from any other state
- The strategy for determining the order in which we search
This is the base implementation since {Norvig’s Book} is informing the design.
<<cl-auto-generated-note>>
<<cl-tree-search>>
<<cl-successors>>
<<cl-depth-first>>
<<cl-breadth-first>>
<<cl-helpers>>(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) ;nothing left to search
fail)
((funcall goal-p (first-states)) ;found a goal state
(first states))
(t
(tree-search
(funcall combiner
(funcall successors (first states))
(rest states))
goal-p successors combiner))))One of the things Common Lisp emphasizes is good names. A good name for a predicate generator is is …depending on how ‘is’ is defined.
(defun is (value)
#'(lambda (x) (eql x value)));;;;;;;;;;;;;;;;
;; SUCCESSORS ;;
;;;;;;;;;;;;;;;;
<<cl-inifinite-binary-tree>>
<<cl-finite-binary-tree>>As always, Common Lisp has a way of challenging me. Rather than defining a data set to search, Norvig defines a binary tree with a function. Although now that I think about it, that’s how we really want to think about search – we want to think about search over a stream that might be infinite rather than a haystack of fixed size. Even when the stream of possible solutions is bounded, combinatorial explosion produces a solution space that is for practical purposes equivalent to an infinite one.
(defun binary-tree (x)
(list (* 2 x) (+ 1 (* 2 x))))For testing it makes sense to have a finite binary tree as well. Again, the tree is generated with a function (that’s the idea of successors), but it prunes the successors that don’t meet the criteria. The important point here, is that =successor= does the pruning. That was hard to see when I was trying to right these functions previously.
(defun finite-binary-tree (n)
"Return a successor function that generates a binary tree with n nodes."
#'(lambda (x)
(remove-if #'(lambda (child) (> child n))
(binary-tree x))))(defun depth-first-search (start goal-p successors)
"Search new states first until goal is reached."
(tree-search (list start) goal-p successors #'append))The difference between depth first and breadth first search is that earlier successors are searched before later successors. To create this, use a simple analog to append.
(defun prepend (x y)
"Prepend y to the start of x."
(append y x))Defining a breadth first search from tree search becomes:
(defun breadth-first-search (start goal-p successors)
"Search oldest states first until goal is reached."
(tree-search (list start) goal-p successors #'prepend));;;;;;;;;;;;;
;; HELPERS ;;
;;;;;;;;;;;;;
<<cl-is>>
<<cl-prepend>>;;; This file was autogenerated using org-babel-tangle
;;; on the literate programming document located in the
;;; root directory of the git repository.<<python-auto-generated-note>>
<<python-tree-search>>
<<python-successors>>
<<python-depth-first>>
<<python-breadth-first>>
<<python-helpers>>def tree_search(states, goal_p, successors, combiner):
"""Find a state that satisfies goal_p. Start with states and search according to successors and combiner."""
if not states:
return fail
elif goal_p(states[0]):
return states[0]
else:
tree_search(combiner(successors(first states), rest(states)), goal_p, successors, combiner)<<python-inifinite-binary-tree>>
<<python-finite-binary-tree>><<python-is>>
<<python-prepend>>"""This file was autogenerated using org-babel-tangle
on the literate programming document located in the
root directory of the git repository."""