¿Puede alguien explicar en términos sencillos qué es un lenguaje funcional?

Question

Duplicar posibles:
Functional programming and non-functional programming

Me temo que Wikipedia no me trajo ninguna más. Muchas gracias

PD: Este hilo pasado también es muy bueno, sin embargo estoy feliz de haber hecho esta pregunta de nuevo como las nuevas respuestas eran grandes - gracias

Functional programming and non-functional programming

Answer 1

primero aprende lo que es un Turing machine es (de wikipedia).

Una máquina de Turing es un dispositivo que manipula símbolos en una tira de cinta según una tabla de reglas. A pesar de su simplicidad, una máquina de Turing se puede adaptar para simular la lógica de cualquier algoritmo de computadora, y es particularmente útil para explicar las funciones de una CPU dentro de una computadora.

Esto es aproximadamente Lamda calculus. (de wikipedia).

En la lógica matemática y la informática, el cálculo lambda, también escrito como el λ-cálculo, es un sistema formal para el estudio de las funciones computables recursivas, una teoría de la computabilidad Los Ángeles, y fenómenos relacionados tales como la unión variable y sustitución.

Los lenguajes de programación funcional utilizan, como su modelo fundamental de computación, el cálculo lambda, mientras que todos los demás lenguajes de programación utilizan la máquina de Turing como su modelo fundamental de computación. (Bueno, técnicamente, debería decir lenguajes de programación funcionales vr.s imperative programming idiomas, ya que los lenguajes de otros paradigmas usan otros modelos. Por ejemplo, SQL usa el modelo relacional, Prolog usa un modelo lógico, etc., sin embargo, prácticamente todo los lenguajes en los que las personas realmente piensan cuando hablan de lenguajes de programación son funcionales o imperativas, así que me quedaré con la generalidad fácil.)

¿Qué quiero decir con "modelo fundamental de computación"? Bueno, todos los lenguajes se pueden pensar en dos niveles: uno, algún núcleo del lenguaje completo de Turing, y luego capas de abstracciones o azúcar sintáctico (dependiendo de si te gustan o no) que se definen en términos de la base de Turing- idioma completo. El lenguaje central para los lenguajes imperativos es entonces una variante del modelo clásico de computación de Turing que podríamos llamar "el lenguaje C". En este idioma, la memoria es una matriz de bytes que se pueden leer y escribir, y usted tiene una o más CPU que leen la memoria, realizan aritmética simple, ramifican en condiciones, etc. Eso es lo que quiero decir con el modelo fundamental de computación de estos lenguajes es la Máquina de Turing.

El modelo fundamental de computación para lenguajes funcionales es el Cálculo Lambda, y esto se muestra de dos maneras diferentes. Primero, una cosa que hacen muchos lenguajes funcionales es escribir sus especificaciones explícitamente en términos de una traducción al cálculo lambda para especificar el comportamiento de un programa escrito en el lenguaje (esto se conoce como "semántica denotacional").Y segundo, lenguajes de programación casi todos funcionales implementan sus compiladores utilizar un lenguaje intermedio lambda-cálculo similar explícita Haskell ha Core, Lisp y Esquema tener su representación “desazucaradas” (una vez aplicadas todas las macros), Ocaml (Objective Categorical Abstract Machine Language) tiene su lispish representación intermedia, y así sucesivamente.

Entonces, ¿qué es este cálculo lambda sobre el que he estado hablando? Bueno, la idea básica es que, para hacer cualquier cálculo, solo necesitas dos cosas. Lo primero que necesita es abstracción de funciones: la definición de una función sin nombre, de argumento único. Alonzo Church, que primero definió el cálculo Lambda utilizó la notación más bien oscura para definir una función como la letra griega lambda, seguido del nombre de un carácter del argumento para la función, seguido de un punto, seguido de la expresión que era la cuerpo de la función. Entonces, la función de identidad, que tiene algún valor, simplemente devuelve ese valor, se vería como "λx.x". Voy a usar un enfoque levemente más legible para los humanos. Voy a reemplazar el carácter λ por la palabra " diversión ", el período con" -> ", y permite espacios en blanco y permite nombres de múltiples caracteres. Así que podría escribir la función de identidad como "diversión x -> x", o incluso "diversión cualquiera -> lo que sea". El cambio en la notación no cambia la naturaleza fundamental. Tenga en cuenta que esta es la fuente del nombre "expresión lambda" en lenguajes como Haskell y Lisp-expresiones que introducen funciones locales sin nombre.

Lo único que puede hacer en el Cálculo Lambda es llamar a funciones. Usted llama a una función al aplicarle un argumento. Voy a seguir la convención estándar de que la aplicación es solo los dos nombres en una fila, por lo que f x está aplicando el valor x a la función llamada f. Podemos reemplazar f con alguna otra expresión, incluida una expresión Lambda, si queremos, y podemos Cuando se aplica un argumento a una expresión, se reemplaza la aplicación con el cuerpo de la función, con todas las ocurrencias del nombre del argumento reemplazado con cualquier valor que se aplicó. Entonces la expresión (fun x -> x x) y se convierte en y y. Los teóricos hicieron todo lo posible para definir con precisión lo que significan "reemplazando todas las apariciones de la variable con el valor aplicado", y pueden seguir explicando cómo funciona esto exactamente (lanzando términos como "alfa"). cambio de nombre "), pero al final las cosas funcionan exactamente como esperabas. La expresión (fun x -> x x) (x y) se convierte en (x y) (x y) - no hay confusión entre el argumento x dentro de la función anónima, y ​​el x en el valor que se está aplicando. Esto funciona incluso en niveles múltiples: la expresión (fun x -> (fun x -> x x)) (x x)) (x y) se convierte en la primera (fun x -> x x) ((x y) (x y)) y luego ((x y) (x y)) ((x y) (x y)). La x en la función más interna (“(fun x -> x x)”) es una x diferente que las otras x.

