<p>In the first part of this thesis, we contribute to the semantics of typed object calculus by giving (a) a category-theoretic denotational semantics using partial maps making use of an algebraic compactness assumption, (b) a notion of "wrappers'' by which algebraic datatypes can be represented as object types, and (c) proofs of computational soundness and adequacy of typed object calculus via Plotkin's FPC (with lazy operational semantics), thus making models of FPC suitable also for first-order typed object calculus (with recursive objects supporting method update, but not subtyping). It follows that a valid equation in the model induces operationally congruent terms in the language, so that program algebras can be studied. For (c), we also develop an extended first-order typed object calculus, and prove subject reduction. The second part of the thesis concerns recursion principles on datatypes including the untyped lambda calculus as a special case. Freyd showed that in certain domain theoretic categories, locally continuous functors have minimal invariants, which possess a structure that he termed dialgebra. This gives rise to a category of dialgebras and homomorphisms, where the minimal invariants are initial, inducing a powerful recursion scheme (direcursion) on a complete partial order. We identify a problem that appears when we translate (co)iterative functions to direcursion, and as a solution to this problem we develop a recursion scheme (primitive direcursion). This immediately gives a number of examples of direcursive functions, improving on the situation in the literature where only a few examples have appeared. By means of a case study, this line of work is connected to object calculus models.</p> / Delarbete II är även publicerad som Teknisk rapport, 2007, Oct, No2.

In the first part of this thesis, we contribute to the semantics of typed object calculus by giving (a) a category-theoretic denotational semantics using partial maps making use of an algebraic compactness assumption, (b) a notion of "wrappers'' by which algebraic datatypes can be represented as object types, and (c) proofs of computational soundness and adequacy of typed object calculus via Plotkin's FPC (with lazy operational semantics), thus making models of FPC suitable also for first-order typed object calculus (with recursive objects supporting method update, but not subtyping). It follows that a valid equation in the model induces operationally congruent terms in the language, so that program algebras can be studied. For (c), we also develop an extended first-order typed object calculus, and prove subject reduction. The second part of the thesis concerns recursion principles on datatypes including the untyped lambda calculus as a special case. Freyd showed that in certain domain theoretic categories, locally continuous functors have minimal invariants, which possess a structure that he termed dialgebra. This gives rise to a category of dialgebras and homomorphisms, where the minimal invariants are initial, inducing a powerful recursion scheme (direcursion) on a complete partial order. We identify a problem that appears when we translate (co)iterative functions to direcursion, and as a solution to this problem we develop a recursion scheme (primitive direcursion). This immediately gives a number of examples of direcursive functions, improving on the situation in the literature where only a few examples have appeared. By means of a case study, this line of work is connected to object calculus models. / Delarbete II är även publicerad som Teknisk rapport, 2007, Oct, No2.

Computer software is ubiquitous. More than 35 × 10 18 computer instructions are executed around the globe each second. As computers dominate more aspects of our lives, there is a growing need to reason more accurately about computer software. Most contemporary computer software is written using object-oriented (OO) programming languages, such as J AVA, C#, and C++. How should we mathematically characterize object-oriented software? This is the question this thesis addresses by presenting an accurate domain-theoretic model of mainstream object-oriented programming. Mainstream object-oriented languages are class-based. In such languages, the name of a class is part of the meaning of an object, a property often called "nominality". Most mainstream OO languages also conform to a static type discipline. Hence, the focus of this thesis is the construction of an accurate model of nominal, statically-typed OO languages. In statically-typed nominal OO languages, class names are also part of the meaning of corresponding class types, and class inheritance (subclassing) is explicitly declared; one class is a subclass of another only if it is declared as such. When static type systems are formulated to describe sets of objects, subtyping is defined so that subclassing is consistent with subtyping. Nevertheless, some programming languages (PL) theoreticians dismiss this identification as a design error because the only published models of OO languages exclude nominal information from objects and define subtyping in a way that ignores nominality. In nominal OO languages, program behavior depends on the nominal information embedded in objects. This thesis builds a model of OO languages called NOOP that includes nominal information and defines static types in accord with mainstream OO language designs. In NOOP , the meaning of every object includes its class name. Similarly, types are defined such that objects belong to a particular class type if and only if they are members of classes that inherit from the class corresponding to the class type. To demonstrate the utility of the model, we show that in NOOP inheritance and OO subtyping coincide. This work shows that mainstream OO languages are not technically defective in identifying inheritance and subtyping. In models that include nominal information and define types that respect nominal information, this identification is mathematically correct. The folklore among OO programming language researchers that "inheritance is not subtyping" is incorrect.

