O cálculo lambda não parecia abstrato. E eu não consigo ver o objetivo disso

A questão subjacente:

O que o cálculo lambda faz por nós que não podemos fazer com as propriedades básicas da função e notação geralmente aprendidas na álgebra do ensino médio?

Antes de tudo, o que significa abstrato no contexto do cálculo lambda? Minha compreensão da palavra abstrato é algo que está separado da maquinaria, o resumo conceitual de um conceito.

No entanto, as funções lambda, eliminando os nomes das funções, impedem um certo nível de abstração. Por exemplo:

f(x) = x + 2
h(x, y) = x + 5 y

Mas mesmo sem definir o mecanismo dessas funções, podemos facilmente falar sobre sua composição. Por exemplo:

1. h(x, y) . f(x) . f(x) . h(x, y) or 
2. h . f . f . h

Podemos incluir os argumentos, se quisermos, ou podemos abstrair completamente para dar uma visão geral do que está acontecendo. E podemos reduzi-los rapidamente a uma única função. Vejamos a composição 2. Posso ter camadas de detalhes dos alunos com as quais posso escrever, dependendo da minha ênfase:

g = h . f . f . h
g(x, y) = h(x, y) . f(x) . f(x) . h(x, y)
g(x, y) = h . f . f . h = x + 10 y + 4

Vamos executar o acima com cálculo lambda, ou pelo menos definir as funções. Não sei se isso está certo, mas acredito que a primeira e a segunda expressões aumentam em 2.

(λuv.u(u(uv)))(λwyx.y(wyx))x

E multiplicar por 5y.

(λz.y(5z))

Em vez de ser abstrato, isso parece entrar no próprio mecanismo do que significa somar, multiplicar etc. Abstração, na minha opinião, significa nível superior, e não inferior.

Além disso, estou lutando para ver por que o cálculo lambda é mesmo uma coisa. Qual é a vantagem de

(λuv.u(u(uv)))(λwyx.y(wyx))x

sobre

h(x) = x + 5 y

ou uma notação combinada

Hxy.x+5y

ou até a notação de Haskell

h x y = x + 5 * y

Novamente, o que o cálculo lambda faz por nós que não podemos fazer com as propriedades da função f (x) e a notação com as quais muitos estão familiarizados.

Existem muitas razões pelas quais o cálculo lambda é tão importante.

Uma razão muito importante é que o cálculo lambda nos permite ter um modelo de computação no qual as funções computáveis ​​são cidadãos de primeira classe.

Não se pode expressar funções de ordem superior na linguagem da álgebra do ensino médio.

Tome como exemplo a expressão lambda

Essa expressão simples nos mostra que, dentro do cálculo lambda, a composição da função é ela própria uma função. Na álgebra do ensino médio, isso não é facilmente expresso.

No cálculo lambda, é muito fácil expressar que uma função retornará uma função como resultado.

Aqui está um pequeno exemplo. A expressão (onde eu assumo aqui um cálculo lambda aplicado com adição e constantes inteiras)

reduzirá para

Observe também que dentro do cálculo lambda, funções são expressões e não definições da forma . Isso nos liberta da necessidade de nomear funções e distinguir entre uma categoria sintática de expressões e uma categoria sintática de definições.$f(x) = e$

Além disso, quando se torna impossível (ou apenas notadamente complicado) expressar funções de ordem superior, também se pode ter problemas ao atribuir tipos a expressões.

A composição da função possui o tipo polimórfico

no sistema do tipo Hindley-Milner.

Um ponto de venda muito forte para o cálculo lambda é precisa a noção de cálculo lambda digitado . Os vários sistemas de tipos para linguagens de programação funcional, como Haskell e a família ML, são baseados em sistemas de tipos para cálculos lambda, e esses sistemas de tipos fornecem fortes garantias na forma de teoremas matemáticos:

