Тип вывод для модели данных Calca Comminator Calculus
-
13-10-2019 - |
Вопрос
Я пробую очень легкое кодирование расчета комбинатора в 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, и как правильно обрабатывать типы ∀-Quallified. Возможно, я хочу что -то подобное?
implicit def typeOfK(k: K.type): TypeOf = { type typeOf = ∀[X, X ⊃ (∀[Y, Y⊃X])] }
Тем не менее, я не уверен, как я должен писать тип ∀, чтобы сделать сантехника. У меня есть ощущение, что в дополнение к тому, чтобы получить ∀ правильно, у TypeOfAP будет второй подразумеватель, чтобы обрабатывать случай A#typeof =: = ∀ [...] в дополнение к выходу#typeof =: = ⊃ [ ...] один.
Спасибо,
Мэтью
Решение
Это помогает?
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]