Production compilers implement optimizing transformation rules for built-in types. What justifies applying these optimizing rules is the axioms that hold for built-in types and the built-in operations supported by these types. Similar axioms also hold for user-defined types and the operations defined on them, and therefore justify a set of optimization rules that may apply to user-defined types. Production compilers, however, do not attempt to construct and apply these optimization rules to user-defined types. Built-in types together the axioms that apply to them are instances of more general algebraic structures. So are user-defined types and their associated axioms. We use the technique of generic programming, a programming paradigm to design efficient, reusable software libraries, to identify the commonality of classes of types, whether built-in or user-defined, convey the semantics of the classes of types to compilers, design scalable and effective program analysis for them, and eventually apply optimizing rules to the operations on them. In generic programming, algorithms and data structures are defined in terms of such algebraic structures. The same definitions are reused for many types, both built-in and user-defined. This dissertation applies generic programming to compiler analyses and transformations. Analyses and transformations are specified for general algebraic structures, and they apply to all types, both built-in and primitive types.

The Power Wall has stopped the past trend of increasing processor throughput by increasing the clock frequency and the instruction level parallelism.Therefore, the current trend in computer hardware design is to expose explicit parallelism to the software level.This is most often done using multiple processing cores situated on a single processor chip.The cores usually share some resources on the chip, such as some level of cache memory (which means that they also share the interconnect, e.g. a bus, to that memory and also all higher levels of memory), and to fully exploit this type of parallel processor chip, programs running on it will have to be concurrent.Since multi-core processors are the new standard, even embedded real-time systems will (and some already do) incorporate this kind of processor and concurrent code. A real-time system is any system whose correctness is dependent both on its functional and temporal output. For some real-time systems, a failure to meet the temporal requirements can have catastrophic consequences. Therefore, it is of utmost importance that methods to analyze and derive safe estimations on the timing properties of parallel computer systems are developed. This thesis presents an analysis that derives safe (lower and upper) bounds on the execution time of a given parallel system.The interface to the analysis is a small concurrent programming language, based on communicating and synchronizing threads, that is formally (syntactically and semantically) defined in the thesis.The analysis is based on abstract execution, which is itself based on abstract interpretation techniques that have been commonly used within the field of timing analysis of single-core computer systems, to derive safe timing bounds in an efficient (although, over-approximative) way.Basically, abstract execution simulates the execution of several real executions of the analyzed program in one go.The thesis also proves the soundness of the presented analysis (i.e. that the estimated timing bounds are indeed safe) and includes some examples, each showing different features or characteristics of the analysis. / Worst-Case Execution Time Analysis of Parallel Systems / RALF3 - Software for Embedded High Performance Architectures

The thesis explores the possible use of parametric object definitions during capacity analysis to support Open Building design processes.The study proposes that design criteria regarding possible size, position and relation of design elements can be formulated and modeled parametrically. Then developed parametric data can be used as library objects during the exploration of dwelling unit layout alternatives. Parametric models, holding explicit design information can be shared, modified and re-used in different design cases. The process and criteria used in the study are based on S.A.R. (Stichting Architecten Research) methods described in the study, "Variations - The Systematic Design of Supports" focused particularly on residential building types. Parallel to the S.A.R methods, the study focuses on the spatial capacity analysis between a floor plate and a number of alternative dwelling unit layout arrangements. Other capacity analyses such as structural, daylight or thermal performances can be formulated and studied in a similar way, but are not included in this study.GDL (Geometric Description Language), a programming medium for ArchiCAD software, is used for the production of parametric models. The Keyenburg housing project designed by Dutch architect Frans Van Der Werf is taken as a base-building model to demonstrate the development and the use of parametric models.Keywords: Open Building, capacity analysis, parametric objects, design constraints, GDL (Geometric Description Language) / Department of Architecture

Writing truly concurrent software is hard, scaling software to fully utilize hardware is one of the reasons why. One abstraction for increasing the scalability of systems software is clustered objects. Clustered objects is a proven method of increasing scalability. This thesis explores a user-level abstraction based on clustered objects which increases hardware utilization without requiring any customization of the underlying system. We detail the design, implementation and testing of Scalable Clustered Objects with Portable Events or (SCOPE), a user-level system inspired by an implementation of the clustered objects model from IBM Research’s K42 operating system. To aid in the portability of the new system, we introduce the idea of a clustered object event, which is responsible for maintaining the runtime environment of the clustered objects. We show that SCOPE can increase scalability on a simple micro benchmark, and provide most of the benefits that the kernel-level implementation provided.

Thesis (M.S.)--Rochester Institute of Technology, 1990. / Includes bibliographical references (leaves 70-71).

Context Writing and working with regular expressions could be a slow and tedious task,which is mainly because of its syntax, but also because there exist several different dialectswhich easily could cause confusion. Even though regular expression has been widely used forparsing and programming language design, they are now frequently used for input validationand seen in common applications such as text editors. Objectives The main objectives of our thesis are to determine whether or not a regularexpression language that is more like the surrounding programming language would increaseusability, readability, and maintainability. We will then investigate further into what kind ofimpact this would have regarding e.g, development speed, and what benefits and liabilities amore modernized syntax could introduce. Methods Two different methods were used to answer our research questions, exploratory in-terviews, and experiments. The data from the experiments were collected by screen recordingand a program in the environment we provided to the participant. Results.By doing interviews with developers that use traditional regular expressions on aregular basis, their stories confirm that its syntax is confusing even for developers with alot of experience. Our results from the experiment indicate that a language more like thesurrounding language increases both the overall ease of use and development speed. Conclusions From this research, we can conclude that a regular expression language thatis more like the surrounding programming language does increase usability, readability, andmaintainability. We could clearly see that it had a positive effect on the development speed aswell. Keywords — regular expressions, programming language design, readability

