Q1(a) ------------------------------------------------------------------------- {with {x 42} {with {f {fun {y} x}} {with {x 1729} {f 0}}}} Em FWAE: 42 Em FWAE/D: 1729 Q1(b) ------------------------------------------------------------------------- {with {f {fun{y} x}} {with {x 1729} {f 0}}} Em FWAE: identificador livre Em FWAE/D: 1729 Q1(c) ------------------------------------------------------------------------- {with {x 42} {with {f {fun {y} {+ x y}}} {with {x {fun {z} 1729}} {f 0}}}} Em FWAE: 42 Em FWAE/D: erro semantico (tentativa de somar numero com funcao) Q2(a) ------------------------------------------------------------------------- {{fun {f} {+ 1 {f 10}}} {fun {x} {+ x x}}} Q2(b) ------------------------------------------------------------------------- ((lambda (f g) (g (f 10))) (lambda (x) (+ x x)) (lambda (x) (+ 1 x))) Q2(c) ------------------------------------------------------------------------- {{fun {f} {{fun {g} {g {f 10}}} {fun {x} {+ 1 x}}}} {fun {x} {+ x x}}} Q3 ---------------------------------------------------------------------------- Na primeira dimensao o que varia e' o momento da substituicao, isto e', QUANDO a substituicao ocorre. A substituicao explicita acontece quando for interpretada a expressao que ESTABELECE um vinculo de um identificador a um objeto. A substituicao postergada acontece quando forem interpretadas as expressoes que USAM o identificador. Na segunda dimensao o que varia e' o QUE e' vinculado, isto e', qual a natureza dos objetos vinculados aos identificadores. Na avaliacao avida, esses objetos sao VALORES (expressoes ja' avaliadas). Na avaliacao preguicosa, eles sao EXPRESSOES ainda nao avaliadas. Q4(a) ------------------------------------------------------------------------- Um fechamento e' um valor que representa uma funcao. Alem de conter as informacoes presentes na definicao da funcao (os nomes dos parametros e o corpo da funcao), ele captura o ambiente (o conjunto de vinculos) em vigor no momento da definicao da funcao. Q4(b) ------------------------------------------------------------------------- Implementar escopo estatico em linguagens que tenham funcoes de primeira classe e usem substituicao postergada. Sem fechamentos, o escopo seria dinamico. Q4(c) ------------------------------------------------------------------------- A necessidade de fechamentos nao existe no regime de substituicao explicita. Q4(d) ------------------------------------------------------------------------- A estrutura fun representa uma definicao de funcao na sintaxe abstrata (como um no' da arvore sintatica). Ela tem um campo com o identificador correspondente ao parametro da funcao (as funcoes do PLAI tem so' um parametro) e outro com o corpo da funcao (uma expressao, tambem representada na sintaxe abstrata). A estrutura closureV representa um fechamento. Ela e' um tipo especifico de valor que pode ser produzido pela avaliacao de uma expressao. A estrutura closureV tem os mesmos campos que a estrutura fun, e mais um campo com o ambiente de definicao da funcao. Esse campo guarda o conjunto de vinculos que estava em vigor quando o fechamento foi criado. Q5 ---------------------------------------------------------------------------- ((lambda (x) 42) (/ 1729 0)) Nao era necessario escrever a traducao para Haskell, que neste caso e' (\ x -> 42) (1729 / 0) Q6(a) ------------------------------------------------------------------------- Quando interpreta aplicacoes de funcoes. Ao interpretar uma aplicacao de funcao, o interpretador cria um fechamento da expressao passada como parametro `a funcao. Ele interpreta o corpo da funcao num ambiente que contem um vinculo entre o parametro formal da funcao (um identificador extraido do fechamento da funcao) e o fechamento da expressao passada como parametro. Q6(b) ------------------------------------------------------------------------- Garantir o escopo estatico numa linguagem com semantica preguicosa. Sem fechamentos de expressoes, o escopo estatico deixaria de funcionar. Q6(c) ------------------------------------------------------------------------- Estes sao os pontos de avaliacao estrita: - Adicao (operacao +): as duas parcelas precisam ser avaliadas estritamente. - Aplicacao de funcao: a expressao correspondente `a funcao precisa ser avaliada estritamente. - Forma condicional (if0): a primeira expressao (que corresponde `a condicao) precisa ser avaliada estritamente. Opcionalmente pode-se tambem fazer com que o nivel superior ("top level") do interpretador seja um ponto de avaliacao estrita extra-linguistico. Dessa forma os fechamentos de expressoes nunca seriam expostos aos usuarios. Q7 ---------------------------------------------------------------------------- Restringiremos nossa atencao `as "chamadas mais interessantes" de interp, isto e', as chamadas que tem alguma novidade no ambiente. Em outras palavras, vamos ignorar as chamadas recursivas a interp que receberem um ambiente igual ao da execucao de interp que efetuou a chamada recursiva. Esta solucao mostra detalhes de representacao de ambientes (mtSub, aSub, aRecSub) mas esses detalhes nao sao importantes. 1. Ambiente externo (ambiente passado como parametro na chamada a interp que avalia a forma rec): (mtSub) 2. Ambiente E passado como parametro na chamada recursiva a interp que avalia o corpo da forma rec: (aRecSub 'fac (box (closureV 'n (if0 ...) E)) (mtSub)) [Aqui o importante e' que o ambiente contido no closureV e' o proprio E!] 3. Ambiente passado como parametro na chamada recursiva a interp que avalia o corpo da funcao na aplicacao {fac 2}: (aSub 'n (numV 2) (aRecSub 'fac (box (closureV 'n (if0 ...) E)) (mtSub)) Como o identificador n nao esta' vinculado a zero, a avaliacao do if0 gera a aplicacao {fac 1}. 4. Ambiente passado como parametro na chamada recursiva a interp que avalia o corpo da funcao na aplicacao {fac 1}: (aSub 'n (numV 1) (aRecSub 'fac (box (closureV 'n (if0 ...) E)) (mtSub)) Como o identificador n nao esta' vinculado a zero, a avaliacao do if0 gera uma chamada {fac 0}. 5. Ambiente passado como parametro na chamada recursiva a interp que avalia o corpo da funcao na aplicacao {fac 0}: (aSub 'n (numV 0) (aRecSub 'fac (box (closureV 'n (if0 ...) E)) (mtSub)) Agora a avaliacao do if0 produz (numV 1). A chamada a interp para {fac 0} devolve esse valor. 6. O valor de {fac 0} e' multiplicado pelo n do ambiente 4 (que tambem e' (numV 1)), produzindo (numV 1), que e' o valor devolvido pela chamada a interp para {fac 1}. 7. O (numV 1) e' multiplicado pelo n do ambiente 3 (que e' (numV 2)), produzindo (numV 2), que e' o valor devolvido pela chamada a interp para {fac 2}. 8. A primeira chamada a interp recebe o resultado da chamada recursiva que interpretou {fac 2} e o devolve como valor da forma rec. Q8 ---------------------------------------------------------------------------- A mutabilidade foi usada na implementacao de avaliacao preguicosa com caching e na implementacao de recursao. No caso da avaliacao preguicosa com caching, um campo tipo box foi adicionado `a estrutura exprV, que representa um fechamento de expressao. No momento da criacao de um fechamento de expressao, essa box e' inicializada com um valor que nao e' um dos possiveis resultados da avaliacao de alguma expressao (e portanto nao pode ser confundido com um valor de expressao). Quando o fechamento de expressao for avaliado estritamente pelo primeira vez, a box sera' atualizada com o valor da expressao representada pelo fechamento de expressao. No caso da recursao foi necessario implementar um ambiente ciclico, isto e', um ambiente E que contem um vinculo entre um identificador e um fechamento que captura o proprio ambiente E. Para isso foi definido um novo tipo de vinculo: o vinculo recursivo (aRecSub), cujo campo valor e' uma box. Na criacao de um vinculo recursivo, essa box e' preenchida com um valor provisorio. Logo em seguida o valor provisorio e' substituido por um fechamento de funcao que captura o ambiente que contem o vinculo recursivo.