Thesis (M.S.)--Rochester Institute of Technology, 1992. / Typescript. Includes bibliographical references.

L’analyse examina l’impact des relations tonales, des fonctions et des types formels transformés sur l’unité compositionnelle dans les œuvres orchestrales de Max Reger. Le contexte théorique est celui de nouvelles Formenlehre et Harmonielehre. La forme conçue comme une succession des fonctions fut analysée sur la base de la théorie des fonctions formelles de Caplin. Son apparatus analytique a été combiné avec le modèle sophistiqué de ponctuation et le concept de la déformation de la théorie de la sonate de Hepokoski et Darcy. En examinant les relations et la structure tonales, l’analyse adhère au concept de la monotonalité de Schoenberg. L’attention analytique fut focalisée sur les motifs harmoniques dérivés des accords, des progressions et de la ligne de basse. La Grundgestalt (une configuration fondamentale) fut perçue comme une structure motivique ou un contour intervallique quasi-arythmique. L’analyse montra comment Reger avait confirmé la clarté de l’unité tonale du mouvement ou de l’œuvre. / The analysis examined the impact of tonal relations and transformed formal types and functions on the compositional unity in Max Reger’s orchestral works. The theoretical background consisted of New Formenlehre and Harmonielehre. The form conceived as a succession of functions, was analyzed on the basis of Caplin’s formal function theory. His analytical apparatus was combined with the sophisticated punctuation model and the concept of “deformation” developed in the competing sonata theory of Hepokoski and Darcy. In consideration of tonal relationships and structure, the analysis adhered to Schoenberg’s concept of monotonality. The analytical attention was focused on harmonic motives derived from chords, progressions and the bass line. The Grundgestalt (basic configuration) was perceived as a motivic structure or quasi-arrhythmic interval contour. The analysis showed how Reger has confirmed the clarity of the tonal unity of a movement or work in whole.

Le concept d'objet actif est un modèle de calcul puissant utilisé pour définir des systèmes distribués et concurrents. Dans ce travail, nous étudions un modèle d'objet actif sans type futur explicite et avec 'attente par nécessité', une technique qui déclenche une synchronisation sur la valeur retournée par une invocation lorsque celle-ci est strictement nécessaires. Bien que la concurrence élevée combinée à un haut niveau de transparence conduise à de bonnes performances, elles rendent le système plus propice à des problèmes comme les deadlocks. C'est la raison qui nous a conduit à étudier l'analyse de deadlocks dans ce modèle d'objets actifs. Le développement de notre analyse de les deadloks est divisé en deux travaux principaux. Dans le premier travail, nous nous concentrons sur la synchronisation implicite sur la disponibilité d'une certaine valeur. De cette façon, nous pouvons analyser la synchronisation des flux de données inhérente aux langues qui permettent une attente par nécessité. Dans le deuxième travail, nous présentons une technique d'analyse statique basée sur des effets et des types comportementaux pour dériver des modèles de synchronisation d'objets actifs et confirmant l'absence de deadlock dans ce contexte. Notre système d'effets trace l'accès aux champs d'objet, ce qui nous permet de calculer des types comportementaux qui expriment des modèles de synchronisation de manière précise. En conséquence, nous pouvons vérifier automatiquement l'absence de blocages dans des programmes basés sur des objets actifs avec des synchronisations d'attente par nécessité et des objets actifs dotés d’un état interne. / The active object concept is a powerful computational model for defining distributed and concurrent systems. This model has recently gained prominence, largely thanks to its simplicity and its abstraction level. In this work we study an active object model with no explicit future type and wait-by-necessity synchronisations, a lightweight technique that synchronises invocations when the corresponding values are strictly needed. Although high concurrency combined with a high level of transparency leads to good performances, they also make the system more prone to problems such as deadlocks. This is the reason that led us to study deadlock analysis in this active objects model.The development of our deadlock analysis is divided in two main works. In the first work we focus on the implicit synchronisation on the availability of some value. This way we are able to analyse the data-flow synchronisation inherent to languages that feature wait-by-necessity. In the second work we present a static analysis technique based on effects and behavioural types for deriving synchronisation patterns of stateful active objects and verifying the absence of deadlocks in this context. Our effect system traces the access to object fields, thus allowing us to compute behavioural types that express synchronisation patterns in a precise way. As a consequence we can automatically verify the absence of deadlocks in active object based programs with wait-by-necessity synchronisations and stateful active objects.

