The ability to write nested loops is not a sufficient condition of employment

But it ought to be a necessary one.

Suppose you were helping me write a TicTacToe program. I have this Java code so far:

package com.vaporware.tictactoe;

import com.vaporware.common.logging.FormattingLogger;

class Board {
  Piece cells [][];

  Board() {
    this.cells = new Piece [3][3];
  }

  boolean xWins () {
    return wins(Player.X);
  }

  boolean oWins () {
    return wins(Player.O);
  }

  boolean wins (Player player) {
    // FINISH ME!
    return false;
  }
}

Assume further that there is a getOwner() method on a Piece that returns a Player.
Can we finish the wins (Player player) method?

Curious

(define (fmod numerator denominator)
  (- numerator
     (* (floor (/ numerator denominator))
 denominator)))

(define (test-fmod numerator denominator)
  (let ((answer (fmod numerator denominator)))
    (if (> answer denominator)
 (begin (display "Whoops: ")
        (display (list numerator denominator answer))
        (newline)))))

1 ]=> (do ((i 0 (+ i 1))) ((>= i 1000)) (test-fmod (random 1.0) (random 1.0)))

; Value: #t

1 ]=> (test-fmod .59 .01)
Whoops: (.59 .01 1.0000000000000009e-2)
;Unspecified return value

Package system horrors

Arcane Sentiment mentioned how the Lisp Machine used to handle package prefixes in this post, and it reminded me of an interesting problem.


When we were building the LMI K-machine we had to cross-compile from the existing Lisp Machine. Naturally, the cross-compiler would read the source code and intern the source code symbols as part of the process. But the K-machine had a different package setup. New packages weren't a particular problem, but the locations of some symbols were. In addition, some things that were implemented as macros in the Lisp Machine were implemented as compiler intrinsic special forms on the K-machine, and vice versa.


The compiler naturally uses symbol identity to determine how to handle a special form. If you want to compile a conditional, for example, the CAR of the form had better be the symbol CL:IF. A symbol named "IF" in a different package won't generally work.


Well, that's not exactly correct... When the Lisp Machine was built, there was no CL package. There was no Common Lisp. So when the CL package was added, it was necessary to make sure that the symbol named "IF" in the CL package was the same EQ symbol as the one the compiler used for conditionals. There are a couple of ways to arrange for this. The symbol could be explicitly interned in the CL package, or it could be visible to the CL package via inheritance.


We wanted to change some of these things on the K-machine, but the cross-compiler was running on the LMI Lambda and when it read the source code it would intern the symbols in the Lambda's packages. Munging the existing Lambda packages was out of the question. The ‘solution’ was to play some nasty tricks with the entire package system. We created two different packages, both named "COMMON-LISP". Some of the symbols were common between them, but others were not. The package inheritance was different, too. The trick was to dynamically switch how package names were resolved to package objects.


So if you have two different “package systems”, how do you refer explicitly to “the symbol IF in the other "COMMON-LISP" package? With a reader hack, of course. We made the triple colon ::: prefix indicate which package system to use to resolve the package name.


This kind of worked, but it was a horror. Most of the system didn't care, the rest didn't know, but if you accidentally had the wrong package system in place when you read a file, you would definitely trash the entire machine and need to reboot. We had a few helper functions that would try to ensure that the correct package system was selected before doing anything (for instance, when calling the cross-compiler, we'd switch out, and when it returned we'd switch back. Works great until you enter a debug repl...). The big problem was that it was impossible to ‘close’ over the correct context, so you could not in general guarantee seamless operation. (For example, if you referred to the K-machine's CL:READ symbol, you probably wanted to switch to the K-machine package set, but there was no way to do this automatically.)

Another little puzzle

Write a procedure that, given two integers L and R, produces the integer that results from interleaving the binary representation of L and R. For example, suppose L is 23 and R is 13. The binary representation of L is 10111. The binary representation of R is 1101. If we interleave the bits (starting with R and padding with zeros when necessary) we get 1001111011. The answer is therefore 635.

Of course this is easy if you print the numbers and then do string manipulation. Can you do it with arithmetic? Can you extend it to handle negative numbers?

20 minute puzzle

You have a list of names and a list of objects. Each object has 1 unique name. Neither list contains duplicates. Write a procedure that determines if every name in the list corresponds to an object. (Suppose the list never contains more than four names, would you change your program?)

Another quick(?) question

I was asked: In your opinion, from a Google perspective, what qualities make up a great CTO?

I'm not sure what a “Google perspective” is, but I can dig up an uniformed opinion or two (or three).

As an officer of a business, a CTO has the primary responsibility of keeping the business going and growing (“maximizing shareholder value”), with particular emphasis on the technological tools the company uses and perhaps creates. A good CTO would be well-informed about where the state-of-the-art is and where it will be in a few years and what tools will give the most advantage with the least cost and risk.

That's the business school answer. I didn't go to business school.

I have been employed by a few companies that were big enough to have a CTO, and I have a different opinion in that context. While I want the company to be successful, and I do my part to help, I don't have the responsibility to consider the “business issues” associated with the technology. I personally take into consideration the effect that the technology has on my job and my co-workers jobs. I went to a tech school because I like technology for its own sake. I like to hang out and work with others that feel the same way. As an employee, I want a CTO that does what is necessary for the business, but also provides sufficient tools and “toys” so that my job is interesting, exciting, and challenging. If the work is dull, tedious, and requires little thought, I start to daydream about something better.

You can see that my desires aren't perfectly aligned with the CTO's responsibilities, so a company with a “great” CTO might be anathema to me, but a CTO that indulges the engineers of a company much more than is strictly necessary for business would make me more interested in being employed there.

Recursion with no base case?

Here's my solution:

(define (all-descendants node-children root)
  (cons root
        (append-map (lambda (child)
                      (all-descendants node-children child))
                    (node-children root))))

I wasn't measuring, but it took me more than a minute. I spent most of that time thinking about transitive closures, queues, iterating over elements, etc., before I realized that since I'm working with a tree rather than a directed graph, I need not worry about shared structure or duplicate elements.

This is an example of a well-founded recursive program that does not have an explicit base case. append-map (mapappend in Common Lisp) implicitly does not call the mapped function if the list argument is empty, so the recursion ends at the nodes of the tree that have no children.