My website has moved again. The new location:
http://hyperquantum.be
And the pages about Hyper are here:
http://hyperquantum.be/hyper
I hope it's the last time I need to move my website. Having to update all links to it is not that much fun really.
Sunday, February 15, 2009
Saturday, February 07, 2009
Having "pure" functions
I have been thinking on this new feature for some time, but I'm not sure if it's a good idea. Just in case, the keyword for it has already been reserved in the 0.4.2 release of the compiler front end.
The idea is to introduce "pure" functions. Any procedure that is qualified as "pure" would guarantee to have no side effects and to have it's result only depend on the values of its parameters. The main purpose of this is to enable extra optimizations by the compiler, and to guarantee that some functions that do not need side-effects will not have them. So if you have some container class, its "count()" procedure (that returns the number of elements in the container) can be qualified as "pure" because it doesn't (and shouldn't) alter the state of the container, and because as long as the container is not modified, it will keep returning the same value over and over again. This implies that we consider the "this" pointer an implicit parameter for each non-static procedure, and that "pure" is a more restrictive version of the "const" qualifier for procedures. If you need a "pure" procedure that doesn't depend on its hidden "this" parameter, then you should also qualify it as "static".
Now the implications of this new feature:
The third one could make things a bit more difficult than they are now. If you design a class that will be inherited from, you will have to be careful that any procedure you mark as "pure" will never have to be overridden with one that isn't pure. Could be trivial for functions like "count()", but for other cases it might be a (very) difficult decision.
The fourth one might even be a show-stopper for including the feature. If the compiler needs to check that a procedure is really "pure", then it would need to put restrictions on each statement and expression used in that procedure. You would not be allowed to access any class fields, from the same class or from any other class. All expressions used should be pure as well. Any assignment statements should only modify local variables. If you declare variables in the procedure, their constructors should also be pure (no access to outside data and no side-effects elsewhere). It would be possible to have the compiler check those things, but it would put a major burden on the programmer. He would need to have "pure" in his mind everytime he writes a constructor for a class, because it might need to be called at some point somewhere in a "pure" procedure. He would need to mark all (or most) of his user-defined operators as "pure", unless I make "pure" the default or even a requirement for all binary (and unary?) operators. All these things would cause the programmer's code to be filled with things marked as "pure", just in case. Most programmers would probably just avoid "pure" entirely because it makes things too difficult.
So I'm unsure wether or not to include the feature. It could certainly be useful. But would it be worth the effort?
Another possibility is to use "pure" just as an attribute that informs the compiler about potential optimisations. But in that case someone could mark a procedure as "pure" while it does have side-effects.
At this time, I am still thinking about the feature. Feedback is welcome, as usual.
The idea is to introduce "pure" functions. Any procedure that is qualified as "pure" would guarantee to have no side effects and to have it's result only depend on the values of its parameters. The main purpose of this is to enable extra optimizations by the compiler, and to guarantee that some functions that do not need side-effects will not have them. So if you have some container class, its "count()" procedure (that returns the number of elements in the container) can be qualified as "pure" because it doesn't (and shouldn't) alter the state of the container, and because as long as the container is not modified, it will keep returning the same value over and over again. This implies that we consider the "this" pointer an implicit parameter for each non-static procedure, and that "pure" is a more restrictive version of the "const" qualifier for procedures. If you need a "pure" procedure that doesn't depend on its hidden "this" parameter, then you should also qualify it as "static".
Now the implications of this new feature:
- Because "pure" is actually a more restrictive version of "const", you can have a normal and a "pure" version of the same procedure, just like you can put a normal and a "const" procedure with the same parameters in a class.
- You can override a "const" procedure with a "pure" one.
- You can only override a "pure" procedure with a "pure" one.
- The compiler needs to check if a "pure" procedure really has no side-effects and if it only uses its parameters to calculate the result (!).
The third one could make things a bit more difficult than they are now. If you design a class that will be inherited from, you will have to be careful that any procedure you mark as "pure" will never have to be overridden with one that isn't pure. Could be trivial for functions like "count()", but for other cases it might be a (very) difficult decision.
The fourth one might even be a show-stopper for including the feature. If the compiler needs to check that a procedure is really "pure", then it would need to put restrictions on each statement and expression used in that procedure. You would not be allowed to access any class fields, from the same class or from any other class. All expressions used should be pure as well. Any assignment statements should only modify local variables. If you declare variables in the procedure, their constructors should also be pure (no access to outside data and no side-effects elsewhere). It would be possible to have the compiler check those things, but it would put a major burden on the programmer. He would need to have "pure" in his mind everytime he writes a constructor for a class, because it might need to be called at some point somewhere in a "pure" procedure. He would need to mark all (or most) of his user-defined operators as "pure", unless I make "pure" the default or even a requirement for all binary (and unary?) operators. All these things would cause the programmer's code to be filled with things marked as "pure", just in case. Most programmers would probably just avoid "pure" entirely because it makes things too difficult.
So I'm unsure wether or not to include the feature. It could certainly be useful. But would it be worth the effort?
Another possibility is to use "pure" just as an attribute that informs the compiler about potential optimisations. But in that case someone could mark a procedure as "pure" while it does have side-effects.
At this time, I am still thinking about the feature. Feedback is welcome, as usual.
Monday, February 02, 2009
Compiler development update
So here's an update on how things went after my previous post ("Compiler development roadmap").
After the "typerefactor" branch was more or less finished, I tried to merge it into (a copy of) the "llvm" branch. But the merge didn't work, so I decided to do things in a different way.
I created a completely new branch called "llvm-new", starting from the code of the "typerefactor" branch. Then I added the LLVM 2.4 sources to it, using the CMake build system from LLVM itself. To get the thing completely compiled and working I had to update to a SVN version of the LLVM code, though. And then I started writing my LLVM back end from scratch.
Wanting to avoid the mistakes of the first "llvm" branch, I started immediately on the implementation of a complete mechanism to manage types and to do type conversions. This means dealing with real class types, that are passed as a (this-)pointer, with primitive types that are passed as a value directly, passing parameters by reference or by value, passing values to "inout" parameters, referencing/dereferencing, indirectly returning values (using a extra hidden function parameter), etc... Eventually this implementation turned out pretty good, so it's no longer a PITA to write back end code like passing a value to a parameter.
Now I'm working on the implementation of codegen for all types (classes actually), expressions and statements. For most things implementation is easy, because I can look at the old implementation in the "llvm" branch and port that code to the new way of doing things. This new way is not just the typepassing/-conversion infrastructure; I've also changed the way I emit instructions. Previously I created the LLVM IR directly, but now I use the IRBuilder utility class from LLVM. And I now have a utility class that makes it a lot easier to emit basic blocks and branches to them.
So things are going forward slowly. I think that my "llvm-new" branch now has about 75% of the codegen functionality that was in the "llvm" branch. But things are still primitive; the compiler spits out lot of debug output followed by LLVM IR. You can try it if you want to, the code is available on the Launchpad project page:
https://code.launchpad.net/hyper
So most of my time is currently spent on the "llvm-new" branch. But that doesn't mean that the other branches are dead, however. The "typerefactor" branch now acts as a merge bridge between "llvm-new" and "main" (the 'official' front end branch). All front end related changes in "llvm-new" are regularly merged into "typerefactor". And those improvements are then merged into the "main" branch. The reason for doing things this way is that I like to keep the differences between "llvm-new" and "typerefactor" (in their front end code, at least) as small as possible. And now I can do some more or less invasive changes in the "main" branch without worrying about breaking the back end code.
As you might have noticed, progress has been going rather slowly these days. That's because I found a job as a software developer, using .NET (C# and VB). But at home it's still only Linux (Gentoo) for me. I'd prefer not to depend on Microsoft personally, but I need something to pay the bills of course.
After the "typerefactor" branch was more or less finished, I tried to merge it into (a copy of) the "llvm" branch. But the merge didn't work, so I decided to do things in a different way.
I created a completely new branch called "llvm-new", starting from the code of the "typerefactor" branch. Then I added the LLVM 2.4 sources to it, using the CMake build system from LLVM itself. To get the thing completely compiled and working I had to update to a SVN version of the LLVM code, though. And then I started writing my LLVM back end from scratch.
Wanting to avoid the mistakes of the first "llvm" branch, I started immediately on the implementation of a complete mechanism to manage types and to do type conversions. This means dealing with real class types, that are passed as a (this-)pointer, with primitive types that are passed as a value directly, passing parameters by reference or by value, passing values to "inout" parameters, referencing/dereferencing, indirectly returning values (using a extra hidden function parameter), etc... Eventually this implementation turned out pretty good, so it's no longer a PITA to write back end code like passing a value to a parameter.
Now I'm working on the implementation of codegen for all types (classes actually), expressions and statements. For most things implementation is easy, because I can look at the old implementation in the "llvm" branch and port that code to the new way of doing things. This new way is not just the typepassing/-conversion infrastructure; I've also changed the way I emit instructions. Previously I created the LLVM IR directly, but now I use the IRBuilder utility class from LLVM. And I now have a utility class that makes it a lot easier to emit basic blocks and branches to them.
So things are going forward slowly. I think that my "llvm-new" branch now has about 75% of the codegen functionality that was in the "llvm" branch. But things are still primitive; the compiler spits out lot of debug output followed by LLVM IR. You can try it if you want to, the code is available on the Launchpad project page:
https://code.launchpad.net/hyper
So most of my time is currently spent on the "llvm-new" branch. But that doesn't mean that the other branches are dead, however. The "typerefactor" branch now acts as a merge bridge between "llvm-new" and "main" (the 'official' front end branch). All front end related changes in "llvm-new" are regularly merged into "typerefactor". And those improvements are then merged into the "main" branch. The reason for doing things this way is that I like to keep the differences between "llvm-new" and "typerefactor" (in their front end code, at least) as small as possible. And now I can do some more or less invasive changes in the "main" branch without worrying about breaking the back end code.
As you might have noticed, progress has been going rather slowly these days. That's because I found a job as a software developer, using .NET (C# and VB). But at home it's still only Linux (Gentoo) for me. I'd prefer not to depend on Microsoft personally, but I need something to pay the bills of course.
Sunday, October 26, 2008
Compiler development roadmap
You probably already know that there are two important versions of the compiler in development: the "main" branch with only a front-end (called "trunk" on Launchpad), and the "llvm" branch with an experimental LLVM-based back-end. Their source code can be found on the Launchpad project page:
https://code.launchpad.net/hyper
That page contains another development branch as well, called "typerefactor". This branch is a heavily modified version of the main branch with the purpose of refactoring the handling of types and type conversions. I started the typerefactor branch because the code of the llvm branch has become a bit difficult and fragile; the typerefactor branch will improve the front-end part of the compiler so that developing the LLVM back-end will be much easier.
Another thing on my TO-DO list is the upgrade of the back-end to LLVM 2.4. This means that I will have to replace my custom CMake build system for LLVM by the official one. Yes, you read that correctly: LLVM now has an (experimental) CMake-based build system of its own. I posted my code for building LLVM with CMake on the LLVM mailing list quite a while ago, and now someone has used that code as a start for writing a real CMake build system for LLVM (mine was very Unix-oriented and was just enough for using LLVM with my compiler front-end).
So currently I'm planning to do the following:
Some things that will need to be done to the front-end:
https://code.launchpad.net/hyper
That page contains another development branch as well, called "typerefactor". This branch is a heavily modified version of the main branch with the purpose of refactoring the handling of types and type conversions. I started the typerefactor branch because the code of the llvm branch has become a bit difficult and fragile; the typerefactor branch will improve the front-end part of the compiler so that developing the LLVM back-end will be much easier.
Another thing on my TO-DO list is the upgrade of the back-end to LLVM 2.4. This means that I will have to replace my custom CMake build system for LLVM by the official one. Yes, you read that correctly: LLVM now has an (experimental) CMake-based build system of its own. I posted my code for building LLVM with CMake on the LLVM mailing list quite a while ago, and now someone has used that code as a start for writing a real CMake build system for LLVM (mine was very Unix-oriented and was just enough for using LLVM with my compiler front-end).
So currently I'm planning to do the following:
- Finish the typerefactor code.
- Create another branch, "llvm-experimental", based on the llvm branch, and merge the typerefactor code into it. It's possible that this will require some extra changes to the front-end code, and those will be merged into the typerefactor branch again.
- Upgrade the one of the llvm branches to LLVM 2.4. What branch I will use will depend on how long it takes to finish item 2 and on how difficult the build system transition will be.
- When item 2 is done, merge the typerefactor branch into the main branch.
- When items 2 and 3 are done, merge the llvm-experimental branch into the llvm branch.
- Implement codegen for everything the front-end currently supports (in the llvm branch).
- Merge the llvm branch into the main branch.
Some things that will need to be done to the front-end:
- Add support for 'references' (or restricted pointers)
- Create a Unicode interface for the "string" type (no more random access)
- Change the handling of operator overloading for binary operators (no more global list)
Subscribe to:
Posts (Atom)