scala组合子演算数据模型的类型推断

Question

我正在尝试在scala中使用非常轻量级的组合子演算编码.最初,我只是实现S和K组合器,应用程序和常量值.后来我希望提升scala函数并允许将表达式作为scala函数进行求值.但是,这是为了以后.这是我到目前为止所拥有的.

/** Combinator expression */
sealed abstract class CE

/** Application: CE| (x y) <=> LC| (x:(A=>B) y:A) : B */
case class Ap[A <: CE, B <: CE, X](e1: A, e2: B) extends CE

/** A raw value with type */
case class Value[T](v: T) extends CE

/** Some combinator */
sealed abstract class Comb extends CE

/** The S combinator: CE| S x y z
 *                    LC| ?x:(A=>B=>C).?y:(A=>B).?z:A.(x z (y z)) : C
 *  S : ?A.?B.?C. (A => B => C) => (A => B) => A => C
 */
case object S extends Comb
/** The K combinator: CE| K x y
 *                    LC| ?x:A.?y:B.x:A : A
 *  K : ?A => ?B => A
 */
case object K extends Comb

现在我想对此进行一些类型的推断.为了简化实现小步和大步减少,数据模型是无类型的,所以我希望类型在这个结构的外部.让我们介绍一下保存类型信息的东西.

trait TypeOf { type typeOf }

值类型很简单.

implicit def typeOfValue[T](vt: Value[T]) : TypeOf =
    new TypeOf { type typeOf = T }

应用程序有点棘手,但基本上归结为功能应用程序.让我们为组合器应用程序引入一个类型,,以避免与正常的scala应用程序混淆.

/** Combinator application */
class ?[+S, -T]

implicit def typeOfAp[Ap[A, B], A <: CE, B <: CE], X, Y](Ap(A, B)
  (implicit aIsFXY: A#typeOf =:= (X?Y), bIsX: B#typeOf =:= X) : TypeOf =
      { type typeOf = Y }

这是我被卡住的地方.我需要表示S和K组合器的类型.但是,它们是普遍量化的类型.在开始应用它们之前,您不知道它们的实际类型.我们以K为例.

(K x:X y:Y) : X
(K x:X) : ?Y.Y => X
(K) : ?X.x => ?Y.Y => X

我尝试使用它的前几次,我将K参数化为K [X,Y],但这是(灾难性的)不充分多态.K的类型应该等待第一个参数的类型,然后是下一个参数的类型.如果将K应用于一个值,则不应修复下一个参数的类型.您应该能够(K x:X)并将其应用于字符串,或者int或您喜欢的任何类型.

所以我的问题是如何编写为S和K生成typeOf的隐式,以及如何正确处理quantif量化类型.也许我想要这样的东西？

implicit def typeOfK(k: K.type): TypeOf = { type typeOf = ?[X, X ? (?[Y, Y?X])] }

但是,我不确定我应该如何编写∀类型来进行管道工作.我有一种感觉,除了得到正确之外,还有第二个隐含的typeOfAp来处理A#typeOf =:=∀[...]的情况除了退出A#typeOf =:=⊃[ ......]一个.

谢谢,

马修

Answer 1

这有帮助吗？

\n\n

trait \xce\xbb {\n    type ap[X] <: \xce\xbb\n}\n\ntype K = \xce\xbb {\n    type ap[X<:\xce\xbb] = \xce\xbb {\n        type ap[Y<:\xce\xbb] = X\n    }\n}\n\ntype S = \xce\xbb {\n    type ap[X<:\xce\xbb] = \xce\xbb {\n        type ap[Y<:\xce\xbb] = \xce\xbb {\n            type ap[Z<:\xce\xbb] = X#ap[Z]#ap[Y#ap[Z]]\n        }\n    }\n}\n\ntype I = S#ap[K]#ap[K]\n\ndef ap[X<:\xce\xbb,Y<:\xce\xbb](x:X,y:Y): X#ap[Y]\n

\n