¿Cómo se implementa la coincidencia de patrones en Scala a nivel de bytecode?

123

¿Cómo se implementa la coincidencia de patrones en Scala a nivel de bytecode?

¿Es como una serie de if (x instanceof Foo)construcciones, o algo más? ¿Cuáles son sus implicaciones de rendimiento?

Por ejemplo, dado el siguiente código (de Scala By Example, páginas 46-48), ¿cómo se vería el código Java equivalente para el evalmétodo?

abstract class Expr
case class Number(n: Int) extends Expr
case class Sum(e1: Expr, e2: Expr) extends Expr

def eval(e: Expr): Int = e match {
  case Number(x) => x
  case Sum(l, r) => eval(l) + eval(r)
}

PD: Puedo leer el código de bytes de Java, por lo que una representación de código de bytes sería lo suficientemente buena para mí, pero probablemente sería mejor para los otros lectores saber cómo se vería como código de Java.

PPS ¿El libro Programación en Scala da una respuesta a esta y otras preguntas similares sobre cómo se implementa Scala? He ordenado el libro, pero aún no ha llegado.

Esko Luontola
fuente
¿Por qué no compila el ejemplo y lo desmonta con un desensamblador de código de bytes Java?
Zifre el
Probablemente haré eso, a menos que alguien dé una buena respuesta primero. Pero ahora mismo quiero dormir un poco. ;)
Esko Luontola
27
¡La pregunta es útil para otros lectores!
djondal
1
@djondal: la mejor manera de decir eso es simplemente votar la pregunta :-)
Blaisorblade

Respuestas:

96

El nivel bajo se puede explorar con un desensamblador, pero la respuesta corta es que es un montón de if / elses donde el predicado depende del patrón

case Sum(l,r) // instance of check followed by fetching the two arguments and assigning to two variables l and r but see below about custom extractors 
case "hello" // equality check
case _ : Foo // instance of check
case x => // assignment to a fresh variable
case _ => // do nothing, this is the tail else on the if/else

Hay mucho más que puedes hacer con patrones como o patrones y combinaciones como "case Foo (45, x)", pero en general esas son solo extensiones lógicas de lo que acabo de describir. Los patrones también pueden tener guardias, que son restricciones adicionales en los predicados. También hay casos en los que el compilador puede optimizar la coincidencia de patrones, por ejemplo, cuando hay cierta superposición entre los casos, puede unir un poco las cosas. Los patrones avanzados y la optimización son un área activa de trabajo en el compilador, así que no se sorprenda si el código de bytes mejora sustancialmente sobre estas reglas básicas en las versiones actuales y futuras de Scala.

Además de todo eso, puede escribir sus propios extractores personalizados además de o en lugar de los predeterminados que Scala usa para las clases de casos. Si lo hace, el costo de la coincidencia de patrones es el costo de lo que haga el extractor. Una buena descripción general se encuentra en http://lamp.epfl.ch/~emir/written/MatchingObjectsWithPatterns-TR.pdf

James Iry
fuente
Creo que este es el enlace actual: infoscience.epfl.ch/record/98468/files/…
greenoldman
78

James (arriba) lo dijo mejor. Sin embargo, si tiene curiosidad, siempre es un buen ejercicio observar el bytecode desmontado. También puede invocar scalaccon la -printopción, que imprimirá su programa con todas las funciones específicas de Scala eliminadas. Básicamente es Java en la ropa de Scala. Aquí está la scalac -printsalida relevante para el fragmento de código que proporcionó:

def eval(e: Expr): Int = {
  <synthetic> val temp10: Expr = e;
  if (temp10.$isInstanceOf[Number]())
    temp10.$asInstanceOf[Number]().n()
  else
    if (temp10.$isInstanceOf[Sum]())
      {
        <synthetic> val temp13: Sum = temp10.$asInstanceOf[Sum]();
        Main.this.eval(temp13.e1()).+(Main.this.eval(temp13.e2()))
      }
    else
      throw new MatchError(temp10)
};
Jorge Ortiz
fuente
34

Desde la versión 2.8, Scala ha tenido la anotación @switch . El objetivo es garantizar que la coincidencia de patrones se compilará en un interruptor de tabla o de búsqueda en lugar de una serie de ifinstrucciones condicionales .

Om nom nom
fuente
66
¿Cuándo elegir @switch en vez de regular?
Aravind Yarram
2
usar @switches más eficiente que la coincidencia de patrones regular. así que si todos los casos contienen valores constantes, siempre debe usar @switch(porque la implementación del código de bytes será la misma que la de Java en switchlugar de muchos if-else)
lev