Qual é a relação entre cálculo lambda e linguagens de programação? [fechadas]

13

Estou começando meu primeiro ano (na faculdade) em Ciência da Computação no próximo ano e escrevo principalmente em C (se isso for importante). Eu tentei pesquisar, mas a maior parte do que acho assume conhecimento de cálculo lambda. Por que o cálculo lambda é considerado muito mais útil do que o cálculo de variável única no prograrmming? Existe uma relação entre expressões lambda e programas funcionais? Foi o trabalho da Alonzo Church sobre o cálculo lambda que influenciou o desenvolvimento de linguagens de programação?

Todo mundo que fica fora da escola continua falando sobre isso e eu não tenho idéia do que eles estarão falando, mesmo que eu esteja ansiosa para aprender e ver como isso se relaciona diretamente com a minha programação e compreensão das linguagens de programação.

RonaldMunodawafa
fonte
2
Esta pergunta será melhor respondida em cs.stackexchange.com .
Davidk01 18/10/2014
@ChrisF. Talvez essa pergunta se encaixe melhor em um dos sites de ciência da computação. Caso contrário, tentei reduzi-lo e me pergunto se ele pode ser reaberto na sua forma atual.
Tom Au
O Mathematica notou que o cálculo lambda foi feito por ninguém.
William William

Respostas:

26

O Cálculo Lambda é interessante, elegante e facilita muito o entendimento de linguagens de programação funcionais. No entanto, você não encontrará o LC em um curso típico de bacharelado em CS; portanto, não precisa aprender agora - recomendo experimentar primeiro as linguagens funcionais antes de revisar o Cálculo Lambda. Acredito que o OCaml seja um bom ponto de partida para a programação funcional de um programador em C, e que o Scheme seja um bom ponto de partida para mergulhar no Lambda Calculus.

O Cálculo Lambda não está associado ao Cálculo (que deveria ser chamado de Análise). Em geral, um cálculo é um "sistema formal", isto é, um conjunto de regras para fazer alguma coisa. Enquanto o Cálculo diferencial fornece regras sobre a alteração de valores, as regras do Cálculo Lambda descrevem a própria computação. A partir desse conjunto de regras muito básicas, podemos construir cálculos arbitrários, representações de dados como booleanos, números inteiros ou listas e até controlar construções de fluxo, como condicionais ou loops. O LC é equivalente às Máquinas de Turing, mas qualquer um dos modelos possui forças diferentes.

O Lambda Calculus teve um imenso impacto nas linguagens de programação. A segunda linguagem de alto nível a ser implementada foi o Lisp, que pode ser entendido como uma codificação direta do LC em uma linguagem de programação. Essa "programação funcional" tem imenso efeito na evolução das linguagens de programação. Recursos como funções anônimas, ponteiros de função, fechamentos (funções aninhadas), coleta de lixo, escopo variável, metaprogramação, avanços em sistemas de tipos, inferência de tipos, linguagens interpretadas, linguagens dinamicamente tipadas, programação orientada a objetos são todos devidos a uma grande parte para o ramo de programação funcional das linguagens de programação. Há uma piada de que qualquer nova linguagem de programação (não acadêmica) apenas adiciona recursos que o Lisp já possui há décadas.

Além disso, o Cálculo Lambda e outros cálculos relacionados são ferramentas indispensáveis ​​na teoria da linguagem de programação e em certas técnicas de construção de compiladores.

Qualquer linguagem que possua funções anônimas que se comportem como fechamentos e possam ser passadas livremente imediatamente contém uma codificação do cálculo lambda. Funções anônimas correspondem a expressões lambda, exceto que nas funções LC sempre há exatamente um argumento. No entanto, qualquer idioma completo de Turing é equivalente ao LC, portanto, o LC sempre pode ser implementado no topo desses idiomas. Isso costuma ocorrer em sistemas de correspondência de regras ou em formatos de configuração excessivamente inteligentes, dando origem à “décima regra de Greenspun” (em tom de brincadeira - principalmente): “ Qualquer programa C ou Fortran suficientemente complicado contém um programa ad hoc, especificado informalmente e com erros , implementação lenta de metade do Common Lisp. "

amon
fonte
Esta é uma resposta melhor do que a que eu havia selecionado antes. Sua resposta realmente chega em casa. Era exatamente isso que eu estava procurando!
RonaldMunodawafa
"... exceto que nas funções LC sempre há exatamente um argumento": esse recurso é chamado de currying ou pelo menos está relacionado a ele?
Giorgio
@Giorgio Currying é diferente, mas relacionado. O LC não possui funções com vários argumentos, mas essas podem ser simplesmente codificadas como funções aninhadas que recebem um argumento cada. Exemplo usando a notação ML: x = fn (a, b, c) => a + b + c(tipo int * int * int -> int, invocação fn (1, 2, 3)) pode ser transformado em x = fn a => fn b => fn c => a + b + c(tipo int -> int -> int -> int, invocação ((x 1) 2) 3- parens opcional em ML). Agora, em vez de fornecer todos os três argumentos, também podemos fornecer apenas dois: plus3 = x 1 2que possui tipo int -> int. Isto é aplicação parcial / currying.
amon
Eu pensei que curry significava ter todas as funções usando apenas um argumento (como no LC).
Giorgio
8

O cálculo Lambda não tem nada a ver com cálculo diferencial / integral. Cálculo no sentido mais genérico da palavra significa apenas um sistema de cálculo.

Em um nível muito alto, o cálculo lambda é um modelo de computação da mesma forma que uma máquina de turing é um modelo de computação. A razão pela qual os pesquisadores de linguagem de programação estudam o cálculo lambda é porque, como modelo, ele tem fortes conexões com métodos formais em matemática, como lógica e teoria de categorias. Portanto, os métodos desses domínios podem ser aplicados ao estudo de vários aspectos e extensões do cálculo lambda, o que, por sua vez, ajuda a projetar melhores linguagens de programação com determinadas propriedades.

A influência mais direta do cálculo lambda nas linguagens de programação geralmente aparece na forma de funções e fechamentos de primeira classe. C não tem suporte para fechamentos e, portanto, você precisará explorar o conceito em uma linguagem de alto nível como Lisp, Python, Ruby, JavaScript etc. Historicamente, o Lisp é considerado a primeira implementação concreta do cálculo lambda como uma linguagem de programação .

davidk01
fonte
1
Você pode mencionar idiomas específicos muito próximos do cálculo lambda, por exemplo, Lisp.
Giorgio
1
Ainda estou aprendendo o Scheme usando o SICP e espero aprender mais sobre esta área. Obrigado pela sua resposta e sugestão elaboradas.
RonaldMunodawafa