Christiano Braga cbragacbraga/lp/lp.pdf · Conteudo I 1 Introdu˘c~ao Objetivo Motiva˘c~ao 2 Valores e tipos Tipos primitivos Tipos compostos Tipos recursivos Sistemas de tipos Express~oes

Linguagens de programacao

Christiano Bragahttp://www.ic.uff.br/~cbraga

Instituto de ComputacaoUniversidade Federal Fluminense

(Ultima atualizacao: 23 de maio de 2012.)

http://www.ic.uff.br/~cbraga

Conteudo I1 Introducao

ObjetivoMotivacao

2 Valores e tiposTipos primitivosTipos compostosTipos recursivosSistemas de tiposExpressoes

3 Semantica operacionalFundamentosExemplo

4 Semantica formal de expressoes

5 Amarracoes e escopoAssociacoes e o ambienteEscopo

C. Braga (UFF) Linguagens de programacao 2 / 149

Conteudo IIComposicao e escopoBlocosSemantica operacional de declaracoes

6 Variaveis e a memoriaVariaveis e a memoriaComandosSemantica operacional de comandos

7 AbstracoesSemantica operacional de abstracoes


Introducao Objetivo

Objetivo do curso, aulas e avaliacoes

Objetivo

Apresentar conceitos basicos de linguagens de programacao sob a otica dasemantica formal.

Pagina do curso: http://www.ic.uff.br/~cbraga/lp: verferiados, aulas a avaliacoes.

Bibliografia:

David Watt, Programming Language Design Concepts, John Wiley &Sons, 2004Peter Mosses, Fundamental Concepts and Formal Semantics ofProgramming Languages, notas de aula, 2002


http://www.ic.uff.br/~cbraga/lp

Introducao Motivacao

Motivacao

Por que estudar conceitos de linguagens de programacao?

Linguagens aparecem em diferentes disciplinas da ciencia dacomputacao:

Ao programar: programas sao escritos numa linguagem deprogramacao. (Ex: Java)Ao especificar: formulas sao escritas numa linguagem logica. (Ex:logica de 1a. ordem)Ao formalizar: modelos computacionais sao descritos numa linguagemformal. (Ex: maquina de Turing)

Quando entendemos o significado das construcoes de uma linguagemde programacao (declaracoes ou comandos, por exemplo), somoscapazes de escrever programas “melhores”, isto e, corretos eeficientes.



Motivacao (cont.)

Entender os conceitos basicos de linguagens de programacao nosauxilia no design (projeto) de novas linguagens.

Hoje em dia o projeto de linguagens e mais “mundano”nodesenvolvimento de software do que se pensa. No chamadodesenvolvimento de software dirigido a modelos (DDM) o projeto delinguagens e tarefa essencial.

Em DDM sistemas sao gerados automaticamente a partir de modelosque por sua vez sao descritos em linguagens de modelagem numprocesso similar ao de compilacao de programas.



Motivacao (cont.)

Como estudar linguagens de programacao?Neste curso:

analisaremos conceitos basicos comuns a (maioria das) linguagens deprogramacao,

entenderemos seu significado formal, isto e, sob a perspectiva de ummodelo preciso,

estudaremos diferentes paradigmas de linguagens de programacao,isto e, diferentes modelos computacionais.



Caracterısticas de linguagens de programacao

Sintaxe, semantica e pragmatica

Turing-completude

Paradigma: orientado a objetos, imperativo, funcional, logico e/ouconcorrente. (Nota: nao sao exclusivos!)


Valores e tipos Tipos primitivos

Tipos

Um tipo e um conjunto de elementos mais as operacoes sobre oconjunto.

Identificamos {true, false} como um conjunto por percebermosoperacoes como =,∧ ou ∨.

O conjunto {13, true,monday} nao possui, aparentemente, operacoessobre ele.



Tipos primitivos

Um valor primitivo e um que nao pode ser decomposto em valoresmais primitivos.

Um tipo primitivo e aquele cujos valores sao primitivos.

Em geral, tipos primitivos sao pre-definidos (built-in) numa linguagemde programacao.



Problemas com tipos primitivos

A escolha errada de um tipo primitivo pode trazer problemas pararepresentar apropriadamente um domınio.

O tipo int em Java e capaz de representar valores em{−2.147.483.648, . . . ,+2.147.483.647}. Se um programa em Javadeclara uma variavel do tipo int para representar a populacao daterra, provavelmente tera problemas pois atualmente (entre 6 e 7bilhoes de pessoas) este valor e maior do que a capacidade do tipo.

Outro problema e quando a representacao do tipo depende daplataforma. Por exemplo, se declaramos em C uma variavel do tipoint para representar valores maiores que 216 − 1, este programa teraproblemas quando executado em maquinas com inteiros de 16 bits.



Exemplos de Tipos primitivos

Enumeracoes: um tipo e definido pela definicao explıcita de seuselementos. Ex em C++: enum Month {jan, feb, mar, apr,may, jun, jul, aug, sep, oct, nov, dec} ;

Tipo primitivo discreto: e um tipo primitivo que possui uma bijecaocom um subconjunto dos inteiros. O tipo Character e um exemploem ADA:

freq: array (Character) of Natural ;...for ch in Character loop

freq(ch) := 0 ;end loop ;

Em ADA, uma enumeracao tambem pode ser utilizada como ındicenum array.


Valores e tipos Tipos compostos

Tipos compostos

Um valor composto e constituıdo resultado da composicao de valoresprimitivos ou um valores composto.

Um tipo composto e aquele que possui valores compostos comoelementos de seu conjunto.

Os principais mecanismos de composicao sao:

Produto cartesiano (estruturas)Mapas (vetores)Uniao disjunta (objetos)Tipos recursivos (listas)



Produto cartesiano

Nos referimos aqui ao conceito matematico de produto cartesiano.

Dados dois conjuntos S e T , o produto cartesiano S × T e umconjunto onde cada elemento e um par 〈s, t〉 onde s ∈ S e t ∈ T .

Uma estrutura, na linguagem C por exemplo, e um produtocartesiano:

struct Date {Month m ;byte d ;

}Date = {jan, feb,mar , . . . , sep, oct, nov , dec} × {0, . . . , 255}



Mapa

Mapas representam as relacoes entre todos os elementos de umconjunto em outro.

Formam a base de vetores e funcoes.

O conjunto de todos os mapas de S em T eS → T = {m | s ∈ S ⇒ m(s) ∈ T}.



Mapa × Produto cartesiano

#(S → T ) = (#T )#S

#(S × T ) = #S ×#T



Vetores sao mapas

As operacoes basicas sobre vetores sao: construcao e indexacao.

Vetor bi-dimensional em ADA:

type Xrange is range 0 .. 511 ;type Yrange is range 0 .. 255 ;type Window is array (Xrange, Yrange) of Pixel ;...w(8,12)

Window = {0, . . . , 511} × {0, . . . , 255} → Pixel



Funcoes sao mapas

Funcoes tem parametros e um tipo de retorno.

Funcao implementando um mapa em C++:

bool isEven (int n) {return (n % 2 == 0);

}{. . . , 0→ true, 1→ false, 2→ true, 3→ false, . . .}



Uniao disjunta

Um elemento de uma uniao disjunta e um dos elementos escolhidodentre os conjuntos (possivelmente distintos) sendo unidos.

Os elementos (chamados variantes) sao marcados de forma a indicarsua origem. Ex.:

S + T = {left x | x ∈ S} ∪ {right y | y ∈ T}

Operacoes: construcao (+), marcacao (left e right, no exemploacima), e projecao (que permite obter o variante a partir do elementoda uniao disjunta).

Qual a cardinalidade da uniao disjunta #(S + T )?



Tipos algebricos em Haskell

(Haskell e uma linguagem funcional.)

data Number = Exact Int | Inexact Float

Quais sao os valores do tipo Number?



Tipos algebricos em Haskell

Exemplo:

let pi = Inexact 3.1416 in . . .

rounded num =case num ofExact i -> iInexact r -> round r

A funcao rounded utiliza pattern matching.



Uniao × uniao disjunta

Numa uniao “normal”(nao-disjunta) nao existe marcacao queidentifique a origem do variante.

Este e o caso, por exemplo, nas linguagens C e C++.

A escolha de um elemento de um conjunto e insegura uma vez quenao existe o marcador para garantir a origem do elemento.

E necessaria disciplina do programador para o acesso correto.

enum Accuracy {exact, inexact};struct Number{

Accuracy acc;union {int ival; /* used when acc contains exact */float rval; /* used when acc contains inexact */

} content;} ;



Tipos identificados (discriminated types) em ADA

Exercıcio: entender os exemplos das paginas 29 e 30 do livro texto.



Classes como unioes disjuntas

Objetos como tuplas × tuplas marcadas. Por que escolher a 2a.opcao?

Qual a semantica de heranca?

Qual e o conjunto que representa a declaracao abaixo:

