Notas de Aula Cap. 8 a 13 Conceitos de Linguagens de Programação (Sebesta, Robert W.; Conceitos de Linguagens de Programação; Editora Bookman, 3º ed.) Jorge Habib Hanna El Khouri Unioeste – Foz do Iguaçu Centro de Engenharias e Ciências Exatas Ciência da Computação Foz do Iguaçu, Junho de 2013 Sumário 9 IMPLEMENTANDO SUB-PROGRAMAS ..................................................................................... 3 9.1 Definições .................................................................................................................................. 3 9.2 SUB-PROGRAMA EM FORTRAN 77 ................................................................................... 3 9.3 SUB-PROGRAMA EM LINGUAGEM DO TIPO ALGOL .................................................... 3 10 TIPOS ABSTRATOS DE DADOS .............................................................................................. 5 10.1 Definições .................................................................................................................................. 5 10.2 TIPOS ABSTRATOS DE DADOS DEFINIDOS PELO USUÁRIO ...................................... 6 10.3 EXEMPLOS DE LINGUAGENS ............................................................................................. 6 10.3.1 ADA ................................................................................................................................... 6 10.3.2 C++ .................................................................................................................................... 7 10.4 TIPOS ABSTRATOS DE DADOS PARAMETRIZADOS ..................................................... 7 10.4.1 ADA: .................................................................................................................................. 7 10.4.2 C++: ................................................................................................................................... 7 11 SUPORTE À PROGRAMAÇÃO ORIENTADA Á OBJETO ..................................................... 8 11.1 Introdução .................................................................................................................................. 8 11.2 Definições em OOP: .................................................................................................................. 8 11.3 C++ ............................................................................................................................................ 9 11.4 Java .......................................................................................................................................... 10 12 CONCORRÊNCIA ..................................................................................................................... 11 12.1 Introdução ................................................................................................................................ 11 12.1.1 CATEGORIA DE CONCORRÊNCIA ............................................................................ 11 12.2 Concorrência em Nível de Subprograma ................................................................................ 11 12.3 Sincronização .......................................................................................................................... 12 12.4 CO-ROTINAS ......................................................................................................................... 12 12.5 Projeto de Linguagem para Concorrência ............................................................................... 13 12.5.1 SEMÁFAROS .................................................................................................................. 13 12.5.2 MONITORES .................................................................................................................. 13 12.6 THREADS EM JAVA ............................................................................................................ 14 13 TRATAMENTO DE EXCEÇÕES ............................................................................................. 15 13.1 Conceitos ................................................................................................................................. 15 13.2 CONSIDERAÇÕES NO PROJETO DO TRATADOR DE EXCEÇÃO ............................... 17 13.3 HISTÓRIA DE EXCEÇÕES DEFINIDAS PELO USUÁRIO .............................................. 17 14 REFERÊNCIAS .......................................................................................................................... 18 Conceitos de Linguagens de Programação - ii - 9 IMPLEMENTANDO SUB-PROGRAMAS 9.1 Definições A chamada e o retorno de um subprograma são chamados de ligação de um subprograma. • • • • • ALGOL 60 e a maioria das descendentes utilizam a pilha do run-time; Valor copia o dado para a pilha; acessos são indiretos via pilha; Resultado idem; Referência coloca o endereço na pilha; Nome o segmentos de código (chamado de thunks) ou subprogramas residentes em tempo de execução avaliam o endereço do parâmetro; o código chamado a cada referência ao parâmetro formal; o Muito dispendioso se comparado á referência ou valor-resultado. 9.2 SUB-PROGRAMA EM FORTRAN 77 Semântica da Chamada: 1. 2. 3. 4. Salva o estado de execução do chamador; Efetiva o processo de passagem de parâmetro; Passa o endereço de retorno; Transfere o controle para o chamado; Semântica de retorno: 1. Se passagem de parâmetro do tipo valor-resultado, move parâmetros ==> argumentos; 2. Se é uma function, move resultado ==> local que o chamador possa pegá-lo; 3. Restaura o estado de execução do chamador; 4. Transfere controle para chamador; • Registro de ativação = formado da parte não-código de um sub-programa • Instância de um RA = coleção de dados para uma determinada ativação do subprograma; • FORTRAN 77: Sub-programa possui apenas um RA - Impede recursão; 9.3 SUB-PROGRAMA EM LINGUAGEM DO TIPO ALGOL • Mais complicado que FORTRAN 77 porque: • Parâmetros são passados por mais de um método; • Variáveis locais são alocadas dinamicamente; • Deve suportar recursão; • Deve suportar escopo estático; Conceitos de Linguagens de Programação -3- • Registro de Ativação de uma linguagem do tipo Algol: • • • • • • Parâmetros; Link Estático; Endereço de retorno; Link Dinâmico; Resultado da Função; Variáveis Locais; Chamador Chamado • Formato estático, mas tamanho dinâmico; • Instância do RA criado dinamicamente com a chamada; • Link Estático • • Aponta para a base da instância de um RA de uma ativação do pai estático; É utilizado para acesso a variáveis nao-local; • Link Dinâmico: • • • Aponta para o topo da instância do RA do chamador; Representa o encadeamento de chamadas e a história dinâmica de como a execução chegou à sua posição atual; Observar na lista de exercícios como é feito o acesso a variáveis não-locais para o escopo estático; Conceitos de Linguagens de Programação -4- 10 TIPOS ABSTRATOS DE DADOS 10.1 Definições ABSTRAÇÃO • • • Uma abstração é uma visualização de uma entidade, pode-se dividir em: • Abstração de processo (ex. funções ) • Abstração de dados É uma representação de um objeto que considera apenas os atributos relevantes do objeto original, ignorando os detalhes menos importantes; Em programação, é a arma contra complexidade; ABSTRAÇÃO DE PROCESSO - CAP 8 e 9 • • Abstração de processo é dado por sub-programas. O programador pode especificar o processo a ser realizado sem entrar em detalhes. Exemplo: sort (list, list_len). Os atributos essenciais (detalhes) são o nome do processo (sort), o nome do array a ser ordenado (list) e o comprimento da lista (lista_len). ENCAPSULAMENTO • • Quando um programa fica demasiado grande, existem duas soluções: • Dividi-lo em módulos. (aumentar a legibilidade); • Dividi-lo em Unidades de compilação independentes. (aumentar a eficiência do desenvolvimento). É obtido através do agrupamento lógico de sub-programas e dados em um arquivo ou biblioteca. Dois aspectos se destacam: agrupamento e ocultação. TIPO ABSTRATO DE DADOS É: 1. Um conjunto de objetos de dados; 2. Um conjunto de operações abstratas sobre estes objetos de dados; 3. Encapsulamento do todo de tal forma que o usuário do novo tipo não pode manipular os objetos de dados do tipo, exceto através das operações definidas. O usuário do TAD necessita apenas conhecer o nome do tipo e a semântica das operações envolvidas. Exemplo: floating point é um TAD Nome: float Operações: +, -, *, /, **, >, <, := VANTAGENS DA ABSTRAÇÃO: 1. Proporciona um meio de dividir o programa em unidades lógicas que podem ser compiladas separadamente; Conceitos de Linguagens de Programação -5- 2. Modificação na representação ou nas operações de um tipo são feitas em um único local do programa; 3. Os detalhes do tipo são ocultados do resto do programa de tal forma que a representação do tipo pode modificar sem afetar o resto do programa; 4. Aumenta a confiabilidade porque o programador não pode alterar as representações básicas. Assim, a integridade do objeto permanece inalterada; 10.2 • TIPOS ABSTRATOS DE DADOS DEFINIDOS PELO USUÁRIO A linguagem permite que o usuário defina seu próprio TAD. • Tem que satisfazer as seguintes condições: • A representação e as operações sobre objetos estão contidas numa única unidade sintática. • Outras unidades do programa podem ter permissão para criar variáveis do tipo definido. • Não é visível a representação do tipo de dados às unidades que a utilizam. • As únicas operações possíveis são aquelas oferecidas na sua definição. • As unidade que as utilizam são chamadas Clientes. • Exemplo: name of object - stack operations on object: create (stack) destroy (stack) empty (stack) push( stack, element) pop (stack) top (stack) • Se a representação do dado é alterada, o resto do programa não precisa ser tocado; 10.3 EXEMPLOS DE LINGUAGENS 10.3.1 ADA • Similar ao MODULA-2; • Módulos são chamados de packages com duas partes: specification package e body package; • A parte de dados do TAD pode ser de qualquer tipo; • O dado de um package pode ser declarado como private nos casos em que detalhes da representação não pode ser vistos por outros packages; • O specification package define quais dados e funções são públicos e privados. Os protótipos das funções são definidos; • Package body contém o código das funções mencionadas no specification package. Os parâmetros devem coincidir; Conceitos de Linguagens de Programação -6- 10.3.2 C++ • Class é o modelo para TAD. Uma class pode conter tanto entidades públicas e privadas (dados e funções); • O usuário pode incluir um constructor que é utilizado para criar e inicializar um objeto quando ele é definido; • Constructor é chamado implicitamente quando uma instância da classe é criada; • Também possui um destructor que é chamado para desalocar o objeto; 10.4 TIPOS ABSTRATOS DE DADOS PARAMETRIZADOS • Queremos um TAD que pode armazenar qualquer elemento escalar; Exemplo: Um stack genérico que possa conter real e inteiros; 10.4.1 ADA: • Criar um package genérico com max_size e element_type como parâmetros genéricos: generic <descrever nome dos parâmetros > package generic_stack is ... • Para criar uma instância do TAD para 100 inteiros. package integer_stack is new generic_stack (100, integer); • Para criar uma instância do TAD para 100 floats. package float_stack is new generic_stack (100, float); 10.4.2 C++: • Fazer um class template com element type como parâmetro: template <class Type> class stack { private Type *ptr_stk; int max_len; int top_ptr; ... } • Como em Ada, as classes modeladas C++ são instanciadas durante a compilação. A diferença é que no C++ as instanciações são implícitas. Conceitos de Linguagens de Programação -7- 11 SUPORTE À PROGRAMAÇÃO ORIENTADA Á OBJETO 11.1 Introdução • Categorias de linguagens que suportam OOP: i. Suporte OOP é adicionado a uma linguagem existente • C + + (também suporta programação procedural e dataoriented) • Ada 95 (também suporta programação procedural e dataoriented) • CLOS (também suporta programação funcional) • Scheme (também suporta programação funcional) ii. Suporta OOP, mas tem a mesma aparência e utiliza a estrutura básica de linguagens imperativas anteriores: • Eiffel (não está baseada diretamente em nenhuma predecessora) • Java (baseada em C++) iii. Linguagens OOP puras • Smalltalk • Evolução dos Paradigmas • Procedural - 1950s-1970s • Data-Oriented – início dos anos 1980s (data-oriented) • OOP – fim dos anos 1980s (Herança e amarração dinâmica) • Origens da Herança • Observações na segunda metade dos anos 1980s: • Aumento de produtividade pode advir do reuso; • TAD´s são difícies de reutilizar; • Todos os TAD´s são independentes e estão no mesmo nível; • Herança soluciona tanto a questão de reuso quanto permite uma relação de hierarquia entre classes. 11.2 • • • • • • • Definições em OOP: TAD´s são chamados de classes; Instância de uma classe são chamados de objetos; Uma classe que herda é uma classe derivada ou subclasse; A classe da qual se herda é uma classe pai ou superclasse Subprogramas que definem as operações sobre os objetos são chamados de métodos; A coleção completa de métodos de um objeto é chamada de protocolo de mensagem do objeto ou interface de mensagens; Mensagens possuem duas partes: nome do método e objeto de destino; Conceitos de Linguagens de Programação -8- • • • • • • • • No caso mais simples, uma classe herda todas as entidades do seu pai Herança pode ser complicada através de controles de acessos às entidades encapsuladas; o Uma classe pode omitir entidades das suas subclasses; o Uma classe pode omitir entidades de seus clientes; Além de herdar métodos tal como estão, uma classe pode modificá-lo: o O novo método pode overrides o método herdado o O método do pai será sobreposto (overriden); Existem dois tipos de variáveis em uma classe: o Variáveis da Class variables - um/class; o Variáveis da Instãncia - um/objeto; Existem dois tipos de métodos em uma classe: o Métodos da Classes – mensagens para a classe; o Métodos da Instância – mensagens para os objetos; Herança Simples vs. Herança Múltipla Desvantagem da herança para o reuso: o Cria interdependências entre classes que torna complexa a manutenção: Polimorfismo em Linguagens OOP: o Uma variável polimórfica pode ser definida em uma classe e está apta a referenciar objetos da classe ou qualquer um de seus descendentes; o Quando uma hierarquia de classes inclui classes que sobrepõem métodos e estes métodos são chamados através de uma variável polimórfica, a amarração com o método adequado deve se dar de forma dinâmica; o O polimorfismo simplifica a adição de novos métodos; o Um método virtual é que não inclui a sua definição (é somente um protocolo); o Uma classe virtual é a que inclui pelo menos um método virtual; o Uma classe virtual não pode ser instanciada; 11.3 • • C++ Características Gerais: o Sistema misto de tipos; o Constructors e destructors o Elaborado controle de acesso às entidades da classe; Herança o Uma classe não necessita ser subclasse de outra classe; o Controle de acesso as partes são: Private (visível somente na classe e classes amigas) Public (visível na subclasse e clientes) Protected (visível na classe e subclasses) o Suporte à herança Múltipla o Amarração Dinâmica Um método pode ser definido como virtual, significando que pode ser chamado através de uma variável polimórfica e amarrado dinamicamente à mensagem; Uma função virtual pura não possui a parte de definição; Conceitos de Linguagens de Programação -9- Uma classe que possui pelo menos um função virtual pura é uma classe abstrata; o Avaliação C++ proporciona um extensivo controle de acesso; C++ proporciona herança múltipla; Em C++, o programador deve decidir em tempo de projeto que métodos serão amarrados estaticamente e dinamicamente; Amarração estática é mais rápida; 11.4 Java • Características Gerais: • Todos os dados são objetos, exceto os tipos primitivos; • Todos os tipos primitivos possuem classes empacotadoras (wrapper) que contém um dado desta natureza. Dispõem de vários métodos, principalmente voltados para conversão entre tipos; Conceitos de Linguagens de Programação - 10 - 12 CONCORRÊNCIA 12.1 • • • • • Introdução Razões para estudar concorrência: • Envolve uma nova maneira de projetar software pode ser útil, pois muitos problemas do mundo real são concorrentes; • Computadores atuais possuem capacidade de concorrência física; Os programas apresentados até o momento possuem um fluxo de controle descrevendo a sequencia de execução; Atualmente, os hardwares são capazes de suportar a execução concorrente de múltiplos subprogramas. Facilidades das linguagens para suportar unidades de programas rodando simultaneamente; Níveis de Concorrência: i. Nível de instrução de máquina: • Executando duas ou mais instruções de máquina simultaneamente. ii. Nível de comando: • Executando dois ou mais comandos simultaneamente. iii. Nível de unidade: • Executando duas simultaneamente. iv. • ou mais unidades de subprogramas Nível de programa: • Executando dois ou mais programas simultaneamente. Normalmente as LP's suportam o 2o e o 3o modo de concorrência; 12.1.1 CATEGORIA DE CONCORRÊNCIA • • • 12.2 • • • • Paralelismo Físico - unidades em cada processador; Paralelismo Lógico - unidades compartilham o mesmo processador; Quasi-Concorrência - intercalamento de co-rotinas, porém apenas uma é executada por vez; Concorrência em Nível de Subprograma Programas concorrentes consistem de um número de processos executando em paralelo; Task é uma unidade de programa que pode estar em execução concorrente com outras unidades de programa; Threads são unidades concorrentes que compartilham um mesmo espaço de endereço, possuem acesso ao mesmo ambiente global; Task é diferente de subprograma porque: Conceitos de Linguagens de Programação - 11 - • Uma task pode ser implicitamente iniciada; • Unidade de programa que envolve a task não necessita esperar a task; • Para suportar interação entre processos uma linguagem deve prever: • Instruções de sincronização; • Comunicação entre processos; • Os estados de uma task são descritos no seguinte diagrama de transição: Selection Create Process READY RUNNING End of Process Preemption Release Wait Sincronização executada por outro processo (recurso liberado) 12.3 • • instrução de sincronização executada pelo processo (aguarda recurso) É um mecanismo para controlar a ordem na qual tarefas são executadas; Tipos: Sincronização de Cooperação • • Necessário quando uma task A deve esperar que B complete uma atividade; Ex.: Produtor -> dado -> consumidor; Sincronização de Competição • • • • WAITING Sincronização • 12.4 Wait Necessário quando duas tasks precisam utilizar mesmo recurso não disponível simultaneamente; É um problema, uma vez que as operações não são atômicas; CO-ROTINAS MÓDULA-2 e SIMULA-67; Simetria de processamento; Conceitos de Linguagens de Programação - 12 - • • • • • • 12.5 • Processamento alternado entre rotinas A e B; Transição de controle => Resume X; Interrupção de execução => Detach; Há transferência explícita; Programas não podem ser recursivos; Dois RA's são mantidos como ativos em pilhas separadas; Projeto de Linguagem para Concorrência Aspectos da LP que proporcionam sincronização de competição; • Semáforos; • Monitores; • Passagem de Mensagens; 12.5.1 SEMÁFAROS • • • • DISKSTRA (ALGOL 68); É uma estrutura de dados consistindo de um contador (inteiro) e uma fila; Contador é alterado por primitivas Get, Release; A guarda de um código faz com que o semáforo gerencie uma fila de processos em espera; GET - reserva de privilégio; RELEASE - liberação; • • Para sincronização de competição; A idéia é prover acesso limitado a uma estrutura de dados compartilhada pela inserção de um guarda (semáforo) em torno do código que acessa a estrutura; Get (s) if s>0 Then dec(s); Else suspende current task; Release(s) if ∃ (existe) processo suspenso em s Then selecione para execução; Else inc (s); 12.5.2 MONITORES • • É um tipo abstrato de dados que encapsula os recursos e as operações de acesso. Pascal Concurrent, Modula e Mesa oferecem o conceito de monitor. Atualmente Ada, Java e C# também disponibilizam. • Disponibilizam duas operações de sincronização: • delay - suspende processo em uma fila; • continue - seleciona processo da fila; Conceitos de Linguagens de Programação - 13 - 12.6 THREADS EM JAVA • • • As unidades concorrentes em Java são os métodos run; O método run é herdado e sobrescrito na subclasse da classe Thread; A classe Thread: • Inclui vários métodos além do run • Start, que chama run, e cujo fluxo de controle retorna imediatamente para start; • Yield, que para a execução da thread e a coloca na fila de task pronta; • Sleep, que para a execução da thread e a coloca em bloqueada pelo tempo especificado no parâmetro; • Suspend, que para a execução da thread até que seja reiniciada com resume; • Resume, que reinicia uma thread suspensa; • Stop, que mata uma thread; • Sincronização de Competição com Threads Java: • • • • Um método que inclui o modificador synchronized desabilita qualquer outro método de acessar o objeto, enquanto ele está em execução. Se apenas um parte de um método deve executar sem interferência, ele pode ser sincronizado. Um objeto cujos métodos são todos sincronizados é efetivamente um monitor. Sincronização de Cooperação com Threads Java: • • Utilização dos métodos wait e notify/notifyall, implementados na classe raiz denominada Object, de onde todos são herdeiros. O método wait deve ser chamado em um loop; Conceitos de Linguagens de Programação - 14 - 13 TRATAMENTO DE EXCEÇÕES 13.1 Conceitos Programação Defensiva • Programação defensiva é uma técnica que torna os programas mais robustos em relação a eventos inesperados, tais como erros de run-time. o Quanto menos problemas com um programa em tempo de execução maior é a qualidade do software • Eventos inesperados podem ocorrer devido à: o Erros de entrada do usuário (e.g. entrada de data com formato errado) o Problemas de entrada/saída de arquivos (e.g. end of file ou disk full) o Problemas aritméticos (e.g. overflow) o Interrupção de Hardware e software (e.g. pressionar da tecla break) • Implementação de tratamento de exceção na linguagem de programação pode facilitar a programação defensiva. o Uma exceção é uma condição especial de um erro inesperado em tempo de execução o Exceções built-in podem ser detectadas automaticamente pela implemantação da linguagem o Exceções podem ser explicitamente levantadas (raised) o Exceções pode ser tratadas por tratadores de exceção a fim de recuperar das condições de erro. o Tratador de exceção são fragmentos de programas definidos pelo usuário que são executados quando ocorre uma exceção (raised) • Exceção: é um evento não usual, ou um erro, ou mesmo um evento não detectado tanto pelo hardware quanto pelo software, e que pode demandar processamento especial; Exemplo: Floating point overflow, subscript out-of-range, I/O error reading file, zero divide, memory fault, ... • • • • Tratador de Exceção: são fragmentos de programas definidos pelo usuário que são executados quando ocorre uma exceção (raised); Uma exceção é uma condição especial de um erro inesperado em tempo de execução; Algumas LP's proporcionam mecanismos que permitem o programa codificar o tratador de exceção quando certas condições de software ou hardware ocorrem. Sem estes mecanismos o programador trata algumas exceções: Conceitos de Linguagens de Programação - 15 - Observe o seguinte exemplo1: readFile { open the file; determine its size; allocate that much memory; read the file into memory; close the file; } errorCodeType readFile { initialize errorCode = 0; open the file; if (theFileIsOpen) { determine the length of the file; if (gotTheFileLength) { allocate that much memory; if (gotEnoughMemory) { read the file into memory; if (readFailed) { errorCode = -1; } } else { errorCode = -2; } } else { errorCode = -3; } close the file; if (theFileDidntClose && errorCode == 0) { errorCode = -4; } else { errorCode = errorCode and -4; } } else { errorCode = -5; } return errorCode; } 1 readFile { try { open the file; determine its size; allocate that much memory; read the file into memory; close the file; } catch (fileOpenFailed) { doSomething; } catch (sizeDeterminationFailed) { doSomething; } catch (memoryAllocationFailed) { doSomething; } catch (readFailed) { doSomething; } catch (fileCloseFailed) { doSomething; } } Copyright (c) 2012, Oracle America, Inc Conceitos de Linguagens de Programação - 16 - 13.2 CONSIDERAÇÕES NO PROJETO DO TRATADOR DE EXCEÇÃO 13.3 • HISTÓRIA DE EXCEÇÕES DEFINIDAS PELO USUÁRIO PL/1 - primeira a implementar; ON CONDITION BEGIN ... END; • • {NOME DA EXCEÇÃO} Algumas built-in exceções: ENDPAGE, ENDFILE, CONVERSION, OVERFLOW, UNDERFLOW, ZERODIVIDE, SIZE, STRINGRANGE, SUBSCRIPTRANGE, UNDEFINEDFILE. Atualmente implementada nas seguintes linguagens: Clu, Ada, Modula-3, Python, PHP, Ruby, C++, Java, C# e ML, dentre outras. Conceitos de Linguagens de Programação - 17 - 14 REFERÊNCIAS i. ii. iii. iv. v. Ghezzi, Carlo, Mehdi, Jazayeri; Programming Language Concepts; Editora Wiley, 3º ed. Sebesta, Robert W.; Conceitos de Linguagens de Programação; Editora Bookman, 3º ed. Pratt, Terrence W., Zelkowitz, Marvin V; Programming Languages: Design and Implementation; Editora Prentice Hall, 3º ed. http://archive.adaic.com/pol-hist/history/holwg-93/index.html#toc Java Tutorials. Copyright (c) 2012, Oracle America, Inchttp://docs.oracle.com/javase/tutorial/essential/exceptions/advantages.html Conceitos de Linguagens de Programação - 18 -