typescript - Tip sabit noktası hesaplama

Diyelim ki bazı tür-fonksiyonlarımız var F<T>, ve sabit noktasını hesaplamak istiyoruz type X=F<X>. Bu, nesne olan türlerde işe yarayabilir

interface Tree1<T> { left: T; right: T }
interface Tree extends Tree1<Tree> {}
declare const t: Tree;
const r = t.left.right; // OK

daha genel tip-fonksiyonlar için yapmaz:

type Tree1<T> = null | { left: T; right: T }
interface Tree extends Tree1<Tree> {} // can't extend not-object

interface tarafından verilen ertelenmiş bir tür düzeyinde hesaplama olmadan, sonsuz örneklemeyi önlemek zor. Yapabileceğim en iyi şey sadece bunu geciktirmek:

interface Tree1<T> { left: T; right: T }
type Temp1<T> = { a: null | [T[keyof T], T[keyof T]] }
interface Temp2 extends Temp1<Temp2> {}
declare const t: Temp2;
const r = t.a; // Type instantiation is excessively deep

Ayrıca, ağaca gereksiz düğümler ekleyerek bunu düzeltmek mümkündür, ama ben bunun peşinde değilim.

type Tree1<T> = null | { left: T; right: T }
type Tree = Tree1<{ref: Tree}> // OK

Hiçbiri doğrudan Tree'i tanımlamıyor.

type Tree = null | { left: Tree, right: Tree }

O zor bulunan sabit nokta nasıl hesaplanır?

type Tree1<T> = null | { left: T; right: T }
type Tree = ???
const t: Tree = {left: null, right: {left: null, right: null}};

Cevap #1

Bir tür fonksiyonunun literal sabit noktasını oluşturmanın bir yolunu bilmiyorum, ama bir özelliği aracılığıyla dolaylı olarak kendine başvuran bir tür oluşturabilirsiniz. Ne için kullandığınıza bağlı olarak, bu yeterince iyi olabilir.

Sorunuza, soyut sözdizimi ağaçlarını nasıl türleyebileceğimi düşündüğüm için geldim. Özellikle, ilgili bir dil ailesi için AST'leri türlemek istiyorum. Örneğin, "a + b + c" gibi değişkenleri toplamanın yer aldığı ifadeler için bir türümüz olabilir ve "a*b + c" gibi değişkenler, toplama ve çarpma içeren ifadeler için başka bir türümüz olabilir.

Bunların gerçekten statik tipler olmasını istiyorum — hepsini yönetmek için sadece tek bir büyük AST tipi kullanmak istemiyorum. Ama aynı zamanda tiplerin genişletilebilir olmasını da istiyorum. Yeni bir AST düğümü türü eklediğimde tüm grameri yeniden tanımlamak zorunda kalmak istemiyorum.

Yani şöyle düşünüyordum, eğer dil varyantına karşılık gelen bir genel parametreniz olsaydı, AST düğümlerini şöyle tanımlayabilirdiniz:

type Plus<α extends Grammer> = { 
    kind: "plus"
    left: Expr<α>
    right: Expr<α>
}

Sonra gramerin genel bir sürümünü şöyle tanımlayabilirsiniz:

type AbelianGroupBaseGrammer<α extends Grammer> = Variable<α> | Plus<α>

Ve bunu bir sabit nokta oluşturarak tek tip bir yapıya dönüştürmek

AbelianGroupGrammer = AbelianGroupBaseGrammer<AbelianGroupGrammer>

Bunu daha büyük dillere şöyle genişletebilirsiniz

type RingBaseGrammar<α extends Grammer> = AbelianGroupBaseGrammer<α> | Times<α>

Bu TypeScript'te çalışmaz, Type alias 'AbelianGroupGrammer' circularly references itself hatasını alırsınız

Ama eğer öz-yönlendirmeyi bir nesne özelliğinin içine gizlersen, aynı etkiyi elde edebilirsin. Bu sürüm tipi hatasız kontrol eder:

type Grammer = {
    "expression": unknown
}

type Expr<α extends Grammer> = α["expression"]

type Plus<α extends Grammer> = { 
    kind: "plus"
    left: Expr<α>
    right: Expr<α>
}

type Times<α extends Grammer> = { 
    kind: "times"
    left: Expr<α>
    right: Expr<α>
}

type Variable<α> = { 
    kind: "variable"
    name: string
}

type AbelianGroupBaseGrammer<α extends Grammer> = { 
    "expression": Variable<α> | Plus<α>
}

type AbelianGroupGrammer = { 
    "expression": Expr<AbelianGroupBaseGrammer<AbelianGroupGrammer>>
}

type RingBaseGrammer<α extends Grammer> = { 
    "expression": Expr<AbelianGroupBaseGrammer<α>> | Times<α>
}

type RingGrammer = {
    "expression": Expr<RingBaseGrammer<RingGrammer>>
}

const x : Expr<AbelianGroupGrammer> = {kind: "variable", name: "x"}
const y : Expr<AbelianGroupGrammer> = {kind: "variable", name: "y"}
const x_plus_y : Expr<AbelianGroupGrammer> = {kind:"plus", left: x, right: y}
const x_times_x_plus_y : Expr<RingGrammer> = {kind:"times", left: x, right: x_plus_y}

function group2ring(a : Expr<AbelianGroupGrammer>) : Expr<RingGrammer> { 
    return a
}