High-level languages for small devices: a case study

ABSTRACT

In this paper we study, through a concrete case, the feasibility of using a high-level, general-purpose logic language in the design and implementation of applications targeting wearable computers. The case study is a "sound spatializer" which, given real-time signals for monaural audio and heading, generates stereo sound which appears to come from a position in space. The use of advanced compile-time transformations and optimizations made it possible to execute code written in a clear style without efficiency or architectural concerns on the target device, while meeting strict existing time and memory constraints. The final executable compares favorably with a similar implementation written in C. We believe that this case is representative of a wider class of common pervasive computing applications, and that the techniques we show here can be put to good use in a range of scenarios. This points to the possibility of applying high-level languages, with their associated exibility, conciseness, ability to be automatically parallelized, sophisticated compile-time tools for analysis and verification, etc., to the embedded systems eld without paying an unnecessary performance penalty.

References

1. P. A. Bigot and S. K. Debray. A Simple Approach to Supporting Untagged Objects in Dynamically Typed Languages. In International Logic Programming Symposium, pages 257--271, 1995.]]
2. J. Blauert. Spatial Hearing: The Psychophysics of Human Sound Localization. The MIT Press, 1983.]]
3. G. Bolella and J. Gosling. The Real-Time Specification for Java. IEEE Computer, 33(6), June 2000.]]
4. F. Bueno, D. Cabeza, M. Carro, M. Hermenegildo, P. López-Garcá, and G. P. (Eds. ). The Ciao System. Reference Manual (v1. 10). Technical report, School of Computer Science (UPM), 2004. Available at http://clip.dia.fi.upm.es/Software/Ciao/.]]
5. M. Carro and M. Hermenegildo. Concurrency in Prolog Using Threads and a Shared Database. In 1999 International Conference on Logic Programming, pages 320--334. MIT Press, Cambridge, MA, USA, November 1999.]]
6. A. Casas, D. Cabeza, and M. Hermenegildo. A Syntactic Approach to Combining Functional Notation, Lazy Evaluation and Higher-Order in LP Systems. In Eighth International Symposium on Functional and Logic Programming (FLOPS'06), Fuji Susono (Japan), April 2006.]]
7. P. Cousot and R. Cousot. Abstract Interpretation: a Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. In Proc. of POPL'77, pages 238--252, 1977.]]
8. G. Gupta, E. Pontelli, K. Ali, M. Carlsson, and M. Hermenegildo. Parallel Execution of Prolog Programs: a Survey. ACM Transactions on Programming Languages and Systems, 23(4):472--602, July 2001.]]
9. M. Hermenegildo, F. Bueno, D. Cabeza, M. Carro, M. Garcá de la Banda, P. López-Garcá, and G. Puebla. The CIAO Multi-Dialect Compiler and System: An Experimentation Workbench for Future (C)LP Systems. In Parallelism and Implementation of Logic and Constraint Logic Programming, pages 65--85. Nova Science, Commack, NY, USA, April 1999.]]
10. M. Hermenegildo, G. Puebla, F. Bueno, and P. López-Garcá. Integrated Program Debugging, Verification, and Optimization Using Abstract Interpretation (and The Ciao System Preprocessor). Science of Computer Programming, 58(1 ?2):115--140, October 2005.]]
11. S. P. Jones, editor. Haskell 98 Language and Libraries: The Revised Report. Cambridge University Press, 2003.]]
12. E. A. Lee. Overview of the Ptolemy Project. Technical Report UCB/ERL M03/25, University of California at Berkeley, July 2003.]]
13. X. Leroy. Unboxed Objects and Polymorphic Typing. In Conference Record of the Nineteenth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 177--188, Albequerque, New Mexico, 1992.]]
14. M. Leuschel. Design and Implementation of the High-Level Specification Language CSP(LP). In I. V. Ramakrishnan, editor, PADL'01, volume 1990 of Lecture Notes in Computer Science, page 14. Springer-Verlag, March 2001.]]
15. M. McCarthy and H. Muller. No Pingers: Ultrasonic Indoor Location Sensing without RF Synchonisation. Technical Report 003-004, University of Bristol, Department of Computer Science, May 2003.]]
16. J. Morales, M. Carro, and M. Hermenegildo. Improving the Compilation of Prolog to C Using Moded Types and Determinism Information. In Intnl. Symposium on Practical Aspects of Declarative Languages, number 3057 in LNCS, pages 86--103. Springer, June 2004.]]
17. H. Muller and C. Randell. An Event-Driven Sensor Architecture for Low Power Wearables. In ICSE 2000, Workshop on Software Engineering for Wearable and Pervasive Computing, pages 39--41. ACM/IEEE, June 2000.]]
18. J. Peterson. Untagged Data in Tagged Environments: Choosing Optimal Representations at Compile Time. In Fourth International Conference on Functional Programming Languages and Computer Architecture, pages 89--99. ACM Press, September 1989.]]
19. J. Peterson, P. Hudak, and C. Elliott. Lambda in Motion: Controlling Robots with Haskell. In PADL, pages 91--105, 1999.]]
20. S. L. Peyton Jones and J. Launchbury. Unboxed Values as First Class Citizens in a Non-strict Functional Language. In J. Hughes, editor, Proceedings of the Conference on Functional Programming and Computer Architecture, pages 636--666, Cambridge, Massachussets, USA, 26--28 August 1991. Springer-Verlag LNCS523.]]
21. G. Puebla, F. Bueno, and M. Hermenegildo. An Assertion Language for Constraint Logic Programs. In Analysis and Visualization Tools for Constraint Programming, pages 23--61. Springer LNCS 1870, 2000.]]
22. C. Randell and H. L. Muller. The Well Mannered Wearable Computer. Personal and Ubiquitous Computing, 6(1):31--36, February 2002.]]
23. Z. Somogyi, F. Henderson, and T. Conway. The Execution Algorithm of Mercury:an E cient Purely Declarative Logic Programming Language. JLP, 29(1 ?3), October 1996.]]
24. R. Stevens. A Survey of Stream Processing. Acta Informatica, 34:491--541, 1997.]]
25. W. Thies, M. Karczmarek, and S. Amarasinghe. StreamIt: A Language for Streaming Applications. In International Conference on Compiler Construction, number 2304 in LNCS, pages 179--196. Springer Verlag, 2002.]]
26. P. Van Roy. Can Logic Programming Execute as Fast as Imperative Programming? PhD thesis, Univ. of California Berkeley, 1990. Report No. UCB/CSD 90/600.]]
27. C. Vaucheret and F. Bueno. More Precise yet Efficient Type Inference for Logic Programs. In Proc. of SAS'02, pages 102--116. Springer LNCS 2477, 2002.]]
28. M. Wallace. Functional Programming and Embedded Systems. PhD thesis, York University, January 1995.]]
29. G. Welch and G. Bishop. An Introduction to the Kalman Filter. Technical Report TR95-041, Department of Computer Science, University of North Carolina-Chapel Hill, November 1995.]]
30. M. Wolfe. How Compilers and Tools Differ for Embedded Systems. In International Conference on Compilers, Architecture, and Synthesis for Embedded Systems. ACM and IEEE Computer Society, September 2005. Keynote Speech.]]

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Knowledge representation and reasoning

      • Logic programming and answer set programming

• Hardware

  • Electronic design automation

    • Methodologies for EDA

  • Integrated circuits

    • Logic circuits

      • Arithmetic and datapath circuits

      • Design modules and hierarchy

• Software and its engineering

  • Software notations and tools

    • Compilers

      • Source code generation

    • General programming languages

      • Language types

        • Constraint and logic languages