Submitted by Isaac Francisco de Souza Dias (isaac.souzadias@ufpe.br) on 2016-01-19T17:04:34Z
No. of bitstreams: 2
license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5)
GIovannyTesis.pdf: 1126817 bytes, checksum: 54a975f083d8ea416057bffa468c281c (MD5) / Made available in DSpace on 2016-01-19T17:04:34Z (GMT). No. of bitstreams: 2
license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5)
GIovannyTesis.pdf: 1126817 bytes, checksum: 54a975f083d8ea416057bffa468c281c (MD5)
Previous issue date: 2015-03-16 / CAPES / CNPq / There are several approaches to defining a formal semantics of a programming language. The main established ones are operational, denotational and axiomatic semantics. The first two rely on defining an explicit model, whereas the latter one is based on postulating relevant properties of the language in terms of axioms. Particularly, in a purely algebraic approach the axioms take the form of conditional equations (typically denoted as programming laws) that relate the language constructs. Without requiring an explicit model, the advantage of the algebraic approach is incrementality: the language can be extended and the laws tend to remain valid, provided the new constructs do not interfere with the behaviour of the original ones. Algebraic laws have been proposed to uncover interesting properties of several programming paradigms: imperative, logic, functional, concurrent and object oriented, among others. As for the other paradigms, there is a comprehensive set of laws for object oriented constructs, but these are restricted to a language with copy semantics; some laws to deal with references have also been proposed, but these are tailored to specific applications, and are far from being comprehensive. In general, formal reasoning with references has been a persistent challenge and algebraic approaches usually have avoided including them in programming languages. We propose a set of algebraic laws for reasoning about object oriented programs with a reference semantics. First we focus on sequential imperative programs that use object references like in Java. The theory is based on previous work by adding laws to cope with object references. The incrementality of the algebraic method is fundamental; with a few exceptions, existing laws for copy semantics are entirely reused, as they are not affected by the reference semantics. As an evidence of relative completeness, we show that any program can be transformed, through the use of our laws, to a normal form which simulates it using an explicit heap with copy semantics. Soundness is addressed by illustrating how some of the laws can be proved in a relational semantics for a subset of the language. We extend the theory of imperative programs for an object oriented language with the usual constructs: additional imperative commands with references, classes with inheritance and subtyping, visibility control, dynamic binding, type tests and downcasts. Algebraic laws are proposed for these new constructs. In order to illustrate the expressiveness of the laws for the object oriented language, we characterize and prove a set of refactorings from Fowler’s catalog. These are contrasted with previous work that formalized refactorings in the context of copy semantics. / Existem várias abordagens para descrever formalmente a semântica de linguagens de programação. As principais são semântica operacional, denotacional e axiomática. As duas primeiras definem modelos semânticos explícitos enquanto a última postula axiomas que descrevem propriedades relevantes da linguagem. Em uma abordagem puramente algébrica, os axiomas são equações (tipicamente denominadas leis de programação) que relacionam os diversos construtores da linguagem. A vantagem da álgebra é a facilidade de extensão: quando
uma linguagem é estendida, a tendencia é que as leis já estabelecidas continuem sendo válidas, desde que os novos contrutores não interfiram com o comportamento dos construtores originais da linguagem Leis algébricas tem sido propostas para estudar propriedades interessantes de vários paradigmas de programação: imperativo, lógico, funcional, concorrente e orientado a objetos, entre outros. Em geral, para todos estes paradigmas existe um conjunto representativo de leis. Porém, para programação orientada a objetos, os trabalhos tem se restringido a linguagens com semântica de cópia ou as leis relacionadas com referências tem sido direcionadas somente para aplicações específicas e estão distantes de serem representativas. Em geral, raciocínio formal com referências tem sido um desafio persistente e os trabalhos algébricos usualmente tem evitado a inclusão de referências nas linguagens de programação. Propomos um conjunto de leis algébricas que permitem raciocinar com programas orientados a objetos com uma semântica de referências. Primeiro, focamos em uma linguagem imperativa sequencial que usa referências a objetos como em Java. A teoria é baseada em trabalhos anteriores adicionando leis que lidam com referências. A facilidade de extensão do método algébrico é fundamental; com poucas exeções, as leis anteriores para semântica de cópia são reusadas, pois elas não são afetadas pela semântica de referência. Como uma evidência de completude relativa, mostramos que qualquer programa pode ser transformado, usado as leis, em uma forma normal que simula o programa original usando um heap explícito com semântica de cópia. A consistência (soundness) das leis é abordada ilustrando como algumas das leis podem ser provadas em uma semântica relacional para um subconjunto da linguagem. Estendemos a teoria de programas imperativos para uma linguagem orientada a objetos com os habituais construtores: comandos imperativos adicionais com referências, classes com herança e subtipos, controle de visibilidade, amarração dinâmica, e testes e casts de tipos. Leis são propostas para estes novos construtores. Para ilustrar a expressividade das leis para a linguagem orientada a objetos, caracterizamos e provamos um conjunto de refatorações do catalógo clássico de Fowler. Comparamos nossa apresentação com trabalhos anteriores que formalizaram refatorações em um contexto de semântica de cópia.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufpe.br:123456789/14930 |
| Date | 16 March 2015 |
| Creators | PALMA, Giovanny Fernando Lucero |
| Contributors | http://lattes.cnpq.br/3977760354511853, SAMPAIO, Augusto Cezar Alves, NAUMANN, David |
| Publisher | Universidade Federal de Pernambuco, Programa de Pos Graduacao em Ciencia da Computacao, UFPE, Brasil |
| Source Sets | IBICT Brazilian ETDs |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Source | reponame:Repositório Institucional da UFPE, instname:Universidade Federal de Pernambuco, instacron:UFPE |
| Rights | Attribution-NonCommercial-NoDerivs 3.0 Brazil, http://creativecommons.org/licenses/by-nc-nd/3.0/br/, info:eu-repo/semantics/openAccess |
Page generated in 0.0024 seconds