用 Scala 3 实现 Jaskell Parsec

Scala 3（项目名 Dotty）在 2020年底发布了 3.0.0-M3 。我从 M1 开始着手升级 Jaskell ，目前已经成功的在 M3 上实现了 Jaskell Parsec 库。

这是一个非常棒的升级，Scala 3提供了完整的 Typeclass 能力。借助 Type Lambda、Typeclass Trait 、Given 和 Extension，我们终于可以比较规范的建立组合子体系。

基础算子实现

现在，我们终于不需要将bind、then这些基础的函数式编程概念都绑定在 Parsec 定义中。现在，我参考 dotty 实现了 Functor -> Applicative -> Monad 定义。

在现代的 Haskell 中， Functor、Applicative、Monad 是顺序继承的。首先我们实现 Functor：

package jaskell

import scala.util.{Failure, Success, Try}

trait Functor[F[_]]:
  def pure[A](x: A): F[A]

  extension[A, B] (x: F[A])

  /** The unit value for a monad */
    def map(f: A => B): F[B]

    def flatMap(f: A => F[B]): F[B]

given Functor[List] with
  def pure[A](x: A) = List(x)
  extension[A, B] (xs: List[A])
    def map(f: A => B): List[B] =
      xs.map(f) // List already has a `map` method
    def flatMap(f: A => List[B]): List[B] = xs.flatMap(f)

这里的版本跟 dotty 官方那篇 typeclasses 教程里的实现不太一样，这是因为 flatMap 本身是一个极其重要的方法，Scala 的 for 语法直接依赖 flatMap 和 map。如果照搬 Haskell 的设计，在 Monad 中实现 flatMap（以及bind和do），那么 Scala 语法级别的 for yield 表达式就会显得很奇怪，而我还需要在 Applicative 实现中大量使用它。所以，我将 flatMap 和 map 放到了 Functor 中。

然后我们实现 Applicative：

package jaskell

import scala.util.{Try, Success}

trait Applicative[F[_]] extends Functor[F] {
  extension[A, B] (fa: F[A => B])
    def <*>(fb: F[A]): F[B] = for {
      f <- fa
      a <- fb
    } yield f(a)

    def <|>(fb: F[A => B]): F[A => B] =
      for {
        a <- fa
        b <- fb
      } yield (arg: A) => try {
        a(arg)
      } catch {
        _ => b(arg)
      }

  extension[A, B] (x: F[A])
    def *>(bx: F[B]) = for {
      _ <- x
      b <- bx
    } yield b

    def <*(bx: F[B]) = for {
      a <- x
      _ <- bx
    } yield a

  extension[A, B, C] (fx: F[(A, B) => C])
    def liftA2(ax: F[A], bx: F[B]): F[C] = for {
      f <- fx
      a <- ax
      b <- bx
    } yield f(a, b)
}

given tryApplictive[Arg]: Applicative[[Result] =>> Arg => Try[Result]] with {
  def pure[T](arg: T): Arg => Try[T] = x => Success(arg)

  extension[A, B] (fa: Arg => Try[A]) {
    def map(f: A => B): Arg => Try[B] = arg => fa(arg).map(f)

    def flatMap(fb: A => Arg => Try[B]): Arg => Try[B] = arg => fa(arg).flatMap(x => fb(x)(arg))
  }

  extension[A] (fa: Arg => Try[A]) {
    def <|>(fb: Arg => Try[A]): Arg => Try[A] = arg => fa(arg).orElse(fb(arg))
  }
}

在 Parsec 实现中，经常要用到Applicative提供的运算符。它们可以极大的简化这些有条件约束的模式匹配和推导逻辑。

然后是 Monad 实现，很大程度上这个实现是一种“形式上的美感”，Scala 将Monad的功能已经糅合在语言和标准库中，我们可能并不会直观的体会到这个实现的作用：

package jaskell
import scala.util.{Try, Success, Failure}

trait Monad[F[_]] extends Applicative[F]:
  extension [A, B](x: F[A])
    def >>= (f: A=> F[B]): F[B] = {
      x.flatMap(f)
    } 

    /** The `map` operation can now be defined in terms of `flatMap` */
    def map(f: A => B): F[B] = x.flatMap(f.andThen(pure))

    def >> (f: A => B): F[B] = map(f)

given listMonad: Monad[List] with
  def pure[A](x: A): List[A] =
    List(x)
  extension [A, B](xs: List[A])
    def flatMap(f: A => List[B]): List[B] = 
      xs.flatMap(f) // rely on the existing `flatMap` method of `List`

given optionMonad: Monad[Option] with
  def pure[A](x: A): Option[A] = Option(x)

  extension [A, B](xo: Option[A])
    def flatMap(f: A => Option[B]): Option[B] = xo match
      case Some(x) => f(x)
      case None => None

given tryMonad: Monad[Try] with
  def pure[A](x: A) = Success(x)
  extension [A, B](xt: Try[A])
      def flatMap(f: A => Try[B]): Try[B] = xt.flatMap(f)

Given 语法可以为我们提供特定约束条件下的实现，例如我们可以通过 given ，为 Parsec 算子引入 Monad typeclasses 。

Parsec 实现

package jaskell.parsec
import scala.util.{Try, Success, Failure}
import scala.language.implicitConversions
import jaskell.Monad

trait Parsec[A, B] {
    def apply(state: State[A]): Try[B]

    def ?(state: State[A]): Try[B] = this.apply(state)

    def !(state: State[A]): B = this.apply(state).get

    def attempt: Parsec[A, B] = new Attempt(this)

    def iterate(state: State[A]): Iterator[A, B] = new Iterator(this, state)

