Trends in Functional Programming Volume 4 by Stephen Gilmore (PDF)

Description

These proceedings from the September 2003 Fourth International Symposium on Trends in Functional Programming, held in Edinburgh, UK, address the research problems at the forefront of the practical application of functional programming languages. Papers examine topics including resource-aware functional programing for the JVM, testing reactive systems with GAST, implementation of mobile Haskell, and testing scheme programming assignments automatically. Each paper ends with conclusions and overviews of related work. There is no subject index. The book is distributed in the US by ISBS. Annotation ©2004 Book News, Inc., Portland, OR (booknews.com)

User’s Reviews

Editorial Reviews: Excerpt. © Reprinted by permission. All rights reserved. Trends in Functional Programming Volume 4By Stephen GilmoreIntellect LtdCopyright © 2005 Intellect LtdAll rights reserved.ISBN: 978-1-84150-122-2Contents1 Is It Time for Real-Time Functional Programming?, 2 FSM-Hume is Finite State, 3 amelot and Grail: Resource-Aware Functional Programming for the JVM, 4 O’Camelot: Adding Objects to a Resource-Aware Functional Language, 5 Static Single Information from a Functional Perspective, 6 Implementing Mobile Haskell, 7 Testing Scheme Programming Assignments Automatically, 8 Testing Reactive Systems with GAST, CHAPTER 1Is It Time for Real-Time Functional Programming?Kevin HammondAbstract This paper explores the suitability of functional languages for programming real-time systems. We study the requirements of real-time systems in general, outline typical language approaches for this domain, consider issues relating to memory and time usage and explore how all existing functional languages, including our own language Hume, match these requirements. We conclude by posing some research challenges that functional language designs and implementations must meet if they are to be regarded as suitable vehicles for realtime systems implementation.1.1 INTRODUCTIONFunctional programs use large amounts of memory. Functional programs are slow. It is impossible to predict memory and other resource usage for functional languages. Clearly, functional languages are therefore unsuitable for use in restricted memory settings with strong time requirements. Or are they? This paper explores the suitability of functional language designs for use in settings with strong limitations on resource usage such as real-time systems. It compares current functional approaches, including our own Hume notation (Sec. 1.6), with those used by other language paradigms and outlines some challenges for functional language designs and implementations that must be met if functional programming is to be used for serious real-time programming.1.2 WHAT IS REAL-TIME PROGRAMMING?The key characteristic of a real-time system is that its correctness depends not only on its functional behaviour, but also on the (real-) time or times at which it produces those results. Such systems can be classified as having either soft realtime or hard real-time properties. Soft real-time has been defined as a situation where “nothing really serious happens if a time constraint is not met”. Examples of soft real-time systems might include computer games, telephone switches, digital set-top boxes or digital sound cards. In contrast, hard real-time involves guaranteed system response and is often associated with safety-critical systems or ones with high penalty cost for failure. Examples include avionics control software, autonomous vehicles, or software used by stock market traders. In many situations, such as embedded systems, such real-time constraints are combined with other resource restrictions including memory limitations and even power consumption requirements. Despite the focus on real-time, such systems need not necessarily be ultra high-performance. The problem is to design systems that are sufficiently reliable and have minimal cost and acceptable performance. Doing so in a cost-effective manner is a major bonus.1.2.1 The Importance of Real-Time SystemsReal-time systems have been growing in importance in recent years. Numerically, a very high percentage of all computer systems produced today have real-time characteristics. Many of these are embedded systems. Real-time embedded systems are a fundamental part of modern everyday society in the shape of vehicle control systems, mobile telephones, GPS and consumer appliances such as DVD players or digital set-top boxes. These commonplace devices are additional to those used in telecommunications, to promote automation in factories, to ensure security and safety in the home and workplace, to increase the safety and efficiency of transport and service industries and for military uses, etc. In fact, today more than 98 per cent of all new processors are used in such systems.1.2.2 Essential Properties of Real-Time LanguagesMcDermid identifies a number of essential or desirable properties for a language that is aimed at hard real-time systems.• determinacy – the language should allow the construction of determinate systems, by which we mean that under identical environmental constraints, all executions of the system should be observationally equivalent;• bounded time/space – the language must allow the construction of systems whose resource costs are statically bounded – so ensuring that hard real-time and real-space constraints can be met;• asynchronicity – the language must allow the construction of systems that are capable of responding to inputs as they are received without imposing total ordering on environmental or internal interactions;• concurrency – the language must allow the construction of systems as communicating units of independent computation;• correctness – the language must allow a high degree of confidence that constructed systems meet their formal requirements.These requirements may be relaxed to acceptable engineering tolerances for soft real-time systems. Moreover, the language design must incorporate at least:• periodic scheduling to ensure that real-time constraints are met;• interrupts and polling to deal with connections to external devices.1.3 LANGUAGES FOR PROGRAMMING REAL-TIME SYSTEMSProgramming languages for real-time systems may be either specially designed to meet the requirements of the domain (domain-specific languages) or adapted from commonly used designs. Since non-functional approaches have been described in detail elsewhere (e.g.), this paper provides only a brief overview of such languages here. Berry further considers the issue of whether to use general purpose or domain-specific languages for real-time programming.1.3.1 Using General Purpose Languages for Real-Time ProgrammingHistorically, much embedded systems software/firmware was written for specific hardware using native assembler. Rapid increases in software and the need for productivity improvements mean that there has been a transition to the use of C/C++ and in some cases Java. Two extreme approaches to enforcing real-time properties in a language that is derived from a general-purpose design are exemplified by SPARK Ada and the real-time specification for Java (RTSJ). SPARK Ada epitomises the idea of language design by elimination of unwanted behaviour from a general-purpose language, including concurrency. The remaining behaviour is guaranteed by strong formal models. In contrast, RTSJ provides specialised runtime and library support for real-time systems work, but makes no absolute performance guarantees. Thus, SPARK Ada provides a minimal, highly controlled environment for real-time programming emphasising correctness by construction, whilst Real-Time Java provides a much more expressible but less controlled environment, without formal guarantees.A major issue for programming real-time embedded systems is memory management: it is essential both to bound memory usage and to control memory access time. When using general purpose languages, it is thus common to avoid recursive programming constructs (which may grow the stack in an “unrestricted” fashion) and also to avoid automatic dynamic memory allocation/collection. In Sec. 1.4 we describe some modern approaches that may allow the safe use of such constructs in a real-time embedded system.1.3.2 Domain-Specific Languages for Real-Time ProgrammingProcess Algebra Derived NotationsProcess algebras such as CSP, CCS, LOTOS and the p-calculus are formal notations designed to permit reasoning about complex systems of concurrent processes. They provide an elegant set of operators for developing concurrent systems, so allowing succinct expression of concurrent programs. Typical process algebras use synchronous communication, support non-determinism, and allow choice, restriction of names and relabelling at the process level. Concurrency is usually modelled through interleaving processes. Process algebras provide a rich, tractable semantics, using observation equivalence to hide internal behaviours. This extensionalist approach contrasts with the intensionalist approach taken by Petri nets, where internal behaviour is important and must consequently be exposed. Explicit notions of time have been incorporated into a number of process algebras, e.g. TCCS or Timed CSP. While process algebras are generally intended as formal notations to allow reasoning about concurrent specifications, there have also been some attempts to derive concrete programming notations from such bases. For example, LOTOS (Language of Temporally Ordered Specifications) is often used as a programming notation and several timed extensions have been designed with the intention of dealing with real-time systems.Finite-State LanguagesFinite-state approaches are attractive when dealing with certain kinds of real-time system, since they allow a system to be defined by composing small, easily costed components. Such approaches often, however, prove problematic when one is constructing complex programs: typically the finite-state machines derived for such systems will have a large number of states, which can be difficult for the programmer to manage; moreover, relatively small extensions can cause exponential growth in the number of states. A number of extended finite-state languages have been proposed incorporating composition, communication and data structures to give Turing-complete notations. Many also incorporate quantitative notions of time. Three common examples are Estelle, an imperative language developed for OSI communications protocols; SDL, a language similar to Estelle, which has a graphical dialect used as a design tool; and TTM, a graphical notation, similar to Petri nets, used to describe real-time discrete event processes.In synchronous dataflow languages, every action (whether computation or communication) has a zero-time duration. In practice this means that actions must complete before the arrival of the next event to be processed. Communication with the outside world occurs by reaction to external stimuli and by instantaneous emission of responses. Because of their origin in the combination of control theory and computer science, synchronous notations have long been popular in the area of automatic control. Since they are equivalent to the zero-delay model of circuits, they have also more recently found employment in hardware design.Several languages have applied the synchronous model to real-time systems control. For example, Signal and Lustre are similar declarative notations, built around the notion of timed sequences of values. Esterel is an imperative notation that can be translated into finite-state machines or hardware circuits, and Statecharts is a quasi-synchronous notation with a visual notation, which is primarily used for design, and which has been subsumed into UML. One obvious deficiency of pure synchronous notations is the lack of expressive power, notably the absence of recursion and of higher-order combina-tors. Synchronous Kahn networks incorporate higher-order functions and recursion, but lose strong guarantees of resource boundedness. It is thus generally accepted that pure synchronous languages are not powerful enough for complex systems programming and must interact with other languages and communication styles, in particular with asynchronous ones. There have consequently been some attempts to combine the two styles of programming, for example CRP combines Esterel and CSP, and the Polis hardware/software codesign system also employs Esterel in a mixed synchronous and asychronous setting.1.3.3 Functional Language ApproachesThe main advantages of functional language approaches are compositionality, ease of reasoning and program structuring. Typical modern language designs, such as Standard ML or Haskell, incorporate automatic memory management which eliminates errors arising from poor manual memory management; strong typing which eliminates a large number of programming errors; higher-order functions which abstract over common patterns of computation; polymorphism which abstracts internal details of data structures; and recursion allows a number of algorithms, especially involving data structures, to be expressed in a more natural and thus less error-prone fashion.These language features improve productivity through raising the level of expressivity and program abstraction. However, they divorce the programmer from the ability to directly control program execution, and thus from a simple intuitive model of the program’s time and space behaviour. Moreover, functional language implementations must bridge a larger gap between source language and concrete machine than is present with lower-level languages. This has historically led to a significant performance difference between functional languages and their imperative counterparts, and consequent doubt over the suitability of functional notations for real-time settings, where it is necessary to program within strong time and space bounds.Compared with McDermid’s criteria, the primary functional language designs thus meet the requirements for determinacy and correctness, but fail to deal effectively with asynchronicity, concurrency and bounded time and space. Concurrent extensions such as Concurrent ML or Concurrent Haskell add mechanisms for asynchronicity and concurrency, but likewise provide no bounded time or space guarantees. None of these notations provide mechanisms for periodic scheduling or interrupt handling, and all use a relatively low-level notion of thread and communication, with explicit message handling.Soft Real-Time Functional LanguagesThe most widely used soft real-time functional language is the impure, strict language Erlang, a concurrent language with a similar design to Concurrent ML. Erlang has been used by Ericsson to construct a number of successful telecommunications applications in the telephony sector, including a real-time database, Mnesia. Erlang is concurrent, with a lightweight notion of a process. Such processes are constructed using explicit spawn operations, with communication occurring through explicit send and receive operations to nominated processes. Finally, rather than exploiting static analysis order to ensure that hard dynamic resource bounds are achieved, the weakly typed Erlang relies exclusively on dynamic timeouts to meet soft real-time targets.In contrast, Embedded Gofer is a strongly-typed purely functional programming language with a two-level structure, separating process and functional layers. It uses a monadic notation with explicit register access, processes and communication, similar in kind to other explicitly concurrent programming notations. Unlike Erlang, Embedded Gofer is non-strict, raising questions about accurate static costing of programs (as opposed to dynamic measurement of typical runtime behaviour, which is not adequate to guarantee real-time behaviour). A similar approach has been taken by Fijma and Udink, who introduced special language constructs into Twentel to control a robot arm.RT-FRP builds on functional reactive programming embedded as a domain-specific language in Haskell to construct time and space bounded programs. RT-FRP is separated into a reactive part (comparable to a synchronous system) and a base part that must be guaranteed terminating and resource-bounded. It exploits tail-recursion across reactive components to encapsulate time and space resource usage within a single reactive component, and also supports integration across a series of reactive components. The work provides a formal operational semantics for resource consumption, which can be used to construct an automatic analysis to determine space and time bounds. Since RT-FRP is based on Haskell, of course, the underlying language implementation technology may affect timings and space usage through non-strict evaluation and non-real-time garbage collection. Consequently, in the current system, these bounds cannot be guaranteed. A different language substrate might, however, provide a better basis for these requirements. Finally, RT-FRP does not yet consider issues of periodic scheduling, and events are handled without regard to real-time concerns, such as dynamic memory allocation, making them unsuitable for low-level interrupt handling.Finally, a number of reactive applications have been written in more conventional functional languages without recourse to even an incremental garbage collector or attempting to formally bound time or space behaviour. Examples include the impure Concurrent ML and the purely functional Concurrent Haskell, Concurrent Clean and Eden. An interesting example of such work is the games engine and games written in Concurrent Clean. (Continues…)Excerpted from Trends in Functional Programming Volume 4 by Stephen Gilmore. Copyright © 2005 Intellect Ltd. Excerpted by permission of Intellect Ltd. All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

Reviews from Amazon users which were colected at the time this book was published on the website:

⭐

⭐

Keywords

Free Download Trends in Functional Programming Volume 4 in PDF format
Trends in Functional Programming Volume 4 PDF Free Download
Download Trends in Functional Programming Volume 4 2013 PDF Free
Trends in Functional Programming Volume 4 2013 PDF Free Download
Download Trends in Functional Programming Volume 4 PDF
Free Download Ebook Trends in Functional Programming Volume 4