Es perfectamente válido pensar en la aplicación de funciones como una manipulación de cadenas. Si tengo una (diversión x -> alguna expresión) y le aplico algún valor, entonces el resultado es solo una expresión con todas las "x" reemplazadas textualmente por "algún valor" (a excepción de aquellas que están sombreadas por otro argumento)

Como comentario, añadiré paréntesis donde sea necesario para desambiguar las cosas, y también las eludiré cuando no las necesite. La única diferencia que hacen es la agrupación, no tienen otro significado.

Así que eso es todo lo que hay para el cálculo Lambda. No, en realidad, eso es todo, solo abstracción de funciones anónimas y aplicación de funciones. Veo que tiene dudas sobre esto, así que permítanme abordar algunas de sus preocupaciones.

Primero, especifiqué que una función solo tomaba un argumento: ¿cómo se tiene una función que toma dos o más argumentos? Fácil: tienes una función que toma un argumento y devuelve una función que toma el segundo argumento.Por ejemplo, la composición de funciones podría definirse como fun f -> (fun g -> (fun x -> f (g x))) - léala como una función que toma un argumento f, y devuelve una función que toma un argumento g y devuelve una función que toma un argumento xy devuelve f (g x).

Entonces, ¿cómo representamos los enteros, usando solo funciones y aplicaciones? Fácilmente (si no obviamente) - el número uno, por ejemplo, es una función fun s -> fun z -> s z - dada una función "sucesora" sy una "cero" z, uno es el sucesor a cero. Dos es divertido s ->fun z -> s s z, el sucesor del sucesor a cero, tres es fun s -> fun z -> s s s z, y así sucesivamente.

Agregar dos números, por ejemplo x y y, es una vez más simple, si es sutil. La función de adición es solo fun x -> fun y -> fun s -> fun z -> x s (y s z). Esto parece extraño, así que déjame mostrarte un ejemplo para mostrar que sí, de hecho funciona, agreguemos los números 3 y 2. Ahora, tres son solo (fun s -> fun z -> s s s z) y dos son solo (fun s -> fun z -> s s z), entonces lo conseguimos (cada paso se aplica un argumento a una función, en ningún orden particular):

(fun x -> fun y -> fun s -> fun z -> x s (y s z)) (fun s -> fun z -> s s s z) (fun s -> fun z -> s s z) 

(fun y -> fun s -> fun z -> (fun s -> fun z -> s s s z) s (y s z)) (fun s -> fun z -> s s z) 

(fun y -> fun s -> fun z -> (fun z -> s s s z) (y s z)) (fun s -> fun z -> s s z) 

(fun y -> fun s -> fun z -> s s s (y s z)) (fun s -> fun z -> s s z) 

(fun s -> fun z -> s s s ((fun s -> fun z -> s s z) s z)) 

(fun s -> fun z -> s s s (fun z -> s s z) z) 

(fun s -> fun z -> s s s s s z) 

Y al final obtenemos la respuesta sorprendente del sucesor del sucesor del sucesor del sucesor del sucesor de cero, más conocido coloquialmente como cinco . Además funciona mediante la sustitución de la zero (o en el que se inicia el recuento) del valor x con el y de valor para definir la multiplicación, que en lugar DIDDLE con el concepto de “sucesor”:

(fun x -> fun y -> fun s -> fun z -> x (y s) z) 

lo dejaré a que permite verificar que el código anterior hace

Wikipedia says

programas imperativos tienden a enfatizar la serie de medidas adoptadas por un programa para llevar a cabo una acción, mientras que los programas funcionales tienden a emphas ize la composición y disposición de funciones, a menudo sin especificar pasos explícitos. Un ejemplo simple ilustra esto con dos soluciones para el mismo objetivo de programación (cálculo de números de Fibonacci). El ejemplo imperativo está en C++.

// Fibonacci numbers, imperative style 
int fibonacci(int iterations) 
{ 
    int first = 0, second = 1; // seed values 

    for (int i = 0; i < iterations; ++i) { 
     int sum = first + second; 
     first = second; 
     second = sum; 
    } 

    return first; 
} 

std::cout << fibonacci(10) << "\n"; 

Una versión funcional (en Haskell) tiene una sensación diferente a él:

-- Fibonacci numbers, functional style 

-- describe an infinite list based on the recurrence relation for Fibonacci numbers 
fibRecurrence first second = first : fibRecurrence second (first + second) 

-- describe fibonacci list as fibRecurrence with initial values 0 and 1 
fibonacci = fibRecurrence 0 1 

-- describe action to print the 10th element of the fibonacci list 
main = print (fibonacci !! 10) 

---

See this PDF also

Answer 2

(A) La programación funcional describe soluciones mecánicamente. Usted define una máquina que está produciendo constantemente de forma correcta, p. con Caml:

let rec factorial = function 
    | 0 -> 1 
    | n -> n * factorial(n - 1);; 

(B) programación de procedimiento describe soluciones temporalmente. Usted describe una serie de pasos para transformar una entrada determinada en la salida correcta, p. con Java:

int factorial(int n) { 
    int result = 1; 
    while (n > 0) { 
    result *= n--; 
    } 
    return result; 
} 

Un lenguaje de programación funcional quiere que hagas (A) todo el tiempo. Para mí, la mayor singularidad tangible de la programación puramente funcional es apatridia: nunca se declaran variables independientemente de para qué se utilizan.