RESUMEN UNIDAD #2: ELEMENTOS DE UN PROGRAMA

...

Bibliografía:

- Luis Joyanes Aguilar, Matilde Fernandez Azuela.. (1996). Fundamentos de programación. Libro de problemas. España: McGraw-Hill.

- Francisco Javier Pinales Delgado César Eduardo Velázquez Amador. (2013). PROBLEMARIO DE ALGORITMOS RESUELTOS CON DIAGRAMAS DE FLUJO Y PSEUDOCÓDIGO. Aguascalientes, México.: Universidad Autónoma de Aguascalientes.

Cálculo Lambda

Fue desarrollado por Alonso Church en la década del 30 con el objeto de dar una teoría general de las funciones. Tiene por objeto explicitar el concepto que representa el empleo de funciones como medio de transformación de argumentos en resultados. Se puede considerar al cálculo lambda como el lenguaje universal de programación más pequeño. Consiste en una regla de transformación simple (sustitución de variables) y un esquema simple para definir funciones. Ha sido empleado como fundamento conceptual de los lenguajes de programación, aportando:

- una sintaxis básica

- una semántica para el concepto de función como proceso de transformación de argumentos en

- un medio para definir primitivas de programación

SINTAXIS DEL CALCULO LAMBDA

La sintaxis del Cálculo Lambda ( CL ) es la siguiente:

::= |

O . |

( )

En el cálculo lambda, una expresión o término se define regularmente a través de las siguientes reglas de formación:

- Toda variable es un término: x, y, z, u, v, w, x1, x2, y9…

- Si t es un término y x es una variable, entonces (λx.t) es un término (llamado una abstracción lambda).

- Si t y s son términos, entonces (ts) es un término (llamado una aplicación lambda).

- Nada más es un término.

Según estas reglas de formación, las siguientes cadenas de caracteres son términos:

x

(xy)

(((xz)y)x)

(λx.x)

((λx.x)y)

(λz.(λx.y))

Por regla se suelen omitir los paréntesis externos, ya que no cumplen ninguna función de desambiguación. Por ejemplo se escribe (λz.z)z en vez de ((λz.z)z), y se escribe x(y(zx)) en vez de (x(y(zx))). Además, se suele adoptar la convención de que la aplicación de funciones es asociativa hacia la izquierda. Esto quiere decir, por ejemplo, que xyzz debe entenderse como (((xy)z)z), y que (λz.z)yzx debe entenderse como ((((λz.z)y)z)x).

Conclusiones: El cálculo lambda es computacionalmente equivalente a las máquinas Turing porque es capaz de evaluar y expresar cualquier función computable. cualquier cálculo que se pueda lograr en cualquiera de estos otros modelos se puede expresar en el cálculo lambda y viceversa. Según la tesis de Church-Turing, ambos modelos pueden expresar cualquier cómputo posible.

Es sorprendente que el cálculo lambda pueda representar cualquier cómputo concebible usando solamente las nociones simples de abstracción funcional y aplicación basado en la substitución textual simple de términos por variables.

Bibliografía:

- Solis Reyes Alfonso. (2014). Cálculo Lambda. 07/03/2017, de Universidad de Chile Sitio web: https://cs.famaf.unc.edu.ar/wiki/lib/exe/fetch.php?media=compiladores:apuntes120427.pdf

- Anónimo. (2012). Cálculo lambda. 07/03/2017, de ECURED Sitio web: https://www.ecured.cu/C%C3%A1lculo_lambda