PDF de programación - Introducción al lenguaje Haskell

Introducción al lenguaje

Haskell

Jose E. Labra G.

e-mail: [email protected]

http://lsi.uniovi.es/~labra

Octubre 1998

Universidad de Oviedo
Departamento de Informática

Introducción al lenguaje Haskell

1.- Introducción

Haskell es un lenguaje funcional puro, de propósito general, que incluye muchas de las
últimas innovaciones en el desarrollo de los lenguajes de programación funcional, como son las
funciones de orden superior, evaluación perezosa, tipos polimórficos estáticos, tipos definidos
por el usuario, encaje por patrones, y definiciones de listas por comprehensión.

Incorpora, además, otras características interesantes como el tratamiento sistemático de la
sobrecarga, la facilidad en la definición de tipos abstractos de datos, el sistema de
entrada/salida puramente funcional y la posibilidad de utilización de módulos.

El contenido de este cuaderno se divide en dos partes, en la primera se introduce el modelo
funcional indicando sus ventajas respecto al modelo imperativo sin referirse a ningún lenguaje
funcional en concreto. En la segunda parte se describe el lenguaje Haskell y sus principales
características.

Se utiliza como referencia el entorno de programación Hugs y se supone que el lector tiene
unos mínimos conocimientos del modelo de programación imperativo o tradicional.

Referencias: Aunque al final de estos apuntes se incluye una bibliografía consultada para su
realización, las principales fuentes han sido el manual "An Introduction to Gofer" de Mark
P. Jones incluido en la distribución del sistema Gofer y el artículo "A gentle Introduction to
Haskell" de P. Hudak.

1

Introducción al lenguaje Haskell

2.- Introducción a la Programación funcional
2.1.-Crisis del Software

A principios de la década de los setenta aparecieron los primeros síntomas de lo que se ha
denominado crisis del software. Los programadores que se enfrentan a la construcción de
grandes sistemas de software observan que sus productos no son fiables. La alta tasa de
errores conocidos (bugs) o por conocer pone en peligro la confianza que los usuarios
depositan en sus sistemas.

Cuando los programadores quieren corregir los errores detectados se enfrentan a una dura
tarea de mantenimiento. Cuando se intenta corregir un error detectado, una pequeña
modificación trae consigo una serie de efectos no deseados sobre otras partes del sistema
que, en la mayoría de las ocasiones, empeora la situación inicial.

La raíz del problema radica en la dificultad de demostrar que el sistema cumple los
requisitos especificados. La verificación formal de programas es una técnica costosa que en
raras ocasiones se aplica.

Por otro lado, el incremento en la potencia de procesamiento lleva consigo un incremento en
la complejidad del software. Los usuarios exigen cada vez mayores prestaciones cuyo
cumplimiento sigue poniendo en evidencia las limitaciones de recursos y la fragilidad del
sistema.

Las posibles soluciones podrían englobarse en las siguientes líneas de investigación:
• Ofrecer nuevos desarrollos de la Ingeniería del Software que permitan solucionar el
problema del Análisis y Diseño de grandes Proyectos Informáticos. Actualmente las
Metodologías Orientadas a Objetos han aportado una evolución importante dentro de este
campo.

• Proporcionar Sistemas de Prueba y Verificación de programas cuya utilización no sea

costosa.

• Construir técnicas de Síntesis de Programas que permitan obtener, a partir de unas

especificaciones formales, código ejecutable.

• Diseñar nuevas Arquitecturas de Computadoras, en particular, técnicas de procesamiento

en paralelo.

• Proponer un modelo de computación diferente al modelo imperativo tradicional.

Esta última solución se basa en la idea de que los problemas mencionados son inherentes al
modelo computacional utilizado y su solución no se encontrará a menos que se utilice un
modelo diferente. Entre los modelos propuestos se encuentra la programación funcional o
aplicativa, cuyo objetivo es describir los problemas mediante funciones matemáticas puras sin
efectos laterales, y la programación lógica o declarativa, que describe los problemas
mediante relaciones entre objetos.

2

Introducción al lenguaje Haskell

2.2.-Problemas del Modelo imperativo

Los lenguajes de programación tradicionales como Pascal, C, C++, ADA, etc. forman una
abstracción de la máquina de Von-Neumann caracterizada por:

• Memoria Principal para almacenamiento de datos y código máquina.
• Unidad Central de Proceso con una serie de registros de almacenamiento temporal y un
conjunto instrucciones de cálculo aritmético, modificación de registros y acceso a la
Memoria Principal.

Máquina de Von Neumann

Programa Imperativo

Unidad Central

de Proceso

Datos

+

Instrucciones

Máquina

Memoria Principal

Abstracción

Datos Globales

Compilación

+

Secuencia de
Comandos

Figura 1. Modelo imperativo

