Как сопоставление с образцом в Scala реализовано на уровне байт-кода?

Как сопоставление с образцом в Scala реализовано на уровне байт-кода?

Это похоже на серию if (x instanceof Foo) конструкций или что-то еще? Каковы его последствия для производительности?

Например, учитывая следующий код (из Scala By Example, страницы 46- 48), как бы выглядел эквивалентный Java-код для метода eval?

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)
}

P.S. Я могу читать байт-код Java, поэтому мне было бы достаточно представления байт-кода, но, вероятно, другим читателям было бы лучше знать, как он будет выглядеть как Java-код.

P.P.S. Дает ли книга Программирование на Scala ответ на этот вопрос? и подобные вопросы о том, как реализована Scala? Я заказал книгу, но она еще не пришла.


person Esko Luontola    schedule 15.04.2009    source источник
comment
Почему бы вам просто не скомпилировать пример и не разобрать его с помощью дизассемблера байт-кода Java?   -  person Zifre    schedule 16.04.2009
comment
Я, наверное, так и сделаю, если только кто-то сначала не ответит хорошо. Но сейчас я хочу немного поспать. ;)   -  person Esko Luontola    schedule 16.04.2009
comment
Вопрос будет полезен другим читателям!   -  person djondal    schedule 03.07.2011
comment
@djondal: лучший способ сказать это - просто проголосовать за вопрос :-)   -  person Blaisorblade    schedule 10.02.2012


Ответы (4)


Низкий уровень можно исследовать с помощью дизассемблера, но краткий ответ заключается в том, что это набор if / elses, где предикат зависит от шаблона.

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

Вы можете сделать гораздо больше с такими шаблонами, как или шаблоны и комбинации, такие как case Foo (45, x), но в целом это просто логические расширения того, что я только что описал. У шаблонов также могут быть охранники, которые являются дополнительными ограничениями для предикатов. Также есть случаи, когда компилятор может оптимизировать сопоставление с образцом, например, когда есть некоторое перекрытие между случаями, он может немного объединить вещи. Расширенные шаблоны и оптимизация являются активной областью работы в компиляторе, поэтому не удивляйтесь, если байтовый код существенно улучшится по сравнению с этими базовыми правилами в текущей и будущих версиях Scala.

В дополнение ко всему, вы можете написать свои собственные экстракторы в дополнение к тем, которые Scala использует по умолчанию для классов case, или вместо них. Если вы это сделаете, то стоимость сопоставления с образцом будет равна стоимости того, что делает экстрактор. Хороший обзор можно найти в http://lamp.epfl.ch/~emir/written/MatchingObjectsWithPatterns-TR.pdf

person James Iry    schedule 16.04.2009
comment
Я считаю, что это текущая ссылка: информация .epfl.ch / record / 98468 / files / - person greenoldman; 11.03.2018

Джеймс (вверху) сказал это лучше всего. Однако, если вам интересно, всегда полезно посмотреть на дизассемблированный байт-код. Вы также можете вызвать scalac с параметром -print, который распечатает вашу программу со всеми удаленными специфическими для Scala функциями. По сути, это Java в одежде Scala. Вот соответствующие scalac -print выходные данные для предоставленного вами фрагмента кода:

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)
};
person Jorge Ortiz    schedule 16.04.2009

Начиная с версии 2.8 в Scala есть аннотация @switch. Цель состоит в том, чтобы гарантировать, что сопоставление шаблонов будет скомпилировано в tablewitch или поисковый переключатель вместо серии условных if операторов.

person om-nom-nom    schedule 14.08.2012
comment
когда выбрать @switch вместо обычного, если еще? - person Aravind Yarram; 28.07.2016
comment
использование @switch более эффективно, чем обычное сопоставление с образцом. поэтому, если все случаи содержат постоянные значения, вы всегда должны использовать @switch (потому что реализация байт-кода будет такой же, как в java switch вместо многих if-else) - person lev; 21.04.2018

Чтобы расширить комментарий @Zifre: если вы читаете это в будущем и компилятор scala принял новые стратегии компиляции, и вы хотите знать, что они из себя представляют, вот как вы узнаете, что он делает.

