gps_py.org

#+OPTIONS: num:nil ^:{}
#+Title: General Problem Solver in Python
*** Preface: Python is not Pythonic :noexport:
Python was perhaps the first 'new' language I read about after I discovered Hacker News. I had great expectations when I saw =spam= and =eggs=...I have the [[https://www.amazon.com/Complete-Pythons-Flying-Circus-Megaset/dp/B0009XRZ92][16 Tons]] (not an affiliate link). I saw /Holy Grail/ in the theater as a child. I thought 'this sounds like fun.' I expected something completely different.

In case you're unfamiliar with Python the language, other than the half similarity of the language's name to the comedic troop's name and the use of =spam= for =foo= and =eggs= for =bar=,  there's really no relation in either spirit or philosophy. I won't say Python is committed to dishumor, but it doesn't seem to live up to the philosophy espoused in *Meaning of Life*...also seen in the theater as part of a tweener birthday party. Anyway, Python did not turn out to be the language of my soul.

In the years since, I've found that I can't hate Python as much as I wish I could. I've also found I can't love it as much as I could. I can't hate it because it is easy to bang out certain types of programs. It's practical and it isn't JavaScript.

But I take a deep philosophical dislike to the notion of Pythonic. Or rather the evil Pythonic enables: calling code and coders 'unpythonic' as a pejorative, and 'unpythonic' is always used as a pejorative by the Python community. It's corrosive. It enables bullying. It accomplishes nothing but an excuse for unproductive behavior. Two space indentation is unpythonic. Tabs are unpythonic. Whatever someone with more community standing does not like is unpythonic. How stupid is the notion of unpythonic? Well Python 2 is on the verge of becoming unpythonic. It's about [[https://web-beta.archive.org/web/20120922091721/http://learncodethehardway.org/blog/AUG_19_2012.html][social mores]], not programming idioms. 

So there's that. Which means I am not particularly concerned if anyone considers my code unpythonic or if it is considered pythonic for the same reasons that I don't care what someone thinks of the =loop= macro's inclusion in Common Lisp. I care if the code works and if the program is readable (the latter is why I am using literate programming (I also don't care whether or not literate programming is pythonic either))...actually I am probably using literate programming so writing essays like this one count as programming.

Anyway, it's great if you find the literate format entertaining or informative. If you don't, just skip this document and look at the code. It should have doc strings and at least a few comments.

* Introduction
This is a 'port' of Norvig's General Problem Solver from Norvig's Common Lisp code to my own Python. While my intent with the exercise includes learning a bit more Python, the big goal is to ensure a better understanding of the General Problem Solver. Just as typing in code from a book creates deeper understanding than mere reading, I suspect that rewriting a program in a second language increases the understanding even more so...yeah, it's a theory.

** So why Python? 
Practically speaking, rewriting GPS in another Lisp (such as Clojure or Racket or Arc) smells a bit sour as an intellectual exercise. On the other hand, Norvig's handy [[http://norvig.com/python-lisp.html][/Python for Lisp Programmers/]] means there's an external basis for rewriting in Python and some signposts on how to proceed.

** General Approach
The primary goal is working code by porting the Common Lisp to Python. Isomorphism between the code bases may wind up being a stronger condiseration than idiomatic Python. There's always time for refactoring later. However, the code base will reflect Norvig's completed version of GPS rather than following the iterative process in his book.
* General Problem Solver
The outline for this Python implementation follows the structure of my Common Lisp implementation...for better or worse.
#+NAME: gps
#+BEGIN_SRC python :noweb tangle :results none :tangle gps.py
  # gps.py
  # This file autogenerated from gps_py.org

  <<special-variables>>

  <<op-data-structure>>

  <<gps-function>>

  # Utilities
  
  <<cons>>

  <<first>>
#+END_SRC
** Special Variables
The global variables follow the convention used by the debugger.
#+NAME: special-variables
#+BEGIN_SRC python
  # Special Variables
  _ops_ = []
#+END_SRC
** Data Structure
An =op= has four fields. The Common Lisp implementation uses =defstruct=. There is not a clear equivalent data structure in Python. So here are a number of alternatives for representing the data structure. Dictionaries seemed like a reasonable alternative. But would require writing constructor functions to initialize the fields of dictionary objects. Named tuples seemed like another alternative and have the advantage of immutability. The probelm there is that using =my_tuple.replace(action=[spam, eggs])= when =my_tuple= is in a list of =namedtuple= requires pointer maintenance because Python lists are place based. Again there's book keeping.

So objects it is. 
#+NAME: op-data-structure
#+BEGIN_SRC python
  # Data Structure
  class Op:
      """
      An action is the basis of an operation.
      An action can only occur if all its preconditions exist in the execution environment.
      An action changes the state of the world by:
          1. adding the conditions in its add_list to the environment.
          2. removing the conditions in its del_list from the enviroment.
      """
      def __init__(self, action=[], preconds=[], add_list=[], del_list=[]):
          self.action = action
          self.preconds = preconds
          self.add_list = add_list
          self.del_list = del_list
      def __repr__(self):
          return str(vars(self))
#+END_SRC

** GPS
#+NAME: gps-function
#+BEGIN_SRC python
  def gps(state, goal, ops=_ops_):
      """
      General Problem Solver: from state achieve goal using ops.
      """
      return find_all_if(action_p, achieve_all(cons ('start', state)), goals, [])
#+END_SRC
*** TODO verify find_all_if versus find_all
** Major Functions
*** achieve_all
#+NAME: achieve_all
#+BEGIN_SRC python
  def achieve_all(state, goals, goal_stack):
      return [g for g in orderings(goals) if any achieve_each(state, g, goal_stack)]
#+END_SRC
*** achieve_each
The critical bit of code in =achieve_each= is to create a mutable copy of the global state. There are several ways to do this in Python, one way is to create a mutable object such as a =list=. Here a =class= is used instead.
#+NAME: achieve_each
#+BEGIN_SRC python 
  def achieve_each(state, goals, goal_stack):
      """Achieve each goal and make sure that they all hold at the end"""
      # the function will mutate state
      # but don't mutate the current state
      class Obj:
          Obj.current_state = state
      # achieve a goal using the local version of the state
      # and update the local copy of state
      def f(goal):
          Obj.current_state = achieve(Obj.current_state, goal, goal_stack)
      # make sure each goal is achievable on its own
      # and that no goal clobbers another goal
      if all(map(f, goals)) and set(goals) < set(Obj.current_state):
          return Obj.current_state
#+END_SRC
*** achieve
#+NAME: achieve
#+BEGIN_SRC python
  def achieve(state, goal, goal_stack):
      """
      A goal is achieved when it already holds
      or if there is an appropriate op that
      is applicable.
      """
      # make debugger available
      debug_indent('gps', len(goal_stack), 'Goal: {}'.format(goal))

      # local function keep line length down
      def a_lambda(op):
          return apply_op(state, goal, op, goal_stack)

      # main logic
      if goal in state:
          return state
      elif goal in goal_stack:
          return False
      else return any(op for op in map(a_lambda, appropriate_ops(goal, state)))
#+END_SRC
*** appropriate_p
*** apply_op
*** appropriate_ops
The Common Lisp version of this function uses quite a bit of the language's built in list handling to do a lot in a little space.
#+NAME: appropriate_ops
#+BEGIN_SRC python :noweb tangle
  def appropriate_ops(goal, state):
      """
      Return a list of appropriate operators
      sorted by the number of unfilled preconditions.
      """
      <<appropriate-ops-key>>
#+END_SRC
One of the features the Lisp version uses is a =:key= for the sort command. It takes an op and counts how many of its preconditions are not met in the current state.
#+NAME: appropriate-ops-key
#+BEGIN_SRC python
  def appropriate_ops_sort_key(op):
      """A closure over the external value state"""
      return len([p for p in op.preconds if p not in state])
#+END_SRC
** Auxilary Functions
*** action_p
#+NAME: action-p
#+BEGIN_SRC python
  def action_p(x):
      """
      Is x the start start state or an executing form.
      """
      return x == ['start'] or executing_p(x)
#+END_SRC
*** convert-op
The executing convention adds a sense of time transition to the world by handling actions such as =run_around_block= as a change to the world state. To implement the convention, every =op= has at least one executing form in =op.add_list=. The default executing form when no other executing form is present is =['executing', op.action]=. =convert-op= adds the default to an =op= if none is present.
#+NAME: convert-op
#+BEGIN_SRC python
  def convert_op(op):
      """
      op -> NONE
      Make op conform to the ['executing', op] convention.
      """
      add_list = op.add_list
      some_executing = any(executing_p(item) for item in add_list)
      if not some_executing: # aka unless 
          op.add_list = cons(['executing', op.action], add_list)
#+END_SRC
*** executing_p
#+NAME: executing-p
#+BEGIN_SRC python
  def executing_p(x):
      """
      Is the form ['executing' ...]?
      """
      return starts_with(x, 'executing')
#+END_SRC
*** find_all
The version here is simpler than the version Norvig provides in that it does not have a wide range of options as is typical for Common Lisp functions.
#+NAME: find-all
#+BEGIN_SRC python
  def find_all(a_list, test, not_test=False):
      """
      List -> List
      Non-mutating.
      Finds all the elements of a list that pass the test if not_test is False.
      If not_test evaluates to True, returns all elements that do not pass the test.
      """
      if not_test:
          return [element for element in a_list if not test(element)]
      else:
          return [element for element in a_list if test(element)]
#+END_SRC
*** mappend
*** member_equal
*** op
*** remove_if_not
*** starts_with
#+NAME: starts_with
#+BEGIN_SRC python
  def starts_with (a_list x):
      """
      Is this a list that starts with x?
      """
      return type(a_list) is list and first(a_list) == x
#+END_SRC
*** use
* Knowledge Bases
** School Ops
** Monkey Ops
** Maze Ops
* Applications
** School Ops
** Monkey Ops
** Maze Ops
* Debugger
One of the fun parts of Norvig's approach is building something rather than searching for someone else's tool. The simple debugger he implements for GPS seems like a good place to start.

#+NAME: py_debugger
#+BEGIN_SRC python :noweb tangle :tangle debugger.py
  # debugger.py
  # This file autogenerated from gps_py.org

  <<dbg_ids>>

  <<dbg>>

  <<debug>>

  <<undebug>>

  <<dbg_indent>>
#+END_SRC

** dbg ids
I used leading underscores to indicate there is something a bit special about the variable as an isomorphism to the asterisks in =*dbg-ids*= from Common Lisp.

#+NAME: dbg_ids
#+BEGIN_SRC python
# Identifiers used by dbg.
_dbg_ids_ = []
#+END_SRC

** dbg
Uses =target= instead of 'id'. May need to import =sys= and =write= to a different stream.
#+NAME: dbg
#+BEGIN_SRC python
    def dbg (target, format_string, *args):
        """Print debugging information if target has been specified"""
        if target in _dbg_ids_:
            print(format_string.format(args))
#+END_SRC

** debug
#+NAME: debug
#+BEGIN_SRC python
  def debug(*ids):
      """Start dbg output the given ids."""
      global _dbg_ids_
      _dbg_ids_ = _dbg_ids_ + list(ids)
#+END_SRC

** undebug
Python does not have set semantics for lists so I had to make =list_diff=, or rather I made =list_diff= so that =undebug= would have the appropriate level of abstraction. It seems to me that incorporating a list comprehension within =undebug= sort of gets in the way of readability...particularly because the list comprehension contains a negative statement.

I used =minuend= and =subtrahend= per [[https://en.wikipedia.org/wiki/Subtraction][Wikipedia]].

Python requires the =global= keyword to perform the assignment to =_dbg_ids_= because the === operator makes the variable locally scoped.

#+NAME: undebug
#+BEGIN_SRC python
  def list_diff(minuend, subtrahend):
      """Remove the elements of the subtrahend from the minuend."""
      return [val for val in minuend if val not in subtrahend]

  def undebug(*ids):
      """Stop dbg on the ids. If no ids, stop all debugging"""
      global _dbg_ids_
      if ids:
          _dbg_ids_ = list_diff(_dbg_ids_, list(ids))
      else:
          _dbg_ids_ = []
#+END_SRC

** debug indent
#+NAME: dbg_indent
#+BEGIN_SRC python
  def dbg_indent (target, indent, format_string, *args):
      """Print indented debugging info if target has been specified"""
      if target in _dbg_ids_:
          s = ""
          for i in range(indent):
              s += "    "
          s = s + format_string
          print(s.format(args))
#+END_SRC

* Utilities
Since the first goal is to port code from Common Lisp it probably makes sense to have a some tools for handling lists in a familiar way. All of this can be refactored later.
** cons
Where to start but with =cons=. It's not that Python doesn't have the ability to add to lists, it's just that trying to translate from front to rear addition is probably not the best place to start.
#+NAME: cons
#+BEGIN_SRC python :session yes :results none
  def cons (element, a_list):
      """
      Adds an elment to the *front* of a_list.
      If a_list is not a list, cons creates a list of one element holding a_list.
      """
      if not type(a_list) == list:
          a_list = [a_list]
      a = [element]
      a.extend(a_list)
      return a
#+END_SRC
** first
#+NAME: first
#+BEGIN_SRC python :session :results output silent
  def first(a_list):
      """
      Returns the first elment of a list.
      Returns False if the list is empty.
      """
      if len(a_list)==0:
          return False
      else:
          return a_list[0]
#+END_SRC
** rest
#+NAME: rest
#+BEGIN_SRC python :session :results output silent
  def rest(a_list):
      """
      Returns a list minus its first elment.
      Returns false if list is empty.
      Returns the empty list if list has one element.
      """
      if len(a_list)==0:
          return False
      elif len(a_list)==1:
          return []
      else:
          return a_list[1:]
#+END_SRC
** list_append
Python has an =append= function that adds an element onto the end of a list. While the =+= operator will concatenate two lists, my quick and dirty testing indicates it cannot be passed directly to =reduce=.
#+BEGIN_EXAMPLE
  # Example
  >>> reduce(+, [[1],[2],[3]])
    File "<stdin>", line 1
      reduce(+, [[1],[2],[3]])
              ^
  SyntaxError: invalid syntax
#+END_EXAMPLE

The call to =+= must be wrapped in a =lambda=. It works and it's not terrible
#+BEGIN_EXAMPLE
  # Example
  reduce(lambda x,y: x + y, [[1],[2],[3]])
  # => [1, 2, 3]
#+END_EXAMPLE
This means that mapping an append operation starts to look like lambdas inside of lambdas and that smells to me like a breakdown of abstraction layers.

In the end, a function that works with lists just feels right to me. It can be fed to =reduce= or its equivalent list comprehension. Having a meaningful name is useful.
#+NAME: list_append
#+BEGIN_SRC python :session :results output silent
  def list_append(list_1, list_2):
      return list_1 + list_2
#+END_SRC