El dispositivo de Jensen es una técnica de programación informática que explota las llamadas por su nombre . Fue ideado por el informático danés Jørn Jensen , quien trabajó con Peter Naur en Regnecentralen . Trabajaron en el compilador GIER ALGOL , una de las primeras implementaciones correctas de ALGOL 60 . ALGOL 60 utilizó la llamada por nombre. [1] [2] [3] Durante su discurso del Premio Turing, Naur menciona su trabajo con Jensen en GIER ALGOL.
Descripción
El dispositivo de Jensen explota las llamadas por nombre y los efectos secundarios . Llamar por nombre es una convención de paso de argumentos que retrasa la evaluación de un argumento hasta que se usa realmente en el procedimiento, lo cual es una consecuencia de la regla de copia para procedimientos. ALGOL introdujo la llamada por su nombre.
Un ejemplo clásico del dispositivo de Jensen es un procedimiento que calcula la suma de una serie, : [4] [5] [6]
procedimiento real Suma (k, l, u, ak) valor l, u; entero k, l, u; real ak; el comentario k y ak se pasan por nombre; comenzar s reales ; s: = 0; para k: = l paso 1 hasta u hacer s: = s + ak; Suma: = s terminar ;
En el procedimiento, la variable de índice k
y el término de suma ak
se pasan por nombre. Llamar por nombre permite que el procedimiento cambie el valor de la variable de índice durante la ejecución del for
bucle. La llamada por nombre también hace que el ak
argumento se reevalúe durante cada iteración del ciclo. Normalmente, ak
dependerá del cambio (efecto secundario) k
.
Por ejemplo, el código para calcular la suma de los primeros 100 términos de una matriz real V[]
sería:
Suma (i, 1, 100, V [i]).
Durante la ejecución de Sum
, el argumento real i
se incrementará durante cada paso del for
ciclo, y cada una de las evaluaciones del procedimiento de ak
utilizará el valor actual de i
para acceder a los elementos sucesivos de la matriz V[i]
.
El dispositivo de Jensen es general. Se puede hacer una doble suma como:
Suma (i, l, m, Suma (j, l, n, A [i, j]))
La Sum
función se puede emplear para funciones arbitrarias simplemente empleando las expresiones apropiadas. Si se deseara una suma de números enteros, la expresión sería justa Sum(i,1,100,i);
, si una suma de cuadrados de números enteros, entonces Sum(i,1,100,i*i);
, y así sucesivamente. [7] Una ligera variación sería adecuada para iniciar una integración numérica de una expresión mediante un método muy similar al de Sum
.
La evaluación de ak
se implementa con un procesador , que es esencialmente una subrutina con un entorno. El thunk es un cierre sin argumentos. Cada vez que un procedimiento necesita el valor de su argumento formal, simplemente llama al procesador. El procesador evalúa el argumento real en el ámbito del código de llamada (no en el ámbito del procedimiento).
En ausencia de esta facilidad de paso por nombre, sería necesario definir funciones que incorporen esas expresiones que se pasarán de acuerdo con los protocolos del lenguaje informático, o crear una función de compendio junto con algún arreglo para seleccionar la expresión deseada para cada uso.
GPS
Otro ejemplo es GPS (General Problem Solver), que se describe en ALGOL 60 confidencial de DE Knuth y JN Merner . [8]
GPS de procedimiento real (I, N, Z, V); real I, N, Z, V; comience para I: = 1 paso 1 hasta que N haga Z: = V; GPS: = 1 extremo ;
A continuación se muestra una única declaración que encuentra m-ésimo primo usando GPS.
I: = GPS (I, si I = 0 entonces -1,0 otro I, P, si i = 1 entonces 1,0 demás si GPS (A, I, Z, si A = 1 entonces 1,0 demás si entier (A) x (entier (I) ÷ entier (A)) = entier (I) ∧ A then 0.0 else Z) = Z then ( si Pentonces P + 1 else I × GPS (A, 1.0, I, -1.0)) más P)
(Nota: En el artículo original, la expresión cerca del final se GPS(A, 1.0. I, 0.0)
debe a un caso de esquina en la especificación de la semántica de ALGOL 60 para la declaración).
Crítica
El dispositivo de Jensen se basa en la llamada por nombre, pero la llamada por nombre es sutil y tiene algunos problemas. En consecuencia, la llamada por nombre no está disponible en la mayoría de los idiomas. Knuth comenta que ALGOL 60 no puede expresar un increment(n)
procedimiento que aumente su argumento en uno; la llamada increment(A[i])
no realiza la acción esperada si i
es un funcional que cambia con cada acceso. [9] Knuth dice: "El uso de facilidades de definición 'macro' para extender el lenguaje, en lugar de depender únicamente de los procedimientos para este propósito, da como resultado un programa de ejecución más satisfactorio".
Otros señalan que un procedimiento de llamada por nombre que intercambia su argumento puede tener problemas sutiles. [10] Un procedimiento de intercambio obvio es:
procedimiento de intercambio (a, b) entero a, b; comenzar temp. entero; temp: = a; a: = b; b: = temp; final;
El procedimiento hace lo correcto para muchos argumentos, pero la invocación de swap(i,A[i])
es problemática. El uso de la regla de copia conduce a las asignaciones:
temp: = i; i: = A [i]; A [i]: = temp;
El problema son los cambios de la segunda asignación i
, por lo que A[i]
la tercera asignación probablemente no será el mismo elemento de matriz que al principio. Si, por otro lado, el procedimiento se codificara al revés (con b guardado en temp en lugar de a ), entonces resultaría la acción deseada, a menos que se invocara comoswap(A[i],i)
Ver también
- Pila de llamadas , marco de pila, enlace estático y pantalla (cierre que incluye enlace de entorno)
- Dispositivo de Duff
- Problema de Funarg de cómo pasar y devolver funciones como valores
- Prueba de hombre o niño , prueba de entorno
Referencias
- ^ Naur, Peter (2005). Video de la conferencia de Peter Naur . Premios ACM . Dinamarca: Asociación de Maquinaria Informática . Consultado el 11 de septiembre de 2020 .
- ^ David (1 de marzo de 2006). "El pionero del software Peter Naur gana el premio Turing de ACM" . Política pública de ACM . Asociación de Maquinaria Informática . Consultado el 11 de septiembre de 2020 .
- ^ "ACM: Becarios: Peter Naur, profesor emérito, Universidad de Copenhague, Cita" . 2005. Archivado desde el original el 12 de febrero de 2008 . Consultado el 21 de septiembre de 2020 .
- ^ MacLennan, Bruce J. (1987). Principios de lenguajes de programación: diseño, evaluación e implementación (Segunda ed.). Holt, Rinehart y Winston. págs. 141-142. ISBN 0-03-005163-0.
- ^ Dijkstra, EW (noviembre de 1961). "Defensa de ALGOL 60 (Carta al Editor)". Comunicaciones de la ACM . 4 (11): 502–503. doi : 10.1145 / 366813.366844 .
- ^ Knuth, DE (octubre de 1967). "Los puntos problemáticos restantes en ALGOL 60". Comunicaciones de la ACM . 10 (10): 611–617. doi : 10.1145 / 363717.363743 .
- ^
Sum
requiere unreal
argumento para el término, por lo que se asume la conversión de tipo. - ^ Donald E. Knuth y Jack N. Merner. 1961. ALGOL 60 confidencial. Comun. ACM 4, 6 (junio de 1961), 268-272. DOI = 10.1145 / 366573.366599 doi.acm.org
- ^ Knuth 1967 , p. 613. Por ejemplo,
increment(A[increment(j)])
se incrementaráj
dos veces. - ^ MacLennan, 1987