Archive for the 'Functional' Category

Ohm – Least Resistance

Published
by
Victor Nicollet
on August 30, 2010
in Functional
. 2 Comments

A few astute readers have noticed that there was a new section, titled Ohm, in the blog header above. They have written in private to ask me, and were shortly included in the private beta testing phase for the project. That phase has now come to an end, as I now reveal the project to begin its open beta testing phase.

ohm-70x70Ohm – Least Resistance is a lightweight PHP 5.2 framework designed to be as simple as possible. You can use Ohm before your morning cup of coffee. If you need to do something clever or unusual, you can read the Ohm source code to find out how you can bend it to your needs: it’s only 2,000 lines, comments included. And Ohm conveys this simplicity to your own code, if you are willing to accept its philosophy:

1. Most frameworks can be extended because there are configuration options for every single piece of behavior. Ohm can be extended because it’s extremely simple.

2. Most frameworks help the programmer write code faster, often pushing the dynamic nature of PHP beyond its safe boundaries. Ohm recognizes that reading code is harder than writing it, and helps the programmer write code that is easy to read later on.

3. Most frameworks try to become repositories for countless pieces of useful but highly specific functionality. Ohm concentrates on being a HTTP/PHP/MySQL framework.

The Ohm framework is open source. In fact, its code is in the public domain, though I appreciate references and/or links back to the project page. What you get by downloading the framework:

  • Class auto-loader : finds your classes based on their name, so you don’t have to use require and include all over the place.
  • Request dispatcher : responds to HTTP requests by loading the appropriate action class and executing its response method.
  • Model-View-Controller : the framework layout follows the MVC pattern and helps your application do so as well.
  • Reusable Layouts : lets you define generic page templates that will be wrapped around the actual template. You can insert JS/CSS into the layout from the content.
  • Simple Forms : a backbone module for creating, processing and drawing HTML forms that you can extend to fit your needs.
  • Database Layer : a dead-simple extension on top of mysqli that lets you have an easier time writing SQL requests and retrieving the data, without having to learn a new query language.

If you have any questions about the framework, you can contact me directly (victor-ohm@nicollet.net). Any comments and feedback are welcome (this is an open beta, after all), either by mail or as comments on this post.

Enjoy!

P = NP for Normal People

Published
by
Victor Nicollet
on August 12, 2010
in Functional
. 7 Comments

A few days ago, an Indian computer scientist working for HP has announced that he has proven that P ≠ NP, solving the decades-long search for an answer to the P = NP question. A lot of computer scientists, me included, are quite excited over this, and waiting to see whether the proof actually holds (it’s long and complex enough that only people with a lot of spare time on their hands can actually determine if it’s correct). To us, this is the equivalent of finding life in outer space or learning who killed JFK.

Why are we so excited? Here’s a short explanation for normal people:

Linear Complexity

Suppose you’re in the outsourcing business, and all the world’s spell-checking algorithms have mysteriously disappeared overnight. Being the clever businessman that you always were, you hire a hundred workers from India, buy them a hundred English dictionaries, and start sending them pieces of text with instructions to reply with a list of words that were not in the dictionary.

Having a minimum-wage offshore worker look up a word in a dictionary costs you $0.01; this means that if your customers pay you $0.02 / word, you’re a winner regardless of how large the text is. In essence, spell-checking a text has a linear complexity, because the price as a function of the text size is a line:

linear

Polynomial Complexity

Not everything is linear. Suppose now that you have a different business: big corporations and political parties give you a list of things, and you sort them by popular preference. For instance, you could determine that Pepsi > Coke Light > Coke. You do this by polling people. A “pick one” poll costs you $100 to set up and execute.

If asked to sort two items (Pepsi and Coke), you would need only one poll – $60 per item is a good price (you earn $120 and pay $100).

If asked to sort three items (Pepsi, Coke and Coke Light), one “pick one” poll is not enough : what if everyone loves Pepsi, and there’s not enough answers to order Coke and Coke Light? You need two polls. Now $60/item runs you into the red (you earn $180 and pay $100). So, you increase your price to $100/item just to be sure you’ll never be in the negative. Right?

Well, there are exactly 24 ways of ordering a list of four items:

1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3
2 1 3 4 1 3 4 2 3 4 2 1 4 2 1 3
3 2 1 4 2 1 4 3 1 4 3 2 4 3 2 1
4 2 3 1 2 3 1 4 3 1 4 2 1 4 2 3
1 3 2 4 3 2 4 1 2 4 1 3 4 1 3 2
1 2 4 3 2 4 3 1 4 3 1 2 3 1 2 4

On the other hand, if you run four “pick A or B” polls, you only get 16 different outcomes:

A A A A A A A B A A B A A A B B
A B A A A B A B A B B A A B B B
B A A A B A A B B A B A B A B B
B B A A B B A B B B B A B B B B

So, you have a testing strategy that can give you only 16 different results, and based on those results you have to find which one of 24 situations you are in. This is impossible. You need a fifth test, which will increase the number of results to 32. Now you’re earning $400 but paying $500…

Adding an item to the list multiplies the number of permutations by the number of elements in the list: adding a tenth item multiplies it by ten. On the other hand, adding a new poll only multiplies the number of results by two. This means that the number of polls will increase faster than the number of items. No matter what per-item price you select, you will run out of money sooner or later. Keep this in mind: it’s going to be very important soon.

This plot represents cost (red) and earnings (blue) as a function of the number of items, for a per-item price of $1,000 :

