Estou iniciando um curso de graduação em ciência da computação no próximo outono, mas não consigo entender o cálculo λ no contexto da programação funcional. Posso estar interpretando mal isso completamente, mas, com base nessa definição da Stanford Encyclopedia of Philosophy, é apenas mais uma notação para funções.
Se é exatamente isso, por que é vantajoso usar o cálculo λ sobre as notações de funções regulares para calcular o tempo de execução do algoritmo?
Respostas:
Em ciência da computação, queremos analisar e entender o código-fonte com rigor matemático. Essa é a única maneira de provar propriedades interessantes (como rescisão) com certeza absoluta. Para isso, precisamos de uma linguagem com um significado muito bem definido para cada construto.
Em teoria, isso poderia ser qualquer linguagem com uma boa semântica formal . Mas, para tornar as coisas menos complicadas e menos propensas a erros, é melhor usar uma linguagem o mais simples possível, mas ainda capaz de expressar qualquer programa (ou seja, Turing está completo ). Para raciocinar sobre códigos imperativos, existem máquinas de Turing . Mas, para raciocinar sobre programação funcional, existe o cálculo.λ
O calcculus básico é como uma linguagem de programação funcional, mas com muita 'bagagem' retirada. Não é importante que seja uma linguagem agradável para escrever programas, nem que seja uma linguagem eficiente. Só que é simples e expressivo. Por exemplo, não precisamos de loops, porque podemos simulá-los com recursão. E não precisamos de funções com vários parâmetros, pois podemos simulá-las com o Currying .λ
Agora, em algum momento, convém provar propriedades sobre construções que não fazem parte do cálculo- básico (sem tipo) . É por isso que os cientistas da computação o estenderam em diferentes direções ao longo dos anos. Por exemplo, para raciocinar sobre sistemas de tipos, existem muitas variações de λ- cálculos digitados .λ λ
fonte
há muitas vantagens em usar o Lisp ou a programação funcional e calcular o tempo de execução do algoritmo é apenas uma possibilidade (embora seja útil se você citar uma referência para isso). uma vez que já está em notação funcional, algumas vezes determinar as fórmulas para o tempo de execução via relações de indução ou recorrência pode ter uma relação mais forte ou mais óbvia com o código original. outros tipos de análise do algoritmo também são simplificados.
Outra vantagem principal é a simplicidade sintática. analisadores para outros idiomas são muito complexos, mas os analisadores Lisp são muito simples. então o Lisp é uma ótima linguagem para estudar a teoria da análise.
outro aspecto fundamental é analisar o software mais de uma lente / visão lógica ou matemática, em vez de uma perspectiva "científica do computador".
como a outra resposta aponta, o Lisp é sobre recursão, em vez de iteração, e a recursão está no coração do CS.
[1] Estrutura e interpretação de programas de computador, por Abelson & Sussman
fonte