567
Linguagens de Programação Leonardo de Oliveira Nunes 2012/1 Escola Politécnica - DEL - EEL670

Slides Da Disciplina Completos

Embed Size (px)

Citation preview

Page 1: Slides Da Disciplina Completos

Linguagens de

Programação

Leonardo de Oliveira Nunes2012/1

Escola Politécnica - DEL - EEL670

Page 3: Slides Da Disciplina Completos

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++

Page 4: Slides Da Disciplina Completos

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

Page 5: Slides Da Disciplina Completos

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:

Page 6: Slides Da Disciplina Completos

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

Page 7: Slides Da Disciplina Completos

Avaliação

4 Provas

Listas (opcionais)

Laboratório

Page 8: Slides Da Disciplina Completos

Por quê?

Conceitos de linguagens de programação

Aprendizado de novas linguagens

Funcionamento das linguagens

Page 9: Slides Da Disciplina Completos

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

Page 10: Slides Da Disciplina Completos

PARTE IFundamentos

Page 11: Slides Da Disciplina Completos

Introdução

Linguagem:

Projeto x Implementação

O que será visto:

Histórico do projeto de linguagens

Introdução à implementação

Page 12: Slides Da Disciplina Completos

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

Page 13: Slides Da Disciplina Completos

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]

Page 14: Slides Da Disciplina Completos

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

Page 15: Slides Da Disciplina Completos

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

Page 16: Slides Da Disciplina Completos

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

Page 17: Slides Da Disciplina Completos

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.

Page 18: Slides Da Disciplina Completos

Declarativa x Imperativa

Declarativa

Foco: o que o computador deve fazer

Mais alto nível

Imperativa

Foco: como o computador deve fazer

Mais eficiente

Page 19: Slides Da Disciplina Completos

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

Page 20: Slides Da Disciplina Completos

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

Page 21: Slides Da Disciplina Completos

Linguagens Lógicas

Inspiração: lógica de predicados

Computação: provar teoremas a partir de regras

Page 22: Slides Da Disciplina Completos

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”

Page 23: Slides Da Disciplina Completos

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

Page 24: Slides Da Disciplina Completos

Linguagens OO

Similares a linguagens von Neumann

Computação: interação entre objetos

Objetos: estado interno e rotinas para controlá-lo

Page 25: Slides Da Disciplina Completos

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.

Page 26: Slides Da Disciplina Completos

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)))))

Page 27: Slides Da Disciplina Completos

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

Page 28: Slides Da Disciplina Completos

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

Page 29: Slides Da Disciplina Completos

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

Page 30: Slides Da Disciplina Completos

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

Page 31: Slides Da Disciplina Completos

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

Page 32: Slides Da Disciplina Completos

“Linker”

Compilador

Código fonte

Linker

Código de máquina incompleto Bibliotecas

Código de máquina

Page 33: Slides Da Disciplina Completos

Conversão para Assembler

Compilador

Código fonte

Assembler

Código “assembler”

Código de máquina

Page 34: Slides Da Disciplina Completos

Tradução

Tradutor

Código fonte

Código fonte em outra linguagem

Page 35: Slides Da Disciplina Completos

“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

Page 36: Slides Da Disciplina Completos

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

Page 37: Slides Da Disciplina Completos

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

Page 38: Slides Da Disciplina Completos

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”

Page 39: Slides Da Disciplina Completos

Ferramentas auxiliares:

“Debuggers”

Editores

Verificadores de estilo: análise sintática/semântica

Controle de configuração e dependências

“Profilers”

Page 40: Slides Da Disciplina Completos

IDE

“Integrated Development Environment”

Integram diversas ferramentas

Ex.: Eclipse, XCode, MS Visual Studio

As vezes são essenciais para a linguagem:

Ex.: Smalltalk

Page 41: Slides Da Disciplina Completos

Exemplo

Page 42: Slides Da Disciplina Completos

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”

Page 43: Slides Da Disciplina Completos

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)

}

Page 44: Slides Da Disciplina Completos

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

Page 45: Slides Da Disciplina Completos

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) ; }

Page 46: Slides Da Disciplina Completos

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

Page 47: Slides Da Disciplina Completos

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

Page 48: Slides Da Disciplina Completos

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

Page 49: Slides Da Disciplina Completos

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)

Page 50: Slides Da Disciplina Completos

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

Page 51: Slides Da Disciplina Completos

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”

Page 52: Slides Da Disciplina Completos

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

Page 53: Slides Da Disciplina Completos

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)

Page 54: Slides Da Disciplina Completos

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

Page 55: Slides Da Disciplina Completos

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

Page 56: Slides Da Disciplina Completos

Sintaxe

Linguagens de computação precisam ser precisas

Especificação sem ambiguidade da:

forma (sintaxe)

significado (semântica)

Veremos sintaxe

Page 57: Slides Da Disciplina Completos

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

Page 58: Slides Da Disciplina Completos

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

Page 59: Slides Da Disciplina Completos

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

Page 60: Slides Da Disciplina Completos

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

Page 61: Slides Da Disciplina Completos

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

Page 62: Slides Da Disciplina Completos

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

Page 63: Slides Da Disciplina Completos

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

Page 64: Slides Da Disciplina Completos

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”

Page 65: Slides Da Disciplina Completos

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 ➝ + | - | * | /

Page 66: Slides Da Disciplina Completos

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

Page 67: Slides Da Disciplina Completos

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

Page 68: Slides Da Disciplina Completos

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 ➝ /

=

Page 69: Slides Da Disciplina Completos

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

Page 70: Slides Da Disciplina Completos

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

Page 71: Slides Da Disciplina Completos

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

Page 72: Slides Da Disciplina Completos

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

Page 73: Slides Da Disciplina Completos

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

Page 74: Slides Da Disciplina Completos

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”

Page 75: Slides Da Disciplina Completos

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

