#LyX 2.3 created this file. For more info see http://www.lyx.org/ \lyxformat 544 \begin_document \begin_header \save_transient_properties true \origin unavailable \textclass book \begin_preamble \input{../defs} \end_preamble \use_default_options true \maintain_unincluded_children false \language spanish \language_package default \inputencoding auto \fontencoding global \font_roman "default" "default" \font_sans "default" "default" \font_typewriter "default" "default" \font_math "auto" "auto" \font_default_family default \use_non_tex_fonts false \font_sc false \font_osf false \font_sf_scale 100 100 \font_tt_scale 100 100 \use_microtype false \use_dash_ligatures true \graphics default \default_output_format default \output_sync 0 \bibtex_command default \index_command default \paperfontsize default \spacing single \use_hyperref false \papersize default \use_geometry false \use_package amsmath 1 \use_package amssymb 1 \use_package cancel 1 \use_package esint 1 \use_package mathdots 1 \use_package mathtools 1 \use_package mhchem 1 \use_package stackrel 1 \use_package stmaryrd 1 \use_package undertilde 1 \cite_engine basic \cite_engine_type default \biblio_style plain \use_bibtopic false \use_indices false \paperorientation portrait \suppress_date false \justification true \use_refstyle 1 \use_minted 0 \index Index \shortcut idx \color #008000 \end_index \secnumdepth 3 \tocdepth 3 \paragraph_separation indent \paragraph_indentation default \is_math_indent 0 \math_numbering_side default \quotes_style french \dynamic_quotes 0 \papercolumns 1 \papersides 1 \paperpagestyle default \tracking_changes false \output_changes false \html_math_output 0 \html_css_as_file 0 \html_be_strict false \end_header \begin_body \begin_layout Section Historia \end_layout \begin_layout Standard En 1928, David Hilbert planteó el \series bold problema de la decisión \series default o \series bold \emph on \lang naustrian Entscheidungsproblem \series default \emph default \lang spanish , que pide un algoritmo para determinar si una proposición lógica se deriva o no de los axiomas en un sistema lógico que incluya la aritmética de Peano. En 1931, Gödel demuestra en su \series bold teorema de incompletitud \series default que tal sistema lógico no puede ser a la vez consistente y completo. En 1936, Alan Turing y Alonzo Church, de forma independiente, crean respectivam ente las \series bold máquinas de Turing \series default y el \series bold cálculo \begin_inset Formula $\lambda$ \end_inset \series default para definir el concepto de algoritmo o \series bold función computable \series default y lo usan para probar que no hay algoritmo que resuelva el \emph on \lang naustrian Entscheidungsproblem \emph default \lang spanish . \end_layout \begin_layout Standard Las máquinas de Turing fundamentan la teoría de la computabilidad, y el cálculo \begin_inset Formula $\lambda$ \end_inset la de la programación funcional. Moses Shönfinkel y Haskell Curry introducen la \series bold lógica combinatoria \series default , útil en la implementación de lenguajes funcionales. \end_layout \begin_layout Standard En 1956, John McCarthy organiza el \emph on \lang english Dartmouth Summer Research Project on Artificial Intelligence \emph default \lang spanish , que populariza el término \begin_inset Quotes cld \end_inset inteligencia artificial \begin_inset Quotes crd \end_inset , y en los años sucesivos Newell, Simon y Shaw escribieron \begin_inset Quotes cld \end_inset \emph on \lang english Logic theorist \emph default \lang spanish \begin_inset Quotes crd \end_inset y \begin_inset Quotes cld \end_inset \emph on \lang english General problem solver \emph default \lang spanish \begin_inset Quotes crd \end_inset y McCarthy escribió \begin_inset Quotes cld \end_inset \emph on \lang english Programs with common sense \emph default \lang spanish \begin_inset Quotes crd \end_inset . En 1958, McCarthy crea el lenguaje \series bold Lisp \series default ( \emph on \lang english LISt Processing \emph default \lang spanish ) para usarlo en inteligencia artificial. Este usa listas \begin_inset Foot status open \begin_layout Plain Layout En las diapositivas dice que como tipo básico, pero en realidad están hechas por pares ( \begin_inset Quotes cld \end_inset \lang english conses \lang spanish \begin_inset Quotes crd \end_inset ), que sí son un tipo básico. \end_layout \end_inset , funciones de orden superior, recursividad y recolección de basura, aunque también características de lenguajes imperativos como asignación destructiva y efectos colaterales para hacerlo práctico, y fue el primer lenguaje de alto nivel interpretado. Posteriormente surgió Scheme, basado en Lisp y más cercano a la idea original de Lisp. Lisp aparece en la mayoría de la literatura de IA y se ha usado en \lang english Carnegie Mellon \lang spanish , \lang english MIT \lang spanish y \lang english Stanford \lang spanish . Los lenguajes \series bold ISWIM \series default ( \emph on \lang english If you See What I Mean \emph default \lang spanish ) se acercan más al cálculo \begin_inset Formula $\lambda$ \end_inset que Lisp. \end_layout \begin_layout Standard En 1964, Peter Landin crea una \series bold semántica denotacional \series default para un subconjunto del lenguaje imperativo ALGOL 60, relacionándolo con el cálculo \begin_inset Formula $\lambda$ \end_inset . \end_layout \begin_layout Standard A principios de los 70 se da la crisis del software y se busca facilitar la verificación formal de programas con modelos como la \series bold programación funcional \series default o \series bold aplicativa \series default y la \series bold programación lógica \series default o \series bold declarativa \series default . \end_layout \begin_layout Standard En 1978, John Backus publica \begin_inset Quotes cld \end_inset \emph on \lang english Can programming be liberated from the von Neumann style? \emph default \lang spanish \begin_inset Quotes crd \end_inset , donde critica la programación imperativa, muestra las ventajas de la programac ión funcional y diseña el lenguaje FP ( \emph on \lang english Functional Programming \emph default \lang spanish ), con la idea de definir nuevas funciones combinando otras. Esta adquiere interés en varias universidades británicas, y se crean lenguajes funcionales como Hope, ML, SASL, KRC o Miranda, que usan conceptos como polimorfismo, evaluación perezosa y funciones de orden superior y consiguen código muy abstracto y muy conciso. \end_layout \begin_layout Standard En septiembre de 1987 se celebra la conferencia \series bold FPCA \series default , en la que se discuten los problemas de esta proliferación de lenguajes funcionales y se forma un comité internacional para diseñar un lenguaje puramente funcional de propósito general, \series bold Haskell \series default , que busca unificar las características más importantes de los lenguajes funcionales. Durante casi 10 años aparecieron versiones del lenguaje hasta que en 1998 se crea el estándar \series bold Haskell 98 \series default , que se continúa con la investigación de nuevas características y extensiones, llegando a la última versión del estándar, \series bold Haskell 2010 \series default . Actualmente proliferan lenguajes multiparadigma que tienen base imperativa pero incorporan conceptos de programación funcional, como \series bold Python \series default , creado a finales de los 80, y lenguajes funcionales como Haskell se usan para muchas aplicaciones. \end_layout \begin_layout Section Programación funcional \end_layout \begin_layout Standard Un \series bold programa imperativo \series default es una secuencia de \series bold comandos \series default que modifican un \series bold estado \series default . El principal modificador es la asignación, \begin_inset Formula $v=E$ \end_inset o \begin_inset Formula $v\coloneqq E$ \end_inset . Se pueden ejecutar comandos en secuencia escribiéndolos separados, por ejemplo, por \begin_inset Quotes cld \end_inset \begin_inset Formula $;$ \end_inset \begin_inset Quotes crd \end_inset , y ejecutarse condicionalmente con \family typewriter if \family default o \family typewriter while \family default . Los \series bold lenguajes imperativos \series default , como FORTRAN, C, ALGOL o Java, soportan programación imperativa. \end_layout \begin_layout Standard Este modelo establece una dependencia entre el algoritmo y el modelo \lang naustrian von Neumann \lang spanish , donde los datos del programa corresponden a datos en memoria principal y el código a instrucciones máquina en dicha memoria, lo que permite generar programas eficientes y sencillos al tener un nivel cercano a la máquina pero dificulta usar los algoritmos en arquitecturas que usen otros modelos. \end_layout \begin_layout Standard Además, las modificaciones del estado con asignaciones oscurecen la semántica del programa, dificultan estudiar la corrección y complican la optimización y paralelización del código por parte del compilador. \end_layout \begin_layout Standard Un \series bold programa funcional \series default es una expresión, y ejecutar el programa significa evaluar la expresión. No hay estado ni asignaciones, ni secuenciación o repetición ya que la evaluación de una expresión no afecta a otras, pero los usos de estas se pueden simular mediante recursividad. Se usan funciones en sentido matemático, cuyo valor devuelto depende sólo de los parámetros de entrada, y se tiene \series bold transparencia referencial \series default , consistente en que una misma expresión siempre evalúa al mismo valor, lo que facilita probar la corrección de programas. Las funciones se pueden usar como valores, permitiendo \series bold funciones de orden superior \series default , que aceptan otras funciones como parámetros o devuelven una función, dando flexibilidad al programador. \begin_inset Foot status open \begin_layout Plain Layout Las diapositivas llaman función de orden superior a cualquiera que se use como valor. Esto es incorrecto. \end_layout \end_inset \end_layout \begin_layout Standard Los \series bold lenguajes funcionales \series default soportan programación funcional, y suelen incluir: \end_layout \begin_layout Itemize \series bold Inferencia de tipos \series default , con la que el programador no tiene que declarar el tipo de los valores en la mayoría de los casos sino que el compilador lo deduce, aunque el programador puede declarar el tipo para que el compilador lo compare con el tipo inferido. Esto aumenta la concisión respecto a los lenguajes en los que hay que declarar los tipos explícitamente, y da mayor seguridad y eficiencia respecto a los lenguajes con tipos dinámicos ya que evita tener que comprobar los tipos en tiempo de ejecución y los errores que aparecen cuando estas comprobaci ones fallan, ya que las comprobaciones se han hecho al compilar. \end_layout \begin_layout Itemize \series bold Polimorfismo \series default , con el que el tipo de los parámetros o la salida de una función dependen de uno o más parámetros, permitiendo una mayor reutilización del código al no tener que repetir algoritmos para estructuras similares. \end_layout \begin_layout Itemize \series bold Evaluación perezosa \series default , no evaluando un argumento hasta que se necesita, evaluando después de sustituirlo en la definición de la función, aunque guardando el valor evaluado por eficiencia. Esto es en contraposición a la tradicional \series bold evaluación ansiosa \series default , en que primero se evalúan los argumentos y luego se llama a la función. La evaluación perezosa permite manipular estructuras de datos conceptualmente infinitas. \end_layout \begin_layout Standard Como no tienen variables ni asignación, los programas son más cercanos a objetos matemáticos abstractos y aumenta la libertad de implementación, permitiendo la paralelización. Además, las funciones de orden superior hacen el código más conciso y elegante, mejoran la reusabilidad y modularidad y permiten representar estructuras de datos infinitas de forma conveniente. También hay herramientas para probar la corrección de programas funcionales, lo que en lenguajes imperativos es complicado porque hay que explicitar los estados. \end_layout \begin_layout Standard Por otro lado, es más difícil representar entrada y salida y programas interacti vos o que se ejecutan de forma continua, como editores o controladores, y al estar más alejados del \emph on \lang english hardware \emph default \lang spanish que los lenguajes imperativos, son menos eficientes y es más difícil razonar sobre su eficiencia en tiempo y espacio. \end_layout \begin_layout Standard La \series bold notación lambda \series default representa una función \begin_inset Formula $x\mapsto E[x]$ \end_inset como \begin_inset Formula $\lambda x.E[x]$ \end_inset , que también se puede escribir como \begin_inset Formula $[x]\ E[x]$ \end_inset . Una función \begin_inset Formula $f:X_{1}\times\dots\times X_{n}\to Y$ \end_inset se puede representar como \begin_inset Formula $g:X_{1}\to\cdots\to X_{n}\to Y$ \end_inset , donde \begin_inset Quotes cld \end_inset \begin_inset Formula $\to$ \end_inset \begin_inset Quotes crd \end_inset es asociativo por la derecha, de modo que \begin_inset Formula $g(x_{1})(x_{2})\cdots(x_{n})=f(x_{1},\dots,x_{n})$ \end_inset . A esto se le llama \series bold currificación \series default en honor a Haskell Curry. \end_layout \end_body \end_document