b'\n_START_ARTICLE_\nC\xc3\xa1lculo lambda\n_START_PARAGRAPH_\nNa l\xc3\xb3gica matem\xc3\xa1tica e na ci\xc3\xaancia da computa\xc3\xa7\xc3\xa3o, lambda c\xc3\xa1lculo , tamb\xc3\xa9m escrito como c\xc3\xa1lculo-\xce\xbb \xc3\xa9 um sistema formal que estuda fun\xc3\xa7\xc3\xb5es recursivas comput\xc3\xa1veis, no que se refere a teoria da computabilidade, e fen\xc3\xb4menos relacionados, como vari\xc3\xa1veis ligadas e substitui\xc3\xa7\xc3\xa3o. Sua principal caracter\xc3\xadstica s\xc3\xa3o as entidades que podem ser utilizadas como argumentos e retornadas como valores de outras fun\xc3\xa7\xc3\xb5es._NEWLINE_A parte relevante de lambda c\xc3\xa1lculo  para computa\xc3\xa7\xc3\xa3o ficou conhecida como lambda c\xc3\xa1lculo  n\xc3\xa3o-tipado. O lambda c\xc3\xa1lculo  tipado e o n\xc3\xa3o-tipado tem suas ideias aplicadas nos campos da l\xc3\xb3gica, teoria da recurs\xc3\xa3o (computabilidade) e lingu\xc3\xadstica, e tem tido um grande papel no desenvolvimento da teoria de linguagens de programa\xc3\xa7\xc3\xa3o (com a vers\xc3\xa3o n\xc3\xa3o-tipada sendo a inspira\xc3\xa7\xc3\xa3o original para programa\xc3\xa7\xc3\xa3o funcional, em particular Lisp, e a vers\xc3\xa3o tipada contribuindo para fundamentar modernos sistemas de tipos e linguagens de programa\xc3\xa7\xc3\xa3o). Neste artigo, a vers\xc3\xa3o n\xc3\xa3o-tipada ser\xc3\xa1 discutida largamente.\n_START_SECTION_\nHist\xc3\xb3ria\n_START_PARAGRAPH_\nLambda c\xc3\xa1lculo  foi apresentada por Alonzo Church na d\xc3\xa9cada de 1930 como parte da investiga\xc3\xa7\xc3\xa3o dos fundamentos da matem\xc3\xa1tica. O sistema original foi demonstrado ser logicamente inconsistente em 1935 quando Stephen Kleene e J. Barkley Rosser desenvolveram o paradoxo Kleene-Rosser._NEWLINE_Em seguida, em 1936, Church isolou e publicou apenas a computa\xc3\xa7\xc3\xa3o e que depois ficou conhecida como lambda c\xc3\xa1lculo  n\xc3\xa3o-tipado. Em 1940, ele tamb\xc3\xa9m apresentou uma vers\xc3\xa3o computacionalmente mais fraca, mas com um sistema l\xc3\xb3gico consistente, conhecido como lambda c\xc3\xa1lculo  simplesmente tipado._NEWLINE_Alonzo Church foi orientador de Alan Turing. De certa forma, o trabalho de Church est\xc3\xa1 para o conceito de software assim como o de Turing relaciona-se muito diretamente ao conceito de Hardware.\n_START_SECTION_\nO C\xc3\xa1lculo Lambda\n_START_PARAGRAPH_\nO c\xc3\xa1lculo lambda consiste de uma linguagem de termos lambda junto com uma teoria equacional (que pode tamb\xc3\xa9m ser entendida operacionalmente)._NEWLINE_Como os nomes de fun\xc3\xa7\xc3\xb5es s\xc3\xa3o uma mera conveni\xc3\xaancia, o lambda c\xc3\xa1lculo  n\xc3\xa3o tem interesse em nomear uma fun\xc3\xa7\xc3\xa3o. J\xc3\xa1 que todas as fun\xc3\xa7\xc3\xb5es esperando mais de um argumento podem ser transformadas em fun\xc3\xa7\xc3\xb5es equivalentes recebendo uma \xc3\xbanica entrada (via Currying), o lambda c\xc3\xa1lculo  n\xc3\xa3o tem interesse em criar fun\xc3\xa7\xc3\xb5es que aceitam mais de um argumento. E como os nomes dos argumentos s\xc3\xa3o irrelevantes, a no\xc3\xa7\xc3\xa3o nativa de igualdade entre termos lambda se chama equival\xc3\xaancia-alpha e que demonstra este princ\xc3\xadpio.\n_START_SECTION_\nFun\xc3\xa7\xc3\xb5es que operam em fun\xc3\xa7\xc3\xb5es\n_START_PARAGRAPH_\nEm lambda c\xc3\xa1lculo , fun\xc3\xa7\xc3\xb5es s\xc3\xa3o consideradas como valores, ent\xc3\xa3o elas podem servir de entrada para outras fun\xc3\xa7\xc3\xb5es, e fun\xc3\xa7\xc3\xb5es podem retornar fun\xc3\xa7\xc3\xb5es como sa\xc3\xadda._NEWLINE_Por exemplo, \xce\xbbx.x representa a fun\xc3\xa7\xc3\xa3o identidade, x \xe2\x86\xa6 x, e (\xce\xbbx.x)y representa a fun\xc3\xa7\xc3\xa3o identidade aplicada a y. E assim, (\xce\xbbx.y) representa a fun\xc3\xa7\xc3\xa3o constante x \xe2\x86\xa6 y, uma fun\xc3\xa7\xc3\xa3o que sempre retorna, independentemente da entrada. \xc3\x89 importante ressaltar que a aplica\xc3\xa7\xc3\xa3o de fun\xc3\xa7\xc3\xb5es \xc3\xa9 associativa \xc3\xa0 esquerda, ent\xc3\xa3o (\xce\xbbx.x)y z = ((\xce\xbbx.x)y)z._NEWLINE_O que torna os termos ainda mais interessantes s\xc3\xa3o as v\xc3\xa1rias no\xc3\xa7\xc3\xb5es de equival\xc3\xaancia e redu\xc3\xa7\xc3\xa3o que podem ser definidas sobre eles.\n_START_SECTION_\nAlfa-equival\xc3\xaancia\n_START_PARAGRAPH_\nUma forma b\xc3\xa1sica de equival\xc3\xaancia, definida para termos lambda, \xc3\xa9 chamada de alfa-equival\xc3\xaancia._NEWLINE_Ela determina que a escolha da vari\xc3\xa1vel ligada, na abstra\xc3\xa7\xc3\xa3o lambda, n\xc3\xa3o importa (normalmente)._NEWLINE_Por exemplo, \xce\xbbx.x e \xce\xbby.y s\xc3\xa3o termos lambda alfa-equivalentes, representando a mesma fun\xc3\xa7\xc3\xa3o identidade._NEWLINE_Perceba que os termos x e y n\xc3\xa3o s\xc3\xa3o alfa-equivalentes, porque eles n\xc3\xa3o est\xc3\xa3o ligados por uma abstra\xc3\xa7\xc3\xa3o lambda._NEWLINE_Em muitos casos, \xc3\xa9 f\xc3\xa1cil de identificar termos lambda equivalentes._NEWLINE_As pr\xc3\xb3ximas defini\xc3\xa7\xc3\xb5es ser\xc3\xa3o necess\xc3\xa1rias para que a defini\xc3\xa7\xc3\xa3o de beta-redu\xc3\xa7\xc3\xa3o seja poss\xc3\xadvel.\n_START_SECTION_\nVari\xc3\xa1veis livres\n_START_PARAGRAPH_\nAs vari\xc3\xa1veis livres de um termo s\xc3\xa3o aquelas vari\xc3\xa1veis que n\xc3\xa3o s\xc3\xa3o ligadas por uma abstra\xc3\xa7\xc3\xa3o lambda._NEWLINE_Isto \xc3\xa9, as vari\xc3\xa1veis livres de x s\xc3\xa3o apenas x; as vari\xc3\xa1veis livres de \xce\xbbx.t s\xc3\xa3o as vari\xc3\xa1veis livres de t, com x removido, e as vari\xc3\xa1veis livres de ts s\xc3\xa3o a uni\xc3\xa3o das vari\xc3\xa1veis livres de t e s._NEWLINE_Por exemplo, o termo lambda representando a fun\xc3\xa7\xc3\xa3o identidade \xce\xbbx.x n\xc3\xa3o tem vari\xc3\xa1veis livres, mas a fun\xc3\xa7\xc3\xa3o constante \xce\xbbx.y tem uma \xc3\xbanica vari\xc3\xa1vel livre, y.\n_START_SECTION_\nRedu\xc3\xa7\xc3\xa3o Beta\n_START_PARAGRAPH_\nA regra de redu\xc3\xa7\xc3\xa3o beta afirma que uma aplica\xc3\xa7\xc3\xa3o da forma  reduz para o termo . A nota\xc3\xa7\xc3\xa3o  \xc3\xa9 usada para indicar que  beta reduz para . Por exemplo, para todo , . Isto demostra que  realmente \xc3\xa9 a fun\xc3\xa7\xc3\xa3o identidade. De forma semelhante, , Que demonstra que  e uma fun\xc3\xa7\xc3\xa3o constante._NEWLINE_O lambda c\xc3\xa1lculo  pode ser visto como uma linguagem de programa\xc3\xa7\xc3\xa3o funcional idealizada. Como Haskell ou Standard ML. Sob este ponto de vista beta redu\xc3\xa7\xc3\xa3o corresponde a um passo de computa\xc3\xa7\xc3\xa3o. Este passo pode ser repetido por convers\xc3\xb5es beta adicionais at\xc3\xa9 que n\xc3\xa3o haja mais redu\xc3\xa7\xc3\xb5es beta. Em lambda c\xc3\xa1lculo n\xc3\xa3o tipado, como este apresentado aqui, este processo pode n\xc3\xa3o terminar em alguns casos. Um exemplo \xc3\xa9 o seguinte, considere o termo . Assim temos . Isto \xc3\xa9, o termo reduz para ele mesmo em um passo da beta redu\xc3\xa7\xc3\xa3o, e portanto o processo de redu\xc3\xa7\xc3\xa3o nunca termina._NEWLINE_Outro aspecto do lambda c\xc3\xa1lculo n\xc3\xa3o tipado \xc3\xa9 que ele n\xc3\xa3o faz distin\xc3\xa7\xc3\xa3o entre diferentes tipos de dados. Por exemplo, ele pode n\xc3\xa3o ter interesse em escrever uma fun\xc3\xa7\xc3\xa3o que apenas opera com n\xc3\xbameros. Contudo, em um lambda c\xc3\xa1lculo n\xc3\xa3o tipado, n\xc3\xa3o h\xc3\xa1 nenhuma maneira de impedir uma fun\xc3\xa7\xc3\xa3o de ser aplicadas a valores de verdade, strings ou outros objetos n\xc3\xa3o-num\xc3\xa9ricos.\n_START_SECTION_\n\xce\xb1-convers\xc3\xa3o\n_START_PARAGRAPH_\nAlpha-convers\xc3\xa3o, \xc3\xa0s vezes \xc3\xa9 conhecida como alfa-renomea\xc3\xa7\xc3\xa3o, permite alterar nomes de vari\xc3\xa1veis ligadas. Por exemplo, alpha-convers\xc3\xa3o de \xce\xbbx.x pode produzir \xce\xbby.y. Termos que diferem apenas por alfa-convers\xc3\xa3o s\xc3\xa3o chamados \xce\xb1-equivalente. Freq\xc3\xbcentemente, no lambda c\xc3\xa1lculo , termos alfa-equivalente s\xc3\xa3o considerados equivalentes._NEWLINE_As regras para a alfa-convers\xc3\xa3o n\xc3\xa3o s\xc3\xa3o completamente triviais. Primeiro, quando alfa-convers\xc3\xa3o atua em uma abstra\xc3\xa7\xc3\xa3o, as \xc3\xbanicas ocorr\xc3\xaancias de vari\xc3\xa1veis que podem ser renomeados s\xc3\xa3o aqueles que s\xc3\xa3o vinculados a esta mesma abstra\xc3\xa7\xc3\xa3o. Por exemplo, um alfa-convers\xc3\xa3o de \xce\xbbx.\xce\xbbx.x  poderia resultar em \xce\xbby.\xce\xbbx.x, mas n\xc3\xa3o pode resultar em \xce\xbby.\xce\xbbx.y. Este \xc3\xbaltimo tem um significado diferente do original._NEWLINE_Em segundo lugar, alfa-convers\xc3\xa3o n\xc3\xa3o \xc3\xa9 poss\xc3\xadvel se isto iria resultar em uma vari\xc3\xa1vel sendo capturada por uma abstra\xc3\xa7\xc3\xa3o diferente. Por exemplo, se substituirmos x com y em \xce\xbbx.\xce\xbby.x, n\xc3\xb3s obter\xc3\xadamos \xce\xbby.\xce\xbby.y, que tem um significado diferente da express\xc3\xa3o anterior._NEWLINE_Em linguagens de programa\xc3\xa7\xc3\xa3o com escopo est\xc3\xa1tico, alfa-convers\xc3\xa3o pode ser usado para fazer name resolution garantindo que nenhum nome de vari\xc3\xa1vel masks um nome em um determinado escopo (veja alpha renaming to make name resolution trivial)._NEWLINE_Na nota\xc3\xa7\xc3\xa3o De Bruijn index, quaisquer dois termos alfa-equivalente s\xc3\xa3o literalmente id\xc3\xaanticos.\n_START_SECTION_\nSubstitui\xc3\xa7\xc3\xa3o\n_START_PARAGRAPH_\nSubstitui\xc3\xa7\xc3\xa3o, escrito E[V\xc2\xa0:= R], \xc3\xa9 o processo de substitui\xc3\xa7\xc3\xa3o de todas as ocorr\xc3\xaancias da vari\xc3\xa1vel livre V na express\xc3\xa3o E pela express\xc3\xa3o R. Substitui\xc3\xa7\xc3\xa3o de termos em \xce\xbb-c\xc3\xa1lculo \xc3\xa9 definido por recurs\xc3\xa3o sobre a estrutura de termos, do seguinte modo (note: x e y s\xc3\xa3o apenas as vari\xc3\xa1veis enquanto M e N s\xc3\xa3o alguma \xce\xbb express\xc3\xa3o)._NEWLINE_x[x\xc2\xa0:= N] \xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xe2\x89\xa1 N_NEWLINE_y[x\xc2\xa0:= N] \xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xe2\x89\xa1 y, se x \xe2\x89\xa0 y_NEWLINE_(M\xe2\x82\x81 M\xe2\x82\x82)[x\xc2\xa0:= N]\xc2\xa0 \xe2\x89\xa1 (M\xe2\x82\x81[x\xc2\xa0:= N]) (M\xe2\x82\x82[x\xc2\xa0:= N])_NEWLINE_(\xce\xbbx.M)[x\xc2\xa0:= N] \xc2\xa0\xe2\x89\xa1 \xce\xbbx.M_NEWLINE_(\xce\xbby.M)[x\xc2\xa0:= N] \xc2\xa0\xe2\x89\xa1 \xce\xbby.(M[x\xc2\xa0:= N]), se x \xe2\x89\xa0 y, e y \xe2\x88\x89 FV(N)_NEWLINE_Para substituir em uma abstra\xc3\xa7\xc3\xa3o lambda, \xc3\xa0s vezes \xc3\xa9 necess\xc3\xa1rio algo converter \xce\xb1-express\xc3\xa3o. Por exemplo, n\xc3\xa3o \xc3\xa9 correto para (\xce\xbbx.y) [y = x:] para resultar em (\xce\xbbx.x), porque o x substitu\xc3\xaddo era suposto ser livre, mas acabou sendo ligado. A substitui\xc3\xa7\xc3\xa3o correta neste caso \xc3\xa9 (\xce\xbbz.x), pela \xce\xb1-equival\xc3\xaancia. Observe que a substitui\xc3\xa7\xc3\xa3o \xc3\xa9 definida exclusivamente at\xc3\xa9 a \xce\xb1-equival\xc3\xaancia.\n_START_SECTION_\n\xce\xb2-redu\xc3\xa7\xc3\xa3o\n_START_PARAGRAPH_\nBeta-redu\xc3\xa7\xc3\xa3o capta a ideia de aplica\xc3\xa7\xc3\xa3o de fun\xc3\xa7\xc3\xa3o. Beta-redu\xc3\xa7\xc3\xa3o \xc3\xa9 definida em termos de substitui\xc3\xa7\xc3\xa3o: a beta-redu\xc3\xa7\xc3\xa3o de ((\xce\xbbV.E) E\xe2\x80\xb2)\xc2\xa0 \xc3\xa9 E[V\xc2\xa0:= E\xe2\x80\xb2]._NEWLINE_Por exemplo, assumindo alguns codifica\xc3\xa7\xc3\xa3o de 2, 7, \xc3\x97, temos a seguinte \xce\xb2-redu\xc3\xa7\xc3\xa3o: ((\xce\xbbn.n\xc3\x972) 7) \xe2\x86\x92 7\xc3\x972.\n_START_SECTION_\n\xce\xb7-convers\xc3\xa3o\n_START_PARAGRAPH_\nEta-convers\xc3\xa3o expressa a ideia de extensionalidade, que neste contexto \xc3\xa9 que duas fun\xc3\xa7\xc3\xb5es s\xc3\xa3o as mesmas se e somente se eles d\xc3\xa3o o mesmo resultado para todos os argumentos. Eta-convers\xc3\xa3o converte entre \xce\xbbx.(f x) e f sempre que x n\xc3\xa3o aparece livre em f.\n_START_SECTION_\nForma normal e conflu\xc3\xaancia\n_START_PARAGRAPH_\nPara o lambda c\xc3\xa1lculo  n/tipado, \xce\xb2-redu\xc3\xa7\xc3\xa3o como uma rewriting rule n\xc3\xa3o \xc3\xa9 nem strongly normalising nem weakly normalising._NEWLINE_No entanto, se puder ser demonstrado que a \xce\xb2-redu\xc3\xa7\xc3\xa3o \xc3\xa9 confluent. (\xc3\x89 claro que estamos a trabalhar livre \xce\xb1-convers\xc3\xa3o, ou seja, n\xc3\xb3s consideramos duas formas normais para ser igual, se \xc3\xa9 poss\xc3\xadvel \xce\xb1-converter um para o outro.)_NEWLINE_Portanto, ambos os termos fortemente normalizados e termos fracamente normalizados tem uma forma normal \xc3\xbanico. Para termos fortemente normaliz\xc3\xa1veis, qualquer estrat\xc3\xa9gia de redu\xc3\xa7\xc3\xa3o \xc3\xa9 garantida para alcan\xc3\xa7ar a forma normal, enquanto que para termos fracamente normaliz\xc3\xa1veis, algumas estrat\xc3\xa9gias de redu\xc3\xa7\xc3\xa3o pode n\xc3\xa3o conseguir encontr\xc3\xa1-lo.\n_START_SECTION_\nCodificando tipos de dados\n_START_PARAGRAPH_\nO lambda c\xc3\xa1lculo b\xc3\xa1sico pode ser usado para modelar booleano, aritm\xc3\xa9tica, estruturas de dados e a recursividade, como ilustrado nas subsec\xc3\xa7\xc3\xb5es seguintes.'