Introducción
Thunks
En un concepto anterior se mencionó que tanto las etiquetas locales como las funciones no son más que direcciones dentro de una sección con código ejecutable, como section .text.
De hecho, las funciones se pueden manipular igual que cualquier dirección de memoria, es decir, se pueden cargar en registros, pasar de un sitio a otro y guardar en memoria.
También es posible usar call o jmp para transferir la ejecución a una función guardada en un registro o en memoria:
section .text
sum_op:
lea rax, [rdi + rsi] ; loads the sum rdi + rsi into rax
ret
apply_sum:
lea rax, [rel sum_op]
jmp rax ; tail call
Una dirección de función que se pasa de un sitio a otro como un valor se denomina thunk.
Los thunks son un componente básico de la programación de orden superior en ensamblador: código que opera sobre otro código.
El código como datos
Las direcciones de función también se pueden guardar en memoria y recuperar más tarde:
section .bss
cached_fn resq 1
section .text
save_op:
mov qword [rel cached_fn], rdi
ret
apply_op:
; arguments are already set up according to the ABI
jmp qword [rel cached_fn] ; tail call
save_op escribe en cached_fn la dirección de función que recibe.
El valor persiste después de que save_op devuelva, así que cualquier llamada posterior a apply_op salta a la última dirección que se haya guardado.
Esto permite cambiar qué función invoca apply_op en tiempo de ejecución.
Tablas de despacho
Guardar direcciones de función en un array permite seleccionar distintas funciones según un índice, que puede depender de una condición en tiempo de ejecución.
Esto se conoce como tabla de despacho:
section .data
dispatch_table dq add_op, sub_op, mul_op
section .text
dispatch:
; this function takes two arguments in rdi and rsi, and an index in rdx
; it then applies the function corresponding to the index in rdx to the arguments
lea rax, [rel dispatch_table]
jmp qword [rax + 8*rdx] ; tail-call the function address for the index
Thunks con estado
Un thunk que lee o actualiza cierta memoria persistente entre llamadas puede comportarse de forma distinta según lo que haya ocurrido antes.
Su resultado puede depender de algo más que de sus propios argumentos.
Por ejemplo, un contador que recibe una función y la invoca con el recuento actual, avanzando el recuento cada vez:
section .data
count dq 0
section .text
tick:
mov rax, rdi ; saves the function address
mov rdi, [rel count] ; loads the current count as the function's argument
inc qword [rel count] ; advances the count
jmp rax ; tail-calls the function
tick invoca la función dada con el recuento actual como argumento y, después, avanza el recuento.
Así, la primera llamada a tick(square) invoca square(0), la siguiente llamada a tick(square) invoca square(1), la siguiente square(2), y así sucesivamente.
Otro ejemplo sería un cálculo diferido:
section .bss
captured_fn resq 1
argument resq 1
section .text
delay:
mov qword [rel captured_fn], rdi ; saves the function
mov qword [rel argument], rsi ; saves the argument
lea rax, [rel invoke] ; returns the `invoke` function
ret
invoke:
mov rdi, qword [rel argument] ; loads the saved argument into `rdi`
jmp qword [rel captured_fn] ; tail-calls the saved function
delay recibe una función y un valor, los guarda y devuelve invoke.
Cuando se llama a invoke, ejecuta la función capturada con el argumento guardado.
Muchos de los patrones habituales en los lenguajes de nivel superior, como los callbacks, los métodos virtuales, los generadores, el currying, la composición de funciones y muchos otros, se construyen sobre thunks combinados con estado persistente.
Instrucciones
Eres el contable de un pequeño banco de pueblo.
Cada cliente tiene una cuenta y tú llevas su saldo en tu libro de cuentas.
A lo largo del año, se aplican transacciones a estos saldos: se abonan intereses, se deducen comisiones, se pagan bonificaciones y se cobran penalizaciones.
Cada transacción toma un saldo y produce uno nuevo.
Tienes cuatro tareas.
Puedes asumir que cada thunk (transacciones y guardas) de este ejercicio es una función que:
- toma como argumento un número entero no negativo de 64 bits
- y además devuelve un número entero no negativo de 64 bits.
1. Recordar una transacción
El cajero conoce una nueva transacción al empezar el día y la anota para poder aplicarla más tarde, cuando llegue un cliente.
Define dos funciones:
-
remember_transaction toma una transacción y la almacena en memoria.
-
apply_remembered toma un saldo y le aplica la transacción almacenada previamente.
Ejemplo, suponiendo que add_interest es una transacción que abona cinco unidades de interés:
remember_transaction(add_interest);
apply_remembered(100);
// => 105
remember_transaction(service_fee);
apply_remembered(100);
// => 98 (assuming service_fee deducts 2)
Para remember_transaction:
- El argumento es una transacción que se guarda para usarla más tarde.
- No hay valor devuelto.
Para apply_remembered:
- El argumento es un número entero no negativo de 64 bits.
- El valor devuelto es un número entero no negativo de 64 bits.
2. El manual del banco
El manual del banco tiene una lista de transacciones frecuentes almacenada en una tabla de despacho.
Cada sucursal mantiene su propia copia de la lista y puede registrar transacciones distintas según su política local.
Define dos funciones que operan sobre una tabla de despacho proporcionada por quien llama:
-
register_transaction toma la dirección de memoria de una tabla de despacho, un índice y una transacción.
Almacena esta transacción en el índice indicado de la tabla.
-
select_transaction toma la dirección de memoria de una tabla de despacho, un índice y un saldo.
Busca la transacción en el índice indicado y la aplica al saldo, devolviendo el nuevo saldo.
select_transaction debe llegar a la transacción buscada con una única llamada de cola indirecta.
Ejemplo, suponiendo que manual es la dirección de memoria de una tabla de despacho con cuatro ranuras vacías:
register_transaction(manual, 0, monthly_interest);
register_transaction(manual, 1, service_fee);
select_transaction(manual, 0, 100);
// applies monthly_interest to 100
select_transaction(manual, 1, 100);
// applies service_fee to 100
Para register_transaction:
- El primer argumento es la dirección de memoria de una tabla de despacho.
- El segundo argumento es un número entero no negativo de 64 bits (el índice).
- El tercer argumento es una transacción.
- No hay valor devuelto.
Para select_transaction:
- El primer argumento es la dirección de memoria de una tabla de despacho.
- El segundo argumento es un número entero no negativo de 64 bits (el índice).
- El tercer argumento es un número entero no negativo de 64 bits (el saldo).
- El valor devuelto es un número entero no negativo de 64 bits.
Al final del mes, se concilia la cuenta de un cliente.
Cada transacción que tuvo lugar durante el mes se aplica al saldo inicial, una tras otra, y el resultado es el nuevo saldo.
Define una función process_statement que toma un saldo inicial, la dirección de memoria de un array de transacciones y el número de transacciones del array.
Para cada transacción en secuencia, debe aplicar la transacción al saldo acumulado y después usar el resultado como saldo para la siguiente transacción.
Se devuelve el saldo final.
En pseudocódigo, process_statement(balance, transactions, n) calcula:
for each transaction in transactions:
balance = transaction(balance)
return balance
Ejemplo, suponiendo que transactions es la dirección de memoria de un array que contiene las transacciones add_interest, service_fee y add_interest en ese orden, donde add_interest suma 5 y service_fee resta 2:
process_statement(100, transactions, 3);
// add_interest(100) = 105
// service_fee(105) = 103
// add_interest(103) = 108
// => 108
El primer argumento es un número entero no negativo de 64 bits.
El segundo argumento es la dirección de memoria de un array de transacciones.
El tercer argumento es un número entero no negativo de 64 bits (la longitud del array).
El valor devuelto es un número entero no negativo de 64 bits.
4. Procesar con una guarda
La política del banco exige que ciertas transacciones se comprueben antes de confirmarse.
Una guarda es una función que inspecciona un saldo propuesto y decide si es aceptable.
Esta función de guarda devuelve un valor distinto de cero para aprobar, o cero para rechazar.
Define process_with_guard, que toma un saldo inicial, la dirección de memoria de un array de transacciones, el número de transacciones del array y una función de guarda.
Para cada transacción en secuencia:
- Aplica la transacción al saldo acumulado para calcular un nuevo saldo tentativo.
- Llama a la guarda con el saldo tentativo.
- Si la guarda devuelve un valor distinto de cero, confirma: el saldo acumulado pasa a ser el saldo tentativo.
- Si la guarda devuelve cero, el saldo acumulado no cambia y se omite la transacción.
Una vez procesadas todas las transacciones, devuelve el saldo final junto con el número de transacciones aprobadas.
En pseudocódigo, process_with_guard(balance, transactions, n, guard) calcula:
approved = 0
for each transaction in transactions:
tentative = transaction(balance)
if guard(tentative) is non-zero:
balance = tentative
approved = approved + 1
return balance, approved
Por ejemplo, supón que:
-
add_interest es una transacción que suma 5 y service_fee es otra transacción que resta 2
-
at_least_10 es una guarda que devuelve un valor distinto de cero cuando el saldo es >= 10
Entonces:
process_with_guard(5, {add_interest, service_fee, add_interest}, 3, at_least_10);
// add_interest(5) = 10; at_least_10(10) != 0;
// => balance = 10, approved = 1
//
// service_fee(10) = 8; at_least_10(8) = 0;
// => balance = 10, approved = 1
//
// add_interest(10) = 15; at_least_10(15) != 0;
// => balance = 15, approved = 2
//
// final balance (15) is returned in rax
// number of approved transactions (2) is returned in rdx
Para process_with_guard:
- El primer argumento es un número entero no negativo de 64 bits (el saldo inicial).
- El segundo argumento es la dirección de memoria de un array de transacciones.
- El tercer argumento es un número entero no negativo de 64 bits (la longitud del array).
- El cuarto argumento es una función de guarda que toma un número entero no negativo de 64 bits y devuelve un número entero no negativo de 64 bits.
- Los valores devueltos son dos números enteros no negativos de 64 bits: el saldo final en
rax y el número de transacciones aprobadas en rdx.
Ejercicio de aprendizaje
