Finalmente estou voltando para as traduções dos artigos de Ola Bini. Posso demorar para traduzir, mas espero conseguir traduzir toda a série.

Tradução do seguinte artigo: the general problem solver part 2 Divide em duas partes por ser um artigo grande. A próxima parte você encontra em: http://www.agaelebe.com.br/traducao-paipr-o-resolvedor-de-problemas-gerais-parte-2-continuacao

No último artigo desta série eu descrevi uma simples versão do Resolvedor de Problemas Gerais. Este artigo analisará uma versão mais completa que corrige alguns dos problemas que discuti anteriormente. O primeiro problema a se resolver é que em certos casos pode ser um pouco difícil depurar a saída de nosso resolvedor. Caso ele falhe, só sabemos que ele falhou, mas não quanto ele avançou no problema. Então vamos começar criando um framework customizado para debug (lib/ch04/dbg.rb):

$dbg_ids = []

def dbg(id, format, *args)
  if $dbg_ids.include?(id)
    $stderr.puts(format%args)
  end
end

def debug(*ids)
  $dbg_ids = ($dbg_ids + ids).uniq
end

def undebug(*ids)
  $dbg_ids -= ids
end

def dbg_indent(id, indent, format, *args)
  if $dbg_ids.include?(id)
    $stderr.print "  "*indent
    $stderr.puts(format%args)
  end
end

Este código usa uma variável global para decidir quais declarações de debug devem ser usadas. Podemos habilitar ou desabilitar ids específicos usando os métodos debug e undebug. Além disso, podemos usar dbg e dbg_indent para realmente escrever algo na tela.

Perceba que eu usei o operador sprintf (%) para fazer a formatação das strings internas ao sistema.

Agora é hora de olharmos para o GPS2, que apresenta soluções para os problemas “correndo ao redor do quarteirão”, ” derrotas do pré-requisito irmão” (prerequisite clobbers sibling), “saltando antes de olhar” e “subobjetivo recursivo”.

Uma das mudanças mais interessantes é que esta versão não imprimirá nada, mas ao invés disso retornará uma lista de status que descreve as ações tomadas. Mais tarde isto dará mais flexibilidade em relação a como o código é usado.

Antes de começarmos há algumas coisas que precisamos adicionar para fazer com que a saída seja aceitável. Faremos isso representando as operações de forma um pouco diferente, incluindo na lista de adição uma ação composta que incluirá o símbolo executing e o nome da ação. Também precisamos de um equivalente da função some (alguns). Por fim, precisamos ter algo que possa criar novas operações incluindo a parte de execução na lista de adições.

Este código poder ser visto em lib/ch04/gps2.rb:

require 'gps'
require 'gps_no_clobber'
require 'dbg'

module Enumerable
  def some?
    self.each do |v|
      result = yield v
      return result if result
    end
  end
end

class GPS::Op
  def convert!
    unless self.add_list.any? do |l|
        l.is_a?(Array) && l.first == :executing
      end
      self.add_list << [:executing, self.action]
    end
    self
  end
end

GPS::SCHOOL_OPS.each do |op|
  op.convert!
end

class GPS2 < GPS
  class << self
    def op(action, parts = {})
      GPS::Op.new(action,
             parts[:preconds],
             parts[:add_list],
             parts[:del_list]).convert!
    end
  end
end

Neste caso eu optei por fazer uma subclasse do GPS2 e usei os helperes existentes no gps e no gps_no_clobber, embora no final das contas a maioria dos métodos serão sobrescritos.

Eu defini o método some? (alguns) no módulo Enumarable; Ele é bastante similar a versão Ruby do find/detect. A única diferença é que precisamos salvar o resultado do bloco e realmente retorná-lo ao invés do valor que enviamos para o bloco.

Abri a classe GPS::Op e adicionei o método convert!. Perceba que nomeei-o com um exclamação (bang) , já que ele pode modificar a instância atual. Também decidi não seguir a convenção retornando nil de um método com exclamação. Ao invés disso, retorno self porque isso fará meu código um pouco mais simples em certas ocasiões. O método convert! checa se a lista de adição já contem um array em que o primeiro elemento é :executing, caso contrário ele adicionará um destes. Isto será mais interessante mais tarde.

