FSM-Hume: programming resource-limited systems using bounded automata

ABSTRACT

Hume is a novel domain-specific programming language targeting resource-bounded computations, such as real-time embedded systems or mobile code. It is based on generalised concurrent automata, controlled by transitions characterised by pattern matching on inputs and (recursive) function generation on outputs. This paper discusses trade-offs between expressibility and decidability in the design of FSM-Hume, a subset of Hume (or Hume layer) based on generalised linear bounded automata with statically determinable time and space use. We illustrate our approach with reference to space costing of a simple real-time simulation of a line-following automous vehicle.

REFERENCES

• 1: Tobias Amnell , Elena Fersman , Leonid Mokrushin , Paul Pettersson , Wang Yi, TIMES - A Tool for Modelling and Implementation of Embedded Systems, Proceedings of the 8th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, p.460-464, April 08-12, 2002
• 2: Gérard Berry, The foundations of Esterel, Proof, language, and interaction: essays in honour of Robin Milner, MIT Press, Cambridge, MA, 2000
• 3: Walter S. Brainerd , Lawrence H. Landweber, Theory of Computation, John Wiley & Sons, Inc., New York, NY, 1974
• 4: K. Hammond and G. Michaelson. Predictable Space Behaviour in FSM-Hume. In Proc. 2002 Intl. Workshop on Implementation of Functional Languages (IFL '02), Madrid, Spain. Springer-Verlag LNCS 2670, Sep. 2002.
• 5: Kevin Hammond , Greg Michaelson, Hume: a domain-specific language for real-time embedded systems, Proceedings of the second international conference on Generative programming and component engineering, p.37-56, September 22-25, 2003, Erfurt, Germany
• 6: K. Hammond and P. Vasconcelos. Inferring Costs for Recursive, Polymorphic and Higher-Order Programs. In submitted to 2004 European Symp. on Programming (ESOP 2004), 2004.
• 7: David Harel, Statecharts: A visual formalism for complex systems, Science of Computer Programming, v.8 n.3, p.231-274, June 1, 1987 [doi>10.1016/0167-6423(87)90035-9]
• 8: Martin Hofmann, A Type System for Bounded Space and Functional In-Place Update--Extended Abstract, Proceedings of the 9th European Symposium on Programming Languages and Systems, p.165-179, April 02, 2000
• 9: G. J. Holzmann. The Spin Model Checker: Primer and Reference Manual. Addison-Wesley, 2004.
• 10: John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
• 11: T. Hune, K. G. Larsen, and P. Pettersson. Guided Synthesis of Control Programs Using UPPAAL. In Proc. IEEE ICDCS Intl. Workshop on Distributed Systems Verification and Validation, pages E15--E22, 2000.
• 12: A. Jeffrey and I. Wakeman. A survey of semantic techniques for active networks, 1997. http://www.cogs.susx.ac.uk/users/ianw/papers/ansurvey.ps.gz.
• 13: Mads Tofte , Jean-Pierre Talpin, Region-based memory management, Information and Computation, v.132 n.2, p.109-176, Feb. 1, 1997 [doi>10.1006/inco.1996.2613]
• 14: Zhanyong Wan , Walid Taha , Paul Hudak, Real-time FRP, Proceedings of the sixth ACM SIGPLAN international conference on Functional programming, September 03-05, 2001, Florence, Italy
• 15: Zhanyong Wan , Walid Taha , Paul Hudak, Event-Driven FRP, Proceedings of the 4th International Symposium on Practical Aspects of Declarative Languages, p.155-172, January 19-20, 2002

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

General Terms:
Design, Experimentation, Languages

Keywords:
finite state automata, functional language, multi-process simulation