Upload
dangduong
View
214
Download
0
Embed Size (px)
Citation preview
FCT-UNESP 04/07/2017
Prof. Dr. Rogério E. Garcia 1
Faculdade de Ciências e TecnologiaDepartamento de Matemática e Computação
Bacharelado em Ciência da Computação
Conceitos de Linguagens de Programação
Aula 06
Rogério Eduardo Garcia([email protected])
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
2
Aula 6
Subprogramas
FCT-UNESP 04/07/2017
Prof. Dr. Rogério E. Garcia 2
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
3Linguagens de Programação: hierarquia de componentes
Tipos de Dados
Expressões
Comandos
Unidades
Programas
representação e operações
obtenção de valores
fluxo de controle
ambientes: abstrações de valores e comandos
unidade de execução
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
4
Unidades [Ghezzi]
Estruturas de controle no nível de unidades– Unidades subordinadas chamadas explicitamente
Procedimentos, funções, métodos
– Unidades chamadas implicitamente Tratamento de exceções
– Unidades simétricas Co-rotinas
– Unidades concorrentes
FCT-UNESP 04/07/2017
Prof. Dr. Rogério E. Garcia 3
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
5
Semântica
síncrono
P Q
P Q
assíncrono
t1 call
t2
ret
t3
t1 call
t2
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
6
Semântica
"handshake"
P Q
P Q
"future"t2
t1 call
t1t2
t3
call
ack
datat3
t4
FCT-UNESP 04/07/2017
Prof. Dr. Rogério E. Garcia 4
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
7
Semântica
cooperativo
P Q
t1 call
yield
t3 call t4
t2
yield
t5
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
8
Unidades [Sebesta]
Blocos
Subprogramas
Co-rotinas
Unidades concorrentes
Tratadores de exceções
FCT-UNESP 04/07/2017
Prof. Dr. Rogério E. Garcia 5
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
9
Mecanismos de Abstração em LPs
Mecanismos de abstração– Abstração de processo
– Abstração de dados
Um subprograma é um tipo de abstração deprocesso– Instruções para realizar uma tarefa são agrupadas
e tratadas como uma unidade lógica
– O conceito economiza espaço e esforço dedesenvolvimento e codificação
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
10
Subprogramas
Características fundamentais– Cada subprograma possui um único ponto de entrada
– O chamador tem a sua execução suspensa durante aexecução do subprograma
– O fluxo de controle sempre retorna ao ponto de chamadaquando termina a execução do subprograma
mesmo ambiente, único fluxo
FCT-UNESP 04/07/2017
Prof. Dr. Rogério E. Garcia 6
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
11
Subprogramas: Definições básicas
A definição de um subprograma consiste nadescrição de seu cabeçalho e de seu corpo– O cabeçalho de um subprograma inclui tipo do
subprograma, nome, parâmetros formais, tipo deretorno
– O corpo de um subprograma é a descrição dasações da abstração do subprograma
A chamada de um subprograma é umarequisição explícita para que o subprogramaseja executado
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
12
Subprogramas: Definições básicas
A declaração de um subprograma é umadescrição do tipo de abstração(função/procedimento), seu nome e seusparâmetros formais (cabeçalho)
Um parâmetro formal é uma variável queaparece no cabeçalho do subprograma e éusada no corpo do subprograma
Um parâmetro real representa um valor ouendereço usado na chamada do subprograma
FCT-UNESP 04/07/2017
Prof. Dr. Rogério E. Garcia 7
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
13
Tipos de Subprogramas: procedimentos e funções
Um procedimento atua como um novocomando definido pelo usuário– Resultados produzidos via parâmetros ou variáveis
não locais
Uma função atua como um novo operadordefinido pelo usuário– Função sem efeitos colaterais
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
14
Questões de Projeto de Subprogramas
Variáveis locais: estáticas ou semi-estáticas?
Parâmetros– Correspondência
– Métodos de passagem
– Verificação de tipos
Subprogramas passados para outro subprograma– Ambiente de referência
– Verificação de tipos em parâmetros
Definição de unidades aninhadas
Sobrecarga de subprogramas
Subprogramas genéricos
FCT-UNESP 04/07/2017
Prof. Dr. Rogério E. Garcia 8
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
15
Variáveis Locais
Semi-estáticas (dinâmicas de pilha):
– Vantagens:a. Suporte a recursão
b. Memória para variáveis locais é compartilhada entrealguns subprogramas
– Desvantagens:a. Tempo de alocação, desalocação
b. Endereçamento Indireto
c. Subprogramas não podem manter "história"
Estáticas
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
16
Variáveis Locais
Exemplos:– 1. FORTRAN 77 - estáticas
– 2. C - static , default é semi-estática
– 3. Pascal, Java e Ada - semi-estática
FCT-UNESP 04/07/2017
Prof. Dr. Rogério E. Garcia 9
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
17
Parâmetros: Correspondência
Correspondência entre parâmetros– Por posição (positional parameters): mapeiam
parâmetros formais e reais em função de suaordem na lista de parâmetros
– Por palavra-chave (keyword parameters): mapeiamparâmetros formais e reais através de nomes
Exemplo: por posição
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
18
Correspondência por palavra-chave
Exemplo– Declaração:
procedure SORT(LIST : LIST_TYPE;
LENGTH : INTEGER := 100);
– Chamada 1: SORT(LIST => A, LENGTH => N);
– Chamada 2: SORT(LIST => A);
Avaliação– Correspondência por palavra-chave promove maior
legibilidade e confiabilidade
FCT-UNESP 04/07/2017
Prof. Dr. Rogério E. Garcia 10
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
19Métodos de passagem de parâmetros
Modelos semânticos– in mode, out mode, inout mode
Modelos conceituais de transferência– Mover o valor ("fisicamente")
– Mover um caminho de acesso par o valor
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
20
Modelos de Passagem de Parâmetros"mover valor"
FCT-UNESP 04/07/2017
Prof. Dr. Rogério E. Garcia 11
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
21Métodos de passagem de parâmetros
Modelos de implementação– Passagem por valor
– Passagem por resultado
– Passagem por valor-resultado
– Passagem por referência
– Passagem por nome
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
22
Passagem por valor
Ou por passagem física ou por caminho
Desvantagem de acesso por caminho:– Deve-se proteger contra gravação no subprograma
chamado
– Acessos custam mais (endereçamento indireto)
Desvantagem em cópia física:– Requer maior armazenamento (espaço duplicado)
– Custo de transferência (para parâmetros grandes)
FCT-UNESP 04/07/2017
Prof. Dr. Rogério E. Garcia 12
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
23
Passagem por valor
Modo de entrada
Parâmetros são copiados em um novo local(armazenamento) no subprograma quandoele começa. Do ponto de vista dosubprograma, o acesso é eficiente, mas acópia não
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
24
Passagem por resultado
Modo de saída
O resultado em um subprograma é copiado noparâmetro atual quando o subprogramaretorna
Pode causar problema quando o mesmoparâmetro é mapeado para múltiplosparâmetros formais, ou quando o parâmetroatual é uma constante, que pode ser alteradaquando o programa retorna
FCT-UNESP 04/07/2017
Prof. Dr. Rogério E. Garcia 13
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
25
Passagem por valor-resultado
Modo In-out
Combina passagem por valor e passagem porresultado. Também chamado passagem porcópia
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
26
Passagem por referência
Modo In-out
Diferente da passagem-por-valor-resultado,um caminho de acesso a dado é passado parao subprograma, não o dado em si
Passagem de parâmetros é eficiente, mas oacesso não
Pode introduzir alias “inesperado” quando umparâmetro atual é mapeado para diferentesparâmetros formais, ou quando uma variávelglobal é passada a um subprograma onde aprópria variável global é visível
FCT-UNESP 04/07/2017
Prof. Dr. Rogério E. Garcia 14
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
27
Passagem por nome
Modo In-out
A ocorrência de um parâmetro formal é textualmente trocada peloparâmetro atual
O método de acesso é ligado à invocação do subprograma, mas aavaliação acontece cada vez que o parâmetro formal éencontrado
Se o parâmetro atual é uma variável escalar, então a passagempor nome tem o mesmo comportamento da passagem porreferência
Se o parâmetro atual é uma constante, é equivalente a passagempor valor
Se o parâmetro atual é a referência para um array ou umaexpressão com variáveis, então ela é avaliada cada vez que éencontrada. Isso é chamado de avaliação preguiçosa ou ligaçãotardia (late binding)
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
28
Implementação
Todos os principais métodos de passagem deparâmetro podem ser implementados por meio depilhas
Há diferenças entre passagem por referência e porvalor-resultado, sendo que neste último é alocadoespaço para o armazenamento (completo) doparâmetro formal. As alterações feitas no parâmetroatual são visíveis somente quando o subprogramatermina, mas na passagem por referência reflete asalterações passo a passo
Passagem por nome é implementada como umamáscara em segmento de código, que é ligada aoambiente de referência quando o subprograma échamado, e é avaliado para cada ocorrência doparâmetro formal
FCT-UNESP 04/07/2017
Prof. Dr. Rogério E. Garcia 15
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
29
Exemplo
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
30
Funções como parâmetros
O protótipo de ver checado para o parâmetro atual,que é um subprograma
A referência para o subprograma A que é passadopara outro subprograma B pode ser:
– Binding Superficial – o ambiente (em B) A é chamado
– Binding em profundidade – o ambiente A é definido
– Binding Ad Hoc – o ambiente onde A é passado para B (ondeB é chamado)
Bloco estruturado geralmente usa deep binding parafacilitar a adoção de escopo estático
FCT-UNESP 04/07/2017
Prof. Dr. Rogério E. Garcia 16
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
31
Parâmetros que são Subprogramas
Questões:1. Os parâmetros são checados?
– Primeiras versões de Pascal e FORTRAN 77 não
– Versões posteriores de Pascal e FORTRAN 90 sim
– Ada não permite parâmetros em subprogramas
– Java não permite nomes de métodos serempassados como parâmetros
– C e C++ passam ponteiros para funções;parâmetros podem ser checados
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
32
F(g): g é um ponteiro para a função g(parametros)int f(*p())
{Chama-se p
}
int g(int x)
{...
}
main()
{f(g)
}
FCT-UNESP 04/07/2017
Prof. Dr. Rogério E. Garcia 17
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
33
Parâmetros que são Subprogramas
2. Qual é o ambiente de referência correto paraum subprograma que foi mandado comoparâmetro?
– Possibilidades:a. É aquele que executou o subprograma
Binding Superficial (shallow binding)
b. É aquele que declarou o subprograma Binding em Profundidade (deep binding)
c. É aquele que passou Binding Ad hoc (nunca usado)
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
34
Parâmetros que são subprogramas
Para linguagens de escopo estático, deepbinding é mais natural
Para linguagens de escopo dinâmico shallowbinding é mais natural
FCT-UNESP 04/07/2017
Prof. Dr. Rogério E. Garcia 18
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
35
Exemplo: sub1sub2sub3
call sub4(sub2)sub4(subx)call subx
call sub3
Qual é o ambiente de referencia do sub2 quando ele échamado em sub4?
– Shallow binding => sub2, sub4, sub3, sub1
– Deep binding => sub2, sub1
Parâmetros que são subprogramas
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
36
Sobrecarga de subprogramas
Subprogramas que têm o mesmo nome, masdiferentes protótipos
Em Ada o compilador pode distinguir o usopelo tipo de retorno, portanto o protótipocompleto deve ser considerado
FCT-UNESP 04/07/2017
Prof. Dr. Rogério E. Garcia 19
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
37
Subprogramas Genéricos
Polimorfismo significa que a mesma construção podeter significado diferente de acordo com o contexto
– Polimorfismo Ad hoc – sobrecarga de operadores
– Polimorfismo Paramétrico – um “programa” genérico quefunciona com diferentes tipos de variáveis, de acordo com osparâmetros recebidos
Em Ada– Unidade genérica para um programa que implementa
polimorfismo paramétrico
Em C++– Chamado de template em C++ e provê flexibilidade de
programação
– As funções são “construídas” pelo uso (no header file, não nocódigo fonte)
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
38
Aspectos de Projetos para Funções
1. Efeitos colaterais são permitidos?a. Parâmetros Two-way (Ada não permite)
b. Referência não-local (todas pertmitem)
2. Quais tipos de retorno são permitidos?
FCT-UNESP 04/07/2017
Prof. Dr. Rogério E. Garcia 20
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
39
Co-rotinas
O controle é trocado entre vários processos
Um processo é “resumed”, e não há retorno
Geralmente um processo master cria outrosprocessos, e distribui o controle entre eles
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
40
Esquema
FCT-UNESP 04/07/2017
Prof. Dr. Rogério E. Garcia 21
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
41
Exemplo
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
42
Exemplo
FCT-UNESP 04/07/2017
Prof. Dr. Rogério E. Garcia 22
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
43
Abstrações: suporte
Abstração procedimental (subprogramas/métodos)– modos de passagem de parâmetros
– ambientes de referência: local e global, escopo evisibilidade de componentes
– proteção de componentes locais
– sobrecarga de operadores e polimorfismo
– unidades genéricas
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
44
Semântica de chamadas e retornos
A ligação de subprogramas exige armazenamento deinformações sobre:
– estado da execução no ponto de chamada
– passagem de parâmetros, dependendo do modo
– ambiente global de execução
– ambiente local de execução
– endereço de retorno
Informações são organizadas em um registro deativação
A cada ativação é criada uma instância do registro deativação e colocada na pilha de execução
FCT-UNESP 04/07/2017
Prof. Dr. Rogério E. Garcia 23
04
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
45Abstração procedimental: execução
Requisição
A execução ocorre quando éfeita uma chamada
Uma unidade requisita aexecução de outra unidade(chamada)
A unidade requisitantesuspende sua execução eaguarda o término daexecução da unidadechamada
Parâmetros
As definições/chamadaspodem ser parametrizadas
Parâmetros reais: valorespassados à unidade chamada(argumentos)
Parâmetros formais:descrição dos tipos de dadosque a abstração pode receber
Tipo da abstração: tipo deresultado da execução