Page 76: Slides Da Disciplina Completos

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

Page 77: Slides Da Disciplina Completos

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)

Page 78: Slides Da Disciplina Completos

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 ➝ * | /

Page 79: Slides Da Disciplina Completos

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:

Page 80: Slides Da Disciplina Completos

Parte IIElementos de Linguagens de

Programação

Page 81: Slides Da Disciplina Completos

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

Page 82: Slides Da Disciplina Completos

Nomes, Uniões e Escopo

Page 83: Slides Da Disciplina Completos

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

Page 84: Slides Da Disciplina Completos

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

Page 85: Slides Da Disciplina Completos

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

Page 86: Slides Da Disciplina Completos

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, ...

Page 87: Slides Da Disciplina Completos

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)

Page 88: Slides Da Disciplina Completos

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

Page 89: Slides Da Disciplina Completos

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

Page 90: Slides Da Disciplina Completos

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

Page 91: Slides Da Disciplina Completos

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

Page 92: Slides Da Disciplina Completos

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

Page 93: Slides Da Disciplina Completos

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)

Page 94: Slides Da Disciplina Completos

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

Page 95: Slides Da Disciplina Completos

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

Page 96: Slides Da Disciplina Completos

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”

Page 97: Slides Da Disciplina Completos

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

Page 98: Slides Da Disciplina Completos

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

Page 99: Slides Da Disciplina Completos

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

Page 100: Slides Da Disciplina Completos

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

Page 101: Slides Da Disciplina Completos

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

Page 102: Slides Da Disciplina Completos

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

Page 103: Slides Da Disciplina Completos

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

Page 104: Slides Da Disciplina Completos

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

Page 105: Slides Da Disciplina Completos

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

Page 106: Slides Da Disciplina Completos

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

Page 107: Slides Da Disciplina Completos

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

Page 108: Slides Da Disciplina Completos

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

Page 109: Slides Da Disciplina Completos

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

Page 110: Slides Da Disciplina Completos

Exemplo

int main(){int i = 0;{int i = 1; /* i == 1 */{int i = 2; /* i == 2 */

}/* i == 1 */

}/* i = 0 */

}

Page 111: Slides Da Disciplina Completos

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

Page 112: Slides Da Disciplina Completos

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

Page 113: Slides Da Disciplina Completos

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

Page 114: Slides Da Disciplina Completos

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)

Page 115: Slides Da Disciplina Completos

Pascal

const N = 10;...procedure foo;const M = N;

varA : array [1..M] if integer;N : real;

Page 116: Slides Da Disciplina Completos

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; ...

Page 117: Slides Da Disciplina Completos

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

Page 118: Slides Da Disciplina Completos

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

Page 119: Slides Da Disciplina Completos

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;...

};

Page 120: Slides Da Disciplina Completos

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

Page 121: Slides Da Disciplina Completos

C

struct gerente; /* Declaração!*/struct empregado {

struct gerente *chefe;struct empregado *proximo_empregado;...

};struct gerente { /* Definição!*/

struct empregado *primeiro_empregado;...

};

Page 122: Slides Da Disciplina Completos

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

Page 123: Slides Da Disciplina Completos

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

Page 124: Slides Da Disciplina Completos

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

Page 125: Slides Da Disciplina Completos

Módulos em Diferentes Linguagens

Package: Ada, Java, Perl

Module: Python

Namespace: C++, C#, PHP

Page 126: Slides Da Disciplina Completos

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;

Page 127: Slides Da Disciplina Completos

“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

Page 128: Slides Da Disciplina Completos

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

Page 129: Slides Da Disciplina Completos

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

Page 130: Slides Da Disciplina Completos

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

Page 131: Slides Da Disciplina Completos

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

Page 132: Slides Da Disciplina Completos

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

Page 133: Slides Da Disciplina Completos

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

Page 134: Slides Da Disciplina Completos

Exemplo

class stack {...

bool deeper_than(stack other) {return (top > other.top);

}...

}...if (a.deeper_than(B)) ...

Page 135: Slides Da Disciplina Completos

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, ...

Page 136: Slides Da Disciplina Completos

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

Page 137: Slides Da Disciplina Completos

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”

Page 138: Slides Da Disciplina Completos

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

Page 139: Slides Da Disciplina Completos

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)

Page 140: Slides Da Disciplina Completos

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

Page 141: Slides Da Disciplina Completos

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

Page 142: Slides Da Disciplina Completos

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

Page 143: Slides Da Disciplina Completos

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

Page 144: Slides Da Disciplina Completos

Sobrecarga

Quando um nome referencia mais de um objeto

Exemplo: operador + em C

Page 145: Slides Da Disciplina Completos

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!

Page 146: Slides Da Disciplina Completos

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);

Page 147: Slides Da Disciplina Completos

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)

Page 148: Slides Da Disciplina Completos

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;

Page 149: Slides Da Disciplina Completos

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

Page 150: Slides Da Disciplina Completos

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

Page 151: Slides Da Disciplina Completos

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

Page 152: Slides Da Disciplina Completos

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

Page 153: Slides Da Disciplina Completos

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#)

Page 154: Slides Da Disciplina Completos

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

Page 155: Slides Da Disciplina Completos

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

Page 156: Slides Da Disciplina Completos

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

Page 157: Slides Da Disciplina Completos

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

Page 158: Slides Da Disciplina Completos

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?

Page 159: Slides Da Disciplina Completos

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)

Page 160: Slides Da Disciplina Completos

“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

Page 161: Slides Da Disciplina Completos

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

Page 162: Slides Da Disciplina Completos

“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

Page 163: Slides Da Disciplina Completos

“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

Page 164: Slides Da Disciplina Completos

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

Page 165: Slides Da Disciplina Completos

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?

Page 166: Slides Da Disciplina Completos

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

