In order to achieve the highest possible performance, the ray traversal and intersection routines at the core of every high-performance ray tracer are usually hand-coded, heavily optimized, and implemented separately ...
详细信息
ISBN:
(纸本)9781450355247
In order to achieve the highest possible performance, the ray traversal and intersection routines at the core of every high-performance ray tracer are usually hand-coded, heavily optimized, and implemented separately for each hardware platform-even though they share most of their algorithmic core. the results are implementations that heavily mix algorithmic aspects with hardware and implementation details, making the code non-portable and difficult to change and maintain. In this paper, we present a new approach that offers the ability to define in a functional language a set of conceptual, high-level language abstractions that are optimized away by a special compiler in order to maximize performance. Using this abstraction mechanism we separate a generic ray traversal and intersection algorithm from its low-level aspects that are specific to the target hardware. We demonstrate that our code is not only significantly more flexible, simpler to write, and more concise but also that the compiled results perform as well as state-of-the-art implementations on any of the tested CPU and GPU platforms.
We report on the design and implementation of an extensible programming language and its intrinsic support for formal verification. Our language is targeted at low-level programming of infrastructure like operating sy...
详细信息
ISBN:
(纸本)9781450323260
We report on the design and implementation of an extensible programming language and its intrinsic support for formal verification. Our language is targeted at low-level programming of infrastructure like operating systems and runtime systems. It is based on a cross-platform core combining characteristics of assembly languages and compiler intermediate languages. From this foundation, we take literally the saying that C is a "macro assembly language": we introduce an expressive notion of certified low-level macros, sufficient to build up the usual features of C and beyond as macros with no special support in the core. Furthermore, our macros have integrated support for strongest postcondition calculation and verification condition generation, so that we can provide a high-productivity formal verification environment within Coq for programs composed from any combination of macros. Our macro interface is expressive enough to support features that low-level programs usually only access through external tools with no formal guarantees, such as declarative parsing or SQL-inspired querying. the abstraction level of these macros only imposes a compile-time cost, via the execution of functional Coq programs that compute programs in our intermediate language;but the run-time cost is not substantially greater than for more conventional C code. We describe our experiences constructing a full C-like language stack using macros, with some experiments on the verifiability and performance of individual programs running on that stack.
We present the design and implementation of a SQL query processor that outperforms existing database systems and is written in just about 500 lines of Scala code - a convincing case study that high-level functional pr...
详细信息
ISBN:
(纸本)9781450336697
We present the design and implementation of a SQL query processor that outperforms existing database systems and is written in just about 500 lines of Scala code - a convincing case study that high-level functionalprogramming can handily beat C for systems-level programming where the last drop of performance matters. the key enabler is a shift in perspective towards generative programming. the core of the query engine is an interpreter for relational algebra operations, written in Scala. Using the open-source LMS Framework (Lightweight Modular Staging), we turn this interpreter into a query compiler with very low effort. To do so, we capitalize on an old and widely known result from partial evaluation known as Futamura projections, which state that a program that can specialize an interpreter to any given input program is equivalent to a compiler. In this pearl, we discuss LMS programming patterns such as mixed-stage data structures (e.g. data records with static schema and dynamic field components) and techniques to generate low-level C code, including specialized data structures and data loading primitives.
this paper presents a personal, qualitative case study of a first course using How to Design Programs and its functional teaching languages. the paper reconceptualizes the book's six-step design process as an eigh...
详细信息
ISBN:
(纸本)9781450328739
this paper presents a personal, qualitative case study of a first course using How to Design Programs and its functional teaching languages. the paper reconceptualizes the book's six-step design process as an eight-step design process ending in a new "review and refactor" step. It recommends specific approaches to students' difficulties with function descriptions, function templates, data examples, and other parts of the design process. It connects the process to interactive "world programs." It recounts significant, informative missteps in course design and delivery. Finally, it identifies some unsolved teaching problems and some potential solutions.
functional Reactive programming (FRP) is an approach to the development of reactive systems which provides a pure functional interface, but which may be implemented as an abstraction of an imperative event-driven laye...
详细信息
ISBN:
(纸本)9781450323260
functional Reactive programming (FRP) is an approach to the development of reactive systems which provides a pure functional interface, but which may be implemented as an abstraction of an imperative event-driven layer. FRP systems typically provide a model of behaviours (total time-indexed values, implemented as pull systems) and event sources (partial time-indexed values, implemented as push systems). In this paper, we investigate a type system for event-driven FRP programs which provide liveness guarantees, that is every input event is guaranteed to generate an output event. We show that FRP can be implemented on top of a model of sets and relations, and that the isomorphism between event sources and behaviours corresponds to the isomorphism between relations and set-valued functions. We then implement sets and relations using a model of continuations using the usual double-negation CPS transform. the implementation of behaviours as pull systems based on futures, and of event sources as push systems based on the observer pattern, thus arises from first principles. We also discuss a Java implementation of the FRP model.
Writing loops with tail-recursive function calls is the equivalent of writing them with goto's. Given that loop packages for Lisp-family languages have been around for over 20 years, it is striking that none have ...
详细信息
ISBN:
(纸本)9781595930644
Writing loops with tail-recursive function calls is the equivalent of writing them with goto's. Given that loop packages for Lisp-family languages have been around for over 20 years, it is striking that none have had much success in the Scheme world. I suggest the reason is that Scheme forces us to be precise about the scoping of the various variables introduced by our loop forms, something previous attempts to design ambitious loop forms have not managed to do. I present the design of a loop package for Scheme with a well-defined and natural scoping rule, based on a notion of control dominance that generalizes the standard lexical-scope rule of the lambda-calculus. the new construct is powerful, clear, modular and extensible. the loop language is defined in terms of an underlying language for expressing control-flow graphs. this language itself has interesting properties as an intermediate representation.
We describe the implementation of first-class polymorphic delimited continuations in the programming language Scala. We use Scala's pluggable typing architecture to implement a simple type and effect system, which...
详细信息
ISBN:
(纸本)9781605583327
We describe the implementation of first-class polymorphic delimited continuations in the programming language Scala. We use Scala's pluggable typing architecture to implement a simple type and effect system, which discriminates expressions with control effects from those without and accurately tracks answer type modification incurred by control effects. To tackle the problem of implementing first-class continuations under the adverse conditions brought upon by the Java VM, we employ a selective CPS transform, which is driven entirely by effect-annotated types and leaves pure code in direct style. Benchmarks indicate that this high-level approach performs competitively.
Recent research has shown how boilerplate code, or repetitive code for traversing datatypes, can be eliminated using generic programming techniques already available within some implementations of Haskell. One particu...
详细信息
ISBN:
(纸本)9781595930644
Recent research has shown how boilerplate code, or repetitive code for traversing datatypes, can be eliminated using generic programming techniques already available within some implementations of Haskell. One particularly intractable kind of boilerplate is nameplate, or code having to do with names, name-binding, and fresh name generation. One reason for the difficulty is that operations on data structures involving names, as usually implemented, are not regular instances of standard map, fold, or zip operations. However, in nominal abstract syntax, an alternative treatment of names and binding based on swapping, operations such as a-equivalence, capture-avoiding substitution, and free variable set functions are much better-behaved. In this paper, we show how nominal abstract syntax techniques similar to those of FreshML can be provided as a Haskell library called FreshLib. In addition, we show how existing generic programming techniques can be used to reduce the amount of nameplate code that needs to be written for new datatypes involving names and binding to almost nothing-in short, how to scrap your nameplate.
this paper proposes a design-driven development approach that is dedicated to the domain of orchestration of masses of sensors. the developer declares what an application does using a domain-specific language (DSL). O...
详细信息
ISBN:
(纸本)9781450336871
this paper proposes a design-driven development approach that is dedicated to the domain of orchestration of masses of sensors. the developer declares what an application does using a domain-specific language (DSL). Our compiler processes domain-specific declarations to generate a customized programming framework that guides and supports the programming phase.
We present a new way of embedding functional languages into the Coq proof assistant by using meta-programming. this allows us to develop the meta-theory of the language using the deep embedding and provides a convenie...
详细信息
ISBN:
(纸本)9781450370974
We present a new way of embedding functional languages into the Coq proof assistant by using meta-programming. this allows us to develop the meta-theory of the language using the deep embedding and provides a convenient way for reasoning about concrete programs using the shallow embedding. We connect the deep and the shallow embeddings by a soundness theorem. As an instance of our approach, we develop an embedding of a core smart contract language into Coq and verify several important properties of a crowd-funding contract based on a previous formalisation of smart contract execution in blockchains.
暂无评论