The task of implementing a programming language is a task that entails a great deal of work. Yet much of this work is similar for different programming languages: most languages require, e.g., parsing, name resolution, type-checking, and optimization. When implementing domain-specific languages (DSLs) the reimplementation of these largely similar tasks seems especially redundant. A number of approaches exist to alleviate this issue, including embedded DSLs, macro-rewriting systems, and more general systems intended for language implementation. However, these tend to have at least one of the following limitations: They present a leaky abstraction, e.g., error messages do not refer to the DSL but rather some other programming language, namely the one used to implement the DSL. They limit the flexibility of the DSL, either to the constructs present in another language, or merely to the syntax of some other language. They see an entire language as the unit of composition. Complete languages are extended with other complete language extensions. Instead, this thesis introduces the concept of a syntax construction, which represents a smaller unit of composition. A syntax construction defines a single language feature, e.g., an if-statement, an anonymous function, or addition. Each syntax construction specifies its own syntax, binding semantics, and runtime semantics, independent of the rest of the language. The runtime semantics are defined using a translation into another target language, similarly to macros. These translations can then be checked to ensure that they preserve binding semantics and introduce no binding errors. This checking ensures that binding errors can be presented in terms of code the programmer wrote, rather than generated code in some underlying language. During evaluation several limitations are encountered. Removing or minimizing these limitations appears possible, but is left for future work / Att implementera ett programmeringsspråk är ett mycket arbetstungt åtagande. Detta trots att mycket av det som behöver göras inte skiljer sig särskilt mycket mellan olika språk, de flesta behöver exempelvis parsning, namnupplösning, typcheckning och optimering. För ett domänspecifikt programmeringsspråk (DSL) är denna upprepning ännu mer tydlig. Det finns ett antal olika metoder för att hantera detta, exempelvis embeddade DSLer, macro-system, och mer generella system för programspråksimplementation. Dessa tenderar dock att ha en eller flera av följande begränsningar: De abstraktioner som introduceras "läcker", felmeddelanden kan exempelvis referera till abstraktioner i ett annat programmeringsspråk, nämligen det som användes för att implementera DSLet. DSLet som implementeras blir begränsat, antingen till vad som finns i implementationsspråket, eller till implementationsspråkets syntax. Ett DSL ses som den minsta hela beståndsdelen i systemet. Om delar av språket ska återanvändas eller inkluderas i ett annat måste hela språket följa med. Denna avhandling introducerar istället syntaxkonstruktioner som minsta beståndsdel. En syntaxkonstruktion representerar en enskild del av ett språk, exempelvis en if-sats, en anonym funktion, eller addition. Varje syntaxkonstruktion definierar sin egen syntax, bindningssemantik och exekveringssemantik, utan referenser till språket som helhet. Exekveringssemantiken liknar en macro, den uttrycks som en översättning till ett implementationsspråk. Tack vare att bindningssemantiken är specifierad kan vi sedan kontrollera översättningen så att den inte kan introducera bindningsfel. Detta medför att felmeddelanden kan referera enbart till kod som programmeraren faktiskt skrev, istället för genererad kod i implementationsspråket. Evalueringen påvisar flera begränsningar med systemet. Begränsningarna tycks lösbara, men detta arbete lämnas till framtiden.

As an extension to the ongoing Coconut (COde COnstructing User Tool) project at McMaster University, we present a Scala library for constructing type-safe domain-specific languages that uses Coconut’s hypergraph-based representation of code (code graphs) as the intermediate representation. Our library automatically produces strongly typed, deeply embedded DSLs given only a minimal specification of the DSL’s value types and primitives. We make extensive use of path-dependent types and implicit argument lookup to construct a type-safe interface on-the-fly, rather than requiring DSL designers to explicitly create a type-safe interface. In this thesis we present our library and demonstrate its utility as both a general-purpose DSL framework and as a suitable platform for continued research on the Coconut project. By giving practical examples of the library in use, we demonstrate both its general utility, and the striking swiftness with which new DSLs may be constructed, especially compared to the previously laborious Haskell DSLs of Coconut. / Thesis / Master of Science (MSc)

No description available.

<p> The Haskell programming language uses type classes to deal with overloading. Functions are overloaded by defining some types to be instances of a class. A meaningful instance should satisfy the invariants of the class.</p> <p> In this thesis we present one method to validate the type instances of classes informally, and another one to verify them in a formal way.</p> <p> The first method uses QuickCheck, which is an automatic testing tool for Haskell programs. We introduce how to specify the properties of type classes in QuickCheck by some examples, and I also present testing for Haskell standard types and classes.</p> <p> The second method I adopted uses the theorem prover Isabelle/HOL. To facilitate the usage of Isabelle/HOL for Haskell programmers, I define a set of translation rules from Haskell programs to Isabelle/HOL, and design a simple automatic translating tool based on those rules. Logical differences between Haskell and Isabelle/HOL need to be considered in the translation. For example Isabelle/HOL is not suitable to describe the semantics of lazy evaluation and of Haskell functions that are non-terminating. I also prove some type instances to illustrate how the properties are verified in Isabelle/HOL.</p> / Thesis / Master of Applied Science (MASc)