Page 167: Slides Da Disciplina Completos

Outros Mecanismos

Não permitir rotinas aninhadas: C, C++

Só rotinas “de fora” são de primeira classe: Modula-2

Page 168: Slides Da Disciplina Completos

Fechamento de Objetos

Impedimento de rotinas aninhadas

Problema:

Impede a passagem de funções com contexto

Alternativa em OO: objetos simples

Page 169: Slides Da Disciplina Completos

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

Page 170: Slides Da Disciplina Completos

Fechamento de Objetos

Objeto que faz o papel de uma função e contexto:

Object closure, function object, functor

Page 171: Slides Da Disciplina Completos

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

Page 172: Slides Da Disciplina Completos

Controle de Fluxo

Page 173: Slides Da Disciplina Completos

Controle de Fluxo

Determinação da ordem em que as tarefas são executadas no código

Fundamental para quase todas linguagens

Page 174: Slides Da Disciplina Completos

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

Page 175: Slides Da Disciplina Completos

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)

Page 176: Slides Da Disciplina Completos

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

Page 177: Slides Da Disciplina Completos

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

Page 178: Slides Da Disciplina Completos

Notação Polonesa

Utilizada em Lisp para funções e operadores

(* (+ 1 3) 2)

(append a b c my_list)

Page 179: Slides Da Disciplina Completos

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

Page 180: Slides Da Disciplina Completos

Notação por Infixo em C

a = b != 0 ? a/b : 0;

Page 181: Slides Da Disciplina Completos

Posfixo

Comum em algumas calculadoras

Aparece ocasionalmente em algumas linguagens

Exemplo:

++ e -- em C++

Page 182: Slides Da Disciplina Completos

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

Page 183: Slides Da Disciplina Completos

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!

Page 184: Slides Da Disciplina Completos

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

Page 185: Slides Da Disciplina Completos

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

Page 186: Slides Da Disciplina Completos

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

Page 187: Slides Da Disciplina Completos

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

Page 188: Slides Da Disciplina Completos

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;

Page 189: Slides Da Disciplina Completos

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?

Page 190: Slides Da Disciplina Completos

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

Page 191: Slides Da Disciplina Completos

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)

Page 192: Slides Da Disciplina Completos

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

Page 193: Slides Da Disciplina Completos

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;

Page 194: Slides Da Disciplina Completos

Atribuição Múltipla

a, b, c = 1, 2, 3;a, b = c, d;a, b, c = foo(d, e, f);

Page 195: Slides Da Disciplina Completos

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

Page 196: Slides Da Disciplina Completos

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

Page 197: Slides Da Disciplina Completos

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

Page 198: Slides Da Disciplina Completos

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

Page 199: Slides Da Disciplina Completos

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

Page 200: Slides Da Disciplina Completos

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)

Page 201: Slides Da Disciplina Completos

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)

Page 202: Slides Da Disciplina Completos

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;

Page 203: Slides Da Disciplina Completos

Exemplo

const MAX = 10;int A[10];...if (i >= 0 && i < MAX && A[i] > foo)...

if ( d != 0 && n/d > limiar) ...

Page 204: Slides Da Disciplina Completos

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

Page 205: Slides Da Disciplina Completos

Fluxo Não Estruturado

Década de 70: programação estruturada

Abolição do goto

Page 206: Slides Da Disciplina Completos

Alternativas ao goto

Retornos de função

Erros e exceções

break

continue

Page 207: Slides Da Disciplina Completos

Sequenciamento

Determina a ordem das atribuições

Lista de statements sequenciados:

“{“ e “}”

“begin” e “end”

Page 208: Slides Da Disciplina Completos

Seleção

If ... then ... else ...

Algol: primeiro “if”

if condition then statementelse if condition then statementelse if condition then statement...else statement

Page 209: Slides Da Disciplina Completos

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(...)))

Page 210: Slides Da Disciplina Completos

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

Page 211: Slides Da Disciplina Completos

Sequenciamento

Case/Switch

alternativa para if aninhados

CASE (*expressao*) OF1: ... 2, 7: ...3..5: ...10: ...ELSE ...

END

Page 212: Slides Da Disciplina Completos

Sequenciamento

Case/Switch

Variações sintáticas:

série de valores x único valor

default requerido x opcional

Page 213: Slides Da Disciplina Completos

SequenciamentoCase/Switch do C: pouco usual

switch (...) {case 1: ...

break;case 2: ...case 7: ...

break;case 3: ...case 4: ...case 5: ...

break;default: ...

break;}

Page 214: Slides Da Disciplina Completos

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

Page 215: Slides Da Disciplina Completos

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

Page 216: Slides Da Disciplina Completos

Complicações Semânticas

Loop “for”:

apenas para iteração: implementação simples

facilitador de enumeração

Page 217: Slides Da Disciplina Completos

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

Page 218: Slides Da Disciplina Completos

For em Cfor (i = first; i<= last; i += step){...

}

{i = first;while (i <= last) {...i += step;

}}

=

Page 219: Slides Da Disciplina Completos

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++

Page 220: Slides Da Disciplina Completos

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

Page 221: Slides Da Disciplina Completos

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

Page 222: Slides Da Disciplina Completos

Objetos Iteradores

C++, Java: não tem yield

Solução: guardar o estado da última iteração num objeto

Objeto iterador

Page 223: Slides Da Disciplina Completos

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);

}

=

Page 224: Slides Da Disciplina Completos

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();}

}}

Page 225: Slides Da Disciplina Completos

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);

Page 226: Slides Da Disciplina Completos

Iteração Controlada Logicamente

Verificação de uma condição de parada lógica

Duas opções:

teste no início

teste no fim

Page 227: Slides Da Disciplina Completos

Recursão

Função em função dela mesmo

Não requer sintaxe extra

Qualquer algoritmo iterativo pode ser reescrito recursivamente