Der soziale Geschlechterdualismus bestimmt als auf dem Arbeits- wie dem Ausbildungsmarkt gültiges Strukturierungsprinzip über Lebenschancen und –risiken. Das heißt zugleich, dass die Makro-Berufsfeldklassifizierungen als „männlich“ oder „weiblich“ ein Element der sozialen Ordnung der Geschlechter darstellen, die sich durch die kulturelle Annahme „geschlechtsspezifischer“ Neigungen, Begabungen, Kompetenzen und Verhaltensweisen (als für die Berufswahl relevanter Faktoren) legitimiert. Die Schule aber ist ein Teil unseres kulturellen Systems. Die vorliegende Studie hinterfragte darum die Verzahnung des Bildungs- und Beschäftigungssystems aus dem sozialkonstruktivistischen Blickwinkel der „geschlechtsspezifischen“ schulischen Sozialisation und stellte somit die Frage nach deren Bedeutung für das -makrostatistisch betrachtet- geschlechtstypische Berufswahlverhalten der Geschlechter. Im Vordergrund der explorativen Studie stand es dabei herauszufinden, welche berufswahlrelevanten schulischen Einflussfaktoren existieren und wie wesentlich diese Einflussfaktoren für die Berufswahlentscheidung sind. An der quantitativen Untersuchung beteiligten sich bundesweit 33 Schulen (8 Hauptschulen, 9 Realschulen, 5 Gesamtschulen, 11 Gymnasien) bzw. 1513 aus diesen Schulen rekrutierte Befragte (737 Schülerinnen und 776 Schüler der jeweils letzten beiden Klassenstufen der beteiligten Schulformen), die mit Hilfe eines im Internet bereitgestellten elektronischen Erhebungsbogens befragt wurden. Die Untersuchungsergebnisse dokumentierten, dass auch -mit den kulturellen Geschlechterrollen in Kontext stehende- schulische Sozialisationsvorgänge das geschlechtsrollennonkonforme oder aber geschlechterrollenadäquate Berufswahlverhalten von Schülerinnen und Schülern (durch sich auf der curricularen, interaktionalen, strukturellen bzw. berufsorientierenden Ebene ereignende Alltagseinflüsse) prägen. Denn sowohl das schulischerseits mitbeeinflusste fachliche Selbstkonzept als auch das unter anderem von seiten der Schule geformte soziale Selbstkonzept tragen entsprechend den in der Untersuchung ermittelten Korrelationen dazu bei, dass die Berufsfindung geschlechtsrollenorientiert oder eben gerade nicht geschlechtsrollenorientiert verläuft. Da die Schule als zentrale Sozialisationsinstanz nach den Untersuchungsergebnissen nicht nur gemäß ihrem pädagogischen Auftrag durch die gezielte Vermittlung von Fachkompetenzen ohne Ansehen des Geschlechtes auf die Integration in den Ausbildungs- bzw. Arbeitsmarkt vorbereitet und hierfür für beide Geschlechter prinzipiell gleiche Voraussetzungen schafft, sondern im schulischen Rahmen auch berufswahlrelevante Lernprozesse über kulturelle Normen von „Weiblichkeit“ und „Männlichkeit“ stattfinden, die mit der „geschlechtsspezifischen“ Segregation des Ausbildungs- und Arbeitsmarktes korrespondieren, ergibt sich hier ein deutlicher Handlungsbedarf im Sinne eines veränderten schulischen Verständnisses für die Kompetenzvermittlung zur perspektivischen Integration in das Beschäftigungssystem. Diesem Handlungsbedarf nach einem (per Festschreibung der Koedukation) nicht nur theoretischen, sondern auch in der alltäglichen Praxis verankerten Selbstverständnis der Schule als androgyner Lehr- und Lernraum für alle Altersklassen wird in den aus dem Erhebungsbogen abgeleiteten pädagogisch-sozialpädagogischen Schlussfolgerungen Rechnung getragen. Des weiteren verweisen die Schlussfolgerungen auf das bildungspolitische Erfordernis, die Koedukation bundeseinheitlich!- tatsächlich bildungsprogrammatisch (und nicht nur wie bisher primär pragmatisch) zu verankern und ihren emanzipatorischen pädagogischen Auftrag in einer Bildungs- und Erziehungstheorie detailliert auszuformulieren, um dergestalt kontinuierlich (über die Schuljahre) und systematisch (also fächerübergreifend) den schulischen Beitrag zum Gelingen einer wahrhaft selbstbestimmten Berufswahl von Jugendlichen zu leisten – gerade in Zeiten demographisch und globalisierungsbedingter Umbrüche, die nicht nur eine raschere Ausbreitung neuer beruflicher Vorbilder für Frauen und Männer gestatten, sondern sie geradezu bedingen. Die methodischen Schlussfolgerungen der Erhebung sind in einem Konzept für die sozialwissenschaftliche Nutzung des Internets zu Befragungszwecken zusammengefasst. (Dissertation zum Thema: „Zur Stimmigkeit zwischen „geschlechtsspezifischer“ Sozialisationserfahrung in der Schule und geschlechter-segregativer Arbeitsmarktstruktur“)

