Type Inferenz für ein Scala -Kombinator -Calculus -Datenmodell

Question

Ich probiere eine sehr leichte Codierung von Kombinatorrechnung in Scala aus. Zunächst implementiere ich einfach die S- und K -Kombinators, Anwendungs- und Konstantwerte. Später hoffe ich, Scala -Funktionen in der Bewertung eines Ausdrucks als Scala -Funktion zu ermöglichen. Das ist jedoch für später. Hier ist, was ich bisher habe.

/** 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

Jetzt möchte ich darüber nachgelassen werden. Um die Einfachheit bei der Implementierung der Reduzierung kleiner und großer Stufe zu implementieren, ist das Datenmodell nicht angegeben. Daher möchte ich, dass die Typen dieser Struktur extern sind. Lassen Sie uns etwas vorstellen, um die Typinformationen zu erhalten.

trait TypeOf { type typeOf }

Der Werttyp ist einfach.

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

Die Anwendung ist etwas schwieriger, läuft aber im Grunde auf die Funktionsanwendung hinaus. Führen Sie einen Typ ⊃ für die Kombinatoranwendung ein, um Verwirrung mit normaler Skala -Anwendung zu vermeiden.

/** 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 }

Hier bin ich stecken. Ich muss den Typ der S- und K -Kombinators darstellen. Es sind jedoch universell quantifizierte Typen. Sie kennen ihren tatsächlichen Typ erst, wenn Sie anfangen, sie anzuwenden. Nehmen wir K als Beispiel.

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

In den ersten paar Malen habe ich versucht, damit zu arbeiten. Die Art von K sollte auf die Art des ersten Arguments warten, und dann auf das nächste. Wenn Sie K auf nur einen Wert anwenden, sollte der Typ des nächsten Arguments noch nicht behoben werden. Sie sollten in der Lage sein, (k x: x) aufzunehmen und auf eine Zeichenfolge oder auf einen int oder einen egalwaren Typ anzuwenden, den Sie mögen.

Mein Problem ist also, wie ich das implizite Schreiben des Typs von S und K und wie man die ∀-quantifizierten Typen korrekt erzeugt. Vielleicht möchte ich so etwas?

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

Ich bin mir jedoch nicht sicher, wie ich den Typ schreiben sollte, um die Sanitäranlagen zu erledigen. Ich habe das Gefühl, dass es zusätzlich zu dem Fall A#TypeOF =: = ∀ [...] zusätzlich zum Ausgang a#typeof =: = ⊃ [ ...] eines.

Vielen Dank,

Matthew

Answer 1

Hilft das?

trait λ {
    type ap[X] <: λ
}

type K = λ {
    type ap[X<:λ] = λ {
        type ap[Y<:λ] = X
    }
}

type S = λ {
    type ap[X<:λ] = λ {
        type ap[Y<:λ] = λ {
            type ap[Z<:λ] = X#ap[Z]#ap[Y#ap[Z]]
        }
    }
}

type I = S#ap[K]#ap[K]

def ap[X<:λ,Y<:λ](x:X,y:Y): X#ap[Y]