21045-71298-1-PB

7/14/2019 21045-71298-1-PB

http://slidepdf.com/reader/full/21045-71298-1-pb 1/11

,

PROGRAMACION

FUNCIONAL

yLAMBDAr

CALCULO

Jonatán Gómez Perdomo* -Wilson Castro Rojas** - Alexander Cardona López

Ingenieros de Sistemas

Universidad Nacional de Colombia, Santafé de Bogotá.

Resumen

En laprimera parte de este artículo se explicanalgunos conceptos de los lenguajes deprogramación, haciendo énfasis en las caracteristicasy propiedades de los lenguajes de programaciónfuncional. En la segunda, se realiza una introducción

al lambda cálculo puro, su notación, axiomas y reglaselementales.

INTRODUCCIÓN

El manejo que se le da a las funciones en loslenguajes imperativos hace muy complicado (o

*Docente de la Universidad Nacional de Colombia

**Docente Ocasional Universidad Nacional de Colombia

INGENIERÍA E INVESTIGACIÓN

imposible) realizar operaciones quematemáticamenteson importantes, tales como la composición defunciones. Los lenguajes funcionales surgen comouna forma de llenar este vacío, dándoles a lasfunciones un valor de primer orden, gracias a lo

cual éstas pueden tratarse como cualquier dato,permitiéndose incluso utilizar una función comoparámetro de otra función.

Un programa desarrollado en lenguajefuncional se denomina programa funcional. Unprograma funcional se explica como un conjunto decomposición reiterada de funciones que resuelvenlos problemas en un estilo particular. Un programafuncional puede escribirse en varios lenguajes comoLISP, SML, Miranda, SCHEME (dialecto de LISP) y

7/14/2019 21045-71298-1-PB


otros. La implementación de lenguajes funcionalesconlleva la construcción de una sintaxis y semánticafáciles de definir a partir del cálculo lambda. Si un

lenguaje funcional permite realizar asignación yevaluación de expresiones no es puro, de otra formaes puro.

El cálculo lambda permite estudiar laspropiedades de las funciones, de tal forma que seconstituye en la teoría que formaliza los lenguajesfuncionales, facilitando la rigurosa evaluación yprueba de expresiones. La forma elemental de ver elcálculo lambda puro es: Ax.M que constituyen lasllamadas abstracciones, donde x es el parámetro dela función y M el cuerpo. MN es la aplicación de la

funciónMaN Visto como una gramática de términos