Page 228: Slides Da Disciplina Completos

Iteração x Recursão

Iteração -> linguagens imperativas

Recursão -> linguagens recursivas

Page 229: Slides Da Disciplina Completos

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);

}

Page 230: Slides Da Disciplina Completos

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;

}

Page 231: Slides Da Disciplina Completos

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

Page 232: Slides Da Disciplina Completos

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;}

}

Page 233: Slides Da Disciplina Completos

Exemplo

(define summation (lambda (f low high)(if (= low high)

(f low) ; “then” “then”

(+ (f low) (summation f (+ low 1) high))))) ; “else”

Lisp

Page 234: Slides Da Disciplina Completos

Pensando Recursivamente

define fib (lambda (n)(cond ((= n 0) 1)

((= n 1) 1)(#t (+ (fib (- n 1)) (fib (- n 2)))))))

Scheme

Problema: tempo exponencial!

Page 235: Slides Da Disciplina Completos

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

Page 236: Slides Da Disciplina Completos

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

Page 237: Slides Da Disciplina Completos

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”

Page 238: Slides Da Disciplina Completos

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

Page 239: Slides Da Disciplina Completos

Tipos de Dados

Page 240: Slides Da Disciplina Completos

Introdução

Funções de tipos:

contexto para operações

limites semânticos para operações

Page 241: Slides Da Disciplina Completos

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

Page 242: Slides Da Disciplina Completos

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

Page 243: Slides Da Disciplina Completos

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

Page 244: Slides Da Disciplina Completos

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

Page 245: Slides Da Disciplina Completos

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

Page 246: Slides Da Disciplina Completos

Classificação de Tipos

Classificação varia de linguagem para linguagem

Classificação mais usual:

caracteres

binários

inteiros

reais

Page 247: Slides Da Disciplina Completos

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

Page 248: Slides Da Disciplina Completos

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

Page 249: Slides Da Disciplina Completos

Tipos Discretos

Binários (booleanos)

Inteiros

Caracters

Possuem: antecessor e sucessor

Page 250: Slides Da Disciplina Completos

Enumerações

Conjunto de nomes

Normalmente ordenados

Equivalente a definir constantes

Em C: equivalente

Em Pascal: tipo próprio

Page 251: Slides Da Disciplina Completos

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)

Page 252: Slides Da Disciplina Completos

Tipos Compostos

Records ou Structures

Varitant Records ou Union

Array

Sets

Lists

Files

Page 253: Slides Da Disciplina Completos

Ortogonalidade

Ortogonalidade -> todo statement é expressão

Tipo que representa ausência de retorno

“Void”

Page 254: Slides Da Disciplina Completos

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

Page 255: Slides Da Disciplina Completos

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

Page 256: Slides Da Disciplina Completos

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

Page 257: Slides Da Disciplina Completos

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

Page 258: Slides Da Disciplina Completos

Exemplo

type student = recordname, address: stringage : integer

type school = recordname, address: stringage: integer

x : student;y : school;...x := y;

Page 259: Slides Da Disciplina Completos

Variações de Equivalência por Nome

new_type -> alias

Mesmo tipo ou tipos diferentes?

TYPE new_type = old_type;

Page 260: Slides Da Disciplina Completos

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;

Page 261: Slides Da Disciplina Completos

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;

Page 262: Slides Da Disciplina Completos

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

Page 263: Slides Da Disciplina Completos

Exemplo

subtype stack_element is integer;...type celsius_temp is new integer;type fahrenheit_temp is new integer;

Page 264: Slides Da Disciplina Completos

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

Page 265: Slides Da Disciplina Completos

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”

Page 266: Slides Da Disciplina Completos

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

Page 267: Slides Da Disciplina Completos

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>

Page 268: Slides Da Disciplina Completos

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

Page 269: Slides Da Disciplina Completos

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

Page 270: Slides Da Disciplina Completos

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

Page 271: Slides Da Disciplina Completos

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;

Page 272: Slides Da Disciplina Completos

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

Page 273: Slides Da Disciplina Completos

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?

Page 274: Slides Da Disciplina Completos

Type Tags

Tag: objeto guarda o seu tipo

C++: dynamic_cast

Page 275: Slides Da Disciplina Completos

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

Page 276: Slides Da Disciplina Completos

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

Page 277: Slides Da Disciplina Completos

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;

Page 278: Slides Da Disciplina Completos

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

Page 279: Slides Da Disciplina Completos

Records (Structs)

Armazenamento de dados heterogêneos

Normalmente: definem um tipo

Page 280: Slides Da Disciplina Completos

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

Page 281: Slides Da Disciplina Completos

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

Page 282: Slides Da Disciplina Completos

Utilização de Memória

Records aninhados:

Modelo por valor: cópia do record aninhado

Modelo por referência: cópia da referência

Page 283: Slides Da Disciplina Completos

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

Page 284: Slides Da Disciplina Completos

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

Page 285: Slides Da Disciplina Completos

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

Page 286: Slides Da Disciplina Completos

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

Page 287: Slides Da Disciplina Completos

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;

Page 288: Slides Da Disciplina Completos

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;

}

Page 289: Slides Da Disciplina Completos

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

Page 290: Slides Da Disciplina Completos

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

Page 291: Slides Da Disciplina Completos

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/))

Page 292: Slides Da Disciplina Completos

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

Page 293: Slides Da Disciplina Completos

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

Page 294: Slides Da Disciplina Completos

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

Page 295: Slides Da Disciplina Completos

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;

Page 296: Slides Da Disciplina Completos

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];

}}

}

Page 297: Slides Da Disciplina Completos

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”;

Page 298: Slides Da Disciplina Completos

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] ...}

}

Page 299: Slides Da Disciplina Completos

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)

Page 300: Slides Da Disciplina Completos

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’;

