Posts in the coding category:

  1. Google Interview Part 1 03 Nov 2009
  2. Multiple window.onload functions in JavaScript 01 Jun 2009
  3. Get and Set 27 Apr 2009
  4. Lambda 22 Aug 2008
  5. Installing Pubcookie 3.3 on Ubuntu 7.10 with Apache 2 29 Dec 2007

REXML could not parse this XML/HTML: 
<div class="posts">

    <div class="post">
        <div class="meta">
            <a name="/2009/11/google-interview-part-1" />
            <h2><a href="/2009/11/google-interview-part-1/">Google Interview Part 1</a></h2>
            <div class="date">03 Nov 2009</div>
        </div>
        <div class="content">
        <p>So I had my first Google interview last week. I submitted an online resume and cover letter and was asked to come in for a 1.5-hour, 2-session interview on campus. (No, I&#8217;m no longer a student. I guess that doesn&#8217;t matter.) I got asked in about a month after submitting a resume.</p>

<p>Here&#8217;s a brief summary on how each of the interview sessions went. It&#8217;s a bit sloppy, but you can deal with that.</p>

<h3 id='the_first'>The First</h3>

<p>Friendly software test guy. Not super chatty but nice.</p>

<p>Question:</p>

<blockquote>
<p>Design an algorithm to visit every room in a building once.</p>
</blockquote>

<p>This was really open-ended: there were no constraints on what the structure of the input might be. &#8220;You decide&#8221; was the response for most questions I asked about clarifications.</p>

<p>Since I knew I was going to have to code this up, I decided on using an adjacency matrix to represent the graph of rooms. This also turned out to be wise because your solution can be optimized very easily.</p>

<p>The answer is pretty easy. I&#8217;ll let you write the code, but here&#8217;s a pretty detailed description of the algorithm and data structure used:</p>

<pre><code>Ryan&#39;s Room Algorithm
-----------------------
Let A be the square adjacency matrix of size n by n with
  A_i,j = A_j,i = 1 if room i is connected to room j and
  0 otherwise.  Represent this as n arrays of n boolean
  values:  boolean A[n][n]; If you have rooms A, B, C, D
  with a door between A-&gt;B-&gt;C-&gt;D, your matrix would look
  like this:
        [[ 1 1 0 0 ]
         [ 1 1 1 0 ]
         [ 0 1 1 1 ]
         [ 0 0 1 1 ]]
Let V be an empty collection of rooms (can use size-n
  array or a hash table or ....).
Function Do(Room R):
    For each entry E in A[R]
    if E is not in V, go from R to E and put E in V
    Perform Do(E)
    Go back from E to R
You will end up back in R and will have visited every
  reachable room.</code></pre>

<p>This is, of course, O(n^2) space, and it turns out to be O(n^2) time complexity as well. You can do much better by using a simple Java class:</p>

<pre><code>class Room {
    int name;
    ... other data
    Collection&lt;Room&gt; children;
}</code></pre>

<p>You can use a <code>HashMap&lt;Room,Boolean&gt;</code> for your <code>V</code> in the above algorithm, and your solution ends up being O(n) worst-case in both time and space. I was asked specifically about the optimizations that might be made if there were <em>lots</em> of other data about the rooms and if there were millions of rooms. Specifically, you might want to leave the <code>Room</code> Java class pretty small and make it have a pointer to a <code>RoomData</code> object for the other data about the room. Make this accessible via a method like <code>getRoomData()</code> or something so it can be made to do lazy initialization from the disk if necessary. Note that <code>V</code> isn&#8217;t really something you need to worry about.</p>

<p>Then I was asked how I would test my solution. I drew some graph structures that might cause problems including an empty graph, a disconnected graph (sets of rooms that aren&#8217;t connected to any other sets of rooms):</p>

<pre><code>+---+    +---+       +---+    +---+
| A | -&gt; | B |       | C | -&gt; | D |
+---+    +---+       +---+    +---+</code></pre>

<p>and cycles (<code>A-&gt;B-&gt;C-&gt;A</code>). The interviewer was very happy with my answers.</p>

<p>Important that you should think of other implementations: this might have been implemented using a <code>Stack&lt;Room&gt;</code> or something of that sort, so giving a test case where that sort of thing might end in an infinite loop is wise.</p>

<h3 id='the_second'>The Second</h3>

<p>Really nice software engineer on the search team.</p>

<p>Question:</p>

<blockquote>
<p>Given a <code>List&lt;List&lt;T&gt;&gt;</code>, write an implementation for an <code>Iterator&lt;T&gt;</code>.</p>
</blockquote>

<p>This is a &#8220;list of lists of items of type <code>T</code>&#8221;, and you&#8217;re asked to write an <code>Iterator</code> that returns the next <code>T</code>. (I didn&#8217;t remember everything the <code>Iterator</code> interface had, but the important bits are the <code>next()</code> and <code>hasNext()</code> methods.)</p>

<p>This is actually surprisingly easy if you use anonymous classes. This is a good way to show off your question-asking ability, though like what the structure of the data might look like (are there allowed to be null values for the &#8220;inner&#8221; list:</p>

<pre><code>List&lt;T&gt; |  List&lt;T&gt; |  null | List&lt;T&gt; | List&lt;T&gt;</code></pre>

<p>and what is the expected behavior of it, etc. Say &#8220;as long as it&#8217;s documented you can do whatever you want.&#8221; Developers love that kind of thing. PMs and users hate it, but you&#8217;re being jovial with a coder here, right?</p>

<p>Using an anonymous inner class was deemed to be a good solution by my interviewer who hadn&#8217;t thought of doing something so clever. I decided to declare that there could be no inner null lists. Each element of the list of lists had to be a valid list of items. This makes the coding a <em>lot</em> easier.</p>

<p>Here&#8217;s a very basic outline of my solution:</p>
<div class='highlight'><pre><code class='java'><span class='kd'>class</span> <span class='nc'>ListOfList</span><span class='o'>&lt;</span><span class='n'>T</span><span class='o'>&gt;</span> <span class='kd'>implements</span> <span class='n'>Iterable</span><span class='o'>&lt;</span><span class='n'>T</span><span class='o'>&gt;</span> <span class='o'>{</span>
    
    <span class='kd'>private</span> <span class='n'>List</span><span class='o'>&lt;</span><span class='n'>List</span><span class='o'>&lt;</span><span class='n'>T</span><span class='o'>&gt;&gt;</span> <span class='n'>data</span><span class='o'>;</span>
    
    <span class='kd'>public</span> <span class='n'>Iterator</span><span class='o'>&lt;</span><span class='n'>T</span><span class='o'>&gt;</span> <span class='n'>iterator</span><span class='o'>()</span> <span class='o'>{</span>
        <span class='n'>ListOfList</span><span class='o'>&lt;</span><span class='n'>T</span><span class='o'>&gt;</span> <span class='n'>self</span> <span class='o'>=</span> <span class='k'>this</span><span class='o'>;</span>
        
        <span class='k'>return</span> <span class='k'>new</span> <span class='n'>Iterator</span><span class='o'>&lt;</span><span class='n'>T</span><span class='o'>&gt;()</span> <span class='o'>{</span>
            <span class='n'>Iterator</span><span class='o'>&lt;</span><span class='n'>List</span><span class='o'>&lt;</span><span class='n'>T</span><span class='o'>&gt;&gt;</span> <span class='n'>outer</span> <span class='o'>=</span> 
                <span class='n'>self</span><span class='o'>.</span><span class='na'>data</span><span class='o'>.</span><span class='na'>iterator</span><span class='o'>();</span>
            <span class='n'>Iterator</span><span class='o'>&lt;</span><span class='n'>T</span><span class='o'>&gt;</span> <span class='n'>inner</span> <span class='o'>=</span> <span class='n'>outer</span><span class='o'>.</span><span class='na'>next</span><span class='o'>();</span>
            
            <span class='kd'>public</span> <span class='kt'>boolean</span> <span class='nf'>hasNext</span><span class='o'>()</span> <span class='o'>{</span>
                <span class='k'>if</span> <span class='o'>(</span> <span class='o'>!</span> <span class='n'>outer</span><span class='o'>.</span><span class='na'>hasNext</span><span class='o'>()</span> <span class='o'>)</span> <span class='o'>{</span>
                    <span class='n'>outer</span> <span class='o'>=</span> <span class='n'>outer</span><span class='o'>.</span><span class='na'>next</span><span class='o'>().</span><span class='na'>iterator</span><span class='o'>();</span>
                    <span class='k'>return</span> <span class='nf'>hasNext</span><span class='o'>();</span>
                <span class='o'>}</span>
                <span class='k'>return</span> <span class='n'>inner</span><span class='o'>.</span><span class='na'>hasNext</span><span class='o'>();</span>
            <span class='o'>}</span>
            
            <span class='kd'>public</span> <span class='n'>T</span> <span class='nf'>next</span><span class='o'>()</span> <span class='o'>{</span>
                <span class='k'>if</span> <span class='o'>(</span> <span class='o'>!</span><span class='n'>hasNext</span><span class='o'>()</span> <span class='o'>)</span>
                    <span class='k'>return</span> <span class='kc'>null</span><span class='o'>;</span>
                <span class='k'>return</span> <span class='n'>inner</span><span class='o'>.</span><span class='na'>next</span><span class='o'>();</span>
            <span class='o'>}</span>
            
        <span class='o'>};</span>
    <span class='o'>}</span>   
<span class='o'>}</span>
</code></pre>
</div>
<p>I noted to the interviewer the &#8220;clever&#8221; use of recursion and how the assumptions work to my advantage. Also note that the assumption isn&#8217;t particularly reasonable (maybe) and that the code isn&#8217;t so clear at first, so there should be lots of documentation. Also note the slightly ugly usage of the <code>self</code> variable. Note why this is necessary (because the <code>this</code> keyword is scoped to the inner class) and discuss closures.</p>

<p>I was then asked about how to test it and what the complexities are. Testing is pretty easy; complexity is constant time (again using the assumptions).</p>

<p>I then asked the guy a bunch of questions about working for Google, and we chatted it up for about 20 minutes past when the interview was supposed to be finished. This was mostly about some interesting projects at Google but was also about my past projects and interests as well. It went long because the interviewer seemed to be legitimately enjoying the conversation.</p>

<p>In all, I think I&#8217;ll get a callback! The process was very &#8220;fair&#8221;: no &#8220;how would you move Mount Fuji&#8221; or weighing pills on balances questions; the questions were practical, open-ended and allowed me to show my stuff pretty well.</p>
        </div>
    </div>

    <div class="post">
        <div class="meta">
            <a name="/2009/06/multiple-windowonload-functions-in-javascript" />
            <h2><a href="/2009/06/multiple-windowonload-functions-in-javascript/">Multiple window.onload functions in JavaScript</a></h2>
            <div class="date">01 Jun 2009</div>
        </div>
        <div class="content">
        <p>Writing in JavaScript often requires triggering code to execute <em>after</em> the page has finished loading (that is, when the Document Object Model <em>DOM</em> is ready).</p>

<p>Say you want to set the contents of the document&#8217;s <code>&lt;title&gt;</code> tag to the contents of the first <code>&lt;h1&gt;</code> tag. Here is the na&#8221;ive solution:</p>
<div class='highlight'><pre><code class='html'><span class='nt'>&lt;html&gt;&lt;head&gt;&lt;title&gt;&lt;/title&gt;</span>
  <span class='nt'>&lt;script </span><span class='na'>type=</span><span class='s'>&quot;text/javascript&quot;</span> <span class='na'>charset=</span><span class='s'>&quot;utf-8&quot;</span><span class='nt'>&gt;</span>
  
    <span class='nb'>document</span><span class='p'>.</span><span class='nx'>title</span> <span class='o'>=</span>
        <span class='nb'>document</span><span class='p'>.</span><span class='nx'>getElementsByTagName</span><span class='p'>(</span><span class='s1'>&#39;h1&#39;</span><span class='p'>)[</span><span class='mi'>0</span><span class='p'>].</span><span class='nx'>innerHTML</span><span class='p'>;</span>
  
  <span class='nt'>&lt;/script&gt;</span>
<span class='nt'>&lt;/head&gt;&lt;body&gt;&lt;h1&gt;</span>Hello!<span class='nt'>&lt;/h1&gt;&lt;/body&gt;&lt;/html&gt;</span>
</code></pre>
</div>
<p>The problem, of course, is that this is executed while still in the <code>&lt;head&gt;</code> section: before the <code>&lt;body&gt;</code> has even been seen. Thus, when we ask for <code>document.getElementsByTagName(&#39;h1&#39;)</code>, we will get <code>null</code> back, and this will cause an error.</p>

<p>The solution is to wait until after the document has loaded:</p>
<div class='highlight'><pre><code class='html'><span class='nt'>&lt;html&gt;&lt;head&gt;&lt;title&gt;&lt;/title&gt;</span>
  <span class='nt'>&lt;script </span><span class='na'>type=</span><span class='s'>&quot;text/javascript&quot;</span> <span class='na'>charset=</span><span class='s'>&quot;utf-8&quot;</span><span class='nt'>&gt;</span>
  
    <span class='nb'>window</span><span class='p'>.</span><span class='nx'>onload</span> <span class='o'>=</span> <span class='kd'>function</span><span class='p'>()</span> <span class='p'>{</span>
        <span class='nb'>document</span><span class='p'>.</span><span class='nx'>title</span> <span class='o'>=</span>
            <span class='nb'>document</span><span class='p'>.</span><span class='nx'>getElementsByTagName</span><span class='p'>(</span><span class='s1'>&#39;h1&#39;</span><span class='p'>)[</span><span class='mi'>0</span><span class='p'>].</span><span class='nx'>innerHTML</span><span class='p'>;</span>
    <span class='p'>};</span>
    
  <span class='nt'>&lt;/script&gt;</span>
<span class='nt'>&lt;/head&gt;&lt;body&gt;&lt;h1&gt;</span>Hello!<span class='nt'>&lt;/h1&gt;&lt;/body&gt;&lt;/html&gt;</span>
</code></pre>
</div>
<p>This sets up a &#8220;callback&#8221; that the browser knows to execute as soon as it&#8217;s loaded the whole Document.</p>

<p>The problem, though, is that we might want <em>many</em> such functions to execute. Lots of (or at least more than one) <code>window.onload</code>. And if we overwrite the contents of <code>document.onload</code> as we&#8217;ve done here, then we&#8217;ve shot the rest of our code in the foot and thrown it out to the curb to die.</p>

<p>The solution is to create a <strong>stack</strong> of functions to execute and simply add them one by one. Then set <code>window.onload</code> to pop off all the functions on the stack and execute them using the <code>call()</code> method for functions.</p>

<p><a href='http://jquery.com'>jQuery</a> does this automatically. So we could simply have this in the <code>&lt;head&gt;</code> section:</p>
<div class='highlight'><pre><code class='html'><span class='nt'>&lt;script </span><span class='na'>type=</span><span class='s'>&quot;text/javascript&quot;</span> <span class='na'>charset=</span><span class='s'>&quot;utf-8&quot;</span><span class='nt'>&gt;</span>

    <span class='nx'>$</span><span class='p'>(</span><span class='kd'>function</span><span class='p'>(){</span>
        <span class='nb'>document</span><span class='p'>.</span><span class='nx'>title</span> <span class='o'>=</span> <span class='nx'>$</span><span class='p'>(</span><span class='s2'>&quot;h1:first&quot;</span><span class='p'>).</span><span class='nx'>html</span><span class='p'>();</span>
    <span class='p'>});</span>

<span class='nt'>&lt;/script&gt;</span>
</code></pre>
</div>
<p>&#8230;but if we didn&#8217;t have jQuery at our disposal, we could do this manually:</p>
<div class='highlight'><pre><code class='html'><span class='nt'>&lt;html&gt;&lt;head&gt;&lt;title&gt;&lt;/title&gt;</span>
  <span class='nt'>&lt;script </span><span class='na'>type=</span><span class='s'>&quot;text/javascript&quot;</span> <span class='na'>charset=</span><span class='s'>&quot;utf-8&quot;</span><span class='nt'>&gt;</span>
    
    <span class='c1'>// Prevent overwriting loadstack if it&#39;s already set:</span>
    <span class='kd'>var</span> <span class='nx'>loadstack</span> <span class='o'>=</span> <span class='nx'>loadstack</span> <span class='o'>||</span> <span class='p'>[];</span>
    
    <span class='c1'>// Add our function that changes the &lt;title&gt;</span>
    <span class='c1'>// to the contents of the first &lt;h1&gt;:</span>
    <span class='nx'>loadstack</span><span class='p'>.</span><span class='nx'>push</span><span class='p'>(</span><span class='kd'>function</span><span class='p'>(){</span>
        <span class='nb'>document</span><span class='p'>.</span><span class='nx'>title</span> <span class='o'>=</span>
            <span class='nb'>document</span><span class='p'>.</span><span class='nx'>getElementsByTagName</span><span class='p'>(</span><span class='s1'>&#39;h1&#39;</span><span class='p'>)[</span><span class='mi'>0</span><span class='p'>].</span><span class='nx'>innerHTML</span><span class='p'>;</span>
    <span class='p'>});</span>
    
    <span class='c1'>// ... lots of other additions to the loadstack ...</span>

    <span class='c1'>// this *must* be the last code in the &lt;head&gt;</span>
    <span class='c1'>// section&#39;s JS block (or at least the very last</span>
    <span class='c1'>// thing to touch window.onload):</span>
    
    <span class='k'>if</span> <span class='p'>(</span> <span class='nb'>window</span><span class='p'>.</span><span class='nx'>onload</span> <span class='p'>)</span>
        <span class='nx'>loadstack</span><span class='p'>.</span><span class='nx'>push</span><span class='p'>(</span><span class='nb'>window</span><span class='p'>.</span><span class='nx'>onload</span><span class='p'>);</span>
    
    <span class='nb'>window</span><span class='p'>.</span><span class='nx'>onload</span> <span class='o'>=</span> <span class='kd'>function</span><span class='p'>()</span>
    <span class='p'>{</span>
        <span class='k'>while</span> <span class='p'>(</span> <span class='nx'>loadstack</span><span class='p'>.</span><span class='nx'>length</span> <span class='o'>&gt;</span> <span class='mi'>0</span> <span class='p'>)</span>
            <span class='c1'>// `this` will be bound to the window object</span>
            <span class='c1'>// inside the called function</span>
            <span class='nx'>loadstack</span><span class='p'>.</span><span class='nx'>pop</span><span class='p'>().</span><span class='nx'>call</span><span class='p'>(</span><span class='k'>this</span><span class='p'>);</span>
    <span class='p'>};</span>
  <span class='nt'>&lt;/script&gt;</span>
<span class='nt'>&lt;/head&gt;&lt;body&gt;&lt;h1&gt;</span>Hello!<span class='nt'>&lt;/h1&gt;&lt;/body&gt;&lt;/html&gt;</span>
</code></pre>
</div>
<p>Adding code to execute is simple as this:</p>
<div class='highlight'><pre><code class='javascript'><span class='nx'>loadstack</span><span class='p'>.</span><span class='nx'>push</span><span class='p'>(</span><span class='kd'>function</span><span class='p'>(</span><span class='nx'>win</span><span class='p'>){</span>
    <span class='c1'>// code to execute here.</span>
    <span class='c1'>// (win is the window object if you need it)</span>
<span class='p'>});</span>
</code></pre>
</div>
<p>All said, I usually just use jQuery&#8217;s built-in handling of this, but it&#8217;s nice to know that it&#8217;s pretty easy to to it all ourselves if we had to.</p>
        </div>
    </div>

    <div class="post">
        <div class="meta">
            <a name="/2009/04/get-and-set" />
            <h2><a href="/2009/04/get-and-set/">Get and Set</a></h2>
            <div class="date">27 Apr 2009</div>
        </div>
        <div class="content">
        <p>Although I work with Java on a regular basis at work, I&#8217;ve long been scared away from Java for personal projects based solely on its verbosity.</p>

<p>Rather than having object members (&#8220;properties&#8221;) be declared public, Java tends to have everything declared private and then accessed for reading/writing via &#8220;getters&#8221; and &#8220;setters.&#8221; So if a Document object has a <code>title</code> property, the Document class would likely have the methods <code>String
getTitle()</code> and <code>void setTitle(String t)</code>.</p>

<p>What is simpler, however, is to overload a method having the same name as the property. When called with <em>no</em> arguments, the method serves as the <em>getter</em>, and when called <em>with</em> a single argument, the method serves as a <em>setter</em> - setting the value to the indicated argument.</p>

<p>This is less verbose and more in-line with what happen &#8220;nowadays&#8221; with the more scripting-inclined languages like Ruby and PHP.</p>

<p>The old way:</p>
<div class='highlight'><pre><code class='java'><span class='n'>Document</span> <span class='n'>d</span> <span class='o'>=</span> <span class='k'>new</span> <span class='n'>Document</span><span class='o'>();</span>
<span class='n'>String</span> <span class='n'>oldTitle</span> <span class='o'>=</span> <span class='n'>d</span><span class='o'>.</span><span class='na'>getTitle</span><span class='o'>();</span>
<span class='n'>d</span><span class='o'>.</span><span class='na'>setTitle</span><span class='o'>(</span><span class='s'>&quot;New Title&quot;</span><span class='o'>);</span>
</code></pre>
</div>
<p>The new way:</p>
<div class='highlight'><pre><code class='java'><span class='n'>Document</span> <span class='n'>d</span> <span class='o'>=</span> <span class='k'>new</span> <span class='n'>Document</span><span class='o'>();</span>
<span class='n'>String</span> <span class='n'>oldTitle</span> <span class='o'>=</span> <span class='n'>d</span><span class='o'>.</span><span class='na'>title</span><span class='o'>();</span>
<span class='n'>d</span><span class='o'>.</span><span class='na'>title</span><span class='o'>(</span><span class='s'>&quot;New Title&quot;</span><span class='o'>);</span>
</code></pre>
</div>
<p>And here is a sample POJO <em>&#8220;Plain Old Java Object&#8221;</em> that utilizes this:</p>
<div class='highlight'><pre><code class='java'><span class='kd'>class</span> <span class='nc'>MyDocument</span>
<span class='o'>{</span>

    <span class='kd'>private</span> <span class='n'>String</span> <span class='n'>title</span><span class='o'>;</span>

    <span class='kd'>public</span> <span class='nf'>MyDocument</span><span class='o'>()</span>
    <span class='o'>{</span>
    <span class='o'>}</span>

    <span class='kd'>public</span> <span class='n'>String</span> <span class='nf'>title</span><span class='o'>()</span>
    <span class='o'>{</span>
        <span class='k'>return</span> <span class='n'>title</span><span class='o'>;</span>
    <span class='o'>}</span>

    <span class='kd'>public</span> <span class='kt'>void</span> <span class='nf'>title</span><span class='o'>(</span><span class='n'>String</span> <span class='n'>t</span><span class='o'>)</span>
    <span class='o'>{</span>
        <span class='k'>this</span><span class='o'>.</span><span class='na'>title</span> <span class='o'>=</span> <span class='n'>t</span><span class='o'>;</span>
    <span class='o'>}</span>

<span class='o'>}</span>
</code></pre>
</div>
<p>Just my $0.02.</p>
        </div>
    </div>

    <div class="post">
        <div class="meta">
            <a name="/2008/08/lambda" />
            <h2><a href="/2008/08/lambda/">Lambda</a></h2>
            <div class="date">22 Aug 2008</div>
        </div>
        <div class="content">
        <p><a href='http://php.net'>PHP</a> has been in dire need of some new features for some time. PHP 5.3 plans to add a <a href='http://www.php.net/archive/2008.php#id2008-08-01-1'>slew of new features</a>, <em>finally</em> adding lambdas a/k/a <em>anonymous functions</em> to the language.</p>

<p>That is&#8230; &#8230;once it gets out of alpha. Then out of beta. Then onto production systems.</p>

<p>(PHP haters can now stop sipping quite so much hater-ade in that PHP now also supports namespaces, but I don&#8217;t find that new feature particularly interesting.)</p>

<p>What makes lambdas so interesting is how much simpler and cleaner they can make your code.</p>

<p>Consider the problem of wanting to sort a list where some of the items have the words &#8216;The&#8217; or &#8216;A&#8217; as a prefix. We want to sort the list</p>

<ul>
<li>Beck</li>

<li>The Starting Line</li>

<li>Blue October</li>

<li>The All American Rejects</li>
</ul>

<p>to be</p>

<ul>
<li>The All American Rejects</li>

<li>Beck</li>

<li>Blue October</li>

<li>The Starting Line</li>
</ul>

<p>and <strong>not</strong></p>

<ul>
<li>Beck</li>

<li>Blue October</li>

<li>The All American Rejects</li>

<li>The Starting Line</li>
</ul>

<p>Without the use of lambdas, we have to do something like this in <em>old</em> PHP:</p>
<div class='highlight'><pre><code class='php'><span class='k'>function</span> <span class='nf'>stem_the</span><span class='p'>(</span><span class='nv'>$a</span><span class='p'>)</span>
<span class='p'>{</span>
    <span class='k'>return</span> <span class='nb'>preg_replace</span><span class='p'>(</span> 
    <span class='s1'>&#39;/^(a|the) *(.*)$/i&#39;</span><span class='p'>,</span> <span class='s1'>&#39;$2&#39;</span><span class='p'>,</span> <span class='nv'>$a</span> 
    <span class='p'>);</span>
<span class='p'>}</span>

<span class='k'>function</span> <span class='nf'>cmp_the</span><span class='p'>(</span><span class='nv'>$a</span><span class='p'>,</span><span class='nv'>$b</span><span class='p'>)</span>
<span class='p'>{</span>
    <span class='nv'>$a</span> <span class='o'>=</span> <span class='nx'>stem_the</span><span class='p'>(</span><span class='nv'>$a</span><span class='p'>);</span>
    <span class='nv'>$b</span> <span class='o'>=</span> <span class='nx'>stem_the</span><span class='p'>(</span><span class='nv'>$b</span><span class='p'>);</span>
    <span class='k'>return</span> <span class='nb'>strcmp</span><span class='p'>(</span><span class='nv'>$a</span><span class='p'>,</span><span class='nv'>$b</span><span class='p'>);</span>
<span class='p'>}</span>

<span class='nv'>$bands</span> <span class='o'>=</span> <span class='k'>array</span><span class='p'>(</span> <span class='s1'>&#39;The All American Rejects&#39;</span><span class='p'>,</span>
        <span class='s1'>&#39;Beck&#39;</span><span class='p'>,</span> <span class='s1'>&#39;Blue October&#39;</span><span class='p'>,</span>
        <span class='s1'>&#39;The Starting Line&#39;</span> <span class='p'>);</span>

<span class='nb'>usort</span><span class='p'>(</span> <span class='nv'>$bands</span><span class='p'>,</span> <span class='s1'>&#39;cmp_the&#39;</span> <span class='p'>);</span>
</code></pre>
</div>
<p><code>usort()</code>&#8217;s second argument is a <strong>string</strong>. This is really ugly. <em>Old</em> PHP didn&#8217;t have functions as first-class citizens, so that <em>was</em> the only way we could do something like this. It&#8217;s <em>ugly</em> and <em>slow</em>.</p>

<p>Moreover, we&#8217;re forced to create two functions <code>stem_the()</code> and <code>cmp_the()</code> (my names are always this creative). We&#8217;ve cluttered the global function namespace for our very trivial task.</p>

<p>Enter stage left, Dr. Martin Luther Lambda. His dream is promoting functions to first-class citizens&#8230;</p>

<p>With lambdas, we can rewrite that entire mess to be the clean, simple, <em>elegant</em> mess that follows:</p>
<div class='highlight'><pre><code class='php'><span class='nv'>$bands</span> <span class='o'>=</span> <span class='k'>array</span><span class='p'>(</span> <span class='s1'>&#39;The All American Rejects&#39;</span><span class='p'>,</span>
        <span class='s1'>&#39;Beck&#39;</span><span class='p'>,</span> <span class='s1'>&#39;Blue October&#39;</span><span class='p'>,</span>
        <span class='s1'>&#39;The Starting Line&#39;</span> <span class='p'>);</span>

<span class='nb'>usort</span><span class='p'>(</span> <span class='nv'>$bands</span><span class='p'>,</span> <span class='k'>function</span><span class='p'>(</span><span class='nv'>$a</span><span class='p'>,</span><span class='nv'>$b</span><span class='p'>)</span>
<span class='p'>{</span>
    <span class='k'>list</span><span class='p'>(</span><span class='nv'>$a</span><span class='p'>,</span><span class='nv'>$b</span><span class='p'>)</span> <span class='o'>=</span> <span class='nb'>array_map</span><span class='p'>(</span><span class='k'>function</span><span class='p'>(</span><span class='nv'>$s</span><span class='p'>)</span> <span class='p'>{</span>
    <span class='k'>return</span> <span class='nb'>preg_replace</span><span class='p'>(</span><span class='s1'>&#39;/^(a|the) *(.*)$/i&#39;</span><span class='p'>,</span><span class='s1'>&#39;$2&#39;</span><span class='p'>,</span> <span class='nv'>$s</span><span class='p'>);</span>
    <span class='p'>},</span> <span class='k'>array</span><span class='p'>(</span><span class='nv'>$a</span><span class='p'>,</span><span class='nv'>$b</span><span class='p'>));</span>
    <span class='k'>return</span> <span class='nb'>strcmp</span><span class='p'>(</span><span class='nv'>$a</span><span class='p'>,</span><span class='nv'>$b</span><span class='p'>);</span>
<span class='p'>});</span>
</code></pre>
</div>
<p>Notice that this code doesn&#8217;t create any new functions in the global namespace. It&#8217;s slightly harder to read initially (mostly because of the gratuitous use of the <code>list()</code> language construct), but it is vastly cleaner and, in a word <em>elegant</em>.</p>

<p>(Aside: calling super geeky things elegant is not even close to pass&#8217;e yet.)</p>

<p>We can also now perform the operation of <strong><a href='http://en.wikipedia.org/wiki/Currying'>currying</a></strong>-partially instantiating a function with multiple parameters. Let&#8217;s say we want to apply a function to each item in a list that adds 7 to that item. PHP has a built-in <code>array_map()</code> function, used above, that allows us to apply a function to every item in an array, but its argument is again a string, and we still have to create a global-namespace function to accomplish this.</p>

<p>Let&#8217;s just say we have a function <code>add()</code> such as</p>
<div class='highlight'><pre><code class='php'><span class='k'>function</span> <span class='nf'>add</span><span class='p'>(</span><span class='nv'>$x</span><span class='p'>,</span><span class='nv'>$y</span><span class='p'>)</span> <span class='p'>{</span> <span class='k'>return</span> <span class='nv'>$x</span> <span class='o'>+</span> <span class='nv'>$y</span><span class='p'>;</span> <span class='p'>}</span>
</code></pre>
</div>
<p>and we want to create a function <code>add7($x)</code> that returns <code>$x + 7</code>. We could simply create it:</p>
<div class='highlight'><pre><code class='php'><span class='k'>function</span> <span class='nf'>add7</span><span class='p'>(</span><span class='nv'>$x</span><span class='p'>){</span> <span class='k'>return</span> <span class='nv'>$x</span> <span class='o'>+</span> <span class='mi'>7</span><span class='p'>;</span> <span class='p'>}</span>
</code></pre>
</div>
<p>Now what we want to do is <em>partially instantiate</em> our <code>add()</code> function to have a sort of &#8216;hard-coded&#8217; first argument 7. In this way, we would define <code>add7()</code> to be</p>
<div class='highlight'><pre><code class='php'>    <span class='k'>function</span> <span class='nf'>add7</span><span class='p'>(</span><span class='nv'>$x</span><span class='p'>){</span> <span class='k'>return</span> <span class='nx'>add</span><span class='p'>(</span><span class='mi'>7</span><span class='p'>,</span><span class='nv'>$x</span><span class='p'>);</span> <span class='p'>}</span>
</code></pre>
</div>
<p>We just had to create another function in the global namespace: bloating our memory footprint and creating an obtrusive disaster of our codebase to accomplish a trivial task.</p>

<p>With currying, we could simply do this:</p>
<div class='highlight'><pre><code class='php'><span class='nv'>$add</span>  <span class='o'>=</span> <span class='k'>function</span><span class='p'>()(</span> <span class='nv'>$x</span><span class='p'>,</span> <span class='nv'>$y</span> <span class='p'>)</span> <span class='p'>{</span> <span class='k'>return</span> <span class='nv'>$x</span> <span class='o'>+</span> <span class='nv'>$y</span><span class='p'>;</span> <span class='p'>};</span>
<span class='nv'>$add7</span> <span class='o'>=</span> <span class='nx'>curry</span><span class='p'>(</span><span class='nv'>$add</span><span class='p'>,</span><span class='mi'>7</span><span class='p'>);</span>
</code></pre>
</div>
<p>The punchline is that <code>curry()</code> <em>returns a function</em>. It&#8217;s a robot that gives birth to new robots. Elegant?</p>

<p>So we can increment every item in an array by 7 very simply:</p>
<div class='highlight'><pre><code class='php'><span class='nv'>$nums</span> <span class='o'>=</span> <span class='k'>array</span><span class='p'>(</span> <span class='mi'>1</span><span class='p'>,</span> <span class='mi'>2</span><span class='p'>,</span> <span class='mi'>3</span><span class='p'>,</span> <span class='mi'>4</span> <span class='p'>);</span>
<span class='nv'>$add</span>  <span class='o'>=</span> <span class='k'>function</span><span class='p'>()(</span> <span class='nv'>$x</span><span class='p'>,</span> <span class='nv'>$y</span> <span class='p'>)</span> <span class='p'>{</span> <span class='k'>return</span> <span class='nv'>$x</span> <span class='o'>+</span> <span class='nv'>$y</span><span class='p'>;</span> <span class='p'>};</span>
<span class='nv'>$nums</span> <span class='o'>=</span> <span class='nb'>array_map</span><span class='p'>(</span> <span class='nx'>curry</span><span class='p'>(</span><span class='nv'>$add</span><span class='p'>,</span><span class='mi'>7</span><span class='p'>),</span> <span class='nv'>$num</span> <span class='p'>);</span>
</code></pre>
</div>
<p>(This example is very contrived, of course, since there was no reason to use currying here-we could have simply had</p>
<div class='highlight'><pre><code class='php'><span class='nv'>$nums</span> <span class='o'>=</span> <span class='k'>array</span><span class='p'>(</span> <span class='mi'>1</span><span class='p'>,</span> <span class='mi'>2</span><span class='p'>,</span> <span class='mi'>3</span><span class='p'>,</span> <span class='mi'>4</span> <span class='p'>);</span>
<span class='nv'>$nums</span> <span class='o'>=</span> <span class='nb'>array_map</span><span class='p'>(</span> <span class='k'>function</span><span class='p'>(</span><span class='nv'>$x</span><span class='p'>){</span> <span class='k'>return</span> <span class='nv'>$x</span> <span class='o'>+</span> <span class='mi'>7</span><span class='p'>;</span> <span class='p'>},</span> <span class='nv'>$num</span> <span class='p'>);</span>
</code></pre>
</div>
<p>but cut me some slack.)</p>

<p><strong>Unfortunately</strong> <code>curry()</code> is not yet part of the PHP standard library. It&#8217;s also not inherently obvious how to implement it-the necessary language constructs were only introduced a mere three weeks ago today.</p>

<p><strong>Fortunately</strong>, I have implemented <code>curry()</code> for you. It&#8217;s a bit ugly, but it works. It&#8217;s actually fairly fast as well (although my initial tests of it were not exhaustive).</p>
<div class='highlight'><pre><code class='php'><span class='k'>function</span> <span class='nf'>curry</span><span class='p'>(</span><span class='nv'>$fn</span><span class='p'>,</span> <span class='nv'>$arg</span><span class='p'>)</span>
<span class='p'>{</span>
    <span class='k'>return</span> <span class='k'>function</span><span class='p'>()</span> <span class='k'>use</span> <span class='p'>(</span><span class='nv'>$fn</span><span class='p'>,</span> <span class='nv'>$arg</span><span class='p'>)</span>
    <span class='p'>{</span>
        <span class='nv'>$args</span> <span class='o'>=</span> <span class='nb'>func_get_args</span><span class='p'>();</span>
        <span class='nb'>array_unshift</span><span class='p'>(</span> <span class='nv'>$args</span><span class='p'>,</span> <span class='nv'>$arg</span> <span class='p'>);</span>
        <span class='k'>return</span> <span class='nb'>call_user_func_array</span><span class='p'>(</span> <span class='nv'>$fn</span><span class='p'>,</span> <span class='nv'>$args</span> <span class='p'>);</span>
    <span class='p'>};</span>
<span class='p'>}</span>
</code></pre>
</div>
<p>It&#8217;s cool because you can chain it to itself. So if you wanted a function that always returned 7, you could simply say:</p>
<div class='highlight'><pre><code class='php'><span class='nv'>$return7</span> <span class='o'>=</span> <span class='nx'>curry</span><span class='p'>(</span><span class='nx'>curry</span><span class='p'>(</span><span class='nv'>$add</span><span class='p'>,</span><span class='mi'>3</span><span class='p'>),</span><span class='mi'>4</span><span class='p'>);</span>
</code></pre>
</div>
<p>Or if you had a function that took three arguments and you wanted a new function with the first two &#8216;hard-coded&#8217; (imagine <code>g(x) = f(1,3,x)</code> from math), you could simply &#8220;curry <code>f()</code>&#8221; twice:</p>
<div class='highlight'><pre><code class='php'><span class='nv'>$g</span> <span class='o'>=</span> <span class='nx'>curry</span><span class='p'>(</span><span class='nx'>curry</span><span class='p'>(</span><span class='nv'>$f</span><span class='p'>,</span><span class='mi'>3</span><span class='p'>),</span><span class='mi'>1</span><span class='p'>);</span>
</code></pre>
</div>
<p>A better implementation would be for <code>curry()</code> to take a variable number of arguments and to curry all of them in:</p>
<div class='highlight'><pre><code class='php'><span class='nv'>$g</span> <span class='o'>=</span> <span class='nx'>curry</span><span class='p'>(</span><span class='nv'>$f</span><span class='p'>,</span><span class='mi'>3</span><span class='p'>,</span><span class='mi'>1</span><span class='p'>);</span> <span class='c1'>// or `curry($f,1,3)` maybe?</span>
</code></pre>
</div>
<p>I&#8217;ll leave this as &#8216;an exercise for the reader&#8217;, but it&#8217;s not too difficult to implement.</p>

<p>Awesome, <em>n&#8217;est-ce pas</em>?</p>

<p>You, too, can have some PHP 5.3 alpha goodness by running the following nonsense on your command line:</p>
<div class='highlight'><pre><code class='bash'>mkdir -p <span class='s2'>&quot;$HOME/src/php53alpha/build&quot;</span>
<span class='nb'>cd</span> <span class='s2'>&quot;$HOME/src/php53alpha&quot;</span>
wget http://downloads.php.net/johannes/php-5.3.0alpha1.tar.gz
tar zxf php-5.3.0alpha1.tar.gz
<span class='nb'>cd </span>php-5.3.0alpha1
./configure --prefix<span class='o'>=</span><span class='s2'>&quot;$PWD/../build&quot;</span>
make
make install
</code></pre>
</div>
<p>This installs the <code>php</code> binary in <em>~/src/php53alpha/build/bin</em>, so you can run your <em>.php</em> scripts by simply calling, e.g.,</p>
<div class='highlight'><pre><code class='bash'>~/src/php53alpha/build/bin/php my_script_file.php
</code></pre>
</div>
<p>Also read:</p>

<ul>
<li><a href='http://wiki.php.net/rfc/closures'>PHP.net&#8217;s explanation of lambdas and closures</a></li>

<li><a href='http://www.php.net/archive/2008.php#id2008-08-01-1'>PHP.net&#8217;s release notes for PHP 5.3 alpha1</a></li>
</ul>

<p>Enjoy.</p>
        </div>
    </div>

    <div class="post">
        <div class="meta">
            <a name="/2007/12/Installing-Pubcookie-33-On-Ubuntu-710-with-Apache-2" />
            <h2><a href="/2007/12/Installing-Pubcookie-33-On-Ubuntu-710-with-Apache-2/">Installing Pubcookie 3.3 on Ubuntu 7.10 with Apache 2</a></h2>
            <div class="date">29 Dec 2007</div>
        </div>
        <div class="content">
        <p>I recently had the wonderful experience of configuring UW&#8217;s Pubcookie for use on Ubuntu&#8217;s package-manager version of Apache2. I took modest notes while doing this, and it was spread out over several weeks whenever I could find the time, so maybe don&#8217;t take this as a guide so much as a few installation notes, but these are the spots that gave me the most trouble.</p>

<p>This accompanies the Pubcookie Apache Module installation guide at <a href='http://pubcookie.org/docs/install-mod_pubcookie-3.3.html'>http://pubcookie.org/docs/install-mod_pubcookie-3.3.html</a> and the UW-specific guide notes at <a href='http://www.washington.edu/computing/pubcookie/uwash-install.html'>http://www.washington.edu/computing/pubcookie/uwash-install.html</a>.</p>

<p>(Of course following the convention that <code>$</code> are commands run as a limited user while <code>#</code> commands are run as root.)</p>

<ol>
<li>
<p>Ensure Apache2 is installed and configured with OpenSSL:</p>

<pre><code># apt-get install apache2-threaded-dev apache2 openssl
# mkdir -p /etc/apache2/ssl</code></pre>
</li>

<li>
<p>Obtain Weblogin Server Registration for your hostname at <a href='https://server-reg.cac.washington.edu/pubcookie/'>https://server-reg.cac.washington.edu/pubcookie/</a></p>
</li>

<li>
<p>Get the UW Root Cert from <a href='http://certs.cac.washington.edu/?req=svpem'>http://certs.cac.washington.edu/?req=svpem</a></p>

<p>I put this file at <strong>/etc/apache2/ssl/server.pem</strong>. This is the server&#8217;s public key.</p>
</li>

<li>
<p>Get the CA Bundle from <a href='http://www.washington.edu/computing/pubcookie/ca-bundle.crt'>http://www.washington.edu/computing/pubcookie/ca-bundle.crt</a></p>

<p>I put this file at <strong>/etc/apache2/ssl/ca-bundle.crt</strong></p>

<p>This file allows the server to verify peers&#8217; certificates and is used by keyclient.</p>
</li>

<li>
<p>Generate your cert&#8217;s private key and have it signed by your CA.</p>

<p>Information on how to generate a private key and a signature signing request are probably documented on whatever site is signing your certificate. The UW CA&#8217;s Technical Information can be found at <a href='https://www.washington.edu/computing/ca/infra/'>https://www.washington.edu/computing/ca/infra/</a>.</p>

<p>Generating a request for the UW CA (and probably all other CAs as well) is simply a matter of:</p>

<pre><code># cd /etc/apache2/ssl
# openssl req -nodes -newkey 1024 \
    -keyout key.pem -out req.pem</code></pre>

<p>When I went through the request process, the CA gave me the following values to fill in to the request UI:</p>

<pre><code>Country (C)         US
State (ST)          WA or Washington
Organization (O)    Optional
Organizational Unit (OU)    Optional
Common Name (CN)    Your host&#39;s fully qualified domain name</code></pre>
</li>

<li>
<p>Put your private key at <strong>/etc/apache2/ssl/key.pem</strong> and your CA-signed certificate at <strong>/etc/apache2/ssl/cert.pem</strong>.</p>

<p>(Note that the above step should generate the key and the request at these locations already.)</p>
</li>

<li>
<p>Working in $HOME, get the Pubcookie tarball and unzip:</p>

<pre><code>$ mkdir -p $HOME/pubcookie
$ wget http://www.pubcookie.org/downloads/pubcookie-3.3.3.tar.gz
$ tar xzf pubcookie-3.3.3.tar.gz</code></pre>
</li>

<li>
<p>Modify the configure script to know where apache&#8217;s PREFIX is. This problem seems to come from the fact that Apache isn&#8217;t built from source locally when using aptitude.</p>

<p>The diff for this modification is</p>

<pre><code>3783c3783
 &lt;   APACHE_PREFIX=`$APXS -q PREFIX`
 ---
 &gt;   APACHE_PREFIX=&quot;/usr/share/apache2&quot; #`$APXS -q PREFIX`</code></pre>

<p>This via a message from the Pubcookie mailing list.</p>
</li>

<li>
<p>Configure, compile install:</p>

<pre><code>$ cd $HOME/pubcookie/pubcookie-3.3.3/
$ ./configure   \
    --enable-apache  \
    --prefix=/usr/local/pubcookie  \
    --with-apxs=/usr/bin/apxs2
$ make
$ sudo make install</code></pre>
</li>

<li>
<p>Based on information from the installation guide, the following serves as a good checkpoint:</p>

<pre><code>$ ls -F /usr/local/pubcookie
keyclient*      keys/</code></pre>
</li>

<li>
<p>Here is my keyclient configuration file, <strong>/usr/local/pubcookie/config</strong></p>

<pre><code># ssl config
ssl_key_file: /etc/apache2/ssl/key.pem
ssl_cert_file: /etc/apache2/ssl/cert.pem

# keyclient-specific config
keymgt_uri: https://weblogin.washington.edu:2222
ssl_ca_file: /etc/apache2/ssl/ca-bundle.crt</code></pre>
</li>

<li>
<p>Run keyclient to request a new key and to download the &#8220;granting&#8221; certificate:</p>

<pre><code># cd /user/local/pubcookie
# ./keyclient
# ./keyclient -G keys/pubcookie_granting.cert</code></pre>
</li>

<li>
<p>Create a pubcookie load file so we can continue to use Ubuntu&#8217;s methodology for managing Apache extensions (e.g. using <code>a2enmod</code> and <code>a2dismod</code>, which really only create/modify symlinks in <strong>/etc/apache2/mods-enabled</strong> but are sometimes reportedly used by other installation scripts):</p>

<pre><code># echo &#39;LoadModule pubcookie_module /usr/lib/apache2/modules/mod_pubcookie.so&#39; \
&gt; /etc/apache2/mods-available/pubcookie.load</code></pre>
</li>

<li>
<p>Stop Apache and load the pubcookie module:</p>

<pre><code># apache2ctl stop
# a2enmod pubcookie</code></pre>
</li>

<li>
<p>Set Pubcookie directives in <strong>/etc/apache2/httpd.conf</strong>:</p>

<pre><code>PubcookieGrantingCertFile /usr/local/pubcookie/keys/pubcookie_granting.cert
PubcookieSessionKeyFile /etc/apache2/ssl/key.pem
PubcookieSessionCertFile /etc/apache2/ssl/cert.pem
PubcookieLogin https://weblogin.washington.edu/
PubcookieLoginMethod POST
PubcookieDomain .washington.edu
PubcookieKeyDir /usr/local/pubcookie/keys/
PubCookieAuthTypeNames UWNetID null SecurID</code></pre>

<p>Note that Ubuntu&#8217;s Apache likes to have lots of configuration files. The main configuration happens in <strong>/etc/apache2/apache2.conf</strong> while &#8220;user&#8221; modifications appen in the httpd.conf file as per above. You will also need to have Apache listen for SSL requests on port 443 by modifying <strong>/etc/apache2/ports.conf</strong> to include</p>

<pre><code>Listen *:443</code></pre>
</li>

<li>
<p>Enable SSL on your default site. This can usually be done by modifying <strong>/etc/apache2/sites-available/default</strong> to include</p>

<pre><code>SSLEngine on
SSLCertificateFile /etc/apache2/ssl/cert.pem
SSLCertificateKeyFile /etc/apache2/ssl/key.pem</code></pre>

<p>You might be able to get away with only enabling SSL on select virtual hosts if your environment is such that you have multiple host names pointing to the same Apache instance. I was able to accomplish this to some degree but am still working out a few ambiguities that Apache isn&#8217;t telling me about.</p>
</li>

<li>
<p>Restart Apache and you&#8217;re good to go:</p>

<pre><code># apache2ctl -k start</code></pre>
</li>
</ol>

<p>You now have the usual <strong>.htaccess</strong> directives at your disposal. E.g.:</p>

<pre><code>AuthType UWNetID
Require valid-user</code></pre>

<p>Have some sorbet?</p>
        </div>
    </div>

</div>