es M:=x l (M¡M 2J I (Ax .MJ .

I.S IN TAXIS Y S EMÁNT ICA

En ciencias de la computación uno de losfundamentos para el desarrollo de lenguajes deprogramación consiste en el estudio de la forma deescribir los programas y el significado einterpretación de los mismos.

A. Forma deBackus - Naur

Todos los elementos que componen unlenguaje, junto con sus relaciones, hacen deducirun conjunto de reglas que lo determinan. Lossímbolos atómicos de un lenguaje se conocen comocomponentes léxicos o símbolos terminales; lossímbolos no terminales son llamados constructoresdeun lenguaje. El símbolo no terminal que representaal constructor principal de un lenguaje se denominasímbolo no terminal inicial.

Una de las gramáticas independientes decontexto más usadas para especificar la sintaxis deun lenguaje de programación es la gramática BNF(Backus-Naur Form), la cual se muestra en elsiguiente ejemplo:

Ejemplo:

Describir la sintaxis de los números realescomo 3.14159 con una parte entera, un punto decímaly una parte fraccionaria.

Los números reales pOSltlVOS puedendefinirse por las siguientes reglas:

• Un número real positivo está formado pordos secuencias de dígitos separadas porun punto. La primera es finita.

• Una secuencia de dígitos está compuestapor uno o más dígitos.

• UndígitoesO,I,2,3,4,5,6,7,8 ó 9.

UsandoBNF:

<número-real> ::= <secuencia-dígitos>.<secuencia-dígitos>

<secuencia-dígitos> ::= <dígitoc+cdlgito>

<secuencia-dígitos><dígito> ::= 0111213141516171819

en donde

< > : encierran variables representandoconstructores

: se lee como "es": se lee como "o", - disyunción-.

Cada opción separada por 1 es una regladistinta; por ejemplo:

<secuencia-dígitos> ::= <dígito> 1<dígito><secuencia-dígitos>

Se puede escribir como:

<secuencia-dígitos> ::= <dígito><secuencia-dígitos> ::= <dígito>

<secuencia-dígitos>

En este caso, los símbolos terminales son losdígitos (0,1,2, etc.) y el punto. Los constructoresson los símbolos no terminales, como <secuencia-

dígitos>.

A menos que se afirme otra cosa, lasproducciones del símbolo no terminal inicial son lasprimeras en aparecer. Además, hay que aclarar queuna cadena es una secuencia finita de símbolosterminales con una longitud igual al número desímbolos. La cadena vacía tiene longitud cero.

Una expresión es una secuencia de símbolosque describen un cómputo. Las más importantes


7/14/2019 21045-71298-1-PB


clases de símbolos son constantes,variables,operadores y paréntesis [5]. La notaciónde las expresiones es importante debido quedependiendo de la adopción de una determinadanotación ,un intérprete lee las expresiones y puedeevaluar si una expresión pertenece o no al lenguaje.Por ejemplo, un operador binario se aplica a dosoperandos en notación infija cuando el operadorse coloca entre los operandos (a*b),prefija cuandoel operador aparece primero (*ab) yposfija cuandoel operador va al final (ab*).

B. Sintaxis

La sintaxis de un lenguaje especifica cómo se

construyen los programas, en dicho lenguaje. Laestructura sintáctica, es decir la estructura impuestapor la sintaxis del lenguaje, constituye laherramienta fundamental para trabajar con éste. Poreso se ha utilizado para describir constructores yreglas para entender los programas escritos en undeterminado lenguaje.

Definición: El constructor de un lenguaje esuna estructura sintáctica o conjunto deestructuras de un lenguaje, que sirven paraexpresar una clase particular de operaciones

[3].

La sintaxis desempeña dos funcionesprincipales en los lenguajes de programación:primero, la sintaxis abstracta de un lenguaje

identifica los componentes significativos de cadaconstructor. Las descripciones de lenguajes y lasimplementaciones están organizadas alrededor delas sintaxis abstractas. Segundo, la sintaxis concretade un lenguaje describe su representación escrita,incluyendo detalles como la colocación de palabrasclaves y los signos de puntuación [4].

C. Semántica

Inicialmente se habló de la semántica entrabajos que se referían al estudio del cambio designificado de las palabras. Hoy generalmente sedefine como el estudio de las relaciones entre laspalabras y las instrucciones de un lenguaje escritoo hablado y su significado. En áreas delconocimiento como la lingüística y la filosofia, lapalabra semántica tiene una aplicación un tanto


distinta, dado que interesa más el análisis del

lenguaje natural.

Semántica se entiende como el significado desentencias en el lenguaje formal de la lógicamatemática [2], o también como el desarrollo deformas para expresar lenguajes usados paraprogramación de computadores digitales. Estaúltima caracterización es más conocida comosemántica de los lenguajes de programación, loscuales tradicionalmente se han basado en sentenciasimperativas. En contraste, las sentencias de la lógicamatemática intentan plantear axiomas, reglas,declaraciones, proposiciones, etcétera.

El significado de las palabras, frases,expresiones o signos que determinan una idea ocosa material, debe ser especificado en los lenguajespara determinar el significado deun programa. Comopueden darse varias especificaciones distintas,dependiendo del lenguaje, una misma sintaxis puedetener semánticas distintas.

En programación es un problema ladeterminación de los valores de las variables asícomo la definición del ambiente (ámbito), en el cualel lenguaje puede entender y reconocer una

expresión, una variable o una función. Por tal razón,en los lenguajes existen reglas para la determinacióndel ámbito, las cuales son de dos clases: de ámbitodinámico, cuando para cualquier estado en que seencuentre un programa las variables pueden tomarvalores distintos; de ámbito estático, cuando unavez definido un valor para una variable, la aplicaciónde ese valor se mantendrá en cualquier estado delprograma a partir de la aplicación del valor.Además,todas las funciones poseen una distinción entre loque es el ambiente en el cual se define la función(ambiente de definición) y el ambiente en el cual se

aplica ésta (ambiente de activación).

El análisis semántico ayuda a laestandarización de terminologías y a la identificaciónde similitudes y diferencias entre lenguajes. Esto lepermite al diseñador encontrar restriccionesindeseables, incompatibilidades, ambigüedades,etc., mediante el uso de una formalización rigurosay pruebas de las propiedades semánticas dellenguaje.

7/14/2019 21045-71298-1-PB


II. LENGUAJES FUNCIONALES

Los lenguajes de programación se dividen

principalmente en dos clases según la forma en queel lenguaje permita definir la obtención de los

resultados deseados.

Lenguajes declarativos (no procedimen-

tales): un programa afirma explícitamente lo

que requiere que exhiba el resultado, pero no

afirma cómo debe obtenerse el resultado;

acepta cualquier forma de producir un

resultado que muestre las propiedades

requeridas [3].

Lenguajes imperativos (procedimentales):

es el caso contrario de los lenguajes

declarativos. Se define explícitamente cómo

será obtenido el resultado, pero no se define

explícitamente qué propiedades se espera que

exhiba el resultado [3].

Características

El lambda cálculo, desarrollado por el lógico

matemático Alonso Church [1] ha servido dentro

de la formalización de modelos matemáticos, para eldiseño de lenguajes de programación, en especial

como la base de los lenguajes de programación

funcional.

Un lenguaje funcional puede entenderse

como una subclase de los lenguajes declarativos.

Un programa escrito en un lenguaje funcional está

compuesto de un conjunto de ecuaciones basadas

en el uso de valores, funciones y recursión. Estas

ecuaciones operan con funciones y valores

evaluados a partir de funciones primitivas y valoresprovistos por el lenguaje.

Ejemplo

Evaluar la suma de los enteros de l a 10.

En un lenguaje imperativo se podría dar

solución al problema usando un ciclo finito, que

consiste en la actualización repetida del valor

contenido en un contador y la variable acumuladora:

total =O;for (i=I; i<=JO; ++i)

{

total =otal+i;

}

En este caso se trabaja con la asignación deun valor a la variable total, cada vez que cumpleuna iteración del ciclo, hasta que al final del cicloesta variable contenga el valor total de la suma.

En el caso de un lenguaje declarativo, elprograma puede expresarse sin actualización devariables. Así:

sum[J ..JOj.

Expresa la suma, donde [1..10] esuna expresiónque representa la lista de enteros de 1a 10,mientrassum es una función que puede usarse para calcularla suma de una lista arbitraria de valores.

En el caso particular de lenguajes funcionalescomo ML o SCHEME, es común encontrar lasolución del problema utilizando un ciclo finito. EnML se hace de la siguiente manera, aunque laactualización de variables no es necesaria:

let fun sum ita! =f(i=O) then tot else sum(i-J)

(tot+i)

in sum JOO

end

Donde se define una función sum, la cual tienecomo resultado tot si i=O; en caso contrario lafunción se "llama" a si misma en forma recursivacon argumentos (i-J) y (tot+i).

En el ejemplo se observa que un resultadopuede obtenerse, utilizando un lenguaje declarativo(por ejemplo uno funcional) o uno imperativo; lacuestión es definir en qué lenguaje se implementa.

Otra de las características importantes de loslenguajes funcionales es que los usuarios no tienenque preocuparse por el almacenamiento de datos,ya que se hace manejo de almacenamiento

implícito, que consiste en que ciertas operacionesintegradas de los datos asignan almacenamiento enel momento necesario. El almacenamiento que sevuelve inaccesible se libera, en forma automática.


7/14/2019 21045-71298-1-PB


Esta ausencia de código explícito para la liberaciónde memoria hace a los programas más sencillos ycortos, pero el lenguaje debe estar capacitado para

recuperar memoria que se vuelve innecesaria.

m . PROGRAMACIÓN FUNCIONAL

Cuando se habla de programación funcional,hay que entender que es un mecanismo adoptadopara resolver problemas de programación utilizandoun lenguaje funcional, es decir, trabajando con lasintaxis y con la semántica que definen ese lenguaje.

En programación funcional, una funciónpuede ser el valor de una expresión, puede pasarse

como argumento y puede colocarse en una base dedatos, esto permite la creación de operaciones sobrecolecciones de datos; que en lenguajes imperativosson muy dificiles de realizar o imposibles.

Existen distintas opiniones, incluso dentro dela comunidad de programación funcional, respectoa su definición; hasta el momento se propone lasiguiente:

Definición: programación funcional es unestilo de programación que enfatiza la

evaluación de expresiones, más que laejecución de comandos. Las expresiones enlos lenguajes funcionales se forman medianteel uso de funciones que combinan valoresbásicos [6].

El estilo de programación funcional secaracteriza por la ejecución o evaluación defunciones, que desde un planteamiento generalresuelven problemas con base en una composiciónreiterada de funciones, partiendo de que lascomposiciories más internas son funciones

elementales (primitivas), como por ejemplo la sumade dos enteros. En términos de composición defunciones lo anterior significa:

Aquí la composición más interna (la másbásica) es la que tiene que resolverse primero: entérminos computacionales los niveles más internosde ejecución de funciones son los primeros en

procesarse y los resultados de estas evaluacionesson necesariamente utilizadas en los niveles

superiores.

Ejemplo

5+7*(4-30/(4-19)), se puede ver como:+(5,*(7,-(4/(30,-(4,19)))))

En donde la función más interna - (4,19) seríala primera en resolverse. El resultado de estaexpresión es 47.

IV. LAMBDA CÁLCULO

El lambda cálculo surge antes que loslenguajes de programación de alto nivel a raíz delestudio realizado por Alonso Church[ 1]en la décadadel 30, que inicialmente se interesaba en el análisisde las funciones. La relevancia del lambda cálculoen ciencias de la computación sólo se apreció en1960, cuando las propiedades básicas en lenguajesde alto nivel se estudiaron, observándose elpotencial que tiene el lambda cálculo en laespecificación de los lenguajes de programación.Desde entonces, el lambda cálculo es una teoríafundamental de aplicación y abstracción para el

estudio de tipos' ya que puede verse como unagramática para términos de un lenguaje, es decir, ellambda cálculo permite decidir si una expresiónpertenece o no al lenguaje.

El lambda cálculo puro- tiene una sintaxispequeña compuesta solamente de tres cons-tructores: variables, aplicación de funciones ycreación de funciones.

1. El tipo indica los valores que una expresión está en

capacidad de representar y las operaciones que sobre ellas

se pueden aplicar. Dado que como principio generalizado

en el diseño de lenguajes toda expresión debe tener un tipo,entonces los tipos son un mecanismo para clasificar

expresiones. Los tipos surgen de diferentes necesidades,

como por ejemplo, el nivel de máquina, dado que los

compiladores necesitan información sobre el tipo para

poder generar expresiones en código de máquina, nivel de

lenguaje cuando los tipos estructurados se construyen a

partir de tipos básicos y nivel de usuario cuando el usuario

puede definir sus propios tipos dependiendo del problema.

2. El lambda cálculo puro no tiene tipos. Las funciones

pueden aplicarse sin restricciones, pero teniendo en cuenta

el ámbito, el paso de parámetros y las estrategias de

evaluación.

11 INGENIERÍA E INVESTIGACIÓN-- _

7/14/2019 21045-71298-1-PB


Como se había mencionado, el lambda cálculopuro es una gramática de términos, la cual se

especifica así:

M:= x l( MIM2)1 ( A x . M) que dice que

un término puede ser una variable x, una aplicación

(M¡M) de la función M¡ a M2

' o una abstracción(AX .M) .

Se escribe:

A x . M: función con parámetro x y cuerpo

M

Note que las funciones se escriben junto asus argumentos.

í\.x .M ~ abstracción ~ definición de función.

"Determinación de parámetros y cuerpo de lafunción"

xy ~ aplicación ~ invocación.

"Se está invocando la función x con parámetroy, donde y es una función o una variable"

Se usan las letrasj, x, y, z para variables y M,N, P, Q para términos. La letra e se utiliza para

constantes básicas y funciones constantes.

Ejemplo'

( A x . X *X )5 : Es una función que toma el

valor 5 y le aplica el cuerpo "x*x", haciendocorresponder 5*5.(ver nota de pie 4).

"La función Ax. x * x se aplica a cinco" se

escribe (A x .x*x ).5 Ylas fórmulas de este tipo sedenominan términos.

Un lenguaje de programación funcional esesencialmente un lambda cálculo con constantesapropiadas. Un lambda cálculo con tipos se tienecuando se asocia un tipo a cada término' .

Para profundizar en la noción de abstraccióny aplicación se presenta una revisión de la llamadaIgualdad Beta.

A. Igualdad en expresiones lambda

Escribimos M= f3 N siM yN son iguales según

la igualdad beta (la cual se explica posteriormente)y se dice que tienen el mismo valor. Dicho de otraforma, es aplicar una abstracción M.M a unargumento N. Se observan aquí las nociones deinvocación a función y el paso de parámetros enlenguajes de programación.

Ejemplo

Observemos de nuevo la función cuadradoescritaenML [4]

fun cuadrado(x) = x*x;

cuadrado(5) = 5*5 : es la invocación de lafunción con parámetro 5, también la evaluaciónremplazando en el cuerpo de la función el parámetro5.

Utilizando expresiones lambda se puedeescribir:

A x . (*xx) es la abstracción de la función

cuadrado.

Sea M el cuerpo *(xx) y N la funciónconstante 5, entonces

(í\.x. (*xx))5 =J 25 según la igualdad beta.

B. Variables libres y Acotadas

La abstracción í\.x.M también restringe el valorde x en M.M. Entonces, se dice que x está acotadaen í\.x.M

3. La formulación esencial de algunos ejemplos de esta

sección, se encuentra en ejemplos del capitulo 12 del texto

de Sethi[4J.

4. En el ejemplo se utilizó (x=x), que no es correcta en

expresiones lambda. La notación prefija *(xx) es la que se

debe utilizar.

5. Un lambda cálculo con tipos polimorfos se ha usado

para estudiar los tipos en el lenguaje funcional ML.


7/14/2019 21045-71298-1-PB


El conjunto l ibre(M) está formado por todaslas variables libres de M, es decir, las variables que

no están acotadas enM,

dadas por las reglas:

i) l ib re ( x) "xes libre en eltérmino x"

ii) libre(M N) = libre(M ) ulibre(N)

= {x}

"Una variablees libre en MN si eslibre enM o enN'.

iii) l ibre(Ax.M) = libre(M ) - {x}

"Excepto x, todas lasvariable son libres enAx .M '

Nota: x es libre enMsiMtiene la forma AY.N,

donde y es diferente de x y la ocurrencia de x en elsubtérmino Nes libre.

La variable x en A x. M se denomina aparición,o simplemente asociación de x.

Definición: todas las apariciones dex en Ax .M

son acotadas dentro del ámbito de estaabstracción. Todas las apariciones noacotadas de una variable en un término son

libres. Además, toda aparición de una variabledebe ser libre o acotada, pero nosimultáneamente.

Ejemplo

En (Ay.z)(k.z), la variable z es libre, porquees libre en AY.Z . (regla ii).

C . Sustitución

Aplicar una abstracción Ax . Ma un parámetro

N se realiza sustituyendo x por N en el cuerpo M Esdecir, N reemplaza todas las apariciones libres de xenM

La sustitución de un término N por unavariable x en Mse nota {N/x}My se define así:

1 . Suponga que las variables libres de N notienen apariciones acotadas enM. Entonces,el término {N/x}M se forma remplazando conN todas las apariciones libres de x en M

2. En otro caso, suponga que la variable y eslibre enNy acotada en M. La asociación ylas apariciones acotadas correspondientesde y en M se reemplazan de maneraconsistente por alguna variable nuevaz o seutilizan índices posicionales. Se siguennombrando las variables acotadas en Mhasta que se pueda aplicar el caso 1.

Posteriormente se aplica el caso 2.

Ejemplo

(i) M no tiene apariciones acotadas (caso 1).

{u/x}x = "u reemplazaaxenel cuerpo x ".

(u/x}(xx) =(uu) "u remplaza a x en el cuerpo xx,entonces queda uu ".

{ (A x .X )/X }X = (A x .X ) " Ax .X reemplaza ax en el cuerpox, entonces queda (A x.X ) ".

En estos ejemplos, como M no tieneapariciones acotadas, es decir no hay restriccionesde ámbito en los cuerpos x, (xx) y x, se sigue comoen el casol.

(ii)M no tiene apariciones libres de X.

{u/x}y =y "u reemplazaax en el cuerpo y Como

en y no hay apariciones libres de x,entonces queda y

{ (A Y .Y )/ X) ( A x. X) =A x .X

"Ax.X reemplaza a las x libres en elcuerpo Ax .X , como en Ax .X , x esacotada en Ax .X ,

entonces queda A x.X " .

En general, cuando en M no hay variableslibres x para la sustitución {N/x} entonces queda elmismo M, es decir, {N/x}M es M

(iii) u en N tiene apariciones acotadas en M

(caso 2).

{u/x} (M.x) = {u/x} (k.x)= (k.u)

{U/X}(AU.U)= {u/x} (k.z) = (k.z)

Cuando en una sustitución variables acotadasse encuentran notadas con el mismo nombre de unavariable para sustituir, es conveniente realizar uncambio de variable o colocación de índices. El

1 1 ·_ _ _ _ _ _ _ _ _ _ _ ; _ _ _ ; _ _ ~ _INGENIERÍA E INVESTIGACIÓN

7/14/2019 21045-71298-1-PB


axioma a permite asignar sistemáticamente nuevonombre a las variables acotadas. El axioma es elsiguiente:

( A x . M) = fJ k . {rx} M

Suponiendo que z no es libre en M.

Ejemplo

Sea el término ( A xy . * x y) y x.

Si no se renombran las variables y sereemplazan las apariciones libres, se tendríaincorrectamente lo siguiente:

(A Y . *yy )x ~ *xx

Mientras que renombrando las variables seobtiene:

(AUV . *uv)yx ~ (AV . *yv)x

~*yx

(AUV . *u v)y x = f3 * yx

Ejemplo

A x . X = fJ A y . yA x y . X = fJ A u y . U

ya que x no es libre.

Reglas Dirigidas por Sintaxis

Sean P y Q subtérminos del cuerpoM (M =PQ), en donde se hace la sustitución N porx. Entonces:

(i)' { o / x } x = N

(ii) { o / x } y = y si y * ' x .

(iii) { o / x ~ P Q ) = { o / x } p { o / x } Q

(iv) { O / X K . 1 x . p ) = A x . P "si x no es libre".

(V ) { o / x ~ A y . P ) = A y . { o / x } P

si y * 'X ,y É libreeN).

si y * ' X ,z É libreiN), Z É libre(P).

Ejemplo

= k.u "u se renombra por z

ya que no es libre(regla vi)" "regla v".

Ejemplo

D. Igualdad beta

Axioma fundamental de la igualdad beta:

( ?tx .M ) N = f3 {N /x }M

de forma que (?tx .y )u = f3 u y (?tx .y)u=f3Y

pues (?tx .x )u =u/x }x=u y (?tx .y)u ={u /x } y= y

