← Volver a los ejercicios
Ejemplos de inferencia
Veinte programas, y para cada uno la pregunta es qué tipo infiere el interpretador. Primero los que quedan cerrados, donde las primitivas alcanzan a llenar todos los huecos; después los que dejan variables libres, los letrec y los dos que no tipan. Los tipos, los valores y los mensajes de error se midieron con type-of-program y eval-program.
El lenguaje es INFERRED (EOPL §7.3). Las primitivas son
+(e,e), -(e,e), *(e,e),
add1(e), sub1(e), <(e,e),
>(e,e) y zero?(e), y van antes del paréntesis
y con comas; la aplicación lleva paréntesis y va sin comas,
(f 3). El ambiente inicial está vacío. Una variable libre en
el tipo del resultado se escribe aquí t1: el interpretador la
imprime como tvar5 o tvar58, con el número que le
tocó en esa corrida.
Resueltos
| Programa | Tipo |
proc (? x) sub1(x) | (int -> int) |
proc (? x) if x then 1 else 2 | (bool -> int) |
proc (? x) proc (? y) +(x, y) | (int -> (int -> int)) |
proc (? x, ? y) +(x, (y x)) | (int * (int -> int) -> int) |
letrec ? fact (? n) = … in (fact 5) | int |
proc (? f, ? x) (f +(1,x) zero?(x)) | ((int * bool -> t1) * int -> t1) |
proc (? x) (x x) | falla: la variable aparece dentro de su propio tipo |
proc (? f, ? x) (f (x 1) zero?(x)) | falla: x sería procedimiento e int |
Dos fuentes llenan los huecos: las primitivas, que traen tipos escritos de antemano, y la aplicación, que iguala el parámetro del operador con el argumento. Lo que ninguna de las dos restringe se queda como variable, y el programa tipa igual.
Un ejercicio más
Escriba cuatro programas: uno que tipe a bool sin usar true ni false, uno cuyo tipo sea ((bool -> int) * bool -> int), uno cuyo tipo lleve una variable libre que aparezca tres veces y uno que el interpretador rechace por el chequeo de ocurrencia. Mida los cuatro, copie lo que imprime cada uno, y para los dos últimos escriba de qué aplicación sale la ecuación que los explica.