class Point {private float x, y;

. . . // methods}class Circle extends Point {private float r;

. . . // methods}class Rectangle extends Point{private float w, h;

. . . // methods}

Point(Float × Float) +Circle(Float × Float × Float) +Rectangle(Float × Float ×Float × Float)


Valores e tipos Tipos recursivos

Tipos recursivos

Sao tipos auto-referentes.

Listas e strings sao exemplos.



Lista

E uma sequencia de valores de tamanho indefinido.

Pode ser homogenea ou heterogenea.

Operacoes:

lengthemptiness testhead selection (i.e., selection of the list’s frst component)tail selection (i.e., selection of the list consisting of all but the firstcomponent)concatenation



Lista de inteiros

Integer -List = nil Unit + cons(Integer × Integer -List), ouInteger -List = {nil()} ∪ {cons(i , l) | i ∈ Integer , l ∈ Integer -List}

Quais sao as solucoes para estas equacoes?



Lista de inteiros

Uma solucao:

{nil}∪ {cons(i , nil) | i ∈ Integer}∪ {cons(i , cons(j , nil)) | i , j ∈ Integer}∪ {cons(i , cons(j , cons(k, nil))) | i , j , k ∈ Integer}∪ . . .

Ou seja, o conjunto

{cons(i1, cons(. . . , cons(in, nil) . . .)) | n ≥ 0; i1, . . . , in ∈ Integer}.



Lista de inteiros

Outra solucao e incluir tambem listas infinitas.

Esta solucao e viavel computacionalmente?



Listas: o caso geral

T ∗ = Unit + (T × T ∗), cuja menor solucao corresponde as listas (detamanho finito) de valores de T .



Listas em Haskell

data IntList = Nil | Cons Int IntList

NilCons 13 NilCons 2 (Cons 3 (Cons 5 (Cons 7 Nil)))

Built-in list types examples:

[Int] (whose values are integer lists)

[String] (whose values are string lists)

[[Int]] (whose values are integer-list lists)

Exemplos de construcao de listas:

[][13][2, 3, 5, 7]



Strings

Sao sequencias de caracteres.

Operacoes tıpicas:

lengthequality comparisonlexicographic comparison (A string s precedes a string t inlexicographic order if s is a prefix of t, or if c and d are respectively thefirst character of s and t in which s and t differ, then c precedes d incharacter order.)character selectionsubstring selectionconcatenation



Como classificar strings?

Tipo built-in. (Ex.: Linguagem funcional ML)

Vetor de caracteres (Quais sao as consequencias desta escolha?)

Ponteiro para vetor de caracteres. (Ex.: C e C++)

Lista de caracteres, quando o tipo lista e pre-definido. (Ex. Haskell eProlog)

Objetos (Ex.: Java)



Tipos recursivos em geral

R = . . .+ . . .R . . .R . . .

R tem a menor solucao possıvel.

R e construıdo por aproximacoes sucessivas.




A declaracao de tipo

data IntTree = Leaf Int | Branch IntTree IntTree

corresponde a seguinte equacao:

Int-Tree = Leaf Integer + Branch(Int-Tree × Int-Tree)

Primeira aproximacao: Leaf Integer , o conjunto de arvores binariasde profundidade 0.

Segunda aproximacao:Leaf Integer + Branch(Leaf Integer × Leaf Integer), o conjunto dearvores binarias de profundidade 0 ou 1.




Substituindo na equacao recursiva:

Leaf Integer+Branch(Leaf Integer × Leaf Integer)+Branch(Leaf Integer × Branch(Leaf Integer × Leaf Integer))+Branch(Branch(Leaf Integer × Leaf Integer)× Leaf Integer)+Branch(Branch(Leaf Integer × Leaf Integer)×Branch(Leaf Integer × Leaf Integer))

o conjunto de arvores binarias de profundidade 0 - 2. Aproximacoessucessivas induzem o conjunto de das arvores binarias finitas.


Valores e tipos Sistemas de tipos

Sistemas de tipos

Um sistema de tipos de uma linguagem define que tipos primitivos ecompostos sao suportados pela linguagem.

Uma vez definido o sistema de tipos, um programa escrito numalinguagem e dito seguro do ponto de vista dos tipos (type safe) se asoperacoes realizadas pelo programa estiverem bem-formadas do pontode vista dos tipos, isto e, se os valores que manipula puderem de fatoser manipulados pela operacao em questao. Ex.: multiplicar string porum booleano, indexar uma variavel que nao e um vetor ou a disjuncaode expressoes que nao sao booleanas produzem erros de tipagem.

Verificacao de tipos e o processo de verificacao das operacoes ossobre os tipos dos valores sobre os quais a operacao e aplicada.



Sistemas de tipos

Sistema de tipos estatico: variaveis e expressoes tem tipos fixos(declarados ou inferidos). O processo de verificacao de tipos aconteceem tempo de compilacao. (A maioria das linguagens possui este tipode sistema.)

Sistemas de tipos dinamico: variaveis e expressoes tem tipos variaveis.O processo de verificacao de tipos acontece em tempo de execucao.(Ex.: Smalltalk, Python e Lua)

Por que a funcao em C++ abaixo esta bem tipada?

bool even (int n) {return (n % 2 == 0);

}E a funcao abaixo em Python?

def even (n) :return (n % 2 == 0)

even("xyz") ?



Sistema de tipos estatico × dinamico

Existe muita pesquisa neste tema. Cada um tem seus pros e contras.

Um sistema de tipos estatico e mais seguro do que o dinamico umavez que verificacoes sao feitas em tempo de compilacao.

Onerando o programador, pode-se ter a flexibilidade do sistema detipos dinamico com a seguranca do estatico se verificacoes foremfeitas em tempo de execucao antes da avaliacao de uma expressao.Em Lua, por exemplo, pode-se fazer type checking em tempo deexecucao atraves de reflexao computacional: descobre-se o tipo deum objeto em tempo de execucao e condiciona-se a avaliacao de umaexpressao ao resultado do teste de tipagem.

A questao e que fica a cargo do programador e nada se pode falarsobre seguranca de tipos em geral neste tipo de linguagem.



Equivalencia de tipos

Dois tipos sao equivalentes (T1 ≡ T2) quando um pode ser utilizadoem substituicao ao outro, isto e, valores de T2 podem ser utilizadoscomo operandos em operacoes que esperam valores de T1.

Equivalencia estrutural permite que valores de um tipo sejamutilizados em substituicao a outro desde que seus tipos tenham amesma estrutura.



Equivalencia de tipos

Numa linguagem com sistema de tipos estatico, a equivalenciaestrutural entre produtos cartesianos, unioes disjuntas e mapas podeser definida pelas seguintes regras:

If T1 and T2 are both primitive, thenT1 =T2 if and only if T1 and T2are identical.For example: Integer = Integer but Integer /= Float (The symbol“/=” means “is not equivalent to”.)If T1 = A1 × B1 and T2 = A2 × B2, thenT1 = T2 if and only if A1= A2 and B1 = B2.For example: Integer × Float /= Float × IntegerIf T= A1→ B1 and T2 = A2 → B2, then T1 = T2 if and only if A1=A2 and B1 = B2.For example: Integer → Float /= Integer → BooleanIf T1 = A1 + B1 and T2 = A2 + B2, then T1 = T2 if and only ifeither A1 = A2 and B1 = B2, or A1 = B2 and B1 = A2.For example: Integer + Float /= Integer + BooleanOtherwise, T1 /= T2.

Em outras palavras, a uniao disjunta e comutativa, as outras operacoesnao.



Princıpio da completude

Nenhuma operacao deve restringir de forma arbitraria os tiposdos seus operandos.

Este princıpio e uma orientacao para um designer de uma linguagemde programacao para que sua linguagem nao tenha suaexpressabilidade restrita de maneira arbitraria.

Ex.: Pascal restringe o tipo de retorno de suas funcoes a valoresprimitivos e ponteiros somente. Nao existe justificativa para estadecisao. E comum que funcoes em linguagens imperativas retornemqualquer tipo de dados. Diferentemente do suporte a funcoes comoelementos de primeira-classe permitindo que sejam passadas porparametro. (O que e comum, no entanto, em linguagens funcionais.)


Valores e tipos Expressoes

Expressoes

Expressoes sao construcoes de uma linguagem de programacao queproduzem um valor ao serem avaliadas.

Pense numa linguagem de programacao que voce conhece. Quais saoas construcoes desta linguagem que tem esta caracterıstica?



Literais

Um literal denota um valor de algum tipo: 1, 2.5, ’a’, ‘‘Ola’’.



Construtores

Um construtor produz um valor composto a partir de outros valores.

Exemplos:

Vetores em C:

int size[] ={31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};. . .if (is leap(this year)) size[feb] = 29;

Listas em Haskell:

[31, if (isLeap(thisYear)) then 29 else 28,31, 30, 31, 30, 31, 31, 30, 31, 30, 31];



Construtores

Estruturas em Ada:

Date today, last day;today := (m => . . ., d => . . .);last day := (m => today.m, d => size(today.m));

A inicializacao de estruturas em Ada e mais segura pois todos oscomponentes devem ser inicializados simultaneamente,diferentemente de C, por exemplo.

today.m = . . .; today.d = . . .;last day.m = today.m; last day.d = size(today.m);



Aplicacao de funcao

Uma aplicacao (chamada) de funcao e o resultado da avaliacao deuma expressao F(E) onde F denota uma funcao e E os valores sobreos quais a funcao sera aplicada.

Nao necessariamente F e um identificador (nome) de funcao. Emalgumas linguagens, nas quais funcoes sao elementos de 1a. classe, Fpode ser uma expressao que produz uma funcao, como em Haskell:

(if . . . then sin else cos)(x)

A aplicacao F(E1,. . ., En) pode denotar tanto a aplicacao a variosvalores ou a um unico: a n-upla (E1,. . ., En).

Linguagens que interpretam a avaliacao de uma operacao comoaplicacao de uma funcao tem uma semantica mais simples pelotratamento homogeneo aos dois conceitos. (Notacao pre-fixada.)

a * b + c / d ≡ +(*(a, b), /(c, d))



Condicionais

Uma expressao condicional permite uma escolha a partir de um valor.

Expressao case em Haskell

case thisMonth ofFeb -> if isLeap(thisYear) then 29 else 28Apr -> 30Jun -> 30Sep -> 30Nov -> 30-> 31

O padrao fica associado a qualquer valor diferente dos casosanteriores.



Expressoes iterativas

A avaliacao de uma expressao iterativa produz um valor comoresultado do processamento de uma sequencia de valores, como umalista.

Construcao de listas (list comprehensions) em Haskell:

[if isLowercase c then toUppercase c else c | c <- cs]

A expressao c <- cs e chamada geradora.



Avaliacao de identificadores

A avaliacao de um identificador produz o valor associado aoidentificador no ambiente de identificadores, resultante da suadeclaracao.

O ambiente associa identificadores a valores. A memoria associavariaveis a valores.

pi: constant Float := 3.1416; r: Float;. . .2.0 * pi * r


Semantica operacional Fundamentos

Semantica formal

A semantica formal de um programa e modelo das computacoes querealiza.

Em geral, a especificacao da semantica formal de uma linguagem deprogramacao e dirigida pela sintaxe da linguagem.

Para cada construcao sintatica associa-se um objeto formal que odefine.

Semantica estatica especifica a boa-formacao de um programa comrelacao aos seus tipos.

Semantica dinamica especifica o comportamento de programas numalinguagem de programacao.

Equivalencia semantica especifica quando duas computacoes saoequivalentes formalizando, por exemplo, quando um refinamento(implementacao de uma linguagem, por exemplo) e correta.



Semantica operacional

O modelo de um programa e um sistema de transicao.Essencialmente, um sistema de transicao e dado por um conjunto Sde estados e uma relacao de transicao entre os estados →⊆ S × S .

Uma computacao num programa e uma sequencia de transicoes.

Modelos sao especificados por regras.



Sintaxe de linguagens

E especificada por regras, tipicamente em Backus-Naur Form (BNF).

Sintaxe concreta: especifica a sintaxe para uma analise sintatica(parsing) nao-ambigua de um programa.

Sintaxe abstrata: especifica a estrutura sintatica relevante para oprocessamento de um programa numa dada linguagem.

Veremos a semantica operacional (modular) da linguagem StandardML (SML), uma linguagem funcional.



Sintaxe de linguagens

Sintaxe concreta para condicional:Exp ::= if Exp then Exp else Exp | . . . | Exp1

Exp1 ::= Exp2 = Exp2 | . . . | Exp2Exp2 ::= Num | Ide | . . .Num ::= [0-9]+

Ide ::= [A-Za-z][A-Za-z0-9]∗

Sintaxe abstrata para codicional:Exp ::= if Exp then Exp else Exp | . . . |

Exp = Exp | . . . | Exp | Num | Ide | . . .Num ::= [0-9]+

Ide ::= [A-Za-z][A-Za-z0-9]∗

Que ambiguidades a gramatica abstrata possui?

Que informacao “desnecessaria” a gramatica concreta especifica? E“desnecessaria” sob que perspectiva?



Tipos de estados

Estado inicial: e (parte da) a arvore sintatica abstrata de umprograma. Ex.:

let ([(x,1), (y,2)], if(true, x, y))

Estado final: e um valor, como por ex. 1 ∈ N, que e diferente de1 ∈ Ide.

Estados intermediarios: arvores com valores (value-added trees), istoe, arvores sintaticas com, possivelmente, sub-arvores substituıdas porvalores. Ex.: if(true, 1, 2).



Regras

Caso geral:

q1x1→ q′1 . . . qn

xn→ q′nq

x→ q′if ti = t ′i

onde qi ∈ S , xj ∈ L e tk e um termo arbitrario, e i , j , k ∈ N.

O conjunto L e chamado de conjunto dos rotulos das transicoes, com arelacao →⊆ S × L× S . Valores como o ambiente e a memoria de umprograma sao elementos de L.


Semantica operacional Exemplo

Sequencias de bits

gramatica

{Bit ::= 0 | 1

BNum ::= Bit | BNum Bit

regras

0→ 0 1→ 1

BN → n B → n′

BN B → 2n + n′

B → nB : BNum→ n



Representacao grafica da arvore sintatica de 0 1 1

BNum

yysssssssss

��BNum

yysssssssss

��

Bit

��BNum

��

Bit

��

1

Bit

��

1

0



Representacao textual da arvore sintatica de 0 1 1 comouma lista

Na linguagem Maude:

fmod BIT-SIG .sorts Bit BNum .op bit : Nat -> Bit .op bnum : Bit -> BNum .op bnum : BNum Bit -> BNum .

endfm

red bnum(bnum(bnum(bit(0)), bit(1)), bit(1)) .



Aplicacao das regras a sequencia 0 1 1

bnum(bit(0))→ 0 bit(1)→ 1

bnum(bnum(bit(0)), bit(1))→ 2 ∗ 0 + 1 = 1 bit(1)→ 1

bnum(bnum(bnum(bit(0)), bit(1)), bit(1))→ 2 ∗ 1 + 1 = 3



Regras como equacoesNa linguagem Maude:

fmod BIT-SEM is inc BIT-SIG .var N : Nat . var B : Bit . var BN : BNum .op [[ ]] : Bit -> Nat .op [[ ]] : BNum -> Nat .eq [[ bit(N) ]] = N .eq [[ bnum(B) ]] = [[ B ]] .eq [[ bnum(BN, B) ]] = 2 * [[ BN ]] + [[ B ]] .

endfmred [[ bnum(bnum(bnum(bit(0)), bit(1)), bit(1)) ]] .==========================================reduce in BIT-SEM : [[bnum(bnum(bnum(bit(0)), bit(1)), bit(1))]] .rewrites: 10 in 0ms cpu (0ms real) (5000000 rewrites/second)result NzNat: 3

O operador [[ ]] denota “o significado de”.



Exercıcio

Implemente a semantica operacional de sequencias de bits em Haskell.


Semantica formal de expressoes

Literais

Gramatica:

Exp ::= LitLit ::= INum | RNum | Word | Char | String

INum ::= Digits | ˜ DigitsDigits ::= Digit | Digits DigitDigit ::= 0 | . . . | 9. . .



Literais

Regras:

DS → zDS : INum→ z

DS → z˜DS → −z

IN → zIN : Exp → z

D → zD : Digits → z

DS → z D → z ′

DS D → 10z + z ′

0→ 0 1→ 1 . . . 9→ 9

onde D : Digit, DS : Digits, z ∈ Z . A notacao utilizada em D : Digit, porexemplo, denota que a metavariavel D fica associada a arvores sintaticascom raiz em Digit.



Identificadores

Exp ::= Ide

I : Expu→ v if u.bindings(I ) = v

onde u.bindings ∈ Binding = (Ide →f Val), v ∈ Val e Z ⊆ Val e oconjunto de valores que dao significado a dıgitos.

O rotulo da transicao, representado nesta regra pela (meta)variavel u, eorganizado como um record contendo tantos componentes quantoestruturas semanticas necessitarmos, como o ambiente (este caso) ou amemoria.



Sequencia de expressoes

Exp ::= ( ExpSeq )ExpSeq ::= Exp | ExpSeq ; ExpSeq

ESx→ ES ′

( ES )x→ ( ES ′ ) ( v ) → v

Ex→ E ′

E : ExpSeqx→ E ′

ES1x→ ES ′1

ES1 ; ES2x→ ES ′1 ; ES2

v ; ES → ES

onde ES : ExpSeq e v ∈ Val .



Expressoes condicionais

Exp ::= if Exp then Exp else Exp

E1x→ E ′1

if E1 then E2 else E3x→ if E ′1 then E2 else E3

if constr(true) then E2 else E3 → E2

if constr(false) then E2 else E3 → E3

Seja TIde o conjunto de arvores sintaticas cuja raiz e Ide. O conjuntoconstr(TIde) ⊆ Val e o conjunto de estados finais (diferentemente de TIde ,que sao iniciais), denotando o resultado da avaliacao, dos elementos deTIde .Por exemplo, o ambiente possui a associacao true→ constr(true). (Vejaavaliacao de identificadores.)



Exercıcio

Construa a arvore e avalie a expressao

if true 1 else 2

utilizando as regras vistas ate agora.



Aplicacao de operacoes

Exp ::= Exp Exp

E1x→ E ′1

E1 E2x→ E ′1 E2

E2x→ E ′2

v1 E2x→ v1 E ′2

basic(=)tuple(v , v ′)→ constr(true) if v = v ′

basic(=)tuple(v , v ′)→ constr(false) if v 6= v ′

onde o conjunto basic(TIde) denota as operacoes basicas da linguagem.As regras para igualdade apenas ilustram a semantica de cada operacaobasica em SML.



Exercıcio

Especifique as regras para as operacoes aritmeticas basicas. Exemplifiqueo uso das suas regras em diferentes expressoes construindo a arvore emostrando como cada expressao e simplificada pela aplicacao das regras.



Tuplas

Exp ::= () | ( Exp , ExpList ) | # DigitsExpList ::= Exp | Exp , ExpList

() → tuple()

Ex→ E ′

( E , EL )x→ ( E ′ , EL )

ELx→ EL′

( v , EL )x→ ( v , EL′ )

( v , (v1, . . . , vn) )x→ tuple(v , v1, . . . , vn)

Ex→ E ′

E : ExpListx→ E ′

Ex→ E ′

E , ELx→ E ′ , EL

ELx→ EL′

v , ELx→ v , EL′

DS → z# DS → select(z)

if z > 0select(z) tuple(v1, . . . , vn)→ vz

if 1 ≤ z ≤ n

onde EL : ExpList e tuple(Val∗) ⊆ Val .C. Braga (UFF) Linguagens de programacao 71 / 149


Listas

Exp ::= [] | [ ExpList ]

[] → constr(nil)

[ E ] → constr(::) ( E , constr(nil) )

[ E , EL ] → constr(::) ( E , [ EL ] )



Exercıcio

Estude a especificacao para records. Pense numa expressao que possa serdescrita na gramatica para records, construa sua arvore e avalie-a segundoas regras nas paginas 46 e 47 de Fundamental Concepts and FormalSemantics of Programming Languages.


Amarracoes e escopo Associacoes e o ambiente

Identificadores, amarracoes e o ambiente

Identificadores sao utilizados para expressar diferentes entidades numprograma como constantes, variaveis ou procedimentos.

Uma amarracao (binding, em ingles) e uma associacao fixa entre umidentificador e o valor que denota.

O ambiente e um conjunto de amarracoes.



Diferentes pontos de um programa podem ter diferentesambientes

Em Ada:

procedure p isz: constant Integer := 0;c: Character;procedure q isc: constant Float := 3.0e6;b: Boolean;begin. . . ← 2end q;

begin. . . ← 1end p;



Diferentes pontos de um programa podem ter diferentesambientes

Em 1:

c → um caracter,p → um procedimento,q → outro procedimento,z → o inteiro 0

Em 2:

b → um boleano,c → o numero 3.0× 106 ,p → um procedimento,q → outro procedimento,z → o inteiro 0



Bindable values

Valores passıveis de amarracao (bindable values) sao aqueles aos quaisidentificadores podem ficar associados. Exemplos:Em C: tipos, variaveis e funcoes.Em Java: classes, metodos e pacotes.


Amarracoes e escopo Escopo

Escopo e bloco

O escopo de uma declaracao e a porcao de codigo na qual adeclaracao e valida.

Bloco e uma construcao linguıstica que declara um escopo. Ex. emJava: {. . .}, declaracao de metodo, declaracao de classe, declaracaode um pacote ou todo um programa.



Estruturas de blocoMonolıtica, achatada ou aninhada:



Declaracao e avaliacao

Uma declaracao amarra um identificador a um valor no ambiente. (Oque se chama binding occurrence em ingles.)

A avaliacao de um identificador (veja a secao de avaliacao deexpressoes) consulta o ambiente para descobrir o valor associado aum identificador. (O que se chama applied occurrence de umidentificador, em ingles.)



Visibilidade de uma declaracao

Diz-se que um identificador e visıvel dentro do bloco que o declara.

Que situacao potencialmente ambıgua a estrutura de blocosaninhados pode produzir sob a perspectiva da visibilidade deidentificadores?



Declaracoes escondidas



Escopo estatico × escopo dinamicoUma linguagem e dita de escopo estatico quando o ambiente dedeclaracao e utilizado para avaliar um identificador.Uma linguagem e de escopo dinamico quando o ambiente deexecucao e utilizado na avaliacao de um identificador.

const int s=2;int f(int x){return s*x; ← 1

}void p(int y){print(f(y)); ← 2

}void q (int z) {const int s = 3;print(f(z)); ← 3

}

Quais os resultados dasavaliacoes dasexpressoes nos pontos1, 2 e 3 em cada tipode escopo?

Que problemas podem surgir?



Escopo estatico × escopo dinamico

const char s = . . .;int f(int x){return s*x; ← 1

}void p(int y){print(f(y)); ← 2

}void q (int z) {const int s = 3;print(f(z)); ← 3

}

Com escopo estatico,return s*xproduziria um errode compilacao.

Com escopodinamico, 3 naoproduziria problemasmas 2 sim uma vezque o procedimentop utiliza a variavel sdeclaradaglobalmente e q alocal.

Em geral, linguagens com escopo dinamico tambem tem um sistema detipos dinamico.


Amarracoes e escopo Composicao e escopo

Declaracoes

Declaracoes produzem amarracoes quando avaliadas.

Uma declaracao pode produzir um efeito colateral como por exemplona declaracao de uma variavel.

Definicoes produzem exclusivamente amarracoes.



Declaracoes de tipos

Amarram identificadores a tipos existentes ou tipos novos.

Ex. em C:

typedef char* Alpha; ← Tipo existentestruct Book {Alpha title, int edn}; ← Tipo novo



Declaracoes de constantes, variaveis e procedimentosCada tipo de declaracao associa um identificador a um valor apropriado.

Forma geral de declaracao de constantes: const T I = E, onde T eum tipo, I um identificador e E uma expressao. Em linguagens maismodernas, E pode ser uma expressao qualquer. Em linguagens maisantigas, somente expressoes cujo valor se podia conhecer em tempode compilacao.Sinonimos: A linguagem ADA permite a criacao de sinonimos paravariaveis ja declaradas. Ex.:pop: Integer renames population(state);onde population e um vetor.Em geral, pode-se associar um identificador tanto a uma funcaoquanto a um procedimento.

bool even (int n) {return (n % 2 == 0);

}void double (int& n) {

n *= 2;}



Declaracoes colaterais

Permitem que declaracoes (independentes) sejam avaliadassimultaneamente.

O resultado e o ambiente resultante da uniao das declaracoes.

Comum em linguagens funcionais e logicas.

A declaracao em ML

val e = 2.7183 and pi = 3.1416

produz o ambiente { e → 2.7183, pi → 3.1416 }.A declaracao

val e = 2.7183 and pi = 3.1416 and twicepi = 2 * pi

e incorreta.



Declaracoes sequenciais

As subdeclaracoes devem ser avaliadas em sequencia.

A ordem das declaracoes e relevante: uma subdeclaracao pode utilizardeclaracoes que a antecedem porem nao posteriores.

O ambiente resultante e o resultado da juncao das amarracoesproduzidas por cada uma das subdeclaracoes.

Em Ada, a declaracao

count: Integer := 0;procedure bump isbegincount := count + 1;

end;

produz o ambiente {counter → um inteiro, bump → um procedimento}.



Declaracoes recursivas

Produz amarracoes que utilizam amarracoes produzidas pela propriadeclaracao.

Declaracoes mutuamente recursivas produzem amarracoesinterdependentes.

Tipos mutuamente recursivos em Ada:

type Int Node;type Int List is access Int Node;type Int Node is

recordelem: Integer;succ: Int List;

end record

As declaracoes de Int Node e Int List sao mutuamente recursivas. Otipo Int List declara um ponteiro a Int Node.



Declaracoes recursivasFuncoes mutuamente recursivas em C:

void parse expression ();void parse primary () {

if (acceptable(’(’)) {parse expression();accept(’)’);

} elseparse variable();

}void parse expression () {

parse primary();while (acceptable(’+’))parse primary();

}

As funcoes parse primary e parse expression sao mutuamenterecursivas. A declaracao void parse expression (); e chamada deforward declaration que associa o identificador parse expression a umafuncao desconhecida. E necessaria para a declaracao de parse primary.



Escopo de declaracoes


Amarracoes e escopo Blocos

Expressoes de blocos

Descreve uma(um) (conjunto de) declaracao(oes) cujo escopo eum(a) (sequencia de) expressoes(s).

Podem ocorrer tambem como comandos.

Em Haskell:

let s = (a + b + c)/2.0insqrt(s*(s-a)*(s-b)*(s-c))

Em C:

float area (float x, y, z) {float s = (x + y + z)/2.0;return sqrt(s*(s-x)*(s-y)*(s-z));

}. . . area(a, b, c) . . .


Amarracoes e escopo Blocos

Classes e modulos como blocos

A essencia de uma declaracao de bloco e definir um ambiente no qualcomandos ou expressoes serao avaliados.

Sob esta perspectiva, pode-se entender classes (em Java, por ex.) oumodulos (em Ada, por ex.) como declaracoes de blocos.


Amarracoes e escopo Semantica operacional de declaracoes

Amarracoes

Exp ::= IdeDec ::= val ValBind

ValBind ::= Ide = Exp | ValBind and ValBind

VBx→ VB ′

val VBx→ val VB ′ val b → b

Ex→ E ′

I = Ex→ I = E ′ I = v → (I 7→ v)

VB1x→ VB ′1

VB1 and VB2x→ VB ′1 and VB2

VB2x→ VB ′2

b1 and VB2x→ b1 and VB ′2

b1 and b2 → b1 ∪ b2

onde E : Exp, D : Dec , VB : ValBind , VDec = VValBind = Bindings =(Ide →f Val), b ∈ Bindings.



Escopo

Exp ::= let Dec in Exp endDec ::= local Dec in Dec end

Dx→ D ′

let D in E endx→ let D ′ in E end

Ex ′→ E ′

let b in Ex→ let b in E ′ if x ′ = x [bindings = b′], b′ = b/x .bindings

let b in v → v

onde D : Dec e (b2/b1)(I ) = b2(I ) quando I ∈ dom(b2), caso contrario(b2/b1)(I ) = b1(I ), quando definido.

Exercıcio: especifique as regras para a declaracao local .



Para o exemplo a seguir, usaremos as regras:

Dx−→ D ′

let D in E endx−→ let D ′ in E end [1] let b in v → v [3]

Ex ′−→ E ′

let b in E endx−→ let b in E ′ end if x’ = x[bindings = b’], b’ = b/x.bindings [2]

VBx−→ VB ′

val VBx−→ val VB ′ [4]

Ex−→ E ′

I = Ex−→ I = E ′ [5] val b → b [6]

I = v → (I 7→ v) [7]

INx−→ z

IN : Expx−→ z [8] 1→ 1 , 1 ∈ TExp , 1 ∈ N [9]

I : Expu−→ v if u.bindings(I ) = v [10]

DS → zDS : INum→ z [11]

D → zD : Digits → z [12]



Exemplo: let val x = 1 in x end

1[Bindings = ∅]−−−−−−−−−→ 1

[8, 11, 12, 9]

x = 1[Bindings = ∅]−−−−−−−−−→ x = 1

[5]

val x = 1[Bindings = ∅]−−−−−−−−−→ val x = 1

[4]

let val x = 1 in x end[Bindings = ∅]−−−−−−−−−→ let val x = 1 in x end

[1]

x = 1[Bindings = ∅]−−−−−−−−−→ x 7→ 1

[7]

val x = 1[Bindings = ∅]−−−−−−−−−→ val x 7→ 1

[4]

let val x = 1 in x end[Bindings = ∅]−−−−−−−−−→ let val x 7→ 1 in x end

[1]




1[Bindings = ∅]−−−−−−−−−→ 1

[8, 11, 12, 9]

x = 1[Bindings = ∅]−−−−−−−−−→ x = 1

[5]


[4]


[1]

x = 1[Bindings = ∅]−−−−−−−−−→ x 7→ 1

[7]


[4]


[1]




1[Bindings = ∅]−−−−−−−−−→ 1

[8, 11, 12, 9]

x = 1[Bindings = ∅]−−−−−−−−−→ x = 1

[5]


[4]


[1]

x = 1[Bindings = ∅]−−−−−−−−−→ x 7→ 1

[7]


[4]


[1]




val x 7→ 1[Bindings = ∅]−−−−−−−−−→ x 7→ 1

[6]

let val x 7→ 1 in x end[Bindings = ∅]−−−−−−−−−→ let x 7→ 1 in x end

[1]

x[Bindings = x 7→1]−−−−−−−−−−−→ 1

[10]

let x 7→ 1 in x end[Bindings = ∅]−−−−−−−−−→ let x 7→ 1 in 1 end

[2]

let x 7→ 1 in 1 end[Bindings = ∅]−−−−−−−−−→ 1

[3]




val x 7→ 1[Bindings = ∅]−−−−−−−−−→ x 7→ 1

[6]


[1]

x[Bindings = x 7→1]−−−−−−−−−−−→ 1

[10]


[2]


[3]




val x 7→ 1[Bindings = ∅]−−−−−−−−−→ x 7→ 1

[6]


[1]

x[Bindings = x 7→1]−−−−−−−−−−−→ 1

[10]


[2]


[3]



Declaracoes sequenciais

Exercıcio: estude-as e entenda-as.



Pattern matching

ValBind ::= Pat = ExpPat ::= Lit | | Ide | Ide Pat | Ide as Pat | () | ( Pat , PatList ) | ( Pat ) |

[] | [ PatList ] | {} | { PatRow }PatList ::= Pat | Pat , PatList

PatRow ::= Lab = Pat | . . . | Lab = Pat , PatRowExp ::= case Exp of Match

Match ::= Pat => Exp | Match | Match

Exercıcio: construa arvores sintaticas bem formadas em relacao agramatica acima.Note que P = E e uma generalizacao de I = E.



Pattern matching

Ex→ E ′

P = Ex→ P = E ′

Pu′→ b

P = vu→ b if u′ = u[val = v ]

Lu→ v

L : Patu→ ∅ if v = u.val

Lu→ v

L : Patu→ failure if v 6= u.valu→ ∅

I : Patu→ (I 7→ v) if I ∈ dom(u.bindings), v = u.val

I : Patu→ (I 7→ v) if @ I ′. (def u.bindings(I ′) ∧ constr(I ′) = I ), v = u.val

I : Patu→ ∅ if u.bindings(I ) = constr(I ) = u.val

I : Patu→ failure if u.bindings(I ) = constr(I ) 6= u.val

onde val e um novo componente na transicao, assim como bindings,VPat = Bindings ∪ {failure}.




Agora, para este mesmo exemplo, substituiremos algumas regras...

Ex→ E ′

P = Ex→ P = E ′ [13]

Pu′→ b

P = vu→ b if u′ = u[val = v ] [14]

I : Patu→ (I 7→ v) if @I ′.(def u.bindings(I ′) ∧ constr(I ′) = I ),

v = u.val[15]




Chamaremos de b a componente bindings e v a componente val

1[b = ∅, v = ∅]−−−−−−−−−→ 1

[8, 11, 12, 9]

x = 1[b = ∅, v = ∅]−−−−−−−−−→ x = 1

[13]

val x = 1[b = ∅, v = ∅]−−−−−−−−−→ val x = 1

[4]

let val x = 1 in x end[b = ∅, v = ∅]−−−−−−−−−→ let val x = 1 in x end

[1]

x[b = ∅, v = 1]−−−−−−−−−→ x 7→ 1

[15]

x = 1[b = ∅, v = ∅]−−−−−−−−−→ x 7→ 1

[14]

val x = 1[b = ∅, v = ∅]−−−−−−−−−→ val x 7→ 1

[4]

let val x = 1 in x end[b = ∅, v = ∅]−−−−−−−−−→ let val x 7→ 1 in x end

[1]





1[b = ∅, v = ∅]−−−−−−−−−→ 1

[8, 11, 12, 9]

x = 1[b = ∅, v = ∅]−−−−−−−−−→ x = 1

[13]

val x = 1[b = ∅, v = ∅]−−−−−−−−−→ val x = 1

[4]


[1]

x[b = ∅, v = 1]−−−−−−−−−→ x 7→ 1

[15]

x = 1[b = ∅, v = ∅]−−−−−−−−−→ x 7→ 1

[14]

val x = 1[b = ∅, v = ∅]−−−−−−−−−→ val x 7→ 1

[4]


[1]





1[b = ∅, v = ∅]−−−−−−−−−→ 1

[8, 11, 12, 9]

x = 1[b = ∅, v = ∅]−−−−−−−−−→ x = 1

[13]

val x = 1[b = ∅, v = ∅]−−−−−−−−−→ val x = 1

[4]


[1]

x[b = ∅, v = 1]−−−−−−−−−→ x 7→ 1

[15]

x = 1[b = ∅, v = ∅]−−−−−−−−−→ x 7→ 1

[14]

val x = 1[b = ∅, v = ∅]−−−−−−−−−→ val x 7→ 1

[4]


[1]





val x 7→ 1[b = ∅, v = ∅]−−−−−−−−−→ x 7→ 1

[6]

let val x 7→ 1 in x end[b = ∅, v = ∅]−−−−−−−−−→ let x 7→ 1 in x end

[7]

x[b = {x 7→1}, v = ∅]−−−−−−−−−−−−−→ 1

[10]

let x 7→ 1 in x end[b = ∅, v = ∅]−−−−−−−−−→ let x 7→ 1 in 1 end

[2]

let x 7→ 1 in 1 end[b = ∅, v = ∅]−−−−−−−−−→ 1

[3]





val x 7→ 1[b = ∅, v = ∅]−−−−−−−−−→ x 7→ 1

[6]


[7]

x[b = {x 7→1}, v = ∅]−−−−−−−−−−−−−→ 1

[10]


[2]

let x 7→ 1 in 1 end[b = ∅, v = ∅]−−−−−−−−−→ 1

[3]





val x 7→ 1[b = ∅, v = ∅]−−−−−−−−−→ x 7→ 1

[6]


[7]

x[b = {x 7→1}, v = ∅]−−−−−−−−−−−−−→ 1

[10]


[2]

let x 7→ 1 in 1 end[b = ∅, v = ∅]−−−−−−−−−→ 1

[3]



Pattern matching

Exercıcio: regras para padroes estruturados.



Pattern matching

Ex→ E ′

case E of Mx→ case E ′ of M

Mu′→ (b,E )

case v of Mu→ let b in E if u′ = u[val = v ]

P → bP => E → (b,E )

P → failureP => E → failure

M1 → (b,E )

M1 | M2 → (b,E )

M1 → failure M2 → m

M1 | M2 → m

onde VMatch = (Bindings)× TExp ∪ {failure}, m : VMatch.


Variaveis e a memoria

Linguagens de programacao imperativas

Variaveis, comandos e a memoria sao os principais elementos doparadigma de programacao imperativo.

Expressoes, declaracoes e o ambiente sao os principais elementos doparadigma de programacao funcional.

Essencialmente, programacao funcional produz valores, programacaoimperativa produz efeitos colaterais, isto e, muda a memoria.Computacao no paradigma funcional se da pela composicao defuncoes ao passo que computacao no paradigma imperativo se da pelasequenciamento de comandos que alteram a memoria a cada passo.

Nesta secao discutimos os elementos do paradigma imperativo.


Variaveis e a memoria Variaveis e a memoria

Variaveis

Variaveis representam dados cujo estado se altera com o passar dotempo.

Diferentemente do uso de identificadores (constantes) em declaracoescujo valor associado a eles no ambiente nao se modifica, como oproprio nome sugere.

Se para declaracoes utilizamos o ambiente de identificadores paraguardar as amarracoes entre constantes e valores, a memoria eutilizada para armazenar a associacao entre variaveis e valores.



Memoria

A memoria e organizada em celulas indexadas. Seu ındice, que eunico, e chamado endereco da memoria.

O estado de uma celulas de memoria pode ser alocada ou desalocadae seu conteudo pode ser uma valor armazenavel ou indefinido.



Valores armazenaveis

Diferentes linguagens permitem diferentes tipos de valores que podem serassociados a uma variavel numa unica celula na memoria:

C++: valores primitivos e ponteiros.

Java: valores primitivos e ponteiros para objetos.

Em geral valores compostos nao sao armazenaveis por uma unica celulanao e suficiente para armazena-los.



Variaveis simples

Qual a configuracao da memoria em cada um dos passos abaixo?

12 int n ;3 n = 0 ;4 n = n + 1 ;5

1 → memoria vazia2 int n ; → n 7→ undefined

3 n = 0 ; → n 7→ 0

4 n = n + 1 ; → n 7→ 1

5 → memoria vazia

Pode parecer trivial mas o que ocorreria se o programa nao tivesse a linha3?



Variaveis simples


12 int n ;3 n = 0 ;4 n = n + 1 ;5


3 n = 0 ; → n 7→ 0

4 n = n + 1 ; → n 7→ 1

5 → memoria vazia




Variaveis simples


12 int n ;3 n = 0 ;4 n = n + 1 ;5


3 n = 0 ; → n 7→ 0

4 n = n + 1 ; → n 7→ 1

5 → memoria vazia




Variaveis compostas

Variaveis compostas sao aquelas cujo tipo e composto.

Necessitam de varias celulas de memoria adjacentes para armazenarseus valores.



Variaveis compostas

struct Date {int y, m, d ;

} ;Date today ;Date dates[4] ;today.m = 2 ; today.d = 23 ; today.y = 2004 ;dates[0].y = 2004 ; dates[0].m = 5 ; dates[0].d = 5 ;dates[1] = today ;

60 Chapter 3 Variables and storage

55

dates[0]

223

dates[1]

??

dates[2]

dates(b)

2004

2004

?

??

dates[3]?

m 2d 23

today(a)y 2004

md

y

md

y

md

y

md

y

Figure 3.3 Storage for (a) a record variable, and (b) an array variable (Example 3.2).

Each Date value is a triple consisting of three int values. Correspondingly, a Datevariable is a triple consisting of three int variables. Figure 3.3(a) shows the structure ofthe variable today, and the effect of the following assignments:

today.m = 2; today.d = 23; today.y = 2004;

Now consider the array variable declared as follows:

Date dates[4];

A value of this array type is a mapping from the index range 0–3 to four Date values.Correspondingly, a variable of this array type, such as dates, is a mapping from the indexrange 0–3 to four Date variables. Figure 3.3(b) shows the structure of the variable dates,and the effect of the following assignments:

dates[0].y = 2004; dates[0].m = 5; dates[0].d = 5;dates[1] = today;

The last assignment copies the entire value of today. In other words, it updates the threestorage cells of dates[1] with the contents of the three storage cells of today.

3.3.1 Total vs selective updateA composite variable may be updated either in a single step or in several steps,one component at a time. Total update of a composite variable means updatingit with a new (composite) value in a single step. Selective update of a compositevariable means updating a single component.

EXAMPLE 3.3 C++ total and selective updatesConsider the following declarations:

struct Date {int y, m, d;

};Date today, tomorrow;

As atribuicoes a variavel today sao chamadas seletivas por atualizaremcomponentes individuais de um valor composto. A atribuicao dates[1] =today e chamada total (sobre o componente indexado por 1 em date)por atualiza-lo completamente.



Vetores estaticos, dinamicos e flexıveis I

Vetores podem ter seus ındices categorizados entre estatios, dinamicos eflexıveis:

Estatico: sabe-se em tempo de compilacao o intervalo relativo aoındice de um vetor. Ex.: C ou C++.

float v1[] = {2.0, 3.0, 5.0, 7.0} ; // v1 e indexado de 0 a 3.float v2[10] ; // v2 e indexado de 0 a 9.

Dinamico: o intervalo do ındice de um vetor e conhecido em tempode execucao. Ex.: Ada.

type Vector is array (Integer range <>) of Float ;v1 : Vector(1 .. 4) := (2.0, 3.0, 5.0, 7.0) ;v2 : Vector(0 .. m) := (0 .. m => 0.0) ;

O intervalo do ındice de v2 depende do valor da variavel m.A atribuicao v1 := v2 so sera possıvel se os intervalos de v1 e v2tiverem o mesmo tamanho.



Vetores estaticos, dinamicos e flexıveis II

Uma caracterıstica adicional que vetores em Ada possuem emcomparacao a C/C++ e o de um programa ser capaz de identificar oslimites inferior e superior de um vetor atraves da notacao v’first ev’last onde v e um vetor.

Flexıveis: permitem a mudanca do intervalo do ındice de um vetor emtempo de execucao. Ex.: Java.

float v1[] = {2.0, 3.0, 5.0, 7.0} ;float v2[] = {0.0, 0.0, 0.0} ;v1 = v2 ;

Inicialmente o intervalo do ındice de v1 era 0-4. Apos a atribuicao,0-3.



Semantica de copia × semantica de referencia

O que acontece na atribuicao de uma variavel composta depende dasemantica da linguagem de programacao:

Semantica de copia: o valor de cada componente e copiado aocomponente apropriado na variavel do lado esquerdo da atribuicao.

Semantica de referencia: a variavel do lado esquerdo da atribuicaofica associada a um ponteiro ou referencia ao valor compostoassociado a variavel do lado direito da atribuicao.

As duas semanticas podem ser suportadas numa linguagem deprogramacao. Em C/C++ por exemplo a semantica da atribuicao e porcopia porem a semantica de referencia pode ser conseguida pelo usoexplıcito de ponteiros.



Semantica de copia × semantica de referencia em C++

struct Date {inty,m,d;

};Date dateA={2003,12,25};Date dateB;dateB = dateA;

Date* dateP = new Date;Date* dateQ = new Date;*dateP = dateA;dateQ = dateP;64 Chapter 3 Variables and storage

1225

dateA2003

??

dateB?

1225

dateA2003

1225

dateB2003

After ‘dateB = dateA’:

After ‘dateQ = dateP’:

1225

dateP 2003

dateQ??

?

1225

dateP 2003

dateQ

(a)

(b)

Initially:

Initially:

??

?

Figure 3.4 Assignment in C++(Example 3.7): (a) copysemantics; (b) simulatingreference semanticsusing pointers.

EXAMPLE 3.7 C++ copy semanticsThe following C++ code illustrates copy semantics:


};Date dateA = {2003, 12, 25};Date dateB;dateB = dateA;

Figure 3.4(a) shows the effect of this assignment: dateB now contains a complete copy ofdateA. Any subsequent update of dateA will have no effect on dateB, and vice versa.

This further C++ code achieves the effect of reference semantics:

Date* dateP = new Date;Date* dateQ = new Date;*dateP = dateA;dateQ = dateP;

The variables dateP and dateQ contain pointers to Date variables. Figure 3.4(b) showsthe effect of the assignment ‘‘dateQ = dateP’’: dateP and dateQ now point to thesame variable. Any subsequent selective update of *dateP will also selectively update*dateQ, and vice versa.

JAVA adopts copy semantics for primitive values, and reference semantics forobjects. However, programmers can achieve the effect of copy semantics even forobjects by using the clone method.

EXAMPLE 3.8 JAVA reference semanticsConsider the following JAVA class declaration:

class Date {int y, m, d;



Semantica de copia × semantica de referencia em Java I

Java implementa semantica de referencia. Semantica de copia pode serconseguida atraves do metodo Clone.

// Semantica de referenciaclass Date{

int y,m,d;public Date (int y, int m, int d) { . . . }

}Date dateR = new Date(2003, 12, 25);Date dateS = new Date(2000, 1, 1);dateS = dateR;

// Semantica de copiaDate dateT = new Date(2004, 1, 1);dateT = dateR.clone();



Semantica de copia × semantica de referencia em Java II

3.4 Copy semantics vs reference semantics 65

public Date (int y, int m, int d) { . . . }}