Der soziale Geschlechterdualismus bestimmt als auf dem Arbeits- wie dem Ausbildungsmarkt gültiges Strukturierungsprinzip über Lebenschancen und –risiken. Das heißt zugleich, dass die Makro-Berufsfeldklassifizierungen als „männlich“ oder „weiblich“ ein Element der sozialen Ordnung der Geschlechter darstellen, die sich durch die kulturelle Annahme „geschlechtsspezifischer“ Neigungen, Begabungen, Kompetenzen und Verhaltensweisen (als für die Berufswahl relevanter Faktoren) legitimiert. Die Schule aber ist ein Teil unseres kulturellen Systems. Die vorliegende Studie hinterfragte darum die Verzahnung des Bildungs- und Beschäftigungssystems aus dem sozialkonstruktivistischen Blickwinkel der „geschlechtsspezifischen“ schulischen Sozialisation und stellte somit die Frage nach deren Bedeutung für das -makrostatistisch betrachtet- geschlechtstypische Berufswahlverhalten der Geschlechter. Im Vordergrund der explorativen Studie stand es dabei herauszufinden, welche berufswahlrelevanten schulischen Einflussfaktoren existieren und wie wesentlich diese Einflussfaktoren für die Berufswahlentscheidung sind. An der quantitativen Untersuchung beteiligten sich bundesweit 33 Schulen (8 Hauptschulen, 9 Realschulen, 5 Gesamtschulen, 11 Gymnasien) bzw. 1513 aus diesen Schulen rekrutierte Befragte (737 Schülerinnen und 776 Schüler der jeweils letzten beiden Klassenstufen der beteiligten Schulformen), die mit Hilfe eines im Internet bereitgestellten elektronischen Erhebungsbogens befragt wurden. Die Untersuchungsergebnisse dokumentierten, dass auch -mit den kulturellen Geschlechterrollen in Kontext stehende- schulische Sozialisationsvorgänge das geschlechtsrollennonkonforme oder aber geschlechterrollenadäquate Berufswahlverhalten von Schülerinnen und Schülern (durch sich auf der curricularen, interaktionalen, strukturellen bzw. berufsorientierenden Ebene ereignende Alltagseinflüsse) prägen. Denn sowohl das schulischerseits mitbeeinflusste fachliche Selbstkonzept als auch das unter anderem von seiten der Schule geformte soziale Selbstkonzept tragen entsprechend den in der Untersuchung ermittelten Korrelationen dazu bei, dass die Berufsfindung geschlechtsrollenorientiert oder eben gerade nicht geschlechtsrollenorientiert verläuft. Da die Schule als zentrale Sozialisationsinstanz nach den Untersuchungsergebnissen nicht nur gemäß ihrem pädagogischen Auftrag durch die gezielte Vermittlung von Fachkompetenzen ohne Ansehen des Geschlechtes auf die Integration in den Ausbildungs- bzw. Arbeitsmarkt vorbereitet und hierfür für beide Geschlechter prinzipiell gleiche Voraussetzungen schafft, sondern im schulischen Rahmen auch berufswahlrelevante Lernprozesse über kulturelle Normen von „Weiblichkeit“ und „Männlichkeit“ stattfinden, die mit der „geschlechtsspezifischen“ Segregation des Ausbildungs- und Arbeitsmarktes korrespondieren, ergibt sich hier ein deutlicher Handlungsbedarf im Sinne eines veränderten schulischen Verständnisses für die Kompetenzvermittlung zur perspektivischen Integration in das Beschäftigungssystem. Diesem Handlungsbedarf nach einem (per Festschreibung der Koedukation) nicht nur theoretischen, sondern auch in der alltäglichen Praxis verankerten Selbstverständnis der Schule als androgyner Lehr- und Lernraum für alle Altersklassen wird in den aus dem Erhebungsbogen abgeleiteten pädagogisch-sozialpädagogischen Schlussfolgerungen Rechnung getragen. Des weiteren verweisen die Schlussfolgerungen auf das bildungspolitische Erfordernis, die Koedukation bundeseinheitlich!- tatsächlich bildungsprogrammatisch (und nicht nur wie bisher primär pragmatisch) zu verankern und ihren emanzipatorischen pädagogischen Auftrag in einer Bildungs- und Erziehungstheorie detailliert auszuformulieren, um dergestalt kontinuierlich (über die Schuljahre) und systematisch (also fächerübergreifend) den schulischen Beitrag zum Gelingen einer wahrhaft selbstbestimmten Berufswahl von Jugendlichen zu leisten – gerade in Zeiten demographisch und globalisierungsbedingter Umbrüche, die nicht nur eine raschere Ausbreitung neuer beruflicher Vorbilder für Frauen und Männer gestatten, sondern sie geradezu bedingen. Die methodischen Schlussfolgerungen der Erhebung sind in einem Konzept für die sozialwissenschaftliche Nutzung des Internets zu Befragungszwecken zusammengefasst. (Dissertation zum Thema: „Zur Stimmigkeit zwischen „geschlechtsspezifischer“ Sozialisationserfahrung in der Schule und geschlechter-segregativer Arbeitsmarktstruktur“)