    def <|> (p: Parsec[A, B]): Parsec[A, B] = new Combine2(this, p)
}

given parsecConfig[E]: Monad[[T] =>> Parsec[E, T]] with {
    def pure[A](x: A): Parsec[E, A] = new Pack[E, A](x)

    extension [A, B](x: Parsec[E, A]) {
        def flatMap(f: A => Parsec[E, B]): Parsec[E, B] = new Binder(x, f)
    }

}

given textParserConfig[T]: Monad[[T] =>> Parsec[Char, T]] with {
  def pure[A](x: A): Parsec[Char, A] = new Pack[Char, A](x)

  extension [A, B](x: Parsec[Char, A]) {
    def flatMap(f: A => Parsec[Char, B]): Parsec[Char, B] = new Binder(x, f)
  }

  extension [A](x: Parsec[Char, A]) {
      def apply(content: String): Try[A] = x.apply(content.state)
      def ?(content: String): Try[A] = x ? content.state
  }
}

而 extension 可以在不修改原有类型的前提下，提供额外的行为和功能。在这里，我们可以将 Parsec 实现为一个特定的Monad，为其提供特有的 flatMap 实现，这样，我们就可以像在 Haskell 中一样，方便的利用 `<*`，`*>`，`>>=`运算符组合算子。

需要注意的是，Haskell中的实现方式于此不同，Haskell Parsec 库利用 Haskell 语言的 Curry 能力，自动拥有了强大的组合能力，如果要在 Scala 3中模拟，应该将 state 实现为一个 using 参数。要不要这么做，我还在思考和学习。

一旦有了正确的基础类型，组合子的使用就更加便利，例如 between 匹配，现在可以实现为：

package sisp.parsers

import jaskell.parsec.Atom.pack
import jaskell.parsec.Combinator.{between, sepBy1}
import jaskell.parsec.Txt.{ch, skipWhiteSpaces}
import jaskell.parsec.{Parsec, SkipWhitespaces, State}
import sisp.ast.{Element, Expression}

import scala.util.Try

class ExprParser extends Parsec[Char, Any]{
  import jaskell.parsec.parsecConfig
  val skip: SkipWhitespaces = skipWhiteSpaces
  val elementParser = new Parser
  val left = ch('(') *> skip
  val right = skip *> ch(')')
  
  lazy val parser =
    left *> sepBy1(elementParser, skip) <* right  >>=
      {vals => pack(new Expression(vals))}

  override def apply(s: State[Char]): Try[Element] = parser ? s
}

上例是 SISP Dotty 项目的 S 表达式算子，它将括号包围的代码（即LISP程序员熟知的 S 表达式形式）解释为一个表达式对象。这里我们充分利用了 Applicative 和 Bind 带来的便利。

我曾经想在 Scala 2 中实现类似的 Monad 定义，但是 Scala 2 的typeclass 仅支持一个类型参数，并且需要一组眼花缭乱的复杂技巧来实现，于是我很快放弃了。在 Scala 3 实现中，我同样遇到了类型参数的问题，Monad/Applicative/Fucntor定义强调的是对某一个目标类型的封装，而 Parsec 算子是一个一元函数，它需要有输入类型和输出类型两个类型参数。但是实际上我们仔细思考，会发现我们仅仅需要在输出类型上定义 Monad，输入类型在 Parsec 算子定义时已经确定，我们需要的是将输入和输出类型分离为两步单类型参数的定义。这时就需要利用 Scala 3 的 type lambda ：

given parsecConfig[E]: Monad[[T] =>> Parsec[E, T]] with {
    def pure[A](x: A): Parsec[E, A] = new Pack[E, A](x)

    extension [A, B](x: Parsec[E, A]) {
        def flatMap(f: A => Parsec[E, B]): Parsec[E, B] = new Binder(x, f)
    }

}

通过一个带类型参数的 given 实例， 我们将 Parsec 约束为一个单类型参数的 Monad 。这里我们仅需定义 flatMap 和 pure ，就可以令其自动拥有基础算子的各种功能。

Type Classes 的其它场景

当然，我们还可以利用这个功能做很多工作，例如在 JISP/SISP 实现中，我们需要将 `Seq[Try[T]]` 翻转为对应的 `Try[Seq[T]]` 。现在，我们可以直接给 Seq 类型一个 given 实例：

trait SeqU {}

given seqU: SeqU with {
  extension[T] (seq: Seq[Try[T]])
    def sequenceU: Try[Seq[T]] = {
      val failure = seq.filter(_.isFailure)
      if(failure.isEmpty){
        return Success(seq.map(_.get))
      } else {
        return Failure(failure.head.failed.get)
      }
    }
}

在用到这个功能的地方，引入该实例，就可以将 sequenceU 作为对象方法使用：

package sisp.ast

import scala.util.Try

class ListExpr extends Lambda {
  import jaskell.seqU
  override def apply(env: Env, params: Seq[Any]): Try[Any] = {
    (params map env.eval).sequenceU map {values => new Quote(new Expression(values))}
  }
}

其实 sequenceU 这个名字，来自 cats 库中的同名方法。我写下这篇文章的时候，也感觉这个名字太长了点。所以在最新版的 jaskell dotty 中，这个方法改叫 flip 了。

Haskell 的 flip 有不同的含义，它用来交换二元函数的顺序。这个能力对于广泛使用中缀表达式和 Curry 的 Haskell 很有用，Scala 就不同，它更平凡，老老实实的用 lambda 就好了。

Try 是 Scala 标准库的内置类型，它如此重要，所以我在尝试更为通用的 flip 实现，未来的版本，可能会允许任意的 `Monad[Try[T]]` 直接翻转为 `Try[Monad[T]]` 。