Stories
Slash Boxes
Comments
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

Ovid (2709)

Ovid
  (email not shown publicly)
http://publius-ovidius.livejournal.com/
AOL IM: ovidperl (Add Buddy, Send Message)

Stuff with the Perl Foundation. A couple of patches in the Perl core. A few CPAN modules. That about sums it up.

Journal of Ovid (2709)

Thursday June 12, 2008
04:01 AM

More On Constraints

[ #36667 ]

I was Warnocked in my last post about an approach to constraint programming in Perl 6. This isn't terribly surprising. Constraint programming is one of those areas which is fascinating, but for some reason, doesn't seem to catch on, even though I suspect it could eliminate many bugs in software.

If you squint, you could think of a constraint as a data type which is dependent on other variables, but which affects the value of the variable with said type. But what the hell does that mean??? Imagine the variable is $distance_above_ground and this refers to "how far above the ground my feet are". In the real world it's clear that I can't just set this value by jumping to my new height. Newton would not approve. My $distance_above_ground is constrained by $gravity and my $mass, amongst other things. Further more, I might think of it as being constrained by $time and $momentum because as $time advances, $gravity and $momentum are going to have a lot of fun with $distance_above_ground. In fact, if the latter is great enough, my $life will be impacted (hah!) by such things as $terminal_velocity.

So clearly in the real world, variables are seldom (if ever) completely independent of other variables. Constraint programming allows us, in programming, to express those relations in our code. While more commonly used in declarative languages, constraint programming has been brought to Java, C++ and other "mainstream" languages. To give you an idea, here's an example from a paper about the Kaleidoscope programming language.

Consider a thermometer display which has a grey area representing the mercury, a white area representing the area above the mercury, and a display showing the degrees. How would we update this as a mouse drags the mercury level up and down? Here's a traditional mouse button event handler (rewritten in Perl 6 to make it easier to read):

while $mouse.button_down {
    my $old = $mercury.top;
    $mercury.top = $mouse.location.y;
    my $degrees = $mercury.height / $scale;

    if $old < $mercury.top {
        delta_grey($old, $mercury.top);
    }
    elsif $old > $mercury.top {
        delta_white($mercury.top, $old);
    }
    display_number($degrees);
}

That's the example from their paper and right off the bat I noticed the duplicated line of code and I'm suspicious about the delta methods. That being said, assuming the supporting functions work, it's a straightforward imperative way of handling this. However, having to hand code all this behavior is fraught with the possibility of error.

So how do we avoid this? Constraint programming is one way of doing it. We attach the constraints directly to the variables. Rewriting the above in a constraint style gives us this:

while $mouse.button_down {
    $mercury.top = $mouse.location.y;
}

Holy crap! See how much simpler that while loop is? Wouldn't life be wonderful if all programming was that easy?

Of course, you're probably wondering how this works. The reality is that you've previously declared constraints. They might look like this (adjusting from the Kaleidoscope paper's syntax):

always: $degrees = $mercury.height / $scale;
always: white_rectangle($thermometer):
always: grey_rectangle($mercury);
always: display_number($degrees);

Now, if anyone adjusts any of those variables anywhere in the program, you cannot accidentally skip this logic.

Please note that all of what follows is highly speculative.

How do we translate this to Perl 6, though? I'm thinking "subsets". A subset is an easy way for you to declare your own type. For example, let's say you want to have a variable which only allows positive integers. It's easy:

subset PosInt of Int where { $_ > 0 };
my PosInt $foo;

Now, if anyone tries to assign anything but a positive integer to $foo, they get a fatal error.

But what if you don't want that? What if that number should be set to 1 (one) if anyone ever tries to set it to a non-legal value? You have to declare the variable as mutable like this:

subset ConstrainedPosInt of Int where <-> $_ { $_ = 1 if $_ < 1 }

Now you should get a fatal error if it's set to a non-integer value (because it's still an Int), but if it's set to an integer value less than one, it's set to one. That's basic constraint programming, but the full power of this technique comes out when dealing with relationships between variables. So let's look at that.

Borrowing from yesterday's examples and tightening it up a bit, let's say that you are writing a game and you have a target area with a crosshair in it. If you move the target area, the crosshair must be move with it if it's going to be outside the area. If you move the crosshair, it must not move the target area (the latter can drag the former, not vice versa). What would that look like in a Perl 6 contraint style?

subset CrossHair of Point where <-> $_ {
    $_.inside_of($target_area) || $_.move_inside($target_area)
};

subset TargetArea of Rectangle where <-> $_ {
    $_.outside_of($cross_hair) || $cross_hair.move_inside($_)
};

Now, we can move our target area or cross hair and everything Just Works. Now more worrying about all of the special cases every time we write our code.

Well, that's the theory. I've not actually played with this before and you're probably already noticing the undeclared variables in the above example. Where do those come from? It's all terribly academic to me (even though this technique has been around for almost 20 years) but it appears to be a way of maintaining a guaranteed state in a variable without adding too much cognitive overhead. I'm anxious to play with Perl 6 and see how this plays out.

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
 Full
 Abbreviated
 Hidden
More | Login | Reply
Loading... please wait.
  • Fortress (sans unicode in this example) may provide some inspiration:

    factorial (n :Z64) requires n >= 0 =
       if n = 0 then 1
       else n factorial (n - 1)
    end
    Take a look at method contracts and function contracts for possible ideas as there's more to it then just what I've shown.
  • This smells an awful lot like a database to me…when are people going to realize how powerful and flexible the databases are that they already use?

    —Theory
    • This is far different. Would you really want to try to update real-time GUI constraints from a database instead of in the code?