Page 301: Slides Da Disciplina Completos

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)]

Page 302: Slides Da Disciplina Completos

String

Vetor de caracteres

Operações limitadas

Tipo próprio

Mais operações

Page 303: Slides Da Disciplina Completos

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

Page 304: Slides Da Disciplina Completos

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

Page 305: Slides Da Disciplina Completos

Ponteiros

Variável cujo valor é uma referência

Ponteiro ≠ Endereço

Pascal: apenas objetos no heap

C, C++, Algol, Ada: operador “endereço de”

Page 306: Slides Da Disciplina Completos

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

Page 307: Slides Da Disciplina Completos

Java

Modelo intermediário

Tipos padrão: modelo de valor

Tipos definidos pelo usuário: modelo de referência

Page 308: Slides Da Disciplina Completos

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

Page 309: Slides Da Disciplina Completos

Modelo de ReferênciaLisp

Modelo de referência

Não é estaticamente tipada

‘(#\R (#\X () ()) (#\Y (#\Z ()()) (#\W ()())))

Page 310: Slides Da Disciplina Completos

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, ...};

Page 311: Slides Da Disciplina Completos

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

Page 312: Slides Da Disciplina Completos

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#

Page 313: Slides Da Disciplina Completos

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:

Page 314: Slides Da Disciplina Completos

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++

Page 315: Slides Da Disciplina Completos

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;

Page 316: Slides Da Disciplina Completos

Coletor de Lixo

Gerenciamento de memória:

Custoso para o programador

Fonte de erros

Coletor de lixo:

Recupera memória automaticamente

Como funciona?

Page 317: Slides Da Disciplina Completos

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

Page 318: Slides Da Disciplina Completos

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 ?

Page 319: Slides Da Disciplina Completos

“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

Page 320: Slides Da Disciplina Completos

“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

Page 321: Slides Da Disciplina Completos

“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

Page 322: Slides Da Disciplina Completos

1 2

3 4

Page 323: Slides Da Disciplina Completos

“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

Page 324: Slides Da Disciplina Completos

“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”

Page 325: Slides Da Disciplina Completos

Listas

Definição recursiva

Lista é:

lista vazia

par (objeto, lista)

Linguagens funcionais: muito utilizadas

Linguagens imperativas: disponíveis em scripts

Page 326: Slides Da Disciplina Completos

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}

Page 327: Slides Da Disciplina Completos

Rotinas e Abstrações de Controle

Page 328: Slides Da Disciplina Completos

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)

Page 329: Slides Da Disciplina Completos

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

Page 330: Slides Da Disciplina Completos

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

Page 331: Slides Da Disciplina Completos

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

Page 332: Slides Da Disciplina Completos

“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”

Page 333: Slides Da Disciplina Completos

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

Page 334: Slides Da Disciplina Completos

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

Page 335: Slides Da Disciplina Completos

Epílogo

Retorno de parâmetros

Código de finalização de objetos

Remoção da memória alocada

Recuperação dos registradores

Page 336: Slides Da Disciplina Completos

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

Page 337: Slides Da Disciplina Completos

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

Page 338: Slides Da Disciplina Completos

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

Page 339: Slides Da Disciplina Completos

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;}

Page 340: Slides Da Disciplina Completos

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

Page 341: Slides Da Disciplina Completos

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

Page 342: Slides Da Disciplina Completos

Exemplo

x : integer -- globalprocedure foo(y : integer)

y := 3print x

...x := 2foo(x)print x

Page 343: Slides Da Disciplina Completos

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

Page 344: Slides Da Disciplina Completos

Exemplo

x : integer -- globalprocedure foo(y : integer)

y := 3print x

...x := 2foo(x)print x

Page 345: Slides Da Disciplina Completos

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);

Page 346: Slides Da Disciplina Completos

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

Page 347: Slides Da Disciplina Completos

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

Page 348: Slides Da Disciplina Completos

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

Page 349: Slides Da Disciplina Completos

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

Page 350: Slides Da Disciplina Completos

Exemplo C

void append_to_log(const huge_record *r) {......append_to_log(&my_log);

O const vale para o valor apontado por r

Page 351: Slides Da Disciplina Completos

Exemplo: Ada

Três modos de passagem de parâmetros:

“in”: apenas de leitura

“out”: apenas de escrita

“in out”: escrita e leitura

Page 352: Slides Da Disciplina Completos

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;}

Page 353: Slides Da Disciplina Completos

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;

Page 354: Slides Da Disciplina Completos

Fechamentos como Parâmetros

Fechamentos:

rotina + contexto

Podem ser passados como parâmetros

Page 355: Slides Da Disciplina Completos

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);

Page 356: Slides Da Disciplina Completos

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

Page 357: Slides Da Disciplina Completos

Passagem de Arrays

Tempo de união da dimensão e limites

Execução: aberto ou “conformant”

Page 358: Slides Da Disciplina Completos

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);

Page 359: Slides Da Disciplina Completos

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

Page 360: Slides Da Disciplina Completos

Parâmetros Nomeados

put(item => 37, base => 8);

put(base => 8, item => 37);

put(37, base => 8);

Page 361: Slides Da Disciplina Completos

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);

Page 362: Slides Da Disciplina Completos

Número Variável de Argumentos

Número de argumentos indeterminado

Exemplo: printf e scanf

Recurso pouco comum: C/C++, Python, Lisp

Page 363: Slides Da Disciplina Completos

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);

}

Page 364: Slides Da Disciplina Completos

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

Page 365: Slides Da Disciplina Completos

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”

Page 366: Slides Da Disciplina Completos

Exemplo

Matlab: retorno nomeado e múltiplo

function [A, B, C] = foo()

A = 1;B = 2;C = 3;

Page 367: Slides Da Disciplina Completos

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

Page 368: Slides Da Disciplina Completos

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#

