No description available.

Made available in DSpace on 2014-06-12T15:54:28Z (GMT). No. of bitstreams: 2 arquivo7152_1.pdf: 1057833 bytes, checksum: 67e3dddb2bcfb41fafccbd6d0086f285 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2005 / Neste trabalho discutimos o projeto de compiladores corretos por construção para linguagens orientadas a objeto. Um compilador correto é aquele que garante que a semântica é preservada quando o programa fonte _e traduzido para a linguagem destino. O projeto de compiladores corretos para linguagens imperativas se encontra bem fundamentado; atualmente, o maior desafio é o desenvolvimento de uma abordagem para lidar com características de orientação a objetos. Nesta tese, descrevemos uma abordagem algébrica para construção de compiladores corretos para uma linguagem orientada a objetos chamada ROOL (acrônimo para Refenement Objecy-oriented Language), que é similar a Java e C++. Esta linguagem inclue classes, herança, ligação dinâmica, recursão, cast e teste de tipos, e visibilidade baseada em classes. Na nossa abordagem, lidamos com o problema de corretude do compilador transformando a tarefa de compilação em uma tarefa de refinamento de programa. O processo de compilação passa ser identificado como sendo a redução de um programa fonte, escrito em um subconjunto executável da linguagem, para uma forma normal. A forma normal é gerada por uma série de transformações que preservam a corretude, e s ao provadas corretas a partir das leis básicas da linguagem; portanto o processo é correto por construção. A maior vantagem da nossa abordagem reside na caracterização do processo de compilação dentro de um sistema uniforme onde as comparações e traduções entre semânticas são evitadas. A redução a forma normal é formalizada como uma álgebra onde a noção central é a de refinamento de programas. Portanto, o produto da compilação é um programa na própria linguagem fonte. Nossa forma normal é um programa na forma de um interpretador, escrito na mesma linguagem fonte, emulando o comportamento da máquina destino. A partir desse interpretador, é que a seqüência das instruções geradas são capturadas. Definimos a Máquina Virtual de ROOL (RVM) como sendo nossa máquina destino; ela _e baseada na Máquina Virtual de Java (JVM) Tal uniformidade implica que todo o cálculo necessário para assegurar a corretude do processo de compilação é realizado em um único sistema de uma linguagem orientada a objetos cuja semântica é dada por leis algébricas. Nenhuma teoria relativa a linguagem fonte ou destino é desenvolvida ou usada no processo. O processo de compilação é justificado por teoremas de redução da forma normal. Existem cinco fases: pré-compilação de classes, redirecionamento de chamada de métodos, simplificação, eliminação de controle e refinamento de dados. Para cada fase, um teorema assegura o resultado esperado. O teorema principal conecta os passos intermediários e estabelece o resultado para todo o processo. Uma vez que os teoremas de redu¢c~ ao pra cada fase são provados corretos a partir das leis básicas de ROOL, eles corroboram para a corretude de todo o processo

We present a type-based approach to statically derive symbolic closed-form formulae that characterize the bounds of heap memory usages of programs written in object-oriented languages. Given a program with size and alias annotations, our inference system will compute the amount of memory required by the methods to execute successfully as well as the amount of memory released when methods return. The obtained analysis results are useful for networked devices with limited computational resources as well as embedded software. / Singapore-MIT Alliance (SMA)

Dynamic optimizers for object-oriented languages collect a variety of profile data to drive optimization decisions. In particular, the dynamic call graph (DCG) informs key structural optimizations such as which methods to optimize and how to optimize them. Unfortunately, current low-overhead call-stack hardware and software sampling methods are subject to sampling bias, which loses accuracy of 40 to 50% when compared with a perfect call graph. This paper introduces DCG correction, a novel approach that uses static and dynamic control-flow graphs (CFGs) to improve DCG accuracy. We introduce the static frequency dominator (FDOM) relation, which extends the dominator relation on the CFG to capture relative execution frequencies and expose static constraints on DCG edges, which we use to correct DCG edge frequencies. Using conservation of flow principles, we further show how to use dynamic CFG basic block profiles to correct DCG edge frequencies intraprocedurally and interprocedurally. We implement and evaluate DCG correction in Jikes RVM on the SPEC JVM98 and DaCapo benchmarks. Default DCG sampling attains an average accuracy of 52-59% compared with perfect, whereas FDOM correction improves average accuracy to 64-68%, while adding 0.2% average overhead. The dynamic correction raises accuracy to 85% on average, while adding 1.2% average overhead. We then provide dynamically corrected DCGs to the inliner with mixed results -1% average degradations and improvements across a variety of configurations. However, prior work shows that increased DCG accuracy in production VMs has benefits. We believe that high-accuracy DCGs will become more important in the future as the complexity and modularity of object-oriented programs increases.

