Is It Time for Real-Time Functional Programming?

Kevin Hammond

Abstract 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 INTRODUCTION

Functional 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 Systems

Real-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 Languages

McDermid 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 SYSTEMS

Programming 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 Programming

Historically, 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...