Type checking is widely used in mainstream programming languages to detect programming errors at compile time. Model checking is gaining popularity as an automated technique for systematically analyzing behaviors of systems. My research focuses on combining these two software verification techniques synergically into one platform for the creation of correct models for software designs. This thesis describes two modeling languages ATS/PML and ATS/Veri that inherit the advanced type system from an existing programming language ATS, in which both dependent types of Dependent ML style and linear types are supported. A detailed discussion is given for the usage of advanced types to detect modeling errors at the stage of model construction. Going further, various modeling primitives with well-designed types are introduced into my modeling languages to facilitate a synergic combination of type checking with model checking. The semantics of ATS/PML is designed to be directly rooted in a well-known modeling language PROMELA. Rules for translation from ATS/PML to PROMELA are designed and a compiler is developed accordingly so that the SPIN model checker can be readily employed to perform checking on models constructed in ATS/PML. ATS/Veri is designed to be a modeling language, which allows a programmer to construct models for real-world multi-threaded software applications in the same way as writing a functional program with support for synchronization, communication, and scheduling among threads. Semantics of ATS/Veri is formally defined for the development of corresponding model checkers and a compiler is built to translate ATS/Veri into CSP# and exploit the state-of-the-art verification platform PAT for model checking ATS/Veri models. The correctness of such a transformational approach is illustrated based on the semantics of ATS/Veri and CSP#. In summary, the primary contribution of this thesis lies in the creation of a family of modeling languages with highly expressive types for modeling concurrent software systems as well as the related platform supporting verification via model checking. As such, we can combine type checking and model checking synergically to ensure software correctness with high confidence.

OCaml est un langage fonctionnel statiquement typé, qui génère après inférence de types un arbre de syntaxe abstraite dans lequel chacun des noeuds est annoté avec un ensemble d’informations issues de cette inférence. Ces informations, en particulier les types inférés, constituent une preuve de typage de l’expression annotée.Ce manuscrit de thèse s’intéresse à la vérification de ces arbres annotés en les considérant comme des preuves de typages du programme, et décrit un ensemble de règles permettant d’en vérifier la cohérence. La formalisation de ces règles de vérification de preuves de types peut être vue comme une représensation du système de types du langage étudié.Cette thèse présente plusieurs aspects de la vérification d’arbres de syntaxe annotés. Le premier cas étudié est la formalisation d’un dérivé de MiniML où toutes les expressions sont annotées de manière théoriquement parfaite, et montre qu’il est possible d’écrire des règles de vérification de manière algorithmique, rendant directe la preuve de correction vis-à-vis de la spécification. La seconde partie s’intéresse à la formalisation de règles de vérification pour un sous-ensemble du premier langage intermédiaire d’OCaml, le TypedTree, accompagné d’un vérificateur implémentant ces règles. Ces règles constituent alors une représentation du système de types d’OCaml, document jusqu’alors inexistant, au mieux disséminé dans diverses publications. / OCaml is a statically typed programming language that generates typed annotated abstract syntax trees after type inference. Each of their nodes contains information derived from the inference like the inferred type and the environment used to find this information. These annotated trees can then be seen as typing proofs of the program.In this thesis, we introduce a consistency checking of type-annotated trees, considering them as typing proof, and we describe a set of rules that defines the consistency property.Such consistency checking rules can then be seen as a formalized representation of the type system, since consistency ensures the typing invariants of the language.This thesis introduces multiple aspects of checking type-annotated trees. First of all, it considers a simplified and ideal version of MiniML and formalizes a set of rules to check consistency. In this formalism, we consider ideally type-annotated trees, which might not be the case for OCaml typed trees. Such type checking rules are presented in an algorithmic form, reducing as much as possible the gap from formalism to implementation. As such, they ease the correction proof between the implementation of the type checker and the specification of the type system. The second part of this thesis is dedicated to the formalization of a set of rules for a subset of the OCaml annotated trees: the TypedTree. The formalism described in these chapters is implemented as a type checker working on large subset of the language, leaving the formalization of some aspects for a further work. These rules constitute a formalized representation of the OCaml type system in a single document.