La igualdad Beta cumple las siguientespropiedades:

• Reflexividad: un término M es igual a sírmsmo.

Conmutatividad: si M es igual aN, entoncesNes igual aM

Transitividad: si M es igual a N y N es iguala P, entonces M es igual a P

De las tres propiedades anteriores se concluyeque la igualdad beta define una relación deequivalencia.

_ _ _ _ _ _ _ _ 1 1 'NGENIERÍA E INVESTIGACIÓN I

7/14/2019 21045-71298-1-PB


Las propiedades anteriores se notan mediantelas siguientes reglas:

( i) M = f3 M

( re gl a d e r efl ex iv id ad )

(ii)

M=f3N

N=fJM

( re gl a d e c onmu ta tiv id ad )

"Si M = N entonces N= M "f3 ' f3

(iii)

M=f3N N=f3P

M=f3P

( re gl a d e t ra ns it iv id ad )

"Si M = ? y N= ¡,entonces M = rt "

Otras reglas son:

(iv)

M=f3M'A1N=f3M'N ,

(regla 1de cong ruencia )

(v)

(regla 2 d e c on gr ue nc ia )

Ejemplo

Sea 1 = Ax .X y S=xYZ. (XZ)ryz )

o en forma completa:

S=Ax . (Ay . (Az . ( ( x z) r y z) ) )) )

