Lazy functional languages have non-strict semantics and are purely declarative, i.e. they support the notion of referential transparency and are devoid of side effects. Traditional debugging techniques are, however, not suited for lazy functional languages since computations generally do not take place in the order one might expect. Since algorithmic debugging allows the user to concentrate on the declarative aspects of program semantics, and will semi-automatically find functions containing bugs, we propose to use this technique for debugging lazy functional programs. Our earlier work showed that this is a promising approach. However, the current version of our debugger has severe implementational problems, e.g. too large trace size and too many questions asked. This paper suggests a number of techniques for overcoming these problems, at least partially. The key techniques are immediate strictification and piecemeal tracing.
@InProceedings{Nilsson1993,
author = "Henrik Nilsson and Peter Fritzson",
title = "Lazy Algorithmic Debugging: Ideas for Practical
Implementation",
editor = "Peter Fritzson",
volume = "749",
series = "Lecture Notes in Computer Science",
pages = "117--134",
booktitle = "Automated and Algorithmic Debugging",
year = "1993",
address = "Link\"{o}ping, Sweden",
month = may
}
Lazy functional languages have non-strict semantics and are purely declarative, i.e. they support the notion of referential transparency and are devoid of side effects. Traditional debugging techniques are, however, not suited for lazy functional languages since computations generally do not take place in the order one might expect. Since algorithmic debugging allows the user to concentrate on the declarative aspects of program semantics, and will semi-automatically find functions containing bugs, we propose to use this technique for debugging lazy functional programs. Because of the non-strict semantics of lazy functional languages, arguments to functions are in general partially evaluated expressions. The user is, however, usually more concerned with the values that these expressions represent. We address this problem by providing the user with a strictified view of the execution trace whenever possible. In this paper we present an algorithmic debugger for a lazy functional language based on strictification and some experience in using it. A number of problems with the current implementation of the debugger, e.g. too large trace size and too many questions asked, are also discussed and some techniques for overcoming these problems, at least partially, are suggested, the key techniques being immediate strictification and piecemeal tracing.
@Article{Nilsson1994,
author = "Henrik Nilsson and Peter Fritzson",
title = "Algorithmic Debugging for Lazy Functional Languages",
journal = "Journal of Functional Programming",
year = 1994,
volume = 4,
number = 3,
pages = "337--370",
month = jul
}
Debugging programs written in lazy functional languages is difficult, and there are currently no realistic, general purpose debugging tools available. The basic problem is that computations in general do not take place in the order one might expect. Furthermore, lazy functional languages to a large extent free programmers from concerns regarding operational issues such as evaluation order, i.e. they are declarative. Debugging should therefore take place at the same, high level of abstraction. Thus, we propose to use algorithmic debugging for lazy functional languages, since this technique allows the user to focus on the declarative semantics of a program.
However, algorithmic debugging is based on tracing, and since the trace reflects the operational behaviour of the traced program, the trace should be transformed to abstract away these details if we wish to debug as declaratively as possible. We call this transformation strictification, because it makes the trace more like a trace from a strict language.
In this thesis, we present a strictifying algorithmic debugger for a small lazy functional language, and some experience from using it. We also discuss its main shortcomings, and outline a number of ideas for building a more realistic debugger. The single most pressing problem is the size of a complete trace. We propose to use a piecemeal tracing scheme to overcome this, by which only a part of the trace is stored at any one time, other parts being created on demand by re-executing the program.
@MastersThesis{Nilsson1994b,
author = "Henrik Nilsson",
title = "A Declarative Approach to Debugging for Lazy
Functional Languages",
school = "Department of Computer and Information Science,
{Link\"{o}ping} University",
year = 1994,
address = "S-581 83, {Link\"{o}ping}, Sweden",
month = sep,
type = "{L}icentiate {T}hesis {N}o. 450"
}
Debugging programs written in lazy functional languages is difficult, and there are currently no realistic, general purpose debugging tools available. The basic problem is that computations in general do not take place in the order one might expect. Furthermore, lazy functional languages are `declarative'. Hence it is advantageous if debugging takes place at the same, high level of abstraction. Thus, we propose to base debugging on what we call Evaluation Dependence Trees (EDT), which reflect the declarative semantics of the programs rather than operational concerns such as evaluation order. This in turn naturally suggests a two level debugger architecture where the lower level generates the EDT and the upper level allows the user to investigate it. The main advantage of this is flexibility: components realizing the two levels may be chosen independently to suit the debugging problem at hand.
@InProceedings{Sparud1995,
author = "Jan Sparud and Henrik Nilsson",
title = "The Architecture of a Debugger for Lazy Functional
Langauges",
editor = "Mireille Ducass\'{e}",
booktitle = "Proceedings of {AADEBUG '95}, 2nd International
Workshop on Automated and Algorithmic Debugging",
year = 1995,
organization = "{IRISA}, Campus Universitaire de Beaulieu, 35042 Rennes,
Cedex, France",
address = "Saint-Malo, France",
month = may
}
Lazy functional languages are declarative and allow the programmer to write programs where operational issues such as the evaluation order are left implicit. This should be reflected in the design of debuggers for such languages to avoid burdening the programmer with operational details, e.g. concerning the actual evaluation order. Conventional debugging techniques tend to focus too much on operational aspects to be suitable in this context. A record of the execution that only captures the declarative aspects of the execution, leaving out operational details, would be a viable basis for debugging lazy functional programs. Various declarative debugging tools could then be developed on top of such records. In this paper we propose a structure which we call the Evaluation Dependence Tree (EDT) for this purpose, and we describe two different construction methods. Performance problems are discussed along with possible solutions, and some performance figures from experiments in a realistic context are given.
@TechReport{Nilsson1996,
author = "Henrik Nilsson and Jan Sparud",
title = "The Evaluation Dependence Tree: an Execution Record
for Lazy Functional Debugging",
institution = "Department of Computer and Information Science,
{Link\"{o}ping} University",
year = 1996,
type = "Research Report",
number = "{LiTH-IDA-R-96-23}",
address = "S-581 83, {Link\"{o}ping}, Sweden",
note = "This is an extended version of \cite{Nilsson97}.",
month = aug
}
Lazy functional languages are declarative and allow the programmer to write programs where operational issues such as the evaluation order are left implicit. This should be reflected in the design of debuggers for such languages to avoid burdening the programmer with operational details, e.g. concerning the actual evaluation order. Conventional debugging techniques tend to focus too much on operational aspects to be suitable in this context. A record of the execution that only captures the declarative aspects of the execution, leaving out operational details, would be a viable basis for debugging lazy functional programs. Various declarative debugging tools could then be developed on top of such records. In this paper we propose a structure which we call the Evaluation Dependence Tree (EDT) for this purpose, and we describe two different construction methods. Performance problems are discussed along with possible solutions.
@Article{Nilsson1997,
author = "Henrik Nilsson and Jan Sparud",
title = "The Evaluation Dependence Tree as a Basis for Lazy
Functional Debugging",
journal = "Automated Software Engineering",
year = 1997,
volume = 4,
number = 2,
pages = "121--150",
month = apr
}
Lazy functional languages are declarative and allow the programmer to write programs where operational issues such as the evaluation order are left implicit. It is desirable to maintain a declarative view also during debugging so as to avoid burdening the programmer with operational details, for example concerning the actual evaluation order which tends to be difficult to follow. Conventional debugging techniques focus on the operational behaviour of a program and thus do not constitute a suitable foundation for a general-purpose debugger for lazy functional languages. Yet, the only readily available, general-purpose debugging tools for this class of languages are simple, operational tracers.
This thesis presents a technique for debugging lazy functional programs declaratively and an efficient implementation of a declarative debugger for a large subset of Haskell. As far as we know, this is the first implementation of such a debugger which is sufficiently efficient to be useful in practice. Our approach is to construct a declarative trace which hides the operational details, and then use this as the input to a declarative (in our case algorithmic) debugger.
The main contributions of this thesis are:
This work has been supported by the Swedish National Board for Industrial and Technical Development (NUTEK).
@PhdThesis{Nilsson1998,
author = "Henrik Nilsson",
title = "Declarative Debugging for Lazy Functional Languages",
school = "Department of Computer and Information Science,
{Link\"{o}pings universitet}",
year = 1998,
address = "S-581 83, {Link\"{o}ping}, Sweden",
month = may,
type = "{PhD} thesis"
}
The advantage of lazy functional languages is that programs may be written declaratively without specifying the exact evaluation order. The ensuing order of evaluation can however be quite involved which makes it difficult to debug such programs using traditional, operational techniques. A solution is to trace the computation in a way which focuses on the declarative aspects and hides irrelevant operational details. The main problem with this approach is the immense cost in time and space of tracing large computations. Dealing with these performance issues is thus the key to practical, general purpose debuggers for lazy functional languages. In this paper we show that computing partial traces on demand by re-executing the traced program is a viable way to overcome these difficulties. This allows any program to be traced using only a fixed amount of extra storage. Since it takes a lot of time to build a complete trace, most of which is wasted since only a fraction of a typical trace is investigated during debugging, partial tracing and repeated re-execution is also attractive from a time perspective. Performance figures are presented to substantiate our claims.
This work has been supported by the Swedish National Board for Industrial and Technical Development (NUTEK) and by the Wenner-Gren Foundations, Stockholm, Sweden.
@InProceedings{Nilsson1999,
author = "Henrik Nilsson",
title = "Tracing piece by piece: affordable debugging for
lazy functional languages",
pages = "36--47",
booktitle = "Proceedings of the 1999 {ACM SIGPLAN} international
conference on Functional programming",
year = 1999,
publisher = "{ACM} Press",
address = "Paris, France",
month = sep
}
In this extended abstract, we describe our work on an executable, dynamic semantic specification for a significant subset of Java, including exceptions and multi-threading. The dynamic semantics is expressed in natural semantics using the formalism Typol. A dedicated, graphical, programming environment has been generated from the dynamic semantics and a specification of the Java syntax using the Centaur environment, thus allowing the semantics to be tested extensively on real Java programs. This in turn allowed many errors to be fixed, and we now believe that the specification is reasonably correct. The next step is to formally prove the correctness of central aspects of the semantics. We focus on multi-threading aspects and their interaction with the control flow (e.g. exceptions). While this is work in progress, we sketch such a proof in this extended abstract.
@InProceedings{Attali2000a,
author = "Isabelle Attali and Denis Caromel and Henrik Nilsson
and Marjorie Russo",
title = "From Executable Formal Specification to {J}ava Property
Verification",
booktitle = "Second {ECOOP} Workshop on Formal Techniques for Java
Programs",
pages = "1--7",
year = 2000,
organization = "{INRIA} Sophia Antipolis",
address = "Sophia Antipolis, France",
month = jun,
}
This article describes a Java Card programming environment which to a large extent is generated from formal specifications of the syntax and semantics of Java Card, the JCRE (Java Card Runtime Environment), and the Java Card APIs. The resulting environment consists of a set of tightly integrated and somewhat smart tools, such as a Java specific structure editor and a simulator which allows an application to be tested before being downloaded to a card. Furthermore, the simulator analyses the applet in question in order to find out the structure of the accepted commands. This information is then used to automatically adapt the GUI of the simulator.
This work was partially financed by Bull. Henrik Nilsson was supported by a post doctoral grant from the Wenner-Gren Foundations, Stockholm, Sweden.
@InProceedings{Attali2000b,
author = "Isabelle Attali and Denis Caromel and Carine Courbis and
Ludovic Henrio and Henrik Nilsson",
title = "Smart Tools for {J}ava Cards",
editor = "Josep Domingo-Ferrer and David Chan and Anthony Watson",
booktitle = "Smart Card Research and Advanced Applications",
year = 2000,
publisher = "Kluwer Academic Publishers",
month = sep,
note = "Proceedings of the {IFIP} Fourth Working Conference
on Smart Card Research and Advanced Applications
({CARDIS} 2000), {HP} Labs, Bristol, {UK}"
}
This article describes a Java Card programming environment which to a large extent is generated from formal specifications of the syntax and semantics of Java Card, the JCRE (Java Card Runtime Environment), and the Java Card APIs. The resulting environment consists of a set of tightly integrated and somewhat smart tools, such as a Java specific structure editor and a simulator which allows an application to be tested before being downloaded to a card. Furthermore, the simulator analyses the applet in question in order to find out the structure of the accepted commands. This information is then used to automatically adapt the GUI of the simulator.
This work was partially financed by Bull. Henrik Nilsson was supported by a post doctoral grant from the Wenner-Gren Foundations, Stockholm, Sweden.
@Article{Attali2001,
author = "Isabelle Attali and Denis Caromel and Carine Courbis and
Ludovic Henrio and Henrik Nilsson",
title = "An Integrated Development Environment for {Java Card}",
journal = "Computer Networks",
pages = "391--405",
year = 2001,
volume = 36,
number = 4,
month = jul
}
This article describes the implementation of a debugger for lazy functional languages like Haskell. The key idea is to construct a declarative trace which hides the operational details of lazy evaluation. However, to avoid excessive memory consumption, the trace is constructed one piece at a time, as needed during a debugging session, by automatic re-execution of the program being debugged. This article gives a fairly detailed account of both the underlying ideas and of our implementation. It also presents performance figures which demonstrate the feasibility of the approach.
This work has been supported by the Swedish Board for Industrial and Technical Development (NUTEK) and by the Wenner-Gren Foundations, Stockholm, Sweden.
@Article{Nilsson2001,
author = "Henrik Nilsson",
title = "How to Look Busy while Being as Lazy as Ever: The
Implementation of a Lazy Functional Debugger",
journal = jfp,
year = 2001,
volume = 11,
number = 6,
pages = "629--671",
month = nov
}
Functional Reactive Programming (FRP) extends a host programming language with a notion of time flow. Arrowized FRP (AFRP) is a version of FRP embedded in Haskell based on the arrow combinators. AFRP is a powerful synchronous dataflow programming language with hybrid modeling capabilities, combining advanced synchronous dataflow features with the higher-order lazy functional abstractions of Haskell. In this paper, we describe the AFRP programming style and our Haskell-based implementation. Of particular interest are the AFRP combinators that support dynamic collections and continuation-based switching. We show how these combinators can be used to express systems with an evolving structure that are difficult to model in more traditional dataflow languages.
@InProceedings{Nilsson2002a,
author = "Henrik Nilsson and Antony Courtney and John Peterson",
title = "Functional Reactive Programming, Continued",
booktitle = "Proceedings of the 2002 {ACM SIGPLAN} {H}askell
Workshop ({H}askell'02)",
pages = "51--64",
year = 2002,
address = "Pittsburgh, Pennsylvania, USA",
publisher = "{ACM} Press",
month = oct
}
Software for (semi-) autonomous robots tends to be a complex combination of components from many different application domains such as control theory, vision, and artificial intelligence. Components are often developed using their own domain-specific tools and abstractions. System integration can thus be a significant challenge, in particular when the application calls for a dynamic, adaptable system structure in which rigid boundaries between the subsystems are a performance impediment. We believe that, by identifying suitably abstract notions common to the different domains in question, it is possible to create a broader framework for software integration and to recast existing domain-specific frameworks in these terms. This approach simplifies integration and leads to improved reliability. In this paper, we show how Functional Reactive Programming (FRP) can serve as such a unifying framework for programming vision-guided, semi-autonomous robots and illustrate the benefits this approach entails. The key abstractions in FRP, reactive components describing continuous or discrete behavior in a declarative style, are first class entities, allowing the resulting systems to exhibit a dynamic, adaptable structure which we regard as especially important in the area of autonomous robots.
@InProceedings{Pembeci2002,
author = "Izzet Pembeci and Henrik Nilsson and Greogory Hager",
title = "System Presentation -- Functional Reactive Robotics: An
Exercise in Principled Integration of Domain-Specific
Languages",
pages = "168--179",
booktitle = "Principles and Practice of Declarative Programming
({PPDP'02})",
year = 2002,
address = "Pittsburgh, Pennsylvania, USA",
month = oct
}
The modeling and simulation of physical systems is of key importance in many areas of science and engineering, and thus can benefit from high-quality software tools. In previous research we have demonstrated how functional programming can form the basis of an expressive language for causal hybrid modeling and simulation. There is a growing realization, however, that a move toward non-causal modeling is necessary for coping with the ever increasing size and complexity of modeling problems. Our goal is to combine the strengths of functional programming and non-causal modeling to create a powerful, strongly typed fully declarative modeling language that provides modeling and simulation capabilities beyond the current state of the art. Although our work is still in its very early stages, we believe that this paper clearly articulates the need for improved modeling languages and shows how functional programming techniques can play a pivotal role in meeting this need.
@InProceedings{Nilsson2003a,
author = "Henrik Nilsson and John Peterson and Paul Hudak",
title = "Functional Hybrid Modeling",
booktitle = "Proceedings of {PADL'03}: 5th International Workshop on
Practical Aspects of Declarative Languages",
pages = "376--390",
year = 2003,
volume = 2562,
series = lncs,
address = "New Orleans, Lousiana, USA",
month = jan,
publisher = sv
}
Functional reactive programming, or FRP, is a paradigm for programming hybrid systems -- i.e., systems containing a combination of both continuous and discrete components -- in a high-level, declarative way. The key ideas in FRP are its notions of continuous, time-varying values, and time-ordered sequences of discrete events. Yampa is an instantiation of FRP as a domain-specific language embedded in Haskell. This paper describes Yampa in detail, and shows how it can be used to program a particular kind of hybrid system: a mobile robot. Because performance is critical in robotic programming, Yampa uses arrows (a generalization of monads) to create a disciplined style of programming with time-varying values that helps ensure that common kinds of time- and space-leaks do not occur. No previous experience with robots is expected of the reader, although a basic understanding of physics and calculus is assumed. No knowledge of arrows is required either, although we assume a good working knowledge of Haskell.
@InProceedings{Hudak2003,
author = "Paul Hudak and Antony Courtney and Henrik Nilsson
and John Peterson",
title = "Arrows, Robots, and Functional Reactive Programming",
booktitle = "Summer School on Advanced Functional Programming 2002,
Oxford University",
year = 2003,
volume = 2638,
series = "Lecture Notes in Computer Science",
pages = "159--187"
publisher = "Springer-Verlag"
}
Functional Reactive Programming (FRP) is a framework for reactive programming in a functional setting. FRP has been applied to a number of domains, such as graphical animation, graphical user interfaces, robotics, and computer vision. Recently, we have been interested in applying FRP-like principles to hybrid modeling and simulation of physical systems. As a step in that direction, we have extended an existing FRP implementation, Yampa, in two new ways that make it possible to express certain models in a very natural way, and reduces the amount of work needed to put modeling equations into a suitable form for simulation. First, we have added Dirac impulses that allow certain types of discontinuities to be handled in an easy yet rigorous manner. Second, we have adapted automatic differentiation to the setting of Yampa, and generalized it to work correctly with Dirac impulses. This allows derivatives of piecewise continuous signals to be well-defined at all points. This paper reviews the basic ideas behind automatic differentiation, in particular Jerzy Karczmarczuk's elegant version for a lazy functional language with overloading, and then considers the integration with Yampa and the addition of Dirac impulses.
@InProceedings{Nilsson2003b,
author = "Henrik Nilsson",
title = "Functional Automatic Differentiation with {D}irac Impulses",
booktitle = "Proceedings of the Eighth {ACM} {SIGPLAN} International
Conference on Functional Programming",
pages = "153--164",
year = 2003,
address = "Uppsala, Sweden",
month = aug,
publisher = "{ACM} Press"
}
Simulated worlds are a common (and highly lucrative) application domain that stretches from detailed simulation of physical systems to elaborate video game fantasies. We believe that Functional Reactive Programming (FRP) provides just the right level of functionality to develop simulated worlds in a concise, clear and modular way. We demonstrate the use of FRP in this domain by presenting an implementation of the classic "Space Invaders" game in Yampa, our most recent Haskell-embedded incarnation of FRP.
@InProceedings{Courtney2003b,
author = "Antony Courtney and Henrik Nilsson and John Peterson",
title = "The {Y}ampa Arcade",
booktitle = "Proceedings of the 2003 {ACM SIGPLAN} {H}askell
Workshop ({H}askell'03)",
pages = "7--18",
year = 2003,
address = "Uppsala, Sweden",
publisher = "{ACM} Press",
month = aug
}