Computational reflection is a fundamental mechanism in object oriented languages. Reflection has proved useful in many contexts, such as in the design of development environments, language extension, and the dynamic, unanticipated adaptation of running systems We identify three problems with the current approach to reflection in object oriented languages: partial behavioral reflection needs to be anticipated, structural reflection is limited to the granularity of a method, and behavioral reflection cannot be applied to the whole system. To address these problems, we extend structural reflection to cover sub-method elements and present how sub-method structural reflection supports unanticipated partial behavioral reflection. We add the concept of context to represent meta-level execution and show how this allows behavioral reflection to be applied even to system classes. We describe an implementation in Smalltalk. Benchmarks validate the practicability of our approach. In addition, we present an experimental evaluation in which we show how the system is used for dynamic analysis. We realize dynamic feature analysis by annotating the sub-method structure of the system directly to denote features instead of recording full execution traces.

Integrated development environments are essential for efficient realization of complex industrial products, typically consisting of both software and hardware components. Powerful equation-based object-oriented (EOO) languages such as Modelica are successfully used for modeling and virtual prototyping increasingly complex physical systems and components, whereas software modeling approaches like UML, especially in the form of domain specific language subsets, are increasingly used for software systems modeling. A research hypothesis investigated to some extent in this thesis is if EOO languages can be successfully generalized also to support software modeling, thus addressing whole product modeling, and if integrated environments for such a generalized EOO language tool support can be created and effectively used on real-sized applications. However, creating advanced development environments is still a resource-consuming error-prone process that is largely manual. One rather successful approach is to have a general framework kernel, and use meta-modeling and meta-programming techniques to provide tool support for specific languages. Thus, the main goal of this research is the development of a meta-modeling approach and its associated meta-programming methods for the synthesis of model-driven product development environments that includes support for modeling and simulation. Such environments include components like model editors, compilers, debuggers and simulators. This thesis presents several contributions towards this vision in the context of EOO languages, primarily the Modelica language. Existing state-of-the art tools supporting EOO languages typically do not satisfy all user requirements with regards to analysis, management, querying, transformation, and configuration of models. Moreover, tools such as model-compilers tend to become large and monolithic. If instead it would be possible to model desired tool extensions with meta-modeling and meta-programming, within the application models themselves, the kernel tool could be made smaller, and better extensibility, modularity and flexibility could be achieved. We argue that such user requirements could be satisfied if the equation-based object-oriented languages are extended with meta-modeling and meta-programming. This thesis presents a new language that unifies EOO languages with term pattern matching and transformation typically found in functional and logic programming languages. The development, implementation, and performance of the unified language are also presented. The increased ease of use, the high abstraction, and the expressivity of the unified language are very attractive properties. However, these properties come with the drawback that programming and modeling errors are often hard to find. To overcome these issues, several methods and integrated frameworks for run-time debugging of the unified language have been designed, analyzed, implemented, and evaluated on non-trivial industrial applications. To fully support development using the unified language, an integrated model-driven development environment based on the Eclipse platform is proposed, designed, implemented, and used extensively. The development environment integrates advanced textual modeling, code browsing, debugging, etc. Graphical modeling is also supported by the development environment based on a proposed ModelicaML Modelica/UML/SysML profile. Finally, serialization, composition, and transformation operations on models are investigated.

