path: root/pia/n1.lyx

#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