PDF de programación - Programacion Funcional en LISP

Programación Funcional

en LISP

Lógica para Ciencias de la Computación

Primer Cuatrimestre de 2009

– Material Adicional –

Introduccióónn
Introducci

A lo largo de la carrera estudiaremos
diversos paradigmas de programación:

Programación Orientada a Objetos.
Programación Lógica.
Programación Funcional.

En esta clase, abordaremos uno de los
lenguajes que pertenecen al paradigma
funcional, el lenguaje LISP.

2

Origen
Origen

LISP se originó en la década del ‘50, de la
mano de John McCarthy.
Se trata de un lenguaje maduro, aplicable a
diversos escenarios, tales como:

Robótica.
Inteligencia Artificial.
Procesamiento de lenguaje natural.
Demostración automática de teoremas.

3

Principales Caracteríísticas
sticas
Principales Caracter

La característica principal de LISP es que
todo programa consiste de una función.
Otras peculiaridades:

No posee asignaciones.
Su principal estructura de control es la recursión.
Los programas y los datos son equivalentes.
Su principal estructura de datos es la lista.
La memoria es asignada por demanda.

4

LISP vs. LISP Puro
LISP vs. LISP Puro

LISP incorpora ciertos vicios tomados del
paradigma imperativo, que permiten expresar
aspectos ajenos al paradigma funcional.
El subconjunto de LISP netamente funcional
se lo suele denominar LISP puro.
En lo que resta, nos concentraremos
exclusivamente en LISP puro.

5

Expresiones en LISP
Expresiones en LISP

Todo programa es una s-expresión.

Las s-expresiones pueden ser átomos o listas.

Un átomo puede ser un átomo numérico o un
átomo simbólico.

Una lista es una secuencia de s-expresiones
delimitadas por paréntesis, con sus elementos
separados por espacios en blanco.

6

Representacióón de
n de
Representaci
Funciones
Funciones

La aplicación de una función LISP se nota
en forma prefija, mediante una lista:

La función f aplicada a los argumentos a1, a2,
a3, …, an, se denota (f a1 a2 a3 … an), en vez
del usual f(a1, a2, a3, …, an).

Por ejemplo, la suma de 2 con el producto de 5 y
-3 se denota como:
átomos simbólicos

(+ 2 (* 5 -3))

átomos
numéricos

7

Evaluacióón de
n de
Evaluaci
ss--expresiones
expresiones

Como vimos antes, es posible expresar aplicaciones
anidadas de funciones.
Básicamente, el intérprete de LISP evalúa una
s-expresión S, representando posiblemente
aplicaciones anidadas de funciones, de la siguiente
forma:

Si S es un átomo numérico a, entonces el resultado
es simplemete dicho átomo numérico a.
Si S es de la forma (f a1 a2 a3 … an), entonces el
intérprete evalúa recursivamente cada argumento ai,
obteniendo valores v1, v2, …, vn y luego calcula el
resultado de aplicar f a dichos valores.

8

Funciones Aritmééticas
ticas
Funciones Aritm

LISP cuenta, entre otras, con las siguientes
funciones aritméticas:

(+ Arg1 Arg2 … Argn)
(- Arg1 Arg2 … Argn)
(* Arg1 Arg2 … Argn)
(/ Arg1 Arg2 … Argn)
(1+ Arg)
(1- Arg)
(MAX Arg1 Arg2 … Argn)
(MIN Arg1 Arg2 … Argn)

9

QUOTE: “ ` ”
QUOTE:

Como dijimos anteriormente, cuando LISP evalúa una
aplicación, evalúa recursivamente cada argumento de la
misma.

Existen situaciones en las que resulta fundamental evitar la
evaluación de ciertos argumentos en una aplicación.

Por ejemplo, cuando dichos argumentos son listas, pero que
no denotan la aplicación de una función sino simplemente
una lista de elementos como estructura de datos.

A tal efecto, LISP cuenta con la función QUOTE de aridad 1.

10

Funcióón QUOTE:
Funci

n QUOTE: “ ` ”

Sintaxis:

(QUOTE Arg)
o simplemente puede abreviarse ’Arg

Esta función evita que se evalúe su argumento, y
lo retorna intacto como resultado.

> (+ 1 2)
3
> (2 3 5)
ERROR: 2 no es una
función

> `(+ 1 2)
(+ 1 2)
> `(2 3 5)
(2 3 5)

( )
o (QUOTE (+ 1 2))

11

Funcióón EVAL
n EVAL
Funci

EVAL tiene el efecto contrario que la
función QUOTE.

(EVAL Arg) fuerza una evaluación adicional
de su argumento Arg.
Ejemplo:

> (QUOTE (+ 2 2))
(+ 2 2)