Verificar la siguiente igualdad: Slll=¡

( A xy z. ( xz) ( yz} )1 11 = (A x yz . ( xz ) ( vz) ) ( A x. X) ( A x. X) ( A x. X)

= lA yz. {( A x.X )/X }((x z) ry z)) )( A x.X )

( A x.X )

= lA yz. ({ A x.X )Z )ry z))( A x.X )( A x.X )

= I A vz. z( vz )) (A x __ d]( A x .X )

= lA zo Z ({A x.X )Z ))( A x.X )

= IA z. zz)( A x__d]

= lA x .x )( A x.X )

= f 3A x .X

=f31

E. Reducciones

El cálculo con términos lambda hace uso delaxioma fundamental de la igualdad 1 3 y del axioma oc,

los cuales son llamados reducción beta y conversiónalfa respectivamente, los cuales se denotan así:

(Ax.M)N~{NI}Mf3 Ix

(reducción 1 3 )

Ax.M~Az{zl}Ma 7x

z no es lib re en M (conversión a)

Una reducción es cualquier secuencia dereducciones f 3 y conversiones a Donde el resultadode un cálculo no depende del orden en el cual seapliquen las reducciones". Se dice que un términoque no puede tener reducciones 1 3 se encuentra enform a norm al; el término Az.z se halla en formanormal porque ninguno de sus subtérminos es de laforma (Ax .M)N La forma normal es única si existe.