Esta tese propõe cinco construções para linguagens orientadas a objetos. Algumas delas podem ser implementadas por meio de pré-processadores. Estas construções são: visão de classe, adaptador, extensão de classe, Shell dinâmico e extensão dinâmica. Todas elas são baseadas no conceito de filtro, que e um objeto que intercepta as mensagens enviadas a um outro objeto. Visão de classe permite corrigir interpretações incorretas da semântica de uma classe no código de outras classes. Um filtro é usado para traduzir as mensagens para o significado correto. Adaptadores permitem mudar o tipo de um objeto através de um filtro e são usados para acoplar classes que, de outra forma, seriam incompatíveis quanto a tipos. Extensão de classe permite adicionar métodos e variáveis de instancia a classes sem a necessidade de edição do código fonte destas. Shell dinâmico e extensão dinâmica possuem algumas das características de meta-objetos e meta-classes, respectivamente. Eles formam um modelo reflexivo estaticamente tipado. Shell dinâmico permite redirecionar todas as mensagens enviadas a um objeto e extensão dinâmica permite substituir métodos de uma classe em tempo de execução. Todas as construções são originais, podem ser adicionadas em uma linguagem estaticamente tipada sem danificar o sistema de tipos e resolvem alguns problemas descritos na literatura de orientação a objetos. / This thesis proposes five constructions for object-oriented languages. Some of them can be implemented using a preprocessor. These constructions are: class view, adapter, class extension, dynamic shell, and dynamic extension. All of them are based in the concept of filter, that is an object that intercepts the messages sent to another object. Class view allows correcting misinterpretations about the semantics of a class in code of other classes. A filter is used to translate the messages to the correct semantics. Adapters allow changing the type of an object through a filter and are used to glue type incompatible classes. Class extension allows adding methods and instance variables to classes without editing the source code of these classes. Dynamic Shell and dynamic extension have some of the characteristics of meta-objects and meta-classes, respectively. They compose a statically typed reflective model. Dynamic shell allows to redirect all messages sent to an object and dynamic extension allows replacing methods of a class at run time. All constructs are original and can be added to a statically typed language. They solve some problems described in the object-oriented literature.

Esta tese propõe cinco construções para linguagens orientadas a objetos. Algumas delas podem ser implementadas por meio de pré-processadores. Estas construções são: visão de classe, adaptador, extensão de classe, Shell dinâmico e extensão dinâmica. Todas elas são baseadas no conceito de filtro, que e um objeto que intercepta as mensagens enviadas a um outro objeto. Visão de classe permite corrigir interpretações incorretas da semântica de uma classe no código de outras classes. Um filtro é usado para traduzir as mensagens para o significado correto. Adaptadores permitem mudar o tipo de um objeto através de um filtro e são usados para acoplar classes que, de outra forma, seriam incompatíveis quanto a tipos. Extensão de classe permite adicionar métodos e variáveis de instancia a classes sem a necessidade de edição do código fonte destas. Shell dinâmico e extensão dinâmica possuem algumas das características de meta-objetos e meta-classes, respectivamente. Eles formam um modelo reflexivo estaticamente tipado. Shell dinâmico permite redirecionar todas as mensagens enviadas a um objeto e extensão dinâmica permite substituir métodos de uma classe em tempo de execução. Todas as construções são originais, podem ser adicionadas em uma linguagem estaticamente tipada sem danificar o sistema de tipos e resolvem alguns problemas descritos na literatura de orientação a objetos. / This thesis proposes five constructions for object-oriented languages. Some of them can be implemented using a preprocessor. These constructions are: class view, adapter, class extension, dynamic shell, and dynamic extension. All of them are based in the concept of filter, that is an object that intercepts the messages sent to another object. Class view allows correcting misinterpretations about the semantics of a class in code of other classes. A filter is used to translate the messages to the correct semantics. Adapters allow changing the type of an object through a filter and are used to glue type incompatible classes. Class extension allows adding methods and instance variables to classes without editing the source code of these classes. Dynamic Shell and dynamic extension have some of the characteristics of meta-objects and meta-classes, respectively. They compose a statically typed reflective model. Dynamic shell allows to redirect all messages sent to an object and dynamic extension allows replacing methods of a class at run time. All constructs are original and can be added to a statically typed language. They solve some problems described in the object-oriented literature.