Скопируйте и вставьте свой match код в автономный файл примера. Запустите scalac для этого файла. Затем запустите javap -v -c theClassName$.class.

Например, я поместил в /tmp/question.scala следующее:

object question {
  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)
  }
}

Затем я запустил scalac question.scala, который произвел кучу *.class файлов. Немного покопавшись, я нашел выражение соответствия внутри question$.class. Результат javap -c -v question$.class доступен ниже.

Поскольку мы ищем конструкцию потока управления условием, знание набора инструкций байт-кода Java предполагает, что поиск if должен быть хорошим местом для начала.

В двух местах мы находим пару последовательных строк в форме isinstanceof <something>; ifeq <somewhere>, что означает: если последнее вычисленное значение не является экземпляром something, тогда goto somewhere. (ifeq равно jump if zero, а isinstanceof дает вам ноль, чтобы представить ложь.)

Если вы проследите за потоком управления, вы увидите, что он согласуется с ответом @Jorge Ortiz: мы делаем if (blah isinstanceof something) { ... } else if (blah isinstanceof somethingelse) { ... }.

Вот результат javap -c -v question$.class:

Classfile /tmp/question$.class
  Last modified Nov 20, 2020; size 956 bytes
  MD5 checksum cfc788d4c847dad0863a797d980ad2f3
  Compiled from "question.scala"
public final class question$
  minor version: 0
  major version: 50
  flags: (0x0031) ACC_PUBLIC, ACC_FINAL, ACC_SUPER
  this_class: #2                          // question$
  super_class: #4                         // java/lang/Object
  interfaces: 0, fields: 1, methods: 3, attributes: 4
