I just finished working on the 0.7.1 version of eddic.

Even it it's a minor version, there are several new features in the language itself.

First of all, the boolean conditions have been greatly improved. You can now use && (short circuit and operator) and || (short circuit or operator) operators to make complex conditions for if and while structure. Moreover, you can now declare variables of bool type. You can also print bool variables. That will simplify the code that can be written with EDDI.

Another big improvement to the language is the addition of increment and decrement operators. Both postfix and prefix forms are available. You can use an increment or decrement as a single statement or inside another expressions.

Increment and decrement operators are not the only operators added to the language. You can now use compound operators (+=, -=, *=, /= and %=) to make direct modifications to variables.

In the next version, there will certainly be some improvements of the generated assembly. I don't know what improvement will be done on the language.

If some of you have an idea of improvement for the language or the compiler itself, don't hesitate to make me know :)

Download

You can find the compiler sources on the Github repository : https://github.com/wichtounet/eddic

The exact version I refer to is the v0.7.1 available in the github tags or directly as the release branch.

Insight is a very good debugger based on gdb. I prefer it over ddd or kdbg as I find it clearer and easier to use. Moreover, this debugger is also the one used in the book Assembly language Step by Step, for Linux. However, Insight has been removed from Debian packages already more than a year ago.

But, thanks to SevenMachines, a PPA repository is available to install it on Linux Mint (works also on Ubuntu and Ubuntu-based Linux distributions).

To add the repository to your apt sources, add the following lines to the /etc/apt/sources.list file:

deb http://ppa.launchpad.net/sevenmachines/dev/ubuntu natty main 
deb-src http://ppa.launchpad.net/sevenmachines/dev/ubuntu natty main 

and update your apt sources:

sudo apt-get update

Then you can install insight:

sudo apt-get install insight

And now you are ready to use Insight as your debugger.

If you don't trust this PPA repository, you can also try it to install it from the sources (http://sources.redhat.com/insight/), but doesn't seem to very simple to install it. I wasn't able to build it on my Linux Mint 12.

The title is not really clear but I didn't found a better one. The example will be clearer (I hope). In EDDI, I had this little function :

template<typename Visitor, typename Visitable>
void visit(Visitor&amp; visitor, Visitable&amp; visitable){
    visitor(visitable);
}

For the record, this function is only invoking a specific operator of a visitor. The problem was that I wanted this function to handle also non-void visitors. The visitor in question has a result_type typedef indicating the return type of the visit. The naive version cannot work :

template<typename Visitor, typename Visitable>
typename Visitor::result_type visit(Visitor&amp; visitor, Visitable&amp; visitable){
    return visitor(visitable);
}

template<typename Visitor, typename Visitable>
void visit(Visitor&amp; visitor, Visitable&amp; visitable){
    visitor(visitable);
}

The problem here is that there are ambiguities for overload resolution because the return type is not considered in this resolution. What we want is that the overload resolution does not consider the function returning something (the first one). And that's here that Boost can help, specifically the Boost enable_if library. This function allows to enable of disable some function template of function class based on a boolean condition. In our case, we want to disable the function is the return type is void. So, we will use the boost::disable_if template to disable it. This template has to parameter B and T. When B is true, the template is evaluated to T, otherwise there is an error used for SFINAE (Substitution failure is not an error) To test if the return type is void, we will use Boost type_traits, specifically the boost::is_void template.

Here is the version using disable_if :

template<typename Visitor, typename Visitable>
typename boost::disable_if<boost::is_void<typename Visitor::result_type>, typename Visitor::result_type>::type
visit(Visitor&amp; visitor, Visitable&amp; visitable){
    return visitor(visitable);
}

template<typename Visitor, typename Visitable>
void visit(Visitor&amp; visitor, Visitable&amp; visitable){
    visitor(visitable);
}

With that, you can call the visitor with a void return type. However, it's not enough. Indeed, the call is still ambiguous when the return type is not void. So we have to enable the second function only if the return type is void :

