ALGOL
ALGOL (abreviatura de "lenguaje algorítmico") es una familia de lenguajes imperativos de programación informática desarrollados originalmente en 1958. ALGOL influyó mucho en muchos otros idiomas y fue el método estándar para la descripción de algoritmos utilizado por la Association for Computing Machinery (ACM) en libros de texto y fuentes académicas durante más de treinta años.
En el sentido de que la sintaxis de la mayoría de los lenguajes modernos es "similar a Algol", podría decirse que fue más influyente que otros tres lenguajes de programación de alto nivel, entre los cuales era más o menos contemporáneo: FORTRAN, Lisp y COBOL. Fue diseñado para evitar algunos de los problemas percibidos con FORTRAN y finalmente dio lugar a muchos otros lenguajes de programación, incluidos PL/I, Simula, BCPL, B, Pascal y C.
ALGOL introdujo bloques de código y los pares begin
...end
para delimitarlos. También fue el primer lenguaje que implementó definiciones de funciones anidadas con alcance léxico. Además, fue el primer lenguaje de programación que prestó atención detallada a la definición formal del lenguaje y, a través del Informe Algol 60, introdujo la forma Backus-Naur, una notación gramatical formal principal para el diseño del lenguaje.
Había tres especificaciones principales, nombradas según los años en que se publicaron por primera vez:
- ALGOL 58 – originalmente se propuso llamar IAL, para International Algebraic Language.
- ALGOL 60 – primero implementado como X1 ALGOL 60 en 1961. Revisado 1963.
- ALGOL 68 – introdujo nuevos elementos incluyendo arrays flexibles, rebanadas, paralelismo, identificación del operador. Revisado 1973.
ALGOL 68 es sustancialmente diferente de ALGOL 60 y no fue bien recibido, por lo que, en general, "Algol" significa ALGOL 60 y sus dialectos.
Historia
ALGOL fue desarrollado conjuntamente por un comité de científicos informáticos europeos y estadounidenses en una reunión en 1958 en el Instituto Federal Suizo de Tecnología en Zúrich (cf. ALGOL 58). Especificaba tres sintaxis diferentes: una sintaxis de referencia, una sintaxis de publicación y una sintaxis de implementación. Las diferentes sintaxis le permitieron usar diferentes nombres de palabras clave y convenciones para los puntos decimales (comas frente a puntos) para diferentes idiomas.
ALGOL fue utilizado principalmente por científicos informáticos de investigación en los Estados Unidos y en Europa. Su uso en aplicaciones comerciales se vio obstaculizado por la ausencia de funciones estándar de entrada/salida en su descripción y la falta de interés en el idioma por parte de los grandes proveedores de computadoras que no sean Burroughs Corporation. Sin embargo, ALGOL 60 se convirtió en el estándar para la publicación de algoritmos y tuvo un profundo efecto en el desarrollo futuro del lenguaje.
John Backus desarrolló el método de forma normal de Backus para describir lenguajes de programación específicamente para ALGOL 58. Peter Naur lo revisó y amplió para ALGOL 60 y, por sugerencia de Donald Knuth, lo renombró Backus –Forma de Naur.
Peter Naur: "Como editor del ALGOL Bulletin, me involucré en los debates internacionales sobre el idioma y fui seleccionado para ser miembro del grupo europeo de diseño de idiomas en noviembre de 1959. En este cargo, fui el editor de el informe ALGOL 60, producido como resultado de la reunión ALGOL 60 en París en enero de 1960."
Las siguientes personas asistieron a la reunión en París (del 1 al 16 de enero):
- Friedrich L. Bauer, Peter Naur, Heinz Rutishauser, Klaus Samelson, Bernard Vauquois, Adriaan van Wijngaarden, y Michael Woodger (de Europa)
- John W. Backus, Julien Green, Charles Katz, John McCarthy, Alan J. Perlis, y Joseph Henry Wegstein (de los EE.UU.).
Alan Perlis dio una vívida descripción de la reunión: "Las reuniones fueron agotadoras, interminables y estimulantes. Uno se irritaba cuando las buenas ideas de uno eran descartadas junto con las malas de los demás. Sin embargo, la diligencia persistió durante todo el período. La química de los 13 fue excelente."
ALGOL 60 inspiró muchos idiomas que lo siguieron. Tony Hoare comentó: "Aquí hay un lenguaje tan adelantado a su tiempo que no solo fue una mejora con respecto a sus predecesores sino también a casi todos sus sucesores." El lenguaje de programación Scheme, una variante de Lisp que adoptó la estructura de bloques y el alcance léxico de ALGOL, también adoptó la redacción "Informe revisado sobre el esquema de lenguaje algorítmico" por sus documentos normativos en homenaje a ALGOL.
ALGOL y la investigación del lenguaje de programación
Como señaló Peter Landin, ALGOL fue el primer lenguaje en combinar perfectamente los efectos imperativos con el cálculo lambda (llamado por su nombre). Quizás la formulación más elegante del lenguaje se deba a John C. Reynolds, y es la que mejor exhibe su pureza sintáctica y semántica. El ALGOL idealizado de Reynolds también presentó un argumento metodológico convincente con respecto a la idoneidad de los efectos locales en el contexto de los lenguajes de llamada por nombre, en contraste con los efectos globales utilizados por los lenguajes de llamada por valor como ML. La integridad conceptual del lenguaje lo convirtió en uno de los principales objetos de investigación semántica, junto con la programación de funciones computables (PCF) y ML.
Línea de tiempo de implementaciones de IAL
Hasta la fecha ha habido al menos 70 aumentos, extensiones, derivaciones y sublenguajes de Algol 60.
Nombre | Año | Autor | País | Descripción | Objetivo CPU |
---|---|---|---|---|---|
ZMMD-implementation | 1958 | Friedrich L. Bauer, Heinz Rutishauser, Klaus Samelson, Hermann Bottenbruch | Alemania | aplicación de ALGOL 58 | Z22 (más tarde el Z23 de Zuse fue entregado con un compilador Algol 60) |
X1 ALGOL 60 | Agosto de 1960 | Edsger W. Dijkstra y Jaap A. Zonneveld | Países Bajos | Primera implementación de ALGOL 60 | Electrologica X1 |
Elliott ALGOL | 1960s | C. A. R. Hoare | UK | Tema de la conferencia de Turing de 1980 | Elliott 803, Elliott 503, Elliott 4100 series |
JOVIAL | 1960 | Jules Schwartz | USA | A DOD HOL prior to Ada | Diversos (véase el artículo) |
Burroughs Algol (Varias variantes) | 1961 | Burroughs Corporation (con participación de Hoare, Dijkstra y otros) | USA | Basis de los ordenadores Burroughs (y ahora Unisys MCP) | Burroughs sistemas grandes y su gama media también. |
Caso ALGOL | 1961 | Case Institute of Technology | USA | Simula fue contratado originalmente como una extensión de simulación del caso ALGOL | UNIVAC 1107 |
GOGOL | 1961 | William M. McKeeman | USA | Para el sistema de distribución de tiempo de la ODIN | PDP-1 |
RegneCentralen ALGOL | 1961 | Peter Naur, Jørn Jensen | Dinamarca | Aplicación del algoritmo total 60 | DASK en Regnecentralen |
Dartmouth ALGOL 30 | 1962 | Thomas Eugene Kurtz et al. | USA | LGP-30 | |
USS 90 Algol | 1962 | L. Petrone | Italia | ||
Traductor Algol | 1962 | G. van der Mey and W.L. van der Poel | Países Bajos | Staatsbedrijf der Posterijen, Telegrafie en Telefonie | ZEBRA |
Algol para niños | 1963 | F. G. Duncan | UK | English Electric Company KDF9 | |
VALGOL | 1963 | Val Schorre | USA | Una prueba del compilador META II | |
Whetstone | 1964 | Brian Randell y L. J. Russell | UK | Atomic Power Division of English Electric Company. Precursor de Ferranti Pegasus, Laboratorios Físicos Nacionales ACE e implementaciones de DEUCE Eléctrico Inglés. | English Electric Company KDF9 |
NU ALGOL | 1965 | Noruega | UNIVAC | ||
ALGEK | 1965 | URSS | АЛнц,К, basado en el apoyo ALGOL-60 y COBOL, para tareas económicas | Minsk-22 | |
ALGOL W | 1966 | Niklaus Wirth | USA | Proyecto de sucesor de ALGOL 60 | IBM System/360 |
MALGOL | 1966 | publ. A. Viil, M Kotli & M. Rakhendi, | Estonia, URSS | Minsk-22 | |
ALGAMS | 1967 | Grupo GAMS (ГАМС, група автоматизациии программирования для машин среднего класа), cooperación de Comecon Academies of Science | Comecon | Minsk-22, más tarde ES EVM, BESM | |
ALGOL/ZAM | 1967 | Polonia | Polaco ZAM | ||
Simula 67 | 1967 | Ole-Johan Dahl y Kristen Nygaard | Noruega | Algol 60 con clases | UNIVAC 1107 |
Triplex-ALGOL Karlsruhe | 1967/1968 | Karlsruhe, Alemania | ALGOL 60 (1963) con números triplex para intervalo aritmético | ||
Algol chino | 1972 | China | caracteres chinos, expresados a través del sistema de símbolos | ||
DG/L | 1972 | USA | DG Eclipse family of Computers | ||
S-algol | 1979 | Ron Morrison | UK | Adición de tipos de datos ortogonales con uso previsto como lenguaje de enseñanza | PDP-11 con posterior implementación en el VM Java |
Los dialectos de Burroughs incluían dialectos especiales de Bootstrapping como ESPOL y NEWP. Este último todavía se usa para el software del sistema Unisys MCP.
Propiedades
ALGOL 60 como se define oficialmente no tenía facilidades de E/S; las implementaciones definieron las suyas de maneras que rara vez eran compatibles entre sí. En contraste, ALGOL 68 ofreció una extensa biblioteca de instalaciones transput (entrada/salida).
ALGOL 60 permitía dos estrategias de evaluación para el paso de parámetros: la llamada común por valor y la llamada por nombre. La llamada por nombre tiene ciertos efectos en contraste con la llamada por referencia. Por ejemplo, sin especificar los parámetros como valor o referencia, es imposible desarrollar un procedimiento que intercambie los valores de dos parámetros si los parámetros reales que se pasan son una variable entera y una matriz indexada por esa misma variable entera. Piense en pasar un puntero a swap(i, A[i]) en una función. Ahora que cada vez que se hace referencia a swap, se vuelve a evaluar. Diga i:= 1 y A[i]:= 2, por lo que cada vez que se haga referencia a swap devolverá la otra combinación de los valores ([1,2], [2,1], [1,2] y así sucesivamente). Una situación similar ocurre con una función aleatoria pasada como argumento real.
Call-by-name es conocido por muchos diseñadores de compiladores por los interesantes "thunks" que se utilizan para implementarlo. Donald Knuth ideó la "prueba del hombre o del niño" para separar los compiladores que implementaron correctamente "recursividad y referencias no locales." Esta prueba contiene un ejemplo de llamada por nombre.
ALGOL 68 se definió utilizando un formalismo gramatical de dos niveles inventado por Adriaan van Wijngaarden y que lleva su nombre. Las gramáticas de Van Wijngaarden utilizan una gramática libre de contexto para generar un conjunto infinito de producciones que reconocerán un programa ALGOL 68 en particular; en particular, pueden expresar el tipo de requisitos que en muchos otros estándares de lenguajes de programación se denominan "semántica" y deben expresarse en prosa de lenguaje natural propensa a la ambigüedad, y luego implementarse en compiladores como código ad hoc adjunto al analizador de lenguaje formal.
Ejemplos y problemas de portabilidad
Comparaciones de muestras de código
ALGOL 60
(La forma en que se debe escribir el texto en negrita depende de la implementación, por ejemplo, 'INTEGER', comillas incluidas, para entero. Esto se conoce como stropping).
procedimiento Absmax(a) Size:(n, m) Resultado:(y) Subscripts:(i, k); valor n, m; array a; entero n, m, i, k; real y; comentario El mayor elemento absoluto de la matriz a, de tamaño n por m es transferido a y, y los subscriptos de este elemento a i y k; comenzar entero p, q; y:= 0; i:= k:= 1; para p:= 1 paso 1 hasta n do para q:= 1 paso 1 hasta m do si abs(a[p, q]) entonces comenzar y:= abs(a[p, q]); i:= p; k:= q finalfinal Absmax
Aquí hay un ejemplo de cómo producir una tabla usando Elliott 803 ALGOL.
PUNTO DE ALGOL ' BEGIN REAL A,B,C,D READ D FOR A:= 0.0 STEP D UNTIL 6.3 DO BEGIN PRINT PUNCH(3),£L? ' B:= SIN(A) ' C:= COS(A) ' PRINT PUNCH(3),SAMELINE,ALIGNED(1,6),A,B,C' FIN ' FIN '
PUNCH(3) envía la salida a la teleimpresora en lugar de a la perforadora de cinta.
SAMELINE suprime el retorno de carro + avance de línea que normalmente se imprime entre argumentos.
ALIGNED(1,6) controla el formato de la salida con 1 dígito antes y 6 después del punto decimal.
ALGOL 68
Los siguientes ejemplos de código son versiones de ALGOL 68 de los ejemplos de código de ALGOL 60 anteriores.
Las implementaciones de ALGOL 68 utilizaron los enfoques de ALGOL 60 para stropping. En el caso de ALGOL 68, los tokens con el tipo de letra negrita son palabras reservadas, tipos (modos) u operadores.
proc abs max = ([,]real a, ref real Sí, ref int i, k)real: comentario El mayor elemento absoluto de la matriz a, de tamaño aa por 2 2a es transferido a y, y los subscriptos de este elemento a i y k; comentariocomenzar real y:= 0; i:= ⌊a; k:= 2⌊a; para p desde ⌊a a ⌈a do para q desde 2⌊a a 2⌈a do si abdominales a[p, q] entoncesY... abdominales a[p, q]; i:= p; k:= q fi Od Od; Sí. final # Ab max #
Nota: los límites inferior (⌊) y superior (⌈) de una matriz y el corte de la matriz están directamente disponibles para el programador.
punto flotante algol68 prueba: () real a,b,c,d; # printf – envía salida al archivo de pie. # # printf($p$); – selecciona un nueva página # printf(($pg$",Enter d:")); read(d)); para paso desde 0 mientras a:=paso*d; a doprintf($l$); # dólares - selecciona a nueva línea. # b:= pecado(a); c:= cos(a); printf(($z-d.6d$,a,b,c)) # formatos de salida con 1 dígito antes y 6 después del punto decimal. # Od)
Cronología: Hola mundo
Las variaciones y la falta de portabilidad de los programas de una implementación a otra se demuestra fácilmente con el clásico programa hello world.
ALGOL 58 (IAL)
ALGOL 58 no tenía instalaciones de E/S.
Familia ALGOL 60
Dado que ALGOL 60 no tenía funciones de E/S, no hay ningún programa portátil hello world en ALGOL. Los siguientes tres ejemplos están en Burroughs Extended Algol. Los dos primeros tienen salida directa al terminal interactivo en el que se ejecutan. El primero usa una matriz de caracteres, similar a C. El lenguaje permite que el identificador de la matriz se use como un puntero a la matriz y, por lo tanto, en una instrucción REEMPLAZAR.
BEGIN QUIERO F()KIND=REMOTE); EBCDIC ARRAY E[0:11]; REPLACE E BY "¡HELLO WORLD!"; WRITE()F, *, E); FIN.
Un programa más simple que usa un formato en línea:
BEGIN QUIERO F()KIND=REMOTE); WRITE()F, ."¡HELLO WORLD!"■); FIN.
Un programa aún más simple que usa la instrucción Display. Tenga en cuenta que su salida terminaría en la consola del sistema ('SPO'):
BEGIN DISPLAY()"¡HELLO WORLD!") FIN.
Un ejemplo alternativo, usando Elliott Algol I/O es el siguiente. Elliott Algol usó diferentes caracteres para "open-string-quote" y "close-string-quote", representado aquí por ' y ' .
programa HiFolks; comenzar impresión 'Hola. mundo’ final;
A continuación se muestra una versión de Elliott 803 Algol (A104). El Elliott 803 estándar usaba cinta de papel de cinco orificios y, por lo tanto, solo tenía mayúsculas. El código carecía de caracteres de comillas, por lo que se usó £ (signo de libra esterlina) para comillas abiertas y ? (Signo de interrogación) para cerrar la cita. Las secuencias especiales se colocaron entre comillas dobles (por ejemplo, £ £ L ?? produjo una nueva línea en la teleimpresora).
HIFOLKS ' BEGIN PRINT £HELLO WORLD£L? ' FIN '
La versión de E/S de Algol de la serie ICT 1900 permitía la entrada desde cinta de papel o tarjeta perforada. Cinta de papel 'completa' modo permitido en minúsculas. La salida fue a una impresora de línea. Los caracteres de comillas de apertura y cierre se representaron usando '(' y ')' y espacios en %.
'BEGIN' TEXTO WRITE('('HELLO%WORLD')'); 'END'
ALGOL 68
El código ALGOL 68 se publicó con palabras reservadas, normalmente en minúsculas, pero en negrita o subrayadas.comenzarprintf(($gl$,"Hola, mundo!") final
En el lenguaje del "Informe Algol 68" las instalaciones de entrada/salida se denominaron colectivamente "Transput".
Línea de tiempo de los caracteres especiales de ALGOL
Los ALGOL se concibieron en una época en la que los conjuntos de caracteres eran diversos y evolucionaban rápidamente; además, los ALGOL se definieron de modo que solo se requerían letras mayúsculas.
1960: IFIP: el lenguaje y el informe de Algol 60 incluían varios símbolos matemáticos que están disponibles en las computadoras y los sistemas operativos modernos, pero, lamentablemente, no eran compatibles con la mayoría de los sistemas informáticos en ese momento. Por ejemplo: ×, ÷, ≤, ≥, ≠, ¬, ∨, ∧, ⊂, ≡, ␣ y ⏨.
Septiembre de 1961: ASCII: al juego de caracteres ASCII, entonces en una etapa temprana de desarrollo, se le agregó el carácter (barra invertida) para admitir los operadores booleanos / y / de ALGOL.
1962: ALCOR: este conjunto de caracteres incluía el inusual "᛭" carácter cruzado rúnico para la multiplicación y el "⏨" Símbolo de exponente decimal para notación de punto flotante.
1964: GOST: el estándar soviético GOST 10859 de 1964 permitía la codificación de caracteres de 4, 5, 6 y 7 bits en ALGOL.
1968: El "Informe Algol 68" – utilizó los caracteres ALGOL existentes y adoptó los caracteres →, ↓, ↑, □, ⌊, ⌈, ⎩, ⎧, ○, ⊥ y ¢ que se pueden encontrar en el teclado IBM 2741 con typeball (o pelota de golf) cabezales de impresión insertados (como la pelota de golf APL). Estos estuvieron disponibles a mediados de la década de 1960 mientras se redactaba ALGOL 68. El informe se tradujo al ruso, alemán, francés y búlgaro y permitió la programación en idiomas con conjuntos de caracteres más grandes, por ejemplo, el alfabeto cirílico del BESM-4 soviético. Todos los caracteres de ALGOL también forman parte del estándar Unicode y la mayoría de ellos están disponibles en varias fuentes populares.
Octubre de 2009: Unicode: el ⏨
(símbolo de exponente decimal) para la notación de punto flotante se agregó a Unicode 5.2 para compatibilidad con versiones anteriores del histórico software ALGOL del programa Buran.
Contenido relacionado
Luser
Núcleo monolítico
Multiprocesamiento