Aula de revisão de LP 31/07/13

Aula de revisão de 31/07/13

Na aula fizemos uma revisão dos assuntos que estão na Lista 4. Primeiro mostrei outros exemplos de fragmentos de um interpretador que usam diretamente a memória ao invés de usar a abstração de ações, e mostrei possíveis falhas no uso linear da memória.

case Deref(e) => mem => {
  val (ve, nmem) = e.eval(funs)(env)(mem)
  ve match {
    case Caixa(l) => (nmem(l), nmem)
    // Bugs de linearidade, reparem como usamos
    // memória, mem, que já foi usada
    // case Caixa(l) => (nmem(l), mem)
    // case Caixa(l) => (mem(l), nmem)
    case _ => sys.error("valor não é referência")
  }
}

Mais alguns exemplos, usando Seq. Primeiro o caso correto:

case Seq(e1, e2) => mem => {
  val (_, mem1) = e1.eval(funs)(env)(mem)
  val (v, mem2) = e2.eval(funs)(env)(mem1)
  (v, mem2)
}

Agora algumas versões com bugs de linearidade:

case Seq(e1, e2) => mem => {
  val (_, mem1) = e1.eval(funs)(env)(mem)
  val (v, mem2) = e2.eval(funs)(env)(mem1)
  (v, mem) // descartando todos os efeitos
}

case Seq(e1, e2) => mem => {
  val (_, mem1) = e1.eval(funs)(env)(mem)
  // descartando os efeitos de e1
  val (v, mem2) = e2.eval(funs)(env)(mem)
  (v, mem2)
}

case Seq(e1, e2) => mem => {
  val (_, mem1) = e1.eval(funs)(env)(mem)
  val (v, mem2) = e2.eval(funs)(env)(mem1)
  // descartando os efeitos de e2
  (v, mem1)
}

A ordem de avaliação é dada pela “costura” da memória entre as expressões, então no exemplo correto de Seq acima primeiro executamos e1 depois e2. Podemos trocar as chamadas a eval sem mudar a ordem, usando aplicação parcial:

case Seq(e1, e2) => mem => {
  val a2 = e2.eval(funs)(env)
  val a1 = e1.eval(funs)(env)
  val (_, mem1) = a1(mem)
  val (v, mem2) = a2(mem1)
  (v, mem2)
}

Para trocar a ordem de avaliação precisamos mudar a “costura”:

case Seq(e1, e2) => mem => {
  val a2 = e2.eval(funs)(env)
  val a1 = e1.eval(funs)(env)
  val (_, mem1) = a2(mem)
  val (v, mem2) = a1(mem1)
  (v, mem2)
}

Quando introduzimos continuações, o que acontece é que execução não mais retorna seus resultados (o valor e a memória afetada pelos efeitos colaterais), mas os passa adiante para uma continuação:

case Deref(e) => k => mem
  // "ve" e "nmem" eram o que "e" retornava
  e.eval(funs)(env)(ve => nmem =>
    ve match {
      case Caixa(l) => k(nmem(l))(nmem) // usamos "nmem"
      // Bugs de linearidade, reparem como usamos
      // memória, mem, que já foi usada
      // case Caixa(l) => k(nmem(l))(mem)
      // case Caixa(l) => k(mem(l))(nmem)
      case _ => sys.error("valor não é referência")
    }
  )(mem) // usamos "mem"

Notem que ter os mesmos problemas de lineraridade que tínhamos antes. Também podemos eliminar mem, deixando a chamada de eval parcial e eliminando uma fonte de bugs:

case Deref(e) => k =>
  // "ve" e "nmem" eram o que "e" retornava
  e.eval(funs)(env)(ve => nmem =>
    ve match {
      case Caixa(l) => k(nmem(l))(nmem) // usamos "nmem"
      case _ => sys.error("valor não é referência")
    }
  )

Ainda precisamos de nmem, pois temos que acessar uma posição da memória.

O caso de Seq tem o mesmo paralelismo entre a versão sem continuações e a com continuações:

case Seq(e1, e2) => k => mem =>
  e1.eval(funs)(env)(_ => mem1 => 
    e2.eval(funs)(env)(v => mem2 =>
      k(v)(mem2)) // usamos mem2
    (mem1)) // usamos mem1
  (mem) // usamos mem

Mas ao contrário de Deref, em Seq só estamos passando a memória adiante, então podemos simplificar e deixá-la implícita:

case Seq(e1, e2) => k => 
  e1.eval(funs)(env)(_ =>  
    e2.eval(funs)(env)(v => 
      k(v))) // usamos mem1

A ideia da recursão aberta é poder reutilizar uma função já existente, mas modificar o comportamento de chamadas recursivas dentro dessa função. Podemos fazer uma função map que aplica a função f ao resultado de cada chamada da função super:

-- aplica f ao argumento depois de passar pra super

fun map(super, f)
  fun (self, x)
    (f)((super)(self, x))
--  (f)((self)(super, x))  -- faz fat(5) * 2 * 2

--  (f)((self)(self, x))   -- loop infinito!

--  (f)((super)(super, x)) -- faz fat(5) * 2

  end
end

let fat = fun (f, n)
            if n < 2 then
              1
            else
              n * (f)(f, n-1)
            end
          end,
    mf = map(fat, fun (x) 2 * x end)
in
  (mf)(mf, 5) -- 3840.0

end

Os nomes super e self em map deixam mais claro o que está acontecendo. Em proto o parâmetro self é implícito, então temos a recursão aberta de map sem a chance dos erros que estão comentados:

object fat(0)
  def apply(n)
    if n < 2 then 1
    else n * self.apply(n - 1) end
  end
end

object map(0)
  def make(f1, f2)
    object (1) extends f1
      def init(f)
        @0 = f;
        self
      end
      def apply(x)
        @0.apply(super.apply(x))
      end
    end).init(f2)
  end
end

object double(0)
  def apply(x)
    2 * x
  end
end

(map.make(fat, double)).apply(5) -- 3840

Quando chamamos super.apply(x), o método chamado é o do objeto sendo extendido (no nosso caso, fat), mas self dentro desse método será o objeto criado em make, portanto chamadas recursivas (self.apply) no apply de fat caem novamente no objeto que criamos em make, e temos a recursão aberta.

Última Atualização: 2016-05-18 10:58