создание двух связанных AST с запечатанными классами case в Scala

Всякий раз, когда мне приходилось создавать AST в Scala, я использовал шаблон абстрактного запечатанного типажа/кейса. До сих пор это работало очень хорошо, проверка соответствия шаблонов компилятором - большая победа.

Однако теперь я столкнулся с проблемой, с которой не могу справиться. Что делать, если у меня есть 2 языка, где один является подмножеством другого? В качестве простого примера рассмотрим лямбда-исчисление, в котором каждая переменная связана, и другой родственный язык, в котором переменные могут быть связаны или свободны.

Первый язык:

  abstract sealed class Expression

  case class Variable(val scope: Lambda, val name:String) extends Expression

  case class Lambda(val v: Variable, val inner: Expression) extends Expression

  case class Application(val function: Expression, val input: Expression) extends Expression

Второй язык:

  abstract sealed class Expression

  case class Variable(val name:String) extends Expression

  case class Lambda(val v: Variable, val inner: Expression) extends Expression

  case class Application(val function: Expression, val input: Expression) extends Expression

Где единственным изменением является удаление области действия из Variable.

Как видите, избыточности много. Но поскольку я использую запечатанные классы, трудно придумать хороший способ расширить его. Еще одна проблема их объединения заключается в том, что теперь каждая лямбда и приложение должны отслеживать язык своих параметров на уровне типа.

Этот пример не так уж плох, потому что он очень маленький, но представьте ту же проблему для строгого HTML/слабого HTML.


scala case-class abstract-syntax-tree lambda-calculus sealed
person user833970    schedule 14.05.2014    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Классический ответ на эту проблему — иметь один общий AST и дополнительный проход для проверки. Вам придется жить с AST, которые синтаксически правильно сформированы, но не проходят проверку (проверку типов).

Если вы хотите различать на уровне типа, проход проверки типа может создать новый AST. Возможно, вы сможете использовать для этого типы, зависящие от пути.

В качестве примечания, ваш пример, кажется, имеет цикл: для создания Lambda вам нужен Variable, но для создания Variable вам нужен внешний Lambda.

person Iulian Dragos    schedule 14.05.2014
comment
Я заметил циклы, я потерял некоторую корректность, пытаясь создать четкий простой пример. - person user833970; 14.05.2014

arrow_upward
1
arrow_downward

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

def tryEtaReduce(x: Expression): Option[Expression] =
  x match {
    case Lambda(v1, Application(f, v2: Variable)) if v1 == v2 => Some(f)
    case _ => None
  }

Для приведенной выше функции будет работать обобщение, подобное следующему, хотя оно и имеет очевидную безобразность:

trait AST {
  sealed trait Expression

  type Scope

  case class Variable(scope: Scope, name: String) extends Expression
  case class Lambda(v: Variable, inner: Expression) extends Expression
  case class Application(function: Expression, input: Expression) extends Expression
}

object BoundAST extends AST {
  type Scope = Lambda
}

object FreeAST extends AST {
  type Scope = Unit
}

trait ASTOps {
  val ast: AST
  import ast._

  def tryEtaReduce(x: Expression): Option[Expression] =
    x match {
      case Lambda(v1, Application(f, v2: Variable)) if v1 == v2 =>
        Some(f)
      case _ =>
        None
    }
}
person Owen    schedule 14.05.2014