L'utilisation des méthodes formelles est de plus en plus courante dans le développement logiciel, et les systèmes de types sont la méthode formelle qui a le plus de succès. L'avancement des méthodes formelles présente de nouveaux défis, ainsi que de nouvelles opportunités. L'un des défis est d'assurer qu'un compilateur préserve la sémantique des programmes, de sorte que les propriétés que l'on garantit à propos de son code source s'appliquent également au code exécutable. Cette thèse présente un compilateur qui traduit un langage fonctionnel d'ordre supérieur avec polymorphisme vers un langage assembleur typé, dont la propriété principale est que la préservation des types est vérifiée de manière automatisée, à l'aide d'annotations de types sur le code du compilateur. Notre compilateur implante les transformations de code essentielles pour un langage fonctionnel d'ordre supérieur, nommément une conversion CPS, une conversion des fermetures et une génération de code. Nous présentons les détails des représentation fortement typées des langages intermédiaires, et les contraintes qu'elles imposent sur l'implantation des transformations de code. Notre objectif est de garantir la préservation des types avec un minimum d'annotations, et sans compromettre les qualités générales de modularité et de lisibilité du code du compilateur. Cet objectif est atteint en grande partie dans le traitement des fonctionnalités de base du langage (les «types simples»), contrairement au traitement du polymorphisme qui demande encore un travail substantiel pour satisfaire la vérification de type. / Formal methods are rapidly improving and gaining ground in software. Type systems are the most successful and popular formal method used to develop software. As the technology of type systems progresses, new needs and new opportunities appear. One of those needs is to ensure the faithfulness of the translation from source code to machine code, so that the properties you prove about the code you write also apply to the code you run. This thesis presents a compiler from a polymorphic higher-order functional language to typed assembly language, whose main property is that type preservation is verified statically, through type annotations on the compiler's code. Our compiler implements the essential code transformations for a higher-order functional language, namely a CPS conversion and closure conversion as well as a code generation. The thesis presents the details of the strongly typed intermediate representations and the constraints they set on the implementation of code transformations. Our goal is to guarantee type preservation with a minimum of type annotations, and without compromising readability and modularity of the code. This goal is already a reality for simple types, and we discuss the problems remaining for polymorphism, which still requires substantial extra work to satisfy the type checker.