nlogn

The set of all problems that can be solved for a profit, regardless of size, at a per-item price, is the set of problems with linear cost; in computer science lingo, we write this cost as O(n), meaning that you can find a constant (here, the price) such that the cost will be smaller than n times this constant for a problem of size n. Looking for words in a dictionary is a known O(n) problem. Sorting a list of items by comparing them to each other has been proven not to be an O(n) problem (and the description above is a summary of the proof).

Suppose you go for a different pricing method: to sort a list of n items, you ask for $100 × n × n. Two items is $400 (cost: $100), three items is $900 (cost: $200), four items is $1600 (cost $500). You are guaranteed to make a profit because the worst that could happen is that you compare every item to every other item, which means n² polls, and you would still get enough to pay for all of them.

Sorting a list of n items is hence known to be an O(n²) problem.

Remember the definition of linear cost? There exists a constant k such that the cost of working with n items is smaller than than k × n. There is a similar definition for polynomial cost: there exists a constant k such that the cost of working with n items is smaller than nk — n multiplied by itself k times. All linear-cost problems are, by definition, polynomial-cost problems as well.

In the expression “P = NP”, the “P” represents all problems that can be solved at a Polynomial cost.

Non-Deterministic Polynomial Complexity

Let’s think of another business idea. Now, you’re a tour optimizer: salesmen give you a list of cities they need to travel through to sell their wares, and you provide them with a sequence of visits that has the smallest travel costs and never goes more than once through any given city. This is a common toy problem in computer science for which no polynomial-cost solution is known—The Traveling Salesman Problem.

As a quick comparison:

  • Spell-checking a 10-word text involves 10 dictionary searches – O(n)
  • A naive sort of 10 elements takes, at most, 100 comparisons – O(n²)
  • The traveling salesman problem with 10 cities involves testing 3,628,800 paths.

So, you set up a contest: you hand out the problem to a billion minimum wage workers, and you only pay the worker who found the shortest travel path. So, each of them starts computing the length of a certain path, and there are so many workers that every path will be worked on. After a while, they all submit their solutions, and you keep the shortest one.

Each worker spent a polynomial time selecting a travel path and computing its length: they only had to add the distances between consecutive cities in the travel path. So, the cost of solving the problem this way is polynomial. The important thing here is that you did not know what worker you would pay until the answers came in. In computer science, we say that your solving strategy is non-deterministic.

In the expression “P = NP”, the “NP” represents all problems that can be solved at a polynomial cost using a non-deterministic solving strategy — Non-deterministic Polynomial.

P = NP ?

Any P problem is also an NP problem : if you can solve it by paying someone, you can solve it by holding a contest and paying the winner that same amount. The question is whether any NP problem is also a P problem (hence, P = NP) : if you can hold a contest to solve the problem, can you hire someone to do the same while retaining a polynomial cost?

This question is important because our current computing technology (electricity-through-silicon-transistors) does not support non-deterministic computing. So, if we could find efficient deterministic solutions to every problem inside NP, we would be quite happy about it.

Actually… we wouldn’t. Many security features in computer science rely on problems such that 1° solving the problem is very complex but 2° checking whether a solution is correct is very simple. For instance, checking that a password is correct is a P problem (your computer does it several times a day), but finding the password is an NP problem (you have to try all passwords). If a P solution could be found to the “find the password” problem, we would be in trouble.

Turning recursion into loops

Published
by
Victor Nicollet
on July 23, 2010
in Functional
. 2 Comments

This message is a rehash of an earlier post on Stack Overflow. It’s self-sufficient enough to be featured here, and I like to keep my content where I can see it ;) If you’re not a computer genius, you can wait until next Monday for an article that can be read by standard issue humans.

The premise is to take a standard tree traversal function (which is a recursive algorithm) and implement it without recursion. The recursive version is:

traverse(node):
  if node != None do:
    traverse(node.left)
    print node.value
    traverse(node.right)
  endif

Try doing it on your own, then start reading the solution below once your brain is fried.

The solution

This is a clear case of tail recursion, so you can easily turn it into a while-loop.

traverse(node):
  while node != None do:
    traverse(node.left)
    print node.value
    node = node.right
  endwhile

You’re left with a recursive call. What the recursive call does is push a new context on the stack, run the code from the beginning, then retrieve the context and keep doing what it was doing. So, you create a stack for storage, and a loop that determines, on every iteration, whether we’re in a “first run” situation (non-null node) or a “returning” situation (null node, non-empty stack) and runs the appropriate code:

traverse(node):
  stack = []
  while !empty(stack) || node != None do:
    if node != None do: // this is a normal call, recurse
      push(stack,node)
      node = node.left
    else // we're returning: pop and print the current node
      node = pop(stack)
      print node.value
      node = node.right
    endif
  endwhile

The hard thing to grasp is the “return” part: you have to determine, in your loop, whether the code you’re running is in the “entering the function” situation or in the “returning from a call” situation, and you will have an if/else chain with as many cases as you have non-terminal recursions in your code.

In this specific situation, we’re using the node to keep information about the situation. Another way would be to store that in the stack itself (just like a computer does for recursion). With that technique, the code is less optimal, but easier to follow

traverse(node):
  // entry:
  if node == NULL do return
  traverse(node.left)
  // after-left-traversal:
  print node.value
  traverse(node.right)

