Download evolución histórica - Programación Funcional

Lenguajes de programación: Motivación
3º Ingeniería Informática
Francisco José Serón Arbeloa
Juan Antonio Magallón
Sandra Baldassarri
DEPARTAMENTO DE
INFORMÁTICA E
INGENIERÍA DE SISTEMAS
CENTRO POLITÉCNICO
SUPERIOR
UNIVERSIDAD DE
ZARAGOZA
"Lenguajes de Programación"
INTRODUCCIÓN
INTRODUCCIÓN
El propósito de un lenguaje es sencillamente el de transferir significado.
Confucio
Los lenguajes de programación son el corazón de la
Informática, ya que son las herramientas que se usan
para comunicarse no sólo con el computador sino con
la gente.
El desafío que representa el diseño de un lenguaje es
el de “juntar de manera adecuada” diferentes ideas y
características, que permitan al programador la
expresión clara de los algoritmos.
Este conjunto de notas de clase sobre los lenguajes de
programación, presentan los conceptos que subyacen
en los lenguajes de programación y la mayor parte de
los paradigmas que usan estos conceptos en forma
diferente.
Las notas de clase se han agrupado en cuatro
bloques. En este primer bloque se transcribe de forma
íntegra la conferencia impartida por el profesor
Ricardo Peña Marí, en la Universidad de Zaragoza, el
19 de Marzo de 1996 durante el ciclo de conferencias
Jetai’96.
Consideramos este documento de interés suficiente
como para motivar al alumnado en el estudio de los
diferentes aspectos relacionados con los Lenguajes de
Programación.
Los autores
"Lenguajes de Programación"
EVOLUCIÓN HISTÓRICA DE LA
PROGRAMACIÓN DE COMPUTADORES
EVOLUCIÓN HISTÓRICA
DE LA PROGRAMACIÓN DE
COMPUTADORES.
Ricardo Peña Marí
Univ. Complutense de Madrid
Evolución histórica de la programación de computadores
Ricardo Peña Marí
Profesor Titular de Lenguajes y Sistemas Informáticos
Departamento de Informática y Automática
Universidad Complutense de Madrid
e-mail: ricardo@dia.ucm.es
Marzo de 1996
En este trabajo se realiza un recorrido por los
hitos más relevantes de la historia de la
programación de computadores. Se trata,
obviamente, de una visión subjetiva -e incluso
personal- de la misma. Se han omitido hechos
que para otras personas pueden resultar
importantes y se han resaltado otros que quizás
a algunos no les parezcan merecedores de tal
relieve. Comenzando por los hechos más lejanos
en el tiempo se dedica después una sección a
referir el surgimiento y la evolución posterior de
cada uno de los cinco paradigmas principales de
la programación: el imperativo, el orientado a
objetos, el concurrente, el lógico y el funcional.
Hasta donde llega el conocimiento del autor, se
han tratado de señalar las principales líneas de
investigación y el estado actual de cada
paradigma.
tan pragmáticos como el del capital resultante
de un préstamo a interés compuesto y otros
similares. Terminaban con la siguiente
inscripción premonitoria:
". . . y éste es el procedimiento. "
Los egipcios, griegos y romanos enriquecieron
notablemente la colección de algoritmos con sus
avances en geometría y aritmética. Uno de los
más famosos es el algoritmo de Euclides (300
A.C.) para el cálculo del máximo común
divisor.
Pero el sueño del hombre ha sido siempre idear
máquinas que trabajasen para él, y los procesos
mentales de cálculo -muchas veces tediosos y
sujetos a error humano- no podían ser la
excepción. La primera calculadora mecánica
data de 1641, y se debe a Blaise Pascal. La
construyó a la edad de 19 años para ayudar a su
padre en la voluminosa contabilidad necesaria
para la recaudación de impuestos. La máquina
de Pascal sólo era capaz de sumar y restar.
La primera máquina realmente programable fue
la Analythical Engine de Charles Babbage,
construída en 1833. Era totalmente mecánica y
tenía unidades semejantes a las de un
computador actual: una unidad aritmética -the
mill-, una memoria formada por ¡50.000! ruedas
dentadas, y unos mecanismos de transmisión
para bombear datos y resultados entre ambas
unidades. Aunque nunca llegó a funcionar
completamente, tuvo un efecto importante para
la programación (descontando el efecto lateral,
importante sólo para su creador, consistente en
llevarle a la ruina): la de obligar a plantearse por
vez primera la necesidad de describir algoritmos
para ser ejecutados por una máquina. Había
nacido la programación.
El "software" de la citada máquina consistía en
secuencias de tarjetas perforadas donde estaban
descritos los algoritmos. Éstos usaban ya el
concepto de bucle, implementado mediante la
lectura repetida de las mismas tarjetas. La
programadora de los mismos era Ada Augsusta,
Condesa de Lovelace, e hija
1 Los tiempos remotos
La programación se ocupa de resolver
problemas algorítmicos. Un algoritmol se puede
definir como un conjunto de reglas precisas, que
aplicadas sistemáticamente a partir de los datos
iniciales, producen, en un número finito de
pasos, el resultado deseado. Las reglas han de
ser tan precisas y elementales que puedan ser
aplicadas por una máquina.
Es ya un tópico afirmar que los algoritmos
preceden históricamente a los computadores. La
regla de Cramer para el cálculo de un
determinante o método de reducción de Gauss
para resolver sistemas lineales de ecuaciones
son ejemplos de algoritmos, y fueron inventados
respectivamente en los siglos XVIII y XIX. Los
primeros algoritmos conocidos proceden de la
antigua Mesopotamia, datan aproximadamente
del 3.000 A.C., y estaban escritos en tablillas de
arcilla. Su propósito era la realización de
cálculos
---------------------------------------------------------1 Palabra formada a partir del nombre del
matemático árabe del siglo IX Mohammed ibn
Musa Abu Djefar Al-Khwarizmi.
1
que determina los cambios de estado y las posibles alteraciones en el contenido de la memoria
lineal. Con este dispositivo, mostró que era
posible calcular muchas de las funciones
usuales de los naturales en los naturales. Quedó
también claro que existían numerosas funciones
no calculables por su máquina, entre ellas el
famoso problema de parada: no existe una
máquina que decida si otra máquina de Turing
arbitraria se detendrá ante una entrada dada.
Más adelante, se propusieron versiones
especializadas de las máquinas de Turing con
diferentes "necesidades" de memoria y se
estableció una jerarquía de máquinas con
diferentes potencias de cálculo. Esta jerarquía se
correspondía -en el sentido de aceptar frases
válidas de los mismos- con las categorías de
lenguajes formales establecidas por el lingüista
Noam Chomsky en los años 50 [Cho56]. La
llamada tesis de Turing (más adelante, llamada
de Church-Turing) consiste en afirmar que el
conjunto de las funciones computables coincide
exactamente con el de las funciones calculadas
por las máquinas de Turing.
Obviamente, tal conjetura no puede ser probada
sin una caracterización previa de las funciones
computables, por lo que puede tomarse como
una definición de las mismas. En apoyo de que
esta definición representa la intuición adecuada
de computabilidad, está el hecho de que otros
sistemas
de
cálculo
desarrollados
independientemente llegaron a nociones de
computabilidad
que
se
demostraron
equivalentes a la definida por Turing. Entre
ellos se encuentra la teoría de funciones
recursivas y el cálculo lambda.
Éste último fue desarrollado por A. Church
entre 1932 y 1941 [Chu41]. El objetivo de
Church era capturar el aspecto computacional
de las funciones. En vez de usar la definición
tradicional de las mismas como conjuntos de
pares dato-resultado, su interés se centraba en el
proceso de transformación desde el dato de
partida hasta el resultado de llegada. En su
versión más simple, el cálculo lambda consiste
en una gramática de términos y en unas reglas
de
transformación
entre
términos.
Intuitivamente, estos términos representan
funciones. Una característica importante de este
cálculo es la posibilidad de que las funciones
puedan aplicarse a sí mismas. Gracias a ello, se
pueden definir funciones recursivas sin usar
explícitamente la recursividad. Pese a estas
propiedades, no aparecen paradojas o
inconsistencias. La tesis de Church (o de
Church-Turing) consiste en afirmar que las
funciones computables son exactamente
aquellas que pueden ser definidas mediante el
cálculo lambda. Turing probó en 1937 [Tur37]
la equivalencia entre este cálculo y sus
máquinas, mostrando que cada uno podía
simular al otro.
Las máquinas de Turing han dado lugar a una
rama de la informática teórica conocida como
Teoría
del poeta Lord Byron, que ha pasado a la
posteridad como la primera programadora de la
historia. El nombre Ada, dado a un lenguaje de
programación de los 80 (ver la Sección 3), hace
honor a este hecho.
Las
siguientes
máquinas
programables
corresponden ya a los años 40 del presente
siglo. Sus vicisitudes no forman propiamente
parte de la historia de la programación sino más
bien de la de los computadores. La
programación se realizaba, primero en lenguaje numérico, también llamado lenguaje
máquina, y más adelante, en lenguaje simbólico
o ensamblador. A los programadores de esos
años se les llamaba codificadores, quizás para
indicar que las verdaderas protagonistas eran las
máquinas y no los programas. En aquellos días,
los programadores entraban respetuosamente en
los templos donde moraban las máquinas -la
ENIAC de 1946, ocupaba todo un edificiopertrechados tan sólo de una pequeña cartulina
en la que se describía el lenguaje de "la divinidad". Irónicamente, la situación se ha
invertido en la actualidad: hoy el computador
ocupa un pequeño rincón de la mesa, mientras
que los manuales para utilizar los numerosos
programas que contiene llenan varios estantes.
Hay, sin embargo, dos desarrollos matemáticos
-todavía anteriores a la aparición de los
primeros computadores- que sí son relevantes
para la historia de la programación: la máquina
de Turing y el cálculo lambda.
A comienzos de siglo, muchos matemáticos
pensaban que quizás todos los resultados de las
matemáticas podrían obtenerse a partir de un
reducido conjunto de axiomas y de reglas de
inferencia. El problema consistía en dar con
dicho conjunto de axiomas. Si se lograba tal
empeño, todo teorema podría obtenerse de
modo mecánico aplicando una secuencia finita
de pasos de deducción. El teorema de incompletitud de K. Gödel, en 1931, deshizo
bruscamente tales esperanzas: cualquier sistema
de axiomas lo suficientemente rico como para
incluir los números naturales y sus operaciones
de suma y producto admitía fórmulas que no
podían ser demostradas ni refutadas empleando
las reglas de deducción del mismo.
La siguiente pregunta obvia fue: ¿Cuáles son los
sistemas de axiomas donde cabe esperar la
propiedad de demostración automática? Se
demostró que la pregunta era equivalente a esta
otra: ¿Cómo se caracteriza el conjunto de las
funciones efectivamente computables?
Alan Turing propuso en 1936 [Tur36] tal
caracterización por medio de la máquina que
lleva su nombre. Se trata de una máquina
conceptual cuya evolución está gobernada por el
contenido de una memoria lineal de símbolos
potencialmente infinita, una memoria finita de
estados internos, y una función de transición
2
de la Computabilidad. Por su parte, el cálculo
lambda constituye la base teórica del paradigma
de programación funcional. Ambos desarrollos
han sido fundamentales para comprender mejor
cuáles son los límites de lo que es realizable
mediante un computador.
obsoleto. Pero el hecho de ser el primer lenguaje
de alto nivel y haber sido promocionado por la
primera compañía mundial de computadores,
ocasionó que se realizaran ingentes inversiones
en desarrollo de software en dicho lenguaje,
haciendo la pervivencia del mismo mucho más
larga de lo deseable, e impidiendo que lenguajes
más modernos tomaran el relevo.
Las principales aportaciones de Fortran pueden
resumirse como sigue:
2 Los primeros lenguajes de alto nivel
FORTRAN
La verdadera historia de la programación, tal
como la concebimos hoy, comienza con el
desarrollo de los lenguajes de alto nivel. El
primero que merece tal nombre es el lenguaje
FORTRAN
(acrónimo
de
FORmula
TRANslating system), desarrollado por John
Backus y sus colaboradores en IBM entre 1954
y 1957 [IBM57].
Es de resaltar que el ambiente predominante en
aquella época era bastante contrario a este
desarrollo. Backus tuvo que luchar contra el
escepticismo de sus colegas y la indiferencia de
los grupos de usuarios de IBM, que estaban
convencidos del fracaso del proyecto. Los
programadores del momento utilizaban lenguaje
ensamblador con muy pocas ayudas mecanizadas, quizás debido a que los computadores se
concebían como calculadoras exclusivamente
numéricas y no como procesadores de símbolos.
Fueron tareas realmente meritorias, primero
concebir el lenguaje, y después desarrollar el
compilador. Ello llevó tres años al equipo de
Backus el cual, en ciertos momentos, llegó a
alcanzar una docena de personas. También es
meritoria la apuesta de IBM por tal desarrollo.
Backus convenció a sus superiores de que el
nuevo lenguaje ahorraría mucho esfuerzo de
programación. En esa época tan temprana, ya se
comenzaba a intuir que los costes de
programación
terminarían
por
ser
predominantes. El objetivo principal de Backus
era reducir estos costes, pero era consciente de
que el nuevo lenguaje no debería de ser
significativamente más lento que la codificación
manual porque entonces los programadores lo
rechazarían.
La historia dio la razón a Backus y a la apuesta
de IBM. De hecho, Fortran contribuyó en gran
manera al éxito de IBM que llegaría más tarde a
ser la compañía lider en ventas de
computadores. Fortran se convirtió en el
lenguaje estándar para la programación
numérica y se desarrollaron compiladores para
todas las máquinas existentes. De la versión I,
se pasó enseguida a la II, la III y la IV. Los
compiladores de esta última estuvieron
disponibles en 1962. No obstante, la
preocupación por la eficiencia ha dejado su
impronta en el lenguaje, que hoy es a todas
luces
. Lenguaje algebraico con notación muy cercana
a la matemática para las expresiones.
. Aritmética entera y de coma flotante.
. Estructura de datos array con varias
dimensiones y con notación matemática.
. Subrutinas y procedimientos. Si bien éste era
un concepto conocido, la sintaxis escogida en
Fortran para su llamada con parámetros era muy
intuitiva.
. Instrucciones declarativas COMMON y
EQUIVALENCE para compartir y estructurar
zonas de datos.
. Instrucciones de iteración y ramificación sin
contrapartida inmediata en lenguaje máquina:
DO, IF aritmético, IF calculado.
. Entrada/salida con formato. Esta facilidad
liberaba al programador de una de las tareas
más tediosas y más dependientes de la máquina.
Pero la aportación principal es, como se ha
dicho, la de ser un lenguaje de alto nivel, es
decir, la de permitir programar en una notación
independiente de la máquina. Esto tuvo la
consecuencia inmediata de incorporar al campo
de la programación a multitud de personas que
no eran especialistas en un computador
concreto, ni deseaban involucrarse en los
detalles internos de una máquina particular.
ALGOL 60
El éxito de Fortran abrió el camino al desarrollo
de nuevos lenguajes, y apenas empezada su
andadura, los grupos de usuarios de distintas
casas fabricantes -IBM incluida- instaron a la
joven Association for Computer Machinery
(ACM) a que promoviera la definición de un
lenguaje de alto nivel independiente de los
fabricantes que permitiera una programación
portable entre máquinas. Ésta nombró un comité
con participación de la industria (IBM, Rand
Corporation, Westinghouse, ...), los institutos de
investigación (Massachusetts Institute of
Technology, en adelante MIT) y las
universidades, cuya primera reunión
3
aparece no son significativos, y son eliminados
en la fase
de análisis léxico. Introducción del símbolo ‘;’ y
de las construcciones parentizadas begin end
para separar sintácticamente las instrucciones.
tuvo lugar en 1958. En paralelo, en Europa ya
había comenzado un movimiento en el mismo
sentido patrocinado por la Asociación Alemana
de Matemáticas y Mecánica (GAMM). El
comité europeo estaba presidido por Fritz L.
Bauer y posteriormente se incorporó Peter Naur.
En el norteamericano, figuraban el propio J.
Backus (IBM), y John McCarthy (MIT),
posteriormente creador del lenguaje LISP.
Reunidos conjuntamente alumbraron una
propuesta que fue llamada ALGOL 58 (de
ALGOrithmic Language) que, tras varios
refinamientos, se convirtió en el lenguaje Algol
60 [Nau60, Nau63].
Había muchas contradicciones entre el equipo
europeo y el norteamericano. Los primeros
ponían el acento en la solidez y claridad del
lenguaje, mientras que los segundos lo ponían
más en la flexibilidad de las construcciones. Los
europeos querían un lenguaje utilizable a corto
plazo, mientras que los norteamericanos lo
veían más como un estándar a medio plazo que
sirviera de referencia, pero que no les impidiera
utilizar los lenguajes en cuyo desarrollo estaban
involucrados. A pesar de estos problemas, el
lenguaje producido reunió de un modo simple y
elegante la mayoría de los conocimientos del
momento y resultó de gran calidad. Marcó un
hito en la historia de los lenguajes y su
influencia en los lenguajes posteriores fue muy
superior a la de Fortran. Durante una larga
época, el término Algol-like se empleó para
caracterizar la mayor parte de los lenguajes que
se diseñaban. Algol 60 se convirtió en el
vehículo preferido para la publicación de
algoritmos, gracias entre otras razones al apoyo
de ACM y de la revista Algol creada en Europa
para su difusión. Sin embargo, no llegó a
difundirse en la industria debido a que las
compañías fabricantes no pusieron especial
empeño en el desarrollo de compiladores.
Contemplaban Algol 60 como una notación
elegante, pero ineficiente de implementar y
prefirieron ocuparse de sus propios lenguajes.
En particular, IBM estaba en esos momentos
muy interesada en promocionar Fortran.
Son muchas las aportaciones de Algol 60,
algunas de las cuales se dan hoy por supuestas
en el desarrollo de cualquier lenguaje. Un
ejemplo de ello es la sintaxis BNF (Backus and
Naur Form) desarrollada por dichos autores
para expresar su gramática. Esta notación
sistemática dio lugar a un renovado interés por
los lenguajes formales, a muchas de las técnicas
de análisis sintáctico que hoy conocemos, y a la
construcción de generadores de analizadores, es
decir, de analizadores parametrizados por una
gramática. Otras aportaciones no menos
relevantes de Algol 60 fueron las siguientes:
· Primer lenguaje con estructura de bloques.
Introduce las reglas de visibilidad hoy tan
habituales: el ámbito de los identificadores es
local al bloque en que están declarados. Son
visibles los identificadores locales al bloque y
los de los bloques circundantes que no
colisionen con identificadores más internos en
la jerarquía de anidamiento. Los bloques
permiten la declaración de variables temporales
en medio de un texto ejecutable: en cualquier
punto del texto puede iniciarse un nuevo bloque
y declarar variables locales al mismo.
· Primer lenguaje con disciplina de tipos. A diferencia de Fortran, todas las variables han de
ser declaradas, junto con su tipo, antes de ser
nombradas. El compilador comprueba que cada
variable se usa de modo consistente con su tipo.
·
Primer
lenguaje
con
instrucciones
estructuradas de control de flujo. En particular,
las instrucciones for e if then else son
aportaciones de Algol 60.
· Primer lenguaje en introducir la recursividad,
si bien los autores tuvieron muchas dudas antes
de incluirla debido sobre todo a que no se
conocía un modo eficiente de implementarla.
· Primer lenguaje en introducir los pasos de
parámetros por valor y por nombre. Este último
ha sido abandonado en posteriores lenguajes imperativos debido a sus complejos efectos laterales.
· Límites de los arrays decididos en tiempo de
ejecución. Esto conlleva la asignación dinámica
de memoria al dar comienzo a un bloque, y la
subsiguiente liberación de la misma al
abandonar su ejecución.
COBOL
El lenguaje COBOL, acrónimo de "COmmon
Business Oriented Language", se gestó también
a finales de los 50, entre 1959 y 1961 [DoD60,
DoD61]. Respondía a la necesidad de contar
con un lenguaje adaptado a la programación de
gestión, que se alejara de la apariencia
algebraica de los lenguajes numéricos, y que
pusiera el énfasis en los aspectos de descripción
de datos y de manipulación de ficheros.
Su desarrollo contó con el apoyo financiero y
político del Departamento de Defensa
Norteamericano (DoD) interesado en tener un
lenguaje de dichas
. Primer lenguaje con formato libre: los blancos
o fines de linea adicionales al primero que
4
de gestión. Se difundió rápidamente y fue
convertido en estándar ANSI en 1968, 1974 y
1985. El énfasis en la portabilidad hizo que
CODASYL se erigiera en vigilante de su
evolución para evitar la proliferación de
versiones incompatibles. Ello dio una gran estabilidad al lenguaje. Este hecho, junto con el
apoyo decidido del DoD (ningún contrato con el
mismo era aceptado si la compañía ofertante no
disponía de un compilador Cobol), hicieron que,
como en el caso de Fortran, su pervivencia fuera
más allá de los límites razonables. Todavía en la
década de los 80, Cobol seguía siendo el
lenguaje de programación más usado.
características. Estimulado por la industria, puso
en marcha el comité CODASYL2 que coordinó
los trabajos. Participaban las empresas más
importantes (Sperry Rand, Burroughs, IBM,
GE, Honeywell Bull, etc.), representantes del
DoD y de las instituciones de estándares. La
presencia de la universidad era meramente
simbólica. Persona importante en dicho comité
fue Grace M. Hopper (Sperry Rand) autora del
lenguaje
FLOW-MATIC
-y
de
sus
compiladores- en el cual Cobol se inspiró
bastante.
Una característica original de Cobol, sobre la
que había unanimidad entre sus diseñadores y
que sin embargo no ha tenido continuadores, es
el uso de palabras inglesas para construir todas
las expresiones e instrucciones del lenguaje,
incluidas las operaciones aritméticas (que en
Cobol
reciben
los
nombres
ADD,
SUBSTRACT, etc.), dando a los programas un
aspecto verboso muy peculiar. La razón de esta
decisión de diseño era hacer los programas
comprensibles a programadores y ejecutivos sin
una especial formación matemática. Es dudoso
que tal objetivo se consiguiera. En cambio, no
es dudoso que muchos programadores de Cobol
deploran esta característica, y que se han
desarrollado preprocesadores que permiten
trabajar con una notación más abreviada.
Más influencia posterior ha tenido su énfasis en
independizar la descripción de los datos de la de
los procedimientos, y en hacer aquélla lo más
independiente posible del hardware subyacente.
Así, un programa Cobol tiene cuatro apartados:
LISP
El origen de LISP (LISt Processing language) es
muy diferente. En este caso se trata del empeño
de una persona, John McCarthy, del MIT, en
conseguir un lenguaje apto para aplicaciones de
inteligencia artificial. Al comenzarse la
gestación de Lisp (1957) el único lenguaje de
alto nivel era Fortran y ni siquiera estaba
finalizado su compilador. Fortran era
inadecuado para el tratamiento simbólico y para
la creación de estructuras de datos dinámicas.
Ello, junto a la ausencia de recursividad, que
McCarthy estimaba imprescindible, finalmente
le decidieron a plantearse el desarrollo de un
nuevo lenguaje. Un lenguaje previo, IPL,
especie de macroensamblador interpretado
desarrollado por el Carnegie Institute of
Technology, había demostrado la factibilidad de
usar listas heterogéneas para representar
cualquier información simbólica en la memoria
del computador. También habían implementado
un gestor de la memoria dinámica que
proporcionaba celdas libres para la construcción
de tales estructuras de datos. Estas ideas fueron
incorporadas a Lisp [MAE+62]. El primer
intérprete estuvo disponible en 1960.
Las aportaciones de Lisp son conceptualmente
comparables, aunque de distinto signo, a las de
Algol 60. La influencia posterior del lenguaje ha
sido profunda y el uso de sus dialectos notoriamente, el del lenguaje Scheme, aparecido
en 1975 (ver p.e. [SF89])- ha pervivido hasta la
actualidad. Estas aportaciones pueden resumirse
como sigue:
l. La identification division, que suministra
comentarios explicativos acerca del programa y
sus autores.
2. La environment division, que proporciona
información dependiente de la máquina y, en
particular, define la correspondencia entre los
ficheros externos y las descripciones internas de
los mismos.
3. La data division, que describe a nivel lógico
la estructura de los ficheros utilizados por el
programa.
4. La procedure division, que describe los
algoritmos.
El sublenguage de descripción de datos puede
verse como la semilla cuyo fruto serían los
lenguajes posteriores de descripción y consulta
de bases de datos. La estructura record es
también una aportación de Cobol a la
posteridad.
Cobol representó muy bien el consenso
alcanzado por las empresas de la época para
conseguir un lenguage portable para sus
necesidades de programación
----------------------------------------------------------
. Demuestra en la práctica que la recursividad es
suficiente para programar cualquier función.
. Trata las expresiones de datos y de programa
de modo uniforme. Las funciones se pueden pasar como parámetro y evaluarse posteriormente.
Ello proporciona la primera notación de orden
superior de la historia de los lenguajes.
. Esa misma facilidad permite evaluar
programas completos dando lugar así a un
intérprete. Lisp
2COmmittee on DAta SYstem Languages
5
es también el primer lenguaje interpretado de la
historia.
cadenas de caracteres), APL (procesamiento de
matrices numéricas), GPSS (simulación) o los
derivados de Lisp (tratamiento de símbolos).
Sin embargo, no existían criterios claros para
comparar la bondad relativa de tales propuestas.
La programación científica se había adherido a
Fortran, la empresarial a Cobol y cada área
específica de aplicación disponía de su propio
lenguaje. Empezó a tomar forma la idea de que
sería deseable un lenguaje que sirviera "para
todo". Éste debería disponer de una buena
notación matemática para la expresión de
cálculos numéricos, de suficientes facilidades
para la descripción de datos, una entrada/salida
versátil y eficiente, y mecanismos para la
creación de estructuras dinámicas semejantes a
las de Lisp. Adicionalmente, debería tener
algunas de las características de los lenguajes
especializados, tales como el tatamiento de
cadenas de caracteres o facilidades para la
multiprogramación,
concepto
surgido
a
mediados de la década.
Conviene enmarcar esta búsqueda de un
lenguaje "más potente" en los avances en
arquitectura de computadores que estaban
teniendo lugar simultaneamente. Estamos en
1965. Empiezan a surgir los primeros circuitos
integrados (tan solo unas docenas de transistores
por chip), las memorias de ferritas alcanzan
tamaños de 512 K-octetos y los tiempos de ciclo
se sitúan en torno a 1/4 de microsegundo. Hace
unos años que se ha inventado la interrupción
para des-sincronizar la UCP de los periféricos,
cuatro órdenes de magnitud más lentos que
aquella.
Con
ella
ha
surgido
la
multiprogramación y todos los problemas
derivados de la concurrencia. Se abordan
desarrollos de decenas miles de instrucciones, e
IBM está a punto de lanzar su serie 360.
Estamos entrando -según el esquema del
comienzo de esta sección- en la "fase de terror".
Algo no funciona en el mundo del software. Los
desarrollos no sólo conllevan un esfuerzo
desmesurado, sino que los programas
resultantes están plagados de errores. El propio
sistema operativo de la serie 360 es un ejemplo
de ello: 5.000 personas-año costó su desarrollo
y mantenimiento posterior, y el número de
errores detectados se mantenía estable de cada
versión a la siguiente. En este contexto, se
aborda el diseño de dos nuevos lenguajes: PL/I
y Algol 68.
El primero de ellos, en realidad contribuyó a la más adelante- llamada "crisis del software". Su
promotor fue IBM y su objetivo ser el lenguaje
base para la serie 360. Esta familia estaba
dirigida tanto al mercado científico como al
empresarial y, por tanto, el lenguaje de
programación había de satisfacer a ambas
comunidades. Su definición y desarrollo se
extendieron desde 1964 a 1966 y en ellas
participaron usuarios e implementadores de
Fortran y Cobol.
. También es pionero en la incorporación de un
mecanismo automático de recolección de
basura para reutilizar la memoria ocupada por
expresiones que ya no se van a necesitar.
. Utiliza la composición de funciones como mecanismo ordinario para la creación de funciones
más complejas. También aporta una expresión que no una instrucción- condicional. Ello hace
que un subconjunto de Lisp sea un lenguaje
funcional puro. Así, Lisp es una de las semillas
que, tras una larga gestación (ver la Sección 7),
da lugar a un nuevo paradigma de
programación.
Se ha especulado mucho sobre la influencia del
cálculo lambda en la gestación de Lisp. El
propio McCarthy reconoce en [McC78] que esa
influencia fue pequeña, prácticamente limitada a
la sintaxis empleada para las funciones
anónimas -la abstracción lambda λx.e se expresa
como (lambda(x)e) en Lisp. La utilización del
cálculo lambda como fundamento semántico de
los lenguajes funcionales vendría mucho
después.
La crisis
Un texto muy difundido en las empresas asegura
irónicamente que las fases de un proyecto
informático
son
aproximadamente
las
siguientes:
l. Comienzo del proyecto. Realización de
estimaciones irreales.
2. Fase de optimismo desmesurado.
3. Fase de terror.
4. Fracaso del proyecto.
5. Búsqueda implacable de culpables.
6. Premio a estos últimos y castigo de los
inocentes.
Si tuviéramos que aplicar este esquema al
desarrollo de los lenguajes de programación,
diríamos que la década de los 60 corresponde
sin duda a la fase de "optimismo desmesurado".
En estos años se desarrollan docenas de
lenguajes sin más justificación que la de
experimentar nuevas ideas. Ideas que surgían
sin cesar en empresas y universidades. Quizás el
entorno social (éxito sin precedentes de la
música pop, movimientos pacifistas, de
liberación de la mujer, de contestación juvenil,
etc.) era propicio al surgimiento de las mismas.
Fue una época de gran creatividad. Algunos de
estos lenguajes, como JOVIAL, Algol-W,
BASIC, etc., eran de propósito general. Otros
eran de propósito específico, como SNOBOL
(tratamiento de
6
El lenguaje resultante incluía características de
ambos, y algunas otras novedosas como el
manejo de excepciones o las primitivas del tipo
fork y join para lanzar procesos concurrentes.
También suministraba punteros para la creación
de estructuras de datos dinámicas.
fue obra del grupo de trabajo WG 2.1 de la
IFIP,3 y su principal objetivo de diseño era la
ortogonalidad. Algol 68 constaba de muy pocos
elementos primitivos pero se podían combinar
entre sí casi sin restricciones. Por ejemplo,
disponía de cinco tipos básicos y de cinco
modos distintos de formar tipos compuestos a
partir de tipos más simples: arrays , structures
(registros), uniones (equivalen a registros con
variantes), punteros a elementos de un tipo m, y
funciones de un tipo m en un tipo n. Cualquier
combinación de estas construcciones era
aceptable. Así, Algol 68 buscaba la generalidad
por un camino distinto al de PL/I. Sin embargo,
el lenguaje resultó bastante incomprensible y
muy dificil de implementar. Su impacto en la
programación del momento fue mínimo.
Con estos dos desarrollos, hemos alcanzado la
fase de "fracaso del proyecto". Ahora se trataba
de buscar a los culpables de tal situación.
Quizás la aportación de Algol 68 a la historia de
los lenguajes fue ésta: colaborar en la búsqueda
de los culpables. Algunos investigadores que
han marcado la década de los 70, tales como
C.A.R. Hoare y N. Wirth, se apartaron del WG
2.1 ocupado en la definición de Algol 68 y
crearon un nuevo grupo, el WG 2.3, sobre
metodología de la programación. Pensaron que
se imponía un periodo de reflexión antes de
abordar el diseño de nuevos lenguajes. Éstos
deberían reflejar una metodología para la
concepción de programas y no a la inversa. Pero
esa metodología estaba por hacer. Su historia se
relata en la siguiente sección.
El principal problema de PL/I era su volumen y
la falta de ortogonalidad de sus caracteríticas.
En realidad era una acumulación de
construcciones de muy diverso tipo y su
interacción no estaba clara en muchos casos. En
palabras posteriores de E. W. Dijkstra [Dij72a]
"usar PL/I es como pilotar un avion con 7.000
mandos distintos". Estas ambigüedades y
volumen retrasaron mucho la construcción del
compilador. Los diseñadores, conscientes de
que sería difícil para un programador controlar
simultaneamente todos los rincones del
lenguaje, tomaron una decisión de diseño que el
tiempo demostró fue un error: la inclusión de
opciones por defecto allí donde el programador no especificaba nada. Así, se podían
mezclar libremente variables de muy diverso
tipo en las expresiones sin que el compilador
señalara esto como un error (aunque en algunos
casos pudiera ser simplemente una mala
transcripción mecanográfica). El compilador
tenía opciones por defecto para asignar un tipo a
la expresión y para hacer las conversiones
implícitas oportunas, muchas veces para mayor
sorpresa del programador. En ese sentido, PL/I
representa un paso atrás respecto a la disciplina
de tipos de Algol 60.
PL/I no tuvo éxito entre sus potenciales usuarios
a pesar de los esfuerzos de IBM por difundirlo.
A petición de éstos, tuvo que desarrollar y
soportar compiladores de Fortran y Cobol para
la serie 360. Quizás el único impacto positivo de
PL/I en la historia de los lenguajes -aparte del
consabido consuelo de que "de los errores
también se aprende"- fue el esfuerzo por definir
formalmente su semántica. El laboratorio de
IBM en Viena desarrolló el llamado Vienna
Definition Language, VDL [Weg72], lenguaje
formal para expresar el significado de las
construcciones sintácticas de un lenguaje
mediante su interpretación en una máquina
abstracta. Este desarrollo dio lugar a toda una
línea de trabajo en semántica operacional que
posteriormente evolucionó hacia la conocida
como semántica denotacional [SS71]. Éste es
hoy el modo estándar de definir la semántica de
los lenguajes. De la complejidad de PL/I da idea
el hecho de que su semántica formal necesitó
400 páginas escritas en VDL [LW69]. En
contraste, la semántica formal de Algol 60 en el
mismo lenguaje ocupa tan solo 50 páginas.
3 La programación imperativa
El estilo de programación que se estaba
buscando tenía como objetivo que el
programador fuera dueño de su herramienta, el
lenguaje, y no al revés. Ello implicaba hacer uso
tan solo de construcciones que pudieran ser
comprendidas perfectamente y que permitieran
un razonamiento riguroso acerca de la
corrección de los programas con ellas
construidas. Los primeros pasos en esa
dirección los dieron Hoare en [Hoa69] , Dijkstra
en [Dij68c] y [Dij72b], y Wirth en [Wir71a].
El primero de ellos, con antecedentes en
[McC62, Nau66, Flo67, Dij68a], establece los
axiomas fundamentales para la verificación
matemática de los programas. Por primera vez
se disponía de un conjunto de leyes que
permitían razonar con todo el rigor deseado
sobre la corrección de un programa escrito en
un lenguaje de alto nivel. Más aún, este
razonamiento era independiente de cualquier
implementación del lenguaje y de cualquier
computador en que se ejecutara el programa. Es
decir, los programas poseían un
----------------------------------------------------------
El segundo de los lenguajes de propósito
general desarrollado al final de la década, Algol
68 [Wij69] ,
3International
Processing
7
Federation
for
Information
significado por sí mismos, al margen de las
máquinas que los ejecutaban. Estas leyes han de
ser consideradas de trascendental importancia.
Al igual que la aritmética, la mecánica o el
electromagnetismo se apoyan en un conjunto
reducido de axiomas, por primera vez la
programación disponía de un fundamento
similar. El propio Hoare establece esta
comparación en [Hoa84].
La verificación formal de programas se
desarrolla notablemente durante la década,
impulsada sobre todo por E. W. Dijkstra. Su
trabajo [Dij75] y su libro posterior [Dij76] son
todavía hoy de obligada lectura. En ellos se
propone -y se ejercita mediante numerosos
ejemplos nada triviales- la técnica de derivación
formal, consistente en aplicar la verificación de
un modo más cómodo y productivo que a
posteriori, es decir, con el programa ya
construido. Primero, el programador establece
los predicados que han de satisfacerse en ciertos
puntos del programa, y muy particularmente los
invariantes de los bucles, y luego "deduce"
sistemáticamente un programa que los satisface.
De este modo, los programas resultantes son
correctos por construcción. Adicionalmente, el
lenguaje definido en [Dij75] introduce el no
determinismo en la programación secuencial,
concepto harto extraño para tan temprano
momento. Además de mejorar la presentación
de algunos algoritmos secuenciales, las
construcciones no deterministas de [Dij75] van
a tener una profunda influencia en los lenguajes
concurrentes del final de la década (ver la
Sección 5).
Complementarios de las técnicas de verificación
son el desarrollo de programas mediante
refinamientos sucesivos [Wir71a, Dij72b] y el
uso exclusivo de la composición secuencial, la
alternativa if then else y la iteración while,
como instrucciones para dirigir el flujo de
control de un programa [Dij68c, Dij72b].
Pueden utilizarse otras estructuras similares
(p.e. repeat, case) siempre que tengan un sólo
punto de entrada del control y un sólo punto de
salida. El trabajo [BJ66] había dejado
establecido que toda función computable podía
construirse con dichas estructuras. En definitiva,
el go-to no era imprescincible, y en cambio
contribuía en gran manera a la oscuridad de los
programas.
Este
conjunto
de
ideas
(razonamiento
formal,
refinamientos
y
construcciones estructuradas) constituye el
mensaje de la programación estructurada,
movimiento cuyo nombre -al menos- llegó a
todos los rincones del mundo de la
programación a lo largo de dos décadas. Por el
conjunto de sus aportaciones, que también se
extienden al campo concurrente (ver Sección 5),
Dijkstra recibió el premio Turing en 1972. En su
discurso [Dij72a], aprovecha para arremeter
contra los lenguajes de finales de los 60, muy
especialmente contra PL/I del que llega a decir
que es como una "enfermedad mortal".
Estas reflexiones condujeron necesariamente a
diseñar lenguajes mucho más modestos que los
precedentes, de forma que la simplicidad y la
verificabilidad de las construcciones fueran el
hilo conductor. La semántica axiomática
proporcionaba así una herramienta objetiva para
comparar unos lenguajes con otros. En la
medida en que el conjunto de axiomas se
volviera inmanejable, el lenguaje dejaría de ser
útil. La programación con go-to era perjudicial
no sólo porque resultaba subjetivamente más
oscura, sino además porque hacía la tarea de
verificación objetivamente más dificil, cuando
no imposible.
El lenguaje expresamente diseñado para reflejar
y enseñar las ideas de la programación
estructurada, fue Pascal [Wir71b]. En aquel
momento, Niklaus Wirth era profesor en la
Universidad de Zurich y el único lenguaje
práctico de que disponía para la enseñanza era
Fortran. Wirth había sido uno de los
investigadores disidentes del WG 2.1. Su
propuesta para Algol68 había quedado en
minoría y decidió implementarla con el nombre
de Algol-W [Wir66]. Este lenguaje tuvo poca
difusión pero fue muy apreciado por los que
tuvieron ocasión de usarlo. Tenía la misma
simplicidad de Algol 60, e incluía algunas construcciones nuevas que fueron incorporadas
también a Pascal: registros, punteros,
instrucción case, separación de for y while en
dos instrucciones y algunas otras. Pascal, por su
parte, añade la posibilidad de que el
programador defina y dé nombre a sus propios
tipos, que pueden ser construidos a base de
combinar, prácticamente sin restricciones, los
constructores array, record, file y set, los dos
últimos aportaciones originales de Pascal.
También añade la definición de tipos
enumerados y un concepto restringido de
subtipo, los subrangos. Además de esta riqueza
sin precedentes en los tipos, otro de los
objetivos de Pascal era su implementación
eficiente, pues Wirth estimaba que sólo un
lenguaje eficiente podría desplazar a Fortran.
Por ello se decidió por unos arrays cuyo tamaño
había de fijarse en tiempo de compilación, lo
que suponía un paso atrás con respecto a Algol
60.
Wirth y sus colaboradores hicieron notables
esfuerzos por escribir un buen manual, al que
añadieron una abundante colección de ejemplos
[JW74], y por difundir sus técnicas de
compilación, de forma que resultase fácil a otros
la construcción de compiladores. Pascal se
convirtió en poco tiempo en el lenguaje estándar
para la enseñanza de la programación en los
primeros cursos. Andando los años, y gracias a
unas buenas implementaciones para los
computadores medianos y pequeños, también
terminó por desplazar a Fortran en los ámbitos
de la programación científica (excepto en las
aplicaciones de cálculo numérico y estadística).
Así, Pascal es quizás el primer lenguaje
8
que, sin gozar del soporte de una gran compañía
o de una poderosa institución, ha obtenido la
adhesión de una gran parte de la comunidad
informática. También fue el primer lenguaje que
contó con una definición axiomática de la
práctica totalidad de sus construcciones
[HW73].
El segundo avance metodológico de la década
tiene que ver con la abstracción. Tanto Dijkstra
como Hoare ponen mucho énfasis en sus
escritos sobre esta herramienta mental de que
disponemos los humanos para disminuir el
número de detalles a tener en cuenta
simultaneamente. De hecho, [Dij72b] comienza
con una sección titulada "Sobre nuestra
incapacidad para hacer muchas cosas a la vez"
en la que el autor se extiende sobre las
limitaciones de la mente humana y sobre el
desconocimiento de los programadores acerca
de este fenómeno. El deseo de una mayor
abstracción subyace sin duda al surgimiento de
los lenguajes de alto nivel y a la técnica de
especificación de procedimientos mediante
predicados. Pero la abstracción no había llegado
a las estructuras de datos. Tan temprano como
en 1972, Hoare tiene dos trabajos seminales,
[Hoa72b] y [Hoa72a], en los que ya apunta la
necesidad de aplazar las decisiones de
representación de la información lo más posible
cuando se diseñan programas grandes. Incluso
en
[Hoa72b],
introduce
dos
piezas
fundamentales para el razonamiento sobre
representaciones de datos: el invariante de la
representación y la función de abstracción.
Pero es a partir de los trabajos de D. Parnas
[Par72b, Par72a, Par74] y de B. Liskov [Lis72,
Lis74] desde la parte industrial, y de J. Morris
[Mor73] desde la parte universitaria, cuando
surge un nuevo concepto de profunda influencia
posterior en la programación: el de tipo
abstracto de datos. La idea fundamental es
considerar un tipo de datos como un conjunto de
valores cuya representación en la memoria del
computador es irrelevante -y por tanto no es
necesario conocerla para trabajar con él-, y a la
vez como un conjunto de operaciones que son
las únicas aplicables a los valores del tipo.
La tesis de John Guttag [Gut75] acuña el
término y aporta numerosos ejemplos en los que
se demuestra la utilidad del concepto. Además,
introduce un técnica de especificación
ecuacional que formaliza el comportamiento
observable de un tipo abstracto (ver también
[Lis75] y [GHM78b]). A efectos de programación, la consecuencia inmediata es que un
tipo abstracto da lugar a un nuevo tipo de
módulo donde la visibilidad de la representación
se extiende a los procedimientos que componen
el módulo, pero no a los procedimientos
externos al mismo. Los únicos identificadores
exportados por el módulo son el nombre del tipo
y los nombres de sus operaciones. Las reglas de
visibilidad de los lenguajes con estructura de
bloques no sirven a esta nueva necesidad y, por
tanto, aparece una nueva generación de
lenguajes que incorporan los mecanismos de
ocultamiento necesarios. Los primeros de ellos
son CLU [LSAS77] y ALPHARD [WLS76] , y
rápidamente les siguen otros. El propio Wirth
diseña, primero Modula [Wir77], y más
adelante Modula-2 [Wir82] para adaptarse a
esta necesidad.
Además de estas aportaciones a la ingeniería de
la programación, al suministrar un concepto de
módulo, los tipos abstractos despiertan el interés
de los investigadores teóricos. Un grupo de
ellos, proveniente de la teoría de categorías y
empleados por el centro de investigación
Thomas J. Watson de IBM, se preocupan por el
significado matemático de una especificación
ecuacional de un tipo abstracto. Deciden que el
concepto adecuado es el de álgebra heterogénea,
y comprueban que la clase de álgebras que
satisfacen una especificación ecuacional, junto
con los homomorfismos entre ellas, constituyen
una categoría. Como anécdota, el grupo se
autodenominó ADJ, a partir de los funtores
adjuntos (ADJunctions) que aparecen en las
categorías. Eligen como modelo representativo
de la especificación el modelo inicial que,
intuitivamente, es el álgebra en la que sólo
existen valores generados por las operaciones y
que satisface las ecuaciones dadas y ninguna
otra adicional. Este modelo siempre existe y es
único para una especificación dada. En adelante,
las especificaciones ecuacionales de tipos
abstractos se denominarían algebraicas. Las
publicaciones del grupo se extienden a lo largo
de toda la década [GTWW76, GTW78] y
abrieron una linea de investigación que aún
permanece viva. Las especificaciones se
sofistican para poder expresar situaciones de
error, para tratar con operaciones parciales, o
para poder construir modularmente grandes
especificaciones. Se diseñan lenguajes de
especificación y se construyen herramientas
para demostrar teoremas a partir de una especificación. En muchos casos, una especificación
es ejecutable, es decir, puede simular con toda
precisión el comportamiento del programa que
especifica. La técnica empleada para ambos
propósitos (demostración de teoremas y
ejecución) es la de reescritura de términos
[HO80, Les83, GH86]. Ello permite contemplar los lenguajes de especificación como
verdaderos lenguajes de programación, de muy
alto nivel, para la construcción de prototipos
tempranos en el desarrollo de software. Un
lenguaje especialmente diseñado con este
propósito es OBJ2 [FGJM85]. Por otra parte, se
mantiene un vivo debate sobre si la semántica
inicial es o no la más adecuada para una
especificación algebraica. Se proponen otras
semánticas alternativas como la final, la laxa o
la de comportamiento que quizás reflejan mejor
la idea, asociada a los tipos abstractos,
9
El lenguaje de programación que recoge la
mayoría de estas aportaciones es Ada [Ada83].
Se le dio este nombre en honor a Ada Augusta,
Condesa de Lovelace y colaboradora de Charles
Babbage (ver la Sección 1). Su patrocinador,
una vez más, fue el Departamento de Defensa
de los Estados Unidos, preocupado por los
enormes costes de desarrollo de software que
soportaba. Sus responsables consideraron que, si
dispusieran de un lenguaje con suficientes
facilidades para soportar la programación en
gran escala -es decir, modularidad, librerías
estándar, componentes reutilizables- y, en
particular, para la programación de sistemas
empotrados4 -o sea, con construcciones para el
manejo de la concurrencia, de los dispositivos
externos y del tiempo real-, podrían prescindir
de la mayoría de los lenguajes en uso en el
DoD. Con ese fin, ponen en marcha un
complejo mecanismo de creación de
especificaciones, evaluación de propuestas y de
sucesivos refinamientos, que culminan en la
definición del mencionado lenguaje. Sus autores
son el grupo de Jean Ichbiah en Cii-Honeywell
Bull. El proceso se extiende en el tiempo desde
1975 a 1980 [Ada79] y tiene oportunidad de
recoger gran parte de las ideas reseñadas en los
párrafos precedentes, junto con otras sobre
concurrencia que se detallan en la Sección 5. El
primer compilador certificado se termina en
1983, año en que también es estandarizado el
lenguaje por la ANSI [Ada83].
Por primera vez, un lenguaje se diseña a partir
de unas especificaciones previas de requisitos.
Las cuatro propuestas candidatas en la fase final
fueron sometidas a evaluación y crítica por parte
de numerosos grupos de potenciales usuarios.
Es decir, se trata de un lenguaje hecho a la
medida de unas necesidades. Se admite el papel
de Pascal como el principal lenguaje inspirador
de su diseño. El producto resultante es un
lenguaje bastante voluminoso pero con una
unidad interna de la que carecían propuestas
anteriores. No obstante, no se libró de la crítica
de Hoare, quien en la recepción del premio
Turing [Hoa81] le acusó de excesiva
complejidad. Aunque actualmente está muy
difundido, todavía es una incógnita su futuro. El
proceso de introducción ha sido más lento de lo
deseable debido quizás al volumen e
ineficiencia -tanto en el proceso de compilación
como en el código generado- de los primeros
compiladores.
Ada no pretendía innovar, sino más bien,
utilizar conceptos ya probados. Por ejemplo,
adopta una sintaxis parentizada, similar a la de
Modula-2, donde toda construcción tiene una
palabra clave que indica su final. Ello elimina el
conocido problema del else pendiente en
lenguajes como Algol 60, PL/I y Pascal.
----------------------------------------------------------
de ocultamiento de información. En [BW84] y
en [Wir90] se da una amplia visión de estos
aspectos semánticos. Una referencia obligada
para la semántica inicial es [EM85].
El concepto de tipo abstracto ha dado lugar a
otras líneas de investigación. En el terreno del
desarrollo modular de grandes programas, son
imprescindibles las referencias [Lis79] y
[LG86]. En ellas se propone un método de
diseño a gran escala que puede verse como una
puesta al día, a la luz de los tipos abstractos, del
método de los refinamientos sucesivos de Wirth.
Se presentan ejemplos de la magnitud suficiente
como para apreciar las dificultades y los
beneficios de la técnica. La forma de presentar
las estructuras de datos también cambia
notablemente: ahora, se ha de distinguir entre el
tipo observable, descrito por una especificación
(por ejemplo, conjunto de pares (clave, valor),
con operaciones de inserción, búsqueda,
borrado, etc.), y las posibles representaciones
usadas para el mismo (por ejemplo, tabla hash,
árbol binario equilibrado, etc.). Algunos libros
de texto (p.e. [AHU83, Mar86, HS90]) reflejan
esta visión.
Otro concepto importante es el de
implementación, es decir, el conjunto de
criterios que aseguran que una representación, y
sus procedimientos asociados, satisfacen el
comportamiento definido por una especificación
algebraica. Algunos trabajos clave son [Dah78,
EKMP82, BMPW86, ONS92], pero se puede
decir que, a efectos prácticos, el problema
continúa abierto. Es decir, no parece haberse
encontrado un modo de realizar estas
comprobaciones con una inversión razonable de
esfuerzo. Otros trabajos (p.e. [GHM78a,
NHN78]) se han ocupado de combinar las
técnicas de verificación formal con predicados,
con las de especificación ecuacional de tipos
abstractos de datos.
Finalmente, otra idea importante surgida al calor
de esta investigación es la de genericidad. Un
tipo abstracto puede ser genérico o
parametrizado en el sentido de que algunas de
sus características están indefinidas, o tan sólo
parcialmente definidas. Al conjunto de
características indefinidas se le denomina
parámetro formal. En una etapa posterior, se
concreta el tipo genérico suministrando un
parámetro real en el que se precisan los detalles
indefinidos.
Proporcionando
diferentes
parámetros reales, se obtienen diferentes tipos
concretos. Esta idea, una vez incorporada a los
lenguajes de programación, permite una gran
economía de esfuerzo. Por ejemplo, los
algoritmos de ordenación podrían tenerse
almacenados en una librería de algoritmos
genéricos, y obtener la versión concreta deseada
indicando tan sólo el tipo de los elementos, el
tamaño del vector a ordenar y la relación de
orden a utilizar.
4En inglés, embedded systems, es decir,
computadores que forman parte de un sistema
hardware más amplio y al cual controlan.
10
A pesar de lo dicho, pueden señalarse las
siguientes innovaciones de Ada con respecto a
los lenguajes más cercanos:
cosas a la vez, en diferentes niveles de la
estructura del programa.
. Mecanismo de paso de parámetros oculto al
programador. Éste sólo debe especificar si los
mismos han de ser usados en modo lectura parámetros in-, en modo escritura -parámetros
out-, o en ambos modos - parámetros in out. El
compilador garantiza esos usos y elige el
mecanismo que considere más eficiente (por
valor, por referencia) independientemente del
tipo de parámetro.
. La construcción package, mecanismo
principal de ocultamiento y de modularidad. Se
distingue entre su parte visible o interfaz con
sus usuarios, y su parte oculta, o body, cuyas
declaraciones sólo son accesibles a los
procedimientos del package. Construcción
versátil que permite la definición de tipos
abstractos, de objetos (ver Sección 4), de
colecciones de procedimientos, o de zonas
globales de datos.
. Construcción exit para salir prematuramente
de un bucle, o de un conjunto de bucles
anidados. El control pasa al final del (de los)
bucle(s). Esta construcción elimina una de las
posibles utilidades del go-to.
. Facilidades para la programación genérica.
Tanto los packages como los procedimientos,
pueden estar parametrizados por tipos,
operaciones o constantes. El mecanismo de
concreción de una construcción genérica se
concibe como un macroexpansor que, tras
comprobar la consistencia sintáctica entre el
parámetro real y el formal, produce el código
específico para esa concreción.
Después de Ada, no ha habido ningún lenguaje
innovador dentro del paradigma imperativo
puro. Tampoco se han producido importantes
avances metodológicos que hayan hecho
necesario diseñar nuevos lenguajes en este
paradigma. Los 80 y los 90 han visto el
desarrollo espectacular de otros paradigmas de
programación. Se han diseñado muchos otros
lenguajes interesantes pero que pertenecen a, o
incluyen elementos de, esos otros paradigmas.
Su historia se relata en las secciones siguientes.
. Compilación separada como parte del
lenguaje.
Estos
aspectos
se
dejaban
normalmente abiertos en otros lenguajes. En
Ada, el compilador se ocupa de mantener la
consistencia entre las interfaces de los módulos
y sus respectivos bodies. Para compilar un
módulo usuario, sólo es necesario tener
compilada la parte de interfaz de los módulos
utilizados. Ello facilita la realización de grandes
programas, donde diferentes personas pueden
estar trabajando en distintos módulos. La
librería de módulos predefinidos es también
parte del estándar.
4 La programación orientada a objetos
Un lenguaje de la década de los 60 que deliberadamente- no ha sido comentado en la
Sección 2 es Simula 67. Contiene el embrión de
lo que hoy se conoce como la programación
orientada a objetos (en adelante, POO), por lo
que se ha preferido relatar su historia en esta
sección.
Sus creadores fueron Kristen Nygaard y OleJohan Dahl del Centro Noruego de
Computación en Oslo [DMN70], y su desarrollo
se extendió desde 1962 a 1967. El objetivo
inicial era definir un lenguaje de propósito
específico para aplicaciones de simulación. De
hecho, realizaron una primera versión, bajo
contrato con la empresa UNIVAC, que no
incluía conceptos novedosos desde el punto de
vista de programación -aunque sí desde el punto
de vista de simulación- con respecto al lenguaje
más avanzado de esos años, Algol 60.
La versión de 1967 tenía como uno de sus
objetivos ahorrar esfuerzo de programación.
Nygaard y Dahl habían desarrollado grandes
programas de simulación con la primera
versión, y habían detectado dos deficiencias:
. Ampliación, con respecto a Pascal, del
concepto de subtipo y de los criterios de
compatibilidad de tipos. En Ada, por ejemplo,
todos los arrays de rango finito se consideran
subtipos de un array conceptualmente sin
límites. Ello facilita la construcción de
procedimientos que pueden ser llamados con
diferentes arrays como parámetro.
. Introducción de sobrecarga definida por el programador. Éste puede asignar el mismo nombre
o símbolo (p.e. "+") a operaciones distintas, e
incluso a constantes. El compilador deduce por
el contexto -siempre que éste no sea ambiguola operación nombrada en cada caso.
. Tratamiento elaborado de excepciones. El
usuario puede tratar excepciones predefinidas
(p.e. fuera de rango) y definir -y tratar- las suyas
propias (p.e. pila_vacía). A su vez, las
excepciones
pueden
ser
propagadas,
recuperadas, o ambas
11
l. Las entidades proceso y estación, útiles en
simulación, eran entes dinámicos que se creaban
y destruían a lo largo de una ejecución. El
concepto de bloque derivado de Algol 60, era
insuficiente para reflejar este dinamismo. Por
otra parte, cada entidad tenía asociadas un
conjunto de variables y un conjunto de
operaciones que las manipulaban. De nuevo, el
texto del programa no reflejaba claramente esta
relación.
en Simula 67 es el de prefijo, y el de subclase
para la clase definida mediante prefijos.
Es obvio que el proceso se puede iterar, y que se
pueden construir secuencias C1, . . ., Cn en las
que cada clase Ci+l, i ε {l..n - l}, tiene como
prefijo a la clase Ci. Más aún, una misma clase
A puede actuar como prefijo de varias subclases
B1,..., Bm que, en este caso, serían "hijas" de
una misma clase-madre. En [DH72] se
proporciona un embrión de método de
desarrollo descendente basado en esta idea de
jerarquía de clases. A nivel de implementación,
en Simula 67 se reconoce la influencia de
[Hoa68] , especialmente en el uso de punteros y
en la implementación de las subclases de una
misma clase como registros variantes del
registro que implementa la clase-madre.
El siguiente hito en la POO, y en realidad quien
le dio categoría de paradigma con características
propias, fue el lenguaje Smalltalk. Su creador
fue Alan Kay, del Centro de Investigación en
Palo Alto de Xerox Corporation. También en
este caso, la gestación fue larga y laboriosa,
desde una primera versión en 1972, hasta la
versión pública de 1980 [GR83]. En el camino
se desarrollaron varias versiones para uso
interno de Xerox. El autor reconoce en [Kay93]
influencias de Simula 67, de LOGO y de FLEX,
un lenguaje previo desarrollado por él mismo.
Los conceptos de clase, objeto de una clase, y
sub-clase de una clase son los centrales del
lenguaje. A la clase-madre de una subclase se la
denomina superclase de la misma. En Smalltalk
aparece ya nítidamente la obligación de que la
representación de un objeto sea privada y, por
tanto, oculta a los usuarios de una clase. Otras
características de Smalltalk son las siguientes:
2. El código de muchas entidades era bastante
semejante, pero el lenguaje no proporcionaba un
mecanismo que permitiera reutilizar las partes
comunes.
El primer hallazgo de Nygaard y Dahl fue la
distinción entre una clase de entidades -un texto
suministrado por el programador- y los objetos
que se derivan de ella -los ejemplares de la
misma creados y destruidos dinámicamente a lo
largo de una ejecución concreta. Una clase en
Simula 67 consiste en una colección de
procedimientos, asociados a un conjunto de
declaraciones de variable. Cada vez que se crea
un objeto de una clase, se asigna memoria para
contener una colección de dichas variables. Esta
idea, hoy familiar, exigía dos innovaciones con
respecto a los lenguajes de la época:
. Escapar de la estructura de bloques. A diferencia de ésta, un objeto ha de "sobrevivir" al procedimiento que lo crea. Varios objetos de una
misma clase han de poder coexistir en un mismo
ámbito.
. Necesidad de un tipo de datos "referencia a un
objeto" que permitiera designar objetos distintos
en distintos momentos. Este tipo, llamado ref en
el lenguaje, no era otra cosa que un puntero.
. Integración del lenguaje con el entorno de programación. Smalltalk pone mucho énfasis en
este aspecto, extendiendo los conceptos del
lenguaje al propio entorno, que también se
compone de objetos. Además, el entorno gráfico
que acompaña a Smalltalk, el primero basado en
iconos y menús, sirvió de inspiración a todos los
sistemas operativos de ventanas que vinieron
después, comenzando por los de los
computadores de Xerox y de Apple.
Esta noción de clase fue enriquecida en
lenguajes posteriores con la idea de
ocultamiento que -como se ha explicado en la
Sección 3- surgió más adelante, dando lugar al
concepto de objeto que hoy conocemos. La
clase de Simula 67 puede verse como precursora
a la vez de los objetos de la POO y de los tipos
abstractos de datos comentados en la Sección 3.
De hecho, dejando de lado cuestiones de
notación y de terminología, las ideas de
encapsulamiento y de abstracción de datos son
exactamente las mismas.
El segundo hallazgo de Simula 67 -y éste sí que
es específico de la POO- es el concepto de
subclase. La idea esencial es simple: si una
clase B ha de repetir declaraciones de variables
y de procedimientos que ya están en otra clase
A, se indica que la clase A es un prefijo de la
clase B, y se definen en B tan sólo las variables
y los procedimientos que son específicos de B.
En [DH72] se denomina a este proceso concatenación de clases, pero el término original
empleado
. Comprobación de tipos en ejecución.
. Polimorfismo de subtipos, que se define como
el hecho de que un objeto de una subclase es
admisible en cualquier parte del programa
donde sea válido un objeto de su superclase.5
---------------------------------------------------------5Algunos autores llaman polimorfismo, sin
calificativo, a esta característica. Aquí se ha
reservado este término para el polimorfismo
paramétrico de los lengajes funcionales que
poseen el sistema de tipos de Hindley-Milner
[Mil78]. Ver la Sección 7.
12
. Vínculos dinámicos entre identificadores y
objetos. En Smalltalk, un procedimiento de una
clase puede ser redefinido en una subclase de la
misma. Por ello, se difiere al momento de la
ejecución la decisión de qué versión utilizar de
un procedimiento dado, cuando existen varias
versiones del mismo.
no relacionados y, por otro, a un esfuerzo de
generalización, creando clases genéricas que
puedan ser superclases de muchas otras. Ambas
tareas son beneficiosas para una programación
en gran escala. Además, la POO es consciente
de que la reutilización lleva aparejado un cierto
grado de adaptación. Por ello, los lenguajes
orientados a objetos permiten, no sólo ampliar
las definiciones con respecto a las de la
superclase, sino también redefinir algunas de las
operaciones de la misma, si bien manteniendo
siempre el mismo perfil externo.
Conviene hacer notar, no obstante, que lo que se
reutiliza de una clase es su implementación. El
ocultamiento de información de una clase hacia
sus programas usuarios desaparece cuando se
trata de las subclases. Ello va ciertamente en
contra de la idea original de modularidad, según
la cual se puede cambiar la implementación de
un módulo de manera transparente al resto de
los mismos. Si se modifica la implementación
de una clase situada muy arriba en la jerarquía
de clases, muchas subclases habrán de ser
reprogramadas, ya que la nueva implementación
probablemente no podrá ser extendida de la
misma manera que lo era la antigua.
A nivel más teórico, la relación clase-subclase
es una generalización del concepto de subtipo
en programación. Un subtipo es una
especialización de un tipo, que hereda todas las
operaciones del tipo-padre (o supertipo), y que
puede añadir algunas otras. Un valor de un
subtipo es admisible en cualquier parte del texto
donde se espere un valor de su supertipo (ver
comentario acerca de los subtipos de Ada en la
Sección 3). La POO ha despertado un renovado
interés por los sistemas de tipos en los lenguajes
de programación. En particular, un registro que
extiende a otro con campos adicionales, se
contempla actualmente como un subtipo del
primero. Para obtener una panorámica de la
diversidad que pueden alcanzar estos sistemas,
ver [CW85] y [Car89].
Una consecuencia del movimiento de la POO es
que se han producido versiones de lenguajes
existentes -en muchos casos superconjuntosque incorporan características orientadas a
objetos. El caso más evidente es el de C++
[Str86b,
Str86a],
prácticamente
un
superconjunto de C [KR78]. La construcción
modular de C++ también se llama clase, y
permite tanto la definición de tipos abstractos de
datos como la utilización de los conceptos de
herencia. En C++ se refuerza la disciplina de
tipos con respecto a C y, a diferencia de
Smalltalk, la comprobación de tipos es estática.
Otras diferencias con Smalltalk son que C++
admite herencia múltiple -es decir, una clase
puede heredar los atributos de dos o más clases
simultáneamente- y que la gestión de memoria
sigue el esquema de bloques: los objetos se
crean al
. Librería predefinida, de clases y subclases,
muy voluminosa. Se contempla la tarea del
programador más como la de enriquecer
interactivamente dicha librería con subclases de
otras clases ya existentes, que como la de crear
clases nuevas desde cero.
. Incorporación de un algoritmo implícito de
recolección de basura.
. Máquina virtual de soporte al lenguaje que se
ha convertido en un estándar para los lenguajes
orientados a objetos.
A partir de Smalltalk y de su "filosofía"
asociada -"todo" son objetos, creación dinámica
de objetos, librería predefinida de clases,
entorno gráfico interactivo- se produce un
interés muy grande por el paradigma, y la POO
se
difunde
ampliamente
en
entornos
industriales. Se considera que la orientación a
objeios consiste, no sólo en unas facilidades de
ciertos lenguajes de programación, sino también
en un modo de enfocar el diseño de grandes
programas. Muchos libros sobre ingeniería del
software asumen el paradigma y hablan de construcción, diseño y modelización "orientados a
objetos" [Cox86, Mey88, Boo91, RBP+91].
En realidad, la POO no constituye un paradigma
alternativo al imperativo en el mismo sentido
que lo son la programación funcional o la
programación lógica. Por un lado, los lenguajes
orientados a objetos son sin duda imperativos.
Por otro, las ideas originales subyacentes -en
esencia, el concepto de herencia por el cual una
subclase hereda los atributos de clases
superiores en la jerarquía-, son útiles en
cualquier paradigma. De hecho, estamos
asistiendo en estos años al surgimiento de
lenguajes que combinan estas ideas con las
propias de su paradigma: lenguajes funcionales
orientados a objetos, lenguajes lógicos
orientados a objetos, e incluso lenguajes lógicoconcurrentes orientados a objetos.
Desde el punto de vista práctico, la POO aporta
una forma de programar que pone el acento en
la reutilización del software. Antes de
plantearse programar una nueva clase, el
programador ha de ser consciente de las que ya
existen, y tratar de contemplar su clase como
derivada de otra (u otras) previas. Ello le obliga,
por un lado, a un esfuerzo de clasificación,
descubriendo conexiones entre módulos
aparentemente
13
mecanismo del semáforo. Éste consiste, en
esencia, en una variable entera compartida, con
dos operaciones, llamadas P y V, que se
ejecutan en exclusión mutua.
Los semáforos sirven para crear regiones
críticas en las que un proceso consigue
exclusión mutua con respecto a otros en el
acceso a un recurso, o para proveer cualquier
otra sincronización. Sin embargo, como
mecanismo para incorporar a un lenguaje es
poco seguro. Una operación V de más sobre el
semáforo, o de menos, puede producir efectos
catastróficos. Por ello, Hoare propone, en
[Hoa72c], las regiones críticas y las regiones
críticas condicionales (en adelante, RCC's)
como construcciones estructuradas a ser
incluidas en un lenguaje concurrente. La
primera suministra exclusión mutua y la
segunda proporciona además sincronización.
Ésta se produce evaluando en exclusión mutua
una expresión booleana sobre variables
compartidas: si la expresión es cierta, el proceso
prosigue; en caso contrario, libera la exclusión
mutua y queda detenido hasta que la expresión
sea cierta. P. Brinch Hansen populariza estas
construcciones en [Han72] y [Han73], y sugiere
algunas variantes.
Las RCC's resultan bastante expresivas, pero
adolecen de dos problemas: el más grave de
ellos es que son ineficientes de implementar.
Cada vez que un proceso sale de una RCC, el
gestor de procesos "despierta" a todos los
procesos esperando por alguna condición y, por
turno, reevalúan cada uno la suya. Si alguno
vuelve a encontrar que su condición es falsa, es
detenido de nuevo. El fenómeno puede repetirse
muchas veces antes de que la condición sea
cierta, y en consecuencia, los procesos
consumirían tiempo del procesador inútilmente.
El segundo problema es que, en un programa
grande, las RCC's -cada una referida a un
recurso compartido posiblemente distintoquedan dispersas en el texto de los procesos
haciendo difícil el control del uso de las
variables compartidas. Ambos problemas son
resueltos por una nueva construcción: el
monitor. Anticipado por Dijkstra en [Dij71] con
el nombre de "secretario", su introductor como
construcción acabada de lenguaje es Hoare en
[Hoa74].
El concepto de monitor está inspirado en las
abstracciones de datos de la programación
secuencial, y consiste en una colección de
procedimientos y en un conjunto de variables
compartidas por ellos. La diferencia es que
ahora los procedimientos pueden ser llamados
concurrentemente desde varios procesos. Cada
procedimiento se ejecuta en exclusión mutua
con los demás -o consigo mismo, si es llamado
por dos procesos-, suministrando así el
equivalente a la región crítica. Para sincronizar
unos procesos con otros, los monitores pueden
declarar variables condición y realizar sobre
ellas dos operaciones, llamadas
declararlos y se destruyen al abandonar el
bloque. Otro lenguaje que ha sufrido una
metamorfosis parecida es Modula-2: el lenguaje
del mismo autor, Oberon [Wir88] , añade sobre
Modula-2 la construcción de registros
extensibles que no es sino otro nombre para la
idea de subclase. También Ada ha evolucionado
en la misma línea: la reciente revisión Ada 95
[Ada95] incorpora el concepto de herencia y
una librería estructurada de clases.
Un lenguaje moderno especialmente diseñado
para la programación orientada a objetos en
gran escala es Eiffel [Mey88, Mey92]. Incluye
disciplina fuerte de tipos, comprobación
estática, genericidad, herencia múltiple,
vínculos dinámicos, operaciones diferidas
(indefinidas en la superclase pero definidas en
las subclases) y recolección automática de
basura.
5 La programación concurrente
En la Sección 2 se ha mencionado el invento de
la interrupción a finales de los 50 como el hecho
que marca el inicio de la programación
concurrente. El desarrollo de los conceptos
adecuados para este tipo de programación ha ido
siempre a remolque de los avances en
arquitectura de computadores. Los comienzos
fueron extremadamente difíciles, pues se
construían sistemas operativos muy complejos,
como el mencionado OS/360 de IBM, sin
comprender apenas las implicaciones del hecho
de compartir datos entre procesos que podían
ser interrumpidos y recontinuados en instantes
arbitrarios. Fallos que aparecían en una
ejecución, no volvían a aparecer en las
siguientes, haciendo muy difícil la tarea de
depuración. Eran los temibles errores
dependientes del tiempo, específicos de la
programación concurrente.
Las primeras abstracciones las proporciona E.
W. Dijkstra en una sucesión de trabajos [Dij65,
Dij68b, Dij68d, Dij71] que fueron de una
influencia decisiva para la comprensión del
problema. Dijkstra observó que la inmensa
mayoría de los errores era debida a suposiciones
implícitas que el programador de un proceso
hacía acerca del instante de ejecución en que se
hallaban otros procesos. Cuando esas
suposiciones eran invalidadas por pequeñas
variaciones en las velocidades, se producía el
fallo.
La
aportación
principal
-hoy
absolutamente natural, pero nada evidente en
aquel momento- fue concebir el programa
concurrente como un conjunto de procesos
secuenciales asíncronos que no debían hacer
suposiciones implícitas sobre las velocidades
con que progresaban los otros procesos.
Cualquier relación de orden temporal entre ellos
había de conseguirse por medio de
sincronizaciones explícitas. Con este fin,
propuso el
14
comúnmente wait y signal, cuyo efecto es muy
similar al de las operaciones P y V de los
semáforos. De esta manera, el monitor se
convierte en un mecanismo de encapsulamiento
de recursos compartidos y de modularidad para
la construcción de programas concurrentes. P.
Brinch Hansen desarrolló el lenguaje
Concurrent Pascal [Han75] basado en este
concepto. Era el primer lenguaje concurrente de
la historia, y para demostrar su utilidad,
programó con él varios sistemas operativos
[Han76, Han77]. Otros lenguajes concurrentes
posteriores que incorporan monitores son
Modula [Wir77], Mesa [MMS79, LR80] y
Pascal Plus [WB79].
Pero, apenas nacidos, los monitores ya
resultaban un mecanismo insuficiente. Hacia
1975, se habían empezado a fabricar los
primeros microprocesadores y, en muy poco
tiempo, dominarían el mercado gracias a su bajo
coste. Era evidente que la concurrencia en un
solo procesador sería desplazada a medio plazo
por una verdadera programación paralela en la
que diferentes procesos se ejecutarían en
diferentes procesadores. La suposición implícita en los monitores y en los mecanismos
precedentes- de una memoria común en la que
residían las variables compartidas por los
procesos, dejaba de ser realista. Se necesitaba
una construcción que pudiera implementarse
mediante el paso de mensajes entre
procesadores. Se realizan varias propuestas
[Hoa78, Han78, MY80], de las cuales la que ha
tenido más influencia es la de los Procesos
Secuenciales Comunicantes (CSP-78) de Hoare.
El segundo lenguaje influido por la propuesta
CSP-78
es Ada [Ada83]. La sincronización en Ada es
más elaborada que la de CSP-78 porque aquí la
cita involucra mensajes en dos direcciones:
primero, de la tarea llamante a la tarea llamada
para pasar los parámetros de entrada, y luego en
sentido contrario para devolver los posibles
resultados. En lugar de canales, el mecanismo
de comunicación es mediante llamada remota.
Es, por tanto, asimétrico en el sentido de que la
tarea cliente o llamante "conoce" a la tarea
servidora o llamada, pero no a la inversa. Como
varias tareas cliente pueden llamar a la misma
entrada remota de una tarea servidora, Ada
provee una cola FIFO por entrada para gestionar
las esperas. En Ada existe también el
equivalente a las acciones protegidas no
deterministas de CSP-78: mediante la
instrucción select, una tarea servidora puede
estar a la espera de que llamen a cualquiera de
sus entradas. Otras facilidades concurrentes
presentes en Ada, pero no en CSP-78, se
refieren al control sobre el tiempo real y sobre
las interrupciones de los periféricos externos.
Recientemente, se ha producido una importante
revisión de Ada [Ada95] que ha afectado sobre
todo a los aspectos concurrentes del lenguaje.
Además de mantener el mecanismo distribuido
de las tareas, se ha incorporado otro, llamado
tipos protegidos, que se utiliza para compartir
datos en un mismo procesador. La construcción
es una versión de monitor bastante elegante ya
que la sincronización se produce mediante
expresiones booleanas, llamadas aquí barreras.
Sin embargo, ha escapado al problema de la
ineficiencia haciendo que, a lo sumo, exista una
barrera por procedimiento y que ésta sólo
incluya variables locales del monitor. Se añade
una primitiva requeue
para suplir la
imposibilidad de tener varias barreras
consecutivas en un mismo procedimiento. La
razón principal de los tipos protegidos es
aumentar la eficiencia de la sincronización entre
procesos.
La comunicación en CSP-78 se realiza mediante
un paso sincronizado de mensajes o cita. El
primer proceso -lector o escritor de un mensajeque llega al punto de cita, espera al otro.
Cuando ambos están dispuestos, se produce la
comunicación. Adicionalmente, un proceso
puede estar en una espera no determinista por
varias citas. La primera que sea posible, por
estar ya dispuesto el proceso complementario,
es la que se produce. Para expresar esta espera
no determinista, Hoare utiliza una construcción
similar a las acciones protegidas (guarded
commands) del lenguaje secuencial de Dijkstra
[Dij75]. Con ella consigue una expresividad
equivalente a la de las RCC's, ya que las
condiciones de sincronización -llamadas aquí
guardas- son expresiones booleanas, pero sin la
ineficiencia asociada a aquellas. Un lenguaje
que implementa directamente las ideas de CSP78 es Occam [Occ84] , desarrollado por la
empresa INMOS Ltd. como lenguaje base para
sus redes de transputers. Un transputer es un
microcomputador con unas capacidades
mejoradas de comunicación. Occam incorpora
canales entre procesos, idea que ya fue anticipada en [Hoa78].
En el área de la programación concurrente, los
métodos de verificación y de razonamiento
sobre la corrección de los programas no han
alcanzado la misma estabilidad que en el caso
de la programación secuencial. Los primeros
intentos consistieron, siguiendo los pasos de
esta última, en aplicar las técnicas de
especificación con predicados. En [Hoa72c] se
extienden los axiomas de las construcciones
secuenciales con reglas para tratar con las
RCC's y con la instrucción paralela cobegin. . .
coend. Estas
reglas
tienen
excesivas
restricciones sobre el tipo de variables que
pueden aparecer en los asertos. La primera
lógica completa para verificar la corrección
parcial de programas concurrentes basados en
RCC's la proporciona la tesis de Susan Owicki
15
predicados es el lenguaje UNITY [CM88].
Aquí, el programa se
concibe como una ejecución no determinista de
asignaciones atómicas. UNITY no es, pues, un
lenguaje de programación convencional, pero
tiene muchos elementos de éstos: variables,
asignaciones, expresiones condicionales, etc.
Asociada al lenguaje, se proporciona una lógica
con algunos operadores temporales, tales como
leads-to, que expresa el progreso inevitable
desde un estado a otro. Finalmente, existe en el
lenguaje una noción implícita de justicia
(fainess) , según la cual no está permitido diferir
indefinidamente la ejecución de ninguna acción
elemental. Con estos elementos, en [CM88] se
verifican muchos ejemplos clásicos, y otros no
tan clásicos, de la programación concurrente.
Quizás la principal debilidad de UNITY es la
ausencia de una noción de proceso. Ello hace
que la transformación de un programa UNITY a
un lenguaje concurrente convencional sea una
tarea nada formal y pueda perderse, por tanto, la
corrección obtenida con tanto esfuerzo.
El concepto de justicia en los sistemas
concurrentes también ha dado lugar a
numerosos trabajos. En la mayor parte de los
programas no es posible demostrar propiedades
de progreso o de terminación si no se hace
alguna hipótesis sobre la justicia del lenguaje
subyacente. Hay varios tipos de justicia incondicional, débil, fuerte, etc.- y, según la que
se escoja, la técnica de demostración de
propiedades será de un modo o de otro. En
[Fra86] se encuentra una recopilación de
trabajos, y en los libros recientes [AO91] y
[Fra92] se muestra como probar la terminación
de un programa concurrente -y una
postcondición asociada a la misma- bajo
hipótesis de justicia fuerte sobre el lenguaje.
Finalmente, otra linea de investigación muy
prolífica ha sido la de los modelos algebraicos
para especificar sistemas concurrentes. Estos
modelos algebraicos están basados en unos
pocos operadores, y no pretenden ser un
lenguaje de programación sino más bien un
marco formal en el que especificar, transformar
y demostrar propiedades de un sistema
concurrente, a un alto nivel de abstracción, sin
tener que involucrarse en los detalles de un
lenguaje ejecutable. Robin Milner inauguró la
línea con el modelo CCS [MiI80] posteriormente refinado en [MiI89]-, y fue
pronto seguida por el modelo CSP-85 de Hoare
[BRH84, Hoa85] y otros modelos [BK85,
Hen88]. Los elementos de estos lenguajes son
pocos y simples: ecuaciones recursivas,
acciones atómicas -denominadas eventos-,
operadores para componer secuencialmente un
evento y un proceso, para abstraer parte de los
eventos de un proceso, y operadores binarios
que componen dos procesos en paralelo, o
permiten elegir entre dos procesos alternativos.
[Owi75, OG76]. La técnica de verificación
exige que se demuestre la llamada propiedad
de ausencia de interferencia entre los asertos de
cada proceso y las acciones elementales de
todos los restantes. Ello da lugar a un esfuerzo
de demostración proporcional al ¡cuadrado! de
la longitud del texto. Para disminuir este
esfuerzo, se proponen algunas técnicas como la
del invariante global: un predicado que puede
nombrar variables locales a los procesos y
variables compartidas entre ellos, y que es
preservado por todas las acciones atómicas del
programa. La técnica de Owicki y Gries permite
verificar la conservación de la exclusión mutua
y la ausencia de bloqueo.
La idea de que un programa concurrente, en
esencia, mantiene un invariante global, parece
estar presente en todas las técnicas que se han
propuesto posteriormente. Son especialmente
relevantes los numerosos trabajos de Leslie
Lamport. En [Lam77] se proponen los términos
propiedades de seguridad y de vitalidad hoy
completamente aceptados. En [Lam80] se
introducen los predicados at, in y after para
razonar sobre el valor del contador de programa
de cada proceso, y una lógica generalizada para
demostrar propiedades arbitrarias de seguridad y
de vitalidad, en la que el invariante global juega
un papel preponderante. En [LS84] relaciona su
método con el de Owicki y Gries y muestra
cómo es también aplicable a programas escritos
en CSP-78.
Una variante de la lógica simple de predicados
es la lógica temporal, introducida originalmente
por A. Pnueli en [Pnu77]. Esta lógica permite
razonar sobre secuencias de estados y expresar
propiedades de obligatoriedad tales como "el
estado P conduce inevitablemente al estado Q".
En contrapartida, las verificaciones son más
complejas. En [OL82], Owicki y Lamport
demuestran propiedades de vitalidad usando
lógica temporal e invariantes. Se han recopilado los resultados fundamentales de la
investigación en lógica temporal en [MP92]. L.
Lamport ha desarrollado recientemente un
lenguaje muy simple, con una lógica temporal
asociada, para razonar cómodamente sobre las
propiedades de vitalidad de los sistemas
[Lam94].
En [AFdR80] se propone también un conjunto
de reglas de verificación para CSP-78, pero esta
vez en el marco de la lógica simple de
predicados. También en este marco, Hoare dio
en [Hoa74] las reglas de verificación para
monitores. De nuevo, el invariante del monitor
es una pieza fundamental. En un programa con
monitores, el invariante global es, simplemente,
la conjunción de los invariantes de todos los
monitores, y se puede suponer que se satisface
en cualquier punto de un proceso que sea
exterior a las llamadas a monitores.
Otro sistema para el razonamiento sobre
programas concurrentes basado en lógica de
16
La semántica de los sistemas así construidos se
suele dar de tres formas complementarias:
6Para este algoritmo se han propuesto
posteriormente numerosas implemenlaciones
eficientes. Ver p.e. [MM82].
Operacional El lenguaje define un conjunto de
reglas de transición que indican cómo un
término sintáctico evoluciona hacia otros
términos mediante la "ejecución" de eventos.
muy productivos. Descubrieron que había una
cercanía muy grande entre el concepto de
deducción en lógica y la idea de cómputo en
programación. Pudieron escribir predicados
recursivos "ejecutables" para funciones sencillas
como la suma y el factorial. La visita se repitió
en la primavera de 1972. Fue después de esta
visita cuando el grupo de Colmerauer decidió
restringir la forma de los predicados a las
claúsulas de Horn, es decir, a predicados de la
forma B1 Λ ...Λ Bn → A, con n >=0. La
resolución SL es, en ese caso, más eficiente.
Usando cláusulas de Horn, y la resolución SL
modificada como método de deducción,
Colmerauer y sus colaboradores definieron e
implementaron el lenguaje PROLOG durante el
verano de 1972, y escribieron en PROLOG un
largo programa para procesamiento de lenguaje
natural [CKPR73]. El lenguaje fue llamado así
como abreviatura de Programmation en
Logique, a sugerencia de la mujer de Philippe
Roussel. Por su parte, Kowalski publicó
resultados más generales sobre programación
lógica ese mismo año [Kow72].
Un programa PROLOG consta de un conjunto
de cláusulas de Horn. Una cláusula se escribe
A ← Bl, ..., Bn, donde A recibe el nombre de
cabeza de la cláusula, y a B1 ...Bn se les llama
premisas o subobjetivos. El programa puede ser
interrogado mediante un predicado-pregunta
consistente en una conjunción Q1, ...,Qm de
predicados atómicos con variables a los que se
denomina objetivos. El significado intuitivo de
la pregunta es: "¿Existen valores de las variables
tales que los objetivos son consecuencia lógica
del programa?". Si la respuesta es afirmativa, el
programa devuelve una posible concreción de
las variables.
PROLOG utiliza una estrategia sencilla de
aplicación de pasos de deducción, que
corresponde a una exploración en profundidad
del árbol de deducciones posibles. Comenzando
por el conjunto de objetivos dados en la
pregunta, PROLOG unifica, en cada paso, el
objetivo en curso con la cabeza de alguna
cláusula y,
Denotacional Un sistema denota un objeto
complejo en un dominio matemático. Estos
objetos son conjuntos definidos recursivamente
a partir de la estructura sintáctica del lenguaje.
Una componente importante de los mismos
suelen ser las trazas, o secuencias de eventos,
que el sistema puede ejecutar. Dos sistemas son
iguales, si denotan al mismo objeto.
Axiomática Se establecen una serie de axiomas
algebraicos que han de verificar los operadores
del lenguaje. Dos sistemas sintácticamente
distintos son iguales, si existe una demostración
utilizando los axiomas y las propiedades
derivadas de los mismos, que transforma uno en
el otro.
Cualquiera de las tres formas produce sistemas
de cálculo con la potencia de las máquinas de
Turing y, por tanto, indecidibles. El uso práctico
de tales modelos para verificar propiedades o
transformar sistemas necesita, pues, importantes
dosis de ingenio [HJF85, JF89, Bae90]. Otra
técnica importante para demostrar la
equivalencia observacional de dos sistemas,
concepto central en el modelo CCS, es la
bisimulación, introducida originalmente por D.
Park en [Par81].
6 La programación lógica
El paradigma de la programación lógica es
también un producto de los 70. Su surgimiento
es consecuencia de una interacción entre el
grupo de Inteligencia Artificial de la
Universidad de Marsella, dirigido por Alain
Colmerauer, y profesores del Departamento de
Lógica Computacional de la Universidad de
Edimburgo, encabezados por Robert Kowalski.
Este último había colaborado en un trabajo
[KK71] que describía el método de resolución
SL para la demostración de teoremas en lógica.
Éste consistía en un refinamiento del principio
de resolución de Robinson [Rob65] que, a su
vez, utilizaba un algoritmo de unificación,
original también de Robinson y publicado en el
mismo trabajo [Rob65]6. El método interesó al
grupo de Marsella, a la sazón ocupado en
desarrollar
una
herramienta
para
el
procesamiento de lenguaje natural. Kowalski
fue invitado a una estancia de varios dias en
Marsella durante el verano de 1971. Según
relata el propio protagonista [Kow88] , esos dias
fueron
. si tiene éxito, elimina el objetivo en curso del
conjunto de objetivos aún sin resolver, e
incorpora a este conjunto las premisas -si las
tiene- de la clausula utilizada. Los objetivos a
resolver y las cláusulas a ensayar se escogen
secuencialmente, según están escritos en el texto
del programa.
. si fracasa, realiza una vuelta atrás
(backtracking), y reconsidera la última
unificación realizada, ensayando nuevas
cláusulas para ese objetivo.
----------------------------------------------------------
17
PROLOG se veía en aquel momento tan solo
como un primer paso hacia la programación
lógica, ya
mismo nivel de detalle con que lo haría en un
programa imperativo. Incluso, es posible que
escriba cláusulas cuya semántica declarativa no
es la adecuada al problema.
que su estrategia inocente de exploración del
árbol da lugar a un sistema incompleto de
deducción. Un sistema completo se basa en la
resolución SLD - Selecting a literal, using a
Linear strategy, restricted to Definite clausesque, en esencia, realiza una selección no
determinista de las cláusulas y de los
subobjetivos. Su completitud fue demostrada
por un doctorando de Kowalski [Hil74]. Sin
embargo, convertirla en un lenguaje de
programación práctico no parecía tarea fácil.
Ello hizo que PROLOG se convirtiera, en la
práctica, en el único representante de la
programación lógica. Por otra parte, se
benefició desde el principio de una muy buena
implementación, gracias a las ideas de D.
Warren [War77]. Éste también modificó la
sintaxis del PROLOG de Marsella, y realizó una
implementación para DEC-10, llamada Prologl0, que se convirtió, de hecho, en un estándar,
conocido hoy como Prolog de Edimburgo
[WPP79].
A los programas lógicos se les puede asignar
dos tipos de semántica: una operacional, que
consiste informalmente en el conjunto de
objetivos sin variables que son resueltos
afirmativamente por el programa, y otra
declarativa, que se define como el modelo
mínimo del programa. Un modelo es un
conjunto de objetivos sin variables que no
contradice el significado lógico de las cláusulas
del programa, es decir, si A ← B1, ..., Bn es una
concreción de una cláusula del programa, y B1,
..., Bn pertenecen al modelo, entonces A ha de
pertenecer al modelo. La semántica declarativa
se puede dar también empleando la teoría de
dominios de Scott y Strachey [SS71]. Es ésta la
aproximación utilizada en el trabajo seminal de
van Emdem y Kowalski [vEK76].
Esta doble visión, operacional y declarativa, da
lugar a una cierta contradicción en la
caracterización de Prolog:
Los aspectos declarativos confieren propiedades
originales a los programas lógicos que lo
diferencian de otros paradigmas: los programas
no devuelven un resultado único, admiten
muchos tipos de preguntas distintas y, en
muchos casos, son invertibles. Por ejemplo, un
programa que concatena dos listas se puede usar
también para generar todas las formas posibles
de partir una lista en dos, o un programa que
ordena una lista se puede usar para generar permutaciones de una lista ordenada. En la base de
estas propiedades está el mecanismo de
unificación, que se comporta de un modo
simétrico con respecto al objetivo a resolver programa "llamante"- y a la cabeza de la
cláusula elegida -programa "llamado". Es, en
cierto modo, un compendio de mecanismos que
aparecen diferenciados en otros lenguajes: paso
de parámetros en ambas direcciones, ajuste de
patrones contra un valor estructurado, y
construcción de valores estructurados a partir de
sus componentes.
Sus capacidades de deducción lógica hicieron
que Prolog fuera seleccionado como el lenguaje
base para el proyecto japonés -hoy abandonadode computadores de la "Quinta Generación".
Este ambicioso proyecto se lanzó a comienzos
de la década de los 80, y debería haber
producido a finales de la misma unos
computadores con interfaces hombre-máquina
que procesarían el lenguaje natural, y con
capacidades lógicas de razonamiento e
inferencia muy potentes. Aunque no tuvo ese
resultado, sí consiguió popularizar Prolog y la
Inteligencia Artificial. Y ello, no sólo en Japón
sino también en el resto de las potencias
industriales que, recelosas de un posible éxito
japonés en sus objetivos, invirtieron grandes
sumas en la investigación en estas áreas. Se
realizaron implementaciones comerciales de
Prolog muy eficientes y el lenguaje se difundió
notablemente en ambientes industriales.
Desplazó a Lisp en muchas aplicaciones de la
Inteligencia Artificial, en particular en la
construcción de los llamados sistemas expertos,
hoy muy extendidos.
Prolog no consiste simplemente en programar
con cláusulas de Horn. Ya desde su concepción,
incorporó una serie de características añadidas
con el fin de obtener un lenguaje de
programación práctico. Una de las más
controvertidas es el llamado operador de corte.
Es una facilidad con la que el programador
puede podar explícitamente una parte del
espacio de búsqueda. Obviamente, cambia la
semántica declarativa del programa ya que se
pueden perder soluciones, pero, cuando no
existen o no interesan tales soluciones, consigue
aumentar notablemente la eficiencia de muchos
. Si se pone el énfasis en el aspecto declarativo,
se obtiene un lenguaje de muy alto nivel que
puede ser usado como lenguaje de
especificación. El programador sólo ha de
preocuparse de expresar en cláusulas la lógica
de su problema. Pero, entonces, es muy
probable que el programa que obtenga no sea
ejecutable, en el sentido de que caerá con
facilidad en una cadena infinita de deducciones, o de que su ineficiencia será
inaceptable.
. Si se pone el énfasis en el aspecto operacional,
el programador ha de ser muy consciente del
orden en que se ejecutan las cláusulas y los
subobjetivos dentro de ellas y, por tanto,
preocuparse por el flujo de control con el
18
relaciones- es más general que la de la
programación funcional -las funciones-, en
muchas partes de un programa lógico se
calculan funciones deterministas.
En esos casos, la búsqueda de soluciones
múltiples es un mecanismo innecesario y
costoso. Por ello, se han hecho numerosos
intentos de combinar ambos paradigmas en un
solo lenguaje. Ello implica, no sólo tener la
posibilidad de definir funciones en un lenguaje
lógico, sino también extender la lógica a orden
superior, incorporar un mecanismo de
resolución en dicha lógica y dar una semántica
apropiada a tales construcciones. En [BL86]
puede encontrarse una clasificación de varias
aproximaciones al problema. Algunos lenguajes
en esta línea de trabajo son: LOGLISP [RS82] ,
EQLOG [GM84], LEAF [BBLM85], BABEL
[MNRA89] Y FLANG [Man91], este último,
combinación de lenguaje funcional y de
lenguaje lógico con restricciones.
programas. Además, es útil para implementar
una forma incompleta de negación llamada
negación mediante fa1lo: el predicado not P(X)
tiene éxito si el predicado P(X) falla, y
viceversa. La semántica de esta construcción fue
estudiada por primera vez en [Cla78]. Otras
características
extralógicas
son
ciertos
predicados aritméticos, la entrada/salida -que se
concibe como un efecto lateral del programa- y
la capacidad de automodificación en ejecución se pueden eliminar o incorporar cláusulas
durante la misma-, hoy afortunadamente en
desuso.
La programación lógica admite una cierta
separación entre los aspectos lógicos y los
aspectos de control. En [Kow79] se aboga por
esta separación, mostrando que un mismo
conjunto de cláusulas admite distintas
estrategias posibles para el control. Una de ellas
es lanzar procesos paralelos que se encarguen de
explorar distintas partes del espacio de
búsqueda. Esta estrategia es, además, completa
ya que, si existe algún nodo con éxito, será
finalmente alcanzado. El inconveniente es que
se exploran en anchura grandes extensiones del
espacio y se tarda más en llegar a las soluciones,
que están ubicadas en las hojas del árbol. Se han
desarrollado numerosos lenguajes concurrentes
que refinan esta idea. Algunos de ellos son
PARLOG [CG83], Concurrent Prolog [Sha83] y
Delta-Prolog [PN84].
Un conjunto de cláusulas sin premisas se puede
considerar como la definición de una serie de
relaciones. La unión, la intersección y la
proyección de relaciones se pueden expresar
fácilmente en un lenguaje lógico. Ello establece
una conexión natural con los modelos
relacionales de bases de datos, lo cual ha dado
lugar a una línea de trabajo consistente en la
incorporación de facilidades lógicas a los
lenguajes de consulta de bases de datos: son las
llamadas bases de datos deductivas [GM78,
GMN84].
Actualmente se está trabajando intensamente en
la llamada programación lógica con
restricciones. Esta línea tiene su origen en
[JL87] y consiste en enriquecer el lenguaje
lógico con ciertos dominios predefinidos (p.e.
booleanos, reales, dominios finitos) y con
relaciones de igualdad, desigualdad, orden, u
otras funciones, en dichos dominios, que pueden
ser resueltas de modo ad-hoc, al margen del
lenguaje lógico. Estas restricciones aumentan a
la vez la expresividad y la eficiencia del
lenguaje.
Los lenguajes funcionales, desarrollados en
paralelo con el paradigma lógico (ver la Sección
7), han aportado una serie de ideas tales como
las funciones de orden superior, las estructuras
infinitas y la técnica de evaluación perezosa, de
las que carece, por lo general, la programación
lógica. Por otra parte, aunque la base
matemática de la programación lógica -las
7 La programación funcional
En la Sección 3 se ha mencionado el lenguaje
Lisp [MAE+62] como precursor de los
lenguajes funcionales. Si es verdad que Lisp ha
supuesto una fuente importante de inspiración
para este paradigma, los fundamentos del
mismo hay que buscarlos en el cálculo lambda
(ver la Sección 1) y en los trabajos de H. B.
Curry y R. Feys [CF58] sobre lógica
combinatoria. Puede citarse a Peter Landin
como el impulsor originario del paradigma
funcional, en unos años - los 60- en los que las
corrientes predominantes eran muy diferentes.
En su trabajo [Lan65], establece la relación
existente entre el modelo computacional del
cálculo lambda y el de los lenguajes imperativos
de alto nivel del momento, proporcionando una
primitiva semántica denotacional para un
amplio subconjunto de Algol 60. Su familia de
lenguajes ISWIM [Lan66] -acrónimo de If you
See What 1 Mean- supone una amplia
separación con respecto a Lisp tanto en la sintaxis como en la semántica. Sus aportaciones
pueden resumirse como sigue:
. Abandono de la sintaxis prefija de Lisp en
favor de la infija.
. Introducción de las cláusulas let y where para
realizar declaraciones locales a otra declaraci6n.
. Énfasis en el razonamiento ecuacional sobre
los programas.
. Máquina abstracta SECD, basada en cuatro
pilas, para interpretar programas funcionales.
Pero la más importante de sus aportaciones fue
su visión de la programación funcional como un
19
paradigma radicalmente distinto del imperativo,
en el que estaba excluida toda noción de estado
o de asignación
A pesar de que FP ha sido extendido
posteriormente, su utilidad principal ha
consistido en servir como lenguaje base para la
construcción de entornos de transformación
destructiva. Más aún, veía su lenguaje como una
sintaxis edulcorada para el cálculo lambda, al
cual eran traducibles todas sus expresiones.
La programación funcional durmió el sueño de
los justos durante más de diez años, debido
quizás a que sus lenguajes eran meros objetos
de laboratorio que no podían competir en
eficiencia con sus hermanos imperativos. Le
sacó de este letargo la conferencia de John
Backus con ocasión de la recepción del premio
Turing [Bac78]. En ella -y dándose la paradoja
de que el premio era debido fundamentalmente
a su protagonismo en el desarrollo de Fortran y
de Algol 60-, arremetió con tremenda
contundencia contra el paradigma imperativo al
que describió como un corsé que impedía a los
programadores pensar con libertad en sus
algoritmos. En particular, la instrucción de
asignación mereció el nombre de cuello de
botella intelectual, ya que obligaba a los
programadores a pensar cómo realizar
importantes cambios en la memoria a base de
"cambiar una palabra cada vez" con dicha
instrucción. Como alternativa, propone el
paradigma
funcional
y
sus
elegantes
propiedades de ausencia de efectos laterales,
razonamiento
ecuacional
y
ricas
transformaciones algebraicas. Para ilustrar estas
ideas, presenta el lenguaje FP y desarrolla con él
numerosos ejemplos. Su conferencia tuvo el
efecto de reactivar y estimular la investigación
en
programación
funcional
aunque,
paradójicamente, las características de FP no
son las que han prevalecido después. Éstas son
las siguientes:
de programas funcionales, fin para el que resulta
muy apropiado.
Fruto del interés hacia la programación
funcional es la secuencia de lenguajes que se
desarrollan
en
diferentes
universidades
británicas a partir de 1978, cada uno añadiendo
una característica novedosa:
Hope Desarrollado en Edimburgo por el equipo
de Rod Burstall [BMS80], incorpora ajuste de
patrones para mejorar la definición de
funciones, funciones de orden superior
definibles por el programador, tipos recursivos
con ajuste de patrones asociado, y tipos
abstractos de datos.
ML Desarrollado también en Edimburgo
[GMM+78], inicialmente como parte del
demostrador de teoremas LCF, y ampliado
posteriormente con el nombre de Standard ML
[Mi184]. Su principal aportación es el sistema
polimórfico de tipos [Mi178], conocido como
sistema de Hindley-Milner, que será después
adoptado por la gran mayoría de los lenguajes
posteriores: También incluye la definición
recursiva de tipos de datos, tipos abstractos,
excepciones, y un elaborado sistema de
módulos.
SASL, KRC El primero (St. Andrews Static
Language), desarrollado en la universidad de St.
Andrews [Tur76] , el segundo (Kent Recursive
Calculator), en la universidad de Kent [Tur81] ,
y ambos del mismo autor, David Turner. Estos
lenguajes aportan un estilo ecuacional para
escribir las definiciones de función y sustituyen
la expresión condicional por la inclusión de
guardas booleanas en las ecuaciones. También
añaden la notación currificada para las
funciones. El segundo de ellos incorpora la
técnica de evaluación perezosa y la definición
abreviada de listas mediante la notación
conjuntista ZF. 7
. Backus pone el acento en que la programación
ha de consistir en combinar un número reducido
de formas funcionales predefinidas. Éstas no
son otra cosa que funciones de orden superior.
Lo que no ha prevalecido es su concepción de
que el programador no debe poder ampliar el
catálogo de las mismas.
Miranda Culminación de los dos anteriores y
también obra de Turner [Tur85, Tur86].
Incorpora el sistema de tipos de Hindley-Milner,
evaluación perezosa, ecuaciones con guardas,
listas ZF, tipos recursivos, tipos abstractos y,
como novedad, secciones y una entrada/salida
completamente funcional. Su implementación es
también original, pues se realiza mediante
traducción a expresiones con sólo dos
combinadores, S y K, utilizando un resultado
teórico de la lógica de combinadores.
. FP es un lenguaje sin tipos. Todos los objetos
son del tipo secuencia, una variedad de lista
simétrica heterogénea. Los lenguajes posteriores tienen disciplina de tipos y sus listas son homogéneas.
. Las funciones FP no declaran sus parámetros
formales. En realidad, toda función toma un
sólo parámetro y devuelve un único resultado,
ambos de tipo secuencia. Esto da a los
programas un aspecto críptico. Aunque es
posible practicar ese estilo en los lenguajes
actuales, la sintaxis de los mismos admite un
estilo más convencional y más legible.
Este conjunto de características -incorporadas
en tan corto espacio de tiempo- cambia
radicalmente el paradigma funcional. En
particular, la combinación
20
---------------------------------------------------------7Llamada así en honor a los matemáticos
Zermelo y Fränkel.
polimorfismo + orden superior + evaluación
perezosa confiere al mismo un nivel de
abstracción muy elevado. La consecuencia es
que escribir algoritmos en un lenguaje funcional
produce un volumen de líneas de código un
orden de magnitud inferior con respecto al
paradigma imperativo:
La evaluación perezosa consiste en evaluar
una expresión sólo cuando su valor es realmente
requerido por el algoritmo y, aún en ese caso,
evaluarla lo menos posible. La estrategia
alternativa se denomina evaluación impaciente,
y es la empleada comúnmente por los lenguajes
imperativos. El uso de esta técnica de
evaluación reporta las siguientes ventajas:
El polimorfismo permite definir algoritmos y
estructuras de datos parametrizados en los que
el tipo de los parámetros puede ser cualquiera.
A diferencia de los mecanismos de genericidad
explicados en la Sección 3, aquí no hay
separación entre la fase de definición y la de
concreción, ni hay que dar un nombre a cada
concreción. Un tipo polimórfico es ya un tipo no un esquema de tipo- y una función
polimórfica es ya ejecutable -en la genericidad
tipo Ada, sólo son ejecutables las concreciones.
Ello hace el mecanismo polimórfico más fácil
de usar. En contrapartida, las construcciones
genéricas admiten operaciones como parte del
parámetro formal y las construcciones
polimórficas no.
l. Programas que no terminan bajo evaluación
impaciente, lo hacen bajo evaluación perezosa.
2. Permite definir funciones no estrictas, es
decir, funciones que pueden dar un resultado
definido aunque algunos de sus parámetros
estén indefinidos.
3. Permite definir estructuras de datos infinitas
(p.e. la lista de todos los números primos).
4. Gracias a ello, es posible plantear la
entrada/salida sin salirse del marco funcional:
los ficheros se contemplan esencialmente como listas infinitas de caracteres que se van
consumiendo y produciendo "perezosamente" a
medida que sus datos son requeridos por el
programa.
5. La programación con objetos infinitos, y en
general con un lenguaje perezoso, liberan al
programador en gran medida del control estricto
del flujo de control. Ello conduce a programas
más concisos y con un grado de generalidad
mayor que el de sus contrapartidas impacientes.
El sistema polimórfico de Hindley-Milner tiene
otras características importantes: existe para el
mismo un algoritmo de inferencia automática
gracias a la existencia de tipos principales: una
expresión, o bien no es tipificable, o si lo es, su
tipo es único. Ello tiene dos consecuencias
beneficiosas: liberar al programador de la
necesidad de declarar explícitamente los tipos, y
permitir que toda la comprobación de tipos sea
estática. El programa compilado no necesita
incluir ninguna información de tipos.
Esta superioridad de la evaluación perezosa ha
sido reconocida por los investigadores [Hug90]
y, a partir de Miranda, los lenguajes funcionales
posteriores son en su mayoría perezosos.
Hacia finales de los 80 se percibía que el
paradigma estaba suficientemente maduro pero
que, no obstante, su impacto en la comunidad
no investigadora era mínimo. Uno de los
obstáculos detectados fue la ausencia de un
lenguaje estándar que, además, reuniera
suficientes cualidades de lenguaje "real", es
decir, amplia variedad de tipos numéricos,
entrada/salida versátil, módulos, librerías, y una
razonable eficiencia. Se emprendió así el
desarrollo de un nuevo lenguaje que recibió el
nombre de Haskell [HW88, HPJW92, HF92] en
honor al matemático Haskell B. Curry
mencionado al comienzo de esta sección. Pero,
esta vez, el desarrollo iba a ser colectivo,
mediante un comité creado al efecto con ocasión
de la conferencia FPCA8 de 1987.
El orden superior permite asociar a cada
estructura de datos un conjunto de funciones
que encapsulan los esquemas recursivos más
frecuentes para tratar dicha estructura. Muchas
funciones sobre la estructura no son sino
concreciones de uno de estos esquemas. El uso
de orden superior permite así ahorrar esfuerzo
de programación y, por tanto, disminuir la
posibilidad de cometer errores.
El caso de las listas es el más conocido: sumar
los elementos de una lista, multiplicarlos, o
calcular la lista inversa, son concreciones de la
función polimórfica de orden superior foldr
cuyo tipo es (a → b → b) → b → [a] → b.
Sustituyendo
adecuadamente
los
tipos
polimórficos a y b por tipos concretos, el
segundo parámetro de foldr por un valor de tipo
b, y la función que constituye su primer
parámetro por una función apropiada de tipo a
→ b → b, se obtienen los algoritmos arriba
expresados.
---------------------------------------------------------8Functional Programming and Computer
Arquitecture. La de 1987 se celebro en Portland
(Oregon, USA) en Septiembre.
21
barroquismo de aquella. Por ejemplo, se puede
programar genéricamente el algoritmo quicksort
utilizando la comparación sobrecargada <=. El
El objetivo, más que innovar, era reunir y
homogeneizar características ya probadas en
otros lenguajes. Sin embargo, durante su
definición tropezaron con un problema
inesperado: los operadores sobrecargados.
Descubrieron que este aspecto se trataba de un
modo ad-hoc en cada lenguaje e incluso de
formas inconsistentes dentro de un mismo
lenguaje. Por ejemplo, la igualdad de valores, es
considerado un operador polimórfico en
Miranda (su tipo, empleando sintaxis de
Haskell, es (==) :: a → a → Bool) aunque no es
aplicable a las funciones ni a los tipos
abstractos. En ML se considera polimórfico con
restricciones, empleando el tipo 'a → 'a → Bool
para indicar este polimorfismo restringido. Sin
embargo,
ML
trata
otros
operadores
sobrecargados (p.e. +, -, *) de un modo distinto:
el lenguaje "sabe" que lo están y la deducción
de tipos es especial en estos casos (p.e. + es a
veces de tipo Int → Int → Int y a veces de tipo
Float → Float → Float). El programador no
puede sobrecargar más estos símbolos, como
tampoco puede sobrecargar la igualdad impidiendo, por ejemplo, que el programador
defina su propia igualdad para los tipos
abstractos, algo que sería razonable poder hacer.
tipo resultante es Ord a => [a] → [a]. Ello hace
utilizable a quiclsort para listas de cualquier tipo
de datos que pertenezca a la clase Ord. Otras
características interesantes de Haskell son las
siguientes:
. Sistema de módulos que permite una
visibilidad controlada de los identificadores por
parte del programador, con directivas para
exportar, importar y reexportar los mismos.
Compilación separada.
. Sofisticada entrada/salida, tanto en modo texto
como en modo binario, a dispositivos convencionales y a ficheros en disco. La versión 1.3
del lenguaje, de Junio de 1995 [Has95], incluye
un modelo de entrada/salida basado en mónadas
[Mog89], que hace más intuitiva al programador
la escritura de sus programas. Este modelo es
resultado de una linea de trabajo reciente
iniciada por Wadler en [Wad92] y continuada
en [PJW93].
. Facilidad para definir tipos abstractos, no
como una construcción especial, sino como una
consecuencia del sistema de módulos: un tipo
abstracto es un tipo algebraico definido en un
módulo, del cual no se exportan sus
constructoras. Como consecuencia, los módulos
usuarios no pueden construir valores del tipo
directamente ni hacer ajuste de patrones sobre
valores del mismo.
La solución vino de la mano de una propuesta
de Philip Wadler y Stephen Blot [WB89] en la
que los operadores sobrecargados se agrupan en
clases de tipos. Así, los operadores +, - y * se
agrupan en la clase Num de los tipos numéricos,
y las operaciones ==, y /= en la clase Eq de los
tipos con igualdad. Por, ejemplo, el tipo de + se
expresa como Num a => a → a → a para
indicar un polimorfismo restringido a los tipos
de la clase Num. La definición de una clase
provee el nombre y el tipo de los operadores, y
algunas ecuaciones opcionales por defecto. Para
incorporar un tipo concreto a una clase, el
programador ha de suministrar una concreción
de la clase -construcción instance- para ese
tipo. En dicha concreción se dan las ecuaciones
que definen, para ese tipo, los operadores
sobrecargados. De este modo, la sobrecarga es
una facilidad general del lenguaje controlable
por el programador. En [WB89] se dan también
las modificaciones necesarias al algoritmo de
inferencia del sistema de tipos de HindleyMilner para tener en cuenta la presencia de
operadores sobrecargados, y una semántica de
traducción que convierte un programa con
operadores sobrecargados en otro tipificable en
el sistema de Hindley-Milner puro.
La inclusión de clases es la característica
singular que más diferencia a Haskell de los
lenguajes precedentes. La combinación de
sobrecarga y polimorfismo produce efectos
comparables a los de la genericidad, pero sin el
. Inclusión de arrays como tipo abstracto
predefinido.
Su
tamaño
se
decide
dinámicamente. Una programación cuidadosa
con arrays junto con un compilador
"inteligente", o el empleo de las técnicas de
programación con mónadas [Hud93, Lau93],
permiten garantizar que los arrays son
actualizados in situ y, por tanto, con coste
constante. Ello abre a la programación funcional
algoritmos y estructuras de datos (p.e. tablas
hash) que eran patrimonio tradicional de la
programación imperativa [NPP95].
Referencias
[Ada79] Preliminary Ada Reference Manual.
SIGPLAN Notices, 14(6A), June 1979.
[Ada83] Reference Manual for the Ada
Programming Language. ANSI/MIL-STD1815A- 1983,1983.
[Ada95] Reference Manual for the Ada
Programming Language. ISO/IEC 8652:1995,
1995.
[AFdR80] K. R. Apt, N. Francez, and W. P. de
Roever. A Proof System for Communicating
22
Sequential Processes. ACM TOPLAS, 2:359385, 1980.
[CG83] K. L. Clark and S. Gregory. PARLOG:
a Parallel Logic Programming Language.
Technical Report 83/5, Imperial College,
London, 1983.
[Cho56] N. Chomsky. Three Models for the
Description of Language. IRE Transactions on
Information Theory, 2(3):113-124, 1956.
[Chu41] A. Church. The Calculi of Lambda
Conversion. Princeton University Press, New
Jersey, 1941.
[AHU83] A. V. Aho, J. E. Hopcroft, and J. D.
Ullman. Data Structures and Algorithms.
Addison- Wesley, 1983.
[AO91] K. R. Apt and E.-R. Olderog.
Verification of Sequential and Concurrent
Programs. Springer- Verlag, 1991.
[Bac78] J. Backus. Can Programming Be
Liberated from the Von Neumann Style? A
Functional Style and Its Algebra of Programs.
Comm. ACM, 21(8):613-641, August 1978.
[Bae90] Applications of Process Algebra.
Cambridge University Press, Cambridge, 1990.
J. C. M. Baeten (editor).
[BBLM85] R. Barbuti, M. Bellia, G. Levi, and
M. Martelli. LEAF: A Language which
integrates Logic, Equations and Functions. In
Logic Programming: Functions, Equations and
Relations. Prentice Hall, 1985. D. DeGroot and
G. Lindstrom (editors).
[BJ66] C. Bohm and G. Jacopini. Flow
Diagrams, Turing Machines and Languages
with only two Formation Rules. Comm. ACM,
9(5), May 1966.
[BK85] J. A. Bergstra and J. W. Klop. Algebra
of Cornmunicating Processes with Abstraction.
Theoretical
Computer
Science,
37:77121,1985.
[BL86] M. Bellia and G. Levi. The Relation
between Logic and Functional Languages.
Journal of Logic Programming, 3:217-236,
1986.
[BMPW86] M. Broy, B. Möller, P. Pepper, and
M. Wirsing. Algebraic Implementations
Preserve Program Correctness. Science of
Computer Programming, 7:35-37, 1986.
[BMS80] R. M. Burstall, D. B. McQueen, and
D. T.
Sannella. HOPE: An Experimental Aplicative
Language. In The 1980 LISP Conference, pages
136-143. Stanford and Santa Clara Universities,
1980.
[Boo91] G. Booch. Object-Oriented Design.
Benjamin/Cummings, 1991.
[BRH84] S. D. Brookes, A. W. Roscoe, and C.
A. R. Hoare. A Theory for Communicating
Sequential Processes. Journal of the ACM,
31:560-599,1984.
[BW84] M. Broy and M. Wirsing. A Systematic
Study of Models of Abstract Data Types.
Theoretical Computer Science, 33: 139-174,
1984.
[Car89] L. Cardelli. Typeful Programming.
DEC SRC Report no. 45, 1989.
[CF58] H. B. Curry and R. Feys. Combinatory
Logics, volume l. North-Holland, 1958.
[CKPR73] A. Colmerauer, H. Kanoui, R.
Pasero, and P. Roussel. Un Systeme de
Communication Homme-Machine en Franaçais.
Technical
report,
Groupe
d'lntelligence
Artificielle, Univ. de Aix-Marseille II, 1973.
[Cla.78] K. L. Clark. Negation as Failure, pages
293-332. Plenum Publishing. See [GM78],
1978.
[CM88] K. M. Chandy a.nd J. Misra. Parallel
Program Design: A Foundation. Addison
Wesley, Reading, Massachusetts, 1988.
[Cox86]
B.
J.
Cox.
Object-Oriented
Programming: An Evolutionary Approach.
Addison-Wesley, 1986.
[CW85] L. Cardelli and P. Wegner. On
Understanding Types, Data Abstraction, and
Polymorphism. Computing Surveys, 17(4):471522, December 1985.
[Dah78] O.-J. Dahl. Can Program Proving be
made Practical? Institute of Informatics.
University of Oslo. Norway, 1978.
[DH72] O.-J. Dahl and C. A. R. Hoare.
Hierarchical Program Structures. In Structured
Programming, pages 175-220. Academic Press,
1972. ver [DHD72].
[DHD72] E. W Dijkstra, C. A. R. Hoare, and
O.-J. Dahl. Structured Programming. Academic
Press Inc., 1972.
[Dij65] E. W. Dijkstra. Solution of a Problem in
Concurrent Programming Control. Comm.
ACM, 8(9), September 1965.
[Dij68a] E. W. Dijkstra. A Constructive
Approach to the Problem of Program
Correctness. BIT, August 1968.
[Dij68b] E. W. Dijkstra. Cooperating Sequential
Processes. In F. Genuys, editor, Programming
Languages, pages 43-112. Academic Press,
1968.
[Dij68c] E. W. Dijkstra. Go-to Statement
Considered Harmful. Comm. ACM, 11(3):147148, March 1968.
[Dij68d] E. W. Dijkstra. The Structure of the
THE Multiprogramming System. Comm. ACM,
11(5):341-346, May 1968.
[Dij71] E. W. Dijkstra. Hierarchical Ordering of
Sequential Processes. Acta Informatica,
1(2):115-138, 1971. Also in Operating System
23
Techniques, Academic Press 1972, C. A. R.
Hoare and R. H. Perrott (editors).
[GHM78a] J. V. Guttag, E. Horowitz, and D.
Musser. Abstract Data Types and Software
Validation. Comm. ACM, 21(12):1048-1064,
December 1978.
[Dij72a] E. W. Dijkstra. The Humble
Programmer. Comm. ACM, 15(10):859-866,
October 1972.
[Dij72b] E. W. Dijkstra. Notes on Structured
Programming. In Structured Programming,
pages 1-82. Academic Press, 1972. ver
[DHD72].
[Dij75] E. W. Dijkstra. Guarded Commands,
Nondeterminacy and Formal Derivation of
Programs. Comm. ACM, 18(8):453-457, August
1975.
[Dij76] E. W. Dijkstra. A Di.fcipline oJ
Programming. Prentice-Hall, 1976.
[DMN70] O.-J. Dahl, B. Myhrhaug, and K.
Nygaard. The Simula 67 Common Base
Language. Norwegian Computing Center, Oslo,
Pub. S-22, 1970.
[DoD60] COBOL, Initial Specifications for a
Common
Oriented
Business
Language.
Department of Defense. Washington D.C., U.S.
Goverment Printing Office, No. 1960 O552133, 1960.
[DoD61] COBOL, Revised Specifications for a
Common
Oriented
Business
Language.
Department of Defense. Washington D.C., U .S.
Goverment Printing Office, No. 1961 O598941, 1961.
[EKMP82] H. Ehrig, H. J. Kreowski, B. Mahr,
and P. Padawitz. Algebraic Implementation of
Abstract Data Types, volume 20 of Theoretical
Computer Science, pages 209-263. NorthHolland,1982.
[EM85] H. Ehrig and B. Mahr. Fundamentals of
Algebraic Specification 1, volume 6 of EATCS
Monographs on Theoretical Computer Science.
Springer-Verlag, 1985.
[FGJM85] K. Futatsugi, J.A. Goguen, J.-P.
Jouannaud, and J. Meseguer. Principles of
OBJ2. Proc. 12th ACM Symp. on Principles of
Programming Languages, pages 52-56, 1985.
New Orleans.
[Flo67] R. Floyd. Assigning Meaning to
Programs. In Actas del American Mathematical
Society Symposium on Applied Mathematics,
pages 19-32,1967.
[Fra86] N. Francez. Fairness. Springer- Verlag,
1986.
[Fra92]
N.
Francez.
Program
Verification. Addison- Wesley, 1992.
[GH86] A. Geser and H. Hussmann.
Experiences with the RAP system, a
specification interpreter combining term
rewriting and resolution. Springer LNCS,
213:339-350, 1986. European Symp. on
Programming.
[GHM78b] J. V. Guttag, E. Horowitz, and D.
Musser. The Design of Data Type
Specifications, volume IV of Current trends in
programming methodology, pages 60-79.
Prentice-Hall, 1978. Data Structuring. R.T. Yeh
(ed.).
[GM78] H. Gallaire and J. Minker. Logic and
Databases. Plenum Publishing, 1978.
[GM84] J. A. Goguen and J. Meseguer.
Equality, Types, Modules and (why not?)
Generics for Logic Programming. Journal of
Logic Programming, 1:179-210, 1984.
[GMM+78] M. Gordon, R. Milner, L. Morris,
M. Ne- wey, and C. Wadsworth. A
Metalanguage for Interactive Proof in LCF. In
5th ACM Symp. on Principles of Programming
Languages, pages 119-130. ACM, 1978.
[GMN84] H. Gallaire, J. Minker, and J. M.
Nicolas. Logic and Databases: A Deductive
Approach. Computing Surveys, 16:153-185,
1984.
[GR83] A. Goldberg and D. Robson. Smalltalk
80: The Language and Its Implementation.
Addison-Wesley, 1983.
[GTW78] J. A. Goguen, J. W. Thatcher, and E.
G. Wagner. An Initial Algebra Approach to the
Specification, Correctness and Implementation
of Abstract Data Types, volume IV of Current
trends in programming methodology, chapter 5,
pages 80-149. Prentice-Hall, 1978. Data
Structuring. R.T. Yeh (ed.).
[GTWW76] J. A. Goguen, J. W. Thatcher, E. G.
Wagner, and J. B. Wright. A Junction Between
Computer Science and Category Theory. Part I:
IBM Research Report RC 4526. Part II: IBM
Research Report RC 5908, 1973/76.
[Gut75] J. V. Guttag. The Specification and
Application to Programming of Abstract Data
Types. Ph.D. thesis. Univ. of Toronto. Dep. of
Computer Science. Report CSRG-59, 1975.
[Han72] P. Brinch Hansen. Structured
Multiprogramming. Comm. ACM, 15(7):574578, July 1972.
[Han73] P. Brinch Hansen. Concurrent
Programming Concepts. Computing Surveys,
3(4):223-245, December 1973.
[Han75] P. Brinch Hansen. The Programming
Language Concurrent Pascal. IEEE Trans. on
Software Engineering, SE-l(2):199-206, June
1975.
[Han76] P. Brinch Hansen. The SOLO
Operating
System: Processes, Monitors and Classes.
Software Practice and Experience, 6:151-164,
1976.
24
[Han77] P. Brinch Hansen. The Arquitecture of
Concurrent Programs. Prentice Hall, 1977.
[Han78] P. Brinch Hansen. Distributed
Processes: A Concurrent Programming Concept.
Comm. ACM, 21(11):934-941, November 1978.
[HPJW92] P. Hudak, S. Peyton-Jones, and P.
Wadler. Report on the Functional Programming
Language Haskell. version 1.2. ACM SIGPLAN
Notices, 27(5), May 1992.
[HS90] E. Horowitz and S. Sahni.
Fundamentals of Data Structures in PASCAL.
Computer Science Press, 3rd edition, 1990.
[Hud93] P. Hudak. Mutable Abstract Data
Types -or- How to Have your State and Munge
It Too. Technical Report RR-914, Dep. of
Computer Science, Yale University, 1993.
[Has95] Report on the Programming Language
Haskell. Version 1.3. FTP anónimo a
ftp.dcs.gla.ac.uk//pub/haskell, June 1995.
[Hen88] M. Hennessy. Algebraic Theory of
Processes. MIT Press, London, 1988.
[Hug90] J.
Hughes.
Why
Functional
Programming Matters, pages 17-43. Research
Topis in Functional Programming. AddisonWesley, 1990. (Ed.) D. A. Turner.
[HF92] P. Hudak and J. H. Fasel. A Gentle
Introduction to Haskell. ACM SIGPLAN
Notices, 27(5), Ma.y 1992.
[Hil74] R. Hill. LUSH Resolution and its
Completeness. Technical Report DCL-78,
School on Artificial Intelligence, Univ. of
Edinburgh, 1974.
[HW73] C. A. R. Hoare and N. Wirth. An
Axiomatic Definition of the Programming
Language PASCAL. Acta Informatica, 2:335355, 1973.
[HJF85] C. A. R. Hoare and H. Ji-Feng.
Algebraic Specification and Proof of Properties
of Communicating Sequential Processes.
Technical Report PRG-52, Oxford University
Computing Laboratory, London, 1985.
[HW88] P. Hudak and P. Wadler. Report on the
Functional Programming Language Haskell.
Technical Report RR-656, Yale University.
Dep. of Computer Science, 1988.
[IBM57] Programmer's Prime for FORTRAN
Automatic Coding System for IBM 704. New
York, IBM Corporation, Form No. 32-03306,
1957.
[HO80] G. Huet and D. Oppen. Equations and
Rewrite Rules: A Survey. In Formal
Languages: Perspectives and Open Problems.
Academic Press, 1980.
[JF89] H. Ji-Feng. Process Simulation and
Refinement. Formal Aspects of Computíng,
1:229- 241,1989.
[JL87] J. Jaffar and J. L. Lassez. Constraint
Logic Programming. In Principles of
Programming Languages, ACM Press, pages
111- 119,1987.
[Hoa68] C. A. R. Hoare. Record Handling. In
Programming Languages, pages 291-347.
Academic Press, 1968. F. Genuys (editor).
[Hoa69] C. A. R. Hoare. An Axiomatic Basis
for Computer Programming. Comm. ACM,
12(10):89-100,1969.
[Hoa72a] C. A. R. Hoare. Notes on Data
Structuring. In Structured Programming, pages
83-174. Academic Press, 1972. ver [DHD72].
[JW74] K. Jensen and N. Wirth. Pascal: User
Manual and Report. Springer Verlag, 1974.
[Kay93] A. Kay. The Early History of
Smalltalk. SIGPLAN Notices, 23(3):69-95,
March 1993.
[Hoa72b] C. A. R. Hoare. Proof of Correctness
of Data Representations. Acta Informatica,
1:271- 281,1912.
[KK71] R. A. Kowalski and D. Kuehner. Linear
Resolution with Selection Function. Artificial
Intelligence, 2:227-260, 1971.
[Hoa72c] C. A. R. Hoare. Towards a Theory of
Parallel Programming. In Operating Systems
Techniques. Academic Press, 1972. C. A. R.
Hoare and R. H. Perrott (editors).
[Kow72] R. A. Kowalski. The Predicate
Calculus as a Programming Language. In Int.
Symp. and Summer School on Mathematical
Foundations of Computer Science, 1972.
[Hoa74] C. A. R. Hoare. Monitors: An
Operating System Structuring Concept. Comm.
ACM, 17(10):549-557, October 1974.
[Hoa78] C. A. R. Hoare. Communicating
Sequential Processes. Comm. ACM, 21:666-677,
1978.
[Hoa81] C. A. R. Hoare. The Emperor's Old
Clothes. Comm. ACM, 24:75-83, 1981.
[Hoa84] C. A. R. Hoare. Programming: Sorcery
or Science? IEEE Software, pages 5-16, April
1984.
[Kow79] R. A. Kowalski. Algorithm = Logic +
Control. Comm .ACM, 22(7):424-436, July
1979.
[Kow88] R. A. Kowalski. The Early Years of
Logic Programming. Comm. ACM, 31(1):38-43,
January 1988.
[KR78] B. W. Kernighan and D. M. Ritchie.
The C Programming Language. Prentice-Hall,
1978.
[Hoa85] C. A. R. Hoare. Communicating
Sequential Processes. Prentice-Hall, London,
1985.
[Lam77] L. Lamport. Proving the Correctness
of Multiprocess Programs. IEEE Trans. on
25
Software Engineering, SE-3(2):125-143, March
1977.
[MAE+62] J. McCarthy, P. W. Abrahams, D.
Edwards, T. Hart, and M. Levin. LISP 1.5
Programmer’s, Manual. MIT Press, Cambridge,
Mas- sachusetts, 1962.
[Lam80] L. Lamport. The "Hoare" Logic of
Concurrent Programs. Acta Informatica, 14:2137, 1980.
[Man91] A. V. Mantsivoda. FLANG: a
Functional Logic Language. In Workshop on
Processing Declarative Klowledge, pages 257270. Springer Verlag, LNAI 567, 1991.
[Lam94] L. Lamport. Temporal Logic of
Actions. ACM TOPLAS, 16(3):872-923, May
1994.
[Mar86] J. J. Martin. Data Types and Data
Structures. Prentice-Hall, 1986.
[McC62] J. McCarthy. Towards a Mathematical
Science of Computation. In Proc. IFIP
Congress, 1962.
[McC78] J. McCarthy. History of LISP.
SIGPLAN Notices, 13:217-223, 1978.
[Mey88] B. Meyer. Object-Oriented Software
Construction. Prentice-Hall, 1988.
[Mey92] B. Meyer. Eiffel: The Language.
Prentice- Hall, 1992.
[Mil78] R. Milner. A Theory of Type
Polymorphism in Programming. Journal of
Computing Systems Science, 17(3):348-375,
1978.
[Mi180] R. Milner. A Calcululus of
Communicating Systems, volume 92 of Lecture
Notes in Computer Science. Springer- Verlag,
Berlin, 1980.
[Mi184] R. Milner. A Proposal for Standard
ML. In Proceedings of the ACM Conf. on Lisp
and Functional Programming, pages 184197,1984.
[Lan65] P. Landin. A Correspondence between
ALGOL 60 and Church Lambda Notation.
Comm. ACM, 8:89-101,158-165, 1965.
[Lan66] P. Landin. The Next 700 Programming
Languages. Comm. ACM, 9(3):157-163, March
1966.
[Lau93] J. Launchbury. Lazy Imperative
Programming. In ACM SIGPLAN Workshop on
State in Programming Languages, June 1993.
[Les83] P. Lescanne. Computer Experiments
with the REVE Term Rewriting Systems
Generator. Proc. 10th ACM Conf. on Principles
of Programming Languages, pages 99-108,
January 1983.
[LG86] B. H. Liskov and J. Guttag. Abstraction
and Specification in Software Development.
MIT Press, 1986.
[Lis72] B. H. Liskov. A Design Methodology
for Reliable Software Systems. In Fall Joint
Computer Conference, pages 191-199, 1972.
[Mil89] R. Milner. Communication and
Concurrency. Prentice-Hall, London, 1989.
[Lis79] B. H. Liskov. Modular Program
Construction Using Abstraction, pages 354-389.
LNCS 86. Springer Verlag, 1979.
[MM82] A. Martelli and U. Montanari. An
Efficient
Unification
Allgorithm.
ACM
TOPLAS, 4(2):258-282, April 1982.
[LR80] B. W. Lampson and D. D. Redell.
Experiences with Processes and Monitors in
MESA. Comm. ACM, 23(2):105-117, February
1980.
[MMS79] G. J. Mitchell, W. Maybury, and R.
Sweet. MESA Language Manual. Technical
Report CSL- 79-3, Xerox Palo Alto Research
Center, 1979.
[LS84] L. Lamport and S. B. Schneider. The
“Hoare” logic of CSP and all that. ACM
TOPLAS, 6(2):281-296, April 1984.
[MNRA89] J. J. Moreno-Navarro and M.
Rodriguez- Artalejo. BABEL: A Functional and
Logic Programming Language Based on
Constructor Discipline, and Narrowing. In Conf.
on Algebraic and Logic Programming, pages
223-232. Springer Verlag, LNCS 343, 1989.
[LSAS77] B. H. Liskov, A. Snyder, R.
Atkinson, and C. Schaffert. Abstraction
Mechanisms in CLU. Comm. ACM, 20(8):564576, August 1977.
[LW69] P. Luca.s and K. Walk. On the formal
description of PL/I. Annual Review on
Automatic Programming, 6:105-182, 1969.
[Mog89] E. Moggi. Computational Lambda
Calculus and Monads. In Logics in Computer
Science. IEEE, 1989.
[Mor73] J. B. Morris. Types are not Sets. In
Actas ACM Symposium on Principles of
Programming Languages, 1973.
[LZ74] B. H. Liskov and S.N. Zilles.
Programming with Abstract Data Types. ACM
SIGPLAN Notices, 9(4):50-60, 1974.
[MP92] Z. Manna and A. Pnueli. The Temporal
Logic of Reactive and Concurrent Systems.
Springer- Verlag, 1992.
[LZ75] B. H. Liskov and S. N. Zilles.
Specification Techniques for Data Abstraction.
IEEE Trans. on Software Engineering, SEl(1):7- 18, March 1975.
[MY80] T. W. Mao and R. T. Yeh.
Communication Port: A Language Concept for
26
Symp. on Principles of
Languages, pages 71-84, 1993.
Concurrent Programming. IEEE Trans. on
Software Engineering, SE-6(2):194-204, March
1980.
Programming
[PN84] L. M. Pereira and R. Nasr. Delta-Prolog:
A Distributed Logic Programming Language. In
Int. Conf. on Fifth Generation Computer
Systems, pages 283-291, 1984.
[Pnu77] A. Pnueli. The Temporal Logic of
Programs. In 18th Symp. on the Foundations of
Computer Science, pages 46-57, November
1977.
[RBP+91] J. Rumbaugh, M. Blaha, W.
Premerlani, F. Eddy, and W. Lorensen. ObjectOriented Modeling and Design. Prentice-Hall,
1991.
[Rob65] J. A. Robinson. A Machine-Oriented
Logic Based on the Resolution Principle.
Journal of the ACM, 12:23-41, Januuy 1965.
[RS82] J. A. Robinson and E. E. Sibert.
LOGLISP - An Alternative to PROLOG.
Machine Intelligence, 10:399-419, 1982.
[SF89] G. Springer and D. P. Friedman. Scheme
and the Art of Programming. MIT Press, 1989.
[Sha83] E. Shapiro. A Subset of Concurrent
Prolog and its Interpreter. Technical Report TR003, ICOT Institute for New Generation
Computer Technology, Tokyo, 1983.
[SS71] D. S. Scott and C. Strachey. Towards a
Mathematical
Semantics
for
Computer
Languages. In Symp. on Computers and
Automata. Polytechnic Institute of Brooklyn
Press, pages 19-46, 1971.
[Str86a] B. Stroustrup. The C++ Programming
Language. Addison-Wesley, 1986.
[Str86b] B. Stroustrup. An Overview of C++.
SIGPLAN Notices, 21(10):7-18, October 1986.
[Tur36] A. M. Turing. On Computable Numbers
with
an
Application
to
the
Entscheidungsproblem. Proceedings of the
London Mathematical Society, 42:230-265,
1936.
[Tur37] A. M. Turing. Computability and λdefinability. Journal on Symbolic Logic, 2:153163, 1937.
[Tur76] D. A. Turner. SASL Language Manual.
Te- chnical Report. University of ST. Andrew.,
1976.
[Tur81] D. A. Turner. The Semantic Elegance
of Aplicative Languages. In 1981 Conf. on
Functional Programming and Computer
Architecture, pages 85-92, 1981.
[Tur85] D. A. Turner. Miranda: A Non-Strict
Functional Language with Polymorphic Types,
pages 1-16. LNCS 201. Springer-Verlag, Berlin,
1985.
[Tur86] D. A. Turner. An Overview of Miranda.
ACM SIGPLAN Notices, 21(12):158- 166, Dec.
1986.
[Nau60] Report on tbe Algorithmic Language
ALGOL 60. Comm. ACM, 3(5):299-314, May
1960. P. Naur et als. (editors).
[Nau63] Revised Report on the Algorithmic
Language ALGOL 60. Comm. ACM, 6(1):1-17,
Ja- nuary 1963. P. Naur et als. (editors).
[Nau66] P. Naur. Proof of Algorithms by
General Snapshots. BIT, 6:310-316, 1966.
[NHN78] R. Nakajima, M. Honda, and H.
Nakahara. Describing and Verifying Programs
with Abstract Data Types. In Formal
Description of Programming Concepts. North
Holland, 1978.
[NPP95] M. Núñez, P. Palao, and R. Peña. A
Second Year Course on Data Structures based
on Functional Programming. In LNCS 1022,
pages 65-84. Springer- Verlag, 1995. FPLE'95,
Nijmegen (The Netherlands).
[Occ84] Occam Programming Manual. Prentice
Hall, 1984.
[OG76] S. S. Owicki and D. Gries. Verifying
Properties of Parallel Programs: An Axiomatic
Approach. Comm. ACM, 19(5):279-285, May
1976.
[OL82] S. S. Owicki and L. Lamport. Proving
Liveness Properties of Concurrent Programs.
ACM TOPLAS, 4(3):455-495, July 1982.
[ONS92] F. Orejas, M. Navarro, and A.
Sánchez. Implementation and Behavioural
Equivalence: A Survey, volume 665 of LNCS,
pages 93-125. Springer-Verlag, 1992. 8th
Workshop on Specifications of Abstract Data
Types. 3rd COMPASS Workshop.
[Owi75] S. S. Owicki. Axiomatic Proof
Techniques for Parallel Programs. Technical
Report TR- 75-251. Doctoral Dissertation, Dep.
Computer Sience, Cornell University, 1975.
[Par72a] D. L. Parnas. On the Criteria to be
used in Decomposing Systems into Modules.
Comm. ACM, 15(12):1053-1058, December
1972.
[Par72b] D. L. Parnas. A Technique for
Software Module Specification with Examples.
Comm. ACM, 15(5):330-336, May 1972.
[Par74] D. L. Parnas. On a "Buzzword":
Hierarchical Structure. In IFIP Proceedings,
pages 336-339,1974.
[Par81] D. Park. Concurrency and Automata on
Infinite Sequences. In E. H. L. Aarts, J. van
Leeuwen, and M. Rem, editors, Proceedings 5th
GI Conf. of Theoretical Computer Science,
volume LNCS 104, pages 245-251. SpringerVerlag, 1981.
[PJW93] S. L. Peyton-Jones and P. Wadler.
Imperative Functional Programming. In ACM
27
[vEK76] M. H. van Emdem and R. A.
Kowalski. The Semantics of Predicate Logics as
a Programming Language. Comm. ACM,
23(4):733-742, October 1976.
[Wad92] P. Wadler. The Essence of Functional
Programming. 19th Symp. on Principles of
Programming Languages, January 1992.
[War77] D. H. D. Warren. Implementing Prolog
- Compiling Logic Programs. Technical Report
30 and 40, Univ. of Edinburgh, 1977.
[WB79] J. Welsh and D. W. Bustard. PascalPlus- Another Language for Modular
Multiprogramming. Software Practice and
Experience, 9:947-957,1979.
[WB89] P. L. Wadler and S. Blot. How to Make
ad-hoc Polymorphism less ad-hoc. In Proc 16th
ACM Symposium on Principles of Programming
Language, Austin Texas, pages 60-76, 1989.
[Weg72] P. Wegner. The Vienna Definition
Language. Computing Surveys, 4:5-63, March
1972.
[Wij69] Report on the Algorithmic Language
ALGOL 68. Numerishe Mathematik, 14(2):79218, February 1969. A. Van Wijngaarden
(editor).
[Wir66] N. Wirth. A Contribution to the
Development of ALGOL. Comm. ACM,
9(6):413- 431, June 1966.
[Wir71a] N. Wirth. Program Development by
Stepwise Refinement. Comm. ACM, 14(4):221227, April 1971.
[Wir71b] N. Wirth. The Programming
Language PASCAL. Acta Informatica, 1:35-73,
1971.
[Wir77] N. Wirth. Modula: A Language for
Modular Multiprogramming. Software Practice
and Experience, 7:3-35, July 1977.
[Wir82] N. Wirth. Programming in Modula-2.
Springer-Verlag, 1982.
[Wir88] N. Wirth. The Programming Language
Oberon. Software Practice and Experience,
18:671-690,1988.
[Wir90] M. Wirsing. Algebraic Specification. In
J. van Leeuwen, editor, Handbook of
Theoretical Computer Science. North Holland,
1990.
[WLS76] W. A. Wulf, R. London, and M.
Shaw. An Introduction to the Construction and
Verification of ALPHARD Programs. IEEE
Trans. on Software Engineering, SE-2:253264,1976.
[WPP79] D. H. D. Warren, F. Pereira, and L. M.
Pereira. User's Guide to DECsystem-10 Prolog.
Technical Report 15, Dep. of Artificial
Intelligence, Univ. of Edinburgh, 1979.
28