Cette thèse traite de la compilation efficace des langages à objets en héritage multiple. La programmation objet est caractérisée par un mécanisme fondamental, emph{la liaison tardive} --- la méthode appelée dépend du type dynamique d'un paramètre distingué, le emph{receveur}. L'efficacité de ce mécanisme nécessite une implémentation adéquate qui est conditionnée par le schéma de compilation utilisé --- compilation séparée avec chargement dynamique, compilation globale, etc. Cependant la programmation par objets présente une apparente incompatibilité entre trois termes : l'héritage multiple, l'efficacité et l'owa --- en particulier, le chargement dynamique. Nous avons étudié les techniques d'implémentation compatibles avec l'héritage multiple couramment utilisées ainsi qu'une alternative prometteuse, le ph. Nous nous plaçons dans le cadre du typage statique, donc nos conclusions peuvent valoir pour des langages comme cpp, eiffel, java, csharp, etc. Différents schémas de compilation sont considérés, de l'owa à l'cwa. Ces techniques et ces schémas ont été mis en uvre dans le compilateur auto-gène du langage prm. L'influence sur l'efficacité de tous ces éléments a été testée dans un protocole expérimental rigoureux de méta-compilation et les tests ont été réalisés sur une variété de processeurs différents. Les résultats des ces expérimentations sont discutés et comparés aux évaluations a priori effectuées sur les techniques d'implémentation. Ils confirment aussi que le ph est une technique d'implémentation intéressante pour le sous-typage multiple à la java. / His thesis is about efficient compilation of object oriented language with multiple inheritance.Object oriented programing is characterized by a main mechanism, emph{late binding} --- invoked method only depends on the dynamic type of one special parameter, the emph{receiver}.In order to be efficient this mechanism needs an implementation which depends on some compilation scheme --- separate compilation with dynamic loading, global compilation, etc.However object oriented programming present akin of incompatibility between three terms: multiple inheritance, efficiency and open world assumption --- especially with dynamic loading.In this thesis, we have studied common implementation techniques compatible with multiple inheritance and a promising alternative, perfect class hashing.The context of this study is static typing, our conclusion holds for languages like cpp, eiffel, java, csharp, etc.Different compilation schemes are considered, from open world assumption to closed world assumption.These techniques and schemes are implemented in the prm bootstraped compiler.Efficiency influence of all this artifacts has been tested with a rigorous meta-compilation experimental protocol and these tests have been performed on a variety of different processors.Results of these experiments are discuss and compared to an a priori evaluations of implementations techniquesThey mainly confirm perfect class hashing as an interesting implementation for multiple subtyping, a la java.

Les systèmes embarqués sont largement utilisés de nos jours. Pour des raisons d'efficacité, les plus contraints en termes de ressources sont toujours programmés en C et en assembleur. L'adoption de langages de plus haut niveau tels que C# ou Java offrirait plus d'abstraction au programmeur, ce qui réduirait les temps de développement et par conséquent le coût de ces systèmes. Certains d'entre eux ont déjà migré vers de tels langages, comme les téléphones mobiles ou les tablettes tactiles, mais ils sont équipés d'une grande quantité de mémoire externe et ne reflètent pas la majorité des systèmes embarqués.Cette thèse s'intéresse à l'implémentation de Java et .NET pour l'embarqué, et plus spécifiquement à la compilation efficace du polymorphisme. Ce polymorphisme génère un certain coût à l'exécution, comme des indirections dans le cas des appels de méthodes (polymorphisme d'inclusion), ou de la duplication de code dans le cas de la généricité (polymorphisme paramétrique). De nombreuses techniques d'implémentation ont été proposées, notamment pour Java. Il reste cependant à identifier lesquelles sont applicables pour le type de systèmes que nous ciblons, et à en concevoir de nouvelles pour certains aspects comme la généricité. Nous partons du principe que les techniques globales (hypothèse du monde clos) sont les mieux adaptées. Par l'analyse de types, nous détectons qu'une partie importante des programmes est monomorphe et qu'elle peut donc être compilée sans surcoût. Pour implémenter le polymorphisme restant, nous choisissons la technique la mieux adaptée au matériel cible. Nous proposons également une implémentation de la généricité qui est adaptée aux systèmes embarqués. D'après nos évaluations, l'impact négatif du polymorphisme sur l'efficacité est largement réduit. L'efficacité du code optimisé devrait s'approcher de celle du C, et les techniques que nous employons pourraient être applicables dans le contexte plus général du chargement dynamique. / Nowadays, embedded systems are ubiquitous. For efficiency reasons, most constrained systems are still programmed in C and assembly. Adopting higher-level languages such as C# or Java should enhance the level of abstraction offered to programmers and reduce development time and cost for these systems. A small part of them have migrated to such languages, like smartphones and tablet computers, but they have a large amount of external memory available and do not represent the majority of embedded systems.This thesis focuses on the implementation of Java and .NET for embedded systems, and more especially on the efficient compilation of polymorphism. Polymorphism generates an overhead at run-time, such as indirections when methods are invoked (inclusion polymorphism) or code duplication in the case of generics (parametric polymorphism). Many implementation techniques have been proposed, especially for Java. However, it remains to identify which ones are applicable in the context of low-end embedded systems. We consider that whole program optimization (closed-world assumption) is well-suited in this context. Using type analysis, we observe that most part of programs is monomorph, therefore it can be compiled with no overhead with respect to C. In order to implement the remaining polymorphism, we choose the technique which is better suited for the target hardware. We also propose an appropriate implementation of run-time generics. Our results show that the negative impact of polymorphism is mostly reduced. The efficiency of the optimized code should be comparable with C, and the techniques we employ could be applicable in the context of dynamic loading (open-world assumption).