Saltar a contenido

Clase 9. Inferencia de tipos

Martes 17 de noviembre de 2026.

El chequeador de la sesión anterior funciona porque el programador escribe las anotaciones: proc declara el tipo de cada parámetro y letrec declara además el del resultado. Esta sesión quita esa obligación. Donde iba el tipo se escribe ?, y el chequeador tiene que deducirlo a partir de cómo se usa la variable en el resto del programa.

El procedimiento son tres pasos. Ponerle una variable de tipo a cada hueco, generar una ecuación por cada construcción del lenguaje y resolver el sistema. Lo que resuelve el sistema se llama unificación, y es lo que decide si el programa tipa.

El hueco que deja la pregunta

La gramática gana una categoría, el tipo opcional, con dos formas:

<optional-type-exp> ::= ?                no-type-exp
                      | <type-exp>       a-type-exp

proc y letrec la usan en lugar del tipo, y las dos formas se mezclan en el mismo programa:

proc (? f, ? x) (f +(x,1) >(x,0))
proc (int x, ? y) if (y x) then +(x,1) else +(x,3)

El puente entre lo que escribió el programador y el tipo que manipula el chequeador es una sola función:

(define expand-optional-type-expression
  (lambda (otexp tenv)
    (cases optional-type-exp otexp
      (no-type-exp () (fresh-tvar))
      (a-type-exp (texp) (expand-type-expression texp)))))

Donde hay ? nace una variable de tipo; donde hay un tipo escrito se expande como antes.

La variable de tipo

El TAD type gana una tercera variante:

(define-datatype type type?
  (atomic-type (name symbol?))
  (proc-type (arg-types (list-of type?)) (result-type type?))
  (tvar-type (serial-number integer?) (container vector?)))

Una variable de tipo lleva un número que la identifica y un contenedor que empieza vacío y se llena una sola vez. El contenedor es un vector de tamaño uno, y el número sale de un contador que avanza con set!:

(define fresh-tvar
  (let ((serial-number 0))
    (lambda ()
      (set! serial-number (+ 1 serial-number))
      (tvar-type serial-number (vector '())))))

Ese contador es una de las pocas veces que el curso usa set! a propósito: sin él, dos variables distintas podrían salir con el mismo número y la cuenta se confundiría. El número que aparece impreso, tvar13 o tvar56, depende de cuántas variables se hayan creado antes en la sesión de DrRacket, de modo que el mismo programa evaluado en dos momentos imprime números distintos. Lo que importa es cuáles números coinciden dentro de un tipo, no el valor de cada uno.

La variable tiene dos estados. Vacía, cuando no se sabe nada de ella, y llena, cuando ya guarda un tipo. tvar-non-empty? dice en cuál está y tvar-set-contents! la llena. Llenarla es definitivo: un segundo intento con otro tipo no la sobrescribe, hace fallar el programa.

En un lenguaje de tipado dinámico el tipo viaja con el valor y se reemplaza sin que nadie reclame: en Python, a = 8 y después a = "hola" dejan a a con otro tipo. Aquí la variable de tipo no es el valor sino el hueco, y se llena una vez con lo que el programa obligue.

Las ecuaciones que genera cada forma

Expresión Qué exige Qué entrega
if p then c else a p es bool, y c y a son del mismo tipo el tipo de las ramas
proc (? x1, …, ? xn) cuerpo nada por sí sola (t1 * … * tn -> tcuerpo)
(rator rand1 … randn) rator es un procedimiento de n argumentos y el tipo de cada rand coincide con el del parámetro el tipo de resultado de rator
let x = e in cuerpo nada el tipo del cuerpo, con x ligado al tipo de e
letrec ? p (? x) = cuerpo in e el cuerpo tiene el tipo del resultado el tipo de e

Las primitivas se tratan como procedimientos, igual que en el chequeador con anotaciones:

Primitiva Tipo
+, -, * (int * int -> int)
add1, sub1 (int -> int)
<, > (int * int -> bool)
zero? (int -> bool)

El letrec se tipa con lo que dice la declaración y no con lo que resulte del cuerpo: el nombre entra al ambiente de tipos con el tipo armado desde sus anotaciones, aunque sean huecos, y solo después se tipa el cuerpo. Es lo que permite que la llamada recursiva encuentre algo con qué unificar, porque tipar el cuerpo exige conocer el tipo del nombre que el cuerpo está definiendo.

Un ejemplo completo

let func = proc (? f, ? x) (f +(x,1) >(x,0))
in let res = (func proc (? a, ? b) a 10)
   in res

Cada hueco recibe su variable: tf y tx para los parámetros de func, ta y tb para los del procedimiento que se le pasa. De ahí salen las ecuaciones:

tfunc = tf * tx -> t1            por la regla del proc
tf    = int * bool -> t1         por la aplicación (f +(x,1) >(x,0))
tx    = int                      porque x entra a +(x,1) y a >(x,0)
ta * tb -> ta = tf               el primer argumento de func
tx    = int                      el segundo argumento, que es 10

La cuarta ecuación hace el trabajo. Unificar (ta * tb -> ta) con (int * bool -> t1) llena ta con int, tb con bool y, como el resultado de ese procedimiento es ta, llena t1 con int. El sistema queda resuelto:

> (type-to-external-form (type-of-program (scan&parse "… in func")))
((int * bool -> int) * int -> int)
> (type-to-external-form (type-of-program (scan&parse "… in res")))
int

El ejercicio del tablero: el programa de func y res, las ecuaciones tfunc = tf * tx -> t1 y tf = int * bool -> t1, los recuadros con tx = int, t3 = int y t4 = bool, el tipo de f resuelto en int * bool -> int, y la salida del interpretador

Un segundo ejemplo

let f = proc (? x, ? y, ? z) if (x y) then *(z, 2) else z
in let g = proc (? m) if m then true else false
       k = 5
   in let tp = (f g true k) in f

Aquí el primer parámetro de f se usa como procedimiento sin que nada diga de qué tipo es, y el que lo decide es g, que llega en la aplicación:

tf = tx * ty * tz -> t1          por la regla del proc
tx = ty -> t2                    porque (x y) aplica x a y
t2 = bool                        la prueba del if
tz = int, t1 = int               porque *(z,2) pide enteros y la otra rama es z
tg = tm -> t4                    el proc de g
tm = bool, t4 = bool             su cuerpo es un if entre true y false
tx = tg, ty = bool, tz = tk      la aplicación (f g true k)

De la última fila sale todo: tx queda en (bool -> bool), ty en bool y tz en int, que es lo que ya decía k = 5.

> … in f    → ((bool -> bool) * bool * int -> int)
> … in g    → (bool -> bool)

El ejercicio del tablero: el programa con f de tres parámetros, g y k, la cadena de ecuaciones en rojo, los recuadros con t2 = bool, tm = bool, tk = int y tg = bool -> bool, y el resultado tf = (bool -> bool) * bool * int -> int

La unificación

check-equal-type! recibe dos tipos y los vuelve iguales, llenando variables si hace falta, o falla. Antes de decidir qué caso aplica, prune-type sigue las cadenas de variables ya llenas hasta llegar al tipo que de verdad hay detrás.

Los dos tipos Qué pasa
el mismo valor éxito, sin escribir nada
una variable llena se unifica contra su contenido
una variable vacía se llena con el otro tipo
dos atómicos los nombres tienen que coincidir
dos procedimientos misma cantidad de argumentos, y se unifican uno a uno y los resultados
cualquier otra combinación error de tipos

Seis casos concretos:

Se unifica Resultado
int con int éxito, nada que escribir
t1 con int éxito, t1 queda en int
bool con t1 éxito, t1 queda en bool
int con t1, con t1 ya en bool falla, int contra bool
(t1 * int -> bool) con (int * int -> bool) éxito, t1 queda en int
(t1 -> bool) con (int * int -> bool) falla, uno recibe uno y el otro dos

Los tres errores

check-equal-type!: Type mismatch: int doesn't match bool
check-equal-type!: Different numbers of arguments (int * int -> int) and (int -> tvar7)
check-equal-type!: Can't unify: tvar8 occurs in type (tvar8 -> tvar9)

Cada uno tiene un programa de tres líneas que lo produce:

let f = proc (? x) zero?(x) in (f true)
let f = proc (? x, ? y) +(x,y) in (f 1)
proc (? x) (x x)

El tercero es el chequeo de ocurrencia. Antes de llenar una variable, check-no-occurrence! recorre el tipo con que se la quiere llenar buscando esa misma variable adentro. En proc (? x) (x x), aplicar x a sí mismo pide que tx sea (tx -> t), y para saber qué es tx habría que saber primero qué es tx. Sin ese chequeo la variable quedaría apuntándose a sí misma y leerla después daría vueltas sin terminar.

El tipo se fija al usarlo

La misma identidad recibe tres tipos distintos según con qué se use:

let f = proc (? x) x in let p = (f 1) in f                      → (int -> int)
let f = proc (? x) x in let p = (f true) in f                   → (bool -> bool)
let f = proc (? x) x in let p = (f proc (? x) +(x,1)) in f      → ((int -> int) -> (int -> int))

Y no admite dos usos distintos en el mismo programa:

let f = proc (? x) x in let p = (f 1) in let q = (f true) in f
check-equal-type!: Type mismatch: int doesn't match bool

El primer uso llena la variable y el segundo se estrella contra lo que quedó. Un sistema que aceptara los dos a la vez sería polimórfico; este no lo es.

Cuando ningún uso obliga, la variable sobrevive en la respuesta:

> (type-to-external-form (type-of-program (scan&parse "proc (? f, ? x) (f +(1,x) zero?(x))")))
((int * bool -> tvar13) * int -> tvar13)

La salida de f no quedó determinada, y el mismo número en los dos lugares dice que son la misma. Basta aplicarlo una vez para que se llene:

> … "let k = proc (? f, ? x) (f +(1,x) zero?(x)) in let s = (k proc (int x, bool y) x 10) in k"
((int * bool -> int) * int -> int)

Un examen que no tipa

let f = proc (? x, ? y) if zero?(y) then proc (? k, ? l) >(k,l) else x
    g = proc (? z, ? a, ? b) if (a b 9) then a else b
in let h = proc (? c, ? d) (d d c c)
   in (h f g)

f por separado tipa, y queda en ((int * int -> bool) * int -> (int * int -> bool)): las dos ramas del if obligan a que x sea del mismo tipo que proc (? k, ? l) >(k,l).

g no:

check-equal-type!: Can't unify: tvar9 occurs in type (tvar9 * int -> bool)

(a b 9) pide que a sea un procedimiento que recibe a b y un entero, o sea ta = (tb * int -> t). El if pide además que las dos ramas coincidan, ta = tb. Reemplazando, ta = (ta * int -> bool), y la variable aparece dentro de su propio tipo.

h falla por lo mismo en otro sitio: (d d c c) aplica d a tres argumentos y uno de ellos es d, de modo que td tendría que ser a la vez un procedimiento de tres argumentos y el primero de esos tres. En la primera ecuación td es un procedimiento y en la segunda es lo que reciba, y las dos no se pueden cumplir.

El ejercicio del tablero: el programa del examen, las ecuaciones de g y de h en azul, td = td * tc * tc, el desarrollo que deja td igual a un procedimiento de tres argumentos y a int al mismo tiempo, y la conclusión de que no es posible unificar

Queda abierto qué habría que cambiarle al programa para que tipe, sin tocar la cantidad de parámetros. La pista es que z no se usa en ningún lado.

Otro examen, con las respuestas

let a = proc (int x, ? y) if (y x) then +(x,1) else +(x,3)
    b = proc (? n, ? m, ? o, ? p) if (p m) then (n m o) else (n *(m,3) o)
    c = proc (int q) zero?(q)
    d = 3
in let t = proc (? f, ? g, ? z, ? w) (f g w z z)
   in let tp = (t b a c d) in tp

Conviene resolverlo con lápiz antes de mirar la tabla.

Nombre Tipo
a (int * (int -> bool) -> int)
c (int -> bool)
d int
b ((int * (int -> bool) -> int) * int * (int -> bool) * (int -> bool) -> int)
t (((int * (int -> bool) -> int) * int * (int -> bool) * (int -> bool) -> int) * (int * (int -> bool) -> int) * (int -> bool) * int -> int)
tp int

Lo mismo en Java

Java tiene var para variables locales desde la versión 10, y es el mismo mecanismo:

var n = 1 + 2;                        // n queda en int
var nombres = new ArrayList<String>();

Nadie escribió el tipo de n y el compilador lo sacó de la expresión. Por eso n.length() no compila, porque n es un int, y var x; tampoco: sin algo que lo inicialice no hay de dónde deducir. El contraste con int x; es que ahí el tipo está escrito y la declaración se sostiene sola, aunque el valor haya que asignarlo antes de usar la variable.

Ejercicios de la segunda mitad

Ejercicios · FLP · Inferencia de tipos: qué cambia cuando la anotación es ?, qué es una variable de tipo y cuándo dos partes del programa llevan la misma, cómo se genera el sistema de ecuaciones y cómo se resuelve unificando, con el chequeo de ocurrencia al final.

Los apuntes del tablero

Lo que sigue

Objetos. Objetos simples y objetos planos, métodos, mensajes, despacho dinámico y cómo se implementa todo eso en Racket. Con esa sesión cierra el contenido evaluable del curso.