El término (Ax .M)N se denomina exred

(expresión a reducir). De esta forma, si, P = ; Q

entonces P tiene alguna exred (Ax .M)N que sereemplaza con { N/x } M para crear Q .

6. Verteorema de Church-Rosser. En SETHI "Lenguajes

de Programación -Funciones y Contructores-" Sethi. Pág.

444-445.

1 1 ·~~=.=.:...;;,,;;;..;;.;_..;.;;;;.;;...;~:...:...:..;_- _INGENIERÍA E INVESTIGACIÓN

7/14/2019 21045-71298-1-PB


Ejemplo

Verificar L Il = : : ; '1 3. D o n d e L = A x Y .X e J = A x .X .

L11=(Axy.X )(Ax.X )(Ax.X )~(íLy.(Ax.X ))(Ax.X)~ Ax.xf 3 f 3

NOTA: Se dice que una reducción es sin finalcuando la reducción continúa de manera indefinidasin encontrar una forma normal. Por ejemplo, lasreducciones que comienzan con ( A x . X X ) ( A x . X X ) .

Estrategia de Reducción

Existen dos estrategias de reducción, lainvocación por valor y la invocación por nombre.En el primer caso se elige la exred del extremoizquierdo más interna de un término. En cambio,para las invocaciones por nombre se elige la exreddel extremo izquierdo más externa. En este contexto,"interna" y "externa" se refieren a la forma comoestán anidados los términos.

