Jakie są typy rozmiarów w Agdzie?

Question

Jakie są typy rozmiarów w Agdzie? Próbowałem czytać gazetę o MiniAgda, ale nie udało się przejść ze względu na następujące punkty:

1. Dlaczego są typy danych generic nad ich wielkości? O ile mi wiadomo, rozmiar jest głębokością drzewa indukcji.
2. Dlaczego typy danych kowariancyjnych przekraczają ich rozmiar, tj. I < = j -> T_i < = T_j?
3. Co oznaczają wzory > i ?

Answer 1

1. Chodzi o to, że typ wielkości jest tylko rodzina typów zaindeksowane przez rozmiarach, które są zasadniczo porządkowe. Podczas definiowania typu indukcyjnego jako sized data, kompilator sprawdza, czy wynikiem jest typ o poprawnym rozmiarze, tak że na przykład succ w SNat zwiększa rozmiar w 1. W ten sposób dla typu o rozmiarach S(i : Size) -> S i jest zasadniczo elementem z S o rozmiarze i. Co wydaje mi się dziwne, dlatego definicja zero dla SNat jest zero : (i : Size) -> SNat ($ i) zamiast czegoś podobnego do zero : (i : Size) -> SNat ($ 0).
2. Dla których wielkość indukcyjnych typów to ma sens, jak t_I jest typem elementów T o rozmiarze mniejszym niżi, tak, że jeśli i ≤ j ≤ T_j następnie t_I; konstruktorzy muszą zwiększać rozmiar w wywołaniach rekursywnych.

3. Jak wyjaśniono w sekcji 2.3, # jest odpowiednikiem T_∞, rodzaju elementów T bez znanego rozmiaru związanego; jest to najlepszy element dla T_i w preorderie podtypu. Wzorzec (i> j) jest używany do wiązania rozmiaru j przy zachowaniu informacji, które j <. Przykładem na papierze do minus czyni to jasne:

   fun minus : [i : Size] -> SNat i -> SNat # -> SNat i 
   { minus i (zero (i > j)) y = zero j 
   ; minus i x (zero .#) = x 
   ; minus i (succ (i > j) x) (succ .# y) = minus j x y 
   } 
   

   Pierwszy podpis oznacza, że ​​odjęcie dowolną liczbę (SNat # jest numer bez size związany informacji) z szeregu wielkości co najwyżej I (to co SNat i środki) zwraca co najwyżej liczbę i; i dla wzorca >, w ostatnim wierszu używamy go do dopasowania co najwyżej j wielkości, a typ rekursywnego sprawdzania z powodu podtytułu: SNat j ≤ SNat i.