Introducción
Las funciones básicas de Racket están implementadas en C
y se las llama primitivas, por ejemplo cons, car, +, *, y
un largo etcétera (son cómo 1500). En este artículo vamos a ver cómo agregar
una nueva primitiva.
En general, uno no anda por la vida agregando primitivas,
pero me parece un ejercicio interesante para entender cómo están implementadas
las otras primitivas de Racket. Además, la nueva primitiva es útil para el
sistema de tipos oculto y secreto del optimizador de Racket (que no tiene nada
que ver con el sistema de tipos de TypedRacket).
La nueva primitiva
La nueva primitiva va a ser
(strict-true? v)
Devuelve #t si v es #t y
en cualquier otro caso devuelve #f.
En general, no es bueno que el código de Racket verifique algo comparándolo con #t. Normalmente el código debe sólo ver que no es #f. Cómo es una primitiva de mal gusto, la voy a ocultar para que no sea accesible.
(A pesar que está oculta, en los test internos es posible
llamarla importándola desde #%kernel. De todas manera, para
poder hacer algunos ejemplos en el artículo, la voy a exportar renombrada como ugly-strict-true? que
expresa claramente mi opinión.)
La nueva primitiva se parece mucho a
(not v)
Devuelve #t si v es #f y
en cualquier otro caso devuelve #f.
Así que el plan es ver cómo está implementada not, y copiar la implementación.
Para más detalles, pueden ver el código completo en github.
Deshabilitar cstartup.inc
El primer paso para agregar una primitiva es hacer que
Racket ignore el archivo cstartup.inc que es en realidad un
archivo .zo de
bytecode codificado de una manera extraña. El contenido de los archivos .zo
depende de la posición de cada primitiva, así que al agregar o sacar una
primitiva se vuelven obsoletos. En el mismo paso cambiamos el número de versión
así, todos los archivos .zo se recalculan. (Con el archivo cstartup.inc
deshabilitado todo anda más lento, así que hay que recordar habilitarlo al
completar las operaciones.)
Para deshabilitar cstarup.inc esto hay que editar el archivo schminc.h y poner
#define USE_COMPILED_STARTUP 0
El número de versión lo cambiamos en schminc.h y base/info.rkt
Agregando la primitivas
Por un lado hay que escribir la implementación en C, que
en este caso va en el archivo bool.c. Nada sorprendente. Sólo
nos fijamos si el primer argumento es scheme_true que
es el nombre interno de la variable que tiene a #t.
static Scheme_Object
*strict_true_p_prim (int argc, Scheme_Object *argv[])
{
return (SAME_OBJ(argv[0], scheme_true) ? scheme_true : scheme_false);
}
{
return (SAME_OBJ(argv[0], scheme_true) ? scheme_true : scheme_false);
}
Por otro lado creamos la primitiva para poder usar desde Racket la función en C, y la agregamos al environment para que se la reconozca al compilar los nuevos programas en Racket.
p =
scheme_make_folding_prim(strict_true_p_prim, "strict-true?", 1, 1,
1);
SCHEME_PRIM_PROC_FLAGS(p) |= scheme_intern_prim_opt_flags(SCHEME_PRIM_IS_OMITABLE);
scheme_add_global_constant("strict-true?", p, env);
SCHEME_PRIM_PROC_FLAGS(p) |= scheme_intern_prim_opt_flags(SCHEME_PRIM_IS_OMITABLE);
scheme_add_global_constant("strict-true?", p, env);
En la definición se expresan muchos detalles sobre la primitiva. Por suerte es parecida a not y nos podemos copiar.
Algunos de los próximos ejemplos parecen ridículos, pero después de que el código original en Racket sufre varios pasos de expansión, macros e inlineo, a veces se ven cosas parecidas.
Acepta un solo argumento
Así que no necesitamos controlar la cantidad de
argumentos nosotros. Así que
(strict-true? 1 2)
produce un error al ejecutarse
(strict-true? 1 2)
produce un error al ejecutarse
Devuelve un sólo valor.
Esto habilita algunas optimizaciones, por ejemplo
(lambda (x) (car (cons (strict-true? x) x)))
==>
(lambda (x) (strict-true? x))
en vez de
==>
(lambda (x) (values (strict-true? x)))
en la que values se usa para verificar que el resultado tenga exactamente un valor.
(lambda (x) (car (cons (strict-true? x) x)))
==>
(lambda (x) (strict-true? x))
en vez de
==>
(lambda (x) (values (strict-true? x)))
en la que values se usa para verificar que el resultado tenga exactamente un valor.
Además marca a
(lambda (x)
(display x)
(strict-true? x))
como una función que devuelve un solo valor, lo que ayuda al interprete/JIT a evitar generar código para el caso de valores múltiples.
La marcamos como folding,
Así que durante la optimización puede participar en el constant
folding, en expresiones como (strict-true? #t) ==> #t.
O cosas más complicadas que interactúan con otras optimizaciones, como por ejemplo
(lamba (v)
(when (vector? v)
(strict-true? (box? v))))
==>
(lamba (v)
(when (vector? v)
(strict-true? #f)))
==>
(lamba (v)
(when (vector? v)
#f)
La marcamos como OMITABLE
Así que automáticamente se le aplican algunas reducciones
como en
(lamba (x)
(strict-true? x)
(display x))
==>
(lamba (x)
(display x))
(lamba (x)
(strict-true? x)
(display x))
==>
(lamba (x)
(display x))
Pero no la marcamos como UNARY_INLINED
El lector atento habrá notado que no la marqué como UNARY_INLINED,
que es otro flag que tiene not. Lo arreglaremos pronto.
Rehabilitar cstartup.inc
Ahora podemos recalcular el archivo cstartup.inc
usando
make cstartup
y volver a habilitarlo poniendo en el archivo schminc.h
#define USE_COMPILED_STARTUP 1
Mientras estoy preparando el nuevo código me gusta tener estos pasos en diferentes commits en caso de que haya que hacer un rebase y recalcular cstartup.c, pero en la versión definitiva es más prolijo squasharlos en uno solo.
JIT
Si la primitiva es simple, es posible agregarla a la
lista de las primitivas que procesa el JIT, de manera que el código que se
ejecuta esté compilado en código máquina en vez de interpretado desde el
bytecode. Para eso Racket usa GNU lightning junto con varias convenciones y funciones
auxiliares para facilitar la escritura del código.
Primero hay que agregar un flag en la definición de strict-true? en bool.c
p =
scheme_make_folding_prim(strict_true_p_prim, "strict-true?", 1, 1,
1);
SCHEME_PRIM_PROC_FLAGS(p) |= scheme_intern_prim_opt_flags(SCHEME_PRIM_IS_UNARY_INLINED
| SCHEME_PRIM_IS_OMITABLE);
scheme_add_global_constant("strict-true?", p, env);
SCHEME_PRIM_PROC_FLAGS(p) |= scheme_intern_prim_opt_flags(SCHEME_PRIM_IS_UNARY_INLINED
| SCHEME_PRIM_IS_OMITABLE);
scheme_add_global_constant("strict-true?", p, env);
Y después la agregamos en jitinline.c
else if
(IS_NAMED_PRIM(rator, "strict-true?")) {
generate_inlined_constant_test(jitter, app, scheme_true, NULL, for_branch, branch_short, dest);
return 1;
}
generate_inlined_constant_test(jitter, app, scheme_true, NULL, for_branch, branch_short, dest);
return 1;
}
Este caso fue fácil porque está justo la función generate_inlined_constant_test que genera el código JIT para ver si el valor es igual a la constante elegida, en este caso scheme_true. Pero en general escribir la implementación de una primitiva en el JIT es muy muy engorroso.
Para ver el efecto de este cambio, podemos comparar cuánto tarda el siguiente programa antes y después de habilitar el JIT para strict-true?. Lo comparamos con el código análogo que usa not y siempre tiene activo el JIT (Usamos una variable modificable(mutable) x, para que el optimizador no esté seguro de cuánto vale x y tenga que chequear su valor en cada ciclo, en vez de que una optimización astuta elimine el chequeo.)
#lang racket/base
(define x 'something-else)
(set! x x)
(time
(for/or ([i (in-range 1000000000)])
(not x)))
(time
(for/or ([i (in-range 1000000000)])
(ugly-strict-true? x)))
(define x 'something-else)
(set! x x)
(time
(for/or ([i (in-range 1000000000)])
(not x)))
(time
(for/or ([i (in-range 1000000000)])
(ugly-strict-true? x)))
cpu time
(ms)
|
Antes:
|
Después:
|
not
|
4109
|
4109
|
ugly-strict-true?
|
9031
|
4110
|
Estos tiempos incluyen también tiempos del bucle, si lo pudiéramos descontar la diferencia sería aún más notable. En general recomiendo repetir la medición varias veces para tener una versión informal de una estadística, pero en este caso tarda como 5-10 segundos y la mejora es x2 así que no hace falta repetirla para estar seguro.
Variable global
Con los cambios que ya hicimos tenemos nuestra primitiva
completamente lista. Ahora podemos aprovechar y agregar algunas optimizaciones
específicas para strict-true?. Algunas optimizaciones
pueden reconocer a strict-true? por nombre, pero para
otras es necesario poner a strict-true? en
una variable global para que se la pueda reconocer o usar desde otros archivos.
En schpriv.h agregamos
extern
Scheme_Object *scheme_strict_true_p_proc;
No hay una regla oficial para el nombre de las variables globales, pero si es una primitiva en general el nombre es scheme_<nombre>_proc, en dónde en el nombre los - pasan a _ y los ? a _p y cosas así, con alguna que otra excepción.
En la definición que aparece en bool.c hay que guardar la primitiva en la variable y registrar la variable para que la vea el garbage collector.
READ_ONLY
Scheme_Object *scheme_strict_true_p_proc;
REGISTER_SO(scheme_strict_true_p_proc);
p = scheme_make_folding_prim(strict_true_p_prim, "strict-true?", 1, 1, 1);
SCHEME_PRIM_PROC_FLAGS(p) |= scheme_intern_prim_opt_flags(SCHEME_PRIM_IS_UNARY_INLINED
| SCHEME_PRIM_IS_OMITABLE);
scheme_strict_true_p_proc = p;
scheme_add_global_constant("strict-true?", p, env);
REGISTER_SO(scheme_strict_true_p_proc);
p = scheme_make_folding_prim(strict_true_p_prim, "strict-true?", 1, 1, 1);
SCHEME_PRIM_PROC_FLAGS(p) |= scheme_intern_prim_opt_flags(SCHEME_PRIM_IS_UNARY_INLINED
| SCHEME_PRIM_IS_OMITABLE);
scheme_strict_true_p_proc = p;
scheme_add_global_constant("strict-true?", p, env);
Optimizaciones
Hay varias optimizaciones interesantes para agregar. Por
razones de espacio no voy a poner el código y queda como ejercicio para el
lector interesado buscar los detalles en los commits. Son todos agregados a
funciones en optimize.c y sus testeos respectivos.
Predicado relevante
Agregamos strict-true? a
la lista de predicados relevantes, que son los que recuerda el optimizador de
Racket. Estos predicados son casi disjuntos (no sé el termino técnico), así que
esto automáticamente habilita optimizaciones como
(strict-true? (vector 1 2
3)) ==> #f
y también
(vector? (if x
(begin (display x) #t)
#t))
==>
(begin
(if x
(begin (display x) #t)
#t)
#f)
(begin (display x) #t)
#t))
==>
(begin
(if x
(begin (display x) #t)
#t)
#f)
Reemplazar una variable por constante
Si el optimizador deduce que una variable verifica strict-true? la
reemplaza por #t.
(lambda (x)
(when (strict-true? x)
x))
==>
(lambda (x)
(when (strict-true? x)
#t))
(when (strict-true? x)
x))
==>
(lambda (x)
(when (strict-true? x)
#t))
Agregar boolean? como predicado relevante
También podemos agregar a la primitiva boolean? a
los predicados relevantes. El problema es que boolean? incluye
a strict-true? y not (not es
un predicado, es más evidente si la escribimos como not? o strict-false?
pero por razones históricas la llamamos not).
Entonces hay que agregar a mano el código para manejar las uniones e intersecciones y ver si una variable que verifica un predicado puede verificar otro predicado distinto.
Entonces tenemos reducciones como:
Entonces hay que agregar a mano el código para manejar las uniones e intersecciones y ver si una variable que verifica un predicado puede verificar otro predicado distinto.
Entonces tenemos reducciones como:
(lambda (f)
(boolean? (if (f)
(begin (display 1) #t)
(begin (display 2) #f)))
==>
(lambda (f)
(if (f)
(begin (display 1) #t)
(begin (display 2) #f))
#t)
(boolean? (if (f)
(begin (display 1) #t)
(begin (display 2) #f)))
==>
(lambda (f)
(if (f)
(begin (display 1) #t)
(begin (display 2) #f))
#t)
Otro ejemplo que parece que es más interesante es
(lambda (x)
(when (boolean? x)
(if x (box x) (vector x))))
==>
(lambda (x)
(when (boolean? x)
(if x (box #t) (vector #f))))
(when (boolean? x)
(if x (box x) (vector x))))
==>
(lambda (x)
(when (boolean? x)
(if x (box #t) (vector #f))))
Los predicados son booleanos
También podemos marcar al resultado de muchos predicados
usuales como un booleano, entonces tenemos que
(lambda (v)
(let ([x (vector? v)])
(if x (box x) (vector x))))
==>
(lambda (v)
(let ([x (vector? v)])
(if x (box #t) (vector #f))))
(let ([x (vector? v)])
(if x (box x) (vector x))))
==>
(lambda (v)
(let ([x (vector? v)])
(if x (box #t) (vector #f))))
Optimización para or
Un caso muy usual e interesante es la macro or. La
expansión (sin optimización) es
(lambda (x)
(or (symbol? x) 7)
==>
(lambda (x)
(let ([temp (symbol? x)])
(if temp temp 7)))
(or (symbol? x) 7)
==>
(lambda (x)
(let ([temp (symbol? x)])
(if temp temp 7)))
Con la nuevas optimizaciones, el optimizador se da cuenta que temp es booleana y lo optimiza a
==>
(lambda (x)
(let ([temp (symbol? x)])
(if temp #t 7)))
(lambda (x)
(let ([temp (symbol? x)])
(if temp #t 7)))
Sería bueno poder mover la expresión que define temp a la posición de uso y que quede
==>
(lambda (x)
(if (symbol? x) #t 7))
(lambda (x)
(if (symbol? x) #t 7))
pero el optimizador sólo mueve expresiones que define variables
que se usan una sola vez, y el optimizador no se da cuenta que después del
remplazo de temp por #t, a
variable temp queda usada una sola vez.
Por suerte ya había una optimización ad hoc para expresiones como las que produce or, pero se aplicaba sólo cuando estaban en un contexto booleano, como por ejemplo (if (or ...) ... ...) ó (not (or …)). Con algunos cambios la podemos extender a (or <boolean?> ...).
Conclusión
Con estas modificaciones, tendríamos una nueva primitiva en Racket. No es tan útil para usar directamente, pero ayuda a implementar optimizaciones para construcciones usuales, en particular para expresiones que combinan or y una expresión con un resultado booleano.
Para más detalles, pueden ver el código completo en github.
Para más detalles, pueden ver el código completo en github.