traverse(node):
   stack = [node,'entry']
   while !empty(stack) do:
     [node,state] = pop(stack)
     switch state:
       case 'entry':
         if node == None do: break // return
         push(stack,[node,'after-left-traversal']) // store return address
         push(stack,[node.left,'entry']) // recursive call
         break
       case 'after-left-traversal':
         print node.value;
         // tail call : no return address
         push(stack,[node.right,'entry']) // recursive call
      end
    endwhile

Harbringer of Spring postmortem

Published
by
Victor Nicollet
on April 11, 2010
in Functional
. 1 Comment

Yesterday was the seventh installment of the Three Hour Game Development Contest, hosted on GameDev.Net by capn_midnight. The premise is that a theme is provided and contestants have three hours to design, implement and deliver a complete video game using art, libraries and technology of their choice, that is somehow related to that theme. The contest results will be revealed today.

harbringer-of-spring

My entry is called Harbringer of Spring, a game where you have to step on dirt tiles to make grass grow there, and step on the stone tile when there’s grass everywhere. To increase difficulty, water tiles cannot be traversed, and bridge tiles turn into water tiles once they are stepped over. It’s written in HTML-CSS-jQuery, sou can play it online. The original intent is vaguely inspired from the Bridges of Königsberg mathematical problem where you have to cross all bridges exactly once.

The technical details:

  • 233 lines of JavaScript code, divided into 100 lines of level data and 133 lines of actual gameplay code.
  • 53 lines of HTML
  • 174 lines of CSS, divided into 103 lines for the general UI (title, links) and 71 lines for the map and tileset.
  • Uses jQuery 1.4.2 to interact with the document.
  • Uses the PlanetCute tileset, because I couldn’t be bothered with graphics.

Here’s the step-by-step rundown of how I developed this entry (the given time is actually a countdown to the time the game must be delivered).

3:15 (that’s 15 minutes before the contest begins): I’ve already decided that the game shall be written in HTML-CSS-jQuery, so I set up my work environment accordingly. Desktop 1 will be my development environment, with a browser on the left monitor containing documentation for jQuery and an xterm on the right monitor connected to the nicollet.net server through SSH, running an emacs with two vertically split buffers. Desktop 2 will be my testing environment, with a browser containing the game on the left monitor and a maximized Firebug on the right monitor.

I also create the index.html, style.css and game.js files, download (with wget) the latest minified version of jQuery, and create an img directory for my images. I’m a bit bored, so I decide to add the “© 2010 Victor Nicollet” footer to the document.

3:00 : apparently, the theme has already been given out a little earlier. Time to start brainstorming. A few ideas I get right off the bat: a game like Sim City where you have to build spring factories in a world covered by winter. The Silk icon set from FamFamFam contains some weather icons, but they’re really small. Perhaps I could instead build a Risk-like game by placing absolutely positioned stacks of units on a world map image? I start browsing the web for acceptable tile sets, just in case.

2:45 : I stumble upon the PlanetCute tileset (courtesy of the GameDev.Net thread on art resources). The concept seems simple enough to implement a 2D tile map quickly, and I like the grass/dirt contrast. I download (with wget) the file and unzip it into img. The water tiles are quite cute, so I’m starting to think about “Spring” in terms of “Hot Spring” or something. Anyway, I need to be drawing tiles, I might as well get that out of the way while letting my right brain think about the theme.

2:30 : through a clever combination of float:left, position:absolute and background-image CSS trickery (with some help from Firebug for empirically guessing the pixel offsets I need) I manage to render the tile map, with the possibility of a “selection” golden light overlayed on top. It’s all controlled by classes on the root tile elements, so controlling it from jQuery will be easy.

