Now that my proposal is really coming along the exact details of the approach become more clear. I already have written down all the steps of the research and implementation, the only thing I need is a green light from my supervisor. When I get this I will put a link up to the full proposal. For those that cannot wait I have written a little explanation about the functionality of my thesis.
As explained before the subject of the thesis is to create a generic framework that can handle the generation of rule-feedback. An essential property of any generic framework is that it can be instantiated on a particular domain. In this case the instantiation will need a parser and a solver for a specific domain. This is not a real surprise since these objects are always needed when a tool is constructed. Furthermore, an equality module can be given to the framework. Such a module can be used to check two terms on semantic equality instead of syntactic equality. This is needed because in some cases a teacher would want to allow an answer to be either 3/2 or 6/4 as long as the students calculates it correctly. In other situations the answers may only consists of simplified terms, hence the equality may only succeed on the term 3/2.
After instantiation the framework is able to generate rule-feedback for a particular domain. This generation is done in four phases, each of them requiring more information and resources. Phases that need more input are of course able to generate better feedback. Notice that they 'are able to', they do not necessarily generate better feedback. The instantiated framework will give you a change for better feedback, but the default feedback will be on the same level as current tools. Thus it is a change on a gain, never a loss.
Phase zero is able to generate feedback with only the current term and the previous term. These two terms are always available since a student will have to take a step before rule-feedback can be generated. The algorithm of this phase will calculate the answer, e.g. the term a student has to supply as final result, of both terms and compare those. When these answers are equal a correct step has been taken, otherwise the student has done something wrong. The feedback generated in this phase is only 'correct' or 'incorrect' because we have no further information about the intentions of the student.
Within phase one the student will supply the rule he wanted to apply. The algorithm of this phase will check whether the rule was correctly applied and whether the rule was correct. The later is easily done by using the algorithm of phase zero. When this delivers an 'incorrect' the rule was wrong. Checking for a correct application is a matter of applying the rule to the previous term and checking the result against the current term. When these are syntactically equal the rule was applied correctly.
The feedback in this phase can let the student know in which area he made a mistake. Either a mistake in the rule itself or in the application. This will at least be more of a help to a student then a simple 'incorrect'.
The second phase needs more input from the programmer. A set of rewrite-rules defining the allowed actions of the domain will need to be defined as input. From this set the algorithms of this phase will 'guess' the rule a student wanted to apply. When an error has been made the feedback can contain hints about this rule and pointers to explanations or examples.
In the third and last phase the programmer can also supply a set of 'buggy'-rules. These rewrite-rules contain patterns of common misconceptions. By finding a path between the current and previous term with the allowed and buggy-rules the algorithm of this phase can identify a mistake with a high precision. The algorithm for this is well defined by Hennecke, a short English overview can be found here. Feedback from this phase can involve a specific explanation about the mistake, maybe accompanied by an example of a correct rule.
The explanation of the second phase mentions that the algorithm 'guesses' the rule. This 'guessing' is not completely worked out yet, it is actually a large part of the thesis. Algorithms for the other phases are already defined and only need to be implemented in a generic fashion. The result will be a practical implementation combined with formal research.
Everything a master thesis needs, right?
Results from a meeting
Last Tuesday I went to Delft for a meeting with Martin after a long period of only communicating through email/IRC. Although these form of text-communication work fine a real-life meeting will make it easier to discuss things.
One of the subjects of the discussion was my paper for the STC. I already gave my presentation for this course, but finishing the paper was not an easy task for me. As you might have noticed it is quite a challenge for me to write a text in understandable English. When the text must also contain some formal definitions and clear examples the speed of my writings quickly degenerates. However, I still managed to put together a reasonable result. After we discussed which parts needed some modifications I improved the paper in the past couple of days. The result can be found at the new talks-and-paper-page on php-sat.org. Please feel free to provide constructive feedback.
When you followed the link you might have also seen the new page for the PHP-Tools package. This package is now also build within the build-farm, thank you Martin, and available for download. If you have a cool idea for a tool please let me know via the bug-tracker.
Other topics that we discussed will help to improve the path-strategies for file-inclusion, improving the SDF-definition for HereDoc, develop more concise error-reporting and generating the priorities for precedence from the YACC-definition. I have worked a little on all of these issues in the last two weeks, but now I have better ideas to handle the problems I ran into.
A last topic of discussion was an idea I had for an algorithm to use in my thesis. This algorithm uses a set of allowed rewrite rules to ``guess'' the rule a student wanted to apply. I already wrote an example-scenario for my proposal, which is coming along great by the way, so after I reread this I will discuss it in a blog. I'll keep you posted.
One of the subjects of the discussion was my paper for the STC. I already gave my presentation for this course, but finishing the paper was not an easy task for me. As you might have noticed it is quite a challenge for me to write a text in understandable English. When the text must also contain some formal definitions and clear examples the speed of my writings quickly degenerates. However, I still managed to put together a reasonable result. After we discussed which parts needed some modifications I improved the paper in the past couple of days. The result can be found at the new talks-and-paper-page on php-sat.org. Please feel free to provide constructive feedback.
When you followed the link you might have also seen the new page for the PHP-Tools package. This package is now also build within the build-farm, thank you Martin, and available for download. If you have a cool idea for a tool please let me know via the bug-tracker.
Other topics that we discussed will help to improve the path-strategies for file-inclusion, improving the SDF-definition for HereDoc, develop more concise error-reporting and generating the priorities for precedence from the YACC-definition. I have worked a little on all of these issues in the last two weeks, but now I have better ideas to handle the problems I ran into.
A last topic of discussion was an idea I had for an algorithm to use in my thesis. This algorithm uses a set of allowed rewrite rules to ``guess'' the rule a student wanted to apply. I already wrote an example-scenario for my proposal, which is coming along great by the way, so after I reread this I will discuss it in a blog. I'll keep you posted.
Including only once
This week I finally got around to the implementation of a strategy that combines constant-prorogation and some sort of type-state. It was a bit tricky to get it completely right, resulting in some very weird behavior during testing. Fortunately, the problem has been solved and the result is pretty good!
So what problem does this strategy solve? In order to explain this we will first take a quick look at how constant propagation is being handled within PHP-Front (and other Stratego-libraries).
When a value of a variable is known, for example when it is defined in an expression like
Using dynamic rules for linear code is easy, but when code branches it becomes a little bit more complicated. Take this example code:
The value of
If you want to know more about dynamic rules and constant propagation I suggest you take a look at this paper.
Besides the information about the constant propagation we need to take a look at the inclusion mechanism of PHP. You might be aware of the fact that PHP offers both an include as well as an include_once construct. The first one will always include a file, the latter one will only include a file when it wasn't included before.
Dealing with files that are always included in combination with constant propagation is rather easy. We just retrieve/parse/evaluate the file during the constant propagation. Dealing with files that are only included once is also easy with linear code, but things get tricky when branching is involved. Take this piece of code for example:
Within the if-branch the file
But what must we do when we arrive at the other
Notice that we will have to keep track of the inclusion-state of every file. This can (and is) implemented as a state for a file, again with dynamic rules.
Implementing both of these solutions with dynamic rules separately is not that difficult, there are enough sources to figure things out. However, combining these approaches is completely trivial because you will have to deal with dynamic rule-sets and all sorts of merge-strategies. Fortunately for you this is all done behind the scenes. Please enjoy the better constant propagation as of revision 332.
So what problem does this strategy solve? In order to explain this we will first take a quick look at how constant propagation is being handled within PHP-Front (and other Stratego-libraries).
When a value of a variable is known, for example when it is defined in an expression like
$foo = 5, PHP-Front will add a dynamic rule rewriting the variable to the known value. This dynamic rule can later be used to retrieve the value, for example in the expression $bar = $foo+1. This last expression will then be rewritten to $bar = 5+1 which can be completely calculated again. Using dynamic rules for linear code is easy, but when code branches it becomes a little bit more complicated. Take this example code:
$foo = 'say';
if($val){
$bar = 'hello';
} else {
$bar = 'world';
}The value of
$bar can not be statically determined, but we want to keep the knowledge about the variable $foo. A valid way to do this is to take the intersection of the two sets of dynamic rules, the normal one and the one after evaluating the if-branch. This will keep all information about variables that are not used, or given the same value, within the branches of the if. If you want to know more about dynamic rules and constant propagation I suggest you take a look at this paper.
Besides the information about the constant propagation we need to take a look at the inclusion mechanism of PHP. You might be aware of the fact that PHP offers both an include as well as an include_once construct. The first one will always include a file, the latter one will only include a file when it wasn't included before.
Dealing with files that are always included in combination with constant propagation is rather easy. We just retrieve/parse/evaluate the file during the constant propagation. Dealing with files that are only included once is also easy with linear code, but things get tricky when branching is involved. Take this piece of code for example:
if($val){
include_once 'foo.php';
} else {
//other things
}
//some code
include_once 'foo.php';Within the if-branch the file
foo.php might be included and introduce some dynamic-rules. The code for the if will handle this probably so that is not a problem. But what must we do when we arrive at the other
include_once-construct for the same file? Well, there are three different scenario's that can occur:- File has not been included
- File might have been included
- File is definitely included
Notice that we will have to keep track of the inclusion-state of every file. This can (and is) implemented as a state for a file, again with dynamic rules.
Implementing both of these solutions with dynamic rules separately is not that difficult, there are enough sources to figure things out. However, combining these approaches is completely trivial because you will have to deal with dynamic rule-sets and all sorts of merge-strategies. Fortunately for you this is all done behind the scenes. Please enjoy the better constant propagation as of revision 332.
Thesis subject
Working on PHP-Sat this weekend got me a response on Sunday-evening in #stratego. I was told that it was nice to see some more progress on PHP-Sat again. It's very nice to receive such feedback!
What this comment also expressed is that the past month the actual progress on PHP-Sat was not really visible. I have mostly been working on the website and on the GrammarEngineeringTools. Two things that will improve PHP-Sat, but not directly.
But I have to admit, there was another activity that quickly filled up my time:
My thesis-proposal.
I have mentioned before that the subject of my thesis is interesting (of course!), but didn't not explain what it is about. So here is the short version of the goal:
By combining techniques from the field of term-rewriting, strategies and generic programming we aim at supplying a generic framework that supports the generation of rule-feedback with minimal effort.
After reading this, the first question would probably be 'what is rule-feedback?'
Well, imagine a tool that allows you to solve a mathematical exercise such as:
1/2 + 2*(4/5)
by rewriting the expression in little steps. So the first rewrite would evaluate the multiplication which result in:
1/2+8/5.
The second rewrite will perform the addition and will lead to the answer of:
21/10.
(Notice that the rules I applied here are actually a set of combined rules, adding two fractions with different denominator takes more then one step.)
When the application of a rule is incorrect, for example the answer 9/5 for the expression above, feedback will need to be provided. Useful feedback would help a student to understand the mistake that has been made. In this case it could be something like:
You have added two fractions without considering the denominators. Remember that fractions can only be added when the denominators are equal!
I have done quite a bit of research on the feedback that is currently given in educational tools. The conclusion is that it can definitely be improved and certainly needs to be made easier to define. By supplying a generic framework the task of implementing a complete tool is simplified into the specification of the domain.
How this specification can be done, and more details on how the generation of feedback will work, will be explained in some later blogs. I just wanted to let you know what I was doing all day :)
What this comment also expressed is that the past month the actual progress on PHP-Sat was not really visible. I have mostly been working on the website and on the GrammarEngineeringTools. Two things that will improve PHP-Sat, but not directly.
But I have to admit, there was another activity that quickly filled up my time:
My thesis-proposal.
I have mentioned before that the subject of my thesis is interesting (of course!), but didn't not explain what it is about. So here is the short version of the goal:
By combining techniques from the field of term-rewriting, strategies and generic programming we aim at supplying a generic framework that supports the generation of rule-feedback with minimal effort.
After reading this, the first question would probably be 'what is rule-feedback?'
Well, imagine a tool that allows you to solve a mathematical exercise such as:
1/2 + 2*(4/5)
by rewriting the expression in little steps. So the first rewrite would evaluate the multiplication which result in:
1/2+8/5.
The second rewrite will perform the addition and will lead to the answer of:
21/10.
(Notice that the rules I applied here are actually a set of combined rules, adding two fractions with different denominator takes more then one step.)
When the application of a rule is incorrect, for example the answer 9/5 for the expression above, feedback will need to be provided. Useful feedback would help a student to understand the mistake that has been made. In this case it could be something like:
You have added two fractions without considering the denominators. Remember that fractions can only be added when the denominators are equal!
I have done quite a bit of research on the feedback that is currently given in educational tools. The conclusion is that it can definitely be improved and certainly needs to be made easier to define. By supplying a generic framework the task of implementing a complete tool is simplified into the specification of the domain.
How this specification can be done, and more details on how the generation of feedback will work, will be explained in some later blogs. I just wanted to let you know what I was doing all day :)