Lisp code for comparison by Peter Norvig here.

package gps
object gps2 {
  import Utilities._ // debug stuff and port of Lisp "some" function
  
  /** a condition that holds or does not hold
   *  In the Lisp version there are two types of conditions: regular and executing.
   *
   *  Regular conditions are assumed to be atoms (i.e. not lists, usually symbols)
   *  while executing conditions are list of the form ('Executing 'operator-name)
   *
   *  I personally find the convention quite confusing and it doesn't mix well
   *  at all with static typing in Scala.  One solution would be to make them both lists
   *  of Symbols and then pattern match cond :: Nil to be
   *  a regular condition and 'Executing :: op :: Nil to be an executing
   *  condition.  Scala could support this very nicely (assuming ops are symbols).
   *
   *  I don't particularly like that solution either, for a variety of reasons.
   *  So instead, I make Condition a trait and use case classes to
   *  represent normal conditions and executing conditions.  This free the programmer
   *  from remembering patterns and allows the compiler to check for correctness and
   *  fall-through conditions.
   */
  abstract class Condition {
     val name: String
     final override def toString = name
   }
  /** factory object that constructs the basic implementation of condition*/
  object Condition {
    /** make a condition
     *  @param name the name of the Condition
     *  @return a Condition with the specified name
     */
    def apply(name: String) = BasicCondition(name)
  }
  
  /** a normal condition with a specified name */
  case class BasicCondition(val name: String) extends Condition
  /** A condition that represents the the execution of an operator */
  case class ExecutedOpCondition(val op: Operator) extends Condition {
    /** the name is derived from the name of the operator */
    val name = "Executing: " + op.name
  }
 
  /** an action that can be performed to achieve goals
   *  corresponds to the op struct in the Lisp version
   *  some functions related to the operators have been moved directly
   *  into the class
   */
  case class Operator (val name: String, 
                       val preconditions: List[Condition],
                       val baseAdd: List[Condition],
                       val del: List[Condition]) { 
    /** the condition to be added to the state when this operator is executed */
    val executedCondition = ExecutedOpCondition(this) 
    /** the add list for this operator, including the executed condition */
    val add = baseAdd ::: executedCondition :: Nil
    /** test whether this operator is appropriate to achieve the specified goal
     *  @param goal the desired goal
     *  @return true if this op will achieve the goal, false if not
     */
    def appropriate(goal: Condition) = add contains goal 
    override def toString = name
  }
  /** Operator representing the first step  of a solution */
  val Start = Operator("Start", Nil, Nil, Nil)
 
  /** enables typed-checked expression of preconditions using loose types in DSL
   *  Huh?  Type-checked use of loose types?
   *  The idea is to make the DSL interpretter-friendly.  Typing things like
   *  Condition("foo") :: Condition("bar") :: Nil takes a while, and is not
   *  visually different from expressing the addList, delList, etc.
   *  
   *  So this class, along with addList and delList, force preconds to be used
   *  in the proper place when defining an Operator while allowing the user
   *  to enter strings, symbols, Conditions, actual conditions, or anything
   *  else that hopefully is easy to type.
   */
  case class preconds(val conds: AnyRef*)
  /** enables typed-checked expression of the addList in DSL*/
  case class addList(val conds: AnyRef*)
  /** enables typed-checked expression of delList in DSL*/
  case class delList(val conds: AnyRef*)
  
  /** utility function for converty a bunch of AnyRefs into a list of Conditions */
  private def mcl(values: Seq[AnyRef]): List[Condition] = {
    values.toList.map((e) => e match {
      case e: Condition => e
      case _ => Condition(e.toString)
    })
  }
  
  /** utility function for specifying Operators in the DSL
    * @param name the name of the Operator
    * @param preconds the preconditions for the Operator
    * @param addList the addList for the Operator
    * @param delList the delList for the Operator
    * @return an Operator
    */
  def Op(name: String, p: preconds, a: addList, d: delList) = 
    Operator(name, mcl(p.conds), mcl(a.conds), mcl(d.conds))
  /** overloaded version of Op enabling name to be a Symbol */
  def Op(name: Symbol, p: preconds, a: addList, d: delList): Operator =
    Op(name.toString, p, a, d)
  
  /** simulated function for problem-definition DSL
    * an object is used instead of a function because functions
    * with * arguments cannot be partially applied
    * to create aliases used in the DSL 
    */
  object statemaker { 
    def apply(values: AnyRef*): List[Condition] = mcl(values)
  }
  /** condition list factory for DSL to express the initial state*/
  val startState = statemaker
  /** condition list factory for DSL to express the goal state*/
  val goalState = statemaker
 