template<typename Visitor, typename Visitable>
typename boost::disable_if<boost::is_void<typename Visitor::result_type>, typename Visitor::result_type>::type
visit(Visitor&amp; visitor, Visitable&amp; visitable){
    return visitor(visitable);
}

template<typename Visitor, typename Visitable>
typename boost::enable_if<boost::is_void<typename Visitor::result_type>, typename Visitor::result_type>::type
visit(Visitor&amp; visitor, Visitable&amp; visitable){
    visitor(visitable);
}

With that, you can call the function with both visitors and the good function will be chosen depending on the result type of the visitor.

I hope this example of using Boost enable_if will help you when you face similar problems.

Some weeks ago, I finished reading Compilers : Principles, Techniques & Tools, by Afred V. Aho, Monica S. Lam, Ravi Sethi and Jeffrey D. Ullman. This book is also called the Dragon Book due to the cover.

This book is a reference about compiler construction and design. If you are interested in this subject, this book is for you, it's a must-have. However, I have to warn you that this book is very technical and hard. Honestly, some of the chapters are beyond my comprehension. Before this book, I had no real comprehension of the subject. I will certainly read again some of the chapters when I will have more practice into the subject.

If you want, the book is full of exercises about each subject covered in the book. If you plan to do all the exercises, you'll need a lot of time as there are a lot of them and some of them are quite hard. I've done some of them but only a little part.

The first chapter introduces the construction of compilers. You will see the common structure of compilers, the evolution of programming languages and the science behind building a compiler and its applications. The second chapter is still quite general. It will teach you how to develop a simple syntax-directed translator. This chapter is very important as it will give you the basics for understanding the following chapters. You will learn how to define a grammar, what are the main parsing techniques and what is lexical analysis. It will also covers symbol tables and intermediate language generation.

With the third chapter (Lexical Analysis), we are entering the hearth of the matter. You will learn the vocabulary behind lexical analysis (tokens, lexemes, attributes, ...). Then, after you've learned how to define and recognize tokens, you will see the different techniques to build an efficient lexical analyzer. The first technique that will be covered is the use of a lexer generator (Lex). Then you will see in details how to construct a lexer using regular expressions or finite automata especially Nondeterministic Finite Automata and Deterministic Finite Automata.

The next one (Syntax Analysis) is about parsing. After learning how to define and write a grammar you will see how to parse it. You will see in details the most commons types of parsing (Top-Down, Bottom-Up) and the most common parsers (LL(K) and LR(K) parsers). The construction of these kinds of parsers is covered in details and the way to optimize them is also teached. Finally, you will see how to automatically generate a parser using Lex and Yacc. This chapter is sometimes very hard to understand (in my own opinion) but very interesting especially if you plan to build parser without generating it with some advanced tools (for example Yacc or Boost Spirit for C++).

The fourth chapter (Syntax Directed Translation) explains you how to translate some source code (parse it) into a coherent structure (an abstract tree) using a Syntax Directed Scheme. The translation is made based on a syntax using semantic actions and rules to translate the source into something else. You'll see different ways of doing that translations.

Then, the next one (Intermediate Code Generation) teaches you how to generate Intermediate Code from the source. Two different representations are covered : syntax trees and three-address-code. Another subject covered in this chapter is type checking. You'll see in details how to translate expressions, control flow instructions and switch statements into three-address-code statements.

The seventh chapter (Run-Time Environment) gives a lot of information about the different run-time targets that you can compile for. A lot of subjects are covered here: stack and heap allocation, locality exploitation, garbage collectors... This chapter is in my opinion a very good instruction to computer architecture. You cannot imagine develop a compiler without having a deep understanding of the target machine.

The next chapter (Code Generation) is also a very important one. In this chapter, you will see how to generate assembly code from the three-address-code. You will learn how to select the good instructions. A very important subject covered in this chapter is register allocation. You'll learn how to choose wisely the registers to produce efficient code. The basic blocks are also covered there with flow graphs. More than just generating code from Three-Address-Code statements, you'll also see how to optimize them. Only local (to a basic block) optimization techniques  will be covered in this chapter. Several techniques that aims at testing if code is optimal are also taught there.

