Thesis (Ph. D.)--University of Washington, 1988. / Vita. Bibliography: leaves [135]-145.

Highly dynamic languages like Smalltalk do not have much static type information immediately available before the program runs. Static types can still be inferred by analysis tools, but historically, such analysis is only effective on smaller programs of at most a few tens of thousands of lines of code. This dissertation presents a new type inference algorithm, DDP, that is effective on larger programs with hundreds of thousands of lines of code. The approach of the algorithm borrows from the field of knowledge-based systems: it is a demand-driven algorithm that sometimes prunes subgoals. The algorithm is formally described, proven correct, and implemented. Experimental results show that the inferred types are usefully precise. A complete program understanding application, Chuck, has been developed that uses DDP type inferences. This work contributes the DDP algorithm itself, the most thorough semantics of Smalltalk to date, a new general approach for analysis algorithms, and experimental analysis of DDP including determination of useful parameter settings. It also contributes an implementation of DDP, a general analysis framework for Smalltalk, and a complete end-user application that uses DDP.

Tout le monde a déjà rencontré la fonctionnalité ``Undo/Redo' qui permet de se balader dans les versions précédentes d'un document. Bien que le versioning -- sauver et parcourir plusieurs versions d'entités données -- est nécessaire pour beaucoup d'applications, il est difficile de l'implémenter facilement et efficacement en temps et en espace utilisés. Dans cette thèse, nous présentons un système de versioning efficace et expressif pour les langages orientés objet. <p><p>Nous commencons par développer un modèle qui permet au développeur de sélectionner avec précision les parties intéressantes de son système qui seront sauvegardées à des moments clefs. Ce modèle permet de parcourir facilement les différentes versions enregistrées et de faire cohabiter aisément les parties versionnées avec les parties non sélectionnées par le développeur. Ce modèle est de plus compatible avec trois types de versioning (linear, backtracking et branching versioning) qui permettent des opérations diverses sur la ligne du temps, comme supprimer toutes les versions après une version donnée ou créer une nouvelle branche à partir d'une ancienne version. <p><p>Ensuite nous développons les structures efficaces en temps et en espace qui implémentent ce modèle dans un monde réel. Basées sur les travaux de Driscoll et al. elles sont adaptées aux spécificités de chaque type de versioning. <p><p>Nous montrons ensuite comment ce système peut être intégré concrètement dans un langage orienté object. Plus précisément, nous montrons comment notre système peut être intégré de façon transparente pour le développeur grâce à des outils tels que les aspects ou la transformation de bytecodes. <p><p>Pour valider nos propos, nous avons implémenté notre système dans les langages de programmation Smalltalk et Java. Nous montrons des applications réelles qui l'utilisent, telles que les post-conditions à états et le problème du planar point location. <p><p>Nous terminons cette thèse par évaluer l'efficacité de notre implémentation en effectuant des benchmarks détaillés en Smalltalk et en Java. Nous avons notamment étudié l'espace pris par nos structures données et le temps d'éxecution de chaque opération de versioning. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished