EDYCJA: Powyższy komentarz podał brakujący element. Niektórzy ludzie celowo bawią się w mniej niż kompletne języki. Wyraźnie nie dbam o takie języki. Naprawdę łatwy do opanowania język nie jest szalony i trudny do zaprojektowania. Cała reszta omawia to, co się dzieje, próbując zastosować te twierdzenia do pełnego języka.
Fałszywy!
function f(a): forall t: Type, t->t
function g(a): forall t: Type, t->t
return (a is g) ? f : a
return a is f ? g : a
gdzie isoperator porównuje dwie zmienne dla tożsamości referencyjnej. Oznacza to, że zawierają tę samą wartość. Nie jest to wartość równoważna, ta sama wartość. Funkcje fi gsą z definicji równoważne, ale nie są takie same.
Jeśli ta funkcja zostanie przekazana sama, zwraca coś innego; w przeciwnym razie zwraca dane wejściowe. Coś innego ma ten sam typ, co sam, dlatego można je zastąpić. Innymi słowy, ftożsamość nie jest, ponieważ f(f)zwraca g, podczas gdy tożsamość powraca f.
Aby twierdzenie się utrzymało, musi ono przyjąć absurdalną zdolność redukcji
function cantor(n, <z, a>) : forall t: t: Type int, <int, t> -> <int, t>
return n > 1 ? cantor((n % 2 > 0) ? (n + 1) : n / 2, <z + 1, a>) : <z, a>
return cantor(1000, <0, a>)[1]¹
Jeśli zechcesz założyć, że możesz założyć, że łatwiejsze jest wnioskowanie o typie.
Jeśli spróbujemy ograniczyć domenę, dopóki twierdzenie się nie utrzyma, ostatecznie musimy ją okropnie ograniczyć.
- Pure Functional (bez stanu zmiennego, bez IO). OK, mogę z tym żyć. Dużo czasu chcemy przeprowadzać testy funkcji.
- Opróżnij standardową bibliotekę. meh
- Nie
raise i nie exit. Teraz zaczynamy się ograniczać.
- Nie ma typu dna.
- Język ma regułę, która pozwala kompilatorowi zwinąć nieskończoną rekurencję, zakładając, że musi się zakończyć. Kompilator może odrzucać trywialną nieskończoną rekurencję.
- Kompilator może zawieść, jeśli zostanie zaprezentowany z czymś, czego nie można udowodnić w żaden sposób. ² Teraz biblioteka standardowa nie może przyjmować funkcji jako argumentu. Gwizd.
- Nie ma
nil. To zaczyna być problematyczne. Skończyły się nam sposoby radzenia sobie z 1 / 0.³
- Język nie może dokonywać wnioskowania typu rozgałęzienia i nie ma przesłonięcia, gdy programiści mogą udowodnić wnioskowanie typu, którego nie może język. To jest całkiem złe.
Istnienie obu ostatnich dwóch ograniczeń okaleczyło język. Mimo że Turing jest kompletnym jedynym sposobem na uzyskanie z niego ogólnego celu, jest symulacja wewnętrznej platformy, która interpretuje język o luźniejszych wymaganiach.
¹ Jeśli uważasz, że kompilator może to wywnioskować, wypróbuj ten
function fermat(z) : int -> int
function pow(x, p)
return p = 0 ? 1 : x * pow(x, p - 1)
function f2(x, y, z) : int, int, int -> <int, int>
left = pow(x, 5) + pow(y, 5)
right = pow(z, 5)
return left = right
? <x, y>
: pow(x, 5) < right
? f2(x + 1, y, z)
: pow(y, 5) < right
? f2(2, y + 1, z)
: f2(2, 2, z + 1)
return f2(2, 2, z)
function cantor(n, <z, a>) : forall t: t: Type int, <int, t> -> <int, t>
return n > 1 ? cantor((n % 2 > 0) ? (n + 1) : n / 2, <z + 1, a>) : <z, a>
return cantor(fermat(3)[0], <0, a>)[1]
² Dowód, że kompilator nie może tego zrobić, zależy od oślepienia. Możemy użyć wielu bibliotek, aby kompilator nie widział pętli jednocześnie. Ponadto zawsze możemy zbudować coś, co program działałby, ale nie można go skompilować, ponieważ kompilator nie może wykonać indukcji dostępnej pamięci.
³ Ktoś myśli, że możesz mieć ten zerowy zero bez arbitralnych typów ogólnych zwracających zero. To płaci okropną karę, za którą nie widziałem skutecznego języka, który mógłby ją zapłacić.
function f(a, b, c): t: Type: t[],int,int->t
return a[b/c]
nie można kompilować. Podstawowym problemem jest to, że indeksowanie tablicy wykonawczej już nie działa.