No description available.

Cette thèse porte sur l'adaptation de la réalisabilité et la paramétricité au cas des types dépendants dans le cadre des Systèmes de Types Purs. Nous décrivons une méthode systématique pour construire une logique à partir d'un langage de programmation, tous deux décrits comme des systèmes de types purs. Cette logique fournit des formules pour exprimer des propriétés des programmes et elle offre un cadre formel adéquat pour développer une théorie de la réalisabilité au sein de laquelle les réalisateurs des formules sont exactement les programmes du langage de départ. Notre cadre permet alors de considérer les théorèmes de représentation pour le système T de Gödel et le système F de Girard comme deux instances d'un théorème plus général.Puis, nous expliquons comment les relations logiques de la théorie de la paramétricité peuvent s'exprimer en terme de réalisabilité, ce qui montre que la logique engendrée fournit un cadre adéquat pour développer une théorie de la paramétricité du langage de départ. Pour finir, nous montrons comment cette théorie de la paramétricité peut-être adaptée au système sous-jacent à l'assistant de preuve Coq et nous donnons un exemple d'application original de la paramétricité à la formalisation des mathématiques.

We discuss the development of a number of algorithms and techniques to allow object oriented virtual machines to support many of the features needed by functional and other higher level languages. These features include non-strict evaluation, partial function application, higher ranked and higher kinded types. To test the mechanisms that we have developed we have also produced a compiler to allow the functional language Haskell to be compiled to a native executable for the Common Language Runtime. This has allowed us to demonstrate that the techniques we have developed are practically viable.