I do have a problem, however: even though the root tile elements match the flat area on top of the tile graphics, the actual tile graphics are taller, and the CSS hover property seems to detect hovering even though I’m not above the root tile per se. I have no idea about how to resolve this quickly, so I’ll give up on selecting tiles with the mouse (there are plenty of things you can do with keyboard controls, and given the time I have at my disposal, trying to fix the issue might take much too long.

In the mean time, I thought about a simple “step over tiles to paint them” gameplay similar to Q*bert. The trouble is that the existing graphical framework does not support animations, so adding enemies to the fray might be a bad idea. Yet, “paint the nodes” reminds me of graph theory, which in turn reminds me of the Bridges of Königsberg problem. I quickly decide to add non-traversable areas (I did like those water tiles) with bridges that may only be crossed once. Being able to only use a resource once means having to decide when to use it and what for, and these kinds of decisions provide a nice puzzle game design. So be it. Time to implement!

2:00 : the first half hour is the hardest, because I have to set up the general layout of the game code before I can see anything move on the screen. I go for a simple architecture in jQuery-powered JavaScript : an initialization function sets up the DOM and places references to individual DOM tiles in a 2D array. Everything related to the game will be a member of the global «g» object. The code looks like this so far:

var $world   = $('#lyt-world');
g.$t = [];
for (var y = 0; y < 6; ++y ) {
  var r = [];
  for (var x = 0; x < 9; ++x) {
    r.push($('<div class="tile"><div class="tile-img"/><div class="tile-sel"/></div>').appendTo($world));
  }
  g.$t.push(r);
}

If you’ve already done tile-based rendering, you will probably recognize the YX way of doing things: tile x,y can be found at g.$t[y][x]. I’ve also decided that a level array named «l» will hold the levels, in an array-of-strings fashion (space is dirt, tilde is water, plus is bridge and hash is stone). This is what the first level looks like:

{
  name : '1. The beginning...',
  tile : [
    "   ~~~~~ ",
    "    ~#+  ",
    "~~~+~~~  ",
    "~   ~~~ ~",
    "~~+~~~~+~",
    "~        "
  ],
  init : [1,1]
}

Another major architectural decision was how to represent tiles that had been walked on. One possibility was to implement “on step” rules which altered the map whenever the player moved (but that would involve making a copy of the map present in the level definition). The other possibility was to store the list of all positions that had been stepped on in a way that’s easy to query for “has the player stepped there yet?”. JavaScript has dictionaries so I went with the latter, so the rendering code looked like this:

render : function() {
  for (var y = 0; y < 6; ++y) {
    for (var x = 0; x < 9; ++x) {
      var t = this.map[y].charAt(x),
         $t = g.$t[y][x];

      var xy = [x,y].join();

      $t.attr('class',[
        'tile',
        [x,y].join() == this.pos.join() ? 'show' : '',
        t == ' ' && xy in this.stepped ? 'grass' : '',
        t == ' ' && !(xy in this.stepped) ? 'dirt' : '',
        t == '~' || t == '+' && xy in this.stepped ? 'water' : '',
        t == '+' && !(xy in this.stepped) ? 'wood' : ''
      ].join(' '));
    }
  }
},

This made the “step onto tile” code exceedingly simple:

step : function(xy) {
 this.stepped[xy.join()] = true;
 this.pos = xy;
},

Using Firebug, it was fairly easy to test this by manually calling the step and rendering functions.

1:45 : implementing controls meant, mostly, catching keydown events on the document, detecting arrow key presses, and calling a “try step” function with the appropriate movement vector (that function would check if the movement was possible, then call the actual step function, and finally rendering the entire thing). What took me the longest was finding out what the key values were (I eventually found out by logging the key values to the Firebug console).

The game is now officially playable. I pour myself some hot Earl Grey Tea, eat a warm pancake, and give the first level a few test runs.

1:40 : it was pretty obvious that refreshing the entire page to restart the level was not very nice. In the name of polish, I add a “try again” button.

1:35 : turning a bridge into water as soon as it is stepped on feels weird. I split the “stepped” dictionary into “steppedOn” and “steppedOff” dictionaries that are filled independently, and adjust the rendering code accordingly.

1:30 : the game is quite simple. Maybe I could make it more complex if I forced the player to finish on a specific tile? I add stone tiles to the mix.

1:25 : I implement a “all tiles painted green” function and add a test in the “step” function to check the win condition (all tiles painted green and sitting on a stone tile). Winning starts the next level. The game is now officially in Alpha! Knowing that I can now deliver this simple game as is, I decide to move on to level design and design as many levels as possible.

Also, my fiancée just fell asleep. I guess I’ll plug in my headphones before I resume listening to Rammstein.

1:15 : after a bit of testing, it appears necessary to add a level selector, if only for level design purposes (I don’t want to have to solve seven levels just to test the eight). I now have two playable levels. I guess I should start designing more: aside from the game finished screen, everything’s implemented. In fact, there’s no instructions manual or tutorial yet, and the “step on the stone tile when you’re done” idea is not really that obvious.

1:00 : I write a few short text bubble to explain the game logic, place them in a layer that is only visible on the first level, and position them in Firebug. Now, the level design can start!

0:55 : level 3 (Chess) is over. It’s pretty easy to solve.

0:50 : I search for the actual Bridges of Königsberg on Wikipedia, and implement it as a (rather simple) level 4.

0:40 : I reuse the chessboard from  level 3, add another stone tile to confuse players, solve it while stepping on as few bridges as possible, then turn the unused bridges into water tiles. Seems obvious to me, but apparently this ended up being the most difficult level in the game.

0:30 : Out of ideas. I’ll try a random layout and work from there. This ends up as level 6 (Detour).

0:25 : Still out of ideas. Let’s draw a happy face: level 7 (Happy).

0:15 : Still out of ideas. I randomly draw something up, test it, and that’s it. I would have liked to draw more levels, but there was some polishing left to do (namely, the game finished screen).

0:10 : Game finished screen is over. Let’s start packaging the stuff.

0:05 : Last minute bug fix: apparently the overflow:hidden on the tile map behaved badly when the try again and select level elements were floated to the right and were past a certain height (on certain browsers). I add a clear:both to the tile map.

0:00 : as expected, I don’t have zip on my server, my aptitude cache is not up to date, and I don’t want to risk spending 10 minutes updating it. I should have fixed that before the contest! Still. I tar-gzip the stuff, download it on a Windows computer, extract it then turn it into a zip file, and upload it back to the server. There’s no time hunting for capn_midnight’s mail address, so I just post the links in the thread.

-0:05 : I manage to locate the captain’s address, so I mail the file there.

-0:10 : ?????

-0:15 : Profit.

http://en.wikipedia.org/wiki/Q*bert

Handwriting – Apple’s new License Agreement

Published
by
Victor Nicollet
on April 9, 2010
in Functional
. 0 Comments

The latest development in the fight against 1984 is the latest License Agreement for Apple’s iPhone developer platform, which includes a new constraint on allowed applications:

3.3.1 — Applications may only use Documented APIs in the manner prescribed by Apple and must not use or call any private APIs. Applications must be originally written in Objective-C, C, C++, or JavaScript as executed by the iPhone OS WebKit engine, and only code written in C, C++, and Objective-C may compile and directly link against the Documented APIs (e.g., Applications that link to Documented APIs through an intermediary translation or compatibility layer or tool are prohibited).

There should be no problem if you play by the rules and write your software in the specified languages. Conversely, you can expect to have problems if you write your application in a different language (say, ActionScript 3) and use a program to compile and link that against the iPhone API.

There’s a grey area in-between. Suppose for a moment that you originally wrote your software in a different language (say, a Java application on Android).

Can you rewrite that software in Objective C?

Can you outsource the project to a software sweatshop in India to have it rewritten it in Objective C?

Can you have that sweatshop define an API that your Java application has to use, to help them translate instructions in the iPhone API setting?

Can that sweatshop use automatic translation routines that work on 5% of the code (such as changing source file extensions, turning “private” into “@private”…), and finish the remaining 95% by hand?

What if the tools translate 95% of the original Java into clean and readable Objective C, and there’s only 5% left to do by hand?

What if the tools handle 99,99% of the translation work, and the remaining 0,01% is mostly typing in the project’s name and a few configuration elements such as indentation style or source and destination folders?

And, if you manage to find automatic translation routines that work so well and efficiently 99,99% of the work is done by the click of a button, is it really important if the resulting code isn’t easy to read or modify?

Where is the line drawn? And is Apple going to require the application source code, in order to check?

Can Apple require that all your source code listings be handwritten?

PHP 5.3 Closures as Block Literals?

Published
by
Victor Nicollet
on March 4, 2010
in Functional
. 0 Comments

I explained earlier a few things about writing reusable CSS code, and how it interacted with PHP. Let’s start with this basic HTML for generating two columns, with the right one being flexible and resizing to fill all available space:

<div class="col2">
  <div class="col2-l">
    [Content of left column]
  </div>
  <div class="col2-r">
    <div class="col2-ri">
      [Content of right column]
    </div>
  </div>
  <div class="clearer"></div>
</div>

.col2    { }
.col2-l  { float: left ; padding: 0 ; margin: 0 ; width: 120px }
.col2-r  { padding: 0 0 0 120px ; margin: 0 ; width:auto }
.col2-ri { float: left ; width : 100% }
.clearer { clear: both }

Elementary PHP

How does this translate to PHP? Basically as a series of constants (plus documentation detailing what the column HTML should look like):

class CSS_Col2
{
  const ROOT = "col2";
  const LEFT = "col2-l";
  const RIGHT = "col2-r";
  const RIGHT_INNER = "col2-ri";
}

This serves both as documentation for the existence of this component, and as an entry in the auto-completion tool to avoid typing incorrect classes by mistake. However, you still have to get the actual code right:

<div class="<?=CSS_Col2::ROOT?>">
  <div class="<?=CSS_Col2::LEFT?>">
    [20 lines of left column here]
  </div>
  <div class="<?=CSS_Col2::RIGHT?>">
    <div class="<?=CSS_Col2::RIGHT_INNER?>">
      [40 lines of right column here]
    </div>
  </div>
  <?CSS::CLEARER?>
</div>

Did I write everything correctly? Did I forget or misplace a clearer? Forgetting about the inner container in the right column is an easy mistake, and you won’t notice it until you put a clearing element in that column. And if your script is long enough, you won’t be able to see which opening tag matches which closing tag. Surely there must be a way to improve this.

Using HTML constants

A possibility is using constants to contain the relevant HTML:

class CSS_Col2
{
  // as above ...
  const _BEGIN_LEFT = '<div class="col2"><div class="col2-l">';
  const _BEGIN_RIGHT = '</div><div class="col2-r"><div class="col2-ri">';
  const _END = '</div></div><div class="clearer"></div>';
}

This makes code shorter, and you can’t mismatch or misplace tags as easily:

<?=CSS_Col2::_BEGIN_LEFT?>
  [20 lines of left column here]
<?=CSS_Col2::_BEGIN_RIGHT?>
  [40 lines of right column here]
<?=CSS_Col2::_END?>

However, all benefits of a nice and clean HTML editor are lost, because HTML constants don’t react as code, and there is therefore no validation performed. At least Eclipse could detect mismatching open/closing tags on raw HTML. Now, if you forget to “_END” your columns, your life is pain.

Using helpers

A common technique is to use a helper function for such rendering tasks. The function accepts some arguments that let it configure what ought to be displayed, then renders the wrapper HTML and inserts the data. Staying within the previous code:

class View_Helper_Col2
{
  static function Render($left, $right)
  {
    ?>
<div class="<?=CSS_Col2::ROOT?>">
  <div class="<?=CSS_Col2::LEFT?>">
    <?php call_user_func($left); ?>
  </div>
  <div class="<?=CSS_Col2::RIGHT?>">
    <div class="<?=CSS_Col2::RIGHT_INNER?>">
      <?php call_user_func($right); ?>
    </div>
  </div>
  <?CSS::CLEARER?>
</div><?
  }
}

I used callbacks here to do the rendering, because they are the most versatile (it sure beats having to instantiate a “renderable” class for each column). This approach provides the obvious benefit that now the entire rendering is taken care of by a single function, so there is no risk of forgetting or misplacing a tag, and the auto-completion tool can now help check which arguments are provided and in what order.

Still, this means that one should create two functions to render the two columns, and that any necessary data should be made available to them (due to the absence of closures in PHP < 5.3, this often means calling a member function of a view object containing the appropriate data). In the Zend Framework, for instance, one would just write two helpers, and provide them as callbacks knowing that they will have access to the data of the current view:

<?php
  $this->render2col(
    array($this,'myLeftCol'),
    array($this,'myRightCol')
  );
?>

Of course, it’s questionable whether moving a three-line for-each loop to a helper of its own actually increases the readability of the code. If defining a new class for every view, there’s the possibility of defining the columns as member functions within that same class, but it’s still somewhat awkward.

Helpers and Closures

PHP 5.3 introduces closures and optional arguments. This means that one can now write the behavior inline:

<?php
 $self = &$this;
 $this->render2col(
   function() use($self)
   {
     ?><h1><?=esc($self->user->name)?></h1><?php
   },
   function() use($self)
   {
     ?><ul><?php foreach ($self->items as $item): ?>
       <li><?php $self->render($item); ?></li>
     <?php endforeach; ?></ul><?php
   }
 );

However, making those functions inline creates a new issue: its not so obvious anymore what exactly a function is doing (because it’s too far away from the original call to the helper function). This can be solved by using a command pattern (while simultaneously noticing that one can get rid of the use keyword by providing $self as an argument (the helper does that):

<?php
 View_Col2::start($this)

 ->left(function($view){
   ?><h1><?=esc($view->user->name)?></h1><?php
 })

 ->right(function($view){
   ?><ul><?php foreach ($view->items as $item): ?>
     <li><?php $view->render($item); ?></li>
   <?php endforeach; ?></ul><?php
 })

 ->render();

Labels are now clearly mentioned, allowing empty lines to be inserted to separate the columns without forgetting what they are, so that the code looks cleaner overall.

JavaScript (Un)Maintenance Trick

Published
by
Victor Nicollet
on February 16, 2010
in Functional
. 1 Comment

You’re hunting your codebase for bugs, and doing some refactoring and cleanup along the way. You stumble across a classic WTF, if (x == true), and decide to replace it with the shorter if (x).

The trouble is that you’re playing with JavaScript here, and the two are not the same.

This is the story of why [] == ![] is true.

First, the logical-not operator «!» is defined quite simply by the ECMA standard (§11.4.9) as evaluating its argument, converting it to a boolean, and returning true if it was false, and false otherwise. Converting the argument to a boolean is defined (§9.2) as returning true for objects. Since arrays are objects, it makes sense that ![] evaluates to false.

Second, the comparison operator «==» is defined by the standard (§11.9.3) in a rather complex way: first, if its two operands are not of the same type, some type conversion occurs. The first step is that, if an operand is a boolean, it is turned into a number. So, ![] becomes 0.

The next step is, if one operand is a number and the other is an object, to turn the object into a primitive. This conversion is defined (§9.1) as calling the [[DefaultValue]] internal method, which in turn is defined (§8.12.8) as calling methods valueOf() and toString() until one of them returns a number or string. In the case of an array, the former returns the array itself (§15.2.4.4) and the latter calls join() (§15.4.4.2), which will concatenate all values inside the array, separated by commas (§15.4.4.5).

In the case of an empty array, this yields the empty string.

The third and final step is, if an operand is a number and the other is a string, to turn the string into a number (through a lengthy process described in §9.3.1) and compare the two. An empty string becomes zero, so the comparison is true.

Does your brain hurt, yet?

Back to the original question: if([] == true) does not run, but if([]) does.

DOM removal and events

Published
by
Victor Nicollet
on January 7, 2010
in Functional
. 4 Comments

Let’s try something… go to a page with jQuery enabled (such as this one), and run the following code in your Javascript debugger console (such as Firebug):

var button =
  $('<button>Click me</button>')
  .click(function(){alert('Clicked!')})
  .appendTo('body')

In case you were wondering, this creates a brand new button, causes it to display a “Clicked!” message box when it’s clicked, and appends it to the document you are viewing.

Click on the button that just appeared : the message box appears. Not very surprising.

Now, run the following code on the same page :

$('body').html('');
button.appendTo('body')

As expected, everything on the page, including the button, disappears. However, the button is still referenced by the button variable, so it sticks around and we can append it back to the document. And indeed, it does appear on the page.

Click on the button again. This time, no message box appears.

I honestly have no idea why.

Interest(ing) rates

Published
by
Victor Nicollet
on January 6, 2010
in Functional
. 0 Comments

The most common way of investing money is putting it in a savings account. You lend a fixed amount of money to someone, and they pay interest over that money at a predetermined rate. Let’s say you lend 1,000 € at an interest rate of 3%, paid every year: at the end of the year, you would receive 30 € as payment for your lending. You would spend these on fine wine or nice clothes and wait until the next year to get another 30 €, and so on.

Savings accounts work on the basis of simple interest : what you get paid is a linear function of both time and money. Lend for half a year? 3% ÷ 2 = 1.5% Lend for two years? 3% ×2 = 6%

An important thing to bear in mind is that interest is paid at fixed intervals, for instance at the beginning of January. You don’t have to spend those 30 € : you can them on the savings account and earn simple interest on them after a year (3% of 30 € is 0.90 €).

Using this strategy, lending for two years is done at a 6.09% rate instead of 6%, because you get interest on interest. This is known as compound interest : what you get paid is an exponential function of time. Lend for two years ? (+3%)² = +6.09% Lend for three years ? (+3%)³ = +9,27%

The mathematical justification is that, with a 3% interest, your total amount of money is multiplied by 1.03 every year:

1,000 + 30 = 1,000 + 3% of 1,000 = 1,000 + 0.03 × 1,000 = 1.03 × 1,000

So, after two years, the amount is multiplied by 1.03 two times, and so on.

1,060.90 = 1.03 × 1,030 = 1.03 × 1.03 × 1,000

In short, percentages have a multiplicative effect.

And now, pop quiz : I’ve gained +5% weight over the winter holidays. What percentage of my weight do I have to lose to be back to normal ?

If you answered -5%, you missed the point. Multiplicative effect means the total change of weight would be +5% × -5% = 1.05 × 0.95 = 0.9975 = -0.25%. I would be losing too much weight !

The correct answer was 1 ÷ 1.05 = -4.76%.

Similarly, if the number of graduates of a given school increases by +10% on year one and +25% on year two, the total increase is +37.5% and not +35%.

Duality

This is where mathematicians (and computer scientists) use an interesting little concept called duality. Percentages are numbers that are easy to understand, but hard to combine. We can transform them into something that is a little bit harder to understand, but easier to combine.

The traditional way to transform multiplication into addition is to exponentiate, due to an interesting property of the exponential function:

exp(a) ×exp(b) = exp(a + b)

So, I wish to find a percentage operator (§) such that:

  • we conserve some values, 0§ = 0% and 100§ = 100%
  • applying A§, then B§, is equivalent to applying (A+B)§

Then this uniquely defines an operator which is called exponential percentage:

A§ = B%  ↔  A = 100 × log(1 + B ÷ 100) ÷ log(2)

Some common values:

0% = 0§ +100% = +100§ -100% = -∞§ 200% = 158.4§
+1% = +1.4§ +99% = +99.2§ -1% = -1.4§ -99% = -664§
+10% = +13.7§ +90% = +92.6§ -10% = -15.2§ -90% = -332§
+25% = +32.2§ +75% = +80.7§ +50% = +58.4§ -50% = -100§

percent

So, if I gained +5§ weight over the holidays, I can lose -5§ weight and be back to where I started, and if a number increases by 10§, then by 25§, it increases by 35§ overall.

And of course, a yearly interest rate of 4.2§ = 3% compounded over ten years is 42§ = 34%.

No Free Lunch

Normal percentage rules make compounding hard, but it’s reasonably easy to estimate a percentage based on a fraction. Exponential percentage rules make compounding easy, but evaluating a percentage based on real figures is harder.

In practice, compounding happens less often than evaluating, so humans use normal percentage rules. And computers are good at compounding through multiplication, so they don’t need exponentiation.

Duality does have some other uses, though. For instance, there’s the duality between two representations of complex numbers:

a + ib = r exp iθ

The cartesian (a,b) notation makes it easier to add numbers, but multiplication is harder:

a + ib + c + id = (a+c) + i(b+d)

The polar (r,θ) notation makes it easier to multiply numbers, but addition is harder:

r exp iθ × s exp iφ = (r × s) exp i(θ+φ)

For mathematically-oriented computer scientists, duality is a gold mine, because it lets one reduce a complex problem in one area to a simpler problem in another area (whether simpler means faster, as in the case of FFT, or easier to think about)..

The Law of DSLs

There’s one common duality that is fundamental in the computer world: the correspondence between data and code. In a fit of narcissism, let me sit wisely atop a tall mountain to announce Nicollet’s Law of Domain Specific Languages:

Any sufficiently complex data processing algorithm is as an interpreter for a small domain-specific language, and the data being processed is a program executed by the interpreter.

In some cases, this law only complicates things further. In many cases, however, the different angle it provides leads to many advantages, one of them being to transform a non-programming concept (such as an accounting file format) into a concept programmers are familiar with (a programming language).

A minimalist language design culture is enough to grasp several interesting concepts about executing code, which can be quite handy when processing data:

1. Compile to Bytecode

Interpreters don’t execute a string of characters. They tokenize that string, turn the tokens into an abstract syntax tree representing operations, functions and variables, then turn that syntax tree into a sequence of small, executable operations. That sequence is then fed into a virtual machine (or further compiled to machine code) to perform the actual operations.

If the input data for your algorithm is very complex, you can begin on the other side: what will the algorithm do with the data? Will it be inserting the data into a database? Constructing a data object from bits and pieces? What you are looking for is a set of atomic operations you can apply to generate the result. Implement these operations, then start working on a translation algorithm to turn the input data into such operations.

There are several common and friendly representations for such atomic bytecode:

Instruction lists are executed in order. This is your classic assembler listing, without the jumps. A typical “parse file and insert into database” algorithm would generate such an instruction list, and every instruction would be an INSERT, DELETE or UPDATE. Works best when you can read the data and generate the instructions in the right order: if you cannot get the list in the right order from the start, consider another approach.

Dependency graphs work like makefiles: you have several instruction lists floating around with relationships between them, indicating that one list has to be executed before another. A topological sort of the graph results in a single classic instruction list you can execute. A multi-file import, where some files contain data needed in other files, can be the way to go.

Nested scopes are the typical extension to instruction lists: every item in a list can be either an instruction, or another list, possibly tagged with some data. This could be a conditional (if this condition is true, execute this list), a loop (though it is best to avoid these) or a context (a “polygon” scope contains “insert vertex” operations that apply to that polygon). You can even allow variables in a let-in fashion (of which the polygon example above is just a special case) ! Note that nested scopes can be easily represented as XML.

2. Static Analysis

A side-effect of compiling to bytecode is that you get to process the entire file before you actually perform the intended operations. This makes a rollback easier if you notice that there’s an error on the last line of the file: if you make sure that no atomic operation in your target language can fail due to bad input (such as incorrect data values), then you can check your input data for correctness without doing anything to your program state.

Even better, if your compilation process is cheap (linearly traverse a file for parsing) and you have heuristics for predicting how much time and resources your individual instructions require, then you can try to accurately predict the needs of the entire process.

Static analysis also means you can optimize. If, for instance, you’re inserting data into a database and need to resolve names or keys frequently (such as “add this item to list #732″), you can easily construct a table of needed keys (that you can get in one query when the processing starts) using the dependency graph approach.You can also optimize resource allocation by using common register allocation techniques: sort your dependency graph to keep as few resources in memory as possible at any given time.

3. Caching

Try to perform most of the processing offline.

For instance, if you frequently “apply” one file to another, such as a nearly-constant “list of categories” file used to resolve the “category” key in a daily object import, you can benefit from compiling the nearly-constant file to an easily loaded, easily applied format.

You see a cached dictionary that maps keys to categories? I see a DSL that allows dictionary literals as part of the language, and a source file that contains a literal mapping keys to categories, with an interpreter that can apply constant propagation to dictionaries.

Another benefit is when applying changes to mission-critical software. Inserting lots of data into a web database can create a heavy load on the server and make the site unavailable to visitors. It might therefore be preferrable to pre-compile the imported data into requests through a process that keeps a light load on the server, then run the requests.

Besides, with proper nested scoping, you can slice an import into several transactions. This keeps the lock count low, allows spreading the transactions over time to reduce the load, and lets you resume the import process if, for some reason, it gets interrupted.

December 2009 PDF Vulnerability

Published
by
Victor Nicollet
on January 5, 2010
in Functional
. 0 Comments

All file formats follow the same evolution.

  1. They start by grouping together some static content, with some nifty features for presenting and editing that data. Think text files, bitmaps, RTF documents… The file format is reasonably easy to understand, and the reader/writer is so simple that it would take a bad programmer to create vulnerabilities.
  2. Then, they start including plug-ins that let them handle more and more types of contents. This lets you include an image inside an HTML page or an Excel spreadsheet in a Word document. This relies on many plugins for getting things right. It sometimes happens that a given plugin contains a security fault that can then be exploited, for instance Internet Explorer had an issue with images in PNG format. The user would visit a page, that page would display an image, and the computer would be contaminated.
  3. Finally, they need to become interactive, so they include a scripting language of some sort. Excel has a macro system that uses Visual Basic, HTML includes Javascript…

The PDF format followed the same process to end up where it is now. In addition to any static document data (text, vector and raster images) and extended content (flash animations, videos, reader extension signatures) a PDF also contains short JavaScript that let authors create interactive documents. This means a PDF document on your desktop can:

  • Accept user input (such as checkboxes or text fields). The input can be saved to the disk if the reader supports it and allows it (Acrobat Reader, used by the vast majority of computer users, only allows saving a file if its author purchased a reader extensions license and signed the PDF file with it).
  • Change its layout at will, for instance displaying a “spouse” page only if the “spouse” checkbox was ticked.
  • Be cryptographically signed, and display information about who signed it. This kind of signature is actually accepted as valid legal proof in many countries.
  • Compute a scannable bar code from user input, so that it can be printed, then scanned on the other side with reduced error rates.
  • Send data over the internet. It can even send itself as an attachment to an email.

Needless to say, with all these features, there are inevitably going to be some exploitable security issues in the mix. Being a popular program, like Acrobat Reader, only increases the number of black hat hackers looking for vulnerabilities. One of these is the recent CVE-2009-4324 from December 2009. There are many types of vulnerabilities, their common feature being that they end up executing arbitrary operations on the computer (as opposed to the safe operations Acrobat Reader normally allows). These operations are usually to download or install trojans, so that the attacker can gain complete control over the computer.

CVE-2009-4324 is of the use-after-free kind. In short:

  • it creates a resource (which uses some memory),
  • it frees (destroys) the resource to recycle its memory,
  • it writes something to that memory,
  • it attempts to use the resource

Normally, the program should stop at step four and say “you can’t use the resource, it’s been destroyed”. A bug can cause it to believe that the resource is still there. The programmer probably assumed that the memory still contained a valid resource and did defend against the memory containing something else… and accessing that as if it were a valid resource executes some code that the attacker wanted to execute. Bingo.

In the case of CVE-2009-4324, this happens as part of the Doc.media.newPlayer method which, for performance reasons, was not completely implemented in Javascript—a bug in some Javascript code can cause the document to misbehave, but it cannot do anything that the Javascript couldn’t do on its own. Those parts that were written in a lower-level language, with access to the computer, contained the exploited bug.

The bug causes the processor to start executing code at a different memory location. In an ideal hacker world, that location would be precisely where some nasty code is present. Buffer overflows, when used to rewrite pieces of the stack, do allow such deterministic jumps. However, CVE-2009-4324 only allows a jump to an undetermined location.

The hacker solution is to use heap spray. The basic idea is that you have a short piece of code you want to execute (the payload). You create a block from that payload by adding no-ops (machine instructions that say “skip me”) before the payload. Then, you create lots of these blocks in memory, and trigger the exploit.

The exploit causes the computer to jump to an undetermined memory location. If it falls within the no-op section of any of the blocks you’ve created, you win: the computer skips over the no-ops, reaches the payload and executes it. If not, the program will crash. Too bad…

693 feed subscribers
(readers who polled a feed this week)