The following JAVA code illustrates reference semantics:

Date dateR = new Date(2003, 12, 25);Date dateS = new Date(2000, 1, 1);dateS = dateR;

Figure 3.5(a) shows the effect of the assignment ‘‘dateS = dateR’’: dateR and dateSnow point to the same variable. Any subsequent selective update of dateR will alsoselectively update dateS, and vice versa.

This further JAVA code achieves the effect of copy semantics:

Date dateT = new Date(2004, 1, 1);dateT = dateR.clone();

Figure 3.5(b) shows the effect of the assignment ‘‘dateT = dateR.clone()’’. Themethod call ‘‘dateR.clone()’’ returns a pointer to a newly allocated object whosecomponents are copies of dateR’s components. The assignment makes dateT point tothe newly allocated object.

The semantics of the equality test operation in any programming languageshould be consistent with the semantics of assignment. This enables the program-mer to assume that, immediately after an assignment of V1 to V2, V1 is equal toV2, regardless of whether copy or reference semantics is used. It follows that theequality test operation should behave as follows:

• Copy semantics. The equality test operation should test whether corre-sponding components of the two composite values are equal.

After ‘dateS = dateR’:(a) Initially:

1225

dateR 2003

11

dateS 2000

1225

dateR 2003

dateS11

2000

