Skip to main content
main-content

Über dieses Buch

This book constitutes the thoroughly refereed post-conference proceedings of the 11th International Symposium on Trends in Functional Programming, TFP 2010, held in Norman, OK, USA, in May 2010. The 13 revised full papers presented were carefully reviewed and selected from 26 submissions during two rounds of reviewing and improvement. The papers cover new ideas for refactoring, managing source-code complexity, functional language implementation, graphical languages, applications of functional programming in pure mathematics, type theory, multitasking and parallel processing, distributed systems, scientific modeling, domain specific languages, hardware design, education, and testing.

Inhaltsverzeichnis

Frontmatter

Evaluating Call-by-Need on the Control Stack

Ariola and Felleisen’s call-by-need λ-calculus replaces a variable occurrence with its value at the last possible moment. To support this gradual notion of substitution, function applications—once established—are never discharged. In this paper we show how to translate this notion of reduction into an abstract machine that resolves variable references via the control stack. In particular, the machine uses the static address of a variable occurrence to extract its current value from the dynamic control stack.
Stephen Chang, David Van Horn, Matthias Felleisen

Typing Coroutines

A coroutine is a programming construct between function and thread. It behaves like a function that can suspend itself arbitrarily often to yield intermediate results and to get new inputs before returning a result. This facility makes coroutines suitable for implementing generator abstractions.
Languages that support coroutines are often untyped or they use trivial types for coroutines. This work supplies the first type system with dedicated support for coroutines. The type system is based on the simply-typed lambda calculus extended with effects that describe control transfers between coroutines.
Konrad Anton, Peter Thiemann

An Expression Processor: A Case Study in Refactoring Haskell Programs

Refactoring is the process of changing the structure of a program while preserving its behaviour in order to increase code quality, programming productivity and code reuse. With the advent of refactoring tools, refactoring can be performed semi-automatically, allowing refactorings to be performed (and undone) easily.
In this paper, we briefly describe a number of new refactorings for Haskell 98 programs implemented in the Haskell Refactorer, HaRe. In particular, a number of new structural and data-type refactorings are presented. We also implement a simple expression processor, clearly demonstrating how the refactorings and the HaRe tool can aid programmers in developing Haskell software. We conclude the paper with a discussion of the benefits of refactoring Haskell programs, together with their implementation and design limitations.
Christopher Brown, Huiqing Li, Simon Thompson

Static Balance Checking for First-Class Modular Systems of Equations

Characterising a problem in terms of a system of equations is common to many branches of science and engineering. Due to their size, such systems are often described in a modular fashion by composition of individual equation system fragments. Checking the balance between the number of variables (unknowns) and equations is a common approach to early detection of mistakes that might render such a system unsolvable. However, current approaches to modular balance checking have a number of limitations. This paper investigates a more flexible approach that in particular makes it possible to treat equation system fragments as true first-class entities. The central idea is to record balance information in the type of an equation fragment. This information can then be used to determine if individual fragments are well formed, and if composing fragments preserves this property. The type system presented in this paper is developed in the context of Functional Hybrid Modelling (FHM). However, the key ideas are in no way specific to FHM, but should be applicable to any language featuring a notion of modular systems of equations.
John Capper, Henrik Nilsson

Graphical and Incremental Type Inference: A Graph Transformation Approach

We present a graph grammar based type inference system for a totally graphic development language. NiMo (Nets in Motion) can be seen as a graphic equivalent to Haskell that acts as an on-line tracer and debugger. Programs are process networks that evolve giving total visibility of the execution state, and can be interactively completed, changed or stored at any step. In such a context, type inference must be incremental. During the net construction or modification only type safe connections are allowed. The user visualizes the type information evolution and, in case of conflict, can easily identify the causes. Though based on the same ideas, the type inference system has significant differences with its analogues in functional languages. Process types are a non-trivial generalization of functional types to handle multiple outputs, partial application in any order, and curried-uncurried coercion. Here we present the elements to model graphical inference, the notion of structural and non-structural equivalence of type graphs, and a graph unification and composition calculus for typing nets in an incremental way.
Silvia Clerici, Cristina Zoltan, Guillermo Prestigiacomo

Hygienic Macros for ACL2

ACL2 is a theorem prover for a purely functional subset of Common Lisp. It inherits Common Lisp’s unhygienic macros, which are used pervasively to eliminate repeated syntactic patterns. The lack of hygiene means that macros do not automatically protect their producers or consumers from accidental variable capture. This paper demonstrates how this lack of hygiene interferes with theorem proving. It then explains how to design and implement a hygienic macro system for ACL2. An evaluation of the ACL2 code base shows the potential impact of this hygienic macro system on existing libraries and practices.
Carl Eastlund, Matthias Felleisen

What’s the Matter with Kansas Lava?