Page 369: Slides Da Disciplina Completos

Containers

Estrutura de dado

Armazenam outros dados

Exemplo: stack, queue, conjuntos, dicicionários

Tipo: genérico

Ada e C++

Page 370: Slides Da Disciplina Completos

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;

Page 371: Slides Da Disciplina Completos

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

Page 372: Slides Da Disciplina Completos

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

Page 373: Slides Da Disciplina Completos

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

Page 374: Slides Da Disciplina Completos

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

Page 375: Slides Da Disciplina Completos

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

Page 376: Slides Da Disciplina Completos

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#

Page 377: Slides Da Disciplina Completos

Exemplo

template<class T>void sort(T A[], int A_size) { ...

C++

Page 378: Slides Da Disciplina Completos

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);

Page 379: Slides Da Disciplina Completos

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

Page 380: Slides Da Disciplina Completos

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

Page 381: Slides Da Disciplina Completos

Exemplo

try {...if (algo_inesperado)

throw erro();...cout << “tudo ok” << endl;...

} catch (erro) {cout << “problema!” << endl;

}

Page 382: Slides Da Disciplina Completos

Exemplo

try {...foo();...cout << “tudo ok” << endl;...

} catch (erro) {cout << “problema!” << endl;

}

foo() {...if (algo_inesperado)

throw erro();...

}

Page 383: Slides Da Disciplina Completos

“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

Page 384: Slides Da Disciplina Completos

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

Page 385: Slides Da Disciplina Completos

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);

Page 386: Slides Da Disciplina Completos

Propagação de Exceções

try { // Tenta ler do arquivo...// Código complicado de leitura...

} catch(end_of_file) {...

} catch(io_error e) {...

} catch(...) {...

}

Page 387: Slides Da Disciplina Completos

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;

Page 388: Slides Da Disciplina Completos

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

Page 389: Slides Da Disciplina Completos

Exemplo

if (!setjmp(buffer)) {/* código protegido */

} else {/* handler */

}

Page 390: Slides Da Disciplina Completos

Abstração de Dados e Orientação a Objetos

Page 391: Slides Da Disciplina Completos

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

Page 392: Slides Da Disciplina Completos

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

Page 393: Slides Da Disciplina Completos

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

Page 394: Slides Da Disciplina Completos

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

Page 395: Slides Da Disciplina Completos

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

Page 396: Slides Da Disciplina Completos

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)

Page 397: Slides Da Disciplina Completos

Introdução

Linguagens OO modernas:

Eiffel, C++, Modula-3, Ada 95, Fortran 2003, Python, Ruby, Java e C#

Objective-C:

Mensagens de Smalltalk + C

Page 398: Slides Da Disciplina Completos

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

Page 399: Slides Da Disciplina Completos

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

Page 400: Slides Da Disciplina Completos

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

Page 401: Slides Da Disciplina Completos

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”);}

};

Page 402: Slides Da Disciplina Completos

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

Page 403: Slides Da Disciplina Completos

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”)

}};

Page 404: Slides Da Disciplina Completos

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

Page 405: Slides Da Disciplina Completos

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”);}

};

Page 406: Slides Da Disciplina Completos

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

Page 407: Slides Da Disciplina Completos

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

Page 408: Slides Da Disciplina Completos

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

Page 409: Slides Da Disciplina Completos

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#

Page 410: Slides Da Disciplina Completos

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

Page 411: Slides Da Disciplina Completos

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

Page 412: Slides Da Disciplina Completos

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;

}};

Page 413: Slides Da Disciplina Completos

Classe Base de Propósito Geral

list_node:

valor armazenado tem que ser inteiro

Como fazer uma classe base mais geral?

Page 414: Slides Da Disciplina Completos

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;}

};

Page 415: Slides Da Disciplina Completos

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

Page 416: Slides Da Disciplina Completos

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;

}}

};

Page 417: Slides Da Disciplina Completos

Exemplo

class int_list_node : public_list_node {public:

...void remove() {

try{gp_list_node::remove();

} catch(list_err) {// não faz nada

}};

Page 418: Slides Da Disciplina Completos

Acessando Membros da Classe Base

gp_list_node::remove(); // C++super.remove(); // Javabase.remove(); // C#super remove. // Smalltalk[super remove] // Objective C

Page 419: Slides Da Disciplina Completos

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

Page 420: Slides Da Disciplina Completos

Encapsulamento e Herança

Mecanismos de encapsulamento:

agrupamento de dados e sub-rotinas

classe como gerente

Page 421: Slides Da Disciplina Completos

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

Page 422: Slides Da Disciplina Completos

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

Page 423: Slides Da Disciplina Completos

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;

Page 424: Slides Da Disciplina Completos

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

Page 425: Slides Da Disciplina Completos

Exemplo

my_stack.push(x); push(my_stack, x);

Page 426: Slides Da Disciplina Completos

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

Page 427: Slides Da Disciplina Completos

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?

Page 428: Slides Da Disciplina Completos

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

Page 429: Slides Da Disciplina Completos

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

Page 430: Slides Da Disciplina Completos

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

Page 431: Slides Da Disciplina Completos

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

Page 432: Slides Da Disciplina Completos

Regras de Visibilidade: C++

Classe derivada que limita a visibilidade de membros de classe base protegida/privada pode restaurar visibilidade de membros específicos

Page 433: Slides Da Disciplina Completos

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

Page 434: Slides Da Disciplina Completos

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”

Page 435: Slides Da Disciplina Completos

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

}}

Page 436: Slides Da Disciplina Completos

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

Page 437: Slides Da Disciplina Completos

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;

Page 438: Slides Da Disciplina Completos

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;

Page 439: Slides Da Disciplina Completos

Exemplo

Package child em Ada 95:

parecido com classe derivada

mas gerencia um tipo

Abordagens similar: classes em Python