After ‘dateT = dateR.clone()’:Initially:

1225

dateR 2003

11

dateT 2004

1225

dateR 2003

dateT1225

2003

(b)

Figure 3.5 Assignment in JAVA (Example 3.8): (a) reference semantics; (b) effectof cloning. (Objects’ tag fields are omitted here.)



Igualdade, semantica de copia e semantica de referencia

O comportamento do operador de igualdade deve ser coerente com asemantica empregada na atribuicao:

Semantica de copia: o operador de igualdade compara componente acomponente.

Semantica de referencia: o operador de igualdade compara se as duasreferencias apontam para o mesmo endereco.



Referencias indefinidas

Referencias indefinidas (dangling pointers) ocorrem quando se tenta obtero valor de uma referencia fora do seu escopo.Exemplo - Destrutores em C++:


};Date* dateP = new Date;dateP->y = 2000; dateP->m = 1; dateP->d = 1;Date* dateQ = dateP;delete dateQ;cout << dateP->y; // dateP referencia uma celula desalocada!dateP->y = 2003; // O comportamento e imprevisıvel!



Referencias indefinidas

Exemplo - Referencias a variaveis locais em C++:

int* f () {int fv = 42;return &fv;

}int* p = f();*p = 0;

C e C++: e responsabilidade dos programadores evitar referenciasindefinidas.Java: nao existem desalocadores nem referencias explıcitas portanto naoocorrem referencias indefinidas.