Ejemplo

Reducir la siguiente expresión.

(Ax.xx)«Ay.y)(k.z))

En el caso de la invocación por valor, se tiene:

(Ax.xx)«Ay.y)(k.z)) =¡ (Ax.xx)(k.z)=¡ (k.z)(k.z)=¡ (k.z)

En el caso de invocación por nombre.

(Ax.xx)«Ay.y)(k.z)) ~ «Ay.y)(k.z))«Ay.y)(k.z))f3

~ (k.Z)«Ay.y)(k.z))f3

=¡ (Ay.y)(k.z)=¡ (k.z)

_ _ _ _ _ _ _ _ _ 1 1 =NGENIERÍA E INVESTIGACIÓN .

7/14/2019 21045-71298-1-PB


Como se observa, la invocación por valorrequiere menor número de reducciones f 3 paraalcanzar una forma normal, pero existe la posibilidad

de que en algunas expresiones se quede en un cicloinfinito. La reducción por nombre o reducción enorden normal garantiza alcanzar una forma normal,si existe. Comúnmente, los lenguajes funcionalesutilizan la invocación por valor, debido a que esposible implantarla eficientemente.

BIBLIOGRAFÍA

l. BARENDREGT, H. P. "Studies in logic. and thefoundations of mathematics - The LambdaCalculus ". Vol. 103. Amsterdam; North-Holland,1984.

2. GUNTER, Carl A. "Sernantic of ProgrammingLanguages - Structures and Techniques -", MITPress, 1992.

3. GLASER, Edward L. "Dictionary of Computing",Oxford University Press. Oxford. 2a. Edición.1986.

4. SETHI, Ravi. "Lenguajes de Programación. -Conceptos y Constructores -". Adisson Wesley.

1992.

5. WIKSTRÓM, Áke. "Functional ProgrammingUsing Standard ML". Prentice Hall Intemational,Cambridge, 1987.

6. <http://www.cs.not.ac. uk/DepartmentStaff/mpj/faq.html>

1 1 ·~~==~~-- - - - - - - - - - - - - - - - - -INGENIERÍA E INVESTIGACIÓN

Documents

21045-71298-1-PB