The global optimizations are covered in the next chapter (Machine-Independent Optimizations). You will discover several optimizations that you can do globally (inside a function but among different basic blocks). A data-flow analysis framework is explained here in details. After that, for each of the optimization, the parameters of the data flow analysis are explained. The optimization of loops is treated too.

The three next chapters (Instruction-Level Parallelism, Optimizing for Parallelism and Locality and Interprocedural Analysis) are the most complex of the book. They are covering in details the optimizations that can be made when a compiler supports instruction-level parallelism (executes several instructions in one clock cycle). It also covers interprocedural analysis of a program to allow even better optimization than global optimization inside a function. Honestly, I didn't understand some of the concepts described here. I will read them again one by one, chapter by chapter and try to implement some of the techniques in EDDI in the future.

To conclude, I will say that Compilers : Principles, Techniques & Tools is a very good book that every compiler designer and developer should read before starting constructing a  compiler. Although very technical, it's quite clear and contains a huge amount of information. If  you plan to develop a compiler, it is a very good idea to read this book first.

I've implement some of the techniques explained in this book in my own compiler. I implemented most of the local optimizations presented and Intermediate Code generation. You can find some information here.

I'm proud to announce a new release of EDDIC, the version 0.7.

Most of the changes are internal to the compiler. I read a new book : Compilers: Principles, Techniques, and Tools and applied some of the advices of the author. The biggest change is the use of a new intermediate representation : Three-Address-Code statements. This representation is easy, all the statements are basically of the form a = b + c with + being any operator of the language. The big advantage of this representation is that we can easily run optimization on it. Another advantage is that this representation is complete enough to represent most of the programming languages, so, we can imagine compiling several different source languages into the TAC language and then compiling them the same way.

Once the Three-Address-Code representation is generated and separated into basic blocks, it is compiled into X86 assembly using a code generator. I've made a lot of improvements on the generated assembly. For example, I'm using several new instructions (neg, inc, dec, xor, ...) to generate more efficient code. Moreover, I'm doing a better use of registers with keeping variables into registers as long as possible.

Better optimization engine

Here is the list of what the optimizer do at the TAC level:

• Simplify arithmetic identities : a = b + 0 => a = b
• Reduce in strength : a = b * 2 => a = b + b
• Constant folding : a = 2 + 2 => a = 4
• Constant propagation : when a constant is assigned to a, reuse the constant as long as no other assignment is made to a
• Remove overridden assign
• Remove dead basic blocks : when a condition is known at compile time we can know the path it will take and remove basic blocks that will never be taken
• Remove needless jumps : After the other optimization have been done it is possible that a goto is directly targeting the next basic block so we can remove it
• Merge basic blocks : After some statements have been replaced or removed it is possible that we can merge some basic blocks together

The optimizer is running the different optimization technique as long as one of them as an effect on the code. At the present time, the optimization techniques are used locally (within a basic block) so the generated assembly is not perfect, but for what I tested so far, it's a good start.

Other changes

Moreover, the language itself also had some improvements:

• The minus and plus unary operators have been added to the grammar
• The local and global variables can be const
• A source file can now includes another source or a file from the standard library (very little for now, but a little start)

The project itself has also been improved

• Most of the classes and files are now documented using Doxygen
• The unit tests are now testing compilation and execution of some samples, that helped me finding some bugs in the code base and in the new changes

Download

You can find the compiler sources on the Github repository : https://github.com/wichtounet/eddic.

The exact version I refer to is the v0.7 available in the github tags or directly as the release branch.

In the last Linux Mint version (12), the developers have introduced a set of extensions to the Gnome Shell, Mint Gnome Shell Extensions (MGSE).

But, plugins can't do everything the developers want. So they forked Gnome Shell and started building their own shell : Cinnamon.

