About four and a half years ago I wrote a post titled The only design pattern is small solutions. I've recently run into the problem of how small and good intended solutions grows to massive complex systems which devour everything around them. It now reached a point where the code we understand and can work with is in minority.
You know how good ideas need to reach a critical mass before they spread and become popular? Well, these massive complex systems are the black hole equivalent of that -- they absorb everything around them, making themselves larger and more complex with every idea that come in contact with it. They are good ideas that grew out of proportions into black holes of never-ending complexity.
Generally, we prefer to use small to-the-point solutions. We like things that are easy to understand and get our job done. But we also like to show that we're good at what we're doing. Of course, the size of a system reflects the size of the solved problem, but lately I'm thinking more and more that the size of the system also reflects the size of the designer's ego. Great egos write complex software.
I've had the luck of working with really great people who made me realize what it means to write great software with a great team. Maybe at some point I'll get to experience both at the same time, or even one of them over a longer period of time. Anyway, this experience shaped me in really positive ways, and it's only lately that I realized how these two things go hand in hand. Being humble is the opposite of having a big ego -- simple is the opposite of complex. Humble people write simple software.
Monday, December 15, 2014
Monday, December 1, 2014
Constraint Satisfaction Problems
This post is brain dump of my recent dives into CSP -- don't consider any of this to be anything but ramblings by someone who knows approximately nothing about what he's talking about.
To begin with, CSP is likely a programming paradigm very different from the ones you already heard of. If functional and object-oriented programming is what you think of when you hear programming paradigm then CSP is like a magic bottle of golden fairy dust in that it makes everything you heard and learnt about programming seem like monkey patching a steam engine. CSP is that different. On the other hand, if you have done some linear programming, logic programming, or implemented type inferencing, then you'll find yourself right at home.
A CSP program is an set (unordered collection) of constraints (assertions), example:
X > 1
Y > X
X * Y = 21
That it, that's the entire program. To figure out what it does, all you need to do is recall some basic math, because CSP (when operating on integers like this) is essentially the same thing as solving mathematical equations numerically. This means that executing a CSP means to solve the asserted equations. This in turn means that implementing a CSP program means to figure out what equations that should hold on the solution (the answer of the program) and write down those equations. As in math, the ordered of the assertions is irrelevant, so you can organize your program in the way that seems local to you.
This is all nice and all, but how is a CSP executed? Well, this when it's get's complicated. Solving the equations/constraints that constitute the CSP is a hard problem, really hard problem. The reason for this might not be clear from the above example, but replace 21 with a much larger number (e.g., the product of two large prime numbers) and it should be clear why this is a hard problem.
So if it's so hard to execute a CSP why bother writing CSP programs? Well, not all programs are hard to execute and this is important to know. Some programs will take several life-times of the universe to execute while other programs will take a split second to execute. What make the difference is the size of the domain of the variables and the number of variables.
The domain of a variable is the set of it's possible values. In the program above, X has the domain {2, 3, 4, 5, 6, 7, 8, 9, 10, 11} and Y has the domain {3, 4, 5, 6, 7, 8, 9, 10, 11}. Now you might say "well, clearly X nor Y can be 11!", and you would of course be right! What you have done is something called constraint propagation, which is what makes CSP programs with many variables with large domains possible to execute before the universe is rebooted.
What do I mean with this? Let's take a step back and look at what's really given in the above program. The only thing we actually know by looking at the assertions one at the time is the following: the domain of X is {2, 3, 4, ...} and the domain of Y is {...}. That is the domains of X and Y are both infinitely large. How long time would it take to execute a program where the domains of any variable is infinitely large? Infinitely long, of course. This is bad.
What to do? Constraint propagation to the rescue! What this means is that we use our knowledge of how the constrains work (less than, multiplication, and equals, in this case) to infer more knowledge. For example, if Y > X and X > 1, then Y > 2. Pretty simple. Continuing further we have that X * Y = 21, what does this tell us? Well if we know that X and Y are greater than zero (which they are) then we can infer that X <= 21 and Y <= 21. Let's again take a step back and consider what we just have done -- we started with two infinite domains (that is, a program that would take infinitely long to execute) and through a few simple step we're down at two domains of size 19 and 18 respectively, which can be executed fast on any machine you can find (including that old Atari you keep in your storage room). Constraint propagation is that big of a deal.
Considering what we just did, you might ask what if there is no (good) propagator for a certain constraint? This is a very good question, and there is a lot of research going on (and have been going on for a long time) in finding good propagators for all kinds of constraints. Unfortunately, it's likely that there will always be CSP programs that execute slow (the life-time-of-the-universe kind of slow).
Luckily (in some sense) this is not something that is specific for CSP programs, but programs in general -- it just becomes obvious when doing CSP programming as the paradigm open doors that previously closed to you if you came from imperative/object-oriented or functional programming.
CSP is rich in research and diving into any part of it will lead you to diverse research areas. If that doesn't make you interested then what about the fact that Google, Microsoft, and many more is doing it and has identified it as one of the most important areas for the the future.
It's hard to make predictions especially about the future, but considering the amount of research that's is going on in this area and the fact that industry giants work on it as well, it's not too far fetched to imagine CSP to be a big part of programming in a decade or two. Or are everyone just doing it because it "fun and challenging"? No, I don't think so either.
(Don't worry, there will still be room for C/JavaScript programmers in 2034. It'll be hard to implement an operating system using CSP or the CSP solver itself...)
To begin with, CSP is likely a programming paradigm very different from the ones you already heard of. If functional and object-oriented programming is what you think of when you hear programming paradigm then CSP is like a magic bottle of golden fairy dust in that it makes everything you heard and learnt about programming seem like monkey patching a steam engine. CSP is that different. On the other hand, if you have done some linear programming, logic programming, or implemented type inferencing, then you'll find yourself right at home.
A CSP program is an set (unordered collection) of constraints (assertions), example:
X > 1
Y > X
X * Y = 21
That it, that's the entire program. To figure out what it does, all you need to do is recall some basic math, because CSP (when operating on integers like this) is essentially the same thing as solving mathematical equations numerically. This means that executing a CSP means to solve the asserted equations. This in turn means that implementing a CSP program means to figure out what equations that should hold on the solution (the answer of the program) and write down those equations. As in math, the ordered of the assertions is irrelevant, so you can organize your program in the way that seems local to you.
This is all nice and all, but how is a CSP executed? Well, this when it's get's complicated. Solving the equations/constraints that constitute the CSP is a hard problem, really hard problem. The reason for this might not be clear from the above example, but replace 21 with a much larger number (e.g., the product of two large prime numbers) and it should be clear why this is a hard problem.
So if it's so hard to execute a CSP why bother writing CSP programs? Well, not all programs are hard to execute and this is important to know. Some programs will take several life-times of the universe to execute while other programs will take a split second to execute. What make the difference is the size of the domain of the variables and the number of variables.
The domain of a variable is the set of it's possible values. In the program above, X has the domain {2, 3, 4, 5, 6, 7, 8, 9, 10, 11} and Y has the domain {3, 4, 5, 6, 7, 8, 9, 10, 11}. Now you might say "well, clearly X nor Y can be 11!", and you would of course be right! What you have done is something called constraint propagation, which is what makes CSP programs with many variables with large domains possible to execute before the universe is rebooted.
What do I mean with this? Let's take a step back and look at what's really given in the above program. The only thing we actually know by looking at the assertions one at the time is the following: the domain of X is {2, 3, 4, ...} and the domain of Y is {...}. That is the domains of X and Y are both infinitely large. How long time would it take to execute a program where the domains of any variable is infinitely large? Infinitely long, of course. This is bad.
What to do? Constraint propagation to the rescue! What this means is that we use our knowledge of how the constrains work (less than, multiplication, and equals, in this case) to infer more knowledge. For example, if Y > X and X > 1, then Y > 2. Pretty simple. Continuing further we have that X * Y = 21, what does this tell us? Well if we know that X and Y are greater than zero (which they are) then we can infer that X <= 21 and Y <= 21. Let's again take a step back and consider what we just have done -- we started with two infinite domains (that is, a program that would take infinitely long to execute) and through a few simple step we're down at two domains of size 19 and 18 respectively, which can be executed fast on any machine you can find (including that old Atari you keep in your storage room). Constraint propagation is that big of a deal.
Considering what we just did, you might ask what if there is no (good) propagator for a certain constraint? This is a very good question, and there is a lot of research going on (and have been going on for a long time) in finding good propagators for all kinds of constraints. Unfortunately, it's likely that there will always be CSP programs that execute slow (the life-time-of-the-universe kind of slow).
Luckily (in some sense) this is not something that is specific for CSP programs, but programs in general -- it just becomes obvious when doing CSP programming as the paradigm open doors that previously closed to you if you came from imperative/object-oriented or functional programming.
CSP is rich in research and diving into any part of it will lead you to diverse research areas. If that doesn't make you interested then what about the fact that Google, Microsoft, and many more is doing it and has identified it as one of the most important areas for the the future.
It's hard to make predictions especially about the future, but considering the amount of research that's is going on in this area and the fact that industry giants work on it as well, it's not too far fetched to imagine CSP to be a big part of programming in a decade or two. Or are everyone just doing it because it "fun and challenging"? No, I don't think so either.
(Don't worry, there will still be room for C/JavaScript programmers in 2034. It'll be hard to implement an operating system using CSP or the CSP solver itself...)
Sunday, September 14, 2014
Getting more testing done with less effort
It's been a while since I posted here -- but don't worry I haven't been lazy, I just haven't posted what I've done. :) Anyway, the last few days I've been thinking about a new way (to the best of my knowledge and research) to do unit testing that is inspired by Design by Contract.
What is a unit test? For me, a unit test is a small example that illustrates how to use a software unit (function, class, etc). This is good, because examples is a good way to learn how to use something. In fact, looking at examples is a natural way to learn how to do something.
There is a bad side to this though, and that is that examples can't show the general idea that a test is trying to verify. For instance, imagine that you have a class that implements the data structure stack. The class has a push, a pop, and a size method, which does the expected thing.
A test for the pop method, would probably initialize the stack with some predefine content, pop a few values from it, and verify that they are the expected values. (Alternatively, the test could setup the state of stack though a sequence of calls to push -- my point here is still valid).
What such test fails to capture is what pop expects the stack to look like when it's invoked. It's just shows one instance of all possible stacks that pop can operate on. In fact, pop can operate on every possible stack except the empty stack, but examples may or may not communicate this clearly.
And this is precisely what I've been toying with lately: writing tests where the setup code is replaced with a condition that must be true for the test to be valid to execute (a.k.a precondition). Let's take an example of this to illustrate the point. Below are two simple tests (written in a hypothetical version of Protest which supports the idea I'm describing) on a stack object.
suite("stack test") {
Stack s;
test("push test") {
int before = s.size();
s.push(0);
postcond(s.size() == before + 1);
}
test("pop test") {
precond(s.size() > 0); // pop can't operate on the empty stack
int before = s.size();
s.pop();
postcond(s.size() == before + 1);
}
}
These two tests are executed by a framework which invokes one test case after another on the same instance of Stack. In this example, that means that push test will be the first test executes because pop test's precondition isn't fulfilled (the stack is empty). When this test is finished, the framework picks another test that can be executed, which means either push test again or pop test (since the stack is not empty anymore). If the framework decides to execute pop test, the stack will be empty again, thus the only test case that can be executed next is push test, and so on.
So, why do you get more testing done with less effort by writing test-cases in this way? Well, for several reasons:
Right now, the biggest hurdle I've run into is how to express the natural recursive-ness of certain cuts. For example, if you push a value X to a stack you'll get X back when you pop the stack as long as you push and pop the same number of times between the push and the pop of X.
What is a unit test? For me, a unit test is a small example that illustrates how to use a software unit (function, class, etc). This is good, because examples is a good way to learn how to use something. In fact, looking at examples is a natural way to learn how to do something.There is a bad side to this though, and that is that examples can't show the general idea that a test is trying to verify. For instance, imagine that you have a class that implements the data structure stack. The class has a push, a pop, and a size method, which does the expected thing.
A test for the pop method, would probably initialize the stack with some predefine content, pop a few values from it, and verify that they are the expected values. (Alternatively, the test could setup the state of stack though a sequence of calls to push -- my point here is still valid).
What such test fails to capture is what pop expects the stack to look like when it's invoked. It's just shows one instance of all possible stacks that pop can operate on. In fact, pop can operate on every possible stack except the empty stack, but examples may or may not communicate this clearly.
And this is precisely what I've been toying with lately: writing tests where the setup code is replaced with a condition that must be true for the test to be valid to execute (a.k.a precondition). Let's take an example of this to illustrate the point. Below are two simple tests (written in a hypothetical version of Protest which supports the idea I'm describing) on a stack object.
suite("stack test") {
Stack s;
test("push test") {
int before = s.size();
s.push(0);
postcond(s.size() == before + 1);
}
test("pop test") {
precond(s.size() > 0); // pop can't operate on the empty stack
int before = s.size();
s.pop();
postcond(s.size() == before + 1);
}
}
These two tests are executed by a framework which invokes one test case after another on the same instance of Stack. In this example, that means that push test will be the first test executes because pop test's precondition isn't fulfilled (the stack is empty). When this test is finished, the framework picks another test that can be executed, which means either push test again or pop test (since the stack is not empty anymore). If the framework decides to execute pop test, the stack will be empty again, thus the only test case that can be executed next is push test, and so on.
So, why do you get more testing done with less effort by writing test-cases in this way? Well, for several reasons:
- Less development time is spent on setting up the cut (it takes less time to write the preconditions than writing the code that setups the cut such that it fulfills them). As a side effect, tests become shorter, more declarative, and easier to read.
- A single test verifies that several executions paths that sets the cut up in a state the fulfills certain conditions results in a cut that passes the test. This makes it easier to verify code with messy internal state.
- In addition to verifying behavior, a test describes the relationship between the method of the cut's interface. For example, how Stack::pop relates to Stack::size.
- Tests depend on other tests. This is a big no-no and doing this intentionally might fly in the face of intuition.
- The initial state of the cut is less concrete as there is no example code to follow.
- Some classes (e.g., builders) can't naturally be used repetitively in a meaningful way (when an object is built, the builder is done).
Right now, the biggest hurdle I've run into is how to express the natural recursive-ness of certain cuts. For example, if you push a value X to a stack you'll get X back when you pop the stack as long as you push and pop the same number of times between the push and the pop of X.
Tuesday, March 25, 2014
What are phi nodes?
I've been working on a project that I call veria for around two months now, and yesterday it compiled the first piece of Java code to native x64 code through the veria jit compiler. The largest and most complex part of veria is implemented; what remains is mostly the backend of the jit compiler. Most of the backend is trivial stuff -- two hash lookups, a call to a libjit function, and a hash insertion -- however, the phi instruction (the veria instruction set is register-based single static assignment) is somewhat complicated as libjit uses a somewhat different model. Let's take an example; first an instruction set with phi nodes (similar to veria):
JEQ R0, R1, L1
R2 = 10
JMP L2
L1:
R3 = 20
L2:
R4 = PHI(R2, R3)
Second, the same function in an instruction set similar to libjit's:
JEQ R0, R1, L1
R2 = 10
MEM[0] = R2
JMP L2
L1:
R3 = 20
MEM[0] = R2
L2:
R4 = MEM[0]
Looking carefully at these two instruction sequences we see that the PHI instruction is replaced with R4 = MEM[0] (reading from the memory) and the assignments to R2 and R3 are followed by a write to MEM[0]. The instruction sequence without the PHI instruction is very close to how code running on an actual computer, while the first has this magic PHI instruction that can't really be executed... but, assuming R4 = PHI(R2, R3) is just another spelling of R4 = MEM[0], all that is missing from the first sequence to be executed are the writes to memory.
Let's spell those write instructions as PREPHI and give it and it's matching PHI instruction a unique number. Here's the result with comments saying the alternative spelling:
JEQ R0, R1, L1
R2 = 10
PREPHI R2, 0 // MEM[0] = R2
JMP L2
L1:
R3 = 20
PREPHI R3, 0 // MEM[0] = R3
L2:
R4 = PHI(R2, R3, 0) // R4 = MEM[0]
So what we got here is an instruction set that is single static assignments but that can be mapped to instructions set such as libjit's through a single pass. And it also de-mystifies the phi instruction. The cost is that any phi instruction inserted by the optimizer needs a matching prephi instructions.
JEQ R0, R1, L1
R2 = 10
JMP L2
L1:
R3 = 20
L2:
R4 = PHI(R2, R3)
Second, the same function in an instruction set similar to libjit's:
JEQ R0, R1, L1
R2 = 10
MEM[0] = R2
JMP L2
L1:
R3 = 20
MEM[0] = R2
L2:
R4 = MEM[0]
Looking carefully at these two instruction sequences we see that the PHI instruction is replaced with R4 = MEM[0] (reading from the memory) and the assignments to R2 and R3 are followed by a write to MEM[0]. The instruction sequence without the PHI instruction is very close to how code running on an actual computer, while the first has this magic PHI instruction that can't really be executed... but, assuming R4 = PHI(R2, R3) is just another spelling of R4 = MEM[0], all that is missing from the first sequence to be executed are the writes to memory.
Let's spell those write instructions as PREPHI and give it and it's matching PHI instruction a unique number. Here's the result with comments saying the alternative spelling:
JEQ R0, R1, L1
R2 = 10
PREPHI R2, 0 // MEM[0] = R2
JMP L2
L1:
R3 = 20
PREPHI R3, 0 // MEM[0] = R3
L2:
R4 = PHI(R2, R3, 0) // R4 = MEM[0]
So what we got here is an instruction set that is single static assignments but that can be mapped to instructions set such as libjit's through a single pass. And it also de-mystifies the phi instruction. The cost is that any phi instruction inserted by the optimizer needs a matching prephi instructions.
Sunday, January 12, 2014
How to design interfaces
My definition of the word interface is point of contact for a piece of functionality. Designing good interfaces to any piece of functionality is hard -- that's at least my experience. I've designed several interfaces, but very few of those make me particularly proud of my programming skills. The problems I frequently see are:
Consider a piece of code that parses a file where each line holds either a number or a string of text. How should the interface to this code look? Some alternatives are:
With small pieces of code like the example above, it might not be clear why thinking about modeling is important. But consider designing an API for a large and complicated library. What are the concepts that the client need to understand? What are the actions it can perform? What side-effects are expected and when should they be visible?
At work I'm developing an application that just-in-time compiles a proprietary language into native x64/x86 code. We've had some bugs related to when variables are updated. This probably sounds like trivial things to get right, but when you get deep down in the details these things easily slip through because your brain are occupied thinking about other aspects of the problem. These bugs could have been avoided if there was a layer that took care of these details. That is, a layer that models these inherent properties of the language and provides an interface that helps the developers to think in terms of the model.
This brings me to the other aspect of modeling -- as tool for communication.
Given any piece of code -- two programmers will think about it slightly different. Furthermore, the larger the code, the more likely that two programmers will understand it more different. In other words, it will be harder for them to understand each other when talking about the code. However, if the code is partitioned into smaller parts and each part models (not only implements) some logical sub functionality, it will be easier to understand it.
Note that the important word in the above paragraph is not implements, it's models. The implementation of an interface is irrelevant for understanding what a client does if the interface models the solution properly.
Think about opening and reading files. In most languages it's as straight-forward to implement it as it is to say "think about opening and reading files". The interfaces models the way we think about files. Great! That means we don't need to understand what open does in order to understand what the code using open does.
This means that one easy way to get an interface to be easy to use is design it by mimicking something other people already understand (e.g., a parser, a visitor, a file). This is the alternative I've taken the last few times I've designed an interface -- trying to find a suitable analogy and use that as model.
- too specific (hard-wired to a particular client),
- too generic (hard to use for simple problems),
- not extensible (adding functionality requires changing the interface), and
- simply to darn hard to understand.
Consider a piece of code that parses a file where each line holds either a number or a string of text. How should the interface to this code look? Some alternatives are:
- bool str_to_int_or_str(const char* content, int* int_value, const char** text);
- OneOf<const char*, int> str_to_int_or_str(const char* content);
- void read_line(const char* content, void (int_func*)(int), void (txt_func*)(const char*));
- void parse(const char* content, Visitor* visitor);
- template <class C, class V> parse(C content, V visitor);
With small pieces of code like the example above, it might not be clear why thinking about modeling is important. But consider designing an API for a large and complicated library. What are the concepts that the client need to understand? What are the actions it can perform? What side-effects are expected and when should they be visible?
At work I'm developing an application that just-in-time compiles a proprietary language into native x64/x86 code. We've had some bugs related to when variables are updated. This probably sounds like trivial things to get right, but when you get deep down in the details these things easily slip through because your brain are occupied thinking about other aspects of the problem. These bugs could have been avoided if there was a layer that took care of these details. That is, a layer that models these inherent properties of the language and provides an interface that helps the developers to think in terms of the model.
This brings me to the other aspect of modeling -- as tool for communication.
Given any piece of code -- two programmers will think about it slightly different. Furthermore, the larger the code, the more likely that two programmers will understand it more different. In other words, it will be harder for them to understand each other when talking about the code. However, if the code is partitioned into smaller parts and each part models (not only implements) some logical sub functionality, it will be easier to understand it.
Note that the important word in the above paragraph is not implements, it's models. The implementation of an interface is irrelevant for understanding what a client does if the interface models the solution properly.
Think about opening and reading files. In most languages it's as straight-forward to implement it as it is to say "think about opening and reading files". The interfaces models the way we think about files. Great! That means we don't need to understand what open does in order to understand what the code using open does.
This means that one easy way to get an interface to be easy to use is design it by mimicking something other people already understand (e.g., a parser, a visitor, a file). This is the alternative I've taken the last few times I've designed an interface -- trying to find a suitable analogy and use that as model.
Thursday, October 24, 2013
asmf -- a portable, low-level, jit assembler
So I've been busy lately with all kinds of big and small things, related and not related to programming. Recently I've been working on a jit assembler that I call asmf. You can find it here.
Why do I call it asmf, that not such a nice sounding name now is it? Well, it's an assembler (therefore the asm-part) and it's take inspiration from printf (therefore that f-part). Now you must be thinking "really? printf? are you seriously parsing strings to emit binary code?". Well yes, and no.
As you surely like code as much as I do, let's take an example before continuing:
// Use the 'r' wildcard (meaning rax, rbx, etc) in an asmf emit statement.
void clear_reg(unsigned char*& dstbuf, unsigned dst) {
asmf("mov %r, 0", dst, dstbuf);
}
Why do I call it asmf, that not such a nice sounding name now is it? Well, it's an assembler (therefore the asm-part) and it's take inspiration from printf (therefore that f-part). Now you must be thinking "really? printf? are you seriously parsing strings to emit binary code?". Well yes, and no.
As you surely like code as much as I do, let's take an example before continuing:
// Use the 'r' wildcard (meaning rax, rbx, etc) in an asmf emit statement.
void clear_reg(unsigned char*& dstbuf, unsigned dst) {
asmf("mov %r, 0", dst, dstbuf);
}
I'm sure you can see the relation to printf? This code is passed to the asmf preprocessor, which outputs the following code:
// mov %r, 0
void __asmf_mov__r__0(unsigned long op0, unsigned char*& bufp) {
unsigned char* buf = bufp;
buf[0] = 0x48 | ((op0 & 0x08) >> 3);
buf[1] = 0xc7 | (op0 & 0x07);
buf[2] = 0xc0;
buf[3] = 0x00;
buf[4] = 0x00;
buf[5] = 0x00;
buf[6] = 0x00;
bufp += 7;
}
void clear_reg(char* codebuf, unsigned dst) {
__asmf_mov__r__0(dst, dstbuf);
}
That is, the call to the asmf function is replaced to a call to a generated function, and the string literal is dropped. It's a quite simple preprocessor in this regard.
But how does it come up with the newly generated function? This is the core of asmf and this is why I even bother publishing yet another jit assembler -- there are at least 4-5 tools/libraries out there already that does the above. But asmf is different to all those tools, and if you run sloccount on it you'll understand that it is different. In less than 500 lines of code you have a jit assembler for x64 -- and ARM, and Sparc, and your OpenRISC, etc. (Well, in theory at least, as I haven't tried this yet).
How? By being lazy. I knew that I would never be capable of writing a full jit assembler, and I knew that I would never have the patience to reverse-engineer the output of the assembler for all instructions. That why I wrote asmf to do this for me. Yes, asmf is not only a jit assembler -- it's a jit assembler generator and an instruction encoding reverse-engineer:er. This is why I say that asmf should work on every/most platform.
The major part of asmf is implemented, there are some thing related to usability (error messages, more command line switches, documentation) etc. The testing is unfortunately very x64 centered right now, and that has to fixed when ported to new platforms.
Saturday, September 14, 2013
Pythlog, assignments, and equations
Pythlog is a language I'm working on from time to time. It's a dialect of Python that incorporates constraint logic programming. So far it supports integers, list, tuples, strings, and user defined classes. There are a lot things still missing, but it already capable of some pretty cool stuff:
def fac(n):
assert n >= 0
if n == 0:
return 1
else:
return fac(n - 1) * n
print(fac(7)) # Prints 5040
fac(w) = 5040
print(w) # Prints 7
In this example we define the factorial function the a pretty straight-forward recursive manner. Then we call it to calculate the factorial of 7. The second to last line might appear a bit unorthodox though. What's going on here?
As said, Pythlog is a logic programming language. Such languages have a few features that set the aside from traditional imperative languages. On such feature is so call free variable. The code above is equivalent to:
w = free
assert fac(w) == 5040
print(w)
where w is a free variable which is passed to fac. By asserting that the return value must be equal to 5040, the constraint satisfaction framework kicks in and solves w to 7.
I recently introduced the shorthand syntax fac(w) = 5040 for this. I'm not fully happy with it yet, because there are some non-obvious behaviors. I'm pretty sure there will be some changes in this area. For now though, it make the language at least look nicer, soon I hope it will also feel nicer.
def fac(n):
assert n >= 0
if n == 0:
return 1
else:
return fac(n - 1) * n
print(fac(7)) # Prints 5040
fac(w) = 5040
print(w) # Prints 7
In this example we define the factorial function the a pretty straight-forward recursive manner. Then we call it to calculate the factorial of 7. The second to last line might appear a bit unorthodox though. What's going on here?
As said, Pythlog is a logic programming language. Such languages have a few features that set the aside from traditional imperative languages. On such feature is so call free variable. The code above is equivalent to:
w = free
assert fac(w) == 5040
print(w)
where w is a free variable which is passed to fac. By asserting that the return value must be equal to 5040, the constraint satisfaction framework kicks in and solves w to 7.
I recently introduced the shorthand syntax fac(w) = 5040 for this. I'm not fully happy with it yet, because there are some non-obvious behaviors. I'm pretty sure there will be some changes in this area. For now though, it make the language at least look nicer, soon I hope it will also feel nicer.
Tuesday, May 28, 2013
Pretty ugly hacks
Recently I've (re-)discovered the more hacky kind of programming. It started after that I implemented my first bloom-filter. Somehow I ended up reading about all kinds of bit twiddling hacks, and finally I found myself in the realm of xor double linked lists.
Doubled linked list is a data structure where each node in the list has two pointers; one to the next node, and one to the previous node. The size of each node is thus 3 pointers. An xor linked list has the same logical function, but a compress representation -- it only requires 2/3 of the size of a normal linked list. This is achieved by observing that the only way to reach a node in a double linked list is either from the back or from the front of the list. Thus, it's enough to store the xor-sum of the pointer to the next node and the previous node, since either of those pointers is known. Anyway, the linked Wikipedia article explains it much better.
Well, the neighboring country to xor-lists is Tagged Pointer-land. In Tagger Pointer it's ok to do all kinds of crazy things to pointers as long as you know what you're doing. For instance you can exploit that dynamically allocated memory on most systems are aligned to 16-bits, 32-bits, 64-bit or even 128-bits borders. What can this be used for? Distinguishing between native integer values and arbitrary-precision integers for instance, or for putting small data structures (e.g., short strings) in the "pointer" rather than having to dynamically allocating a few bytes of memory.
It's actually pretty useful stuff, although -- as the title says -- pretty ugly. That is, the pretty kind of ugly.
Doubled linked list is a data structure where each node in the list has two pointers; one to the next node, and one to the previous node. The size of each node is thus 3 pointers. An xor linked list has the same logical function, but a compress representation -- it only requires 2/3 of the size of a normal linked list. This is achieved by observing that the only way to reach a node in a double linked list is either from the back or from the front of the list. Thus, it's enough to store the xor-sum of the pointer to the next node and the previous node, since either of those pointers is known. Anyway, the linked Wikipedia article explains it much better.
Well, the neighboring country to xor-lists is Tagged Pointer-land. In Tagger Pointer it's ok to do all kinds of crazy things to pointers as long as you know what you're doing. For instance you can exploit that dynamically allocated memory on most systems are aligned to 16-bits, 32-bits, 64-bit or even 128-bits borders. What can this be used for? Distinguishing between native integer values and arbitrary-precision integers for instance, or for putting small data structures (e.g., short strings) in the "pointer" rather than having to dynamically allocating a few bytes of memory.
It's actually pretty useful stuff, although -- as the title says -- pretty ugly. That is, the pretty kind of ugly.
Sunday, May 26, 2013
Features are social processes
For a while now I've been thinking about how human languages evolve compared to how computer languages are designed and how that relates to the features of the respective languages. In this post I will ramble at bit about how the meaning of software related terms is defined. I'll also discuss hard and soft features in programming languages and how the community surrounding the language affects, and is affected by, those features.
This is mostly a bunch of ideas and observations that I'm trying to put into words to 1) make me understand them better, and 2) make sure I don't forget them. If you expect a scientific survey, then I'm sorry to disappoint you. Maybe, though, you'll find food for your own thought and ideas.
What's a language?
As I see it, languages (be it the human or programming kind) are mutual agreement between the communicating parts of what a statement means. If everyone have a different opinion of what the following statement means, then it effectively doesn't have any meaning at all since we can't use it to communicate with anyone:You need wood from a forest to create a fire.Fire fire = new Fire(forest.getWood());For example, the common breed of C compiler accepts a lot of code most C programmers won't. It's the users of the C language that defines the subset of allowed-by-the-compiler-C that is acceptable for us to use. In other words, the C standard can say all it wants; its the C users who in the end defines the (practical) C language. It a bit like if physics would say "Our universe have 11 dimensions. Go use all of them!", but all known users of the universe are three-dimensional beings, thus, the accepted subset of the universe is three-dimensional. Sorry to break it to you, physics, but that's how it is.
Language features are all about what the community around the language make of the language. In a way, language features are just as much a technical aspect of the language as a social aspect of it. Example: is a language feature that's not accepted by the community really a feature, or is it just useless language complexity? More extreme example: a language without users but with extremely powerful features; effectively, does that language have any features at all?
I would also say that anyone aiming to develop a successful programming language (without the backing of a *caugh* Sun huge *caugh* Microsoft corporation) needs to have equally good eye for the technical aspect as well as the social aspect. (S)he needs to understand the social processes involved for getting a community of users who agree (hopefully with the language designer) on how the language should be used. (I think python is good example of such community, by the way).
What about software?
Developing software is also a social process. For example, you get requirements from your customer, you discuss the requirements in order to understand them, and you implement them. Implementing requirement are also a social process: you design the code by discussing it with your colleagues. And what words do you use for doing that?You use words like object, generic, sort, inheritance, stack, tree, operation, method, message, reuse, client, algorithm, allocation, port, framework, mapping, service, channel, process, decoupled, assumption, resource, provider, input, interface... I could go on forever, but the point is that none of these words really mean anything if we humans don't agree on what they mean. The computer, framework, or programming language has no opinion on what "decouple the client's mapping algorithm from the port allocation" means, but programmers do. It's important it means that same to all programmers involved.
Soft and hard
How does this relate to programming language features? I think there two different kinds of features: hard features that was (deliberately) designed into the language, and soft features that are concepts and idioms that have evolved from using the language.Hard features are concrete. You can make a list of hard features by reading the language specification. Soft features, on the other hand, are not. They are embedded in the community and to enumerate them you need to vibe with it for a while. Hard features are taught in classes and in books; soft features are learned by hacking, hacking, living and breathing, and some more hacking.
Example: C++ templates. Originally intended to provide better type-safety when writing generic code, like std::vector. The C++ community has then discovered that templates can be used for much, much more (like Boost.Spirit). There are a lot of template code written to implement various kinds of abstract features, e.g., compile-time if, compile-time strings, domain specific languages, etc. The hard feature is "write type-safe generic code". The soft features are "compile-time if", "embedded DSL", and even "it's hard, but you can evaluate everything at compile-time".
The D language took these soft features of C++ templates (e.g., compile-time if, embedded DSL) and integrated them into the core language. Thus, enabled more programmers to use them, because of easier syntax, error messages, compiler support, documentation, etc.
So when a C++ programmer talks about enabling or disabling some piece of code (s)he needs to think about some abstract concept like the enable-if template, while a D programming just thinks "static if". In fact, I don't think the D programmer even thinks "static if" because it's so natural to them, just as the more common "dynamic if" is so natural to all of us. The D programmer probably thinks in entirely other abstract concepts because his/her mind is free from the horrible details of C++ templates meta-programming.
You may argue that our mind is very good at abstracting and that this isn't a problem in practice, but I don't think that's true at all. Example: very few C++ programmer have every done something like an template computing the sinus of an angle, so when they're told to optimize a piece of code doing trigonometry what they'll do is to use some kind of table look-up. A D programmer, on the other hand, will simply slap together a sinus function that can be evaluated statically by the compiler because compile-time evaluation is nothing magic to her/him. (In fact, in D 2.0 match function will automatically be evaluated at compile-time if their arguments are constants).
What I'm saying here is that compile-time evaluation is a (hard) language feature of D but not of C++ (where it is an soft feature). Sure, you can in theory do compile-time evaluation of everything you need in C++ (templates are Turing complete), but not in practice because it's so hard that you actively avoid it. Thus, in most programmers conscious mind, C++ does not have compile-time evaluation. Similarly, you can do object-oriented programming in C, but you probably don't because it's hard and littered with horrible details. Thus, C is in most programmers mind not a object-oriented language. It's possible to do structured programing in Commodore BASIC, but most of us don't think of it like that. Got my point yet? Good.
Ok, so what?
By now you are probably thinking "that's all very interesting, but how is this useful?". Well, I did say that this post was a rambling, didn't I? :)Seriously though, I don't really think any of this will make you a better software developer, but I think it could be useful if you are developing an tool and there's a community of users around it. Be sure to note what kinds of words the users uses, what features they ignore, what idioms they invent, etc. Integrate the words and idioms into the tool and it's documentation to make the experience for a new user of the application more consistent.
Friday, May 24, 2013
Small features distinguishes Protest
Protest is a unit testing framework for C++ that make testing fun, fast, and simple (see introduction). Recently, after using it on one of my own project, I've added a few more features to it.
First, I improved the compilation time for compiling a .cc file containing a test cases. This was embarrassingly bad earlier, but now I think its pretty good. The issue was that there were a lot functions defined in the header. I did a bit of preprocessing magic to avoid unnecessary function definition (in favor of function declarations) and that lower the compilation times dramatically.
Second, I made the check macro a bit more intelligent. Protest's check macro was already quite smart: it's capable of dealing with matchers, and splitting the left hand side and the right hand side in a comparison (e.g., foo != bar), which means that there is no need for several check macros as is common for C++ unit test frameworks.
Anyway, while working on some bit twiddling heavy code my tests tended to look something like this:
test("twiddling #2") {
check(f(10) == 0x1f);
check(f(11) == 0x2f);
}
and when a test failed the following was printed:
test.cc:9: f(10) == 0x1f (30 == 31) failed. [suite/twiddling #2][].
which is all pretty nice, isn't it? Well, not really.
I found myself having to convert the decimal print-outs to hexadecimal before the error made sense to me -- bit twiddling is not easy in base-10... It didn't take long until I wished that my favorite unit test framework did this automatically for me. How nice then that I had the author of it so conveniently close. Sitting on the very same chair even!
Fast forward one hour and Protest now gives the following print-out for the example above
test.cc:9: f(10) == 0x1f (0x1e == 0x1f) failed. [suite/twiddling #2][].
that is, Protest recognizes that I used hexadecimal literals in the check and changes the base of the integers in the print-out appropriately.
Pretty convenient.
Sunday, May 5, 2013
pythlog -- python on constraint-logic-programming steroids
I've programmed in Python for about 5 years and I've programmed in Prolog for about half a year. I know my way around python-land reasonably well, but I'm only beginning to learn Prolog. What I have learnt in the last half year, though, is how hard it is to be taken serious when you tell another developer we should really use Prolog to solve this problem. Prolog is simply a too far-off world if you're used to python-land.
A lot about learning a new tool or language is how easy it is to leverage existing knowledge. And Prolog does not fair well in this regard. No side effect? No classes? No for statement? What's this funky if? Where's my list comprehension? Recursion -- for real?? You have to be kidding me! These are all responses of a hypothetical, but likely, programmer that learns Prolog.
Even though I'm advocating learning Prolog, there are some thing that just seem to fundamentally be designed to work against me, and I keep thinking if Prolog only was a tiny bit forgiving and accepted me for the programmer I am... and my tiny brain. In addition, Prolog lacks a lot of syntactic sugar for common operation, such as string concatenation.
As an experiment of how many of Prolog good properties can be moved into python-land, I've started working on a python-to-prolog compiler. The intention is primarily very egoistic: I want a language that makes my life as a programmer better. The way I see it marrying Python with Prolog (or the other way around?) can potentially bring a very powerful language. I'm calling this marriage pythlog and here's the techy elevator pitch:
pythlog is a language that melds the power of constraint logic programming with the ease of development of Python.
What does this mean? It means that not only can a lot of traditional Python code be compiled and run, such as
def mersenne_prime(n):
return 2 ** n - 1
def format_string(a, b):
return "[" + a + b + 2 * a + "]"
but also search/equation solving such as:
n = free # solve this variables
assert mersenne_prime(n) == 618970019642690137449562111
a = free
b = free
assert format_string(a, b) == "[abc, abcabc]"
where n, a, and b are free variables that will be bound to values by solving the above equations. In this example n is solved to 89 and a to "abc", b to ", ".
Before you get too excited, please note that state of pythlog is proof-of-concept: there is basic integer arithmetic, string, and list support. There is also some support for user defined classes.
What can be expected to be supported of the Python language? Well, so far my prototyping indicates that at least integers, strings, lists, sets, dicts, and user-defined classes can be supported. I've done a lot of prototyping to find out what can be done and what can't be done, and I think there is a lot of potential here. In fact, by using existing tools pythlog will support compilation to native code (using the gprolog compiler), which is cool in itself.
A lot about learning a new tool or language is how easy it is to leverage existing knowledge. And Prolog does not fair well in this regard. No side effect? No classes? No for statement? What's this funky if? Where's my list comprehension? Recursion -- for real?? You have to be kidding me! These are all responses of a hypothetical, but likely, programmer that learns Prolog.
Even though I'm advocating learning Prolog, there are some thing that just seem to fundamentally be designed to work against me, and I keep thinking if Prolog only was a tiny bit forgiving and accepted me for the programmer I am... and my tiny brain. In addition, Prolog lacks a lot of syntactic sugar for common operation, such as string concatenation.
 |
| A snake around a piece of wood. Get it? |
pythlog is a language that melds the power of constraint logic programming with the ease of development of Python.
What does this mean? It means that not only can a lot of traditional Python code be compiled and run, such as
def mersenne_prime(n):
return 2 ** n - 1
def format_string(a, b):
return "[" + a + b + 2 * a + "]"
but also search/equation solving such as:
n = free # solve this variables
assert mersenne_prime(n) == 618970019642690137449562111
a = free
b = free
assert format_string(a, b) == "[abc, abcabc]"
where n, a, and b are free variables that will be bound to values by solving the above equations. In this example n is solved to 89 and a to "abc", b to ", ".
Before you get too excited, please note that state of pythlog is proof-of-concept: there is basic integer arithmetic, string, and list support. There is also some support for user defined classes.
What can be expected to be supported of the Python language? Well, so far my prototyping indicates that at least integers, strings, lists, sets, dicts, and user-defined classes can be supported. I've done a lot of prototyping to find out what can be done and what can't be done, and I think there is a lot of potential here. In fact, by using existing tools pythlog will support compilation to native code (using the gprolog compiler), which is cool in itself.
Monday, April 1, 2013
Five years of hacking and searching
Five years ago I write my first post on this blog. Looking back I realize that writing here has been like a hacking diary of some sort. I can see how my interests has shifted by looking on the topics of my posts.
The topic for this 110th post is Five years of hacking and searching, because it's not only been five years of hacking, fiddling, and playing around with ideas -- it has also been five years for searching.
Searching for what? Many things: patterns, tools, design, languages, etc. Ever since I took my first stumbling steps in the programming world by copying code from my Commodore Basic User's Manual, I've felt that there must be better ways of doing this -- this activity that we call hacking, programming, or developing, depending on if we're on couch or at the office.
At the time of User's Manual-copying I was a eight or nine year old kid with an exceptionally average brain capacity, and neither could I understand what the code I was typing did, nor could I imagine how the world of computing would develop -- or that I would make my living out of it for that matter. But that feeling of that things could be done better was there. Why did I have to manually save line numbers in my Basic program (you know, 10, 20, 30, etc)? Why didn't the computer do that?
After some time I found the renumber command which actually did this automatically. Cool, a command that help me writing my Basic program! This made me very excited: renumber was a program that operated on another program (source)! Imagine how awesome that though is for a little kid who just are beginning to program and learning what can be done with a computer.
A few years later my father brought a PC home from work. I was very interested in this machine, but what could I do with it? Well, not much it seemed -- there was no Basic! I don't recall how I found it out -- I guess hours and hours looking around on the hard drive -- but I finally found qbasic.exe. Oh, how I loved playing around in this environment. It was like nothing I had ever seen before. It was an editor. You ran the program in the editor. You could step programs line-by-line in the editor. The help of the editor and the language as integrated into the this environment. The QBasic language even had graphical modes! This was amazing for a computer enthusiast who's feet didn't reach the floor when he was sitting in his father's chair programming his computer through this blue-looking editor. Exploring what the computer memory contained through PEEK was fun, as was seeing it randomly crashing when I POKEd it.
Move forward a couple of year to the mid 1990's. Somehow my family got internet over 28.8 modem and somehow I realize that I can use internet to find solutions to my programming questions. I find support for mouse in QBasic, and crazy cool graphical tricks that I never understood. But I got some pretty cool stuff working with it. I remember writing a GUI application in QBasic with mouse and windowing support. I remember particularly fondly how I by accident stumble upon recursion while doing this. I remember very clearly how I looked at the screen popping one window, and then another when I pressed a GUI button, and when I closed the top window, the one below was still working. A totally awesome feeling of achievement that I never have been able to reach again.
Late 1990 and I'm introduced to Pascal in school. Pascal was cool because it actually felt like a real programming language. Why did it feel like a real programming language? Because there was a compiler, and you had to import modules, etc, to get things working. Pascal has some good things, but it never reached up to QBasic as a play-around-and-learn-as-you-go language. I did manage to write a platforming game that was inspired by a swedish comedy show, but for one reason or another writing in Pascal was more like fencing with the compiler than writing programs.
The next languages I learnt was Scheme at the university, which was the most eye-opening programming experience of my life. Somehow Scheme just made sense to me -- power wrapped in simplicity. Later I learnt C++, which was the complete opposite of learning Scheme -- C++ is a language that "just made sense" to me. C++ has a simple and beautiful core in it's C legacy (C is tiny beautiful language if you approach it from the assembly/machine level), but wrapped around this core are classes, templates, exceptions, etc. The result? Complexity wrapped around simplicity.
Later I learnt Java and Python at work. Java is C++ made simple, but it also C++ without the power. When I first learnt Java I was stunned by how fast I got from idea to working code. But Java isn't elegant. You can't design elegant application in Java, because the powers for doing so has been lost in the process of dumbing down C++. What about Python? It's a very nice language with tonnes and tonnes of nice libraries, but it's not a language that makes me a better programmer. It doesn't force me to come up with elegant solutions, on the contrary, Python encourages hacky solutions. Do I dislike Python? No. Java? No. C++? No.
Then half a year ago I learned Prolog. I don't think Prolog is a practical language, nor is it a language where the simple obvious solution to a problem is the solution that fits the language. However, Prolog makes me a better programmer and it's makes me (want to be) smarter. No other language I've played around with has done this -- except (Q)Basic when I was 11.
Why am I telling you all this? Well, as this five-years-old-celebration post it's partly about my life, but there is also a deeper point. A good language isn't a language with the most flexible type-system, the deepest meta-programming possibilities, the most coherent syntax, or the most well-defined semantics. A good language is a language the makes you a better programmer and in turn make you write better programs. Obviously, this implies that a good language isn't necessarily a practical language, but a good language is a good companion on your search for better solutions.
As I told you, my biggest personal achievement as a hobbyist programmer was when I was kid writing a GUI program from scratch. Would that be something I would bother doing today? Probably not -- there are several GUI toolkits available and writing one from scratch is a massive undertaking. Why did I do it? First, there was no GUI toolkit available for QBasic (the best of my knowledge); and second, I was already playing around with lines, boxes, and 16 colors on a 640x480 pixel screen. It was only natural to make something GUI-like out my 16-color boxes. The programming environment let me transition from text-based programs to simple graphical programs, and then move on to writing GUI toolkits. The environment helped me becoming a better programmer.
I'm wrapping up this post by mentioning something about my latest project. I wish to make a good (according to the definition above) and practical language. I'm doing this through the following equation Python + Prolog = Pythlog. Python is the language that I write most of my hobby hacks in, and Prolog is the language I write most of my interesting hobby hacks in. Python is a friendly language for solving problems, and Prolog is a friendly language for solving complicated symbolic problems. Pythlog is the sweet spot between these two languages. It allows Python-like programs to perform complicated symbolic operations in very concise ways. It allows equational reasoning about the code, and even running functions "in reverse" (what argument should I provide f such that it returns 17?).
Pythlog isn't particularly far developed, but there is a prototype compiler that pass some tests that show of Pythlog's strengths.
The topic for this 110th post is Five years of hacking and searching, because it's not only been five years of hacking, fiddling, and playing around with ideas -- it has also been five years for searching.
Searching for what? Many things: patterns, tools, design, languages, etc. Ever since I took my first stumbling steps in the programming world by copying code from my Commodore Basic User's Manual, I've felt that there must be better ways of doing this -- this activity that we call hacking, programming, or developing, depending on if we're on couch or at the office.
At the time of User's Manual-copying I was a eight or nine year old kid with an exceptionally average brain capacity, and neither could I understand what the code I was typing did, nor could I imagine how the world of computing would develop -- or that I would make my living out of it for that matter. But that feeling of that things could be done better was there. Why did I have to manually save line numbers in my Basic program (you know, 10, 20, 30, etc)? Why didn't the computer do that?
After some time I found the renumber command which actually did this automatically. Cool, a command that help me writing my Basic program! This made me very excited: renumber was a program that operated on another program (source)! Imagine how awesome that though is for a little kid who just are beginning to program and learning what can be done with a computer.
A few years later my father brought a PC home from work. I was very interested in this machine, but what could I do with it? Well, not much it seemed -- there was no Basic! I don't recall how I found it out -- I guess hours and hours looking around on the hard drive -- but I finally found qbasic.exe. Oh, how I loved playing around in this environment. It was like nothing I had ever seen before. It was an editor. You ran the program in the editor. You could step programs line-by-line in the editor. The help of the editor and the language as integrated into the this environment. The QBasic language even had graphical modes! This was amazing for a computer enthusiast who's feet didn't reach the floor when he was sitting in his father's chair programming his computer through this blue-looking editor. Exploring what the computer memory contained through PEEK was fun, as was seeing it randomly crashing when I POKEd it.
Move forward a couple of year to the mid 1990's. Somehow my family got internet over 28.8 modem and somehow I realize that I can use internet to find solutions to my programming questions. I find support for mouse in QBasic, and crazy cool graphical tricks that I never understood. But I got some pretty cool stuff working with it. I remember writing a GUI application in QBasic with mouse and windowing support. I remember particularly fondly how I by accident stumble upon recursion while doing this. I remember very clearly how I looked at the screen popping one window, and then another when I pressed a GUI button, and when I closed the top window, the one below was still working. A totally awesome feeling of achievement that I never have been able to reach again.
Late 1990 and I'm introduced to Pascal in school. Pascal was cool because it actually felt like a real programming language. Why did it feel like a real programming language? Because there was a compiler, and you had to import modules, etc, to get things working. Pascal has some good things, but it never reached up to QBasic as a play-around-and-learn-as-you-go language. I did manage to write a platforming game that was inspired by a swedish comedy show, but for one reason or another writing in Pascal was more like fencing with the compiler than writing programs.
The next languages I learnt was Scheme at the university, which was the most eye-opening programming experience of my life. Somehow Scheme just made sense to me -- power wrapped in simplicity. Later I learnt C++, which was the complete opposite of learning Scheme -- C++ is a language that "just made sense" to me. C++ has a simple and beautiful core in it's C legacy (C is tiny beautiful language if you approach it from the assembly/machine level), but wrapped around this core are classes, templates, exceptions, etc. The result? Complexity wrapped around simplicity.
Later I learnt Java and Python at work. Java is C++ made simple, but it also C++ without the power. When I first learnt Java I was stunned by how fast I got from idea to working code. But Java isn't elegant. You can't design elegant application in Java, because the powers for doing so has been lost in the process of dumbing down C++. What about Python? It's a very nice language with tonnes and tonnes of nice libraries, but it's not a language that makes me a better programmer. It doesn't force me to come up with elegant solutions, on the contrary, Python encourages hacky solutions. Do I dislike Python? No. Java? No. C++? No.
Then half a year ago I learned Prolog. I don't think Prolog is a practical language, nor is it a language where the simple obvious solution to a problem is the solution that fits the language. However, Prolog makes me a better programmer and it's makes me (want to be) smarter. No other language I've played around with has done this -- except (Q)Basic when I was 11.
Why am I telling you all this? Well, as this five-years-old-celebration post it's partly about my life, but there is also a deeper point. A good language isn't a language with the most flexible type-system, the deepest meta-programming possibilities, the most coherent syntax, or the most well-defined semantics. A good language is a language the makes you a better programmer and in turn make you write better programs. Obviously, this implies that a good language isn't necessarily a practical language, but a good language is a good companion on your search for better solutions.
As I told you, my biggest personal achievement as a hobbyist programmer was when I was kid writing a GUI program from scratch. Would that be something I would bother doing today? Probably not -- there are several GUI toolkits available and writing one from scratch is a massive undertaking. Why did I do it? First, there was no GUI toolkit available for QBasic (the best of my knowledge); and second, I was already playing around with lines, boxes, and 16 colors on a 640x480 pixel screen. It was only natural to make something GUI-like out my 16-color boxes. The programming environment let me transition from text-based programs to simple graphical programs, and then move on to writing GUI toolkits. The environment helped me becoming a better programmer.
I'm wrapping up this post by mentioning something about my latest project. I wish to make a good (according to the definition above) and practical language. I'm doing this through the following equation Python + Prolog = Pythlog. Python is the language that I write most of my hobby hacks in, and Prolog is the language I write most of my interesting hobby hacks in. Python is a friendly language for solving problems, and Prolog is a friendly language for solving complicated symbolic problems. Pythlog is the sweet spot between these two languages. It allows Python-like programs to perform complicated symbolic operations in very concise ways. It allows equational reasoning about the code, and even running functions "in reverse" (what argument should I provide f such that it returns 17?).
Pythlog isn't particularly far developed, but there is a prototype compiler that pass some tests that show of Pythlog's strengths.
Wednesday, February 27, 2013
The cost of #include in Protest
Protest is a unit test framework for C++ unit test framework that distinguishes itself by having a single all-covering check/assert and deals with fixtures in an extremely slick way. I recommend that you check it out.
A few month ago I implemented stringification in Protest and I also wrote functions that stringifies all the classes in STL, std::vector, etc. This feature added some value to Protest but it also caused the compilation times to increase dramatically. The test suite of Protest ran in 2.5 minutes before this feature, and almost 4 minutes afterwards. What happened?
Well, what happened was #include-ing every possible header of STL. So how to fix it? Don't include every header of STL? Exactly.
But then the code won't compile as the used classes, e.g., std::vector, isn't declared. To get around this issue I did something really ugly... By surrounding the relevant code with #if/#endif, the stringification function for std::vector is only compiled if the vector header has been included by the client code. This is done by checking if the include guard used by vector is defined.
When this was implemented the test suite of Protest again finished in around 2.5 minutes.
Of course, this has to be done for each supported compiler, but that's a small price to pay considering ~40% less time spent on waiting for your test suite to compile. Actually, I haven't ported this to MSVC yet.
On a more philosophical note, how this feature was added without cost says a lot about Protest -- it questions the status quo, complexity, and lack of features in other C++ testing frameworks. Protest tries to improve.
A few month ago I implemented stringification in Protest and I also wrote functions that stringifies all the classes in STL, std::vector, etc. This feature added some value to Protest but it also caused the compilation times to increase dramatically. The test suite of Protest ran in 2.5 minutes before this feature, and almost 4 minutes afterwards. What happened?
Well, what happened was #include-ing every possible header of STL. So how to fix it? Don't include every header of STL? Exactly.
But then the code won't compile as the used classes, e.g., std::vector, isn't declared. To get around this issue I did something really ugly... By surrounding the relevant code with #if/#endif, the stringification function for std::vector is only compiled if the vector header has been included by the client code. This is done by checking if the include guard used by vector is defined.
When this was implemented the test suite of Protest again finished in around 2.5 minutes.
Of course, this has to be done for each supported compiler, but that's a small price to pay considering ~40% less time spent on waiting for your test suite to compile. Actually, I haven't ported this to MSVC yet.
On a more philosophical note, how this feature was added without cost says a lot about Protest -- it questions the status quo, complexity, and lack of features in other C++ testing frameworks. Protest tries to improve.
Thursday, January 17, 2013
Python type checking -- or why you should learn Prolog
A while ago I wrote about the programming language Prolog. Even longer ago I wrote about a python type-checker (and compiler) I was then working on. That type-checker and compiler never reached a state where it could compile any python code, however, it did type check quite complicated code.
Today I started working on a new type-checker for python that is based on Prolog. Prolog is a logic programming language with several features that makes it an ideal language to implement type-checking in. Here's an example of a piece of code that it successfully type-checks:
A = 1
B = 1.0
C = "c"
def plus_C(value):
return C + value
def func0(a):
global A, B, C
A = "hello"
result = plus_C(A)
C = 10
result = plus_C(B) + a
return result
The way it works is pretty straight-forward. The type-checker simply disassembles the relevant functions (using the dis module), and outputs Prolog code where each instruction is replaced with a Prolog predicate, as follows:
py_plus_C(Module, V_value, ReturnValue) :-
load_attr(Module, 'C', T0),
binary_add(T0, V_value, T1),
return_value(T1, ReturnValue).
py_func0(Module, V_a, ReturnValue) :-
store_attr(Module, 'A', py_str),
load_attr(Module, 'plus_C', T0),
load_attr(Module, 'A', T1),
call_function(Module, T0, [T1], T2),
store_attr(Module, 'C', py_int),
load_attr(Module, 'plus_C', T3),
load_attr(Module, 'B', T4),
call_function(Module, T3, [T4], T5),
binary_add(T5, V_a, T6),
return_value(T6, ReturnValue).
Here, the type-checker infers the return type of func to be float, and the type of the argument a to be either int or float. Note that the definition of Module is omitted because it's mostly just an internal representation of the python module and not terribly interesting.
In addition to dealing with mutable state (mutation really complicates type-checking), it handles parametrized types (e.g., list) as the following example illustrates:
def func1(lla, lb):
return lla[0] + lb
where it infers that lla, lb, and the return type is:
Now to the cool part.
The entire thing is 236 lines of code.
Ok, granted it doesn't handle ifs, fors, etc, but still. The type-checker can be found here. Unfortunately, I currently don't have time to continue working on it, but the code is there and proofs the idea.
Today I started working on a new type-checker for python that is based on Prolog. Prolog is a logic programming language with several features that makes it an ideal language to implement type-checking in. Here's an example of a piece of code that it successfully type-checks:
A = 1
B = 1.0
C = "c"
def plus_C(value):
return C + value
def func0(a):
global A, B, C
A = "hello"
result = plus_C(A)
C = 10
result = plus_C(B) + a
return result
The way it works is pretty straight-forward. The type-checker simply disassembles the relevant functions (using the dis module), and outputs Prolog code where each instruction is replaced with a Prolog predicate, as follows:
py_plus_C(Module, V_value, ReturnValue) :-
load_attr(Module, 'C', T0),
binary_add(T0, V_value, T1),
return_value(T1, ReturnValue).
py_func0(Module, V_a, ReturnValue) :-
store_attr(Module, 'A', py_str),
load_attr(Module, 'plus_C', T0),
load_attr(Module, 'A', T1),
call_function(Module, T0, [T1], T2),
store_attr(Module, 'C', py_int),
load_attr(Module, 'plus_C', T3),
load_attr(Module, 'B', T4),
call_function(Module, T3, [T4], T5),
binary_add(T5, V_a, T6),
return_value(T6, ReturnValue).
Here, the type-checker infers the return type of func to be float, and the type of the argument a to be either int or float. Note that the definition of Module is omitted because it's mostly just an internal representation of the python module and not terribly interesting.
In addition to dealing with mutable state (mutation really complicates type-checking), it handles parametrized types (e.g., list) as the following example illustrates:
def func1(lla, lb):
return lla[0] + lb
where it infers that lla, lb, and the return type is:
- list(float), float, float
- list(int), float, float
- list(int), int, int
- list(str), str, str
- list(list(X)), list(X), list(X)
- dict(int, list(X)), list(X), list(X)
Now to the cool part.
The entire thing is 236 lines of code.
Ok, granted it doesn't handle ifs, fors, etc, but still. The type-checker can be found here. Unfortunately, I currently don't have time to continue working on it, but the code is there and proofs the idea.
Wednesday, January 16, 2013
My open source and my closed work
I usually don't write about things that actually happen to me. Instead I focus on describing tools, cool ideas, or just telling a joke. In this post, though, I'll tell an ongoing story about bringing protest into the company where I work.
protest is a neat little unit testing framework for C++ that I started working on around September last year. It's been open-source under the Boost Software Licence since its very beginning. The reason I started working on it was for one simple reason that has caused many hackers to start... well, hack... scratching an itch.
The particular itch in this case is the terrible state of C++ unit testing. I've tried several testing frameworks over the year, but all make me say yuck, do they really want me to write that? or should I really do that manually? or even worse what... I can't do that?
I've already written about protest here several times, so I won't do that again. What I will do however, is describing the process of using protest at my work. It started in November when I presented protest to my colleagues. They were positive and saw it as a good candidate for replacing UnitTest++ that we're currently using.
I'm working at a company that is very protective of it's source code and information -- for good reasons. What I am worried about is that if we started using protest without explicit acceptance and knowledge from some manager(s), I might run into problems if the source is found on the internet by the "security police" since it has my name on it (my user name on Gitorious is my real name, just as here on my blog). If they found it under my name on the internet, they can (falsely) draw the conclusion that I brought the code outside of the company.
So, to make sure this wouldn't happen I contacted a manager and explained the situation. Unfortunately, he contacted a person who specializes in law that looked into the matter in more detail. The response I got was we can't accept this, CompanyName might lose the the right to use protest if this-and-that, which wasn't true at all of course.
I got a bit put off by this, but I finally got back to the issue this week. My response went along the following lines:
Regardless if you acknowledge and accept the license under which protest is published, you should understand that any open-source software can be used by any employee at CompanyName at any time. I know for a fact that we/CompanyName is using open-source licenced software, indeed, we rely on it daily.
I'm not sure if this was I good idea or not.
protest is a neat little unit testing framework for C++ that I started working on around September last year. It's been open-source under the Boost Software Licence since its very beginning. The reason I started working on it was for one simple reason that has caused many hackers to start... well, hack... scratching an itch.
The particular itch in this case is the terrible state of C++ unit testing. I've tried several testing frameworks over the year, but all make me say yuck, do they really want me to write that? or should I really do that manually? or even worse what... I can't do that?
I've already written about protest here several times, so I won't do that again. What I will do however, is describing the process of using protest at my work. It started in November when I presented protest to my colleagues. They were positive and saw it as a good candidate for replacing UnitTest++ that we're currently using.
I'm working at a company that is very protective of it's source code and information -- for good reasons. What I am worried about is that if we started using protest without explicit acceptance and knowledge from some manager(s), I might run into problems if the source is found on the internet by the "security police" since it has my name on it (my user name on Gitorious is my real name, just as here on my blog). If they found it under my name on the internet, they can (falsely) draw the conclusion that I brought the code outside of the company.
So, to make sure this wouldn't happen I contacted a manager and explained the situation. Unfortunately, he contacted a person who specializes in law that looked into the matter in more detail. The response I got was we can't accept this, CompanyName might lose the the right to use protest if this-and-that, which wasn't true at all of course.
I got a bit put off by this, but I finally got back to the issue this week. My response went along the following lines:
Regardless if you acknowledge and accept the license under which protest is published, you should understand that any open-source software can be used by any employee at CompanyName at any time. I know for a fact that we/CompanyName is using open-source licenced software, indeed, we rely on it daily.
I'm not sure if this was I good idea or not.
Friday, January 4, 2013
Documentation generation in canji
canji is a tool-chain generator that I've been writing about before on this blog and on gitorious. The current focus lies on inferring various attributes of instructions. Recently I've spent some time on generating a descriptive string for each instruction, which will be used for the generated instruction set manual. This blog describes the approach for doing so.
Instructions are described in a C-like language, so to generate a descriptive string for an instruction the code implementing it has to be understood on a high level. This may sound like a dauntingly complex task, but since the purpose of canji is to build virtual machines, we have a good idea of what kind of code that will be processed.
For instance, the following is needed to understood:
So the obvious approach to generate a descriptive string is to simply implement a bunch of real-world instructions and make the description generator generate an appropriate description.
This kind of work is time consuming but simple, and in fact not so much different to what an optimization pass of a compiler does. When a piece of code is optimized it is matched against a bunch of patterns and if any of the patterns matches, the code is rewritten according to the rules of the matched pattern.
When the description is generated for an instruction, its code is matched against a set of patterns, and when a matching pattern is matches a description is generated.
That's the simplest approach for doing this and the approach taken so far. It's likely that this will be extended in the future and have several layers of patterns that deals with different attributes of the code, e.g., conditional, etc.
Here's some example of descriptions generated by canji and the code its generated from:
The next step is to analyse the registers of the virtual memory infer what purpose they fill and generate a description.
Instructions are described in a C-like language, so to generate a descriptive string for an instruction the code implementing it has to be understood on a high level. This may sound like a dauntingly complex task, but since the purpose of canji is to build virtual machines, we have a good idea of what kind of code that will be processed.
For instance, the following is needed to understood:
- reading and writing registers,
- reading and writing memory,
- addition, multiplication, shifting, etc,
- incrementing and decrementing
- pushing and popping,
- branching (assigning the program counter),
- conditional jumps, moves, etc,
- call function,
- return from function,
- and more.
So the obvious approach to generate a descriptive string is to simply implement a bunch of real-world instructions and make the description generator generate an appropriate description.
This kind of work is time consuming but simple, and in fact not so much different to what an optimization pass of a compiler does. When a piece of code is optimized it is matched against a bunch of patterns and if any of the patterns matches, the code is rewritten according to the rules of the matched pattern.
When the description is generated for an instruction, its code is matched against a set of patterns, and when a matching pattern is matches a description is generated.
That's the simplest approach for doing this and the approach taken so far. It's likely that this will be extended in the future and have several layers of patterns that deals with different attributes of the code, e.g., conditional, etc.
Here's some example of descriptions generated by canji and the code its generated from:
- Loads the value at memory address rsrc into rdst.
load src, dst
r[dst] = mem[r[src]]; - Stores rsrc at memory address sp and increments sp.
push src
mem[sp] = r[src];
sp = sp + 1; - Branches to addr if status.z == 1.
jeq addr
if (status.z == 1)
pc = pc + 1;
else
pc = addr;
The next step is to analyse the registers of the virtual memory infer what purpose they fill and generate a description.
Friday, December 28, 2012
Syntax inference in canji
canji is a tool that aims to generate a tool-chain for virtual machines or hardware emulators given a compact description of said machine. The tool-chain contains a interpreter, jit, assembler, programmers' reference manual, etc. In this post we explore the syntax inference engine and how it is used to to generate the assembler of the tool-chain.
First some background information about the way the virtual machine is described. A language developed especially for the purpose is used in conjunction with a very relaxed grammar for the instruction syntax. This is an example of a move instruction similar to the move instruction of the x64 architecture:
move base + scale * idx + offset, src
mem[r[base] + scale * r[idx] + offset] = r[src];
where the first line describes the instruction's syntax in an abstract way and the second line is the concrete implementation of the instruction (mem and r are machine-global variables).
First, the syntax inference engine infers that scale and offset are use directly in integer arithmetic, thus these two operands are immediates and should be written as such. For instance #17 or #42.
Second, the inference engine derives that base, idx, and src, are used to index the register file r, thus should be written as for instance r0, r3, or r15. That is, the name of the register file (r) followed by the index of the register.
Third, the inference engine derives that the expression r[base] + scale * r[idx] + offset is used to index memory and thus should be written according to the memory access syntax, which is for instance [r0 + 2 * r1 + 2] (the Intel assembly flavor).
To sum up, these three items are used to derive a syntax for the move instruction that such that the following example is valid:
move [r0 + 8 * r1 + 16], r8
Currently the syntax inference engine distinguish register files from memories by simply looking at their sizes. Even though this is in the general case not 100% accurate, it is accurate enough in the majority of (reasonable) cases. So it is likely that this will remain.
The syntax inference engine uses another inference engine to complete its work -- the optional operands inference engine. This engine find which operands that trivially can be made optional because they have a natural no-op value. An example of such operand is offset for the move instruction above, which can be made optional by encoding the absence of offset as if offset is 0. Thus, the following are valid move instructions:
move [r0], r8
move [r0 + r1], r8
move [r0 + 16], r8
As you might realize, the inference engine make an assumption to be able to accept these three different version of the instruction. The assumption is that the + and * tokens in the move syntax description:
move base + scale * idx + offset, src
"belongs to" the operand that directly follows them. This means that the operand is optional the + and * tokens that precedes it are also optional. For instance, the version of move without the offset operand have the following syntax:
move base + scale * idx, src
It's a bit hard to explain in word, but pretty straight forward when you see examples like this.
So far, the canji syntax inference engine don't handle instruction flags. It is likely that this will simply be dealt with by looking at the type of the operand -- if an operand is of type u1 or s1 (meaning unsigned one bit integer and signed one bit integer, respectively).
A different approach to deal with the syntax inference is to remove the per instruction description of syntax and have a global syntax description instead. For instance, such global description could say which order source and destination operands should be, etc.
However, many assemblers handle several syntaxes, e.g., the AT&T and Intel assembler syntaxes. How should this be dealt with by canji? Well, currently there is no work on dealing with this, but it is technically not hard to do.
First some background information about the way the virtual machine is described. A language developed especially for the purpose is used in conjunction with a very relaxed grammar for the instruction syntax. This is an example of a move instruction similar to the move instruction of the x64 architecture:
move base + scale * idx + offset, src
mem[r[base] + scale * r[idx] + offset] = r[src];
where the first line describes the instruction's syntax in an abstract way and the second line is the concrete implementation of the instruction (mem and r are machine-global variables).
First, the syntax inference engine infers that scale and offset are use directly in integer arithmetic, thus these two operands are immediates and should be written as such. For instance #17 or #42.
Second, the inference engine derives that base, idx, and src, are used to index the register file r, thus should be written as for instance r0, r3, or r15. That is, the name of the register file (r) followed by the index of the register.
Third, the inference engine derives that the expression r[base] + scale * r[idx] + offset is used to index memory and thus should be written according to the memory access syntax, which is for instance [r0 + 2 * r1 + 2] (the Intel assembly flavor).
To sum up, these three items are used to derive a syntax for the move instruction that such that the following example is valid:
move [r0 + 8 * r1 + 16], r8
Currently the syntax inference engine distinguish register files from memories by simply looking at their sizes. Even though this is in the general case not 100% accurate, it is accurate enough in the majority of (reasonable) cases. So it is likely that this will remain.
The syntax inference engine uses another inference engine to complete its work -- the optional operands inference engine. This engine find which operands that trivially can be made optional because they have a natural no-op value. An example of such operand is offset for the move instruction above, which can be made optional by encoding the absence of offset as if offset is 0. Thus, the following are valid move instructions:
move [r0], r8
move [r0 + r1], r8
move [r0 + 16], r8
As you might realize, the inference engine make an assumption to be able to accept these three different version of the instruction. The assumption is that the + and * tokens in the move syntax description:
move base + scale * idx + offset, src
"belongs to" the operand that directly follows them. This means that the operand is optional the + and * tokens that precedes it are also optional. For instance, the version of move without the offset operand have the following syntax:
move base + scale * idx, src
It's a bit hard to explain in word, but pretty straight forward when you see examples like this.
So far, the canji syntax inference engine don't handle instruction flags. It is likely that this will simply be dealt with by looking at the type of the operand -- if an operand is of type u1 or s1 (meaning unsigned one bit integer and signed one bit integer, respectively).
A different approach to deal with the syntax inference is to remove the per instruction description of syntax and have a global syntax description instead. For instance, such global description could say which order source and destination operands should be, etc.
However, many assemblers handle several syntaxes, e.g., the AT&T and Intel assembler syntaxes. How should this be dealt with by canji? Well, currently there is no work on dealing with this, but it is technically not hard to do.
Monday, December 10, 2012
Generating tool-chains
In my previous post I outlined a way of generating interpreters and JIT compilers from a simple description of the state of the target (virtual) machine and the semantics of the instructions. I also linked to a prototype called jiggawatt where I implemented these ideas.
Since then I continued to explore what can be generated from such small description of the target machine:
Unfortunately, since jiggawatt main purpose was to explore what could be done -- not to be a long-living project -- it has grown into a huge ball of untested code. But out of the ideas and experience a new project has been born: canji (yet, it is intentionally misspelled).
canji's ambitions is much greater than those of jiggawatt. With canji I aim to generate a whole tool-chain for a (virtual) machine: interpreter/simulator (with JIT), assembler/disassembler, a static optimizing compiler, ELF, debugger, and documentation with textual description and example code. I also aim to have a test-case generator that generates tests that verifies the interpreter and static compiler. Simpler things such as Emacs modes for the assembler is also possible and hopefully much more.
The concrete goal of canji is to generate an entire tool-chain, but the less obvious goal is to explore what implicit information that lies hidden in a machine description. For instance, to generate an assembler with operand type-checking (e.g., to check that immediate and register isn't mixed up) in jiggawatt I let the assembler generator assume that if an operand is used to index an array, that operand must be prefixed by the name of that array. For example, an instruction load that take two operands, an immediate and a destination register, must be written as follows:
load #10, r0
assuming the array describing the register file is called r.
Assumptions like this may or may not be a good idea -- as I said canji is a project that explores what can be generated from a very tiny description of a (virtual) machine.
Since then I continued to explore what can be generated from such small description of the target machine:
- Interpreter that doubles as a simple inference engine,
- Optimizing JIT compiler,
- Assembler and disassembler,titool
- Instruction binary encoding, and
- Documentation including textual description of each instruction.
Unfortunately, since jiggawatt main purpose was to explore what could be done -- not to be a long-living project -- it has grown into a huge ball of untested code. But out of the ideas and experience a new project has been born: canji (yet, it is intentionally misspelled).
canji's ambitions is much greater than those of jiggawatt. With canji I aim to generate a whole tool-chain for a (virtual) machine: interpreter/simulator (with JIT), assembler/disassembler, a static optimizing compiler, ELF, debugger, and documentation with textual description and example code. I also aim to have a test-case generator that generates tests that verifies the interpreter and static compiler. Simpler things such as Emacs modes for the assembler is also possible and hopefully much more.
The concrete goal of canji is to generate an entire tool-chain, but the less obvious goal is to explore what implicit information that lies hidden in a machine description. For instance, to generate an assembler with operand type-checking (e.g., to check that immediate and register isn't mixed up) in jiggawatt I let the assembler generator assume that if an operand is used to index an array, that operand must be prefixed by the name of that array. For example, an instruction load that take two operands, an immediate and a destination register, must be written as follows:
load #10, r0
assuming the array describing the register file is called r.
Assumptions like this may or may not be a good idea -- as I said canji is a project that explores what can be generated from a very tiny description of a (virtual) machine.
Sunday, November 25, 2012
Generating interpreters and JIT compilers
Based on a description of each register in a (virtual) machine and each instruction, shouldn't it be possible to generate an interpreter for such machine? And if it's possible to generate a interpreter, shouldn't it be possible to generate a JIT compiler as well? Additionally, if a interpreter can be generated, shouldn't it be possible to generate a "inference engine" that infers various static properties of a program, e.g., that c = a + b is 1 if a = 1 and b = 0?
Of course it is possible -- the question, however, is how such description should look. How convenient is it to write such description? Let's start with the description of the machines registers.
Assuming a simple machine with non-overlapping registers (i.e., no al/ah/ax/eax/rax mess) the register description is fairly straight forward, for instance:
rf: int64[64]
zflag: bit
which say that there is a register file called rf consisting of 64 64bit registers and a flag, zflag, indicating whether or not the result of the last arithmetic operation was zero.
Although the above is a description of the machine's register it's a state-less description, in the sense that it purely declarative description of structure -- there is no mutation described here. Thus, this description is denoted the structural semantic.
On top of the structure of the machine are the instructions, which mutate the registers. These are described by the operational semantics. The following describes the load instruction, which writes an immediate value to the register file:
def load(imm: int64, dst:int6):
rf[dst] = imm
where imm and dst are the operands to the instruction -- an immediate and the (index of the) destination register, respectively. Furthermore, rf is the register file as described by the structural semantics above.
To give some credibility to my first claim, that it is possible to generate an interpreter from this description, note that the semantic description formulated as above can trivially be used as a interpreter (simple text transform is enough) as the following python program indicates:
Now, what about generating a JIT compiler for the load instruction? Let's start by looking at the end result, that is, how can such a JIT compiler be implemented. Here's a sample of an implementation of the load instruction implemented in C++:
I'm guessing that you by now sayt show me the code. Sure, here is a proof-of-concept implementation. It is called jiggawatt and it can, as of the writing of this post, generate interpreters and jit compilers that support load instructions, add and sub instructions, non-conditional jumps, and conditional jumps. So far it does not generate a optimizing jit compiler, however that is (one of) the end goal(s).
But so what? Why would you ever need a interpreter and jit compiler generator? Well, as a back-end for DSLs as well as full-fledge programming languages is one application that comes to mind. Emulators of physical processors or other kind of hardware is another. A third application is for prototyping instruction sets and virtual machines.
Of course it is possible -- the question, however, is how such description should look. How convenient is it to write such description? Let's start with the description of the machines registers.
Assuming a simple machine with non-overlapping registers (i.e., no al/ah/ax/eax/rax mess) the register description is fairly straight forward, for instance:
rf: int64[64]
zflag: bit
which say that there is a register file called rf consisting of 64 64bit registers and a flag, zflag, indicating whether or not the result of the last arithmetic operation was zero.
Although the above is a description of the machine's register it's a state-less description, in the sense that it purely declarative description of structure -- there is no mutation described here. Thus, this description is denoted the structural semantic.
On top of the structure of the machine are the instructions, which mutate the registers. These are described by the operational semantics. The following describes the load instruction, which writes an immediate value to the register file:
def load(imm: int64, dst:int6):
rf[dst] = imm
where imm and dst are the operands to the instruction -- an immediate and the (index of the) destination register, respectively. Furthermore, rf is the register file as described by the structural semantics above.
To give some credibility to my first claim, that it is possible to generate an interpreter from this description, note that the semantic description formulated as above can trivially be used as a interpreter (simple text transform is enough) as the following python program indicates:
rf = [0] * 64
zflag = 0
def load(imm, dst):
def execute():
rf[dst] = imm
return execute
program = [load(1000, 0), load(200, 1)]
for instr in program:
instr()
print(rf[0], rf[1])
Furthermore, translating the description into a more efficient C implementation is simply a matter of more trivialities and a tea spoon of relatively straight-forward type inference. But such details are not important for the argument I'm making.Now, what about generating a JIT compiler for the load instruction? Let's start by looking at the end result, that is, how can such a JIT compiler be implemented. Here's a sample of an implementation of the load instruction implemented in C++:
class load {
int64_t imm;
unsigned dst;
public:
load(int64_t imm, unsigned dst) : imm(imm), dst(dst) { }
void emit(Xbyak::CodeGenerator& cg) {
gc.mov(gc.r8, imm);
gc.mov(gc.r9, dst);
gc.mov([rdi + offsetof(State, rf) + gc.r9 * 8],
gc.r9);
}
};
where we used the great Xbyak framework for translating x64 assembler into binary encoded instructions. This class can be used to emit the load instruction at runtime, that is, we have a working JIT compiler -- all generated from the four line long description above!I'm guessing that you by now sayt show me the code. Sure, here is a proof-of-concept implementation. It is called jiggawatt and it can, as of the writing of this post, generate interpreters and jit compilers that support load instructions, add and sub instructions, non-conditional jumps, and conditional jumps. So far it does not generate a optimizing jit compiler, however that is (one of) the end goal(s).
But so what? Why would you ever need a interpreter and jit compiler generator? Well, as a back-end for DSLs as well as full-fledge programming languages is one application that comes to mind. Emulators of physical processors or other kind of hardware is another. A third application is for prototyping instruction sets and virtual machines.
Subscribe to:
Posts (Atom)