> (EVAL (QUOTE (+ 2 2))
4

12

Funciones Elementales
Funciones Elementales

sobre Listas
sobre Listas

LISP dispone de las siguientes funciones
para manipular listas:

(CAR List) Retorna el primer elemento de la
lista List.
(CDR List) Retorna la cola de la lista List.

Por ejemplo:
> (CAR `(1 2 3))
1
> (CDR `(1 2 3))
(2 3)

13

Constructores de Listas
Constructores de Listas

Como las listas desempeñan un papel
central en LISP, existen múltiples formas de
construir una lista:

(APPEND List1 List2 … Listn) Esta función
concatena las listas List1, List2, …, Listn.
(CONS Elem List) Retorna una lista cuyo
primer elemento es Elem y cuya cola es List.
(LIST Elem1 Elem2 … Elemn) Esta función
retorna una lista formada por los elementos
Elem1, Elem2, …, Elemn.

14

ÁÁtomos Especiales
tomos Especiales

En LISP, los siguientes átomos presentan
un comportamiento especial.

T (verdadero).
NIL (falso, indefinido, lista vacía).
Números en punto fijo.
Números en punto flotante.

Estos átomos son idempotentes con
respecto a la evaluación.

La sobrecarga de significados de NIL constituye

un aspecto cuestionable del lenguaje.

15

Predicados en LISP
Predicados en LISP

Un predicado puede representarse en LISP
como una función que retorna un valor de
verdad.
Se adopta la convención de que NIL denota
falso, y que cualquier otra s-expresión
denota verdadero.
Por ejemplo:

NIL equivale a falso.
T equivale a verdadero.
(+ 2 2) equivale a verdadero.

16

Predicados en LISP
Predicados en LISP

LISP dispone de diversos predicados:

(ATOM Arg)
(EQUAL Arg1 Arg2)
(MEMBER Elem List)
(ZEROP Arg)
(MINUSP Arg)
(< Arg1 Arg2 … Argn)
(= Arg1 Arg2 … Argn)
(> Arg1 Arg2 … Argn)

17

Predicados Lóógicos
gicos
Predicados L

LISP también cuenta con los predicados lógicos
tradicionales:

(NOT Arg) Retorna T si, y sólo si, la valuación de Arg
es NIL. En caso contrario retorna NIL.
(AND Arg1 Arg2 … Argn) Evalúa sus argumentos de
izquierda a derecha. Si encuentra alguno que evalúa a
NIL, retorna NIL, pero si todos evalúan a algo distinto a
NIL retorna el último valor obtenido.
(OR Arg1 Arg2 … Argn) Análoga a la anterior, sólo
retorna NIL cuando todos sus argumentos evalúan a
NIL, retornando en caso contrario el valor del primer
argumento que evalúe a algo distinto a NIL.

18

Funcióón Condicional
n Condicional
Funci

Una de las funciones más importantes es la función
condicional, pues recordemos que la principal estructura
de control en LISP es la recursión:

(COND (Test1 Result1)
(Test2 Result2)
(Testn Resultn))



Esta función va evaluando las diferentes condiciones. En
caso de encontrar algún Testk que evalúe a algún valor
distinto de NIL, retorna la evaluación de Resultk.
Como particularidad, en caso de que todas las
condiciones evalúen a NIL, entonces retornará NIL.
Si las condiciones Testi son exhaustivas, entonces se
suele reemplazar la última (Testn) por T.

19

Definicióón de Funciones
n de Funciones
Definici

Como los datos y programas no difieren entre sí,
incluso la definición de nuevas funciones es
llevada a cabo mediante la invocación de una
función:

(DEFUN FunctionName (Par1 Par2 … Parn)

FunctionDescription)

Esta función define una función de nombre
FunctionName, con argumentos Par1, Par2, …,
Parn, cuyo comportamiento sigue la descripción
FunctionDescription.

20

Definicióón de Funciones
n de Funciones
Definici

La función DEFUN presenta un comportamiento
especial, a saber:

No evalúa sus argumentos.
Retorna como resultado el nombre el la función que
acaba de ser definida.
El nombre de la función debe ser un átomo simbólico.

Ejemplo: definición de la función suc.

(DEFUN suc (N)

(+ N 1)

)

21

Ejemplos
Ejemplos

Ejemplo: definición de la función factorial.

(DEFUN factorial (N)

(COND

((ZEROP N)
(T

1)
(*

)

)

)

)

N
(factorial (- N 1))

22

Ejemplos
Ejemplos

Ejemplo: definición de la función fibo.

(DEFUN fibo (N)

(COND

((< N 2)
(T

1)
(+

)

)

)

)

(fibo (- N 1))
(fibo (- N 2))

23

Ejemplos
Ejemplos

Ejemplo: definición de la función largo.

(DEFUN largo (L)

(COND

((NULL L) 0)
(T

(+ 1 (largo (CDR L))))

)

)

24