API tools faq
paste
VinBR

LP 12/09/2011

VinBR
Apr 28th, 2012
93
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 10.46 KB | None | 0 0
raw download clone embed print report
  1.  
  2. # # # # # # # # # # # # # #
  3. # Linguagens de Programação #
  4. # Prof. Fernando Pereira #
  5. # notasdogarcia.blog.com #
  6. # # # # # # # # # # # # # #
  7.  
  8. Existe um problema matemático que é:
  9. Dada uma linguagem formalmente definida e uma sentença
  10. é possível provar que essa sentença pertence à linguagem?
  11.  
  12. Esse problema foi provado por turing que é um problema indecidível.
  13. Esse problema também foi provado por Alonzo Church que resolveu o mesmo problema um ano antes de turing utilizando
  14. um formalismo chamado "Cálculo Lambida".
  15.  
  16. Vamos falar a respeito desse formalismo nessa aula.
  17. É importante entender que o Cálculo Lambida é tão poderoso quanto uma máquina de turing, sendo portanto uma linguagem de programação válida,
  18. e cuja idéia foi usada como base para linguagens reais de programação.
  19.  
  20. NOTA Aleatória: "Açucar Sintático" é como se chama expressões de programação que comprimem vários comandos em um só, para facilitar o uso da linguagem.
  21. Exemplos disso são: for, while, switch etc.
  22.  
  23. CONCEITO:
  24. Calc Lambida pode ser definido pela gramatica:
  25.  
  26. <E>::= x
  27. | <fun>
  28. | <app>
  29. <fun> ::= <lambida>x.<E>
  30. <app> ::= <E1> <E2>
  31.  
  32. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  33.  
  34. Explicando de forma mais clara:
  35.  
  36. Uma expressão x, é uma variável, e pode significar um nome de função, ou qualquer coisa que voce achar conveniente.
  37.  
  38. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  39.  
  40. Uma função é da forma:
  41.  
  42. (<lambida>x <E>)
  43.  
  44. Mas vou resumir o lambida para <l>, ou seja:
  45.  
  46. (<l>x <E>)
  47.  
  48. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  49.  
  50. Agora o que significa o <l>x?
  51.  
  52. <l>x é uma declaração de um parâmetro.
  53. Ao ler um <l>x voce deve procurar o primeiro valor após o fecha parentesis da função.
  54. Assim para toda vez que voce usar a letra x dentro da função será o mesmo que usar esse parâmetro.
  55. ex:
  56.  
  57. (<l>x x ) 5 = 5
  58. (<l>x x ) y = y
  59. (<l>x x z) y = y z
  60. (<l>x z) y = z (nesse caso a função independia de x)
  61.  
  62. Agora suponha que voce queira 2 parâmetros então faça:
  63.  
  64. (<l>x <l>y y x) 4 5 = 5 4, interessante?k
  65.  
  66. Por fim, lembra que eu disse que o parametro é a primeira coisa depois do fecha parentesis?
  67. Veja um tipo de parâmetro muito usado nessa linguagem:
  68.  
  69. (<l>x x) (<l>y y) 8 = (<l>y y) 8 = 8
  70.  
  71. Ou seja o parametro x ganhou o valor de: (<l>y y) no primeiro passo.
  72. E no segundo o parametro y da segunda função ganhou o valor 8.
  73.  
  74. Nesse linguagem repare que a associatividade é a esquerda.
  75.  
  76. Assim se temos:
  77.  
  78. (<l>x x)y
  79.  
  80. y é chamado de parametro real.
  81. x é chamado de parametro formal.
  82.  
  83. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  84.  
  85. Veja um exemplos de programa:
  86.  
  87. ((<l>x <l>y x y) (<l>z z))w =
  88. (<l>y (<l>z z) y ) w =
  89. (<l>z z) w = w
  90.  
  91. Mantendo sempre a associatividade à esquerda.
  92.  
  93. Outro exercicio igual ao anterior, mas com um posicionamento diferente dos parenteses:
  94.  
  95. (<l>x <l>y x y) ((<l>z z)w) =
  96. (<l>x <l>y x y) w =
  97. (<l>y w y)
  98. Assim a resposta foi uma função.
  99.  
  100. Agora suponha que voce tenha a expressão:
  101.  
  102. (<l>y <l>x (mol(y x)))x
  103.  
  104. Veja que mol é também uma variável assim como qualquer outra, e assim como qualquer outra ela pode ser qualquer coisa.
  105. No caso suponha que ela seja uma função, e cujos parametros serão y e x.
  106.  
  107. Agora veja que resolvendo o <l>y chegamos em um problema.
  108.  
  109. = (<l>x (mol(x x)))
  110.  
  111. Antes <l>x definia o valor de uma única variável (àquela de nome originalmente x)
  112. Após a execução da função <l>y o significado da função <l>x mudou, antes ela fazia mol(y x) sendo y um valor pre definido, e x um parametro da função <l>x.
  113. Agora ela faz mol(x x) sendo ambos parametros dela.
  114.  
  115. Isso é algo que confunde e ocorre de forma não intencional. E quando ocorrer deve ser burlado para manter a coerencia do programa.
  116. Assim podemos mudar o nome de <l>x para <l>w por exemplo, e simplificar nossa vida.
  117.  
  118. (<l>y <l>w (mol(y w)))x
  119.  
  120. Esse programa daria como resposta a função:
  121.  
  122. (<l>w (mol(x, w)))
  123.  
  124. Que preservou o significado de <l>w do inicio ao fim da execução.
  125.  
  126. O nome dado a esse efeito que acabamos de aprender a evitar
  127. é amarração de variável.
  128.  
  129. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  130.  
  131. Agora veja o caso:
  132. (<l>x x(<l>x x))y
  133. Nesse caso temos duas declaraçòes de x.
  134. Assim temos de separa-las pois cada uma fica em um escopo diferente.
  135. Uma analogia razoável é imaginar a declaração de uma variável local em C, cujo nome é o mesmo de uma variável global.
  136.  
  137. Para retirar a ambiguidade vamos fazer da função mais interna uma função diferente da mais externa assim:
  138.  
  139. (<l>x.x(<l>w w))y
  140.  
  141. Assim não havera redeclaração, e o código fica claro.
  142.  
  143. // Em calculo lambida pode-se escrever qualquer algoritimo que seja computável. E é portanto tão poderoso quando uma máquina de turing.
  144.  
  145. // Pre-requisitos minimos para um turing completo:
  146. // - Desvios Condicionais
  147. // - Números
  148. // - Capacidade de soma
  149.  
  150. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  151.  
  152. Agora se calculo lambida é uma linguagem turing completa,
  153. Ela deve ser capaz de expressar números também correto?
  154. E realizar operações matemáticas.
  155.  
  156. Porém até onde vimos parece que todo objeto, ou variável, ou expressão é construido necessáriamente por outras funções.
  157. Se é assim, então como fazer para denotar um número? Bem usando funções também, veja:
  158.  
  159. Números em Calc. Lambida:
  160.  
  161. ZERO = ( <l>s <l>z z )
  162. UM = ( <l>s <l>z s z )
  163. DOIS = ( <l>s <l>z s (s z) )
  164.  
  165. Ou seja, o número ZERO aplica uma função s sobre a variável z 0 vezes.
  166. o número UM aplica uma função s sobre a variável z 1 vez..
  167. e assim por diante.
  168. // Essa definição foi arbitrária do professor e provavelmente pode-se fazer de outras formas.
  169. // Porém imagino que se o professor descreveu essa notação essa deve ser a notação mais comumente usada.
  170.  
  171. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  172.  
  173. Agora ainda faltam algumas coisas para podermos chamar esse conjunto de variáveis de "conjunto de números reais"
  174. O conjunto dos números reais é definido de forma que se X pertence ao conjunto X+1 também pertence,
  175. E portanto para esse conjunto existir deve haver uma função Sucessora de forma que SUC(x) = x+1,
  176. assim temos:
  177.  
  178. Função sucessora:
  179. SUCC = (<l>n <l>y <l>x y(n y x))
  180.  
  181. Agora posso usar:
  182.  
  183. SUCC(ZERO) = (<l>n <l>y <l>x y(n y x))ZERO = (<l>n <l>y <l>x y(n y x))(<l>s <l>z z)
  184.  
  185. Se voce realizar as operações isso necessariamente vai dar UM, o que é interessante não?
  186. Se voce usar como parametro o UM teremos DOIS como resposta e assim por diante.
  187.  
  188. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  189.  
  190. Assim o significado de (n y x) sendo n um número, é aplicar a função y sobre a função x n vezes.
  191.  
  192. Ou seja um número é o número de vezes que se aplica a função a frente sobre seu parametro.
  193.  
  194. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  195.  
  196. Função de soma de dois números:
  197. ADD = (<l>n1 <l>n2 n1 S n2)
  198.  
  199. Assim uma soma de 2 + 3 fica:
  200.  
  201. ADD 2 3 = (<l>n1 <l>n2 n1 SUCC n2) 2 3
  202. substituindo:
  203. 2 SUCC 3
  204.  
  205. Assim vou buscar o sucessor de 3 duas vezes, chegando ao valor CINCO.
  206.  
  207. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  208.  
  209. Como fazer uma função de Multiplicação?
  210.  
  211. MUL = (<l>n1 <l>n2 <l>s n1 (n2 s))
  212.  
  213. Aplicando isso para 2 * 3:
  214.  
  215. ( <l>n1 <l>n2 <l>s n1 (n2 s) ) 2 3
  216.  
  217. Nessa função então eu aplico o número 3 sobre seu parametro duas vezes, ou seja,
  218. se o parametro for x, eu aplico x sobre seu parametro 2*3 = 6 vezes, gerando o número 6 segundo a definição do professor.
  219. mucho loco não?
  220.  
  221. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  222.  
  223. Como fazer uma funçào booleana AND?
  224.  
  225. Vamos definir então que verdadeiro é T e falso é F tal que:
  226.  
  227. T = <l>x <l>y x // ou seja retorna o primeiro elemento
  228. F = <l>x <l>y y // ou seja retorna o segundo elemento
  229.  
  230. Uma funçào AND ficaria:
  231.  
  232. AND = (<l>x <l>y x y F)
  233.  
  234. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  235.  
  236. Como fazer um OR, ou um NOT?
  237.  
  238. OR = (<l>x <l>y x T y)
  239.  
  240. NOT = (<l>x x F T)
  241.  
  242. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  243.  
  244. Como fazer um IF?
  245.  
  246. IF = (<l>c <l>e1 <l>e2 c e1 e2)
  247. // Se c for verdadeiro retorna e1 se for falso e2
  248.  
  249. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  250.  
  251. Função para detectar se é zero.
  252. Z = <l>x x F NOT F
  253.  
  254. Ele mostrou que para 0 essa funçào retorna T e para outros valores F.
  255. Bizarro!
  256.  
  257. // Bem a aula acabou por aqui.
  258. // Bem interessante esse cálculo lambida, mas visívelmente é tão complexo para uso prático quanto a máquina de turing,
  259. // e portanto tem utilidade apenas teorica.
  260. // Mas como se sabe ela assim como a máquina de turing é a base que gerou diversas linguagens, incluindo SML e outras.
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!