Variaveis e a memoria Comandos

Comandos, expressoes e declaracoes

Comandos sao construcoes de uma linguagem de programacao queatualizam o valor de uma variavel.

Diferentemente de uma declaracao ou expressao, que produzem umvalor e fazem uso do ambiente, um comando altera a memoria.



Comandos, expressoes e declaracoes

Comandos sao construcoes de uma linguagem de programacao queatualizam o valor de uma variavel.

Diferentemente de uma declaracao ou expressao, que produzem umvalor e fazem uso do ambiente, um comando altera a memoria.



Comandos primitivos

skips: comando sem efeito. Em C, C++ e Java e representado por ;.

Atribuicao: Um atribuicao e um comando da forma V = E onde E euma expressao que avalia para um valor e V e uma variavel que avaliapara uma celula de memoria.Note que na atribuicao n = n + 1 o identificador n e avaliado deduas formas diferentes. A avaliacao de n produz um endereco dememoria cujo valor e atualizado com n o valor resultante doincremento do valor guardado neste mesmo endereco antes daatribuicao.

Procedimentos: para se comportarem como comandos, devem alteraro estado de alguns de seus parametros ou variaveis globais.



Comandos compostos

Sequencias de comandos.

Comandos colaterais: nao determinısticos, como nas declaracoescolaterais.

