January 20th, 2010 — publication Tagged embedded, events, programming models, threads, wireless sensor networks
Major motes operating systems like TinyOS or Contiki rely on an event-driven programming paradigm. While the use of events allows for limiting memory usage on resource-constrained motes, it may also hamper the development and debugging of applications, especially as their complexity increases [Dunkels2006]. Several authors also investigated the possibility of introducing threads to mote programming [McCartney2009, Duffy2007, Klues2009]. However, the proposed solutions all induce runtime overhead which is inherent to the thread paradigm. In contrast, protothreads combine the benefits of both paradigms by providing thread semantics to the programmer while using events at runtime. This is achieved by an automatic code generation step performed by the C preprocessor. However, while using the C preprocessor guarantees portability across C compilers, it also introduces some limitations. For instance, certain C language constructs such as switch statements may not be used and values of local variables are not retained across context switches. Furthermore, thread functions are not reentrant, blocking calls may only occur in the top-level thread functions, and debugging is performed in the generated code.
To overcome these limitations, we propose to extend the protothreads abstraction by providing cooperative threads with blocking I/O, reentrant functions, and arbitrary nesting of function calls. This is achieved by a comprehensive compiler which translates thread-based code into efficient event-based code. In order to guarantee the efficiency of the generated code there are still some limitations, though. First, the exact number of threads must be known at compile time. Second, recursive functions must not invoke blocking functions. And third, function pointers must not be used to invoke functions that directly or indirectly invoke blocking functions. We argue, though, that these limitations do not severely affect programming of motes as these constructs are rarely used. Furthermore, the compiler can reliably detect any violations of those restrictions.
Continue reading →
November 9th, 2009 — article Tagged code generation, debugging
One of the challenges in meta programming is the ability to debug on the meta level. It is not satisfying to have to step through the generated code in order to figure out what is wrong in the model. And indeed many meta programming toolchains have poor support for proper debugging.
But wait, this problem has in principle actually been solved since ages. When we reduce meta programming to code transformation and realize that a C compiler in that sense is a code transformer this becomes apparent. Almost nobody steps through the assembler code in order to find a bug in the C source. Instead the toolchain has support for so called source level debugging, which is exactly what we want: debugging on the meta level. So it seams advisable to understand the concepts of source level debugging so that we can copy or adapt them to meta programming. That’s why I decided to explore the GCC and the GDB together with its graphical frontend DDD which are the tools I am most familiar with.
Continue reading →
October 23rd, 2009 — article Tagged linux
Since 2008, MD5 is considered broken. Consequently GnuTLS refuses signatures of certificates if they were made with MD5. That’s why since my latest Debian upgrade, msmtp, which uses libgnutls, has not been able to establish a checked TLS session with the SMTP server.
Continue reading →
September 16th, 2009 — article Tagged parser
Rats! is an “easily extensible parser generator for C-like languages” written by Robert Grimm. The main idea of Rats! is to exploit the extensibility of PEGs by providing support for parametrizable grammar modules which can use, instantiate, extend and modify each other. Grimm describes version 1.8.2 of Rats! in Better Extensibility through Modular Syntax. More documentation can be found in the Rats! intro. It is part of the the extensive Javadoc of the xtc project, which is the framework project of Rats!. Here comes what I consider the main design principles, features and properties of Rats!.
Continue reading →
August 20th, 2009 — article Tagged code generation, transformer
As mentioned previously the term language-oriented programming (LOP) today mainly refers to the underlying paradigm of JetBrains‘s Meta Programming System. This is due to a publication from Sergey Dmitriev entitled Language Oriented Programming: The Next Programming Paradigm. There he proclaims the next technology revolution which leads us from the Stone Age to “a new age of invention and an explosion of new technologies”. The paper is very stirringly written but while smiling at this I agree with him in many points. Here is what I consider his main statements.
Continue reading →
August 5th, 2009 — article Tagged programming models
Worlds is “a language construct that reifies the notion of program state, and enables programmers to control the scope of side effects.” Alessandro Warth investigaged this idea together with Alan Kay in a paper entitled Worlds: Controlling the Scope of Side Effects. Chapter 4 of Warth’s dissertation Experimenting with Programming Languages obsoletes this paper. Worlds/JS is an extension of JavaScript implementing worlds.
The basic idea is to turn program state into first-class objects, allowing them to co-exist in the same program and enable them to inherit and delegate state to and from each other. Warth calls such a program state object a world. “All computation takes place inside a world, which captures all of the side effects [...] that happen inside it”.
Continue reading →
July 23rd, 2009 — article Tagged code generation
The term “language-oriented programming” (LOP) is these days mainly used by JetBrains and refers to the underlying paradigm of their Meta Programming System. I will blog about that later. For now I want to focus on Martin Ward, because the LOP term was actually coined by him in 1994 with a paper entitled Language Oriented Programming. There he describes what I consider the core idea of meta-programming. And in fact he names many of the benefits, problems, guidelines and other insights that one can find in today’s discussions about MDSD. Here is an extraction of these:
Continue reading →
July 12th, 2009 — article Tagged parser
OMeta is an object-oriented language for pattern matching based on Parsing Expression Grammars (PEG). It makes some valuable extensions to standard PEGs which I want to summarize here. My main source of information is the paper OMeta: an Object-Oriented Language for Pattern Matching by Alessandro Warth and Ian Piumatra.
Continue reading →
July 9th, 2009 — article Tagged code generation, parser, transformer
Stratego/XT is the first meta programming system I had a closer look at. The project defines itself as “a language and tool set for program transformation”. By program transformation they mean “programming tasks using some form of automatic program generation or transformation, such as code generation from a domain-specific language, aspect weaving, optimization, or specialization of a generic program to a particular context.” So Stratego/XT follows a more generalized approach then what MDE needs.
Continue reading →
July 8th, 2009 — article Tagged parser
Parsing Expression Grammar (PEG) is a rather new class of grammars for formal languages. The foundations date back to 1973 and come from “Parsing algorithms with backtrack” by Alexander Birman and Jeffrey D. Ullman. But in those days the approach was considered as not being practical because of limited memory resources. In 2002 Bryan Ford revived the topic in his master’s thesis Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking by turning the theoretical model into an equivalent, but practical one. Since then the topic has been gaining more and more attraction and additional publications followed. Bryan is collecting the – in his mind – important ones on a PEG homepage.
Continue reading →