Cette thèse s’inscrit dans le cadre du projet Région Aquitaine - INRIA : ITIPY. Ce projet vise à terme l’extraction automatique d’itinéraires à partir de récits de voyage du XIX ème et du début du XX ème siècle. Notre premier travail fut de caractériser le corpus comme échantillon du français, par une étude contrastive d’une part de données quantitatives et d’autre part de la structure des récits de voyage. Nous nous sommes ensuite consacrée à l’étude du temps, et plus particulièrement à l’analyse automatique de la sémantique des temps verbaux du français. Disposant d’un analyseur syntaxique et sémantique à large échelle du français, basé sur les grammaires catégorielles et la sémantique compositionnelle (λ-DRT), notre tâche a été de prendre en compte les temps des verbes pour reconstituer la temporalité des événements et des états, notions regroupées sous le termes d’éventualité. Cette thèse se concentre sur la construction d’un lexique sémantique traitant des temps verbaux du français. Nous proposons une extension et une adaptation d’un système d’opérateurs compositionnels conçu pour les temps du verbe anglais, aux temps et à l’aspect du verbe français du XIX ème siècle à nos jours. Cette formalisation est de facto opérationnelle, car elle est définie en terme d’opérateurs du λ-calcul dont la composition et la réduction, déjà programmées, calculent automatiquement les représentations sémantiques souhaitées, des formules multisortes de la logique d’ordre supérieur. Le passage de l’énoncé comportant une éventualité seule au discours, dont le maillage référentiel est complexe, est discuté et nous concluons par les perspectives qu’ouvre nos travaux pour l’analyse du discours. / This work has been lead in the frame of the ITIPY project which goal was to automatically extract itineraries from travel novels from the XIX th century and from the beginning of the XX th. Our thesis work is close to the text understanding task in the information retrieval field and we aim at building a representation of meaning of linguistic utterances, leaning on the compositionnality principle. More precisely, the itinerary extraction supposes to temporally represent displacement and localization events or states (that we actually call eventualities) of a traveler as far as we understand it through discourse. Working on an automatic parser for syntax (in categorial grammars) and semantics (in λ-DRT), we focused on the building of an semantic lexicon for tense in French. We actually characterized our corpora as a sample of French language, by the means of a quantitative and qualitative analysis as well as a study of the internal structure of this genre. The main contribution of this work deals with tense and aspect semantic processing of the event expressed by tensed verbs, and with its modelling. In this respect, we propose an adaptation and an extension for French from XIX th century to nowadays of a lexicon originally produced to deal with English verbs. This formalisation is operational, for it is defined in λ-calculus which composition and réduction, already implemented, calculate automatically semantics représentations, high order logic formulas. Transition from a single event uterrance to a whole discourse which contains a complex referential network is discussed and allows us to define the limits of this hereby work.

<p>In this thesis I have investigated verb frame divergences in a bilingual Head-driven Phrase Structure Grammar for machine translation. The purpose was threefold: (1) to describe and classify verb frame divergences (VFDs) between Swedish and English, (2) to practically implement a bilingual grammar that covered many of the identified VFDs and (3) to find out what cases of VFDs could be solved and implemented using a common semantic representation, or interlingua, for Swedish and English.</p><p>The implemented grammar, BiTSE, is a Head-driven Phrase Structure Grammar based on the LinGO Grammar Matrix, a language independent grammar base. BiTSE is a bilingual grammar containing both Swedish and English. The semantic representation used is Minimal Recursion Semantics (MRS). It is language independent, so generating from it gives all equivalent sentences in both Swedish and English. Both the core of the languages and a subset of the identified VFDs are successfully implemented in BiTSE. For other VFDs tentative solutions are discussed.</p><p>MRS have previously been proposed as suitable for semantic transfer machine translation. I have shown that VFDs can naturally be handled by an interlingual design in many cases, minimizing the need of transfer.</p><p>The main contributions of this thesis are: an inventory of English and Swedish verb frames and verb frame divergences; the bilingual grammar BiTSE and showing that it is possible in many cases to use MRS as an interlingua in machine translation.</p>