Page 440: Slides Da Disciplina Completos

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();

Page 441: Slides Da Disciplina Completos

Inicialização e Finalização

Linguagens OO:

inicializam e finalizam objetos

Inicialização: método construtor

Finalização: método destrutor

Page 442: Slides Da Disciplina Completos

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

Page 443: Slides Da Disciplina Completos

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

Page 444: Slides Da Disciplina Completos

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

Page 445: Slides Da Disciplina Completos

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

Page 446: Slides Da Disciplina Completos

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)

Page 447: Slides Da Disciplina Completos

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

Page 448: Slides Da Disciplina Completos

Construtores em C++

foo b; // chama foo::foo()foo b(10, ‘x’); // chama foo::foo(int, char)

Page 449: Slides Da Disciplina Completos

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 &)

Page 450: Slides Da Disciplina Completos

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;=

Page 451: Slides Da Disciplina Completos

Exemplo: Eiffel

Todas as variáveis são inicializadas com um valor default

Inclusive atributos de classes

Page 452: Slides Da Disciplina Completos

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 );...

Page 453: Slides Da Disciplina Completos

Construção de Atributos

C++:

permite escolha dos valores iniciais dos atributos

list_node() : prev(this), next(this), head_node(this), val(0) {};

Page 454: Slides Da Disciplina Completos

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

Page 455: Slides Da Disciplina Completos

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 );

Page 456: Slides Da Disciplina Completos

Exemplo: Java

Modelo de referência:

atributos que são classes: inicialização para null

Inicialização explícita no construtor

Page 457: Slides Da Disciplina Completos

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;

}}

}

Page 458: Slides Da Disciplina Completos

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

Page 459: Slides Da Disciplina Completos

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;

Page 460: Slides Da Disciplina Completos

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(); // ??

Page 461: Slides Da Disciplina Completos

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()

Page 462: Slides Da Disciplina Completos

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

Page 463: Slides Da Disciplina Completos

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

Page 464: Slides Da Disciplina Completos

União Dinâmica Opcional

União estática

Método redefinido

União dinâmica

Método sobrecarregado

Page 465: Slides Da Disciplina Completos

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();...

}

Page 466: Slides Da Disciplina Completos

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

Page 467: Slides Da Disciplina Completos

Exemplo

abstract class person {...public abstract void print_data();...

C#

class person {...virtual void print_data() = 0;...

C++

Page 468: Slides Da Disciplina Completos

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

Page 469: Slides Da Disciplina Completos

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

Page 470: Slides Da Disciplina Completos

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

Page 471: Slides Da Disciplina Completos

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);

Page 472: Slides Da Disciplina Completos

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

Page 473: Slides Da Disciplina Completos

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)

Page 474: Slides Da Disciplina Completos

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...

Page 475: Slides Da Disciplina Completos

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”);}

};

Page 476: Slides Da Disciplina Completos

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

Page 477: Slides Da Disciplina Completos

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!

Page 478: Slides Da Disciplina Completos

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) {......

};

Page 479: Slides Da Disciplina Completos

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

Page 480: Slides Da Disciplina Completos

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;

}};

Page 481: Slides Da Disciplina Completos

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

Page 482: Slides Da Disciplina Completos

Fechamento de Objetos

Fechamento de objetos para simular fechamento de rotinas

Fechamento: Método + Contexto

Page 483: Slides Da Disciplina Completos

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);

Page 484: Slides Da Disciplina Completos

Armazenando Argumentos

Aplicação de fechamento de objetos

Fechamento: função + alguns argumentos

Armazena os argumentos para uso posterior

Page 485: Slides Da Disciplina Completos

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);

Page 486: Slides Da Disciplina Completos

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)

Page 487: Slides Da Disciplina Completos

Smalltalk

Linguagem OO canônica

Estruturas de controle são objetos

Ambiente de programação é um objeto

editor

interpretador

Page 488: Slides Da Disciplina Completos

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

Page 489: Slides Da Disciplina Completos

Parte IIIScripts

Page 490: Slides Da Disciplina Completos

Introdução

Linguagens tradicionais:

aplicações auto-contidas

Problema comum:

coordenação entre de diversos programas

Ex.: sistema de folha de pagamento

Page 491: Slides Da Disciplina Completos

IntroduçãoMotivação inicial: juntar programas

Foco:

flexibilidade

desenvolvimento rápido

adaptações locais

verificações em tempo de execução

bibliotecas

Page 492: Slides Da Disciplina Completos

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)

Page 493: Slides Da Disciplina Completos

Server-Side

Controle sobre o conteúdo da página

Uso computacional intensivo

Manipulação de dados sigilosos

Page 494: Slides Da Disciplina Completos

Client-Side

Precisam acessar informações locais

Tempo de execução é crítico

Exemplo: animações, verificação de erros

Page 495: Slides Da Disciplina Completos

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

Page 496: Slides Da Disciplina Completos

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”;

Page 497: Slides Da Disciplina Completos

Desvantagens:

cada acesso: programa separado

instalação em diretórios especiais

cada script precisa gerar o código HTML

Scripts CGI

Page 498: Slides Da Disciplina Completos

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

Page 499: Slides Da Disciplina Completos

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>

Page 500: Slides Da Disciplina Completos

Client-Side Scripts

Necessitam de um interpretador no cliente

Linguagens mais restritas

Mais popular: JavaScript

Page 501: Slides Da Disciplina Completos

Python

Criado no final dos anos 80s

Interpretada

Imperativa (influenciada por ling. funcionais)

Foco:

código legível

facilidade na programação

Page 502: Slides Da Disciplina Completos

Interpretador

Executa código linha por linha

Forma rápida de testar código

Código pode ser armazenado num arquivo

Page 503: Slides Da Disciplina Completos

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

Page 504: Slides Da Disciplina Completos

Tipos Básicos