Comandos condicionais: sequenciais ou colaterais. Comandos case.



Repeticoes

Indefinidas (while) e definidas (for).

Equivalencias:

while (E) C = if (E) { C ; while (E) C }do C while (E) = C ; while (E) C

Seja V a variavel de controle de uma repeticao:

Qual o valor de V apos a terminacao do loop?Qual o valor de V apos um jump ou escape fora do loop?O que acontece se o comando na repeticao altera V?

A maioria das linguagens trata a variavel de controle como umavariavel qualquer.

Ada tem uma semantica mais segura ao interpretar a variavel decontrole como uma constante a cada iteracao do loop cujo escopo ea repeticao.



Expressao-comando

Uma expressao comando e aquele que simultaneamente retorna umvalor (atuando como expressao) mas tambem produz um efeitocolateral.

Um exemplo e o codigo em C abaixo:

while ((ch = getchar(f)) != NUL)putchar(ch);

O procedimento getchar e um exemplo de expressao-comando, umavez que retorna o caracter corrente alem de alterar o estado davariavel f, assim como a atribuicao que produz o valor resultante daavaliacao do operando do lado-direito.

Varias linguagens dao suporte a expressoes-comando como Pascal,C/C++ e Java.


Variaveis e a memoria Semantica operacional de comandos

Memoria

Variaveis: sao representadas por enderecos (locations em ingles)l ∈ Loc, onde Loc e um conjunto nao especificado, podendo ser osnumeros naturais por exemplo, com Loc ⊆ Val . (Entenda Loc comouma class abstrata ou interface.)

A memoria e um mapa finito Store = Loc →f Val .

As transicoes serao estendidas com um par de memorias, indexadaspor store e store’, representando a memoria no inıcio e ao final deuma transicao. O acesso a cada componente do par de memorias efeito de maneira usual: x.store acessa a memoria no inıcio datransicao e x.store’ a memoria ao final da transicao.



Operacoes sobre a memoria

Em Standard ML, sao as seguintes as operacoes sobre a memoria:

A expressao ref E associa um endereco de memoria nao utilizado aovalor produzido pela expressao E .

A expressao ! E avalia para o valor associada ao endereco dememoria produzido pela avaliacao de E .