A noção de tipo é intrínseca ao raciocínio humano, na medida que os seres humanos tendem a "classificar" os objetos segundo seu use e seu comportamento como parte do processo de resolução de problemas. Tal classificação dos objetos implica numa abstração das características irrelevantes dos mesmos,permitindo dessa maneira uma simplificação importante da complexidade do universo de discurso Por outro lado, certos problemas são altamente complexos e requerem um tratamento diferenciado.Esses problemas exigem, para sua resolução, um grande conhecimento do universo de discurso. O ponto critico nesta situação é que o domínio do problema não é exato como poderia ser um domínio matemático. Pelo contrario, ele inclui geralmente aspectos ambíguos e pouco formais que dificultam seu entendimento. Tal domínio a chamado de senso comum e é objeto de estudo de uma linha da computação, a Inteligência Artificial (IA). Para [KRA 87], entre outros, as soluc6es pare muitos problemas de IA dependern mais da capacidade de adquirir e manipular conhecimento do que de algoritmos sofisticados. Por este motivo, existem na IA muitos tipos de linguagens que tentam, de di verses maneiras,facilitar a representação de conhecirnentos sobre universos de discurso de problemas particulares. São as chamadas Linguagens de Representação de Conhecimento. A noção de tipo e implícita nas linguagens de representação de conhecimento, uma vez que tal noção é natural no raciocínio humano e esta intimamente ligada ao conceito de abstração. Este trabalho visa explicitar a noção de tipo subjacente ao núcleo definido da linguagem RECON-II. Para isto, foi realizado um estudo semântico prévio para identificar os tipos semânticos da linguagem. A partir da noção semântica dos tipos foi possível definir a correspondente sintática e finalmente, descrever um Sistema de Tipos para RECON-II. Um Sistema de Tipos consiste numa Linguagem de Tipos (tipos básicos + construtores de tipos) e num Sistema de Dedução que relaciona as expresses da linguagem objeto (linguagem de programação com as expresses da linguagem de tipos. Para a primeira etapa realizada neste trabalho, a determinação da semântica da linguagem, foi utilizado o método algébrico. Nele toda expressão RECON-II é um termo de uma assinatura Z, de modo quo cada assinatura Z determina um conjunto de expressos RECON-UL Mas, por outro lado, uma assinatura também determina um conjunto de álgebras. Dessas álgebras-Z só um subconjunto significativo para as expressões RECON-II. As álgebras-Z significativas são aquelas que satisfazem a assinatura-Z mais um conjunto E de axiomas. A assinatura-Z junto como o conjunto E de axiomas constituem o quo se denomina Tipo Abstrato de Dados, T=CZ, E), e as álgebras-Z significativas são os chamados modelos-Z do tipo T. Assim, uma expressão RECON-II a e um elemento da álgebra de termos quo g uma Álgebra gerada a partir do E. Essa álgebra, 44 4-) conjunto das expressi5es_: RECON-II significativas, e o modelo inicial de tais expressões WOG 781 Dado um tipo abstrato T existe um único modelo para T, ou uma classe de modelos, não isomórficos, denominada MCT>. No segundo caso, asses modelos constituem uma "quasi" ordem parcial com modelo inicial e terminal. A existência e unicidade do modelo inicial para qualquer tipo T foi demonstrada por [GOG 77] Com Σ = (S, F). a (Ws )para 9 S, e o conjunto dos termos de "sort." e. Na RECON-II, são os termos de uma categoria sintática determinada. As categorias sintáticas principais são : Conceitos, Relações, Funções e Redes. Um tipo semântico para s E S é um subconjunto M(T) S M(T) quo satisfaz os axiomas E exigidos de (WΣ) s, constituindo o tipo abstrato T .s.(por exemplo TConceitos, TRedes, etc.) Por último foi definido o Sistema de Tipos, que consiste numa estrutura sintática adequada para os tipos semânticos de cada expressão-RECON e, para cada expressão de tipo, um conjunto de regras de inferências que permuta, a partir de uma expressão-RECON inferir seu tipo mais geral. / The notion of type is intrinsic to human reasoning, since human beings tend to classify objects according their use and behaviour as part of the problem solving process. By classifying objects, their irrevelant characteristics are abstrated; in this way, the complexity of the universe of discourse is much reduced. On the other hand, certain problems are higly complex and require a differentiated treatament. In order to solve these problems, a great knowledge of de universe of discourse is needed. The critical proint in this situation is that the domain of the problem isn't as precise as a matliematic domain. On the contrary, it generally, includes ambiguous and not very formal aspects wich make its uderstanding difficult.. Such a domains is known as common sense and this is the object of studies of one line of Computer Science, Artificial Intelligence CAI). For [KRA 871, among others, the solutions for many AI problems depend on the ability for acquiring and manipulating knowledge rather than on sophisticated algorithm. For this reason, there are in AI many type of languages that attemps in different ways, to represent the UD of a particular problem. These languagesare known as Knowledge Representation Languages. The notion of type is implicit in Knowledge Representation Languages, since it is natural in human reasoning and closely rrelated to the concept of abstraction. This work intends to make the notion of type intrinsic to the RECON-II's kernel language, explicity. In order to do this, a preliminary semantic stidy was carriedaut to identify the semantic types of the languages. From the semantic notion of the types it was possible to define the sintactic counterpart and finally to describe a Type System for RECON- II. A Type System conssit of a type language (basic types + types constructors) end a deduction system that relattes expressions in the language object (programming language) to the expressions in the type language. In the first step of this work, language semantic determination, the algebric method was used. In it every RECON-II expression is one term of a signature 2, so Chet every signature 2 determines a RECON-II expressions set. On the other hand, a signature also determines a set of algebras. Out of these 2-algebras only one subset is significant to the RECON-II expressions. The significant 2-algebras are those t.het satisfy the 2-signature and a' set E of axioms. Together the 2-siganture and the set E of axioms, constitute what is called Abstract Data Type T = (2, E) and the significant E-algebras are the so-called Z-models of type T. Therefore a RECON-II expressions a is an element, of the wich is an algebra generated from E. This 2- 211)1`.9 is the set. of Sl !.171-11. RECON-II expressions, and is the initia; model of such expressions CLOG 78]. Given an abstract type T there is one single model for T or one class of nonisomorphic models denominated M(T). In the second cas,4, these models constitute a "quasi" partial order with an initial and terminal model. the exixstence nad uniqueness of the inititia1 model for any type T was shown at. CLOG 773. With r = <SS, F ) , (W ) for s S. is the set of terms of e sort. In RECON-II, those are •he term of determinate sintactic category. The main -sintactic categories are Concepts, Relations, Functions and Nets. A semantic type for s E S is s subset MCI') S MCT> that satisfies the axioms E required from C.W_), constituting the 8 2- abstract type T (for instance Tconcepts, Tnets, etc.). 8 Finally, the type systems was defined, consisting a syntatic structure suitable for the semantic types of each RECON-II expressions and for every type expressions, a set of inference rules wich allows infering its more general type from a RECON-II expressions.