  private var _ops: List[Operator] = _
  /** convenience implicit def for interactive use so that ops doesn't have
   *  to be repeatedly specified by the user
   *  @return the default of set Operators
   */
  implicit def ops = _ops
  /** set the default set of operators
    * @param operators the new default set of Operators
    * @return the number of operators specified
    */
  def use(operators: List[Operator]): Int = {
    _ops = operators
    _ops.size
  }  
  
  
  /** solve the specified problem
   *  The Lisp version of this function simply returns a list special "executed" conditions,
   *  which are really just lists of symbols that conform to a specific convention.  This funcion
   *  returns the actual Operator objects that must be applied to solve the problem.
   *
   *  I believe returning a list of Operators is substantially more useful,
   *  because the operators are more fit for usage by a calling function.
   *
   *  @param state the current set of conditions
   *  @param goals the set of goal conditions
   *  @return ordered list of operators, starting with Start, on Success; Nil on failure 
   */
  def GPS(state: List[Condition], goals: List[Condition])(implicit ops: List[Operator]): List[Operator] = {
    achieveAll(Start.executedCondition :: state, goals, Nil).flatMap((c) => c match {
      case eoc: ExecutedOpCondition => eoc.op :: Nil
      case _ => Nil
    })
  }
  
  /** achieve all the specified goals
   *  achieveAll works by attempting to achieve each goal until
   *  either one fails or all have succeeded and then return the resulting state
   *
   *  achieveAll is called by GPS with the initial conditions
   *  and state, as well as by applyOp with the preconditions of each
   *  Operator that is attempted.  Note that the invokation by
   *  applyOp means that achieveAll utlimately recurses on itself.
   *
   *  @param state the current list of conditions 
   *  @param goals the set of goal conditions
   *  @param goalStack the set of goals currently being examined
   *  @param ops implicit parameter for the set of available Operators
   *  @return the resulting list of Conditions with embedded operation conditions
   *  @todo failure and a Nil state are not distinguished from one another
   */
  private def achieveAll(state: List[Condition], goals: List[Condition], goalStack: List[Condition])(implicit ops: List[Operator]): List[Condition] = {
    def achieveGoal(state: List[Condition], goal: List[Condition]): List[Condition] = {
      goal match {
        case Nil => state
        case g :: rest => {
          achieve(state, g, goalStack) match {
            case Nil => Nil
            case newState => achieveGoal(newState, rest)
          }
        }
      }
    }
    achieveGoal(state, goals)
     
    /*  Below is a slightly more direct port of the Lisp version which utilizes mutable state
    var currentState = state  //uhoh...mutable state...at least it's hidden in the function
    if (goals.forall((g) => {
      currentState = achieve(currentState, g, goalStack)
      currentState contains g // achieve actually returns Nil so this could be currentState == Nil,
                              // but achieved changed so it no longer returned Nil on failure then
                              // testing for Nil would break this function, while testing for the
                              // goal would still work
    })) currentState else Nil */
  }
  
  /** achieve the specified goal from the state using Operators
   *  achieve works by finding all of the Operators
   *  that can potentially achieve the specified goal, and trying to apply each
   *  one until one succeeds.
   *
   *  achieve recurses on itself because it calls applyOp,
   *  which called achieveAll on the operator's preconditions, which in
   *  turn invokes achieve on each of those preconditions.
   *
   *  @param state the list of current conditions
   *  @param goal the goal condition to be satisfied
   *  @param goalStack the set of goals currently being considered
   *  @param ops implicit get of operators to use to satisfy goal
   *  @return new state if successful, Nil on failure
   */
  private def achieve(state: List[Condition], goal: Condition, goalStack: List[Condition])(implicit ops: List[Operator]): List[Condition] = {
    if (state contains goal) { // goal is already satisfied, return state unchanged
      dbgIndent(goalStack.size, "Goal: " + goal.name + " (already in state)")
      state
    } else if (goalStack contains goal) { // recursive goal encountered, return failure
      dbgIndent(goalStack.size, "Goal: " + goal.name + " (already on stack, failing)")
      Nil
    } else { // goal has yet to be achieved, try operators until one succeeds or all fail
      dbgIndent(goalStack.size, "Goal: " + goal.name)
    	val updatedGoalStack = goal :: goalStack // in the Lisp version this was done in applyOp
      // some is a port of the Lisp some function
      // filter ops down down to operators that are appropriate to those goals
      //   attempt to apply each operator until one succeeds
      //   return the result of applying that operator
    	some(ops.filter((op) => op appropriate goal), applyOp(state, _: Operator, updatedGoalStack))
    }
  }
  
   /** attempt to apply the specified operator to achieve the goal
    *  applyOp attempt to achieveAll the preconditions for the
    *  Operator then applies it.
    *  Applying the Operator consists of removing its delete list from the
    *  state and adding its add list to the state
    *  This method recurses on itself through achieveAll to achieve.  
    *  @param state the current state
    *  @param op the operator to be applied
    *  @param goalStack the current list of goals under consideration
    *  @param ops implicit parameter containing the operators
    *  @return the updated state on success, Nil on failure
    */
  private def applyOp(state: List[Condition], op: Operator, goalStack: List[Condition])(implicit ops: List[Operator]): List[Condition] = {
    dbgIndent(goalStack.size, "Consider: " + op.name)
    achieveAll(state, op.preconditions, goalStack) match {
      case Nil => Nil
      case state2 => {
        dbgIndent(goalStack.size, "Action: " + op.name)
        state2.remove((c) => op.del contains c) ::: op.add
      } // case achieveAll was successful
    } // match on result of achieveAll
  }
} // object gps2
 
object SchoolProblem {
  import gps2._
  val basicStartState = startState("son at home","car needs battery", "have money", "have phone book")
  val basicGoalState = goalState("son at school")
  
  def main(args : Array[String]) : Unit = {
    Console.println("The Get-Son-to-School Problem")
    Console.println("Initial: " + basicStartState.mkString(", "))
    Console.println("Goal: " + basicGoalState.mkString(", "))
    Console.println("Solving...")
    val r = GPS(basicStartState, basicGoalState)(operators)
    Console.println("Done.")
    Console.println("Solution: ")
    Console.println(r.mkString("\n"))
  }
  
  val operators = 
      Op("drive son to school",
            preconds("son at home", "car works"), 
            addList("son at school"),
            delList("son at home")) ::
      Op("shop installs battery",
            preconds("car needs battery", "shop knows problem", "shop has money"),
            addList("car works"),
            delList()) ::
      Op("tell shop problem",
            preconds("in communication with shop"),
            addList("shop knows problem"),
            delList()) ::
      Op("telephone shop",
            preconds("know phone number"),
            addList("in communication with shop"),
            delList()) ::
      Op("ask phone number",
            preconds("in communication with shop"),
            addList("know phone number"),
            delList()) ::
      Op("look up number",
            preconds("have phone book"),
            addList("know phone number"),
            delList()) ::
      Op("give shop money",
            preconds("have money"),
            addList("shop has money"),
            delList("have money")) :: Nil
}
 
object MonkeyProblem {
  import gps2._
  
  val basicStartState = startState("at door", "on floor", "has ball", "hungry", "chair at door")
  val basicGoalState = goalState("not hungry")
  
  def main(args : Array[String]) : Unit = {
    Console.println("The Monkey-and-Bananas Problem")
    Console.println("Initial: " + basicStartState.mkString(", "))
    Console.println("Goal: " + basicGoalState.mkString(", "))
    Console.println("Solving...")
    val r = GPS(basicStartState, basicGoalState)(operators)
    Console.println("Done.")
    Console.println("Solution:")
    Console.println(r.mkString("\n"))
  }
  
  val operators =
    Op("climb on chair",
        preconds("chair at middle of room", "at middle of room", "on floor"),
        addList("at bananas", "on chair"),
        delList("at middle of room", "on floor")) ::
    Op("push chair from door to middle of room",
        preconds("chair at door", "at door"),
        addList("chair at middle of room", "at middle of room"),
        delList("chair at door", "at door")) :: 
    Op("walk from door to middle of room",
        preconds("at door", "on floor"),
        addList("at middle of room"),
        delList("at door")) ::
    Op("grasp bananas",
        preconds("at bananas", "empty handed"),
        addList("has bananas"),
        delList("empty handed")) ::
    Op("drop ball",
        preconds("has ball"),
        addList("empty handed"),
        delList("has ball")) ::
    Op("eat bananas",
        preconds("has bananas"),
        addList("empty handed", "not hungry"),
        delList("has bananas", "hungry")) :: Nil
}
 
object Utilities {
  var dbg = true
  def dbgIndent(depth: Int, msg: String): Unit = {
    if (dbg) {
      def indent(depth: Int): Unit = {
        if (depth <= 0) None
        else {
          Console.print(" ")
          indent(depth - 1)
        }
      }
      indent(depth)
      Console.println(msg)
    } else None
  }
  
  /** emulate the Lisp some function
   *  @param list the list to be processed
   *  @param f the function to be applied to each element
   *  @return the first non-empty list returned by f
  */
  def some[A, B](list: List[A], f: (A) => List[B]): List[B] = {
    list match {
      case first :: rest => f(first) match {
        case Nil => some(rest, f)
        case result => result
      }
      case _ => Nil
    }
  }
}