Los programas imperativos poseen una serie de datos globales y una secuencia de comandos
ó código. Estos dos elementos forman una abstracción de los datos y código de la memoria
principal. Para hacer efectiva dicha abstracción se compila el código fuente para obtener
código máquina. El modelo imperativo ha tenido un gran éxito debido a su sencillez y
proximidad a la arquitectura de los computadores convencionales.

El programador trabaja en un nivel cercano a la máquina que le permite generar programas
eficientes. Con esta proximidad aparece, sin embargo, una dependencia entre el algoritmo y la
arquitectura que impide, por ejemplo, utilizar algoritmos programados para arquitecturas
secuenciales en arquitecturas paralelas.

Los algoritmos en lenguajes imperativos se expresan mediante una secuencia de órdenes
que modifican el estado de un programa accediendo a los datos globales de la memoria.

Las instrucciones de acceso a los datos globales destruyen el contenido previo de un dato
asignando un nuevo valor. Por ejemplo, la instrucción x:=x+1 incrementa el valor anterior
de x de forma que la siguiente vez que se acceda a x, su valor ha cambiado. Las asignaciones

3

Introducción al lenguaje Haskell

producen una serie de efectos laterales que oscurecen la semántica del lenguaje. Considérese
el siguiente programa en un lenguaje imperativo1:

Program Prueba;
VAR
flag:BOOLEAN;

FUNCTION f (n:INTEGER):
INTEGER;
BEGIN
flag := NOT flag;
IF flag THEN f := n;
ELSE f := 2*n
END;

--- Programa Principal
BEGIN
flag:=TRUE;
...
WRITE( f(1) );
WRITE( f(1) );
...
WRITE( f(1) + f(2) );
WRITE( f(2) + f(1) );
...
END.

Figura 2: Programa imperativo

<- Escribe 2
<- Escribe 1

<- Escribe 4
<- Escribe 5

La expresión f(1) toma diferentes valores dependiendo de la secuencia de ejecución. No se
cumplen propiedades matemáticas simples como la propiedad commutativa, en el ejemplo,
f(1) + f(2) no es igual a f(2) + f(1). Es difícil demostrar la corrección de un
programa cuando no se cumplen este tipo de propiedades. Además, al no tener el mismo
valor, no es posible evaluar en paralelo f(1) con f(2) y sumar el resultado.

Las asignaciones dificultan, por tanto, el estudio de la corrección de un programa e impiden
que el compilador puede realizar evaluaciones en paralelo. Además, el compilador tiene
graves problemas para optimizar código con asignaciones destructivas. Considérese, por
ejemplo, la sentencia

z := (2*a*y+b)*(2*a*y+c);

La expresión a la derecha de la asignación contiene una subexpresión común "2*a*y".
Muchos compiladores eliminarían
la evaluación redundante de ambas expresiones
substituyendo la asignación original con

t := 2*a*y;
z := (t+b)*(t+c);

Sin embargo, no siempre es posible realizar dicha substitución cuando intervienen
asignaciones. Considérese, por ejemplo:

y := 2*a*y + b;
z := 2*a*y + c;

De nuevo aparece una subexpresión común. Sin embargo, si se intenta cambiar el código con

t := 2*a*y;
y := t + b;
z := t + c;


1Por motivos didácticos, se ha elegido un lenguaje similar al Pascal, con la sentencia return.

4

Introducción al lenguaje Haskell

el resultado no es equivalente. El problema radica en que el valor de y ha cambiado durante la
primera asignación.

Aunque es posible que un compilador analice el código para detectar cuándo es posible
realizar este tipo de substituciones, dicho análisis resulta complicado y se realiza en escasas
ocasiones.

2.3.-Modelo Funcional

El modelo funcional, tiene como objetivo la utilización de funciones matemáticas puras sin
efectos laterales y, por tanto, sin asignaciones destructivas.

El esquema del modelo funcional es similar al de una calculadora. Se establece una sesión
interactiva entre sistema y usuario: el usuario introduce una expresión inicial y el sistema la
evalúa mediante un proceso de reducción. En este proceso se utilizan las definiciones de
función realizadas por el programador hasta obtener un valor no reducible.

Programador

Usuario

Escrito

(Definiciones de

función)

Expresión

Valor

Evaluador
(Intérprete/
Compilador)

Evaluación

Figura 3: Modelo funcional

El valor que devuelve una función está únicamente determinado por el valor de sus argumentos
consiguiendo que una misma expresión tenga siempre el mismo valor (esta propiedad se
conoce como transparencia referencial). Es más sencillo demostrar la corrección de los
programas ya que se cumplen propiedades matemáticas tradicionales como la propiedad
commutativa, asociativa, etc.

El programador se encarga de definir un conjunto de funciones sin preocuparse de los
métodos de evaluación que posteriormente utilice el s