S-algol (St Andrews Algol) [1] : vii es un lenguaje de programación informático 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 usó para enseñar en la universidad en una licenciatura.nivel hasta 1999. También fue el idioma que se enseñó 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.
Paradigmas | Multi-paradigma : procedimental , imperativo , estructurado |
---|---|
Familia | ALGOL |
Diseñada por | Ron Morrison , Tony Davie |
Desarrollador | Universidad de St Andrews |
Apareció por primera vez | 1979 |
Lenguaje de implementación | S-algol |
Plataforma | PDP-11 /40, IBM System / 360 , VAX , Zilog Z80 , Macintosh , Sun-3 |
SO | Unix , BOS / 360 , VMS , CP / M |
Influenciado por | |
ALGOL 60 | |
Influenciado | |
PS-algol , Napier88 |
PS-algol es un derivado persistente de S-algol. Fue desarrollado alrededor de 1981 en la Universidad de Edimburgo y de St Andrews. Es compatible con la capacidad de la base de datos al proporcionar longevidad de los datos en forma de un montón persistente que sobrevive a la terminación de los programas PS-algol.
Historia e implementaciones
La tesis doctoral de Ron Morrison de 1979, Sobre el desarrollo de 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 ciencias de la computación de 1981 Recursive Descent Compiling describe la implementación del compilador y el proceso de arranque, [2] y el libro de 1982 Una introducción a la programación con S-algol usa el lenguaje para enseñar programación de computadoras. [1]
La primera implementación de S-algol fue en una computadora PDP-11 /40 que ejecuta 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 A de un solo paso , recursiva compilador descenso escrito en S-algol traducida S-algol fuente en S-código, un código de bytes para una máquina abstracta basado en la pila a medida para S-algol. A continuación, la S-código fue ejecutado por un intérprete . La implementación de S-algol tenía muchas similitudes con el trabajo en compiladores Pascal anteriores . La técnica de utilizar un compilador de descendencia recursiva para producir código para una máquina abstracta era bien conocida, siendo el compilador Pascal P un ejemplo famoso de principios de la década de 1970. [2] : 137 El compilador S-algol fue escrito usando 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 de código S se diseñó de modo que cada bytecode consistiera en 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 en código S. El archivo de código S resultante se copió en el PDP-11 y se ejecutó en un intérprete de código S escrito para el PDP-11, haciéndolo autohospedado . El compilador S-algol autohospedado ejecutó aproximadamente 7,7 millones de instrucciones de código S para compilarse a sí mismo, generando un archivo de salida de unas diez mil instrucciones de código S (palabras de 16 bits). [3] : 45
Se escribió un intérprete de código S para la computadora VAX que ejecuta VMS , lo que convierte al VAX en el primer puerto S-algol . S-algol también se transfirió al microprocesador Zilog Z80 que ejecuta CP / M , incluidas las funciones de gráficos de trama 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 de la 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 S-algol a las estaciones de trabajo Macintosh y Sun , con un compilador reescrito en C y dirigido al código S extendido. [4] : 5
S-algol fue la base para la investigación de PS-algol en 1983, y unos años más tarde PS-algol se convirtió en el punto de partida para el lenguaje y la implementación de Napier88 . Si bien todos los compiladores de S-algol produjeron código S para ser interpretado, una implementación posterior de Napier88 experimentó con la generación de código en C y compilándolo con el compilador gcc para proporcionar una implementación de código nativo . [7]
Descripción general del idioma
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 del tipo del valor inicial, por lo que el tipo no se indica explícitamente. Los tipos de datos incluyen entero, real, booleano, cadena, puntero (a una estructura) y archivo, y vectores (matrices) de estos tipos. Las declaraciones de procedimiento especifican los tipos de datos de sus argumentos y el valor de retorno (a menos que sea nulo). 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 dar un valor inicial, y esto determina el tipo de datos de la declaración.deje ancho: = 10! : = establece el valor de una variable, este es un intlet animal: = "perro"! tipo cadenasea x: = -7; sea y: = x + x! ; separa cláusulas, 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, esto es un cfloat (constante flotante)! if y case pueden tener valores y usarse en expresioneslet no.of.lives: = if animal = "cat" then 9 else 1! Tamiz de Eratóstenesescriba "Encontrar números primos hasta n =?"sea n = readi! Se pueden establecer valores constantes durante la ejecución del programa.sea p = vector 2 :: n de verdadero! vector de bool con límites 2 anpara i = 2 para truncar (sqrt (n)) haz! porque los índices son constantes, por lo que usan = en lugar de: = si p (i) lo hago! la desreferencia vectorial usa parens como una llamada a procedimiento para j = 2 * i an por lo que hago p (j): = falsopara i = 2 an do 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 name; pntr left, right)! inserta una nueva cadena en la cabeza del árbol binarioprocedimiento insert.tree (cpntr head; cstring new -> pntr)! la cláusula de caso termina con una opción predeterminada obligatoria, use default: {} si no es necesariocaso verdadero de head = nil: tree.node (nuevo, nulo, nulo) nuevo cabeza } nuevo> encabezado (nombre): {encabezado (derecha): = insert.tree (encabezado (derecha), nuevo); cabeza } predeterminado: cabezaprocedimiento print.tree (cpntr head)si cabeza ~ = nada! ~ = es el operador no igualempezar print.tree (cabeza (izquierda)) escribir cabeza (nombre), "'n" print.tree (cabeza (derecha))finaldejar fruta: = nulofruta: = insertar.árbol (fruta, "plátano")fruit: = insert.tree (fruta, "kiwi")fruit: = insert.tree (fruta, "manzana")fruit: = insert.tree (fruta, "melocotón")print.tree (fruta)! imprimir en orden ordenado! El final del programa S-algol está indicado por??
Principios semánticos
Como sugiere su nombre, S-algol es miembro de la familia de lenguajes de programación ALGOL . Morrison identifica cinco rasgos de la familia ALGOL: [3] : 5
- Reglas de alcance y estructura de bloques : se pueden introducir nombres para definir cantidades locales que no están definidas fuera del entorno local , pero diferentes entornos pueden usar el mismo nombre sin ambigüedades para representar diferentes objetos. [3] : 5
- Facilidad de abstracción : provisión de una poderosa facilidad de abstracción para acortar y aclarar programas. En la familia ALGOL esto se ofrece mediante procedimientos con parámetros . [3] : 5
- Verificación de tipos en tiempo de compilación : los tipos se pueden verificar mediante un análisis estático del programa. [3] : 5
- Almacén infinito : el programador no es responsable de la asignación de almacenamiento y puede crear tantos objetos de datos como sea necesario. [3] : 5
- Actualización selectiva de la tienda : el programa puede alterar selectivamente la tienda. En la familia ALGOL, esto se efectúa mediante la declaración de cesión . [3] : 6
S-algol fue diseñado para diferir de los miembros anteriores de la familia ALGOL al estar diseñado de acuerdo con principios semánticos para proporcionar poder 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:
- Principio de correspondencia : las reglas que rigen los nombres deben ser uniformes y aplicarse en todas partes. Esto se aplica principalmente a la correspondencia entre declaraciones y parámetros de procedimiento, incluida la consideración de todos los modos de paso de parámetros. Este principio fue examinado por RD Tennent junto con Pascal, [8] y tiene sus raíces en el trabajo de Peter Landin [9] y Christopher Strachey . [3] : 9-10 [10]
- Principio de abstracción : debería ser posible abstraer todas las categorías semánticas significativas en el lenguaje. Los ejemplos incluyen la función, que es una abstracción sobre expresiones , y el procedimiento, una abstracción sobre declaraciones . Tennent y Morrison señalan que este es un principio difícil de aplicar porque es difícil identificar los constructos semánticamente significativos que deben abstraerse. [3] : 10
- Principio de integridad del tipo de datos : todos los tipos de datos deben tener los mismos derechos en el idioma y deben estar permitidos en operaciones generales como la asignación o la transferencia como parámetro. [3] : 10 (Ver ciudadano de primera clase ).
Morrison también identifica una consideración de diseño más básica:
- Tienda conceptual : las decisiones clave de diseño relacionadas con la tienda ( gestión de la memoria ) incluyen cómo se utiliza la tienda, su relación con los tipos de datos, la implementación de punteros y la protección ( ubicaciones constantes que no se pueden actualizar). [3] : 10–11
Diseño
La tesis de Morrison explica cómo se aplicaron los principios de diseño en S-algol.
Tipos de datos
Los tipos de datos básicos o primitivos en S-algol son integer, real, boolean, file y string. (Más tarde se agregaron tipos de píxeles e imágenes para admitir gráficos de trama ). Integer , real y boolean son tipos comunes a la mayoría de los lenguajes de programación. El tipo de archivo es un flujo de entrada / salida (E / S) que permite escribir o leer objetos de datos. El tipo de cadena en muchos idiomas en ese momento se consideraba un tipo compuesto , pero incluirlo como tipo nativo hace que las operaciones básicas de concatenación, selección de subcadenas, longitud y las comparaciones (igual, 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
, *T
es el tipo de un vector con componentes de tipo T. Los límites del vector no son parte de su tipo pero 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 los cuales es 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 que sea aceptable. Esto no se aplica a los operadores infijos , ya que son azúcar sintáctico para funciones comunes y no forman parte del modelo semántico. [3] : 12-13
La tienda
Los vectores y las estructuras tienen todos los derechos y pueden asignarse como parámetros pasados, pero copiar en la asignación y cuando se pasan puede ser ineficaz para objetos grandes. Los vectores y las estructuras se tratan como punteros a los objetos, y los punteros se asignan y 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 verdaderos valores constantes , 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. Además, debe ser posible declarar una constante de cualquier tipo de datos, no solo los tipos escalares. [3] : 13
Estructuras de Control
S-algol es un lenguaje orientado a expresiones y las declaraciones son expresiones de tipo void . Como consecuencia, algunas estructuras de control son expresiones que producen valores .
Hay varias construcciones condicionales . La versión de dos alternativas del condicional es if
, donde las cláusulas pueden ser declaraciones o expresiones. Si son expresiones, deben tener el mismo tipo. El condicional de un brazo if
tiene el tipo nulo. [3] : 13 El uso de en do
lugar de else
en la declaración condicional evita la ambigüedad sintáctica colgando else . [2] : 20
La case
cláusula tiene un selector de cualquier tipo que se compara usando una prueba de igualdad contra expresiones del mismo tipo para encontrar la cláusula seleccionada. La cláusula case puede ser una declaración o una expresión, por lo que las cláusulas de resultado deben ser declaraciones (tipo void) o expresiones del mismo tipo. Las coincidencias se prueban en orden, por lo que se asemeja a las órdenes cautelosas de Edsgar Dijkstra sin el no determinismo . [3] : 14
Las declaraciones de bucle son en su mayoría convencionales. El for
bucle 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
y repeat
. La repeat
construcción proporciona la salida temprana o bucle "n-y-medio" [13] . [3] : 14
Abstracciones
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 usó el término secuela para la abstracción sobre secuenciadores, estos serían generalizaciones de goto y break . La abstracción más conocida en esta categoría es llamada-con-continuación-actual , pero no se entendería bien hasta algunos años después. S-algol no incluye goto o break, y no incluye abstracción sobre secuenciadores. [3] : 14
Declaraciones y parámetros
Cada objeto de datos en S-algol debe recibir un valor cuando se declara. Esto corresponde al paso de parámetros de llamada por 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 se rechazan, lo que es coherente 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 llamado por valor ya que el comportamiento es el mismo que el valor usado en el lado derecho de las asignaciones. [3] : 15
Cada declaración tiene un equivalente paramétrico. Se deben especificar todos los tipos de parámetros de procedimiento. Cualquier procedimiento pasado como parámetro tiene su tipo completo especificado (en contraste con Pascal) y lo mismo es cierto para una clase de estructura. [3] : 15
Modelo de entrada y salida
S-algol proporciona el file
tipo de datos para los flujos de E / S, read
y write
se definen varias variaciones de y para operar en los tipos básicos. Se espera que las implementaciones individuales amplíen estas sencillas facilidades según sea necesario. [3] : 15
Sintaxis concreta
Los lenguajes ALGOL han sido criticados por ser prolijos. 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 de forma explícita. [3] : 17
Aunque sería posible inferir el parámetro de procedimiento y los tipos de retorno examinando dónde se llama al procedimiento, S-algol requiere que se especifiquen los tipos de parámetro y 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 ALGOL requieren que todas las declaraciones vayan antes de las declaraciones en un bloque. En S-algol, las declaraciones se pueden mezclar con declaraciones porque todo debe declararse antes de que se use y no hay goto que permita saltar más allá de una declaración. [3] : 17
Ver también
- Napier88
Referencias
- ^ a b c d e Cole, AJ; Morrison, R. (1982), Introducción a la programación con S-algol , Cambridge University Press, ISBN 978-0-521-25001-6
- ^ a b c d e Davie, Antony JT; Ronald Morrison (1981), Brian Meek (ed.), Recursive Descent Compiling , serie Ellis Horwood en computadoras y sus aplicaciones, Chichester, West Sussex: Ellis Horwood, ISBN 978-0-470-27270-1
- ^ a b c d e f g h i j k l m n o p q r s t u v w x y z aa ab ac ad Morrison, R. (1979). Sobre el desarrollo de Algol (PhD). Universidad de St. Andrews . págs. 1-70.
- ^ a b c Morrison, Ron (1988) [1979], The S-algol Language Reference Manual (informe técnico CS / 79/1), Fife: University of St Andrews, págs. 1-53
- ^ Amman, Urs (1972), "El desarrollo de un compilador", Proc. En t. Simposio sobre informática , Holanda Septentrional, págs. 93–99
- ^ Wirth, Niklaus (abril de 1971), "Program development by stepwise refinement", Communications of the ACM , 14 (4): 221–227, doi : 10.1145 / 362575.362577 , hdl : 20.500.11850 / 80846
- ^ Bushell, SJ; Dearle, A; Brown, AL; Vaughan, FA (1994), "Uso de C como lenguaje de destino del compilador para la generación de código nativo en sistemas persistentes" (pdf) , en Atkinson, MP; Maier, D; Benzaken, V (eds.), Proc. 6º Taller internacional sobre sistemas de objetos persistentes (POS6), Tarascon, Francia , Talleres de informática, Springer-Verlag, págs. 164–183
- ^ Tennent, RD (1977), "Métodos de diseño del lenguaje basados en principios semánticos", Acta Informatica , 8 (2): 97-112, doi : 10.1007 / bf00289243
- ^ Landin, PJ (marzo de 1966), "Los próximos 700 lenguajes de programación", Comunicaciones del ACM , 9 (3): 157-164, doi : 10.1145 / 365230.365257
- ^ Strachey, C. (1966), "Towards a formal semantics", Lenguajes formales de descripción del lenguaje , Holanda Septentrional, págs. 198-220
- ^ Hoare, CAR (1975), "Estructuras de datos recursivas" , International Journal of Computer and System Sciences , 4 (2): 105-132, doi : 10.1007 / bf00976239
- ^ Hoare, CAR (1972), "Una nota sobre la declaración for", BIT , 12 (3): 334–341, doi : 10.1007 / bf01932305
- ^ Edsgar Dijkstra (1973). Comunicación personal a Donald Knuth , citada en Knuth, D. (1974), "Programación estructurada con go to Statements" (PDF) , Computing Surveys , 6 (4): 261–301, CiteSeerX 10.1.1.103.6084 , doi : 10.1145 / 356635.356640 , archivado desde el original ( PDF) el 2013-10-23
enlaces externos
- Implementaciones y dialectos de Algol 60 , Computer History Museum Software Preservation Group
- S-algol persistente