Upload
dher-fga
View
89
Download
3
Embed Size (px)
Citation preview
Linguagens de
Programação
Leonardo de Oliveira Nunes2012/1
Escola Politécnica - DEL - EEL670
Contato:
E-mail: [email protected]
Sala: I-146 (LPS II)
Página: https://www.del.ufrj.br/Members/leonardo.nunes/linguagens-de-programacao-2012-2
Visão Geral do CursoParte I - Fundamentos
Evolução das linguagens, paradigmas, interpretação x compilação, gramáticas e análise sintática
Parte II - Elementos de Linguagens de Programação
Escopo de variáveis, estruturas de controle, tipos de dados, orientação a objetos
Parte III - Scripts
Parte III - Programação Funcional
Laboratório: C++
Cronograma Outubro15: Introdução, evolução das linguagens, tipos de linguagens19: Compilação22: Sintaxe e Derivação26: Derivação29: Nomes e tempo de vida de objetos
Novembro02: Finados05: Escopo09: Sobrecarga e Polimorfismo12: Prova 1
16: Recesso19: Provável recesso23: Término Cap. 3 e Fluxo estruturado e não-estruturado26: Iteração, Recursão, e determinação30: Tipo de dados, sistemas de tipos e verificação de tipo
Dezembro03: Estruturas e uniões, Arrays, Strings07: Ponteiros e tipos recursivos10: Coletagem de lixo e listas
Cronograma 14: Subrotinas e abstrações de controle, revisão stack, sequência de uma chamada17: Passagem de parâmetro21: P224: Recesso28: Recesso
Janeiro04: Recesso07: Subrotinas genéricas e módulos11: Abstração de dados e orientação a objetos: programação OO14: Encapsulamento e hereditariedade18: Inicialização e finalização, união dinâmica de métodos, herança múltipla
21: OO25: OO28: P3
Fevereiro01: Scripts: Python04: Scripts: Python08: Scripts: Scheme11: Carnaval15: Scripts: Scheme18: Scripts: Scheme22: P425:
Bibliografia
1. Michael L. Scott, “Programming Language Pragmatics”, Morgan Kraufmann, 3a edição
2.Allen B. Tucker e Robert E. Noonan, “Linguagens de Programação”, McGraw Hill, 2a edição
Avaliação
4 Provas
Listas (opcionais)
Laboratório
Por quê?
Conceitos de linguagens de programação
Aprendizado de novas linguagens
Funcionamento das linguagens
Entender características obscuras das linguagens
Saber escolher entre diferentes formas de se expressar
Fazer bom uso de “debuggers”, “assemblers”, ...
Simular características de uma linguagem em outra
Fazer uso de novas linguagens
PARTE IFundamentos
Introdução
Linguagem:
Projeto x Implementação
O que será visto:
Histórico do projeto de linguagens
Introdução à implementação
Evolução das Linguagens1940-1950
Código de máquina
Códigos hexadecimais
Instruções diretas para CPU
Específico para arquitetura/CPU
Assembler
Mnemônicos no lugar de números
Macros: reutilização de código
55 89 E5 53 89 EC 04 83 E4 F0 E8 31 00 00 00 89 C3 E8 2A 0000 00 39 C3 74 10 8D B6 00 00 00 00 37 C3 7E 13 29 C3 39 C375 F6 89 1C 24 E8 6E 00 00 00 8B 5D FC C9 C3 29 D8 EB EB 90
Linguagem de Máquina: MDC para x86 [1]
pushl %ebp jle Dmovl %esp, %ebp subl %eax, %ebxpushl %ebx B: cmpl %eax, %ebxsubl $4, $esp jne Aandl $-16, %esp C: movl %ebx, (%esp)call getint call putintmovl %eax, %ebx movl -4(%ebp), %ebxcall getint leavecmpl %eax, %ebx retje C D: subl %ebx, %eax
A: cmpl %eax, %ebx jmp B
Assembler: MDC para x86 [1]
Próximo passo...
De linguagens dependentes da arquitetura...
... para linguagens independente da arquitetura
1957: Fortran (e outras ling. logo em seguida)
Tradução do código para assembler:
COMPILADOR
Evolução do compilador: equivalência de desempenho
Projeto de LinguagensHoje em dia: milhares de linguagens
Possíveis razões:Evolução: diferentes paradigmas
Propósito: linguagens específicas para um problema
Preferência pessoal
Poder de expressão
Facilidade de aprendizado
Facilidade de implementação
Padronização
Código aberto
Bons compiladores
Econômicos, patronagem
Evolução das LinguagensPonto de vista do implementador:
fácil de criar um compilador
Ponto de vista do programador:
fácil de descrever algoritmos
Knuth: “programar é a arte de informar outro ser humano o que o computador deve fazer”
Compromisso: claridade x eficiência
Classificação - Visão GeralFuncional Lisp, Scheme, ML, Haskell
DeclarativasDataflow Id, Val
DeclarativasLógica Prolog
Template XSLT
von Neumann C, Ada, Fortran
Imperativas Scripting Perl, Python, Ruby, PHP
OO Smalltalk, Java, C++
Obs.: Uma linguagem pode ser de mais de um tipo.
Declarativa x Imperativa
Declarativa
Foco: o que o computador deve fazer
Mais alto nível
Imperativa
Foco: como o computador deve fazer
Mais eficiente
Linguagens Funcionais
Definição recursiva de funções
Programa: função que mapeia entrada na saída
Funções escritas como funções mais simples
Linguagens Dataflow (fluxo de dados)
Computação como o fluxo de “tokens” entre funções (“nodes”)
Modo inerentemente paralelo:
“nodes” são ativados quando a informação chega
“nodes” podem operar em paralelo
Linguagens Lógicas
Inspiração: lógica de predicados
Computação: provar teoremas a partir de regras
Linguagens von Neumann
Mais familiar: modelo de C
Computação: modificação do valor de variáveis
Atribuições influenciam a computação
“Computação por efeito colateral”
Linguagens “Scripting”
Subconjunto das linguagens von Neumann
Ênfase em juntar diferentes componentes
Muitas desenvolvidas para fins específicos: bash
Ênfase:
facilidade de criação de protótipos
facilidade de expressão no lugar de desempenho
Linguagens OO
Similares a linguagens von Neumann
Computação: interação entre objetos
Objetos: estado interno e rotinas para controlá-lo
Exemplo - C
int gcd(int a, int b){while (a != b){if (a > b){a = a-b;
}else{b = b-a;
}}return a;
}
MDC - von Neumann:
Para computar o MDC de a e b, primeiro verifique se eles são iguais.
Se forem, retorne um e pare.
Caso contrário, substitua o maior pela sua diferença e repita.
Exemplo - SchemeMDC - Funcional
MDC de a e b é definido como:
(1) a quando a e b forem iguais
(2) o MDC de b e a-b quando a for maior que b
(3) o MDC de de a e b-a quando b for maior que a
Para computar o MDC para um par de números, repita, expanda e simplifique essa definição até que termine
(define gcd(lambda (a b)(cond ((= a b) a)((> a b) (gcd (- a b) b))(else (gcd (- b a) a)))))
Exemplo - Prolog
gcd(A,B,G) :- A = B, G = A.gcd(A,B,G) :- A > B, C is A-B, gcd(C,B,G).gcd(A,B,G) :- B > A, C is B-A, gcd(C,A,G),gcd(A,B,G).
MDC - Lógico
A proposição MDC(A,B,G) é verdadeira quando
(1) A, B e G forem iguais
(2) A é maior que B e existe um número C tal que C é A-B e MDC(C,B,G) é verdade
(3) A é menor que B e existe um número C tal que C é B-A e MDC(C,A,G) é verdade
Para computar o MDC de dois números, procure pelo número G para o qual essas regras permitam provar que MDC(A,B,G) é verdadeiro
Compilação
Compilador
Código fonte
ProgramaEntrada Saída
Compilação x Execução
Compilador: programa
Vantagem: desempenho
Decisões feitas na compilação não precisam ser feitas na execução
Interpretação
InterpretadorCódigo fonte
EntradaSaída
Interpretador: máquina virtual
Execução do código fonte em conjunto com a entrada
Vantagem: flexibilidade
Código pode gerar novo código em tempo de execução
Caso Prático
Tradutor
Código fonte
Programa IntermediárioSaídaMáquina Virtual
Entrada
Compilação: tradutor complicado
Interpretação: tradutor simples
Simples = transformação mecânica
substituição de símbolos
Pré-Processamento
Pré-processador
Código fonte
Código fonte alterado
Remove comentários e macros
Pode remover pedaços do código: compilação condicional:
Diferentes versões de um programa a partir do mesmo código
“Linker”
Compilador
Código fonte
Linker
Código de máquina incompleto Bibliotecas
Código de máquina
Conversão para Assembler
Compilador
Código fonte
Assembler
Código “assembler”
Código de máquina
Tradução
Tradutor
Código fonte
Código fonte em outra linguagem
“Bootstrapping”
Compiladores escritos na linguagem que eles foram feitos para compilar
Como compilar o compilador pela primeira vez?
“Bootstrapping”:
Implementação simples: interpretador
Incrementos sucessivos
Pascal
Compiladores para Pascal eram criados usando as seguintes ferramentas:
Compilador Pacal, escrito em Pascal: gera uma saída intermediária chamada P-code
O próprio compilador traduzido em P-code
Um interpretador de P-code escrito em Pascal
Pascal
Criando o compilador:
Tradução (manual) do interpretador de P-code para uma linguagem disponível
Usa-se o interpretador para rodar o compilador
Compila-se o código do compilador o compilador interpretado
Outras formas de compilação
Compilação de linguagens interpretadas:
Geração de código extra que é quase um interpretador
Compilação dinâmica ou “just-in-time”
Compilação imediatamente antes da execução do código
Linguagens que permitem geração de código em tempo de execução
Byte-code de Java
Micro-código:
Linguagem assembler é interpretada por um código de máquina chamado “micro-código”
Ferramentas auxiliares:
“Debuggers”
Editores
Verificadores de estilo: análise sintática/semântica
Controle de configuração e dependências
“Profilers”
IDE
“Integrated Development Environment”
Integram diversas ferramentas
Ex.: Eclipse, XCode, MS Visual Studio
As vezes são essenciais para a linguagem:
Ex.: Smalltalk
Exemplo
Visão Geral: Compilação
Scanner (análise léxica)
Parser (análise sintática)
Análise semântica e geração de código intermediário
Otimização independente da máquina
Geração do código
Otimização dependente da máquina
fluxo de caracteres
Fluxo de tokens
“Parse tree”
Árvore de sintaxe abstrata
Forma intermediária
Linguagem alvo
Linguagem alvo modificada
Tabe
la d
e Sí
mbo
los
“Frontend”
“Backend”
Análise Léxica e SemânticaRelembrando o MDC em C:
int main(){int i = getint(), j =getint();while (i != j){if (a > b) i = i -j;else j = j - i;
}putint(i)
}
Análise Léxica e Semântica
Scanning e parsing:
reconhecer a estrutura do programa
não estão interessados no significado
Scanner leitura caracteres e agrupamento em símbolos
Símbolos: menor unidade significativa do programa
Análise Léxica
Tokens do MDC:
Principal tarefa do analisador léxico:
reduzir número de símbolos para análise sintática
int main ( ) { { int i =getint ( ) , j j = getint () ; while ( i i != j ){ if ( i > > j ) i= i - j ; ; else j =j - i ; } } putint ( i) ; }
Análise Sintática“Parsing”:
geração da “parse tree”
construções de alto nível em função de suas partes
construções de alto nível = funções, expressões
raiz da árvore: programa
Utilização de gramáticas de contexto livre
Regras: construção -> expansão
Exemplo: While em Citeration-statement ➝ while ( expression ) statement
statement ➝ compound-statement
compound-statement ➝ {block-item-list-opt}
block-item-list-opt ➝ block-item-list
block-item-list-opt ➝ ∈
block-item-list ➝ block-item
block-item-list ➝ block-item-list block-item
block-item ➝ declaration
block-item ➝ statement
Análise Semântica
Descobrir significado no programa
Reconhecimento de ocorrência múltipla de símbolos
Ao que cada ocorrência do símbolo se referencia
Identificação dos tipos e verificação de consistência
Tabela de símbolos: auxilia o analisador
Análise SemânticaExemplo em C
Análise semântica em C verifica se:
todo identificador é declarado antes de ser utilizado
um identificador é utilizado num contexto inapropriado
chamadas de funções utilizam o número e tipos corretos para os argumentos
nomes utilizados nos ramos de um switch são corretos
funções possuem o return correto (se não forem void)
Análise Semântica
Nem todas regras semânticas podem ser aplicadas em tempo de compilação:
compilador inclui verificações em tempo de execução para essas regras
Semântica estática: verificável em tempo de compilação
Semântica dinâmica: verificável em tempo de execução
Análise SemânticaExemplo de verificações dinâmicas (em algumas linguagens):
variáveis nunca são utilizadas numa expressão se não possuírem um valor
Ponteiros nunca são de-referenciados a não ser que apontem para um objeto válido
Índices de vetores estão dentro de limites permitidos
Operações aritméticas não causam “overflow”
Análise Semântica
Árvore sintática:
formada através da remoção de nós artificiais na “parse tree”
nós são anotados: atributos
Exemploprogram
:=
(5) call
(3) (6)
:=
call
(3)
while
call
(4) (5)if≠
(5) (6)
> := :=
(5) - -(5) (6) (6) (5)
(5) (6) (6)
Index Símbolo Tipo1 void tipo2 int tipo3 getint func: (1)->(2)4 putint func: (2)->(1)5 i (2)6 j (2)
Geração de Código
Objetivo: gerar código a partir da árvore
Algoritmo:
percorrer a tabela de símbolos e atribuir localização para as variáveis
percorrer a árvore e gerar comandos
Otimização de Código
Diminuição do tempo de execução
Diminuição do consumo de memória
Dependente ou independente da arquitetura/processador
Sintaxe
Linguagens de computação precisam ser precisas
Especificação sem ambiguidade da:
forma (sintaxe)
significado (semântica)
Veremos sintaxe
ExemploNumerais: representação de números
digit -> 0|1|2|3|4|5|6|7|8|9
Digit: bloco de construção de números
Números: sequência de digits começando por um numeral diferente de zero:
non-zero_digit -> 1|2|3|4|5|6|7|8|9
natural_number -> non_zero_digit digit*
Sequência de caractere: sem significado semântico
Especificando SintaxeEspecificação formal de sintaxe: requer regras
Construção a partir de caracteres individuais
Construção de símbolos:
1. Concatenação
2.Alternância
3.“Kleene closure” (repetição)
Restante da sintaxe: recursão
Conjunto regular: definido pelas três regras
Conjuntos regulares: criados por expressões regulares
Conjuntos de strings que podem ser formados por conjuntos regulares + recursão
Linguagem livre de contexto (LLC)
LLC: gerada por uma gramática livre de contexto
Linguagem = linguagem formal ≠ linguagem de programação
Especificando Sintaxe
TokensUnidades de construção de um programa:
menor conjunto de caracteres com significado
Podem ser de diferentes tipos:
palavras chaves
identificadores
símbolos
constantes
Podem ser definidos por apenas um caractere
Exemplo: operadores
Exemplo: C100 tipos de tokens
37 palavras chaves: double, if, return ...
identificadores: minha_variavel, seu_tipo
números inteiros: 0223, 0x1f2,
números em ponto-flutuante: 432e-2
caracteres: `a’, ‘b’
string literals: “test”
“punctuators”: +, [ , ||, *=
formas de comentário
Expressões Regulares
Usadas para especificar tokens
Uma expressão regular é:
1. um caractere
2. uma string vazia = ∈
3. duas expressões regulares uma do lado da outra = concatenação
4. duas expressões regulares separadas por | = alternância
5. uma expressão regular seguida de ⋆ = concatenação por repetição
ExemploSintaxe de constantes numéricas:
token = number
number ➝ (-|+|∈) (integer|real)
integer ➝ digit digit⋆
real ➝ integer exponent | decimal (exponent|∈)decimal ➝ digit⋆(. digit|digit .)digit⋆exponent ➝ (e|E)(+|-|∈)integerdigit ➝ 0|1|2|3|4|5|6|7|8|9
Expressões Regulares:Outros Usos
Forma útil de definir strings
Usada em diversas ferramentas:
grep, emacs
Suporte em algumas linguagens:
Perl, Python, Ruby
Extensões:
“zero ou mais ocorrências”
“qualquer coisa que não seja espaço”
Gramáticas Livre de Contexto (GLC)
Expressões regulares não definem construções aninhadas
Exemplo:
Construção definida a partir dela mesmo
expr ➝ id | number | - expr | ( expr ) | expr op expr
op ➝ + | - | * | /
GLC
Símbolo “➝” = “pode ter a forma de”
Regras de GLC: produção
Símbolos a esquerda: variáveis ou não-terminais
Várias produções para uma mesma variável
Símbolos que gerarão uma derivação: terminais
não podem aparecer na esquerda
Linguagem de programação: terminais = tokens
Ponto de partida: terminal na esquerda da 1a produção
Backus-Naur Form (BNF)
Notação para GLC
Não inclui “⋆” e parênteses
Extended Backus-Naur Form (EBNF)
Inclui “⋆” e parênteses
Pode incluir “+”: 1 ou mais repetições
EBNF = BNF
BNF tem o mesmo poder de expressão do EBNF!
id_list ➝ id (, id)⋆id_list ➝ id
id_list ➝ id_list , id=
op ➝ + | - | * | /
op ➝ +
op ➝ -op ➝ *op ➝ /
=
Derivação e Parse TreeGCL mostra como gerar strings sintaticamente válidas:
1. Comece com um símbolo inicial
2. Escolha uma produção com o símbolo inicial na esquerda
3. Substitua o símbolo inicial com o lado direito da produção
4. Agora escolha uma variável A da string resultante, escolha uma produção P com A no seu lado esquerdo
5. Substitua A pelo lado direito de P
6. Repita até que não sobre nenhuma variável
ExemploGerar a string: “slope * x + intercept”
expr ⇒ expr op expr
⇒ expr op id
⇒ expr + id
⇒ expr op expr + id
⇒ expr op id + id
⇒ expr * id + id
⇒ id * id + id (slope) (x) (intercept)
expr ➝ id
expr ➝ number expr ➝ expr op expr
op ➝ + | - | * | /
BNF
“⇒” deriva
Derivação
Derivação:
Sequencia de substituições que demonstram como chegar num determinado token
Forma sentencial: linhas da derivação
Saída: última forma sentencial que só possui terminais
Parse TreeRepresentação gráfica de uma derivação
expr
exprop
*
expr
exprop
+
exprid (slope)
id (x)
id (intercept)
expr
expr op
+
expr
exprop
*
expr id (intercept)
id (slope)
id (x)
GLC ambígua: permite criação de mais de uma parse tree para uma dada string
Parse TreePara uma dada linguagem:
infinitas gramáticas possíveis
Porém, algumas gramáticas são mais úteis que outras
Evitar gramáticas ambíguas
Símbolos inúteis:
Variáveis que não podem gerar terminais
Terminais que não podem aparecer em nenhum resultado de derivação
Construção de Gramáticas
Critérios no projeto de gramáticas para uma linguagem de programação:
Gramática deve refletir estrutura interna do programa (facilita compilação)
Deve ser facilmente “parsed”
Exemplo
Expressões aritméticas:
uso da gramática para refletir associatividade e precedência
Associatividade: operadores são agrupados da esquerda para direita
Precedência: multiplicação antes da soma
Exemplo
expr ➝ term | expr add_op term
term ➝ factor | term mult_op factor
factor ➝ id | number | -factor | (expr) add_op ➝ + | -mult_op ➝ * | /
Não é ambígua
Captura precedência a associativade
ExemploDerivando 10-4+3expr
expr add_op
+
term
termadd_op
-
expr factor
term factor
expr ➝ term | expr add_op term
term ➝ factor | term mult_op factor
factor ➝ id | number | -factor | (expr)
add_op ➝ + | -
mult_op ➝ * | /factor
number(10)
number(4)
number(3)
ExemploDerivando 3+4*5
expr
expr
op
+
term
term mult_opterm
factorfactor
number(3)
number(4)
*
factor
number(5)
expr ➝ term | expr add_op term
term ➝ factor | term mult_op factor
factor ➝ id | number | -factor | (expr)
add_op ➝ + | -
mult_op ➝ * | /
Exercícios - Calculadora
assign ➝ :=plus ➝ +minus ➝ -times ➝ *div ➝ /lparen ➝ (rparen ➝ )
id ➝ letter (letter|digit)⋆ except for read and write
number ➝ digit digit⋆ | digit⋆(.digit|digit.)digit⋆
comment ➝ /* (non-*|* non-/)⋆ */ | // (non-newline)⋆ newline
Tokens:
Parte IIElementos de Linguagens de
Programação
IntroduçãoPrimeiras linguagens:
Separação código/máquina
Atualmente:
Facilidade de programação
Necessidade de tipos de abstração
Nomes, controles, tipos, rotinas e classes
Decisões de projeto de linguagens
Nomes, Uniões e Escopo
NomesNome = mnemônico
Maior parte das linguagens: identificadores
Tokens alfa-numéricos (+ alguns outros símbolos)
Permitem o programador referenciar
variáveis, constantes, operações, tipos,
Programador não precisa saber conceitos de baixo nível como o endereço de uma variável
Nomes e AbstraçãoAbstração:
processo que o programador utiliza para associar nomes a fragmentos de código
Fragmento: pensado em termos da função que exerce no lugar de como ele exerce essa função
Redução de complexidade: informações irrelevantes ficam escondidas
Rotinas: abstrações de controle
Classes: abstrações de dados
Tempo de União
União: associação entre duas coisas
Neste caso: nome / o que é nomeado
Tempo de União:
instante em que uma união é criada
tempo em que qualquer decisão de implementação é feita
Tempos de UniãoProjeto: estruturas de controle, tipos, ...
Implementação: precisão dos tipos, I/O, ...
Escrita do programa: algoritmos, estruturas de dados, ...
Compilação: mapeamento em código de máquina, ...
“Link”: resolução de nomes de diferentes módulos
Carregamento: momento que o sistema operacional carrega o programa para memória
Execução: união de valores para variáveis, ...
União: Estática x Dinâmica
União estática: antes da execução
União dinâmica: durante a execução
Linguagens compiladas:
decisões sobre uniões ocorrem mais cedo
maior eficiência (ex. vetor)
Tempo de Vida de Objetos
Diferença entre: nome e objetos a que eles se referem
Eventos chaves:
Criação de objetos
Criação de uniões
Referências para variáveis, tipos, ...
Desativação e reativação de uniões
Destruição de uniões
Destruição de objetos
Tempo de Vida de Objetos
Período entre criação de destruição da união/objeto:
Tempo de vida da união/objeto
Tempo de vida da união ≠ Tempo de vida do objeto
Ex.: Passagem de valores por referência
Tempo de vida da união nome de parâmetro/valor menor que o do objeto
Ex.: Conteúdo do ponteiro deletado
Mecanismos de Alocação
Tempo de vida de objetos está associado ao mecanismo utilizado para alocar o objeto:
Estático: endereço constante
Stack: alocação LIFO (“last in - first out”)
Heap: alocação em momentos arbitrários
Alocação EstáticaO que é alocado estaticamente:
Variáveis globais
Instruções do programa
Constantes numéricas e literais
Variáveis locais estáticas
Tabelas auxiliares geradas pelo compilador
Armazenadas em memória só de leitura
Alocação EstáticaConstantes de tempo de compilação
Possuem nome
Expressão deve conter apenas outras constantes e funções padrões
Podem alocadas estaticamente
Constantes de tempo de elaboração
Podem depender de valores em tempo de execução
Não são estáticas
São variáveis cujo valor não podem ser alterado
Alocação Estática de Variáveis Locais
Variáveis locais:
criadas quando sua subrotina é chamada
destruídas quando a subrotina retorna
Cada chamada: nova instância da variável local
Se a linguagem não permite recursão:
alocação estática (pelo compilador)
Ex.: Fortran (antes do Fortran 90)
Dados de uma SubrotinaChamada de uma subrotina/função:
Variáveis locais
Constantes de tempo de elaboração
Argumentos e valores de retorno
Usualmente mantido em registradores
Temporários: usados em cálculos complexos
Misc.: endereço de retorno, informação de debug
Alocação no Stack
Aninhamento de subrotinas:
permite criação de espaço no stack para variáveis locais
Cada instância de uma subrotina: quadro
Argumentos a serem passados para uma subrotina:
no topo do quadro
outros dados não tem uma ordem específica
Alocação no “Stack”
Subrotina D
Subrotina C
Subrotina B
Subrotina B
Subrotina A
Argumentospara rotinas
Temporários
Variáveis Locais
Misc.
Endereço de retorno
procedure C
D; E
procedure B
if ... then
B
else
C
procedure A
B
-- main program
A
sp
fp
fp(quando C está
sendo executado)
sp: “stack pointer”, fp: “frame pointer”
Alocação no Stack
Manutenção do conteúdo do stack
responsabilidade da rotina de chamada
Rotina de chamada:
código executado imediatamente antes e após da rotina propriamente dita
Alocação no StackLocalização de um quadro: não determinado
Comprimento do quadro: determinado estaticamente
Determina o “offset”
“Offset” de coisas dentro do quadro:
usualmente podem ser determinadas estaticamente
“Frame pointer” (apontador para o quadro):
compilador pode faze-lo apontas para uma posição conhecida dentro do quadro
Alocação no Stack
Acesso a variáveis locais de um quadro:
soma de um valor ao FP
Variáveis locais, temporários: offset negativo
Argumentos e valor de retorno: offset positivo
Ficam no quadro de quem chama a rotina
Alocação no Heap
Região de memória onde blocos podem ser arbitrariamente alocados e desalocados
Necessário para determinados objetos:
Listas encadeadas, strings, listas e conjuntos
Coisas que podem mudar de tamanho em tempo de execução
Gerenciamento do Heap
Compromisso: velocidade x espaço
Espaço: fragmentação interna e externa
Interna: alocação de mais memória do que necessário para um objeto
Externa: blocos de um dado objeto são espalhados pela memória
Diversos algoritmos para lidar com esse problema
Coletor de LixoAlocação de memória no Heap:
necessidade de alguma ação no programa
Desalocação de memória no Heap:
C, C++: necessidade de ação
Outras linguagens: desalocação automática
Biblioteca de tempo de execução:
coletor de lixo: definido pela linguagem
Coletor de Lixo
Argumentos contra:
simplicidade de implementação
velocidade de execução
Argumentos a favor:
diminuição de erros e bugs
facilidade de programação
EscopoDefinição:
região textual do programa em que uma união está ativa
Escopo estático:
escopo determinado em tempo de compilação
Escopo dinâmico:
escopo só pode ser determinado em tempo de execução
Conjunto de uniões ativas: conjunto de referência
determinado pelas “regras de escopo” da linguagem
Exemplo - CEntrada de uma rotina:
criação de um novo escopo
criação de uniões para objetos locais
desativação de uniões globais que tenham o mesmo nome que objetos globais
Na saída de uma rotina:
destruição de uniões locais
reativação de uniões globais previamente desativadas
Escopo EstáticoEscopo determinado completamente a partir do código
Usualmente:
união atual para um nome = declaração no bloco mais próximo do uso do nome
Regras de escopo simples:
só existem variáveis globais (1a versão de Basic)
só existem variáveis globais e locais (Fortran)
Normalmente: necessidade de regras mais complicadas
Rotinas Aninhadas
Aninhamento de rotinas:
permitido em diversas linguagens
Pascal, Ada, Python, Scheme, Lisp
C/C++:
Não permitido para funções
Mas, escopos podem ser aninhados
Rotinas AninhadasDeclarações feitas num bloco são invisíveis em outros blocos - escopo do tipo Algol
Regra do “escopo aninhado mais próximo”:
um nome introduzido por uma declaração é visível no escopo em que foi declarado e qualquer escopo aninhado interno
a não ser que o nome seja ocultado por uma declaração com mesmo nome num dos escopos aninhados
Rotinas Aninhadas
Como achar o objeto associado a um nome:
Procura pela declaração com o nome no escopo mais interno em utilização
Se existe uma declaração, ela é utilizada para determinar o objeto
Senão, a busca é feita no escopo imediamente externo
Exemplo
int main(){int i = 0;{int i = 1; /* i == 1 */{int i = 2; /* i == 2 */
}/* i == 1 */
}/* i = 0 */
}
Rotinas Aninhadas
Objetos pré-definidos pela linguagem:
tipos, operadores matemáticos, ...
Eles são definidos num escopo mais externos, acima do escopo onde variáveis globais são declaradas
Resolução de Escopo
União nome-objeto que está oculta por uma declaração aninhada com mesmo nome:
Como acessar esse nome?
Operadores de resolução de escopo:
qualificador do nome: define o escopo em que o nome foi declarado
Exemplo: C++ ::x -> x declarado no escopo global
Ordem de Declaração
Suponha o objeto X declarado no bloco B
O escopo de X inclui a parte de B antes da declaração de X?
Obs.: Exigir declarações no início do bloco não impedem o problema...
Diferentes linguagens, diferentes regras
Pascal
const N = 10;...procedure foo;const M = N; (*static semantic error*)...N = 20; (*declaração local, esconde o N global*)
Declaração vale para todo o bloco (escopo em blocos)
Pascal
const N = 10;...procedure foo;const M = N;
varA : array [1..M] if integer;N : real;
C#
Também utiliza escopo em blocos
class A {const int N = 10;void foo() {const int M = N; // uso do N interno antes da declaraçãoconst int N = 20; ...
Python
Sem declarações de variáveis
Variáveis na rotina S são aquelas que aparecem nas expressões da rotina S
Variáveis não-locais são apenas de leitura e precisam ser explicitamente importadas
Python
a = 1
def f():print a # 1
def g():print a # Erroa = 2
def h():global aa = 2print a # 2
Altera o valor da variável global
Leitura da variável global Ok
Nome “a” agora é local
Declaração e DefiniçãoTipos e rotinas recursivos e linguagens que demandam declaração antes de utilização
Como duas declarações podem aparecer antes uma da outra?
struct empregado {struct gerente *chefe;struct empregado *proximo_empregado;...
};struct gerente {
struct empregado *primeiro_empregado;...
};
Declaração e Definição
Solução de C/C++:
distinção definição x declaração
Declaração: define o nome e seu escopo
Definição: detalhes de implementação
Em alguns casos: declaração pode servir também como definição
C
struct gerente; /* Declaração!*/struct empregado {
struct gerente *chefe;struct empregado *proximo_empregado;...
};struct gerente { /* Definição!*/
struct empregado *primeiro_empregado;...
};
MódulosProjetos grandes:
Como dividir o trabalho entre diversos programadores?
Modularização: divisão do código em partes independentes
Ocultamento de informação:
esconder algoritmos de partes do código onde são desnecessários
reduz a quantidade de código necessária para o entendimento de uma parte do programa
Boa modularização:
interface entre módulos é simples
parte mutável do código ocultada dentro de um módulo
reduz quantidade de conflitos de nomes
Encapsulamento de Dados e Rotinas
Rotinas aninhadas:
ocultamente de informação limitado: objetos limitados ao tempo de vida da rotina
Variáveis estáticas:
permite: rotinas tenham memória
permite: abstração de apenas uma única rotina
não permite: interfaces que precisam de mais de uma rotina
Necessidade de uma nova construção nas linguagens: módulo
Módulos como Abstrações
Módulos:
coleção de objetos: rotinas, variáveis, tipos, ...
Encapsulado de maneira que:
1. Objetos dentro do módulo enxergam uns aos outros
2. Objetos dentro do módulo são invisíveis fora do módulo a não ser que explicitamente exportados
3. (opcional) objetos fora do módulo são invisíveis a não ser que explicitamente importados
Regras definem visibilidade dos objetos, mas não o seu tempo de vida
Módulos em Diferentes Linguagens
Package: Ada, Java, Perl
Module: Python
Namespace: C++, C#, PHP
Exemplo: Stack (Modula-2)
CONST stack_size = ...TYPE element = ......MODULE stack;IMPORT element, stack_size;EXPORT push, pop;TYPE
stack_index = [1..stack_size];VAR
s : ARRAY stack_index OF element;top : stack_index;
PROCEDURE error; ...
PROCEDURE push (elem : element);BEGIN
IF top = stack_size THENerror;
ELSEs[top] := elem;top := top + 1;
END;END push;
PROCEDURE pop () : element;BEGIN
IF top = 1 THENerror;
ELSEtop := top - 1;RETURN d[top];
END;END pop;
BEGIN top := 1;
END stack;
VAR x, y : element;...push(x);...y := pop;
“Import” e “Export”Possíveis limitações da exportação:
variáveis apenas de leitura
tipos “opacos”: não podem ser manipulados
Módulos de escopo fechado: nomes precisam ser explicitamente importados
Reduz conflitos de nomes, facilita entendimento do código
Módulos com escopo seletivamente abertos:
Nome foo exportado pelo módulo A é automaticamente visível no módulo B como A.foo (ou foo se B importar explicitamente o nome)
Ada, Java, C# e Python
Lista de importação: documenta a interface entre partes de um programa
Módulos como Gerentes
Exemplo anterior: módulos definem apenas uma abstração
Módulo define apenas uma pilha
Várias pilhas: módulo como gerente
Gerencia o tipo “pilha”
Subrotinas: criar e destruir o tipo
Subrotinas: argumento definindo stack
CONST stack_size = ...TYPE element = ......MODULE stack_manager;IMPORT element, stack_size;EXPORT stack, init_stack, push, pop;TYPE
stack_index = [1..stack_size];stack = RECORD
s : ARRAY stack_index OF element;top : stack_index;
END;
PROCEDURE init_stack(VAR stk : stack);BEGIN
stk.top := 1;END init_stack;
PROCEDURE push (VAR stk : stack, elem : element);BEGIN
IF stk.top = stack_size THENerror;
ELSEstk.s[stk.top] := elem;stk.top := stk.top + 1;
END;END push;
PROCEDURE pop (VAR stk : stack) : element;BEGIN
IF stk.top = stack_size THENerror;
ELSEstk.top := stk.top - 1;RETURN stk.s[stk.top];
END;END pop;
END stack_manager;
VAR A, B : stack;var x, y : element;...init_stack(A);init_stack(B);...push(A, x);...y := pop(B);
Exemplo: Gerente
Módulos como Tipos
Outra possível solução: módulos definem tipos
Módulo de tipo: permite a declaração de um número arbitrário
Rotinas pertencem ao módulo
Exemplo: Stack (Euclid-2)
const stack_size = ...type element = ......type stack = module
imports (element, stack_size)exports (push, pop)
type stack_index = 1..stack_size;
vars : array stack_index of elementtop : stack_index
procedure push(elem : element) = ...function pop returns element = ......initially
top := 1end stack
VAR A, B : stack;var x, y : element;...A.push(x)...y := B.pop
Orientação a ObjetosLinguagens modernas:
classes = módulos como tipos + herança
Herança
classes definidas como extensões ou refinamento de classes que já existem
objetos podem herdar comportamento de outros objetos
Facilita reuso de código
Cada instância da classe ou módulo A:
cópia separada das variáveis
variáveis são apenas visíveis quando executando uma das rotinas de A
Visíveis para outras rotinas se A é passada como argumento
Orientação a Objetos
Exemplo
class stack {...
bool deeper_than(stack other) {return (top > other.top);
}...
}...if (a.deeper_than(B)) ...
Módulos e Classes
Classes não substituem módulos em todos os casos
Exemplo: Jogo
Hierarquia: personagens, prédios, objetivos, ...
Módulos: divisão do projeto em sub-sistemas (não requerem herança)
Linguagens com classes e módulos: C++, Java, C#, Python, Ruby, ...
Escopo DinâmicoAssociação entre nome e objeto é determinado em tempo de execução:
ordem de chamada das rotinas
Única regra:
união para um nome é aquela encontrada mais recentemente durante a execução do programa e ainda não destruída
Linguagens: APL, Snonbol, TeX e Perl
Verificação de tipos: só possível em tempo de execução
Escopo Dinâmico: Exemplo
int x = 0;int f() {
return x;}int g() {
int x = 1; return f();
}
Escopo estático:- Retorna: 0
Escopo dinâmico- Retorna: 1
f() enxerga associação “mais recente”
Escopo Dinâmico: Exemplo
n : integer
procedure firstn := 1
procedure secondn : integerfirst()
n := 2if read_integer() > 0
second()else
first()write_integer(n)
Escopo estático:- Exibe: 1
Escopo dinâmico- valor depende do valor lido por
read_integer()- Se maior que zero: exibe 2
- Se menor ou igual a zero: exibe 1
Escopo Dinâmico
Ponto favorável: facilita modificação de rotinas
Exemplo: função para imprimir inteiros em qualquer base:
Caso padrão: decimal
Escopo dinâmico: modificação durante execução
begin -- nested blockprint_base : integer = 16 -- hexadecimal print_integer(n)
Implementação do Escopo(Estático)
Tabela de símbolos:
dicionário: nome -> informação
operações:
nova entrada: união nome-objeto
procura: busca de informação de um nome
enter_scope e leave_scope: visibilidade
Nada é removido: tabela é mantida completa
Significado de Nomes
Até agora:
relação um para um entre nome e objeto
Na realidade:
nome pode referenciar mais de um objeto
objeto pode ter mais de um nome
Aliases (Apelidos)
Quando dois nomes apontam para o mesmo objeto:
C: união
Ponteiros
Passagem de variáveis por referência
Em geral: tornam o código mais confuso
Exemploint a, b, *p, *q;...a = *p;*q = 3;b = *p;
Complicação desnecessária para o compilador
Atribuição em a faz com que *p seja trazido para um registrador
Compilador gostaria de deixar *p em um registrador (por causa da atribuição de b)
Mas não consegue fazer isso pois não sabe se p e q apontam para o mesmo objeto
Sobrecarga
Quando um nome referencia mais de um objeto
Exemplo: operador + em C
Exemplo Ada
declare type month is (jan, feb, mar, apr, may, jun,
jul, aug, sep, oct, nov, dec);type print_base is (dec, bin, oct, hex);mo : month;pb : print_base;
beginmo := dec; -- mes dezembropb := oct; -- a base octprint (oct); -- erro!
Exemplo C++struct complex {
double real, imaginary;};enum base {dec, bin, oct, hec};
int i;complex x;
void print_num(int n){...void print_num(int n, base b){...void print_num(complex c){...
print_num(i);print_num(i, hex);print_num(x);
Redefinição de Operadores
Sobrecarga dos operadores aritméticos
Ada, C++, C#, Fortran90, Python
Sintaxe alternativa para o operador:
Ada: A+B -> “+”(A, B)
C++: A+B -> operator+(A, B) ou A.operator+(B)
Exemplo C++
class complex{double real, imaginary;...
public:complex operator+(complex other){
return complex(real+other.real, imaginary+other.imaginary);}...
};...complex A, B, C;...C = A + B;
Sobrecarga, Polimorfismo e Coerção
Para nome de rotinas:
Sobrecarga x Polimorfismo x Coerção
Mecanismos para:
passar argumentos de diferentes tipos para rotinas
Diferença sintática
ExemploCálculo do menor valor entre dois números inteiros ou em pontos-flutuante
function min(a, b : integer) return integer is ...function min(a, b : real) return real is ...
Ada:
double min(double x, double y){ ...
C:
Sobrecarga: compilador chama a função
adequada para o tipo
Coerção:compilador converte de
int para double
Coerção
Processo pelo qual o compilador converte um tipo em outro
Diferente regras em diferentes linguagens:
Ada: não faz coerção de tipo, a menos de constantes
C e Pascal: coerção de inteiros para ponto flutuante
C++: regras de coerção podem ser estendidas pelo programador
Polimorfismo
Mesma rotina, vários tipos de argumentos
SEM conversão
Termo:
“pode assumir várias formas”
Aplicado a dados e rotinas
Tipos precisam ter características em comum
PolimorfismoPolimorfismo paramétrico:
código aceita um tipo ou conjunto de tipos como parâmetros
Encontrado em: linguagens orientada a objetos (herança)
Polimorfismo de subtipo:
código é feito para funcionar para um tipo T, mas o programador por definir extensões e refinamentos
Implícito: tipo não é definido (Lisp, Python)
Explícito: tipo é definido = programação genérica (C++, Java, C#)
Polimorfismo: Implementação
Programação genérica (paramétrico explícito):
Geralmente: múltiplas cópias do código, uma para cada tipo
Herança (subtipo):
única versão do código, informação extra sobre representação dos objetos é incluída
Paramétrico implícito:
pode ser feito das duas maneiras
Polimorfismo: Implementação
Linguagens que fazem verificação de tipo em tempo de execução:
C++, Java, C#: oferecem herança e programação genérica
Smalltalk, Objective-C, Python, Ruby: apenas um mecanismo que fornece ambos tipos de polimorfismo
Exemplo Programação Genérica
generic type T is private;with function “<“(x, y : T) return Boolean;
function min(x, y : T) return T isbegin
if x < y then return x;else return y;end if;
end min;
function string_min is new min(string, “<“);function date_min is new min(date, date precedes);
Ada
ExemploPolimorfismo Param. Implícito
def min(x, y):if x<y:
return xelse:
return y
a = 1b = 2c = complex(1,1)
b = min(a, b) # b=1a = min(a, c) # ERRO
Python
União de Ambientes de Referenciamento
Referência para rotinas:
Rotinas podem ser passadas como referências para outras rotinas
Quando a regra de escopo deve ser aplicada:
Quando a referência é criada?
Quando a rotina é chamada?
Exemplo Escopo Dinâmicotype person = record
...age : integer...
threshold : integerpeople : database
function older_than_threshold(p : person):booleanreturn p.age ≥ theshold;
procedure print_person(p : person)... -- garante que o comprimento da linha (line_length) não é ultrapassado.
procedure print_selected_record(db : database; predicate, print_routine : procedure) line_length : integer
if device_type(stdout) = terminalline_length := 80
elseline_length := 132
foreach record r in dbif predicate(r)
print_routine(r)
-- programa main...threshold := 35print_selected_records(people, older_than_threshold, print_person)
“Shallow bind”:
ambiente de referência é criado quando a função é chamada
Funciona para print_routine
“Deep bind”:
ambiente de referência é criado quando a função é passada como parâmetro
Útil para older_than_threshold
Exemplo Escopo Dinâmico
Fechamento de Rotinas
Implementação de “Deep binding”:
criação explícita do conjunto de referência
união desse conjunto com a referência para função
Conjunto + referência = Fechamento
Padrão para escopo estático
“Deep Binding”program binding_example(input, output);
procedure A(I : integer; procedure P);
procedure B;begin
writeln(I);end
begin (* A *)if I > 1 then
Pelse
A(2, B);end;
procedure C; begin end;
begin (* main *)A(1, C);
end.
B
AI==2
Ap==B
AI==1
Ap==C
main program
“Deep Binding”
Impacto:
variáveis que não são nem locais nem globais
Objetos locais:
fechamento não importa
Objetos globais:
nunca haverá mais de uma versão
Funções de Primeira Classe
Funções de primeira classe:
podem ser passadas como argumentos
podem ser retornadas por uma função
podem ser atribuídas a variáveis
Problema:
Nome dura mais do que o escopo em que foi definido
Exemplo
def plus_x(x):return lambda y: y+x
plus_two = plus_x(2)print plus_two(2) # 4
Escopo de x?
Tempo de vida do objeto?
Unlimited ExtentObjetos locais:
tempo de vida com duração infinita
Memória só é recuperada quando o sistema tiver certeza que o objeto não pode ser mais usado
Coletor de lixo
“Limited extent”: maior parte das linguagens imperativas
“Unlimited extent”: scripts, C#, Smalltalk
Outros Mecanismos
Não permitir rotinas aninhadas: C, C++
Só rotinas “de fora” são de primeira classe: Modula-2
Fechamento de Objetos
Impedimento de rotinas aninhadas
Problema:
Impede a passagem de funções com contexto
Alternativa em OO: objetos simples
Exemplo
interface IntFunc{public int call(int i);
}class PlusX implements IntFunc {
final int x;PlusX(int n) {x = n;}public int call(int i) {return i+x;}
...IntFunc f = new PlusX(2);System.out.println(f.call(3)); // 5
Fechamento de Objetos
Objeto que faz o papel de uma função e contexto:
Object closure, function object, functor
Exemplo
class int_func {public:
virtual int operator()(int i) = 0;};class plus_x : public int_func {
const int x;public:
plus_x(int n) : x(n) { }virtual int operator()(int i){return i+x;}
};...plus_x f(2);cout << f(3) << endl; // 5
Controle de Fluxo
Controle de Fluxo
Determinação da ordem em que as tarefas são executadas no código
Fundamental para quase todas linguagens
Mecanismos de Controle
Sequenciamento: ordem pré-definida
Seleção: escolha entre duas partes do código, dependendo de condições do tempo de execução
Iteração: pedaço do código é repetido até que alguma condição seja satisfeita
Abstração de procedimento: encapsulamento de controles de fluxo: procedimentos, módulos
Mecanismos de ControleRecursão: uma expressão é escrita em função de versões mais simples dela mesma
Concorrência: dois pedaços do programa executando ao mesmo tempo
Controle de exceção: um pedaço do código é executado e, caso ocorra erros, o fluxo é redirecionado para outra parte do código
Não-determinação: ordenação não é determinada (execução em qualquer ordem leva ao resultado correto)
Avaliação de ExpressãoExpressão:
função ou operador aplicado a um conjunto de argumentos
operador: funções da linguagem com sintaxe simplificada
Exemplos:
my_func(A, B, C)
a + b
- c
Operadores
Prefixo: op a b, op(a, b), (op a b)
Infixo: a op b
Sufixo: a b op
Usualmente:
Prefixo: funções e operadores unitários
Infixo: operadores binários
Notação Polonesa
Utilizada em Lisp para funções e operadores
(* (+ 1 3) 2)
(append a b c my_list)
Notação Mixfix
Utilizada em Smalltalk
Infixo para todas as funções
myBox displayOn: myScreen at: 100@50
Chama o método “displayOn: at:” com argumentos myScreen e 100@50
Notação por Infixo em C
a = b != 0 ? a/b : 0;
Posfixo
Comum em algumas calculadoras
Aparece ocasionalmente em algumas linguagens
Exemplo:
++ e -- em C++
Precedência
Define quais operadores são executados primeiro
na ausência de parênteses
Detalhes mudam de linguagem para linguagem
Normalmente: regras tentam garantir que o resultado esperado é encontrado
AssociatividadeDefine como operadores com mesma precedência são agrupados
Comportamento mais uniforme para diferentes linguagens:
Operadores aritméticos: associatividade pela esquerda
Exponenciação: associatividade pela direita
Recomendação: USE PARÊNTESES!
AtribuiçãoLinguagens funcionais: só tem expressões
Atribuições: linguagens imperativas
Mudança no valor de variáveis
Necessita de dois argumentos:
valor
referência para variável que armazenará
Expressões: retornam um valor
“Statements”: não retornam um valor
Referências e ValoresC:
d = a;
a: se refere a um valor
a = b +c;
a: se refere a posição do valor
Variáveis em C: container com nome
Linguagem com modelo de valor
Variáveis no lado direito e esquerdo de atribuições
l-values e r-values
l-value:
o que aparece do lado esquerdo de uma atribuição
r-value:
o que aparece do lado direito
Exemplos
(f(a)+3)->b[c] = 2;g(a).b[c] = 2;
Não é trivial saber o que pode ou não ser l-value
Modelo de ReferênciaVariável: referência para um valor
b referencia 2
c referencia 2 também
passagem das referências para o operador +
a referencia o resultado da operação
“2” é imutável
Filosoficamente: existe um único “2” no programa, que é referenciado por todas as variáveis que possuem esse valor
b := 2;c := b;a := b + c;
Modelo de ReferênciaDistinção entre l-value e r-value é explícita
Toda variável é l-value
Quando necessário num r-value, ela é de-refernciada
conversão implícita
conversão explícita
Necessária a distinção entre:
referências para mesmo valor
Mesmo objeto?
Temporariamente iguais?
Ortogonalidade
Meta ao se desenvolver uma linguagem de programação (ou mesmo programas)
“Features” da linguagem podem ser combinadas em qualquer ordem
Combinação é consistente
Principal princípio do projeto do Algol 68:
Não existem “statements”, apenas expressões
Exemplo
begina := if b < c then d else e;a := begin f(b); g(c) end;g(d);2 + 3;
end
if .. then .. else: retorna o valor da sequencia
statement list: valor de retorno da última função: g(c)
C
Abordagem intermediária:
distinção entre “statement” e expressões
Mas uma das classes de statement é:
“expression statement”: retorna um valor mas o jogo fora
Exemplo:
a = 4, retorna 4
Combinação de Operadores
Simplificação da sintaxe:
a = a+1; == a += 1;
Casos mais útil:
Outras combinações: ++ e --
b.c[3].d = b.c[3].d *e;b.c[3].d *= e;
int j = index_fn(i);A[j] = A[j] + 1;A[index_fn(i)] += 1;
Atribuição Múltipla
a, b, c = 1, 2, 3;a, b = c, d;a, b, c = foo(d, e, f);
Inicialização de VariávelPermitido por algumas linguagens
Vantagens:
inicialização de variáveis estáticas
permite otimização de alocação de variáveis estáticas pelo compilador
Evita uso de variáveis não-inicializadas
Inicialização durante declaração
Inicialização: Verificação Dinâmica
Variáveis não inicializadas podem ser checados em tempo de execução:
Caso estejam no estado “não-inicializdo”: Erro
Caso de variáveis numéricas:
baixo custo computacional
Exigência de Atribuição
Java e C#
Variável precisa ser atribuída antes de ser lida
Por todos os “caminhos” do código
Exemplo
int i;int j = 3;...if (j > 0){i = 2;
}... // valor de j não é alterado aqui...if (j > 0){System.out.println(i); // erro: i pode não
// ter sido inicialização
Construtores
Linguagens OO
Inicialização de variáveis alocadas dinâmicamente
Chamada de uma rotina de construção
C++: construção ≠ atribuição
C# e Java: construção = atribuição
Ordenação dentro de Expressões
a - f(b) - c * d
f(a, g(b), h(c))
Qual a ordem de avaliação?
Importante saber:
Se f(b) modificar d (efeito colateral)
Velocidade de execução
Em geral: ordem não é definida (permite otimização)
Curto-Circuito
Usado em expressões booleanas
Otimização do código
Ex.: a < b and ( b < c)
Se b for menor que c: a < b não é executado
Ex.: (a > b) or (b > c)
Curto Circuito
Pode reduzir tempo de execução:
if (condição_improvável && função_demorada())
Mas pode alterar a semântica:
p = my_list;while (p && p->key != val)p = p->next;
Exemplo
const MAX = 10;int A[10];...if (i >= 0 && i < MAX && A[i] > foo)...
if ( d != 0 && n/d > limiar) ...
Fluxo Não Estruturado
Controle de fluxo em assembler:
saltos condicionais e não-condicionais
Primeiras versões de Fortran:
“10”: statement label
if (A .lt. B) goto 10 ! .lt. é < ...
10
Fluxo Não Estruturado
Década de 70: programação estruturada
Abolição do goto
Alternativas ao goto
Retornos de função
Erros e exceções
break
continue
Sequenciamento
Determina a ordem das atribuições
Lista de statements sequenciados:
“{“ e “}”
“begin” e “end”
Seleção
If ... then ... else ...
Algol: primeiro “if”
if condition then statementelse if condition then statementelse if condition then statement...else statement
SeleçãoModula-2:
Lisp:
IF a = b THEN ...ELSIF a = c THEN ...ELSIF a = d THEN ...ELSE ...END
(cond((= A B)(...))
((= A C)(...))
((= A D)(...))
(T(...)))
Curto-Circuito
Implementação: pulos no código
Condição
não é armazenada
utilizada para controlar o fluxo
geração de código eficiente para booleanos com curto-circuito
Sequenciamento
Case/Switch
alternativa para if aninhados
CASE (*expressao*) OF1: ... 2, 7: ...3..5: ...10: ...ELSE ...
END
Sequenciamento
Case/Switch
Variações sintáticas:
série de valores x único valor
default requerido x opcional
SequenciamentoCase/Switch do C: pouco usual
switch (...) {case 1: ...
break;case 2: ...case 7: ...
break;case 3: ...case 4: ...case 5: ...
break;default: ...
break;}
Iteração
Repetição de tarefas similares
Controle por enumeração:
execução de um código para cada elemento de um conjunto finito
Controle lógico:
execução até que uma condição lógica seja satisfeita
Repetição Controlada por Enumeração
do i = 1, 10, 2 ...enddo
FOR i:= first to last by step DO ...END
Fortran 90
Modual 2
Complicações Semânticas
Loop “for”:
apenas para iteração: implementação simples
facilitador de enumeração
Complicações SemânticasQuestões que definem forma da enumeração:
1. Pode-se sair do loop de alguma forma que não terminando a enumeração?
Break
2. O que acontece quando modifica-se variáveis que afetam o critério de parada dentro do loop?
Critério é pré-computado
3. O que acontece quando o contador é modificado dentro do loop?
Normalmente não é permitido
4. Pode-se ler o conteúdo do índice após o loop? Se sim, qual o seu valor?
Diferentes soluções: declaração dentro do loop, valor final
For em Cfor (i = first; i<= last; i += step){...
}
{i = first;while (i <= last) {...i += step;
}}
=
Iteradores
Até agora:
iteração sobre sequências aritméticas
Ideal:
iteração sobre elementos de um conjunto finito
Solução: iteradores
Clu, Python, Ruby e C#
Objetos iteradores: Java, C++
Iteradoresfor i in range(first, last, step):...
Função range - iterador
Range: calcula o valor e o “retorna” para o loop
Loop usa o valor e chama range novamente
Range retoma a execução do ponto em que parou
Vantagem: separa mecanismo de enumeração do código que o usa
Exemploclass BinTree:def __init__(self): # construtorself.data = self.lchild = self.rchild = None
# Outros métodos: insert, delete, lookup, ...
def preorder(self): # Iteradorif self.data != None:yield self.data
if self.lchild != None:for d in self.lchild.preorder():yield d
if self.rchild != None:for d in self.rchild.preorder():yield d
Objetos Iteradores
C++, Java: não tem yield
Solução: guardar o estado da última iteração num objeto
Objeto iterador
Exemplo
BinTree <Integer> myTree = ......for (Integer i : myTree) {System.out.println(i);
}
BinTree <Integer> myTree = ......for (Iterator<Integer> it = myTree.iterator(); it.hasNext(); ) {Integer i = it.next();System.out.println(i);
}
=
class BinTree<T> implements Iterable<T>{BinTree<T> left;BinTree<T> right;T val;... // outros métodos: insert, delete, lookup
public Iterator<T> iterator(){return new TreeIterator(this);
}private class TreeIterator implements Iterator<T> {
private Stack<BinTree<T>> s = new Stack<BinTree<T>>();TreeIterator(BinTree<T> n) {
if (n.val != null) s.push(n);}public boolean hasNext() {
return !s.empty();}public T next() {
if (!hasNext()) throw new NoSuchElementException;BinTree<T> n = s.pop();if (n.right != null) s.push(n.right);if (n.left != null) s.push(n.left);return n.val;
}public void remove() {
throw new UnsuppertedOperationException();}
}}
Iterando sem Iteradores
bin_tree *my_tree;tree_iter ti;...for (ti_create(my_tree, &ti); !ti_done(ti); ti_next(&ti)){bin_tree *n = ti_val(ti);...
}ti_delete(&ti);
Iteração Controlada Logicamente
Verificação de uma condição de parada lógica
Duas opções:
teste no início
teste no fim
Recursão
Função em função dela mesmo
Não requer sintaxe extra
Qualquer algoritmo iterativo pode ser reescrito recursivamente
Iteração x Recursão
Iteração -> linguagens imperativas
Recursão -> linguagens recursivas
Exemplo
X
1i10
f(i)
typedef int (*int_func) (int);int summation (int_func f, int low, int high) {
int total = 0;int i;for (i = low; i <= high; i++) {
total += f(i);}return total;
}
typedef int (*int_func) (int);int summation (int_func f, int low, int high) {
if (low == high) return f(low);else return f(low) + summation(f, low+1, high);
}
Exemplo
gcd(a, b) =
8<
:
a , if a = bgcd(a� b, b) , if a > bgcd(a, b� a) , if b > a
int gcd(int a, int b){if (a==b) return a;else if (a > b) return gcd(a-b, b);else return (a, b-a);
}
int gcd(int a, int b){while (a != b) {
if (a > b) a = a-b;else b = b-a;
}return a;
}
Tail Recursion
Geração de código recursivo eficiente
Nenhuma computação é realizada após chamada recursiva
Compilador consegue otimizar código:
Reuso de espaço em memória
Exemplo
int gcd(int a, int b){start:
if (a==b) return a;else if (a > b){
a = a-b; goto start;}else {
b = b-a; goto start;}
}
Exemplo
(define summation (lambda (f low high)(if (= low high)
(f low) ; “then” “then”
(+ (f low) (summation f (+ low 1) high))))) ; “else”
Lisp
Pensando Recursivamente
define fib (lambda (n)(cond ((= n 0) 1)
((= n 1) 1)(#t (+ (fib (- n 1)) (fib (- n 2)))))))
Scheme
Problema: tempo exponencial!
Pensando Recursivamente
(define fib (lambda (n)(letrec ((fib-helper (lambda (f1 f2 i)
if (= i n)f2(fib-helper f2 (+ f1 f2) (+ i 1)))))
(fib-helper 0 1 0)))
Lisp
Ordem de Avaliação:Aplicativa e Normal
Até agora, argumentos são avaliados antes de serem passados para uma função
Alternativa:
Passar argumentos “não-avaliados”
Só avaliar se for necessário
Avaliar antes: ordem aplicativa
Avaliar depois: ordem normal
Ordem de Avaliação:Aplicativa e Normal
Ordem aplicativa: mais fácil de entender
Ordem normal: pode gerar código mais rápido
“Lazy evaluation”
Implementação:
promessas: argumentos não avaliados
Sintaxe: informar quais argumentos são “lazy”
Exemplo
(define naturals(letrec ((next (lambda (n) (cons n (delay (next (+ n 1)))))))
(next 1)))(define head car)(define tail (lambda (stream) (force (cdr stream))))
(head naturals) => 1(head (tail naturals)) => 2(head (tail (tails naturals))) => 3
Tipos de Dados
Introdução
Funções de tipos:
contexto para operações
limites semânticos para operações
Sistema de TiposMecanismo para definir tipos e associá-los a construções da linguagem
Conjunto de regras para:
equivalência:
quando dois valores de tipos diferentes são iguais
compatibilidade
quando valores de um tipo podem ser utilizados
inferência
tipo do resultado de uma expressão com base nos seus tipos constituintes
Verificação de TipoProcesso
Verificação: programa obedece as regras de compatibilidade de tipo?
Linguagens:
fortemente tipadas: proíbem uso de uma operação em um objeto que não é permitido por ela
estaticamente tipadas:
fortemente tipada + verificação durante compilação
PolimorfismoMesmo código - diferentes tipos
Pode (ou não) implicar verificações de tempo de execução
Sistema de tipo dinâmico:
tipo é implícito
polimorfismo paramétrico implícito
verificação em tempo de execução
Outros tipos de polimorfismo:
pode ser verificado durante tempo de compilação
Significado de TipoDenotacional
tipo é um conjunto de valores
Construtivo
tipo é pode ser um tipo básico ou um tipo composto
Baseado em abstração
tipo é uma interface para um conjunto de operações
Denotacional
Conjunto de valores: domínio => tipos
Significado de uma expressão:
valor de um domínio - define o tipo da expressão
Tudo possui tipo
Representação através de operações sobre conjuntos
Classificação de Tipos
Classificação varia de linguagem para linguagem
Classificação mais usual:
caracteres
binários
inteiros
reais
Tipos Numéricos
Diferentes comprimentos (C, Fortran)
C# e Java: tipos numéricos com precisão definida
Com ou sem sinal (C, C++, C#)
Número complexo (Fortran, C99, biblioteca)
Número racionais (Scheme e Lisp)
Linguagem scripts: inteiros com precisão arbitrária
Tipos DecimaisRepresentação BCD
Auxiliam no arredondamento de operações
Cobol, PL/I
Arquitetura CISC: BCD “nativo”
IEEE 754 (ponto flutuante):
decimais com ponto flutuante de até 128 bits
Motivação: comércio on-line
Tipos Discretos
Binários (booleanos)
Inteiros
Caracters
Possuem: antecessor e sucessor
Enumerações
Conjunto de nomes
Normalmente ordenados
Equivalente a definir constantes
Em C: equivalente
Em Pascal: tipo próprio
Sequência
Tipo cujos valores definem uma sequência de valores de um tipo
Pascal: type test_score = 0..100;
Pascal: tipo derivado (não é inteiro)
Tipos Compostos
Records ou Structures
Varitant Records ou Union
Array
Sets
Lists
Files
Ortogonalidade
Ortogonalidade -> todo statement é expressão
Tipo que representa ausência de retorno
“Void”
Verificação de Tipo
Linguagens estaticamente tipadas:
definição do tipo de todos objetos
A seguir:
Equivalência de tipo
Compatibilidade de tipo
Inferência de tipo
Equivalência de TipoEstrutural:
dois tipos são iguais se possuem os mesmos componentes
Algol, Modula-3, C (±), ML
de Nome:
cada definição introduz um novo tipo
Java, C#, Pascal
Exemplo
type R2 = recorda, b : integer;
end;
type R3 = recorda: integer; b : integer;
end;
type R4 = recordb: integer; a : integer;
end;
type str = array [1..10] of char
type str = array [0..9] of char
Equivalência Estrutural
Definição do tipo é expandida até:
ser uma string contendo apenas nomes de campos e tipos padrões
Se duas strings forem iguais: mesmo tipo
Baixo nível
Exemplo
type student = recordname, address: stringage : integer
type school = recordname, address: stringage: integer
x : student;y : school;...x := y;
Variações de Equivalência por Nome
new_type -> alias
Mesmo tipo ou tipos diferentes?
TYPE new_type = old_type;
Variações de Equivalência por Nome
alias precisam ser do mesmo tipo!
TYPE stack_element = INTEGER;MODULE stack;IMPORT stack_element;EXPORT push, pop;...PROCEDURE push(elem : stack_element);...PROCEDURE pop() : stack_element;
Variações de Equivalência por Nome
alias deveriam representar tipos diferentes.
TYPE celsius_temp = REAL; fahrenheit_temp = REAL;VAR c : celsius_temp; f : fahrenheit_temp;...f := c;
Variações de Equivalência por NomeEquivalência estrita por nome:
alias são tipos distintos
Equivalência relaxada por nome
alias são o mesmo tipo
Ada: duas formas
subtipo ou derivado
Exemplo
subtype stack_element is integer;...type celsius_temp is new integer;type fahrenheit_temp is new integer;
Conversão de Tipos e “Casts”
a := expression ou a+b
dois lados precisam ter o mesmo tipo
Se os tipos precisam ser exatamente os mesmos
conversão explícita: type cast
Conversão pode ou não ser feita durante execução do programa:
Equivalência por nome de tipos com mesma estrutura: compilação
Tipos representam mesmo conjunto de valores mas com limites distintos: execução
Tipos compostos de tipos básicos que podem ser convertidos: execução
Conversão de Tipos e “Casts”
Exemplo
n : integer; -- 32 bitsr : real; -- precisão duplat : test_score; -- como no exemploc : celsius_temp; -- como no exemplo...t := test_score(n); -- run-time checkn := integer(t); -- sem checkr := real(n); -- conversão run-timen := integer(c); -- sem checkc := celsiur_temp(n); -- sem check
Type Casts Sem Conversão
Re-interpretação dos bits
Não muda o valor da memória
Exemplo: alocação de memória
C++:
reinterpret_cast<tipo>
Compatibilidade
Equivalência nem sempre é necessária
Compatibilidade entre tipos, é
Exemplo: a+b
a e b tem que ser de tipos compatíveis com tipos que permitem soma
Regras mudam de linguagem para linguagem
Coerção
Mudança implícita do tipo de uma variável
Similar a conversão: pode requerer código em tempo de execução
Exemplo
type weekday = (sun, mon, ...);subtype workday is weekday range mon..fri;d : weekday; k : workday; type calendar column is new weekday; c : calendar_column;...k := d; -- run-time checkd := k; -- sem checkc := d; -- erro
Coerção
Confuso: tipos são misturados sem comando explícito por parte do programador
Exemplo: C short int s;unsigned long int l;char c;float f;double d;
s = l;l = s;s = c;f = l;d = f;f = d;
Sobrecarga e CoerçãoSobrecarga ≠ coerção
a + b: “+” soma de inteiros ou reais
Sem coerção: “a” e “b” tem que ser do mesmo tipo
Com coerção:
“a” ou “b” reais: soma de números reais
“a” e “b” inteiros: soma de número inteiros
Mistura: uma das variáveis é convertida
Referências Universais
Referências a qualquer tipo
C/C++: void *
l-value de qualquer tipo pode ser atribuído a referêcia
Nenhuma operação pode ser realizada sobre uma referência universal
De-referência: como garantir tipo?
Type Tags
Tag: objeto guarda o seu tipo
C++: dynamic_cast
Exemplo
import java.util.*;...Stack my_stack = new Stack();String s = “Oi.”;Foo f = new Foo(); ...myStack.push(s);myStack.pop(f);...s = (String) myStack.pop();
Erro durante execução caso topo da pilha não seja do tipo string
Inferência de Tipos
Como determinar o tipo de uma expressão?
Para operações aritméticas e lógicas: fácil
Para sequências e objetos compostos: não
Sequência
Qual o tipo do resultado de a+b?
Pascal: tipo que forma a sequência
Atribuição em sequências:
verificação em tempo de execução
type Atype = 0..20; Btype = 10..20;var a : Atype; b : Btype;
Tipos Compostos
Sobrecarga de operadores
a + b, “a” e “b” structs
resultado pode não ser o mesmo struct
Regras variam de linguagem em linguagem
e de tipo composto para tipo composto
Records (Structs)
Armazenamento de dados heterogêneos
Normalmente: definem um tipo
Records (Structs)
struct element {char name[2];int atomic_number;double atomic_weight;_Bool metallic;
}
type two_chars = array [1..2] of char;
type element = recordname : two_chars;atomic_number : integer;atomic_weight : real;metalic : boolean;
end;
Cada parte do record: campo
Acesso ao campo: “.”
Podem ser aninhadas
Utilização de Memória
Campos em posições adjacentes de memória
Offset para cada campo é armazenado pelo compilador
4 bytes / 32 bits4 bytes / 32 bits4 bytes / 32 bitsnamename
atomic_numberatomic_numberatomic_weightatomic_weight
metallic
Utilização de Memória
Records aninhados:
Modelo por valor: cópia do record aninhado
Modelo por referência: cópia da referência
Exemplo
typeT = record
j : integer;end;S = record
i : integer;n : T;
end;
var s1, s2 : S;...s1.n.j := 0;s2 := s1;s2.n.j := 7;writeln(s1.n.j); (* 0 *)
class T {public int j;
}class S {
public int i;public T n;
}...S s1 = new S();s1.n = new T();S s2 = s1;s2.n.j = 7;System.out.println(s1.n.j); // 7
Pascal Java
Packed Record
Compilador procura otimizar o espaço
Faz com que o tempo de acesso aumente
4 bytes / 32 bits4 bytes / 32 bits4 bytes / 32 bits
name atomic_
_number
atomic_weightatomic_weight
metallic
Atribuição e Comparação
Atribuição em uma única operação
Poucas linguagens: comparação
Cópia e comparação:
record pequeno: campo a campo
record grande: biblioteca
Problema: espaços vazios no record
Minimizando Espaços Vazios
Ordenamento dos arranjos por tamanho dos campos
Feito pelo compilador
4 bytes / 32 bits4 bytes / 32 bits4 bytes / 32 bits
name metallic
atomic_numberatomic_number
atomic_weightatomic_weight
with Statement
ruby.chemical_composition.elements[1].name := ‘Al’;ruby.chemical_composition.elements[1].atomic_number := ’13’;ruby.chemical_composition.atomic_weight := 26.98154;ruby.chemical_composition.elements[1].metallic := true;
with ruby.chemical_composition.elements[1] do beginname := ‘Al’;atomic_number := 13;atomic_weight := 26.98154;metallic := true;
end;
Variant Record (Union)Duas variáveis compartilhando a mesma memória
Necessário quando há restrição de memória
Tamanho da maior variável
Utilizações:
Interpretação da memória de mais de uma forma
Campo mutável de estrutura
union {int i;double d;_Bool d;
}
Arrays
Tipo mais comum de dados compostos
Tipo composto homogêneo
Semanticamente: mapeamento índices/elemento
Índice:
tipo discreto: array convencional
tipo não-discreto: dicionário ou mapa
Sintaxe e Operação
Elemento: nome do array + operador [] ou ()
Declaração:
char upper[26];
character, dimension (1:26) :: uppercharacter (26) upper
var upper : array [‘a’..‘z’] of char
upper : array (character range ‘a’.. ‘z’) of character
C
Fortran
Pascal
Ada
Slices
Slice: pedaço do array
Perl, Python, Ruby e R
Fortran
matrix(3:6, 4:7) matrix(6:, 5) matrix(:4, 2:8:2) matrix(:, (/2, 5, 9/))
Operações
Seleção de elemento: operação mais comum:
Comparação: menos comum (Ada, Fortran 90)
Fortran 90:
Operações aritméticas com slices
Operações elemento a elemento
Dimensões, Limites e Alocação
Tamanho conhecido: alocação no stack
Tamanho desconhecido:
alocação no heap ou no stack
informação do tamanho
Linguagens interpretadas: dimensões e tamanho dinâmico
Linguagens compiladas: tamanho dinâmico
Dope VectorsCompilação:
Tabela: dimensão e limites para cada array
Dimensão e limites estáticos: olhar tabela
Dimensão e limites dinâmicos:
Código para busca em tempo de execução no dope vector
Dope vector:
limites, dimensão e tamanho do array
atualizado em tempo de elaboração
Alocação no Stack
Parâmetros de função: array dinâmico mais simples
Pascal
Chamada da função: passagem do Dope Vector
function DotProduct(A, B:array [lower..upper:integer] of real):real;var i : integer;
rtn : real;begin
rtn := 0;for i := lower to upper do rtn := rtn + A[i]*B[i];DotProduct := rtn
end;
Exemplovoid square(int n, double M[n][n]) {
double T[n][n];for (int i = 0; i < n; i++){
double s = 0;for (int k = 0; k < n; k++) {
double s = j;for (int k = 0; k < n; k++) {
s += M[i][k] * M[k][j];}T[i][j] = s;
}}for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {M[i][j] = T[i][j];
}}
}
Alocação no Heap
Arrays verdadeiramente dinâmicos
Mudam de tamanho durante a execução
Alocação no heap
Linguagens: scripts, Java e C#
Exemplo Java:
String s = “string”;...s = s + “ longa”;
Layout na Memória
Array unidimensional: contíguo
Array multidimensional:
coluna ou linha
Útil saber: otimização do código
for (i = 0; i < N; i++) {for (j = 0; j < N; j++) {
... A[i][j] ...}
}
Row-Pointer Layout
Memória não-contígua
Vetor de ponteiros para linhas
Vantagem: linhas de tamanhos diferentes
Desvantagem: mais lento (maioria das vezes)
Exemplo
char days[][10] = {“Sunday”, “Monday”, “Tuesday”, “Wednesday”,“Thursday”, “Friday”,“Saturday”
}...days[2][3] == ‘s’;
char *days[] = {“Sunday”, “Monday”, “Tuesday”, “Wednesday”,“Thursday”, “Friday”,“Saturday”
}...days[2][3] == ‘s’;
Cálculo de Endereço
Layout contíguo:
como descobrir endereço de um elemento?
A : array[L1..U1] of array[L2..U2] of array[L3..U3] of elem_type;
S3 = tamanho de elem_typeS2 = (U3 - L3 + 1) * S3S1 = (U2 - L2 +1) * S2
A[i,j,k]:endereço de A + (i-L1)*S1 + (j-L2)*S2 + (k-L3)*S3
Forma eficiente:(i*S1)+(j*S2)+(k*S3)+endereço de A-[(L1*S1)+(L2*S2)+(L3*S3)]
String
Vetor de caracteres
Operações limitadas
Tipo próprio
Mais operações
Conjuntos
Coleção homogênea não-ordenada
Operações próprias:
pertence / não pertence
união / intercessão / diferença
Implementação:
arrays, Hash tables e árvores
Ponteiros e Tipos Recursivos
Tipo recursivo: possui referência para ele mesmo
Quase sempre: records
Dados encadeados
Modelo de referência: fácil criar tipos recursivos
Modelo de valor: ponteiros
Ponteiros
Variável cujo valor é uma referência
Ponteiro ≠ Endereço
Pascal: apenas objetos no heap
C, C++, Algol, Ada: operador “endereço de”
Sintaxe e OperaçõesOperações com ponteiros:
alocação e de-alocação
de-referência
atribuição
Modelo de valor:
A := B -> cópia do valor ou da referência
Modelo de referência:
A := B -> cópia da referência
Java
Modelo intermediário
Tipos padrão: modelo de valor
Tipos definidos pelo usuário: modelo de referência
Modelo de ReferênciaML
chr_tree:
vazio
nó de uma árvore com 2 referências
datatype chr_tree = empty | node_of_char * chr_tree * chr_tree
Modelo de ReferênciaLisp
Modelo de referência
Não é estaticamente tipada
‘(#\R (#\X () ()) (#\Y (#\Z ()()) (#\W ()())))
Tipos Mutuamente Recursivos
Como resolver no modelo de referência?
Estaticamente tipada:
Construção explícita na linguagem
datatype sym_tab_rec = variable of ...| type of ...| ...| subroutine of {code : syn : syn_tree_node, ...}
and syn_tree_node = expression of ...| loop of ...| ...| subr_call of {subr : sym_tab_rec, ...};
Modelo de Valortype chr_tree_ptr = ^chr_tree;
chr_tree = recordleft, right : chr_tree_ptr;val : char;
end;
type chr_tree;type chr_tree_ptr is access chr_tree;type chr_tree is record
left, right : chr_tree_ptr;val : character;
end record;
struct chr_tree {struct chr_tree *left, *right;char val;
}
Pascal
Ada
C
Alocação
new(my_ptr);
my_ptr := new chr_tree;
my_ptr = new chr_tree(args);
Pascal
Ada
Cmy_ptr = malloc(sizeof(struct chr_tree));
C++, Java e C#
De-referência
my_ptr^.val := ‘X’;
T : chr_tree;P : chr_tree_ptr;...T.val := ‘X’;P.val := ‘Y’;
my_ptr->val = ‘X’;
Pascal
Ada
C
Explícita:
Implícita:
Removendo Objetos
Alocação no Heap:
remoção de objetos não utilizados
Duas opções: remoção explícita
dispose(my_ptr);
delete my_ptr;
Pascal
Cfree(my_ptr);
C++
Referências Solta
Ponteiro que não aponta para um objeto válido
Ex.: ponteiro para variável local
int i = 3;int *p = &i;...void foo(){int n = 5; p = &n};...cout << *p;foo()’...cout << *p;
int *p = new int;*p = 3;...cout << *p;delete p;...cout << *p;
Coletor de Lixo
Gerenciamento de memória:
Custoso para o programador
Fonte de erros
Coletor de lixo:
Recupera memória automaticamente
Como funciona?
Contagem de Referência
Quando que um objeto na memória pode ser removido?
Quando não há nenhuma referência para ele
Contagem de referência:
Objeto é criado: contagem = 1
Novo ponteiro: contagem é incrementada
Ponteiro removido: contagem é decrementada
Contagem = 0 -> objeto é removido
Contagem de ReferênciaImplementação:
Necessário saber a localização de cada ponteiro
Descritores de tipo:
Tabela com tipos e onde ponteiros podem ser encontrados dentro de cada tipo
Problema:
Objetos sem referência -> inúteis
Objetos inúteis -> sem referência ?
“Tracing Collection”
Objeto útil:
Pode ser encontrado seguindo uma sequência de ponteiros, começando com um objeto que está no stack
Funcionamento:
busca recursiva no heap
“Mark-and-Sweep”Algoritmo clássico
Executado quando espaço no heap fica abaixo de um limiar
Três passos:
Coletor passa por todos objetos do heap, marcando todos os objetos como inúteis
Começando com ponteiros fora do heap, o coletor recursivamente explora os dados encadeados. Cada objeto encontrado é marcado como “útil”
Coletor passa novamente por todos objetos do heap, movendo cada bloco “inútil” para a lista de blocos livres
Informação extra: início e fim de cada objeto no heap
“Pointer Reversal”Exploração do método anterior:
usa muita memória: marcação dos dados
Algoritmo alternativo:
O sentido dos ponteiros da lista encadeada é invertido
Ponteiro do objeto apontado para o objeto que apontava
Objeto atual e anterior são armazenados
Na volta: ponteiros são invertidos novamente
Baixo consumo de memório
1 2
3 4
“Stop-and-Copy”Redução da fragmentação
Evita a busca inicial e final
Divisão do heap em dois blocos de tamanhos iguais
Quando a primeira parte está quase cheia:
Busca por objetos úteis
Cada objeto útil é copiado para a segundo bloco
Ponteiros para esse objeto são redirecionados para o novo bloco
“Generational Collection”Objetos alocados dinâmicamente tendem a ter uma vida curta
Heap é dividido em múltiplas partes -- normalmente duas
Quando o espaço no heap está acabando:
Lixo é coletado da parte mais “nova”
Se espaço recuperado não for suficiente, busca na parte mais “velha”
Objeto na parte “nova” que sobrevive uma busca: vai para parte “velha”
Listas
Definição recursiva
Lista é:
lista vazia
par (objeto, lista)
Linguagens funcionais: muito utilizadas
Linguagens imperativas: disponíveis em scripts
List Comprehensions
Adaptação de notação matemática
[i*i for i in range(1, 100) if i % 2 ==1]
{i⇥ i | i 2 {1, · · · , 100} ^ i mod 2 = 1}
Rotinas e Abstrações de Controle
Introdução
Abstração:
associação nome com pedaço (complicado) de código
Abstração de controle:
objetivo é uma operação bem definida
Principal mecanismo: rotinas (funções e procedimentos)
Rotinas
Realizam uma operação para quem a chama
Chamada da rotina:
transfere o fluxo de controle para a rotina
Maior parte das rotinas: parametrizadas
argumentos alteram o seu funcionamento
Rotinas
Argumentos:
parâmetros verdadeiros
são mapeados nos parâmetros formais durante a chamada da rotina
Função: retorna valor
Procedimento: não retorna valor
O que será visto
O que acontece durante a chamada de uma rotina
Expansão “em linha”
Parâmetros de rotinas
Rotinas genéricas
Manipulação de exceções
“Stack”
Subrotina D
Subrotina C
Subrotina B
Subrotina B
Subrotina A
Argumentospara rotinas
Temporários
Variáveis Locais
Misc.
Endereço de retorno
procedure C
D; E
procedure B
if ... then
B
else
C
procedure A
B
-- main program
A
sp
fp
fp(quando C está
sendo executado)
sp: “stack pointer”, fp: “frame pointer”
Sequência de Chamada
Código executado quando uma rotina é chamada e após a sua execução
Prólogo e epílogo
Responsabilidade: gerenciar o stack
Prólogo
Salva o endereço de retorno
Muda o “sp” e armazenamento em registradores
Alocação de espaço
Atualização do “fp”
Código de inicialização de objetos
Epílogo
Retorno de parâmetros
Código de finalização de objetos
Remoção da memória alocada
Recuperação dos registradores
Sequência Típica
Chamada:
salva os registradores que serão utilizados após o retorno
calcula os valores dos argumentos
pula para a rotina passando o endereço de retorno
Argumentospara rotinas chamadas
Temporários
Variáveis Locais
Registradores Salvos
fp salvo
Endereço de retorno
Argumentospara rotinas
sp
fp
Qua
dro
atua
lQua
dro
ante
rior
Sequência Típica
Prólogo:
aloca memória para o quadro
salva o antigo “fp” no stack e atribui um novo valor para ele
salva os registradores que serão sobrescritos
Argumentospara rotinas chamadas
Temporários
Variáveis Locais
Registradores Salvos
fp salvo
Endereço de retorno
Argumentospara rotinas
sp
fp
Qua
dro
atua
lQua
dro
ante
rior
Sequência Típica
Epílogo:
move os valores de retorno para o local adequado
recupera registradores salvos
recupera “fp” e “sp”
pula para o endereço de retorno
Argumentospara rotinas chamadas
Temporários
Variáveis Locais
Registradores Salvos
fp salvo
Endereço de retorno
Argumentospara rotinas
sp
fp
Qua
dro
atua
lQua
dro
ante
rior
Expansão “Em linha”
Na chamada: cópia do código da rotina
Não ocorre a sequência de chamada
Permite otimizações do compilador
Exemplo (C++ e C99):
Sugestão para o compilador
Problemas: tamanho do código e recursão
inline int max(int a, int b) {return a > b ? a : b;}
Passagem de Parâmetros
Parâmetros:
alteram o comportamento da rotina
fornecem dados
Parâmetros na declaração: parâmetros formais
Argumentos passados: parâmetros reais
A seguir: formas de passagem de parâmetros
Modos de Passagens de Parâmetros
Rotina “p” e parâmetro “x”
p(x);
Duas implementações alternativas:
copiar o valor de “x”
fornecer o endereço de “x”
Modos:
passagem por valor
passagem por referência
Exemplo
x : integer -- globalprocedure foo(y : integer)
y := 3print x
...x := 2foo(x)print x
Passagem por Valor / Retorno
Passagem por referência: modificar a variável
Mesmo comportamento:
chamada por valor/retorno
Valor é copiado na entrada da função
E copiado de volta no retorno da função
Exemplo
x : integer -- globalprocedure foo(y : integer)
y := 3print x
...x := 2foo(x)print x
C
Apenas: passagem por valor
Emulando passagem por referência:
passagem direta do endereço (ponteiros)
Exemplo: void swap(int *a, int *b) {int t = *a;*a = *b;*b = t;
}...int v1, v2;...swap(&v1, &v2);
Passagem por Compartilhamento
Linguagens com modelo por referência
Nem por valor, nem por referência
Só existem referências
Cópia de referência = referência !
Passagem por compartilhamento:
“Cópia da referência”
Altera o valor, mas não a identidade
JavaPassagem por valor:
tipos padrão
Passagem por compartilhamento:
tipos definidos pelo usuário
Consequência:
tipos padrões não podem ser alterados durante rotina
Valor x Referência
Passagem por valor:
assegura que o valor não é modificado
Passagem por referência:
permite modificação do argumento
menor custo computacional
leva a bugs -> confusão semântica
Parâmetros Apenas de Leitura
Combinação:
eficiência computacional de passagem por referência
segurança de passagem por valor
Parâmetro apenas de leitura:
só pode aparecer do lado direito de expressões
Exemplo C
void append_to_log(const huge_record *r) {......append_to_log(&my_log);
O const vale para o valor apontado por r
Exemplo: Ada
Três modos de passagem de parâmetros:
“in”: apenas de leitura
“out”: apenas de escrita
“in out”: escrita e leitura
Referências em C++
Passagem por referência:
Podem ser apenas de leitura: const
Implementação:
passagem do endereço
não podem ser de-referenciados!
void swap(int &a, int &b){int t = a; a = b; b = t;}
Retornando ReferênciasÚtil para operadores
Sem retorno de referência:
cout << a << b << c;
((cout.operator<<(a)).operator<<(b)).operator<<(c);
=
*(*(cout << a) << b) << c;
Fechamentos como Parâmetros
Fechamentos:
rotina + contexto
Podem ser passados como parâmetros
Exemploprocedure apply_to_A(function f(n : integer) : integer;
var A : array[low..high:integer] of integer);var i : integer;begin
for i := low to high do A[i] := f(A[i]);end;...
var k : integer (* escopo aninhado *)...function add_k(m : integer) : integer;begin
add_k := m + k;end;...k := 3;apply_to_A(add_k, my_array);
ResumoModo Linguagens Implementação Operações Muda “real”? Alias?
valor C/C++, Pascal, Java/C# valor leitura, escrita não não
in, const Ada, C/C++, Modula-3
valor ou referência leitura não talvez
out Ada valor ou referência escrita sim talvez
value/result AlgolW valor leitura, escrita sim não
var, ref Fortran, Pascal, C++ referência leitura, escrita sim sim
copartilhamentoLisp/Scheme, ML, Java/C#
valor ou referência leitura, escrita sim sim
in out Ada valor ou referência leitura, escrita sim talvez
Passagem de Arrays
Tempo de união da dimensão e limites
Execução: aberto ou “conformant”
Parâmetros Default
Parâmetro opcional
Se o parâmetro estiver faltando:
valor padrão é utilizado
Exemplo (Ada):type filed is integer range 1..integer’last;type number_base is integer range 2..16;default_width : field := integer’width;default_base : number_base := 10;procedure put(item : in integer; width : in field := default_width; base : in number_base := default_base);
Parâmetros Nomeados
Até agora: parâmetros posicionais
1o parâmetro real = 1o parâmetro formal
Alternativa: parâmetros nomeados
Chamada da função com o nome formal do parâmetro explícito
Parâmetros Nomeados
put(item => 37, base => 8);
put(base => 8, item => 37);
put(37, base => 8);
Exemplo
Parâmetros nomeados como documentação
format_page(columns => 2,window_height => 400, window_width => 200,header_font => Helvetica, body_font => Times,title_font => Times_Bold, header_point_size => 10,body_point_size => 11, title_point_size => 13,justification => true, hyphenation => false,page_num => 3, paragraph_indent => 18,background_color => white);
Número Variável de Argumentos
Número de argumentos indeterminado
Exemplo: printf e scanf
Recurso pouco comum: C/C++, Python, Lisp
Exemplo
#include <stdarg.h> /* definição de va_list, va_start, ... */int printf(char *format, ...){
va_list args;va_start(args, format);...
char c = va_arg(args, char);...double d = va_arg(args, double);
...va_end(args);
}
ExemploJava/C#: parâmetros ocultos do mesmo tipo
static void print_lines(String foo, String... lines) {System.out.println(“First argument is \””+ foo “\”.”);System.out.println(“There are “ +
lines.length+”additional arguments:”);for (String str: lines){
System.out.println(str);}
}...print_lines(“Hello, World.”, “Depois ”, “dos três pontos”);
First argument is “Hello, World”.There are 2 additional arguments:Depoisdos três pontos
Retorno de Funções
Como denotar o retorno da função
Sintaxe varia de linguagem para linguagem
Pascal, Fortran: atribuição a uma variável com nome igual ao da função
Solução mais moderna: “return”
Exemplo
Matlab: retorno nomeado e múltiplo
function [A, B, C] = foo()
A = 1;B = 2;C = 3;
Módulos e RotinasGenéricas
Parâmetros:
Mudança do comportamento
Dados
Operações: podem não depender do tipo
Exemplo: operações sobre fila
Módulos e RotinasGenéricas
Polimorfismo paramétrico explícito:
Rotinas genéricas
Conjunto de rotinas similares:
especialização do tipo
Ada, C++, Java, C#
Containers
Estrutura de dado
Armazenam outros dados
Exemplo: stack, queue, conjuntos, dicicionários
Tipo: genérico
Ada e C++
ExemploC++
template <class item, int max_items = 100>class queue {
item items[max_items];int next_free;int next_full;
public:queue(){ next_free = next_full = 0;}void enqueue(item it) {
items[next_free] = it;next_free = (next_free + 1) % max_items;
}item dequeue() {
item rtn = items[next_full];next_full = (next_full + 1) % max_items;return rtn;
}};
queue<int, 50> int_queue;queue<float> float_queue;
Parâmetros Genéricos
Quais parâmetros podem ser genéricos?
Ada e C++: tipos comuns, rotinas e classes
Java e C#: apenas tipos comuns
Implementação
Compilador: cópia em cada implementação
Se possível: código compartilhado
Java: sempre compartilha código
Ada e C++: similar a macro
Verificação de tipo
Inserido no contexto da linguagem
Limitações de Parâmetros Genéricos
Interface de uma função genérica:
informações de como utilizá-la
Ada, Java e C#:
operações permitidas sobre parâmetro genérico devem ser explicitadas
Exemplo
generic type T is private;with function “<“(x, y : T) return Boolean;
function min(x, y : T) return T isbegin
if x < y then return x;else return y;end if;
end min;
function string_min is new min(string, “<“);function date_min is new min(date, date precedes);
Ada
Exemplo
public static <T extends Comparable<T>> void sort(T A[]) {...if (A[i].compareTo(A[j]) >= 0) ......
}...Integer[] myArray = new Integer[50];...sort(myArray);
Java
Exemplo
static void sort<T>(T[] A) where T : IComparable {...if (A[i].CompareTo(A[j]) >= 0) ......
}...int[] myArray = new int[50];sort(myArray);
C#
Exemplo
template<class T>void sort(T A[], int A_size) { ...
C++
Instanciação
Ada: instanciação explícita
C++: instanciação implícita
procedure int_sort is new sort(integer, int_array, “<“);
int ints[10];double reals[50];string strings[30];
sort(ints, 10);sort(reals, 50);sort(strings, 30);
ExceçõesErro na execução de uma rotina
Como sinalizar o problema?
Inventar um valor que sinaliza o problema
Retornar um “status” para quem chama a rotina
Receber uma função que lida com possíveis erros
Exceção: solução apropriada
ExceçõesPermitem:
definição do fluxo normal do código
caso tenha problema, fluxo é redirecionado
Parte do código que lida com o erro:
Nome: manipulador (“handler”)
assume o controle da rotina assim que o erro acontece
Exemplo
try {...if (algo_inesperado)
throw erro();...cout << “tudo ok” << endl;...
} catch (erro) {cout << “problema!” << endl;
}
Exemplo
try {...foo();...cout << “tudo ok” << endl;...
} catch (erro) {cout << “problema!” << endl;
}
foo() {...if (algo_inesperado)
throw erro();...
}
“Handlers”
Três possíveis tarefas:
corrigir o erro, de forma que o programa possa continuar operando
Erro “out of memory” -> alocar mais memória
se o erro não pode ser corrigido localmente: limpar lixo e fornecer exceção novamente
se nada puder ser feito: exibir mensagem de erro na tela
Definindo Exceções
Linguagem :
Erros semânticos dinâmicos
Programador:
Pode definir exceções específicas
Exceções pré-definidas:
overflow, end-of-file, out-of-range, divisão por zero
Exemplo
Ada: exceção é um tipo padrão
Linguagens OO: classes
declare empty_queue : exception;
class duplicate_in_set {item dup;
};...throw duplicate_in_set(d);
Propagação de Exceções
try { // Tenta ler do arquivo...// Código complicado de leitura...
} catch(end_of_file) {...
} catch(io_error e) {...
} catch(...) {...
}
Operações de Limpeza
Código que é executado sempre
caso a saída seja normal ou com exceção
Modula-3, Python, Java e C#
TRYmyStream := OpenRead(myFileName);
FINALLYClose(myStream);
END;
Emulando Exceções
Forma mais comum: goto
C: rotinas da biblioteca padrão
setjmp: salva num buffer o estado atual do programa
retorno: “normal” = 0, “de um longjmp” ≠ 0
longjmp: restaura o estado do programa a partir de um buffer
Exemplo
if (!setjmp(buffer)) {/* código protegido */
} else {/* handler */
}
Abstração de Dados e Orientação a Objetos
IntroduçãoMódulos:
coleção de rotinas e variáveis estáticas
encapsulamento e ocultação de informação
Módulos como tipos:
módulos que podem ter várias cópias
Classes:
módulo como tipos + herança
CONST stack_size = ...TYPE element = ......MODULE stack_manager;IMPORT element, stack_size;EXPORT stack, init_stack, push, pop;TYPE
stack_index = [1..stack_size];stack = RECORD
s : ARRAY stack_index OF element;top : stack_index;
END;
PROCEDURE init_stack(VAR stk : stack);BEGIN
stk.top := 1;END init_stack;
PROCEDURE push (VAR stk : stack, elem : element);BEGIN
IF stk.top = stack_size THENerror;
ELSEstk.s[stk.top] := elem;stk.top := stk.top + 1;
END;END push;
PROCEDURE pop (VAR stk : stack) : element;BEGIN
IF stk.top = stack_size THENerror;
ELSEstk.top := stk.top - 1;RETURN stk.s[stk.top];
END;END pop;
END stack_manager;
VAR A, B : stack;var x, y : element;...init_stack(A);init_stack(B);...push(A, x);...y := pop(B);
Exemplo: Módulo
Exemplo: Módulo como Tipoconst stack_size = ...type element = ......type stack = module
imports (element, stack_size)exports (push, pop)
type stack_index = 1..stack_size;
vars : array stack_index of elementtop : stack_index
procedure push(elem : element) = ...function pop returns element = ......initially
top := 1end stack
VAR A, B : stack;var x, y : element;...A.push(x)...y := B.pop
Introdução
Módulo: gerentes
Módulo exporta um tipo abstrato
Módulo é inicializado e finalizado
Módulo como tipo e classes:
O próprio módulo é a abstração
Instância do módulo é criada e finalizada
Introdução
Classe:
Herança: novas abstrações criadas a partir de abstrações que já existem
união dinâmica de métodos: nova abstração pode ser usada em contextos que esperavam a abstração antiga
Instância da classe = objeto
Introdução
Encapsulamento, herança e união dinâmica:
Simula (60s)
Melhorias sobre encapsulamento:
Clu, Modula, Euclid (70s)
Melhorias sobre herança e união dinâmica:
Smalltalk (70s)
Introdução
Linguagens OO modernas:
Eiffel, C++, Modula-3, Ada 95, Fortran 2003, Python, Ruby, Java e C#
Objective-C:
Mensagens de Smalltalk + C
O que será visto:
Encapsulamento e ocultação de informação
Inicialização e finalização
União dinâmica de métodos
Herança múltipla
Linguagens verdadeiramente orientada a objetos
Programação OOEvolução dos programas:
necessidade de ocultação de informação
abstração de dados
Benefícios:
Reduz conceitos que o programados tem que aprender
Contingência de erros
Aumenta independência entre partes do programa
Programação OO
Na prática: re-uso do código é complicado
Classe precisa ser “levemente” modificada
Ex.: FIFO para deque
Herança:
permite estender classes já criadas
ou refinar
Exemploclass list_err { // exceçãopublic:
char *description;list_err(char *s){description = s;}
};
class list_node {list_node* prev;list_node* next;list_node* head_node;
public:int val;class list_node() {
prev = next = head_node = this;val = 0;
}
list_node* predecessor() {if (prev == this || prev == head_node)
return 0;return prev;
}
list_node* successor() {if (next == this || next == head_node)
return 0;return next;
}
bool singleton() {return (prev == this);
}
void insert_before(list_node* new_node) {if(!new_node->singleton())
throw new list_err(“inserção repetida”);prev->next = new_node;new_node->prev = prev;new_node->next = this;prev = new_node;new_node->head_node = head_node;
}
void remove(){if(singleton())
throw new list_err(“nó não existe);prev->next = next;next->prev = prev;prev = next = head_node = this;
}
~list_node() {if(!singleton())
throw new list_err(“nó ainda na lista”);}
};
NomenclaturaVariáveis membros da classe:
Atributos ou campos
prev, next, head_node, val
Rotinas membros da classe:
Métodos
predecessor, successor, insert_before e remove
this: ponteiro para instância que está executando o código
Exemplo
class list{
list_node header;
public:
int empty() {return header.singleton();
}
list_node* head() {return header.successor();
}
void append(list_node *new_node) {header.insert_before(new_node);
}~list() {
if (!header.singleton())throw new list_err(“Lista não vazia”)
}};
ExemploComo criar listas:
Criação: execução do construtor
método com mesmo nome que a classe
Destrução: execução do destrutor
método com nome da classe com “~” na frente
list my_list_ptr;list_node elem;
list* my_list_ptr = new list;list_node* elem_ptr = new list_node;
Stack Heap
Exemploclass list_err { // exceçãopublic:
char *description;list_err(char *s){description = s;}};
class list_node {list_node* prev;list_node* next;list_node* head_node;
public:int val;list node() {
prev = next = head_node = this;val = 0;
}
list_node* predecessor() {if (prev == this || prev == head_node)
return 0;return prev;
}
list_node* successor() {if (next == this || next == head_node)
reuturn 0;return next;
}
bool singleton() {return (prev == this);
}
void insert_before(list_node* new_node) {if(!new_node->singleton())
throw new list_err(“inserção repetida”);prev->next = new_node;new_node->prev = prev;new_node->next = this;prev = new_node;new_node->head_node = head_node;
}
void remove(){if(singleton())
throw new list_err(“nó não existe);prev->next = next;next->prev = prev;prev = next = head_node = this;
}
~list_node() {if(!singleton())
throw new list_err(“nó ainda na lista”);}
};
Membros Públicos e Privados
public:
Tudo que vem depois: visível de fora da classe
Determina quais membros serão visíveis para quem usa a classe (interface)
private:
Membros visíveis apenas para a classe
Oculta informação de quem usa a classe
Declaração
class list_node {list node* prev;list node* next;list_node* head_node;
public:int val;list_node();list_node* predecessor();list_node* successor();bool singleton();void insert_before(list_node* new_node);void remove();~list_node();
};
...void list_node::inset_before(list_node* new_node){
...}...
list_node.h
list_node.cpp
Rotinas Curtas
Programas OO:
chamadas para rotinas pequenas
informação é escondida por trás de uma chamada
Boa prática:
atributos sempre privados
métodos: get e set para modificá-los
Propriedades
Propriedades:
membros com métodos “set” e “get” próprios
Accessors:
métodos que atributem e lêem valores de atributos
Python e C#
Exemplo
class list_node {...int val; // val é privadopublic int Val {
get {return Val;
}set {
val = value; // value é palavra chave}
}...
}
list_node n;...int a = n.Val; // chama o método getn.Val = 3; // chama o método set
Classes DerivadasJá temos a lista
Queremos uma fila
Solução OO: fila é derivada a partir da lista
fila é (filha ou derivada) de lista
lista é (mãe, base, superclasse) de filha
Classe derivada tem todos os membros da classe base
Exemplo
class queue : public list {public:
void enqueue(list_node* new_node){append(new_node);
}
list_node* dequeue(){if(empty())
throw new list_err(“fila vazia”);list_node* p = head();p->remove();return p;
}};
Classe Base de Propósito Geral
list_node:
valor armazenado tem que ser inteiro
Como fazer uma classe base mais geral?
Exemplo: Ada 95
class gp_list_node {gp_list_node* prev;gp_list_node* next;gp_list_node* head_node;
public:gp_list_node();gp_list_node* predecessor();gp_list_node* successor();bool singleton();void insert_before(gp_list_node* new_node);void remove();~gp_list_node();
};
class int_list_node : public_list_node {public:
int val;int_list_node(){
val = 0;}int_list_node(int v) {
val = v;}
};
Sobrecarga de Construtor
No exemplo: construtor foi sobrecarregado
Pode não receber nenhum argumento:
val inicializado como vazio
Pode receber inteiro:
val inicializado com inteiro fornecido
int_list_node element1; // val = 0int_list_node element2(1); // val = 1int_list_node *e_ptr = new int_list_node(13); // val = 13
Modificando Métodos da Classe Base
Classe derivada pode modificar métodos da classe base
Exemplo:
class int_list_node : public list_node {public:
...void remove() {
if (!singleton()) {prev->next = next;next->prev = prev;prev = next = head_node = this;
}}
};
Exemplo
class int_list_node : public_list_node {public:
...void remove() {
try{gp_list_node::remove();
} catch(list_err) {// não faz nada
}};
Acessando Membros da Classe Base
gp_list_node::remove(); // C++super.remove(); // Javabase.remove(); // C#super remove. // Smalltalk[super remove] // Objective C
Containers/CollectionsAbstração que contêm coleção de objetos
Conjuntos, queues, stacks, dicionários
Várias formas de definir containers:
Exemplos: objetos são derivados do tipo base
Outras soluções:
nós possuem ponteiros para objetos armazenados
lista derivada da classe do objeto derivado
Encapsulamento e Herança
Mecanismos de encapsulamento:
agrupamento de dados e sub-rotinas
classe como gerente
Encapsulamento em Módulos
Ocultação da dados
Módulo: import e export
Tipos opacos:
Módulo exporta o tipo “T”
Resto do programa: só pode passar objetos deste tipo para rotinas definidas no módulo
Encapsulamento em Módulos
Divisão: cabeçalho e implementação
Permite compilação separada
Modula-2:
tudo no cabeçalho é público
tudo na implementação é privado
Ada: cabeçalho dividido em parte pública e privada
Tipo T: opaco
Encapsulamento em Módulos
package foo is -- header...type T is private;...
private...type T is ......
end foo;
Parâmetro “this”
Como o módulo sabe qual a instância que está executando?
Solução inocente:
cópia das rotinas em cada instância
Solução prática:
uma única versão de cada rotina
parâmetro extra oculto: instância
Exemplo
my_stack.push(x); push(my_stack, x);
Falta de Cabeçalhos em Java e C#
C# e Java: não possuem arquivos de cabeçalho
Parte pública: definida no código fonte
Compilador: extrai informação a partir do código
Encapsulamento com Herança
Classe B deriva de A
Membros privados de A são visíveis em B?
Membros públicos de A continuam públicos em B?
Exemplo
class queue : private list {public:
using list::empty;using list::head;void enqueue(gp_list_node* new_node);gp_list_node* dequeue();
};
Queue: método append da classe list não faz sentido
Herança: privada
tudo herdado é privado
C++: Protected
Qualificador de visibilidade
como public e private
O que faz:
Membros protected são visíveis em
métodos da própria classe
métodos de classes derivadas
Regras de Visibilidade: C++
Classe pode limitar a visibilidade de seus membros
membros públicos: visíveis quando a classe está no escopo
membros privados: visíveis apenas nos métodos
membros protegidos: privados + classe derivada
Regras de Visibilidade: C++Classes derivadas podem restringir a visibilidade de membros da classe base, nunca ampliar
Membros privados da classe base: são visíveis apenas na classe base
Membros públicos/protegidos da classe base pública: mantêm a visibilidade
Membros públicos/protegidos da classe base protegida: se tornam protegidos
Membros públicos/protegidos da classe base privada: se tornam privados
Regras de Visibilidade: C++
Classe derivada que limita a visibilidade de membros de classe base protegida/privada pode restaurar visibilidade de membros específicos
Visibilidade em Outras Linguagens
Java e C#: parecido com C++
não existe classe base privada, pública ou protegida
Classes derivadas não podem nem restringir nem ampliar visibilidade
protected em Java: limita visibilidade para classes derivadas dentro do mesmo package
Smalltalk e Objective-C: sem visibilidade, tentativa de executar código em tempo de execução
Python: todos membros são públicos
Aninhamento de Classes
Definição de uma classe dentro da outra
Se “inner” é definida dentro de “outer”
“inner” enxerga os membros privados de “outer”?
Caso sim, de qual instância?
C++ e C#: só membros estáticos são visíveis
Java: todos os membros são visíveis
Cada instância de “inner” pertence a uma instância de “outer”
Exemplo
class Outer {int n;class Inner {
public void bar() {n = 1};}Inner i;Outer() {i = New Inner();}public void foo() {
n = 0;System.out.println(n); // 0i.bar();System.out.println(n); // 1
}}
Extensão de TiposSmalltalk, Objective-C, C++, Java e C#:
linguagens projetadas OO
módulo como tipo: classe fornece encapsulamento e herança
Ada, Fortran 93, Modula-3:
extensões OO de linguagens existentes
módulos: encapsulamento
herança: extensão de estruturas
Exemplo: Ada 95package gp_list is
list_err : exception;type gp_list_node is tagged private;type gp_list_node_ptr is access all gp_list_node;procedure initialize(self : access gp_list_node);function predecessor(self : access gp_list_node) return gp_list_node_ptr;function successor(self : access gp_list_node) return gp_list_node_ptr;function singleton(self : access gp_list_node) return boolean;procedure insert_before(self : access gp_list_node; new_node : access gp_list_node_ptr);procedure remove(self : access gp_list_node);
type list is tagged private;type list_ptr is access all list;procedure initialize(self : access list);procedure finalize(self : acess list);function empty(self : access list) return boolean;function head(self : access list) return gp_list_node_ptr;procedure append(self : access list; new_node : gp_list_node_ptr);
privatetype gp_list_node is tagged record
prev, next, head_node : gp_list_node_ptr;end record;type list is tagged record
header : aliased gp_list_node;end record;
end gp_list;...package body gp_list is
-- definição das rotinasend gp_list;
package gp_list.queue is -- queue é filha de gp_listtype queue is new list with privateprocedure initialize(self : access queue);procedure finalize(self : access queue);procedure enqueue(self : access queue; new_node : gp_list_node_ptr);function dequeue(self : access queue) return gp_list_node_ptr;
privatetype queue is new list with null record; -- sem campos novos
...package body gp_list.queue is
procedure initialize(self : access queue) isbegin
initialize(list_ptr(self));end initialize;
procedure finalize(self : access queue) isbegin
finalize(list_ptr(self));end enqueue;
function dequeue(self : access queue) return gp_list_node_ptr isrtn : gp_list_node_ptr;begin
if empty(list_ptr(self)) thenraise list_err;
end if;rtn := head(list_ptr(self));remove(rtn);return rtn;
end dequeue;end gp_list.queue;
Exemplo
Package child em Ada 95:
parecido com classe derivada
mas gerencia um tipo
Abordagens similar: classes em Python
Extensão sem Herança
O que fazer quando herança não é possível?
Código já existente: não permite herança
C#: “extension methods”
static class AddToString {public static int toInt(this string s) {
return int.Parse(s);}
}
int n = mySring.toInt();
Inicialização e Finalização
Linguagens OO:
inicializam e finalizam objetos
Inicialização: método construtor
Finalização: método destrutor
Inicialização e Finalização
Escolhendo um construtor:
Uma classe pode ter 0 ou mais construtores
Modelo por referência:
Criação explícita de objetos: fácil saber quando construtor é executado
Modelo por valor:
Criação é implícita: objeto criado sem inicialização OU mecanismo para escolher construtor
Inicialização e Finalização
Ordem de execução:
Classe A deriva de Classe B: construtor de B precisa ser chamado antes do construtor de A?
Se Classe A tem um atributo da Classe B: construtor de B precisa ser chamado antes do construtor de A?
C++: sim e sim
Inicialização e Finalização
Destrutores:
Úteis em linguagens que não tem coleta automática de lixo
Facilitam a recuperação de memória alocada
Escolhendo um Construtor
Smalltalk, Eiffel, C++, Java e C#: mais de um construtor por classe
C++, Java e C#:
Todos com o mesmo nome
Diferem no número e tipo dos argumentos
Smalltalk e Eiffel:
Construtores com nomes diferentes
Código deve explicitar o construtor a ser utilizado
Exemplo: Eiffelclass COMPLEXcreation -- define os construtores
new_cartesian, new_polarfeature {ANY} -- público
x, y : REAL
new_cartesian(x_val, y_val : REAL) isdo
x := x_val; y := y_valend
new_polar(rho, theta : REAL) isdo
x := rho * cos(theta)y := rho * sin(theta)
end
feature {NONE} -- privado
end...a, b : COMPLEX!!b.new_cartesian(0, 1)!!a.new_polar(pi/2, 1)
Referências e ValoresSmalltalk, Python, Ruby e Java:
variáveis referenciam objetos
C++, Ada 95:
variáveis são objetos
C#:
class: referência
struct: valor
Construtores em C++
foo b; // chama foo::foo()foo b(10, ‘x’); // chama foo::foo(int, char)
Construtores de Cópia
foo a; // chama foo::foo()bar b; // chama bar::bar()...foo c = a; // chama foo::foo(foo &)foo d = b; // chama foo::foo(bar &)
≠foo a, c, d; // chama foo::foo() três vezesbar b; // chama bar::bar()...c = a; // chama foo::operator=(foo &)d = b; // chama foo::operator=(bar &)
Inicialização e Atribuição
C++: distinção entre atribuição e inicialização
Desempenho:
Chamadas:
foo::foo()
foo::foo(foo &)
foo::~foo()
foo a = b + c;foo t;t = b.operator+(c);foo a = t;=
Exemplo: Eiffel
Todas as variáveis são inicializadas com um valor default
Inclusive atributos de classes
Ordem de Construção
C++: todo objeto deve ser inicializado
Se A deriva de B: B->A
Como passar parâmetros para construtor de B?
class foo : public bar{
foo( foo param ) : bar( bar_param );...
Construção de Atributos
C++:
permite escolha dos valores iniciais dos atributos
list_node() : prev(this), next(this), head_node(this), val(0) {};
Exemplo: C++
class foo : bar {mem1_t member1; // atributo cujo tipo é classe mem1_tmem2_t member2; // atributo cujo tipo é classe mem1_t
}
foo::foo( foo_params ) : bar( bar_args ), member1 ( mem1_args), member2 (mem2_args) {...
}
Uso do construtor de cópia para:
member1 e member2
Exemplo: JavaJava: requer inicialização (como C++)
Sintaxe diferente
Primeira linha do construtor:
Caso não tenha chamada explícita:
compilador insere uma chamada para:
super()
super( args );
Exemplo: Java
Modelo de referência:
atributos que são classes: inicialização para null
Inicialização explícita no construtor
Destrutor
Chamado na ordem inversa do construtor
class name_list_node : public gp_list_node {char *name;
public:name_list_node() {
name = 0;}name_list_node(char *n) {
name = new char[strlen(n)+1];strcpy(name, n);
}~name_list_node(){
if (name != 0) {delete [] name;
}}
}
União Dinâmica de Métodos
Classe D deriva de Classe C
D pode ter todos os membros públicos de C
Tudo que pode ser feito com C...
... pode ser feito com D
Polimorfismo de subtipo
União Dinâmica de Métodos
class person { ...class student : public person { ...class professor : public person { ...
student s;professor p;...person *x = &s;person *y = &p;
class person { ...public:
void print_data();...
}
class student : public person { ...public:
void print_data();...
}
class professor : public person { ...public:
void print_data();...
}student s;professor p;...person *x = &s;person *y = &p;...s.print_data(); // student::print_datap.print_data(); // professor::print_data...x->print_data(); // ??y->print_data(); // ??
União Dinâmica de Métodos
União estática de métodos:
person::print_data()
União dinâmica de métodos:
student::print_data()
professor::print_data()
ConsistênciaUnião dinâmica de métodos:
classe garante consistência
class text_file {char *name;long position;
public:void seek(long where);...
};
class read_ahead_text_file : public text_file {char *upcoming_characters;
public:void seek(long where); //redefinição...
};
Se read_ahead_text_file::seek não for executado:
upcoming_files poderá ficar insistente
União Dinâmica de Métodos
União dinâmica para todos os métodos:
Smalltalk, Objective-C, Python e Ruby
União dinâmica é padrão, mas pode ser alterado
Java e Eiffel
União estática padrão/ União dinâmica opcional
Simula, C++, C# e Ada
União Dinâmica Opcional
União estática
Método redefinido
União dinâmica
Método sobrecarregado
Métodos Virtuais
C++ e C#:
métodos “virtuais” usam união dinâmica
Chamadas para métodos virtuais:
são encaminhadas para a implementação adequada em tempo de execução
class person {public:
virtual void print_data();...
}
Classe Abstrata
Classe base:
Método sem implementação
Só possui interface
C++: método virtual puro
Classe base: abstrata
Não podem ter objetos
Exemplo
abstract class person {...public abstract void print_data();...
C#
class person {...virtual void print_data() = 0;...
C++
Encontrando Métodos
Como os métodos dinâmicos são encontrados em tempo de execução?
Objeto referenciado deve conter a informação necessária para que o método correto seja encontrado
Implementação usual:
vtable
Busca por Métodos
class foo {int a;double b;char c;
public:virtual void k (...virtual void l (...virtual void m (...virtual void n (......
};
foo F;
ab
c
Fklmn
vtable de foo
Implementação de m
Busca por Métodos
class bar : public foo {int w;
public:void m();virtual double s (...virtual char *t (......
};
bar B;
ab
cw
Bklmnst
vtable de bar
bar::m
foo::n
bar::s
Exemplo
foo F;bar B;foo *q;bar *s;...q = &B; // Oks = &F; // Erro...// Verificação em tempo de execução:s = dynamic_cast<bar *>(q);
Exemplo: Eiffel
class foo ...class bar inherit foo ......f : foob : bar...f := b-- b recebe f caso f referencie um-- objeto do tipo barb ?= f
Virtual x “In line”
Métodos virtuais não podem ser expandidos em linha
Métodos curtos com expansão em linha:
estáticos (não-virtuais)
Polimorfismo
Rotina que opera sobre foo:
funciona para qualquer filho de foo
União dinâmica de métodos:
métodos da classe filha serão chamados
Mas não resolve todos os problemas...
Revisando Exemplo de Listaclass list_err { // exceçãopublic:
char *description;list_err(char *s){description = s;}};
class list_node {list_node* prev;list_node* next;list_node* head_node;
public:int val;list node() {
prev = next = head_node = this;val = 0;
}
list_node* predecessor() {if (prev == this || prev == head_node)
return 0;return prev;
}
list_node* successor() {if (next == this || next == head_node)
reuturn 0;return next;
}
bool singleton() {return (prev == this);
}
void insert_before(list_node* new_node) {if(!new_node->singleton())
throw new list_err(“inserção repetida”);prev->next = new_node;new_node->prev = prev;new_node->next = this;prev = new_node;new_node->head_node = head_node;
}
void remove(){if(singleton())
throw new list_err(“nó não existe);prev->next = next;next->prev = prev;prev = next = head_node = this;
}
~list_node() {if(!singleton())
throw new list_err(“nó ainda na lista”);}
};
class list{
list_node header;
public:
int empty() {return header.singleton();
}
list_node* head() {return header.successor();
}
void append(list_node *new_node) {header.insert_before(new_node);
}~list() {
if (!header.singleton())throw new list_err(“Lista não vazia”)
}};
Revisando Exemplo de Lista
Revisando Exemplo de Lista
class int_list_node : public_list_node {public:
...void remove() {
try{gp_list_node::remove();
} catch(list_err) {// não faz nada
}};
int_list_node *q, r;...r = q->successor(); // Erro!gp_list_node * p = q->successor();cout << p.val; // Erro!
Classes Genéricas
template <class V>class list_node {
list_node<V>* prev;list_node<V>* next;list_node<V>* head_node;
public:V val;list_node<V>* predecessor() {...list_node<V>* successor() {...void insert_before(list_node<V>* new_node) {......
};
template <class V>class list {
list_node<V> header;public:
list_node<V>* head() {...void append(list_node<V> *new_node) {......
};
Classes Genéricastypedef list_node<int> int_list_node;typedef list_node<int> int_list;...int_list numbers;int_list_node* firtst_int;...first_int = numbers->head();
Tipo genérico: abstração do tipo
Flexibilidade extra
Não é possível fazer isso com herança
Exemplo
template <class V>class queue : public list <V> {public:
void enqueue(list_node<V>* new_node){append(new_node);
}
list_node<V>* dequeue(){if(empty())
throw new list_err(“fila vazia”);list_node<V>* p = head();p->remove();return p;
}};
Exemplo: Eiffelclass gp_list_node ......class gp_listfeature {NONE} -- private
header : gp_list_node -- a ser redefindofeature {ALL} -- public
head : like header is ...append (new_node : like header) is ......
end...class student_list_node inherit gp_list_node ......class student_list
inherit gp_listredefine header end
feature {NONE}header : strudent_list_node-- não é preciso redefinir head e append
Fechamento de Objetos
Fechamento de objetos para simular fechamento de rotinas
Fechamento: Método + Contexto
Exemplotemplate <class T>class un_op{public:
virtual T operator()(T i) const = 0;};
class plus_x : public un_op<int> {const int x;
public:plus_x(int n) : x(n) { }virtual int operator()(int i) const {
return i + x;}
};
void apply_to_A(const un_op<int>& f, int A[], int A_size) {int i;for (i = 0; i < A_size; i++) A[i] = f(A[i]);
}...int A[10];apply_to_A(plus_x(2), A, 10);
Armazenando Argumentos
Aplicação de fechamento de objetos
Fechamento: função + alguns argumentos
Armazena os argumentos para uso posterior
Exemploclass fn_call {public:
virtual void trigger() = 0;};void schedule_at(fn_call& fc, time t) {
...}...void foo(int a, double d, char c) {
...}class call_foo : public fn_call {
int arg1;double arg2;char arg3;
public:call_foo(int a, double b, char c) : arg1(a), arg2(b), arg3(c) {}void trigger() {
foo(arg1, arg2, arg3);}
};...call_foo cf(3, 3.14, ‘x’);schedule_at(cf, now() + delay);
Linguagens OO
Linguagens com modelo uniforme de objetos
Todo tipo é uma classe
Toda variável é um objeto
Objetos antropomórficos:
responsáveis por toda computação
Smalltalk, Ruby, Python (3)
Smalltalk
Linguagem OO canônica
Estruturas de controle são objetos
Ambiente de programação é um objeto
editor
interpretador
C++ é OO?Não
Permite fazer programas OO
Coisas não OO de C++:
rotinas fora de classes
tipos não são classes
métodos são estáticos por padrão
... mantém compatibilidade com C
Parte IIIScripts
Introdução
Linguagens tradicionais:
aplicações auto-contidas
Problema comum:
coordenação entre de diversos programas
Ex.: sistema de folha de pagamento
IntroduçãoMotivação inicial: juntar programas
Foco:
flexibilidade
desenvolvimento rápido
adaptações locais
verificações em tempo de execução
bibliotecas
Scripts e Programação Web
Como gerar conteúdo dinamicamente num página web?
Executar um programa
Onde?
No servidor (server-side)
No computador do usuário (client-side)
Server-Side
Controle sobre o conteúdo da página
Uso computacional intensivo
Manipulação de dados sigilosos
Client-Side
Precisam acessar informações locais
Tempo de execução é crítico
Exemplo: animações, verificação de erros
Scripts CGI“Common Gateway Interface”
Mecanismo para executar scripts no servidor
Visão geral:
cliente acessa um endereço
servidor executa o script
script retorna resultado para o cliente
normalmente em HTML
Exemplo
#!/usr/bin/perl
print “Content-type: text/html\n\n”;
$host = ‘hostname’; chop $host;print “<HTML>\n<HEAD>\n<TITLE>Status of ”, $host, “<\TITLE>\n<\HEAD>\n<BODY>\n”print “<H1>”, $host, “</H1>\n”;print “<PRE>\n”, ‘uptime’m “\n”, ‘who’;print “</PRE>\n</BODY>\n<\HTML>\n”;
Desvantagens:
cada acesso: programa separado
instalação em diretórios especiais
cada script precisa gerar o código HTML
Scripts CGI
Server-Side Includes
Servidores Web: módulos de execução de script
Scripts inseridos no código HTML
Servidor executa o script e substitui o código pelo resultado
Transparente para o usuário
Exemplo
<HTML><HEAD><TITLE>Status of <?php echo $host = chop(‘hostname’) ?></TITLE></HEAD><BODY><H1><?php echo $host ?></H1><PRE><?php echo ‘uptime’, “\n”, ‘who’ ?></PRE></BODY></HTML>
Client-Side Scripts
Necessitam de um interpretador no cliente
Linguagens mais restritas
Mais popular: JavaScript
Python
Criado no final dos anos 80s
Interpretada
Imperativa (influenciada por ling. funcionais)
Foco:
código legível
facilidade na programação
Interpretador
Executa código linha por linha
Forma rápida de testar código
Código pode ser armazenado num arquivo
Sistema de Tipos
Tipos são dinâmicos
Variáveis são criadas conforme são utilizadas
Modelo por referência
Variáveis são nomes para valores
Fortemente tipado:
Operações sobre tipos definidos
Tipos Básicos
string = ‘two’ # stringf = 2.0 # ponto flutuantei = 2 # inteirob = True # booleanoc = 1 + 1j # complexo
OperaçõesAdição: +
tipos: todos (string = concatenação)Subtração: -
tipos: todos - stringMultiplicação: *
tipos: todos (string = concatenação mult.)Divisão: /
tipos: todos - stringResto: %
tipos: todos - stringExponenciação:
tipos: todos - string Obs.: +=, -= ,...
Atenção!
Python é fortemente tipado:
f1 = 1.0str = ‘1’f2 = f1 + 2.0print f2str2 = str + ‘2’print str2f3 = f1 + str # ERROf3 = f1 + float(str) # Ok: Conversão é explícitastr3 = str(f1) + str # Ok: Conversão é explícita
Operações Lógicas
Igualdade: ==
Diferente: !=
Menor/maior: >, <
Operadores lógicos: not, and, or
Ordem de Execução e Escopo
Cada linha executada de cada vez
quebra de linha denota o fim do “comando”
Escopo
delimitados por identação
mesma identação: mesmo bloco
variáveis: escopo por bloco
precisam ser definidas antes de serem utilizadas
Tipos de Escopo
Global
Local
Classe
Tempo de Vida de Objetos
Objetos possuem tempo de vida ilimitado
Contagem de referência
Ignora referência cruzada
Coletor de lixo:
Executado apenas quando
desalocação - alocação > limiar
Estruturas de Controle
Repetição com controle lógico:
while
Sequenciamento:
if / elif
Repetição por enumeração:
for
while
contador = 3while contador > 0:
print contadorcontador -= 1
if / elif
temp = 23if temp < 18:
print ‘frio’elif temp > 28:
print ‘calor’else:
print ‘normal’
Exemplo
num = 2while num <= 1000:
eh_primo = Truediv = 2while div**2 <= num:
if (num % div) == 0:eh_primo = False
div += 1if eh_primo:
print numnum += 1
ListasContainer padrão em Python
Alocação dinâmica: tipo mutável
Associação: índice -> referência
Dados heterogêneos
Declaração: l = [1.0, 2.0, 3.0]
Acesso: l [0] == 1.0, l [1] == 2.0, l [2] == 3.0
l [-1] == 3.0, l [-2] == 2.0, l [-3] == 1.0
Operações
append: inclui elemento ao final da lista
del: exclui elementos
len: número de elementos
l = [1.0]l.append(‘Jose’)l.append(1 + 1j)del l[1]print l #[1.0, (1+1j)]print len(l) # 2
Listas Aninhadas
pessoa1 = [‘Joao’, 20]pessoa2 = [‘Jose’, 30]dados = [pessoa1, pessoa2]dados[0][1] = 21print pessoa1[1] # 21
Operador “is”
Teste de identidade
Verifica se duas referências apontam para o mesmo objeto
l1 = [1]l2 = l1l3 = [1]l4 = [l1]print l1 is l2 # Trueprint l1 is l3 # Falseprint l1 is l4[0] # True
Operador “in”
Pertence ou não pertence
l1 = [1]l2 = l1l3 = [1]l4 = [l1]print 1 in l2 # Trueprint l2 in l1 # Falseprint l1 in l4 # True
Iterando sobre Listas
loop for
itera sobre elementos de uma lista
l = [1, ‘Joao’, 1+1j, 3.5]for item in l:
print item
Função Range
Retorna lista inteiros dentro de um conjunto
i = range(10) # 0..9i = range(1, 10) # 1..9i = range(1, 10, 2) # 1, 3, 5, 7, 9
lista = [...for ind in range(len(lista)):
print ind, lista[ind]
Cortes de Listas
i = range(10) # 0..9print i[0:-1] # [0, 1, 2, 3, 4, 5, 6, 7, 8]print i[2:5] # [2, 3, 4]print i[2:9:2] # [2, 4, 6, 8]print i[-1:0:-1] # [9, 8, 7, 6, 5, 4, 3, 2, 1]print i[0:] # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]print i[:-1] # [0, 1, 2, 3, 4, 5, 6, 7, 8]print i[:0:-1] # [9, 8, 7, 6, 5, 4, 3, 2, 1]print i[::-1] # [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]print i[::] # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Obs.: Funciona com strings também!
Cortes de Listas
i = range(10) # 0..9i[0:3] = [1, 1, 1]print i # [1, 1, 1, 3, 4, 5, 6, 7, 8, 9]j = i[3:6]j[0] = 4print j # [4, 4, 5]print i # [1, 1, 1, 3, 4, 5, 6, 7, 8, 9]
Dicionários
Alocação dinâmica: tipo mutável
Associação: chave -> “valor”
Dados heterogêneos
Declaração: d = {‘a’:1.0, ‘c’:2.0, 3:3.0}
Acesso: d[‘a’] == 1.0, d[‘c’] == 2.0, d[3] == 3.0
Exemplos
l = [1, ‘2’, 3]d = {‘a’:1, 2:3, 1+1j:’5’, l:1.0} # ERROd = {‘a’:1, 2:3, 1+1j:’5’, 1:l}print d.keys() # ['a', 1, 2, (1+1j)]print d.values() # [1, [1, '2', 3], 3, '5']d[1][2] = 2print l # [1, '2', 2]print d # {'a': 1, 1: [1, '2', 2], 2: 3, (1+1j): '5'}for item in d:
print item # imprime os valoresprint d.has_key(1+1j) # True
Set
Parecido com dicionário
Não possui elementos repetidos
Não tem “chave”
Tuple
t = (1, ‘a’, c)
t[0] == 1
t[1] == ‘a’
Tuple é imutável:
t[0] = 2 # ERRO!
Tuple
Parênteses podem ser omitidos
t = 1, 2, 3
Tuple pode ser desempacotado:
item1, item2, item3 = t
item1, item2, item3 = 1, 2, 3
Funções
Variáveis de primeira classe
Parâmetros:
não possuem tipo
passagem por referência
podem ter valores padrão
podem ser nomeados
sempre retornam um valor
Funções: Sintaxe
def hello():print ‘hello’
>>> hello() # ‘hello’def hello(nome):
aux = ‘hello, ’ + nomeprint aux
>>> hello(‘Eu’) # ‘Hello, Eu’def add(a):
b = a + 1return b
>>> c = add(1)>>> print c # 2>>> c = add(‘test’) # ERRO
Funções - Retornos
def sign(num):if num > 0:
return 1elif num < 0:
return -1else:
return 0
def hello():print ‘hello’
>>> temp = hello()>>> print type(hello) # None
Exemplosdef add(arg):
return 1 + arg
def add(arg):if type(arg) == ‘Int’
return 1 + argelif type(arg) == ‘Str’
return ‘erro’RUIM
def add(arg):try:
return 1 + argexcept:
return ‘erro’
BOM
Função: Referências
def appender(a_string, a_list):a_string += ‘test’a_list.append(‘test’)
>>> my_str = ‘test’>>> my_list = [‘test’]>>> appender(my_str, my_list)>>> print my_str>>> print my_list
Funções: Argumentos
def adjust_value(value, amount=2.0):return value * amount
>>> print adjust_value(1.0)>>> print adjust_value(1.0, 3.0)
Funções: Argumentos
def adjust_value(value, amount=2.0, thr=1.0):if value > thr:
return value * amountreturn value
>>> print adjust_value(value=1.0, amount=2.0, thr=3.0)>>> print adjust_value(thr=3.0, amount=2.0, value=1.0)>>> print adjust_value(value=1.0, thr=2.0)>>> print adjust_value(thr=2.0, amount=1.0) # ERRO
Funções: Escopo
>>> aux = 1.0def scope_test():
aux = 2.0>>> scope_test()>>> print aux # 1.0def scope_test_2():
a = auxreturn a
>>> print scope_test_2() # 1.0def scope_test_3():
global auxaux = 2.0
>>> scope_test_3()>>> print aux # 2.0def scope_test_4():
a = auxaux = 2
>>> scope_test_4() # ERRO
Funções: Variáveis
def hello():print ‘Hello’
>>> hello_alias = hello>>> print hello_alias() # Hello
>>> PI = 3.141592654def area(r):
return r * r * PIdef circ(r):
return 2 * r * PI>>> func = [area, circ]>>> for foo in func:
print foo(1.0)
Funções de Alto Nível
def call_it(func, value):return func(value)
def do_all(func, values):result = []for val in values:
result.append(func(val))return result
def combine_values(func, values):current = values[0]for i in range(1, len(values)):
current = func(current, values[i])def add(x, y): return x + ydef mult(x, y): return x * y>>> print combine_values(add, [1, 3, 5])>>> print combine_values(mult, [1, 3, 5])
Funções: Argumentos
def add_all(*args):total = Nonefor a in args:
total += areturn total
>>> print add_all()>>> print add_all(1)>>> print add_all(1, 2, 3)>>> print add_all(‘1’, ‘2’, ‘3’)
Funções: Argumentos
def combine_values(func, *values):current = values[0]for i in range(1, len(values)):
current = func(current, values[i])>>> print combine_values(add, 1, 2, 3)
Funções: Prog. Funcional
filter(f, s): seleciona elementos de s em que f é verdadeiro
map(f, s): aplica f nos elementos de s
reduce(f, s): usa f para combinar todos os elementos de s
Funções: Prog. Funcional
def positive(x): return x >= 0>>> print filter(positive, [-3, -2, -1, 0, 1, 2])def negate(x): return -x>>> print map(negate, [-3, -2, -1, 0, 1, 2])def add(x, y): return x + y>>> print reduce(add, [-3, -2, 0, 1, 2])
Módulo
def add(x, y):return x + y
def sub(x, y):return x - y
>>> import modulo>>> x = 1>>> y = 1>>> print modulo.add(x, y)>>> print modulo.sub(x, y)
modulo.py
Classes
class Vazia(object):pass # Não faz nada
>>> nada_1 = Vazia()>>> nada_2 = Vazia()>>> print nada_1 is nada_2 # False>>> print nada_1 is Nada # False
Métodos
class Vazia(object):
def nada(self):print “Nada”
>>> nada_1 = Vazia()>>> nada_1.nada() # Nada>>> nada_1.nada() # Chamada: nada(nada_1)
Atributos
class Greeter(object):
def greet(self, name):print self.hello + name + ‘!’
>>> g = Greeter()>>> g.hello = ‘Ola, ’>>> g.greet(‘Joao’) # Ola, Joao!
Construtor
class Greeter(object):
def __init__(self, hello):self.hello = hello
def greet(self, name):print self.hello + name + ‘!’
>>> g = Greeter(‘Ola, ’)>>> g.greet(‘Joao’) # Ola, Joao!>>> g.hello = ‘Hello, ’>>> g.greet(‘John’) # ‘Hello, John!’
Cuidado
class Greeter(object):
def __init__(self, hello_msg):hello = hello_msg
def greet(self, name):print self.hello + name + ‘!’
>>> g = Greeter(‘Ola, ’)>>> g.greet(‘Joao’) # ERRO
Interfaces
Interface x Implementação
Interface: o que alguma coisa sabe fazer
Implementação: como ela faz coisas
Exemplo de como usar interfaces em Python:
Sério com amostras irregularmente amostradas
Exemplo
Sinal amostrado irregularmente
Esconder a amostragem irregular
Como reamostrar o sinal?
Constante por partes
Interpolação linear
Filtro mais sofisticado
Exemplo
Interface desejada:
class AlgumNome(object):
def __init__(self, values):‘‘‘ valores = ((x0, y0), (x1, y1), ...)’’’# guardar valores
def get(self, where):# verificar se where está na faixa permitida# retornar valor interpolado
Exemplo
Implementação - constante por partes
class SinalDegrau(object):
...
def get(self, where):if where < self.values[0][0]:
raise IndexError(‘Indice muito pequeno’)for i in range(len(values)-1):
x0, y0 = self.values[i]x1, y1 = self.values[i+1]if x0 <= where <= x1:
return y0raise IndexError(‘Indice muito pequeno’)
Exemplo
Interpolação linear
class SinalLinear(object):
...
def get(self, where):if where < self.values[0][0]:
raise IndexError(‘Indice muito pequeno’)for i in range(len(values)-1):
x0, y0 = self.values[i]x1, y1 = self.values[i]if x0 <= where <= x1:
return y0 + (y1-y0) * (where-x0) / (x1-x0)raise IndexError(‘Indice muito pequeno’)
Exemplo
Aplicação:
def average(signal, x0, x1, num_samples):width = (x1 - x0) / num_samplestotal = 0.0for i in range(num_samples):
x = x0 + i * widthtotal += signal.get(x)
return total / num_samples
Herança
class Pai(object):
def hello(self):print ‘Hello’
class Filho(Pai):
def goodbye(self):print ‘Goodbye’
>>>c = Filho()>>>c.goodbye()>>>c.hello()
def get(self, x):return self.amp * math.sin(x * self.freq)
Exemplo
class SinalInterpolado(object):
def find(self, where):if where < self.values[0][0]:
raise IndexError(‘Indice muito pequeno’)for i in range(len(values)-1):
x0, y0 = self.values[i]x1, y1 = self.values[i]if x0 <= where <= x1:
return iraise IndexError(‘Indice muito pequeno’)
Exemplo
class SinalDegrau(SinalInterpolado):
def __init__(self, values):self.values = values
def get(self, where):i = self.find(where)return self.values[i][1]
Exemplo
class SinalInterpolado(object):
def __init__(self, values):self.values = values[:]
def get(self, where):raise NotImplemented
def find(self, where):if where < self.values[0][0]:
raise IndexError(‘Indice muito pequeno’)for i in range(len(values)-1):
x0, y0 = self.values[i]x1, y1 = self.values[i]if x0 <= where <= x1:
return iraise IndexError(‘Indice muito pequeno’)
Exemploclass SinalDegrau(SinalInterpolado):
def __init__(self, values):super().__init__(values)
def get(self, where):i = self.find(where)return self.values[i][1]
class SinalLilnear(SinalInterpolado):
def __init__(self, values):super().__init__(values)
def get(self, where):i = self.find(where)return y0 + (y1-y0) * (i-x0) / (x1-x0)
Sobrecarga
Classe para vetores
Sobrecarga:
len(vec)
vec[i]
Vetor sem Sobrecargas
class Vetor(object):
def __init__(self, len):self.values = {}self.len = len
def get(self, index):self.check_index(index)return self.values[index]
def set(self, i, value):self.check_index(index)self.values[index] = i
def check_index(self, index):if (index < 0) or (index >= len):
IndexError(‘Index out of range’)
Sobrecarga
Quase tudo em Python é uma chamada para um método
len(x) --> x.__len__()
a = x[0] --> a = x.__getitem__(0)
x[0] = 1 --> x.__setitem__(0, 1)
Exemploclass Vetor(object):
def __init__(self, len):self.values = {}self.len = len
def __getitem__(self, index):self.check_index(index)return self.values[index]
def __setitem__(self, i, value):self.check_index(index)self.values[index] = i
def __len__(self):return self.len
def check_index(self, index):if (index < 0) or (index >= len):
IndexError(‘Index out of range’)
Outros Métodos
__add__
__sub__
__mul__ (__rmul__)
__str__
__iter__
Iteradores
Duas formas:
objetos iteradores
geradores (generators)
Vamos ver objetos iteradores
Objeto IteradoresPossuem um método next():
retorna o próximo elemento
Quando chega ao fim:
Exceção StopIteration
Deve continuar dando StopIteration após chamdas subsequentes
Possuem o métod __iter__():
Retorna ele mesmo
Exemploclass Vetor(object):
...
class VetorIterator(object):
def __init__(self, obj):self.obj = objself.last = 0
def next(self):if self.last >= len(obj):
raise StopIterationself.last += 1return obj[i]
def __iter__(self):return self
def __iter__(self):return VetorIterator(self)