string = ‘two’ # stringf = 2.0 # ponto flutuantei = 2 # inteirob = True # booleanoc = 1 + 1j # complexo

Page 505: Slides Da Disciplina Completos

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.: +=, -= ,...

Page 506: Slides Da Disciplina Completos

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

Page 507: Slides Da Disciplina Completos

Operações Lógicas

Igualdade: ==

Diferente: !=

Menor/maior: >, <

Operadores lógicos: not, and, or

Page 508: Slides Da Disciplina Completos

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

Page 509: Slides Da Disciplina Completos

Tipos de Escopo

Global

Local

Classe

Page 510: Slides Da Disciplina Completos

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

Page 511: Slides Da Disciplina Completos

Estruturas de Controle

Repetição com controle lógico:

while

Sequenciamento:

if / elif

Repetição por enumeração:

for

Page 512: Slides Da Disciplina Completos

while

contador = 3while contador > 0:

print contadorcontador -= 1

Page 513: Slides Da Disciplina Completos

if / elif

temp = 23if temp < 18:

print ‘frio’elif temp > 28:

print ‘calor’else:

print ‘normal’

Page 514: Slides Da Disciplina Completos

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

Page 515: Slides Da Disciplina Completos

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

Page 516: Slides Da Disciplina Completos

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

Page 517: Slides Da Disciplina Completos

Listas Aninhadas

pessoa1 = [‘Joao’, 20]pessoa2 = [‘Jose’, 30]dados = [pessoa1, pessoa2]dados[0][1] = 21print pessoa1[1] # 21

Page 518: Slides Da Disciplina Completos

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

Page 519: Slides Da Disciplina Completos

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

Page 520: Slides Da Disciplina Completos

Iterando sobre Listas

loop for

itera sobre elementos de uma lista

l = [1, ‘Joao’, 1+1j, 3.5]for item in l:

print item

Page 521: Slides Da Disciplina Completos

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]

Page 522: Slides Da Disciplina Completos

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!

Page 523: Slides Da Disciplina Completos

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]

Page 524: Slides Da Disciplina Completos

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

Page 525: Slides Da Disciplina Completos

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

Page 526: Slides Da Disciplina Completos

Set

Parecido com dicionário

Não possui elementos repetidos

Não tem “chave”

Page 527: Slides Da Disciplina Completos

Tuple

t = (1, ‘a’, c)

t[0] == 1

t[1] == ‘a’

Tuple é imutável:

t[0] = 2 # ERRO!

Page 528: Slides Da Disciplina Completos

Tuple

Parênteses podem ser omitidos

t = 1, 2, 3

Tuple pode ser desempacotado:

item1, item2, item3 = t

item1, item2, item3 = 1, 2, 3

Page 529: Slides Da Disciplina Completos

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

Page 530: Slides Da Disciplina Completos

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

Page 531: Slides Da Disciplina Completos

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

Page 532: Slides Da Disciplina Completos

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

Page 533: Slides Da Disciplina Completos

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

Page 534: Slides Da Disciplina Completos

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)

Page 535: Slides Da Disciplina Completos

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

Page 536: Slides Da Disciplina Completos

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

Page 537: Slides Da Disciplina Completos

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)

Page 538: Slides Da Disciplina Completos

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])

Page 539: Slides Da Disciplina Completos

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’)

Page 540: Slides Da Disciplina Completos

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)

Page 541: Slides Da Disciplina Completos

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

Page 542: Slides Da Disciplina Completos

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])

Page 543: Slides Da Disciplina Completos

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

Page 544: Slides Da Disciplina Completos

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

Page 545: Slides Da Disciplina Completos

Métodos

class Vazia(object):

def nada(self):print “Nada”

>>> nada_1 = Vazia()>>> nada_1.nada() # Nada>>> nada_1.nada() # Chamada: nada(nada_1)

Page 546: Slides Da Disciplina Completos

Atributos

class Greeter(object):

def greet(self, name):print self.hello + name + ‘!’

>>> g = Greeter()>>> g.hello = ‘Ola, ’>>> g.greet(‘Joao’) # Ola, Joao!

Page 547: Slides Da Disciplina Completos

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!’

Page 548: Slides Da Disciplina Completos

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

Page 549: Slides Da Disciplina Completos

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

Page 550: Slides Da Disciplina Completos

Exemplo

Sinal amostrado irregularmente

Esconder a amostragem irregular

Como reamostrar o sinal?

Constante por partes

Interpolação linear

Filtro mais sofisticado

Page 551: Slides Da Disciplina Completos

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

Page 552: Slides Da Disciplina Completos

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’)

Page 553: Slides Da Disciplina Completos

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’)

Page 554: Slides Da Disciplina Completos

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

Page 555: Slides Da Disciplina Completos

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)

Page 556: Slides Da Disciplina Completos

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’)

Page 557: Slides Da Disciplina Completos

Exemplo

class SinalDegrau(SinalInterpolado):

def __init__(self, values):self.values = values

def get(self, where):i = self.find(where)return self.values[i][1]

Page 558: Slides Da Disciplina Completos

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’)

Page 559: Slides Da Disciplina Completos

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)

Page 560: Slides Da Disciplina Completos

Sobrecarga

Classe para vetores

Sobrecarga:

len(vec)

vec[i]

Page 561: Slides Da Disciplina Completos

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’)

Page 562: Slides Da Disciplina Completos

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)

Page 563: Slides Da Disciplina Completos

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’)

Page 564: Slides Da Disciplina Completos

Outros Métodos

__add__

__sub__

__mul__ (__rmul__)

__str__

__iter__

Page 565: Slides Da Disciplina Completos

Iteradores

Duas formas:

objetos iteradores

geradores (generators)

Vamos ver objetos iteradores

Page 566: Slides Da Disciplina Completos

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

Page 567: Slides Da Disciplina Completos

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)