Se um programa é bem digitado e e reduzido ao e ' residual , então e ' também será bem digitado.$e$$e$$e'$$e'$

E se for bem digitado, e não exibirá certos erros.$e$$e$

As provas como correspondência de programas são particularmente dignas de nota. O isomorfismo de Curry-Howard (veja, por exemplo, https://www.rocq.inria.fr/semdoc/Presentations/20150217_PierreMariePedrot.pdf ) mostra que existe uma correspondência muito precisa entre o cálculo lambda simplesmente digitado e a lógica proposicional intuicionista: para todo tipo corresponde uma fórmula lógica φ T . Uma prova de & Phi T corresponde a uma duração de lambda com tipo T , e uma redução do efeito de beta do Isto corresponde prazo para realizar uma eliminação corte na prova.$T$$\phi_T$$\phi_T$$T$

Exorto aqueles que acham que a álgebra do ensino médio é uma boa alternativa ao cálculo lambda para desenvolver uma descrição da álgebra do ensino médio de ordem superior e tipicamente polimorficamente, juntamente com uma noção apropriada de isomorfismo de Curry-Howard. Se você puder mesmo elaborar um assistente de prova interativo baseado na álgebra do ensino médio que nos permita provar os muitos teoremas que foram formalizados usando assistentes de prova baseados em cálculo lambda, como Coq e Isabelle, isso seria ainda melhor. Eu começaria a usar álgebra no ensino médio e, tenho certeza, muitos outros comigo.

$\mathbb{R}$$\mathbb{R}$

As funções no cálculo lambda são muito mais gerais. A definição exata depende se o seu cálculo lambda é digitado ou não. No cálculo lambda puro e sem tipo, tudo é uma função. Isso é muito mais geral do que as funções reais do cálculo.

Mesmo linguagens procedurais às vezes usam idéias do cálculo lambda. A função de classificação em C aceita como parâmetro uma função de comparação , usada para comparar elementos. O cálculo do Lambda vai muito além - as funções não apenas aceitam funções como entradas, mas também podem produzi-las.

O cálculo Lambda é um modelo de cálculo equivalente em potência às máquinas de Turing. É um sistema completo em si mesmo. O cálculo lambda puro não tem "5" ou "+" como termos primitivos - eles podem ser definidos dentro do cálculo, assim como "5" e "+" não são primitivos da teoria dos conjuntos. (Linguagens de programação práticas implementam números naturais nativamente por razões de eficiência.)

Suspeito que uma das razões pelas quais você não esteja impressionado com o cálculo lambda é que suas idéias permeiam tanto o discurso da programação que ele não parece mais inovador.

$x^2$$x$$x^2$

$\lambda x.x^2$$x^2$

$f$$f(x) = x^2$$f$

O uso de expressões lambda em linguagens de programação tem uma vantagem semelhante; você pode escrever o que a função faz exatamente onde é necessário, em vez de precisar definir uma nova função em outro lugar do seu programa.

$\frac{d}{dx} x^2$$\frac{d}{dx}$$x^2$

$\theta : V \to V^{**}$

Muitas pessoas acham essa notação de dupla avaliação confusa e / ou perturbadora, bem como esse uso recursivo da definição pontual de uma função. A versão de abstração lambda

não tem esse problema.

Finalmente, há um teorema de absurdo abstrato de que "simplesmente digitar lambda calculus" é basicamente a mesma coisa que "categoria fechada cartesiana" - portanto, se você quiser fazer cálculos em uma categoria fechada cartesiana, provavelmente é uma boa ideia usar simplesmente digitou o cálculo lambda para fazer isso.

Vou dizer de antemão que não sou especialista neste tópico, mas passei um pouco de tempo estudando-o e uma das coisas mais fascinantes para mim em qualquer tópico é a história por trás disso. Então, para mim, entender um pouco da história por trás do cálculo lambda ajuda a explicar por que é útil.

O breve resumo é que, no início dos anos 1900, depois que a teoria dos conjuntos começou a decolar e a matemática foi repensada com base em conjuntos, alguns matemáticos notaram que, embora uma definição de teoria dos conjuntos permita alegar que existe uma certa estrutura, eles não dizem como para construí-lo e calculá-lo. Portanto, as definições da teoria dos conjuntos não são construtivas . Os matemáticos começaram a se perguntar se havia uma maneira de desenvolver definições construtivas que iriam além de provar que algo é e, em vez disso, provar como é .

Da Wikipedia :

Em matemática, uma prova construtiva é um método de prova que demonstra a existência de um objeto matemático criando ou fornecendo um método para criar o objeto. Isso contrasta com uma prova não construtiva (também conhecida como prova de existência ou teorema da existência pura) que prova a existência de um tipo específico de objeto sem fornecer um exemplo.

$*$

Foi então mostrado que o cálculo lambda e a máquina de Turing poderiam representar qualquer função computável e, portanto, equivalentes.

Em teoria, qualquer função ou conceito matemático pode ser codificado na forma de cálculo lambda e computado. Isso significa que o cálculo lambda pode ser uma base completamente separada para a matemática, embora obviamente extremamente tediosa.

O cálculo lambda não é "útil" no sentido de que você não escreverá código usando-o, mas forma a base da semântica denotacional, usada para descrever programas e seus efeitos dinâmicos. Isso é usado nas discussões sobre a correção do programa e o significado semântico. Obviamente, também influenciou fortemente o desenvolvimento de linguagens de programação funcionais, que extraem todo o seu conceito de execução do cálculo lambda.

Espero que ajude.

Edite para adicionar: acabei de apontar para este artigo, mostrando a relação entre topologia, cálculo lambda e física. Percorrendo-o brevemente, deparei-me com esta afirmação fantástica:

Enquanto uma máquina de Turing pode ser vista como um modelo simplificado e idealizado de hardware de computador , o cálculo lambda é mais como um modelo simples de software . Poeticamente, o cálculo lambda descreve um universo onde tudo é um programa e tudo é dados: programas são dados .

O ponto é que o cálculo lambda é um modelo idealizado de computação de software e, como tal, não está vinculado a uma implementação específica em nenhuma linguagem de programação. Ele modela a computação pura .

$\lambda$

O cálculo Lambda não foi projetado para ser uma linguagem de programação. De fato, foi criado na década de 1930, décadas antes de termos computadores programáveis. Pelo contrário, foi criado como um modelo formal para o estudo da computação. Se você está decepcionado com a facilidade com que ele expressa código ou funções matemáticas, é porque não é para isso que serve.

O cálculo do Lambda existe para que funções anônimas (também conhecidas como lambda) possam ser criadas. Se você não acabar com os nomes das funções, o espaço para nome poderá ficar desordenado e pode-se ficar sem os nomes das funções disponíveis. Isso é especialmente importante ao lidar com as chamadas "funções de ordem superior" que retornam funções (ou indicadores de função) por razões óbvias.

Essencialmente, as funções lambda são equivalentes às variáveis ​​com escopo local. A programação funcional sem funções lambda é análoga à programação procedural sem nenhuma variável local, ou seja, uma péssima idéia.

"por que o cálculo lambda é mesmo uma coisa" os matemáticos adoram redundância. O cálculo lambda raramente é usado em matemática porque, como você descobriu, a notação não é muito útil.

"Se você puder trabalhar com um assistente de prova interativo baseado na álgebra do ensino médio que nos permita provar os muitos teoremas formalizados usando assistentes de prova baseados em cálculo lambda, como Coq e Isabelle, seria ainda melhor. comece a usar a álgebra do ensino médio e, tenho certeza, muitos outros comigo. " Você já ouviu falar de metamato? Nenhum cálculo lambda envolvido lá pode provar muitos dos teoremas coq / isabelle