El algoritmo de simplificación no parece estar bien

[javierfernandes]

https://github.com/tadp-utn-frba/tadp-clases/blob/7ae855de96a8589b3f32e084112b148f937ea34b/objetos-puro/src/main/scala/ar/edu/utn/tadp/microprocesador/puro/Instructions.scala#L22

Che, meee parece que ese algoritmo no está bien. Entiendo la idea de que va tomando de a pares que pueden convertirse en 0, 1, 2 instrucciones (0 en caso de simplificar 2 SWAPs ponele, 1 en caso de dejar un sólo LOAD, y ambos 2 elementos en los demás casos). El simplified le da esa especie de "cursor" para seguir adelante analizando los siguientes pares. El problema está en que cuando simplified > 0 entonces estamos procesando un par "de la mitad" de la lista. Y lo que está "antes" de ese cursor se pierde.

ejemplo gráfico

[ ADD, SWAP, BLAH, SWAP, SWAP, ADD, STORE, LOAD ]
                                   |
                              simplified = 3

[ ADD, SWAP, BLAH ]       []              [ADD, STORE, LOAD}
   < ESTO SE PIERDE>

Y queda así
[ADD, STORE, LOAD]

Esto se ve en un test cuando en un programa tengo 2 pares de instrucciones simplificables. Cuando el algoritmo simplifica la 2da, pierde todo lo que tenía antes ya procesado.

[javierfernandes]

Bueno, ahí creo que tengo una solución. Está en castellano, pero es la misma idea.

    def simplificar() {
      var i = 0
      while (i < instrucciones.size - 1) {
        val instruccion = instrucciones(i)
        val siguiente = instrucciones(i + 1)
        val simplificado = instruccion.simplificar(siguiente)

        instrucciones = instrucciones.take(i) ++ simplificado ++ instrucciones.drop(i + 2);
        if (simplificado == Seq(instruccion, siguiente))
          i += 1
      }
    }

Básicamente va manteniendo los elementos anteriores a la posición del cursor. Y se asegura de calcular bien el resto (parte derecha de la lista) en base al cursor.

Una salvedad de esta implementación es que se basa en la idea de que hay que avanzar (1) sólo en el caso en que no haya habido un efecto en la simplificación. Ej.. si mando a simplificar [ADD, SWAP] y me da [ADD, SWAP] entonces no tiene sentido seguir tratando de simplificar ese par, y muevo el cursor en 1. En todo otro caso se mantiene en la misma posición porque quiere decir que hubo un cambio, una simplificación, y habría que reevaluar a ver si ahora surge otra. Me pareció mejor dejar eso más explícito con el if y el +1 en lugar de usar el tamaño de la lista de retorno, que sí, era más genérico y sumado al 0.max terminaba abarcando todos los casos sin un if, pero me pareció más oscuro de entender. En fin, la salvedad más importante es que para que funcione la comparación de ver si cambió el par a simplificar, las instrucciones lógicamente deberían implementar buenos equals / hashcode. Que si uno ya tiene un modelo más funcionaloide con case classes, ya no tiene problema. Pero si viene de un modelo objetoso y generó de alguna manera nuevas instancias aunque sean igual va a dar false y nunca continuar. Igual creo que nunca pasaría eso, por las reglas de simplificación. Pero es otro detalle a tener en cuenta a la hora de analizar una solución más OOP vs una más FP. En la FP me abstraigo un poco de pensar en identidad e igualdad, ya que mis modelos son value objects.

Bueno sr, si usted ha llegado hasta aquí entonces somos dos los que estamos procrastinando algo (en mi caso terminar de preparar la clase de mañana, ud sabrá el suyo.).

Arrivederci !

[javierfernandes]

Bueno, tampoco se banca simplificar la última instrucción, lógicamente porque corta antes, y porque la API de simplificación está acoplada a simplificar de a pares.

Este test no funcaría

[ADD, IF] => [ADD]

En cambio este sí

[IF, ADD] => [ADD]