O comando E1 := E2 atualiza o valor do endereco resultante daavaliacao de E1 com o valor produzido por E2.



Semantica aplicativa

Interpretar cada uma das operacoes sobre a memoria como umaaplicacao produz uma semantica simples e elegante.

Por exemplo, a semantica de ref E e a aplicacao do operador ref aexpressao E .

Que para a atribuicao precisamos da sua forma prefixada. Pode-sepensar num pre-processador que transforma a notacao infixada E1 :=E2 em :=(E1,E2).

Os valores ref, deref e assign sao os valores computados resultantesda avaliacao de ref, ! e :=.



Semantica das operacoes sobre a memoria

Exp ::= ref | ! | :=

ref vx→ l if x = u[store ′ = (l 7→ v)/s], s = u.store ′, l 6∈ dom(s)

deref lu→ v if v = u.store(l)

assign tuple(l , v)x→ tuple() if x = u[store ′ = (l 7→ v)/s],

s = u.store, l ∈ dom(s)

onde u representa a transicao adjacente a x da qual x obtem os outroscomponentes distintos a store’.



Exemplo: let val x = ref 1 in x := !x + 1 endPara este exemplo, serao adicionadas mais algumas regras:

Ex→ E ′

( E , EL )x→ ( E ′ , EL ) [16]

ELx→ EL′

( v , EL )x→ ( v , EL′ ) [17]

( v , (v1, . . . , vn) )x→ tuple(v , v1, . . . , vn) [18]

Ex→ E ′

E : ExpListx→ E ′ [19]

E1x→ E ′1

E1 E2x→ E ′1 E2 [20]

E2x→ E ′2

v1 E2x→ v1 E ′2 [21] basic(+) tuple(v , v ′)→ v + v ′ [22]

+ : Exp → basic(+) [23] ref → ref [24] ! → deref [25] := → assign [26]

ref vx→ l if x = u[store ′ = (l 7→ v)/s], s = u.store, l /∈ dom(s) [27]

deref lx→ v if v = u.store(l) [28]

assign tuple(l , v)x→ tuple() if x = u[store ′ = (l 7→ v)/s], s = u.store, l ∈ dom(s) [29]

OBS: As regras 16 a 19 devem ser recordadas no slide ’Tuplas’.C. Braga (UFF) Linguagens de programacao 134 / 149


Exemplo: let val x = ref 1 in x := !x + 1 endChamaremos de b a componente bindings, s a componente store e s’ a

componente store’.Consideraremos um pre-processador que passa operacoes da forma

infixada para a prefixada.

ref[b = ∅, s = ∅, s′ = ∅]−−−−−−−−−−−−−−−→ ref

[24]

ref 1[b = ∅, s = ∅, s′ = ∅]−−−−−−−−−−−−−−−→ ref 1

[20]

x = ref 1[b = ∅, s = ∅, s′ = ∅]−−−−−−−−−−−−−−−→ x = ref 1

[5]

val x = ref 1[b = ∅, s = ∅, s′ = ∅]−−−−−−−−−−−−−−−→ val x = ref 1

[4]

let val x = ref 1 in := (x , +(!x , 1)) end[b = ∅, s = ∅, s′ = ∅]−−−−−−−−−−−−−−−→ let val x = ref 1 in := (x , +(!x , 1)) end

[1]

1[b = ∅, s = ∅, s′ = ∅]−−−−−−−−−−−−−−−→ 1

[8, 11, 12, 9]

ref 1[b = ∅, s = ∅, s′ = ∅]−−−−−−−−−−−−−−−→ ref 1

[21]

x = ref 1[b = ∅, s = ∅, s′ = ∅]−−−−−−−−−−−−−−−→ x = ref 1

[5]


[4]


[1]






ref[b = ∅, s = ∅, s′ = ∅]−−−−−−−−−−−−−−−→ ref

[24]

ref 1[b = ∅, s = ∅, s′ = ∅]−−−−−−−−−−−−−−−→ ref 1

[20]

x = ref 1[b = ∅, s = ∅, s′ = ∅]−−−−−−−−−−−−−−−→ x = ref 1

[5]


[4]


[1]

1[b = ∅, s = ∅, s′ = ∅]−−−−−−−−−−−−−−−→ 1

[8, 11, 12, 9]

ref 1[b = ∅, s = ∅, s′ = ∅]−−−−−−−−−−−−−−−→ ref 1

[21]

x = ref 1[b = ∅, s = ∅, s′ = ∅]−−−−−−−−−−−−−−−→ x = ref 1

[5]


[4]


[1]






ref[b = ∅, s = ∅, s′ = ∅]−−−−−−−−−−−−−−−→ ref

[24]

ref 1[b = ∅, s = ∅, s′ = ∅]−−−−−−−−−−−−−−−→ ref 1

[20]

x = ref 1[b = ∅, s = ∅, s′ = ∅]−−−−−−−−−−−−−−−→ x = ref 1

[5]


[4]


[1]

1[b = ∅, s = ∅, s′ = ∅]−−−−−−−−−−−−−−−→ 1

[8, 11, 12, 9]

ref 1[b = ∅, s = ∅, s′ = ∅]−−−−−−−−−−−−−−−→ ref 1

[21]

x = ref 1[b = ∅, s = ∅, s′ = ∅]−−−−−−−−−−−−−−−→ x = ref 1

[5]


[4]


[1]



Exemplo: let val x = ref 1 in x := !x + 1 end