A noção de tipo é intrínseca ao raciocínio humano, na medida que os seres humanos tendem a "classificar" os objetos segundo seu use e seu comportamento como parte do processo de resolução de problemas. Tal classificação dos objetos implica numa abstração das características irrelevantes dos mesmos,permitindo dessa maneira uma simplificação importante da complexidade do universo de discurso Por outro lado, certos problemas são altamente complexos e requerem um tratamento diferenciado.Esses problemas exigem, para sua resolução, um grande conhecimento do universo de discurso. O ponto critico nesta situação é que o domínio do problema não é exato como poderia ser um domínio matemático. Pelo contrario, ele inclui geralmente aspectos ambíguos e pouco formais que dificultam seu entendimento. Tal domínio a chamado de senso comum e é objeto de estudo de uma linha da computação, a Inteligência Artificial (IA). Para [KRA 87], entre outros, as soluc6es pare muitos problemas de IA dependern mais da capacidade de adquirir e manipular conhecimento do que de algoritmos sofisticados. Por este motivo, existem na IA muitos tipos de linguagens que tentam, de di verses maneiras,facilitar a representação de conhecirnentos sobre universos de discurso de problemas particulares. São as chamadas Linguagens de Representação de Conhecimento. A noção de tipo e implícita nas linguagens de representação de conhecimento, uma vez que tal noção é natural no raciocínio humano e esta intimamente ligada ao conceito de abstração. Este trabalho visa explicitar a noção de tipo subjacente ao núcleo definido da linguagem RECON-II. Para isto, foi realizado um estudo semântico prévio para identificar os tipos semânticos da linguagem. A partir da noção semântica dos tipos foi possível definir a correspondente sintática e finalmente, descrever um Sistema de Tipos para RECON-II. Um Sistema de Tipos consiste numa Linguagem de Tipos (tipos básicos + construtores de tipos) e num Sistema de Dedução que relaciona as expresses da linguagem objeto (linguagem de programação com as expresses da linguagem de tipos. Para a primeira etapa realizada neste trabalho, a determinação da semântica da linguagem, foi utilizado o método algébrico. Nele toda expressão RECON-II é um termo de uma assinatura Z, de modo quo cada assinatura Z determina um conjunto de expressos RECON-UL Mas, por outro lado, uma assinatura também determina um conjunto de álgebras. Dessas álgebras-Z só um subconjunto significativo para as expressões RECON-II. As álgebras-Z significativas são aquelas que satisfazem a assinatura-Z mais um conjunto E de axiomas. A assinatura-Z junto como o conjunto E de axiomas constituem o quo se denomina Tipo Abstrato de Dados, T=CZ, E), e as álgebras-Z significativas são os chamados modelos-Z do tipo T. Assim, uma expressão RECON-II a e um elemento da álgebra de termos quo g uma Álgebra gerada a partir do E. Essa álgebra, 44 4-) conjunto das expressi5es_: RECON-II significativas, e o modelo inicial de tais expressões WOG 781 Dado um tipo abstrato T existe um único modelo para T, ou uma classe de modelos, não isomórficos, denominada MCT>. No segundo caso, asses modelos constituem uma "quasi" ordem parcial com modelo inicial e terminal. A existência e unicidade do modelo inicial para qualquer tipo T foi demonstrada por [GOG 77] Com Σ = (S, F). a (Ws )para 9 S, e o conjunto dos termos de "sort." e. Na RECON-II, são os termos de uma categoria sintática determinada. As categorias sintáticas principais são : Conceitos, Relações, Funções e Redes. Um tipo semântico para s E S é um subconjunto M(T) S M(T) quo satisfaz os axiomas E exigidos de (WΣ) s, constituindo o tipo abstrato T .s.(por exemplo TConceitos, TRedes, etc.) Por último foi definido o Sistema de Tipos, que consiste numa estrutura sintática adequada para os tipos semânticos de cada expressão-RECON e, para cada expressão de tipo, um conjunto de regras de inferências que permuta, a partir de uma expressão-RECON inferir seu tipo mais geral. / The notion of type is intrinsic to human reasoning, since human beings tend to classify objects according their use and behaviour as part of the problem solving process. By classifying objects, their irrevelant characteristics are abstrated; in this way, the complexity of the universe of discourse is much reduced. On the other hand, certain problems are higly complex and require a differentiated treatament. In order to solve these problems, a great knowledge of de universe of discourse is needed. The critical proint in this situation is that the domain of the problem isn't as precise as a matliematic domain. On the contrary, it generally, includes ambiguous and not very formal aspects wich make its uderstanding difficult.. Such a domains is known as common sense and this is the object of studies of one line of Computer Science, Artificial Intelligence CAI). For [KRA 871, among others, the solutions for many AI problems depend on the ability for acquiring and manipulating knowledge rather than on sophisticated algorithm. For this reason, there are in AI many type of languages that attemps in different ways, to represent the UD of a particular problem. These languagesare known as Knowledge Representation Languages. The notion of type is implicit in Knowledge Representation Languages, since it is natural in human reasoning and closely rrelated to the concept of abstraction. This work intends to make the notion of type intrinsic to the RECON-II's kernel language, explicity. In order to do this, a preliminary semantic stidy was carriedaut to identify the semantic types of the languages. From the semantic notion of the types it was possible to define the sintactic counterpart and finally to describe a Type System for RECON- II. A Type System conssit of a type language (basic types + types constructors) end a deduction system that relattes expressions in the language object (programming language) to the expressions in the type language. In the first step of this work, language semantic determination, the algebric method was used. In it every RECON-II expression is one term of a signature 2, so Chet every signature 2 determines a RECON-II expressions set. On the other hand, a signature also determines a set of algebras. Out of these 2-algebras only one subset is significant to the RECON-II expressions. The significant 2-algebras are those t.het satisfy the 2-signature and a' set E of axioms. Together the 2-siganture and the set E of axioms, constitute what is called Abstract Data Type T = (2, E) and the significant E-algebras are the so-called Z-models of type T. Therefore a RECON-II expressions a is an element, of the wich is an algebra generated from E. This 2- 211)1`.9 is the set. of Sl !.171-11. RECON-II expressions, and is the initia; model of such expressions CLOG 78]. Given an abstract type T there is one single model for T or one class of nonisomorphic models denominated M(T). In the second cas,4, these models constitute a "quasi" partial order with an initial and terminal model. the exixstence nad uniqueness of the inititia1 model for any type T was shown at. CLOG 773. With r = <SS, F ) , (W ) for s S. is the set of terms of e sort. In RECON-II, those are •he term of determinate sintactic category. The main -sintactic categories are Concepts, Relations, Functions and Nets. A semantic type for s E S is s subset MCI') S MCT> that satisfies the axioms E required from C.W_), constituting the 8 2- abstract type T (for instance Tconcepts, Tnets, etc.). 8 Finally, the type systems was defined, consisting a syntatic structure suitable for the semantic types of each RECON-II expressions and for every type expressions, a set of inference rules wich allows infering its more general type from a RECON-II expressions.