O arquivo gps2 também converte todas as operações escolares disponíveis.

Finalmente nós fornecemos um novo método chamado GPS2::op, que irá criar uma nova operação convertida. Perceba que estou usando a convenção de abrir a classe self com class << self. Eu quase sempre prefiro este modo.

O próximo passo é olharmos o novo método solve (resolver). Este será levemente diferente já que agora todos os métodos recebem um argumento de estado para saber em que lugar da avaliação estamos. O único lugar que não recebe o estado é o método solve, já que ele usa o estado inicial dado para inicializar o método. Todos os métodos com exceção do solve também recebem um parâmetro da pilha de objetivos atuais, o que nós ajudará a nos mantermos informado sobre quais objetivos já atingimos.

O método solve se parece com isso (lib/ch04/gps2.rb):

  def solve(*goals)
    achieve_all([[:start]] + @state, goals, []).grep(Array)
  end

O código original em Lisp usa o átomo remove-if #’ (remove se) para filtrar todo o ruído do estado, mas a versão Ruby é muito mais simplificada pelo simples emprego do grep, enviando-o um Array. Você sabia que o grep pode receber qualquer coisas que implementa o método ===, certo?

Para nos mantermos informado do fato de que começamos, adicionamos a lista [:start] ao ínicio do estado atual.

Existem mais três métodos que precisam ser atualizados para que esta implementação rode. Os dois primeiros são achieve_all e achieve (lib/ch04/gps2.rb):

  def achieve_all(state, goals, goal_stack)
    current_state = goals.inject(state) do |current_state, g|
      return [] if current_state.empty?
      achieve(current_state, g, goal_stack)
    end
    if goals.subset_of?(current_state)
      current_state
    else
      []
    end
  end

  def achieve(state, goal, goal_stack)
    dbg_indent(:gps, goal_stack.length, "Goal: %p", goal)

    if state.include?(goal)
      state
    elsif goal_stack.include?(goal)
      []
    else
      @ops.find_all do |op|
        appropriate?(goal, op)
      end.some? do |op|
        apply(state, goal, op, goal_stack)
      end || []
    end
  end

Estes são um pouco mais complicados que na primeira implementação. Isto porque precisamos lidar com algumas coisas com que a primeira implementação não lidava muito bem.

O método achievel_all é definitivamente um pouco mais bagunçado. Isso porque precisamos atualizar o estado atual para cada chamada ao método achieve. No livro de Norvig, a implementação na verdade usa uma variável de estado que era atualizada a cada iteração, mas eu achei que essa modificação explicita não caia bem aqui, especialmente não na presença de inject, que é uma ferramenta perfeita para este tipo de atualização. A única complicação é que nós queremos paralisar tudo se qualquer chamada ao achieve retornar um estado vazio (isso indica que não podemos continuar). Se um objetivo não pode ser alcançado, é óbvio que podemos simplesmente saltá-lo diretamente.

O uso do inject aqui é um pouco diferente já que ele não constrói nada explicitamente mas, ao invés disso, cria uma nova variável que é uma versão modificada da original. Este é um retrabalho (refactoring) que eu gostaria de ver em mutas bases de código, já que é um jeito bastante legal de se livrar da mutação explícita.

Após a construção do estado atual pela chamada de achieve em todos objetivos, também precisamos ter certeza de que todos objetivos ainda fazem parte do estado atual. Fazemos isso com o método subset? (subconjunto) definido no código da primeira versão do GPS.

O método achieve é o primeiro lugar em que usaremos nosso sistema de debugging. O tamanho da pilha de objetivos nos dá um parâmetro óbvio para identação, já que ela ficará maior e maior a medida que a recursão se torna mais profunda. Eu usei %p ao invés de %s pois eu realmente quero a saída inspecionada neste ponto.

O achieve pode rodar de três maneiras. A primeira é quando o objetivo já está no estado atual. Isso significa que já atingimos esse objetivo e tudo está certo.

Se o objetivo está na pilha de objetivos, isso significa que estamos na segunda iteração de uma busca de objetivo recursiva - o que não é bom. Isso significa que falhamos com esse objetivo, portanto retornamos um array vazio.

Finalmente, se nenhuma das situações acima é verdadeira, precisamos encontrar todas as operações apropriadas para o objetivo atual - usando o mesmo método appropriate? do primeiro GPS. Então usamos some? em todas as operações apropriadas. A diferenças entre find/detect e some? fica óbvia aqui - se usassemos find, o resultado seria uma instância de Op, enquanto some? retornará o estado atual retornado pelo método apply chamado dentro do bloco.

No final da avaliação, se some? não encontrar nada, é necessário retornar um array vazio ao invés de nil, já que estou usando o array vazio para representar cada falha (Discutirei isto em maiores detalhes em um artigo comparando Ruby e Common Lisp).

O método faltando no GPS2 é agora o apply. Ele se parecesse com isso (lib/ch04/gps2.rb):

  def apply(state, goal, op, goal_stack)
    dbg_indent(:gps, goal_stack.length, "Consider: %p", op.action)

    state2 = achieve_all(state, op.preconds, [goal] + goal_stack)

    unless state2.empty?
      dbg_indent(:gps, goal_stack.length, "Action: %p", op.action)
      (state2 - op.del_list) + op.add_list
    end
  end

Como você pode ver, usamos dbg_indent em dois lugares diferentes aqui para deixar claro o que está acontecendo enquanto estamos aplicando uma operação. Este também é o lugar em que primeiro fazemos uma recursão para ter certeza de que todas as pré-condições das operações foram satisfeitas. Se recebermos um estado que não está vazio, podemos retornar um novo estado que é modificado pela lista de de remoções e então pela lista de adições.

Uau, isso foi um pouco mais complicado, mas não tão ruim. Vamos ver como essa versão funciona com os problemas que definimos para o GPS anteriormente (lib/ch04/gps2_problem1.rb):

require 'gps2'
require 'pp'

gps = GPS2.new([:son_at_home,
                :car_needs_battery,
                :have_money,
                :have_phone_book],
              GPS::SCHOOL_OPS)
pp gps.solve(:son_at_school)

Se você executá-lo, verá que o resultado bate mais ou menos com os passos que obtemos no primeiro GPS. Eu usei pp para mostrar o resultado da operação. A principal diferença é que a condição de início esta lá também.

Algo bastante simples, como lib/ch04/gps2_problem2 também funciona bem:

 
require 'gps2' 
require 'pp' 

gps = GPS2.new([:son_at_home, 
                :car_works], 
              GPS::SCHOOL_OPS) 
pp gps.solve(:son_at_school) 

O problema que a última versão costuma errar agora funciona corretamente (lib/ch04/gps2_problem3.rb):

 
require 'gps2' 
require 'pp' 

gps = GPS2.new([:son_at_home, 
                :car_needs_battery, 
                :have_money, 
                :have_phone_book], 
              GPS::SCHOOL_OPS) 
pp gps.solve(:have_money, :son_at_school) 

e lib/ch04/gps2_problem4.rb:

 
require 'gps2' 
require 'pp' 

gps = GPS2.new([:son_at_home, 
                :car_needs_battery, 
                :have_money, 
                :have_phone_book], 
              GPS::SCHOOL_OPS) 
pp gps.solve(:son_at_school, :have_money) 

Olhar antes de saltar também falha como previsto (lib/ch04/gps2_problem5.rb):

 
require 'gps2' 
require 'pp' 

gps = GPS2.new([:son_at_home, 
                :car_needs_battery, 
                :have_money], 
              GPS::SCHOOL_OPS) 
pp gps.solve(:son_at_school) 

Problemas bem simples que não requerem nenhuma ação também funcionam corretamente (lib/ch04/gps2_problem6.rb):

 
require 'gps2' 
require 'pp' 

gps = GPS2.new([:son_at_home], 
              GPS::SCHOOL_OPS) 
pp gps.solve(:son_at_home)