Kansas Lava is a functional hardware description language implemented in Haskell. In the course of attempting to generate ever larger circuits, we have found the need to effectively test and debug the internals of Kansas Lava. This includes confirming both the simulated behavior of the circuit and its hardware realization via generated VHDL. In this paper we share our approach to this problem, and discuss the results of these efforts.
Andrew Farmer, Garrin Kimmell, Andy Gill

Types and Type Families for Hardware Simulation and Synthesis

The Internals and Externals of Kansas Lava
In this paper, we overview the design and implementation of our latest version of Kansas Lava. Driven by needs and experiences of implementing telemetry circuits, we have made a number of recent improvements to both the external API and the internal representations used. We have retained our dual shallow/deep representation of signals in general, but now have a number of externally visible abstractions for combinatorial, sequential, and enabled signals. We introduce these abstractions, as well as our new abstractions for memory and memory updates. Internally, we found the need to represent unknown values inside our circuits, so we made aggressive use of type families to lift our values in a principled and regular way. We discuss this design decision, how it unfortunately complicates the internals of Kansas Lava, and how we mitigate this complexity.
Andy Gill, Tristan Bull, Andrew Farmer, Garrin Kimmell, Ed Komp

Testing with Functional Reference Implementations

This paper discusses our approach to test programs that determine which candidates are elected in the Scottish Single Transferable Vote (STV) elections. Due to the lack of properties suited for model-based testing, we have implemented a reference implementation in a pure functional programming language. Our tests revealed issues in the law regulating these elections as well as the programs implementing the rules that are offered for certification. Hence, certification by testing with a reference implementation is able to reveal problems in the software to be certified. Functional programming languages appeared to be an excellent tool to implement reference implementations. The reference implementation was developed quickly and none of the differences found was due to an error in the reference implementation.
Pieter Koopman, Rinus Plasmeijer

Every Animation Should Have a Beginning, a Middle, and an End

A Case Study of Using a Functor-Based Animation Language
Animations are sequences of still images chained together to tell a story. Every story should have a beginning, a middle, and an end. We argue that this advice leads to a simple and useful idiom for creating an animation Domain Specific Language (DSL). We introduce our animation DSL, and show how it captures the concept of beginning, middle, and end inside a Haskell applicative functor we call Active. We have an implementation of our DSL inside the image generation accelerator, ChalkBoard, and we use our DSL on an extended example, animating a visual demonstration of the Pythagorean Theorem.
Kevin Matlage, Andy Gill

Functional Video Games in the CS1 Classroom

Over the past decade enrollments in Computer Science undergraduate programs have drastically dropped while simultaneously seeing demand for computer scientists in the job market increase. The reason for this disconnect is, in part, due to the perception new potential students have of programming as a dull activity requiring no creativity, very little social interaction, and endless hours of coding in front of a monitor. The question then is how can we capture the imagination of new students and perk their interest in a way that gets them excited while at the same time giving them a solid foundation in computer programming and Computer Science. This article puts forth the thesis that developing video games using functional programming should be a new trend in the CS1 classroom. The article describes the approach implemented at Seton Hall University using video game programming and Felleisen et al.’s textbook How to Design Programs. The first-year programming curriculum is briefly described and how to get students interested in programming through the development of a Space-Invaders-like game is illustrated. The presented development gives the reader a clear sense of how to use functional video games in the first semester classroom.
Marco T. Morazán

ComputErl – Erlang-Based Framework for Many Task Computing

This paper shows how Erlang programming language can be used for creating a framework for distributing and coordinating the execution of many task computing problems. The goals of the proposed solution are (1) to disperse the computation into many tasks, (2) to support multiple well-known computation models (such as master-worker, map-reduce, pipeline), (3) to exploit the advantages of Erlang for developing an efficient and scalable framework and (4) to build a system that can scale from small to large number of tasks with minimum effort. We present the results of work on designing, implementing and testing ComputErl framework. The preliminary experiments with benchmarks as well as real scientific applications show promising scalability on a computing cluster.
Michał Ptaszek, Maciej Malawski

Monad Factory: Type-Indexed Monads

Monads provide a greatly useful capability to pure languages in simulating side-effects, but implementations such as the Monad Transformer Library [1] in Haskell prohibit reuse of those side-effects such as threading through two different states without some explicit work-around. Monad Factory provides a straightforward solution for opening the non-proper morphisms by indexing monads at both the type-level and term-level, allowing ‘copies’ of the monads to be created and simultaneously used within even the same monadic transformer stack. This expands monads’ applicability and mitigates the amount of boilerplate code we need for monads to work together, and yet we use them nearly identically to non-indexed monads.
Mark Snyder, Perry Alexander

Backmatter

Weitere Informationen

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!

Bildnachweise