this paper presents an automatic deforestation system, stream fusion, based on equational transformations, that fuses a wider range of functions than existing short-cut fusion systems. In particular, stream fusion is ...
详细信息
ISBN:
(纸本)9781595938152
this paper presents an automatic deforestation system, stream fusion, based on equational transformations, that fuses a wider range of functions than existing short-cut fusion systems. In particular, stream fusion is able to fuse zips, left folds and functions over nested lists, including list comprehensions. A distinguishing feature of the framework is its simplicity: by transforming list functions to expose their structure, intermediate values are eliminated by general purpose compiler optimisations. We have reimplemented the Haskell standard List library on top of our framework, providing stream fusion for Haskell lists. By allowing a wider range of functions to fuse, we see an increase in the number of occurrences of fusion in typical Haskell programs. We present benchmarks documenting time and space improvements.
A tree transducer is a set of mutually recursive functions transforming an input tree into an output tree. Macro tree transducers extend this recursion scheme by allowing each function to be defined in terms of an arb...
详细信息
ISBN:
(纸本)9781450323895
A tree transducer is a set of mutually recursive functions transforming an input tree into an output tree. Macro tree transducers extend this recursion scheme by allowing each function to be defined in terms of an arbitrary number of accumulation parameters. In this paper, we show how macro tree transducers can be concisely represented in Haskell, and demonstrate the benefits of utilising such an approach with a number of examples. In particular, tree transducers afford a modular programming style as they can be easily composed and manipulated. Our Haskell representation generalises the original definition of (macro) tree transducers, abolishing a restriction on finite state spaces. However, as we demonstrate, this generalisation does not affect compositionality.
We present a declarative, object-oriented language in which queries play a central role. Queries are used not only to access data, but also to refer to the application's object members and as a means of program co...
详细信息
ISBN:
(纸本)9781450360302
We present a declarative, object-oriented language in which queries play a central role. Queries are used not only to access data, but also to refer to the application's object members and as a means of program control. the language is fully declarative, with queries and other pure functions defining the relations between the attributes of different objects. A rule-base-like write operation allows state to be updated. Control is achieved by queries selecting the class variants (mixin classes) which are active in each object. the dynamic activation and deactivation of declarative mixin classes allows decomposition of functionality into small reusable classes. the programming style in the language is functional and reactive, with function applications defining object members. Queries are one type of function, which also serves as the glue which puts these functions together, providing them withtheir input. Since queries describe declaratively what they return, they leave it to the system to implement the how of getting it. Combining this with an organization around objects makes the language highly suitable for complex interactive applications driven by large amounts of data from multiple sources. Our implementation of the language includes a strong display component. It can be seen as a conceptual extension of HTML and CSS in a way which replaces the need for the JavaScript imperative component in web applications. the work described here is not restricted, however, to front-end development and can be applied elsewhere as well.
Current languages allow a programmer to describe an interface only by enumerating its parts, possibly including other interfaces wholesale. Such languages cannot express relationships between interfaces, yet when inde...
详细信息
ISBN:
(纸本)9781595930644
Current languages allow a programmer to describe an interface only by enumerating its parts, possibly including other interfaces wholesale. Such languages cannot express relationships between interfaces, yet when independently developed software components are combined into a larger system, significant relationships arise, To address this shortcoming, we define, as a conservative extension of ML, a language for manipulating interfaces. Our language includes operations for adding, renaming, and removing components;for changing the type associated with a value;for making manifest types abstract and vice versa;and for combining interfaces. these operations can express useful relationships among interfaces. We have defined a formal semantics in which an interface denotes a group of four sets;we show how these sets determine a subtyping relation, and we sketch the elaboration of an interface into its denotation.
MashMaker is a web-based tool that makes it easy for a normal user to create web mashups by browsing around, without needing to type, or plan in advance what they want to do. Like a web browser, Mashmaker allows users...
详细信息
ISBN:
(纸本)9781595938152
MashMaker is a web-based tool that makes it easy for a normal user to create web mashups by browsing around, without needing to type, or plan in advance what they want to do. Like a web browser, Mashmaker allows users to create mashups by browsing, rather than writing code, and allows users to bookmark interesting things they find, forming new widgets-reusable mashup fragments. Like a spreadsheet, MashMaker mixes program and data and allows ad-hoc unstructured editing of programs. MashMaker is also a modern functionalprogramming language with non-side effecting expressions, higher order functions, and lazy evaluation. MashMaker programs can be manipulated either textually, or through an interactive tree representation, in which a program is presented together withthe values it produces. In order to cope withthis unusual domain, MashMaker contains a number of deviations from normal function languages. the most notable of these is that, in order to allow the programmer to write programs directly on their data, all data is stored in a single tree, and evaluation of an expression always takes place at a specific point in this tree, which also functions as its scope.
Relational database management systems (RDBMS) are operationally similar to a dynamic language processor. they take SQL queries as input, dynamically generate an optimized execution plan, and then execute it. In recen...
详细信息
ISBN:
(纸本)9781450360302
Relational database management systems (RDBMS) are operationally similar to a dynamic language processor. they take SQL queries as input, dynamically generate an optimized execution plan, and then execute it. In recent decades, the emergence of in-memory databases with columnar storage, which use array-like storage structures, has shifted the focus on optimizations from the traditional I/O bottleneck to CPU and memory. However, database research so far has primarily focused on CPU cache optimizations. the similarity in the computational characteristics of such database workloads and array programming language optimizations are largely unexplored. We believe that these database implementations can benefit from merging database optimizations with dynamic array-based programming language approaches. therefore, in this paper, we propose a novel approach to optimize database query execution using a new array-based intermediate representation, HorseIR, that resides between database queries and compiled code. Furthermore, we provide a translator to generate HorseIR from database execution plans and a compiler that optimizes HorseIR and generates efficient code. We compare HorseIR withthe MonetDB RDBMS, by testing standard SQL queries, and show how our approach and compiler optimizations improve the runtime of complex queries.
programming languages are the way for a person to express a mental plan in a way that the computer can understand. therefore, it is appropriate to consider properties of people when designing new programming languages...
详细信息
programming languages are the way for a person to express a mental plan in a way that the computer can understand. therefore, it is appropriate to consider properties of people when designing new programming languages. In our research, we are investigating how people think about algorithms, and how programming languages can be made easier to learn and more effective for people to use. By taking human-productivity aspects of programming languages seriously, designers can more effectively match programming language features with human capabilities and problem solving methods. Human factors methods can be used to measure the effects, so unsubstantiated claims can be avoided. this talk will present a quick summary of new and old results in what is known about people and programming;from areas that are sometimes called "empirical studies of programmers" and "psychology of programming." Much is known about what people find difficult, and what syntax and language features are especially tricky and bug-prone. Our new research has discovered how people naturally think about algorithms and data structures, which can help with making programming languages more closely match people's problem solving techniques.
We describe the Funlogic system which extends a functional language with existentially quantified declarations. An existential declaration introduces a variable and a set of constraints that its value should meet. Exi...
详细信息
It is possible to extend the basic notion of "function call" to allow functions to have multiple return points. this turns out to be a surprisingly useful mechanism. this article conducts a fairly wide-rangi...
详细信息
It is possible to extend the basic notion of "function call" to allow functions to have multiple return points. this turns out to be a surprisingly useful mechanism. this article conducts a fairly wide-ranging tour of such a feature: a formal semantics for a minimal A-calculus capturing the mechanism;motivating examples;monomorphic and parametrically polymorphic static type systems;useful transformations;implementation concerns and experience with an implementation;and comparison to related mechanisms, such as exceptions, sum-types and explicit continuations. We conclude that multiple-return function call is not only a useful and expressive mechanism, at boththe source-code and intermediate-representation levels, but also quite inexpensive to implement.
Many useful programming constructions can be expressed as monads. Examples include probabilistic modeling, functional reactive programming, parsing, and information flow tracking, not to mention effectful functionalit...
详细信息
ISBN:
(纸本)9781450308656
Many useful programming constructions can be expressed as monads. Examples include probabilistic modeling, functional reactive programming, parsing, and information flow tracking, not to mention effectful functionality like state and I/O. In this paper, we present a type-based rewriting algorithm to make programming with arbitrary monads as easy as using ML's built-in support for state and I/O. Developers write programs using monadic values of type m T as if they were of type T, and our algorithm inserts the necessary binds, units, and monad-to-monad morphisms so that the program type checks. Our algorithm, based on Jones' qualified types, produces principal types. But principal types are sometimes problematic: the program's semantics could depend on the choice of instantiation when more than one instantiation is valid. In such situations we are able to simplify the types to remove any ambiguity but without adversely affecting typability;thus we can accept strictly more programs. Moreover, we have proved that this simplification is efficient (linear in the number of constraints) and coherent: while our algorithm induces a particular rewriting, all related rewritings will have the same semantics. We have implemented our approach for a core functional language and applied it successfully to simple examples from the domains listed above, which are used as illustrations throughout the paper.
暂无评论