ref 1[b = ∅, s = ∅, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−→ lo

[27]

x = ref 1[b = ∅, s = ∅, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−→ x = lo

[5]

val x = ref 1[b = ∅, s = ∅, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−→ val x = lo

[4]

let val x = ref 1 in := (x, +(!x, 1)) end[b = ∅, s = ∅, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−→ let val x = lo in := (x, +(!x, 1)) end

[1]

x = lo[b = ∅, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−→ x 7→ lo

[7]

val x = lo[b = ∅, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−→ val x 7→ lo

[4]

let val x = lo in := (x, +(!x, 1)) end[b = ∅, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−→ let val x 7→ lo in := (x, +(!x, 1)) end

[1]

val x 7→ lo[b = ∅, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−→ x 7→ lo

[6]

let val x 7→ lo in := (x, +(!x, 1)) end[b = ∅, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−→ let x 7→ lo in := (x, +(!x, 1)) end

[1]




ref 1[b = ∅, s = ∅, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−→ lo

[27]

x = ref 1[b = ∅, s = ∅, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−→ x = lo

[5]


[4]


[1]

x = lo[b = ∅, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−→ x 7→ lo

[7]


[4]


[1]


[6]


[1]




ref 1[b = ∅, s = ∅, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−→ lo

[27]

x = ref 1[b = ∅, s = ∅, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−→ x = lo

[5]


[4]


[1]

x = lo[b = ∅, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−→ x 7→ lo

[7]


[4]


[1]


[6]


[1]




:=[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ assign

[26]

:= (x , +(!x , 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ assign(x , +(!x , 1))

[20]

let x 7→ lo in := (x , +(!x , 1)) end[b = ∅, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−→ let x 7→ lo in assign(x , +(!x , 1)) end

[2]

x[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ lo

[10]

(x , +(!x , 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ (lo , +(!x , 1))

[16]

assign(x , +(!x , 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ assign(lo , +(!x , 1))

[21]

let x 7→ lo in assign(x , +(!x , 1)) end[b = ∅, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−→ let x 7→ lo in assign(lo , +(!x , 1)) end

[2]

+[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ basic(+)

[23]

+(!x , 1)[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ basic(+)(!x , 1)

[20]


[19]

(lo , +(!x , 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ (lo , basic(+)(!x , 1))

[17]

assign(lo , +(!x , 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ assign(lo , basic(+)(!x , 1))

[21]

let x 7→ lo in assign(lo , +(!x , 1)) end[b = ∅, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−→ let x 7→ lo in assign(lo , basic(+)(!x , 1)) end

[2]





[26]


[20]


[2]

x[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ lo

[10]


[16]


[21]


[2]


[23]


[20]


[19]


[17]


[21]


[2]





[26]


[20]


[2]

x[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ lo

[10]


[16]


[21]


[2]


[23]


[20]


[19]


[17]


[21]


[2]




![b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ deref

[25]

!x[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ deref x

[20]

(!x , 1)[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ (deref x , 1)

[16]

basic(+)(!x , 1)[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ basic(+)(deref x , 1)

[21]


[19]

(lo , basic(+)(!x , 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ (lo , basic(+)(deref x , 1))

[17]

assign(lo , basic(+)(!x , 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ assign(lo , basic(+)(deref x , 1))

[21]

let x 7→ lo in assign(lo , basic(+)(!x , 1)) end[b = ∅, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−→ let x 7→ lo in assign(lo , basic(+)(deref x , 1)) end

[2]

x[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ lo

[10]

deref x[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ deref lo

[21]

(deref x , 1)[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ (deref lo , 1)

[16]

basic(+)(deref x , 1)[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ basic(+)(deref lo , 1)

[21]


[19]

(lo , basic(+)(deref x , 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ (lo , basic(+)(deref lo , 1))

[17]

assign(lo , basic(+)(deref x , 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ assign(lo , basic(+)(deref lo , 1))

[21]

let x 7→ lo in assign(lo , basic(+)(deref x , 1)) end[b = ∅, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−→ let x 7→ lo in assign(lo , basic(+)(deref lo , 1)) end

[2]




![b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ deref

[25]

!x[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ deref x

[20]

(!x , 1)[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ (deref x , 1)

[16]


[21]


[19]

(lo , basic(+)(!x , 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ (lo , basic(+)(deref x , 1))

[17]

assign(lo , basic(+)(!x , 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ assign(lo , basic(+)(deref x , 1))

[21]

let x 7→ lo in assign(lo , basic(+)(!x , 1)) end[b = ∅, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−→ let x 7→ lo in assign(lo , basic(+)(deref x , 1)) end

[2]

x[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ lo

[10]

deref x[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ deref lo

[21]

(deref x , 1)[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ (deref lo , 1)

[16]


[21]


[19]

(lo , basic(+)(deref x , 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ (lo , basic(+)(deref lo , 1))

[17]

assign(lo , basic(+)(deref x , 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−→ assign(lo , basic(+)(deref lo , 1))

[21]

let x 7→ lo in assign(lo , basic(+)(deref x , 1)) end[b = ∅, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−→ let x 7→ lo in assign(lo , basic(+)(deref lo , 1)) end

[2]




deref lo[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ 1

[28]

(deref lo , 1)[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ (1, 1)

[16]

basic(+)(deref lo , 1)[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ basic(+)(1, 1)

[21]


[19]

(lo , basic(+)(deref lo , 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ (lo , basic(+)(1, 1))

[17]

assign(lo , basic(+)(deref lo , 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ assign(lo , basic(+)(1, 1))

[21]

let x 7→ lo in assign(lo , basic(+)(deref lo , 1)) end[b = ∅, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−→ let x 7→ lo in assign(lo , basic(+)(1, 1)) end

[2]

1[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ 1

[8, 11, 12, 9]

1[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ 1

[19]

(1, 1)[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ (1, 1)

[17]

basic(+)(1, 1)[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ basic(+)(1, 1)

[21]


[19]

(lo , basic(+)(1, 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ (lo , basic(+)(1, 1))

[17]

assign(lo , basic(+)(1, 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ assign(lo , basic(+)(1, 1))

[21]

let x 7→ lo in assign(lo , basic(+)(1, 1)) end[b = ∅, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−→ let x 7→ lo in assign(lo , basic(+)(1, 1)) end

[2]




deref lo[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ 1

[28]

(deref lo , 1)[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ (1, 1)

[16]


[21]


[19]

(lo , basic(+)(deref lo , 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ (lo , basic(+)(1, 1))

[17]

assign(lo , basic(+)(deref lo , 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ assign(lo , basic(+)(1, 1))

[21]

let x 7→ lo in assign(lo , basic(+)(deref lo , 1)) end[b = ∅, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−→ let x 7→ lo in assign(lo , basic(+)(1, 1)) end

[2]

1[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ 1

[8, 11, 12, 9]

1[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ 1

[19]

(1, 1)[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ (1, 1)

[17]


[21]


[19]

(lo , basic(+)(1, 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ (lo , basic(+)(1, 1))

[17]

assign(lo , basic(+)(1, 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ assign(lo , basic(+)(1, 1))

[21]

let x 7→ lo in assign(lo , basic(+)(1, 1)) end[b = ∅, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−→ let x 7→ lo in assign(lo , basic(+)(1, 1)) end

[2]




(1, 1)[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ tuple(1, 1)

[18]

basic(+)(1, 1)[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ basic(+) tuple(1, 1)

[21]


[19]

(lo , basic(+)(1, 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ (lo , basic(+) tuple(1, 1))

[17]

assign(lo , basic(+)(1, 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ assign(lo , basic(+) tuple(1, 1))

[21]

let x 7→ lo in assign(lo , basic(+)(1, 1)) end[b = ∅, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−→ let x 7→ lo in assign(lo , basic(+) tuple(1, 1)) end

[2]

basic(+) tuple(1, 1)[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ 2

[22]


[19]

(lo , basic(+) tuple(1, 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ (lo , 2)

[17]

assign(lo , basic(+) tuple(1, 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ assign(lo , 2)

[21]

let x 7→ lo in assign(lo , basic(+) tuple(1, 1)) end[b = ∅, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−→ let x 7→ lo in assign(lo , 2) end

[2]




(1, 1)[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ tuple(1, 1)

[18]


[21]


[19]

(lo , basic(+)(1, 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ (lo , basic(+) tuple(1, 1))

[17]

assign(lo , basic(+)(1, 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ assign(lo , basic(+) tuple(1, 1))

[21]

let x 7→ lo in assign(lo , basic(+)(1, 1)) end[b = ∅, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−→ let x 7→ lo in assign(lo , basic(+) tuple(1, 1)) end

[2]


[22]


[19]

(lo , basic(+) tuple(1, 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ (lo , 2)

[17]

assign(lo , basic(+) tuple(1, 1))[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ assign(lo , 2)

[21]

let x 7→ lo in assign(lo , basic(+) tuple(1, 1)) end[b = ∅, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−→ let x 7→ lo in assign(lo , 2) end

[2]




(lo , 2)[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ tuple(lo , 2)

[18]

assign(lo , 2)[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ assign tuple(lo , 2)

[21]

let x 7→ lo in assign(lo , 2) end[b = ∅, s = {lo 7→1}, s′ = {lo 7→1}]−−−−−−−−−−−−−−−−−−−−−−−→ let x 7→ lo in assign tuple(lo , 2) end

[2]

assign tuple(lo , 2)[b = {x 7→lo}, s = {lo 7→1}, s′ = {lo 7→2}]−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ tuple()

[29]

let x 7→ lo in assign tuple(lo , 2) end[b = ∅, s = {lo 7→1}, s′ = {lo 7→2}]−−−−−−−−−−−−−−−−−−−−−−−→ let x 7→ lo in tuple() end

[2]

let x 7→ lo in tuple() end[b = ∅, s = {lo 7→2}, s′ = {lo 7→2}]−−−−−−−−−−−−−−−−−−−−−−−→ tuple()

[3]





[18]


[21]


[2]


[29]


[2]


[3]





[18]


[21]


[2]


[29]


[2]


[3]



Semantica de iteracoes

while E1 do E2 → if E1 then (E2 ; while E2 do E2) else ()


Abstracoes

Abstracoes de procedimentos

Uma abstracao de procedimento, que tem suas origens no chamadocalculo lambda, e por isso e tambem chamada de abstracao lambda, euma forma elegante de representar procedimentos como um par: (i)uma lista de identificadores representando parametros doprocedimento e (ii) o bloco do procedimento dado por uma expressaoou comando.

Desta forma, a declaracao de um procedimento e feita “comosempre”: associamos um identificador a um valor representando umaabstracao de procedimento. A avaliacao de uma abstracao produz ovalor do seu bloco. Ex.:

f(x) { val f = λ x. (x + 1)return x + 1 ; ≡

}


Abstracoes

Conceitos fundamentais

Escopo estatico ou escopo dinamico: As amarracoes entreidentificadores devem permanecer as mesmas entre ativacoes de umprocedimento ou podem se modificar?

Chamadas de procedimento recursivas: sao nada mais nada menos doque a aplicacao (do significado!) da abstracao associada a umidentificador representando um procedimento a um valor. Deve-setomar cuidado para preservar o tipo de escopo numa chamadarecursiva, isto e, se a amarracao e estatica e necessario preservar oambiente de amarracoes entre uma chamada recursiva e outra.


Abstracoes

Closures

Uma closure (uma traducao seria “fechamento”) e nada mais nada menosdo que encapsular uma abstracao no seu contexto de declaracao, isto e,criar um par representando a abstracao e o ambiente a ser utilizado para aavaliacao daquela abstracao.


Abstracoes Semantica operacional de abstracoes

Aplicacao de abstracoes

Exp ::= fn Ide => Exp

fn I => Eu→ closure(I => E , u.bindings)

(closure(I => E , b′)) v → let (I 7→ v)/b′ in E end

onde I : Ide, E : Exp, v : Val , b′ : Bindings,closure(TMatch,Bindings) ⊆ Closure ⊆ Val .

E com um numero indeterminado de parametros?



Closures recursivas

Dec ::= fun Ide(Ide) = Exp

fun I (I ′) = Eu→ unfold(I 7→ closure(I ′ => E , u.bindings))

(reclosure(I => E , b′, b))v → let (I 7→ v)/unfold(b)/b′ in E end

reclosure(TMatch,Bindings,Bindings) ⊆ Closureunfold : Bindings → Bindings recloseb : Bindings → Bindings

unfold(b) = recloseb(b)recloseb(I 7→ closure(M, b′)) = (I 7→ reclosure(M, b′, b))recloseb(I 7→ reclosure(M, b′, b′′)) = (I 7→ reclosure(M, b′, b))recloseb(I 7→ v) = (I 7→ v)if v 6∈ Closurerecloseb(b1 ∪ b1) = recloseb(b1) ∪ recloseb(b2)recloseb(∅) = ∅



Exemplo

let fun f(x) = if x=0 then 1 else 2*f(x 1)in f(n)end

CHAPTER 5. ABSTRACTIONS 68

The function identifier I in a recursive function declaration is bound to a reclo-sure, specified here using unfold :

fun I(I !)=Eu!"

unfold(I #" closure(I ! =>E , u.bindings))(5.11)

The use of unfold in the following rule ensures that when a closure bound to I isused in E , it is always a reclosure rather than an ordinary closure:

(reclosure(I =>E , b !, b)) vu!"

let (I #" v)/unfold(b)/b ! in E end(5.12)

A simple illustration of the use of the above definitions may be helpful. Consider

this expression E :

let fun f(x) = if x=0 then 1 else 2*f(x!1)in f(n)

end

and follow its (unique) computation:

E u!" let unfold(b1 ) in f(n) endwhere b1 = (f #" closure(x=>if..., b0 ))where b0 = u.bindings= let b2 in f(n) end

where b2 = unfold(b1 ) = (f #" reclosure(x=>if..., b0 , b1 ))u!"3 let b2 in v1 v2 end

where v1 = reclosure(x=>if..., b0 , b1 ), v2 = b0 (n)u!" let b2 in E ! end

where E ! = let (x #" n)/unfold(b1 )/b0 in if...

Thus a recursive call of f in ...involves exactly the same reclosure as the orig-

inal call, thanks to the unfolding of b1 caused by the semantics of applying a

reclosure. Without that unfolding, the first recursive call illustrated above would

have involved an ordinary closure, leading to the use of b0 (f) rather than b2 (f). Ex. 5.5

To specify the semantics of mutually-recursive function definitions, let us first

introduce a new nonterminal, FunBind , for use only in connection with functiondeclarations:

Dec ::= funFunBindFunBind ::= Ide(Ide)=Exp | FunBind andFunBind

The rule for a simple FunBind construct does not itself involve recursion:

I(I !)=Eu!" (I #" closure(I ! =>E , u.bindings)) (5.13)


Documents

Christiano Braga cbragacbraga/lp/lp.pdf · Conteudo I 1 Introdu˘c~ao Objetivo Motiva˘c~ao 2 Valores e tipos Tipos primitivos Tipos compostos Tipos recursivos Sistemas de tipos Express~oes