Category Archives: Life and everything

Food, challenges and inspiration

This time it was a fantastic week-end, we had a meal with an old friend and an unexpected guest. Can it get any better than a table, with nice (french-canadian) food on it, and intelligent people around it, talking about programming language design? Aside from being wise and clever, what our new friend brought was experience. Insights from others that went down the road of creating a programming language is a precious thing. We learned a lot about the challenges that waits ahead.

We spent a large part of the conversation challenging Alex on his design. Until this day, a few friends had challenged him and I also do the same on a daily basis. But our two guests had a different approach, they have a lot of experience with C++ and other languages, and are actively participating in the D 2.0 effort. They are somewhat part of the competition! This time, I switched side and practiced my own sales pitch to stand by my husband. We had to cross the language barrier as well, English being a second language for everyone.

This challenge was very stimulating, discovering what others seek into a programming language, finding about things we never thought about, explain ideas and try to be convincing about them, and the most important, having fun doing all that. We also reached a point where things were not defined, or refined enough to explain it to someone else, there we had to realize the necessity of putting things down on paper.

After all this, I was bursting with ideas about the importance of documentation in the elaboration of a clear vision. I started working on a new twist of the iterative methodology and couldn’t stop. We went to a Christmas music concert and I started writing everywhere on the concert program. I wanted to write a blog post about this, but I have to calm down and make something organized with all this before it becomes possible.

The dynamic between the two of us is taking shape with each challenges, what is my role into all this, and where he has to work alone. I am growing skills in communication and management in my day job, but in the end, he is the technical expert. This is probably to our advantage, we complete each other in so many ways. They say that behind every great man there’s a great woman, with such a great husband, I will have to surpass myself to keep this saying true.


Winter is back

winterisbackOh here I am to my first « why I haven’t been writing » blog post. I received a comment today asking why I let the site down for so much time, so I have to give an answer at least. So I’m back from a long trip to Europe, which was wonderful. Most of our family, friends and coworkers found pretty weird that I decided to leave without my husband. We both had the same amount of vacation but we have different priorities, for him C3 is on top!

Summer has been a very busy time; because we live in the north, we have a very short period where we can actually work on the house and breathe non-frozen air. On the other hand, in the winter, there is nothing else to do other than cuddle, blog and write compilers.

So everyone rejoice, winter is back and we are also back on working on C3. I say we, but he actually did quite a bunch of things while I was away. He finished writing the PEG parser (now named IPG) and is now starting to write the generator. Also, he read a bunch of things that may have an impact of the C3.

The main discovery was LLVM, or low level vitual machine; some kind of assembly language but ultra portable. It features an amazing level of optimization and flexibility that makes it a very good candidate for a first back-end.

on-the-edge-commodoreThe book about the history of Commodore was an interesting read he says, but is probably more teaching about what not to do. I’m not sure if he did finish the book on ANTLR, a parser generator, seems it doesn’t match his need.
cover-bigHe is now reading Coders at Work. He really liked Founders at Work and is stimulated by those insider’s insights. Don’t be afraid to ask questions, it really helps me with my inspiration!

By the way, if you understand french, you can follow me on twitter and listen to my podcast !standard .

Finding good tools to make greater tools

Programming is usually something fun, but there is two types of situation that always made me mad:

  • Spending too much time finding a stupid syntax error because the compiler gives me a very weird error message and pointing to the wrong place in the code.
  • Having to hack my way out to trace a bug because the debugger doesn’t give me the information I need (or worse, gives me a false answer).

Mostly, as programmers, we want to spend our time creating, and not fighting against our tools.c3wifeinternalerror1

My husband was using XCode until recently. Having only mac at home, this was the obvious choice. But as the codebase continue to grow, he was getting more and more of those two things. Then the search for an alternative started. Codewarrior doesn’t support mac anymore. Anyway we already made an overdose of it in the past, back when we were mac game programmers! Then came Eclipse, he’s testing it now. Will he stick to it? Will he go back to XCode? Will something new arise? Or will he simply buy a PC and go back to Visual Studio and it’s comfortable Visual Assist. Eclipse debugger seems to be a little better, probably because it uses GDB/MI instead of directly parsing GDB’s output (more info). I expect support for C++ to grow very slowly for XCode, Apple’s attention being focused on C and Objective-C (a very similar fate to OpenGL because games weren’t a priority for Apple until recently).

No matter how good the tools are, the root of the problem is in the language grammar. The more hacks there is in your parser, the more difficult it will be to give clear error messages or debug correctly. Leaving retro-compatibility behind open the door to a design that would minimize those problems. In order to do that, my husband always keeps in the KISS motto in mind. A nice lean grammar implemented in a simple yet elegant way shall have lots of good influence in the future. This is a big part of why he didn’t go for YARD; sure he loves templates, but sometimes they are just too much for the needs.

Clear error messages and precise debugging tools are part of the big dream. It won’t prevent us from making stupid mistakes, but will sure save time when we do.

C3’s first sprint backlog

c3wifefirstbacklogLots of our friends, coworkers and cousins had a baby recently. Each of them have this picture of the baby at the hospital with a very cute hat written “My first hat” on it. There is this obssession with babies and the first time they get something done: first step, first word, first day at school, first whatever! C3 having no head or feet can’t have what other children have, but still have it’s first something. We have been talking about it for a while, but today mark the beginning of the first sprint and this comes with a very nice backlog. This is a task-list based on the scrum method, which is gaining popularity in the technology field. Obviously, since my husband is doing this part time we won’t put an end date to the sprint, but at the end, we intent to release something for you my fellow reader, in order to get your comments.

It was hard for me at first to define how to list this. In my husband head, it took the form of a recursive algorithm, while a backlog should be linear (without ifs or gotos) So here I’m unfolding this for you:

Sprint 1: Build a PEG parser with semantic actions that will be able able to regenerate ifself
-Parse PEG description file (without semantic actions) – Done
-Display concrete syntactic tree with the console – Done
-Build the abtract syntactic tree – In progress (Done but not tested)
-Display abstract syntactic tree with the console
-Create a generator of all previous steps
-Parse PEG description file with semantic actions
-Build the abstract syntactic tree with semantic actions
-Adapt the generator with semantic actions

This is a proof of concept. If the PEG parser generator can regenerate itself, (and again, and again) this will be a proof that the algorithm is working. After that he’ll concentrate on the next step: Update the C3 grammar with all the new thing he though about in the last few years!

Double-sided discovery

Yesterday my husband found out about YARD, yet another recursive descent. If you read the description in the article he send me this morning, you’ll find out it does mostly what I described in my latest post (PEG Parser). The problem is, he already have coded most of the features that exist in this library and there is no point redoing everything once again. Inspiration on the other hand is a very good thing.

The main problem is that YARD doesn’t fully support semantic actions and pegtl (another library based on YARD) doesn’t work with many compilers because it uses unreleased feature of C++0x.

This is another proof that the world needs a unified way to share code. YARD have been existing as early as 2004 and yet, he didn’t stumble upon it while searching with google in december. It took an article on Dr. Dobb’s to learn about it. The date: january 2009; five year after the first publication.

Funny thing, the author, Christopher Diggins, lives in the same province, not that far from our place. Almost looks like a trend in our area!

Now coding: parser generator

Thinking of great design is one thing, making it happen is a step fewer people are able to make. So here I’ll describe what have been done so far, what is currently being implemented, and why my husband chose these steps to begin with. The Spirit parser has been lost and wouldn’t be of any use anyway, so he’s making a fresh start. The first step into making a compiler, would be making a parser, which would transform code into an abstract syntax tree. But the first step into making C3 is to make a parser generator.

Currently used language compilers are often built around a context-free grammar. This is a concept directly taken from the Chomsky hierarchy, which describes the different types of formal languages. In the 2000s, Brian Ford gave a name to a concept that has already been floating for a while: the parsing expression grammar, or PEG. The Chomsky hierarchy describes how the sentence (or program) should be composed, while the PEG is going reverse, describing how to recognize a correct sentence of the language.

A context-free grammar usually leads to a bottom-up parser which is very complex. Two well known bottom-up parser generators are YACC (yet another compiler compiler) and Bison (GNU version of Yacc). They achieve a level of complexity that makes the generated code hard to understand and almost impossible to debug. On the other hand, there isn’t many top-down parser generators, probably because it’s a lot easier to directly write the parser which would be a recursive descent parser. PEGs are formal descriptions for this kind of parser. Spirit was described by its author as using modified context-free grammars but in fact it was using PEGs before anyone heard of them!

There are many advantages to use PEGs. The context-free grammar have to consider all possibilities at parsing time, and when facing two possible solutions, it cannot resolve itself without a hack. This is called a “conflict”. For example, many subsequent “if” are in the code, then comes an “else”. The context-free grammar doesn’t know with which “if” to associate the “else”, they are all possible solutions in the grammar definition. A hack is necessary to associate this “else” with the correct “if”. The PEG use a greedy algorithm with a priority to the different possibilities. It doesn’t need to be told what to do in all conflicting situation, it just take the highest priority. This makes the algorithm a lot simpler, and possibly more efficient. This is ideal for programming languages for which the main objective is to be parsed into something else, and the language can be designed based on this assumption. Chomsky’s theory of language was made to describe existing (natural) languages, it is normal that it may not be the most fitting tool to create a new one.

Another thing: when creating a context-free grammar parser, we need to have both a parser and a lexer (also called scanner). The lexer do a top-down operation on small pieces (numbers, variables, etc.) in order to let the parser handle the bigger chunks (instructions, functions, etc.) in a bottom-up way. When parsing top-down, no need for two tools, this is all handled in a single operation. The main reason why this can be done with PEG is that repetition is handled without recursivity. The more I learn about lexer, the more they feel like a big hack, good riddance, hi hi!

A funny thing is that Bjarne Stroustrup himself now regrets his choice of a bottom-up parser. At that time he was counseled by language and grammar specialists that this was the only way to go. But the implementation was so complex, he now thinks that a simple recursive descent parser would have done the job after all.

The type of parser the parser-generator is going to create is a packrat parser, which is a type of recursive descent parser. Recursive descent parsers have backtracking. That means that if the parser realize it took the wrong path because of its greedy nature, it will go backward an try the next solution in the priority table. With packrat parsing, if a subpart of the bad parsing finished correctly, it will be stored in a table to be reused in the following treatment if possible. This optimization is named memoisation.

So at this time, my husband is writing a PEG-packrat parser generator. This isn’t a necessary task, he could have just jumped into coding the parser itself. But having the parser generator will make things more flexible, and it’s also fun to implement (for him at least). There wasn’t any satisfying generator known when he started coding it, including Spirit which have poor compile-time performance and too much complexity coming from C++ templates techniques (after all, he wants to reimplement everything in C3 at some point). He now has a “PEG PEG”, which parse files of PEG description and is working toward PEG parser generator.

There are many concepts in this post that you may never have heard of. This is totally normal. I encourage you to follow the links and read about them. I don’t know if it will make you a better person, but this is all very interesting and essential to understand the fundamentals of programming languages.

The early days

The first ideas about C3 emerged while my husband was at the university. He was a first class student with very high marks even though he wasn’t the most studious. These led him to internship in major companies, but the inspiration didn’t really came from there, the dream was already in him before entering the university in year 2000. At that time, he wanted to created a language as simple as Visual Basic, but as powerful as C++. Learning more about C++ made the idea evolve into something else, the more he coded, the more ideas he had about a new language that would get the name C3 three years later.

The first step into reality was a C3 parser made with Spirit, which is a C++ compile-time parser generator based on expression templates. This parser takes a C3 file, creates the abstract syntax tree and outputs it in a file in XML format. This is somewhat of a proof of concept, a demonstration that the grammar works on practical examples. He acknowledge that this isn’t a full proof, because he haven’t shown that it works for all possibilities. This isn’t a priority anyway, many languages haven’t proved that either. This experience proved two important things. First, the grammar is well designed and there is no need for hacks to generate the abstract syntax tree (which is the case for many languages, including C++). And, he is a good enough programmer to handle such a project! I wouldn’t have married him if I wasn’t sure of that. Ah ah! At least, I wouldn’t be writing this blog.

There is a big void after this, he talked about it quite often, probably thought a lot about it, things continued to grow in this head, but no coding happened for a while. That’s when I met him, I don’t feel I was the distraction however. The company we worked for was very small, and even though we had fun, we worked many hours which didn’t leave much inspiration for coding at home. This would last from 2004 to 2008. The company changed a lot in this period, there are now more than 10 times the number of people than there was when we were hired. At the end of 2008, my soon to be husband completed a very important project and took a few weeks off, connecting with the Christmas vacation, which would make a full month of time to spare. In the second week, he started coding again, like this essential need to create C3, buried for too long, found the surface once again. He hasn’t stopped since, and now that he transfered to a more stable department, I feel confident he won’t stop. I hope that my vulgarization work will help him keep his motivation, this is my main goal in writing this blog (and maybe entertain you all a little, ah!)

First impression

We finally found an wireless connection at the hotel, this should make update easier; and my mother-in-law more comfortable. I understand that she was worrying after a full week of silence.

I show this site for the first time to three programmer friends this morning, here is what they said:

  • Will it support web programming?
  • Can I write the first book about C3?
  • I’ll talk to you later, I’m late for class!

About web programming, the language itself is designed to support mostly everything we know of, including web-oriented programming. The real answer would be: when someone implement support for it, it will become available. Some basic web functionality may be developed early in the process or maybe a javascript backend, but we aren’t there yet. In fact, the web may have changed a lot by the time C3 becomes mature enough to make full support of it. If you are interested in implementing this for the C3 community, you should be able to do it soon!

The first book about C3 will be written by myself, or so I hope! My husband is already writing more technical things on the side but I won’t publish them for now as too much things are still changing. After a bit more discussion, my friend agreed to write the first “C3 for dummies” which is fine by me!

And finally, my student friend is clearly too satisfied with Java to be interested in C3, ah ah, I’m kidding. Still, we are aware that there is many thing to build before entering the competitive world of programming languages. While my husband is working on the core aspects, the main interest remains the creative process of designing a programming language.

Starting to write about C3 has been a powerful kick off for this project which had been standing by for too long. Each answer he gives me opens new doors for other questions. I haven’t been far in the language description so far but don’t hesitate if any question crosses your mind, I’ll be happy to ask my husband!

Last note: english is a second language to me, don’t hesitate to point me any mistakes I could have made.

Wife in progress…

c3wifewifeinprogressI’m not a wife yet, less than two weeks before it happens though. My soon to be husband is writing… pardon me, creating a programming language. Something new and amazing that could change the world, revolutionize how the human is communicating with the machine. So I decided that if something big was going on, maybe someone ought to start talking about it, I could well be that person. Only one obstacle to this, I’ve got a wedding to prepare. I’ll be back during my honeymoon to tell you about C3, because there is much more to do in Mexico than Maya ruins and beaches.