Constant pool:
   #1 = Utf8               question$
   #2 = Class              #1             // question$
   #3 = Utf8               java/lang/Object
   #4 = Class              #3             // java/lang/Object
   #5 = Utf8               question.scala
   #6 = Utf8               MODULE$
   #7 = Utf8               Lquestion$;
   #8 = Utf8               <clinit>
   #9 = Utf8               ()V
  #10 = Utf8               <init>
  #11 = NameAndType        #10:#9         // "<init>":()V
  #12 = Methodref          #2.#11         // question$."<init>":()V
  #13 = Utf8               eval
  #14 = Utf8               (Lquestion$Expr;)I
  #15 = Utf8               question$Number
  #16 = Class              #15            // question$Number
  #17 = Utf8               n
  #18 = Utf8               ()I
  #19 = NameAndType        #17:#18        // n:()I
  #20 = Methodref          #16.#19        // question$Number.n:()I
  #21 = Utf8               question$Sum
  #22 = Class              #21            // question$Sum
  #23 = Utf8               e1
  #24 = Utf8               ()Lquestion$Expr;
  #25 = NameAndType        #23:#24        // e1:()Lquestion$Expr;
  #26 = Methodref          #22.#25        // question$Sum.e1:()Lquestion$Expr;
  #27 = Utf8               e2
  #28 = NameAndType        #27:#24        // e2:()Lquestion$Expr;
  #29 = Methodref          #22.#28        // question$Sum.e2:()Lquestion$Expr;
  #30 = NameAndType        #13:#14        // eval:(Lquestion$Expr;)I
  #31 = Methodref          #2.#30         // question$.eval:(Lquestion$Expr;)I
  #32 = Utf8               scala/MatchError
  #33 = Class              #32            // scala/MatchError
  #34 = Utf8               (Ljava/lang/Object;)V
  #35 = NameAndType        #10:#34        // "<init>":(Ljava/lang/Object;)V
  #36 = Methodref          #33.#35        // scala/MatchError."<init>":(Ljava/lang/Object;)V
  #37 = Utf8               this
  #38 = Utf8               e
  #39 = Utf8               Lquestion$Expr;
  #40 = Utf8               x
  #41 = Utf8               I
  #42 = Utf8               l
  #43 = Utf8               r
  #44 = Utf8               question$Expr
  #45 = Class              #44            // question$Expr
  #46 = Methodref          #4.#11         // java/lang/Object."<init>":()V
  #47 = NameAndType        #6:#7          // MODULE$:Lquestion$;
  #48 = Fieldref           #2.#47         // question$.MODULE$:Lquestion$;
  #49 = Utf8               question
  #50 = Class              #49            // question
  #51 = Utf8               Sum
  #52 = Utf8               Expr
  #53 = Utf8               Number
  #54 = Utf8               Code
  #55 = Utf8               LocalVariableTable
  #56 = Utf8               LineNumberTable
  #57 = Utf8               StackMapTable
  #58 = Utf8               SourceFile
  #59 = Utf8               InnerClasses
  #60 = Utf8               ScalaInlineInfo
  #61 = Utf8               Scala
{
  public static final question$ MODULE$;
    descriptor: Lquestion$;
    flags: (0x0019) ACC_PUBLIC, ACC_STATIC, ACC_FINAL

  public static {};
    descriptor: ()V
    flags: (0x0009) ACC_PUBLIC, ACC_STATIC
    Code:
      stack=1, locals=0, args_size=0
         0: new           #2                  // class question$
         3: invokespecial #12                 // Method "<init>":()V
         6: return

  public int eval(question$Expr);
    descriptor: (Lquestion$Expr;)I
    flags: (0x0001) ACC_PUBLIC
    Code:
      stack=3, locals=9, args_size=2
         0: aload_1
         1: astore_2
         2: aload_2
         3: instanceof    #16                 // class question$Number
         6: ifeq          27
         9: aload_2
        10: checkcast     #16                 // class question$Number
        13: astore_3
        14: aload_3
        15: invokevirtual #20                 // Method question$Number.n:()I
        18: istore        4
        20: iload         4
        22: istore        5
        24: goto          69
        27: aload_2
        28: instanceof    #22                 // class question$Sum
        31: ifeq          72
        34: aload_2
        35: checkcast     #22                 // class question$Sum
        38: astore        6
        40: aload         6
        42: invokevirtual #26                 // Method question$Sum.e1:()Lquestion$Expr;
        45: astore        7
        47: aload         6
        49: invokevirtual #29                 // Method question$Sum.e2:()Lquestion$Expr;
        52: astore        8
        54: aload_0
        55: aload         7
        57: invokevirtual #31                 // Method eval:(Lquestion$Expr;)I
        60: aload_0
        61: aload         8
        63: invokevirtual #31                 // Method eval:(Lquestion$Expr;)I
        66: iadd
        67: istore        5
        69: iload         5
        71: ireturn
        72: new           #33                 // class scala/MatchError
        75: dup
        76: aload_2
        77: invokespecial #36                 // Method scala/MatchError."<init>":(Ljava/lang/Object;)V
        80: athrow
      LocalVariableTable:
        Start  Length  Slot  Name   Signature
            0      81     0  this   Lquestion$;
            0      81     1     e   Lquestion$Expr;
           20      61     4     x   I
           47      34     7     l   Lquestion$Expr;
           54      27     8     r   Lquestion$Expr;
      LineNumberTable:
        line 6: 0
        line 7: 2
        line 8: 27
        line 6: 69
      StackMapTable: number_of_entries = 3
        frame_type = 252 /* append */
          offset_delta = 27
          locals = [ class question$Expr ]
        frame_type = 254 /* append */
          offset_delta = 41
          locals = [ top, top, int ]
        frame_type = 248 /* chop */
          offset_delta = 2
}
SourceFile: "question.scala"
InnerClasses:
  public static #51= #22 of #50;          // Sum=class question$Sum of class question
  public static abstract #52= #45 of #50; // Expr=class question$Expr of class question
  public static #53= #16 of #50;          // Number=class question$Number of class question
  ScalaInlineInfo: length = 0xE (unknown attribute)
   01 01 00 02 00 0A 00 09 01 00 0D 00 0E 01
  Scala: length = 0x0 (unknown attribute)
person Jonas Kölker    schedule 20.11.2020