At the time of writing, the appearance of this new shell is similar to MGSE in Linux Mint 12, but with some differences : only one status bar, the left bottom menu was changed, notification bar in the bottom bar, ...

You can try it on your Linux Mint right now :

sudo apt-get update
sudo apt-get install cinnamon-session

Then, you have to logout and select Cinnamon in the Logon screen as the desktop environment.

Personally, I still prefer MGSE, because I like having two bars, but that will perhaps change with some more tests on Cinnamon. And you, what do you think about Cinnamon ? Or about MGSE ?

If you want more informations about this new shell, you can read the official site.

A bit late, but better late than never : Merry Christmas to all the readers of this blog :)

In their December promotion, Pack Publishing are offering heavy discounts on all their Moodle books during all the month.

You can find all books available on offer on this page : http://www.packtpub.com/news/moodle-festive-month

There are great offers:

• Buy any Moodle print book and get 20% off
• Buy any Moodle eBook and get 30% off

For those who don't know Moodle, Moodle is currently the world's most popular E-learning platform. Moodle is a free, open-source PHP web application for producing modular internet-based courses that support a modern social constructionist pedagogy.

WordPress 3.3 introduces some very interesting features, specially for the blogger itself. It includes a new drag-and-drop uploader, hover menus for the navigation, a new toolbar, improved co-editing support, and a new Tumblr importer.

The admin interface has add a great cleanup too.

More information on the official release notes : http://wordpress.org/news/2011/12/sonny/

I already updated the blog to Wordpress 3.3 and it looks great for now. For the first time, I didn't have to disable all the addons prior to updating. This time it worked directly :)

After the Effective C++ Serie, I read C++ Templates: The Complete Guide, from David Vandevoorde and Nicolai M. Josuttis

The templates are one of the most powerful feature of C++. However, this is a complex technique that is often misused or misunderstood. This book will help you learning what exactly are templates and how they can be used to improve your software development in C++.

This book is sometimes very technical and is not the easiest to read. Nevertheless, the quality of the information it contains is great. This book covers all the aspects of template programming, from generic programming to template meta programming passing by traits and policy classes.

The first two chapters are introducing function templates and class templates. Then, the third chapter is about the nontype template parameters. Indeed, template parameters can be values and not types. For example, you can pass int constants as template parameters. Then, the two following chapters are more about templates in practice. You will learn the different way to include template code in your common C++ base code. You will also see some tricks useful when developing templates. The last chapter of this first part is fixing a terminology for templates.

The second part of the book (Templates in-Depth) starts with the fundamentals  of templates in-depth. Then, the names in templates are covered in details. After that, we have three very technical and complex chapters. The first covers the instantiations of templates in-depth, the second covers the template argument detection and the next one is about specializations and overloading. The last chapter of this part is about the future directions of the C++ templates. This chapter covers some extensions that have been added to library and compilers,  but were not in C++ standard at the time the book was written. Some of these futures directions are now part of the new C++11 standard.

The next part (Templates and Design) is about the techniques that can be used to improve your software design using templates. The first chapter covers the most common use of templates: compile-time polymorphism. Then, the traits and policy classes are covered. The traits classes are a way to add more information to a template parameter and policy classes represent a configurable behavior for templates. The 16th is talking about some optimization that can be made about templates and inheritance. The next chapter focuses on template metaprogramming. A metaprogram is a program that is not computed at runtime, but at compile-time resulting in performance sometimes very important. Then, the last chapter introduces the expression templates. This technique is a way to encapsulate expressions into templates in order to optimize some computations. The example is about matrix computations.

The final part (Advanced Applications) present four examples in which the templates brings a lot of power. The first example is about type classification. How to know at compile-time of what kind is a given type and makes something depending on the characteristics of the type. The second example is about developing Smart Pointers. The next one presents an implementation of tuples with templates and the last one implements function objects and callbacks. These four examples are not made to be used instead of the standard library, but there are good examples to prove the power of templates.

To conclude, I'll say that this book is a very good guide about templates. It covers most of the details that you can face when developing with templates or when working with very templatized libraries like Boost.