As predicted by Gordon Moore, the number of transistors on a chip has roughly doubled every two years. Microprocessors featuring over a billion transistors are no longer science fiction. For example, Intel’s Itanium 9000 series and Intel’s Xeon 7400 series of processors feature 1.7 and 1.9 billion transistors respectively. To keep up with the emerging needs of contemporary very large scale integration (VLSI) design, industrial hardware description languages (HDLs) like Verilog and VHDL must be significantly enhanced. This thesis pinpoints some of the main shortcomings of the latest Verilog standard (IEEE 1364-2005) and shows how to overcome them by extending the language in a backward compatible way. To be able to cope with more complex circuits, well-understood higher-level abstraction mechanisms are needed. Verilog is already equipped with promising generative constructs making it possible to concisely describe a family of circuits as a parameterized module; however these constructs suffer from two problems: First, their expressivity is limited and second, they are not adequately supported by current tools. For instance, there are no static guarantees about the properties of the description generated as a result of instantiating a generic description with particular parameter values. Addressing both problems while remaining backward compatible led us to select a statically typed two-level languages (STTL) formal framework. By formalizing a core subset of Verilog as an STTL, we were able to define a static type system capable of: 1) checking the realizability of a description, 2) detecting bus width mismatches and array bounds violations, and 3) providing parametric guarantees on the resources required to realize a generic description. The power of the chosen framework is once more demonstrated as it also allows us to enrich the language with a new set of constructs that are designed to be expanded away when instantiated. To experiment with these ideas we implemented VPP, a Verilog Preprocessor with a built-in type checker. VPP is an unobtrusive tool accepting extended Verilog descriptions but generating descriptions compatible with any tool compliant with the Verilog standard. Our experience throughout this research showed that STTLs present a particularly suitable framework to formalize and implement generative features of a language. / Rice University, National Science Foundation (NSF) SoD award 0439017, Intel Corporation, Semiconductor Research Corporation (SRC) Task ID 1403.001

L'utilisation des méthodes formelles est de plus en plus courante dans le développement logiciel, et les systèmes de types sont la méthode formelle qui a le plus de succès. L'avancement des méthodes formelles présente de nouveaux défis, ainsi que de nouvelles opportunités. L'un des défis est d'assurer qu'un compilateur préserve la sémantique des programmes, de sorte que les propriétés que l'on garantit à propos de son code source s'appliquent également au code exécutable. Cette thèse présente un compilateur qui traduit un langage fonctionnel d'ordre supérieur avec polymorphisme vers un langage assembleur typé, dont la propriété principale est que la préservation des types est vérifiée de manière automatisée, à l'aide d'annotations de types sur le code du compilateur. Notre compilateur implante les transformations de code essentielles pour un langage fonctionnel d'ordre supérieur, nommément une conversion CPS, une conversion des fermetures et une génération de code. Nous présentons les détails des représentation fortement typées des langages intermédiaires, et les contraintes qu'elles imposent sur l'implantation des transformations de code. Notre objectif est de garantir la préservation des types avec un minimum d'annotations, et sans compromettre les qualités générales de modularité et de lisibilité du code du compilateur. Cet objectif est atteint en grande partie dans le traitement des fonctionnalités de base du langage (les «types simples»), contrairement au traitement du polymorphisme qui demande encore un travail substantiel pour satisfaire la vérification de type. / Formal methods are rapidly improving and gaining ground in software. Type systems are the most successful and popular formal method used to develop software. As the technology of type systems progresses, new needs and new opportunities appear. One of those needs is to ensure the faithfulness of the translation from source code to machine code, so that the properties you prove about the code you write also apply to the code you run. This thesis presents a compiler from a polymorphic higher-order functional language to typed assembly language, whose main property is that type preservation is verified statically, through type annotations on the compiler's code. Our compiler implements the essential code transformations for a higher-order functional language, namely a CPS conversion and closure conversion as well as a code generation. The thesis presents the details of the strongly typed intermediate representations and the constraints they set on the implementation of code transformations. Our goal is to guarantee type preservation with a minimum of type annotations, and without compromising readability and modularity of the code. This goal is already a reality for simple types, and we discuss the problems remaining for polymorphism, which still requires substantial extra work to satisfy the type checker.