S-algol (St Andrews Algol) [1] : vii es un lenguaje de programación informática derivado de ALGOL 60 desarrollado en la Universidad de St Andrews en 1979 por Ron Morrison y Tony Davie. El lenguaje es una modificación de ALGOL para contener tipos de datos ortogonales que Morrison creó para su tesis doctoral . Morrison se convertiría en profesor de la universidad y jefe del departamento de informática . El lenguaje S-algol se utilizó para la enseñanza en la universidad a nivel de pregrado hasta 1999. También fue el lenguaje enseñado durante varios años en la década de 1980 en una escuela local en St. Andrews, Madras College . El texto de informática Recursive Descent Compiling [2] describe un compilador de descenso recursivo para S-algol, implementado en S-algol.
PS-algol es un derivado persistente de S-algol. Fue desarrollado alrededor de 1981 en la Universidad de Edimburgo y de St Andrews. Apoya la capacidad de las bases de datos al proporcionar longevidad de los datos en forma de un montón persistente que sobrevive a la finalización de los programas PS-algol.
La tesis doctoral de Ron Morrison de 1979, On the Development of Algol , describe el diseño y la implementación del lenguaje S-algol. [3] El informe técnico que define el lenguaje, The S-algol Reference Manual (1979, 1988), agradece a varias personas por su ayuda, incluido David Turner por las discusiones sobre el diseño del lenguaje alrededor de 1975. [4] : 5 El texto de informática de 1981 Recursive Descent Compiling describe la implementación del compilador y el proceso de arranque, [2] y el libro de 1982 An Introduction to Programming with S-algol usa el lenguaje para enseñar programación informática. [1]
La primera implementación de S-algol fue en una computadora PDP-11 /40 que ejecutaba el sistema operativo Unix . [1] : vii Debido al pequeño espacio de direcciones de 64 kilobytes disponible en el PDP-11, se eligió una implementación de código de bytes interpretado. [3] : 37–38 Un compilador de descenso recursivo de una sola pasada escrito en S-algol tradujo el código fuente de S-algol en S-code, un código de bytes para una máquina abstracta basada en pila diseñada para S-algol. Luego, un intérprete ejecutó el S-code . La implementación de S-algol tenía muchas similitudes con el trabajo en compiladores Pascal anteriores . La técnica de usar un compilador de descenso recursivo para producir código para una máquina abstracta era bien conocida, y el compilador Pascal P fue un ejemplo famoso de principios de la década de 1970. [2] : 137 El compilador S-algol fue escrito utilizando el proceso de refinamiento paso a paso [2] : 71 descrito por Urs Amman para el desarrollo de un compilador Pascal [5] y defendido por el inventor de Pascal, Niklaus Wirth . [6]
Reflejando la organización de la memoria del PDP-11 como 32K palabras de 16 bits , la codificación de instrucciones del código S se diseñó de modo que cada código de bytes constara de una palabra. [3] : 38 El arranque inicial se realizó escribiendo un compilador S-algol en Algol W en el IBM/360 que producía código S, y usándolo para compilar el compilador escrito en S-algol a código S. El archivo S-code resultante se copió al PDP-11 y se ejecutó en un intérprete S-code escrito para el PDP-11, lo que lo convirtió en autoalojado . El compilador S-algol autoalojado ejecutó aproximadamente 7,7 millones de instrucciones S-code para compilarse a sí mismo, generando un archivo de salida de aproximadamente diez mil instrucciones S-code (palabras de 16 bits). [3] : 45
Se escribió un intérprete de código S para el ordenador VAX que ejecutaba VMS , lo que convirtió al VAX en el primer puerto de S-algol . S-algol también se portó al microprocesador Zilog Z80 que ejecutaba CP/M , incluidas las funciones de gráficos rasterizados que se habían agregado al lenguaje. En 1983, S-algol se utilizó como base para el sistema PS-algol, utilizado para la investigación en persistencia . El intérprete de código S PS-algol se implementó en C , y el lenguaje de código S se amplió para incluir gráficos rasterizados. La implementación de PS-algol fue la base para los puertos de S-algol a las estaciones de trabajo Macintosh y Sun , que presentaban un compilador reescrito en C y apuntaban al código S extendido. [4] : 5
S-algol fue la base de la investigación de PS-algol en 1983 y, unos años más tarde, PS-algol se convirtió en el punto de partida del lenguaje y la implementación de Napier88 . Si bien todos los compiladores de S-algol producían código S para ser interpretado, una implementación posterior de Napier88 experimentó con la generación de código en C y su compilación con el compilador gcc para proporcionar una implementación de código nativo . [7]
Un programa S-algol es una secuencia de declaraciones y cláusulas. Los elementos del lenguaje que se declaran incluyen constantes, variables, procedimientos y estructuras. Las declaraciones de constantes y variables deben especificar un valor inicial. El compilador infiere el tipo de datos de la constante o variable declarada a partir del tipo del valor inicial, por lo que el tipo no se indica explícitamente. Los tipos de datos incluyen enteros, reales, booleanos, cadenas, punteros (a una estructura) y archivos, y vectores (matrices) de estos tipos. Las declaraciones de procedimientos especifican los tipos de datos de sus argumentos y el valor de retorno (a menos que sea void). Las estructuras también especifican los tipos de datos de sus campos. Las cláusulas incluyen expresiones y estructuras de control (if, case, for, while y repeat while). Las estructuras de control if y case pueden tener valores y pueden usarse libremente en expresiones siempre que se cumplan las reglas de compatibilidad de tipos. [4] [1]
! Los comentarios se introducen con un signo de exclamación y continúan hasta el final de la línea.! La palabra clave let introduce declaraciones de constantes y variables.! Los identificadores comienzan con un carácter alfabético seguido de caracteres alfanuméricos o el punto (.).! Se debe proporcionar un valor inicial, y esto determina el tipo de datos de la declaración.let width := 10 ! := establece el valor de una variable, este es un intdeje que el animal := "perro" ! tipo cadenasea x := -7 ; sea y := x + x ! ; separa cláusulas, es necesario solo si hay dos o más cláusulas en una líneasea na = 6.022e+23 ! = se usa para establecer el valor de una constante, esta es una cfloat (float constante)! if y case pueden tener valores y usarse en expresionessea no.de.vidas := si animal = "gato" entonces 9 de lo contrario 1! Tamiz de Eratóstenesescribe "Encontrar primos hasta n = ?"sea n = readi! Los valores constantes se pueden configurar durante la ejecución del programasea p = vector 2::n de verdadero! vector de bool con límites de 2 a npara i = 2 para truncar (sqrt(n)) ¡haga! porque los índices son constantes, por lo que utilizan = en lugar de := Si p(i) ¡hazlo! la desreferenciación vectorial usa paréntesis como una llamada a procedimiento para j = 2 * i a n por i hacer p(j) := falsopara i = 2 a n hacer Si p(i) escribe i, "'n" ! 'n en una cadena literal es una nueva línea¡Tipo de estructura (registro) para un árbol binario de cstrings!! El tipo de datos pntr puede apuntar a una estructura de cualquier tipo, la verificación de tipo se realiza en tiempo de ejecuciónestructura tree.node(cstring nombre; pntr izquierda, derecha)! inserta una nueva cadena en la cabecera del árbol binarioprocedimiento insertar.tree(cpntr head ; cstring new -> pntr)! la cláusula del caso termina con una opción predeterminada obligatoria, use default : {} si no es necesariacaso cierto de cabeza = nil : árbol.nodo(nuevo, nil, nil) nuevo < cabeza(nombre) : { cabeza(izquierda) := insert.tree(cabeza(izquierda), nuevo) ; cabeza } nuevo > cabeza(nombre) : { cabeza(derecha) := insert.tree(cabeza(derecha), nuevo) ; cabeza } predeterminado: cabezaprocedimiento print.tree(cpntr head)si cabeza ~= nil hacer ! ~= es el operador no igualcomenzar imprimir.árbol(cabeza(izquierda)) escribe cabeza(nombre), "'n" imprimir.árbol(cabeza(derecha))findeja fruta := nulofruta := insert.arbol(fruta, "banana")fruta := insert.arbol(fruta, "kiwi")fruta := insert.arbol(fruta, "manzana")fruta := insert.tree(fruta, "melocotón")print.tree(fruit) ! imprimir en orden ordenado! El final del programa S-algol está indicado por ??Como sugiere su nombre, S-algol es un miembro de la familia de lenguajes de programación ALGOL . Morrison identifica cinco rasgos de la familia ALGOL: [3] : 5
S-algol fue diseñado para diferenciarse de los miembros anteriores de la familia ALGOL al estar diseñado de acuerdo con principios semánticos para brindar potencia a través de la simplicidad y simplicidad a través de una mayor generalidad. (Ver Ortogonal ). Morrison describe tres principios semánticos que guiaron el diseño de S-algol:
Morrison también identifica una consideración de diseño más básica:
La tesis de Morrison explica cómo se aplicaron los principios de diseño en S-algol.
Los tipos de datos básicos o primitivos en S-algol son entero, real, booleano, archivo y cadena. (Más tarde se agregaron los tipos píxel e imagen para admitir gráficos rasterizados ). Entero , real y booleano son tipos comunes a la mayoría de los lenguajes de programación. El tipo archivo es un flujo de entrada/salida (E/S) que permite escribir o leer objetos de datos. El tipo cadena en muchos lenguajes en ese momento se consideraba un tipo compuesto , pero incluirlo como un tipo nativo hace que las operaciones básicas de concatenación, selección de subcadenas, longitud y comparaciones (igual a, menor que, etc.) sean más fáciles de usar. Es mucho más agradable que las matrices de caracteres utilizadas en Pascal. [3] : 12
Los vectores se proporcionan con componentes de cualquier tipo. Para cualquier tipo de datos T, *Tes el tipo de un vector con componentes de tipo T. Los límites del vector no son parte de su tipo, sino que se determinan dinámicamente, y las matrices multidimensionales se implementan como vectores de vectores . [3] : 12
El tipo de datos de estructura comprende cualquier número fijo de campos, cada uno de un tipo fijo. La clase de una estructura no es parte del tipo, pero se puede determinar dinámicamente. [3] : 12
El cierre de tipos básicos sobre vectores y estructuras proporciona un número infinito de tipos de datos. La definición del lenguaje permite que se utilice cualquier tipo en cualquier lugar donde un tipo sea aceptable. Esto no se aplica a los operadores infijos , ya que son azúcar sintáctico para funciones comunes y no son parte del modelo semántico. [3] : 12–13
Los vectores y las estructuras tienen todos los derechos y pueden asignarse tal como se pasan como parámetros, pero la copia en la asignación y cuando se pasa puede ser ineficiente para objetos grandes. Los vectores y las estructuras se tratan como punteros a los objetos, y los punteros se asignan y se pasan como parámetros. Los punteros como objetos generales en sí mismos como en ALGOL 68 y C se rechazan para S-algol debido a las preocupaciones de CAR Hoare sobre el puntero nulo [11] y los problemas con los punteros colgantes . [3] : 13
S-algol proporciona valores constantes verdaderos , objetos cuyo valor no se puede actualizar. Esta idea se debe a Strachey, pero las constantes en muchos lenguajes como Pascal son constantes manifiestas, procesadas en tiempo de compilación y no implementadas como ubicaciones protegidas. También debe ser posible declarar una constante de cualquier tipo de datos, no solo de los tipos escalares. [3] : 13
S-algol es un lenguaje orientado a expresiones y las sentencias son expresiones de tipo void . En consecuencia, algunas estructuras de control son expresiones que generan valores .
Existen varias construcciones condicionales . La versión de dos alternativas de la condicional es if <condition> then <clause> else <clause>, donde las cláusulas pueden ser declaraciones o expresiones. Si son expresiones, deben tener el mismo tipo. La condicional de un brazo if <condition> do <statement>tiene el tipo void. [3] : 13 El uso de doen lugar de elseen la declaración condicional evita la ambigüedad sintáctica pendiente de else . [2] : 20
La casecláusula tiene un selector de cualquier tipo que se compara mediante una prueba de igualdad con expresiones del mismo tipo para encontrar la cláusula seleccionada. La cláusula de caso puede ser una declaración o una expresión, por lo que las cláusulas de resultado deben ser todas declaraciones (tipo void) o expresiones del mismo tipo. Las coincidencias se prueban en orden, por lo que esto se asemeja a los comandos protegidos de Edsger Dijkstra sin el no determinismo . [3] : 14
Las instrucciones de bucle son en su mayoría convencionales. El forbucle es similar al de Hoare. [12] El identificador de control es constante y no se puede modificar dentro del bucle. También son convencionales los bucles while <condition> do <statement>and repeat <statement> while <condition>. La repeat <statement> while <condition> do <statement>construcción proporciona la salida temprana o bucle "n-y-a-half" [13] . [3] : 14
S-algol abstrae expresiones como funciones y declaraciones (expresiones nulas) como procedimientos. Los módulos proporcionarían la abstracción de declaraciones, pero S-algol no incluye módulos debido a las dificultades que plantean con el alcance estructurado en bloques. La categoría sintáctica final es secuenciador o estructura de control. Tennent utilizó el término sequel para la abstracción sobre secuenciadores, que serían generalizaciones de goto y break . La abstracción más conocida en esta categoría es call-with-current-continuation , pero no se entendería bien hasta algunos años después. S-algol no incluye goto ni break, y no incluye abstracción sobre secuenciadores. [3] : 14
Cada objeto de datos en S-algol debe recibir un valor cuando se declara. Esto corresponde a una llamada por paso de parámetros de valor y elimina la posibilidad de usar un valor no inicializado. De hecho, la llamada por valor es el único método de paso de parámetros en S-algol. Los parámetros de referencia y resultado son rechazados, lo que es consistente con la prohibición de S-algol de pasar valores l . Las estructuras y los vectores se pasan como punteros a los objetos, pero esto sigue siendo una llamada por valor ya que el comportamiento es el mismo que el valor utilizado en el lado derecho de las asignaciones. [3] : 15
Cada declaración tiene un equivalente paramétrico. Todos los tipos de parámetros de procedimiento deben especificarse. Cualquier procedimiento que se pase como parámetro tiene su tipo completo especificado (a diferencia de Pascal) y lo mismo es válido para una clase de estructura. [3] : 15
S-algol proporciona el filetipo de datos para los flujos de E/S, y se definen varias variaciones de ready writepara operar en los tipos básicos. Se espera que las implementaciones individuales amplíen estas sencillas funciones según sea necesario. [3] : 15
Los lenguajes ALGOL han sido criticados por ser demasiado verbosos. S-algol intenta mejorar esto proporcionando una sintaxis menos restrictiva. [1] : 159 Esto se demuestra principalmente en la sintaxis de declaración. Dado que las declaraciones de variables siempre deben incluir un valor inicial, no es necesario especificar el tipo explícitamente. [3] : 17
Aunque sería posible inferir los tipos de parámetros y de retorno de un procedimiento examinando dónde se llama al procedimiento, S-algol requiere que se especifiquen los tipos de parámetros y de retorno. Esta es una decisión práctica, ya que debería ser posible comprender un procedimiento sin examinar sus llamadas. [3] : 17
La mayoría de los ALGOL requieren que todas las declaraciones se presenten antes de las declaraciones en un bloque. En S-algol, las declaraciones se pueden mezclar con las declaraciones porque todo debe declararse antes de usarse y no hay un goto que permita saltarse una declaración. [3] : 17