Planet Scheme

• “I thought I would free up more memory on the second pass,” Tom recollected.
• “You should always check the pre-conditions,” Tom asserted.
• “Did you use SSL?” Tom asked cryptically.
• “If one of those is smaller, put it first,” Tom ordered weakly.
• “Command continuations discard values,” Tom said expressionlessly.
• “That isn't null or a cons cell,” Tom said listlessly.
• “Does this return an answer?” Tom asked haltingly.
• “This program implicitly depends upon time,” Tom stated.
• “Maybe it's in Reverse Polish Notation,” Tom put forth.

Yesterday I got the Clymer’s service manual in the mail from Murph’s, so with the Kawasaki service manual already in handy I’m ready for servicing my bike!

I’m very proud to announce Ocamlnet 3.0.0, a completely overhauled version of Ocamlnet.

Wish I had some problems that needed solving with ocamlnet!

(via caml-list)

Here is one person’s top ten list of ways to fail to obtain a PhD.

Interesting quotes:

Ph.D. school seems to be a magnet for every kind of procrastinator.

Advisors expect near-terminal Ph.D. students to be proto-professors with intimate knowledge of the challenges in their field. They should be capable of selecting and attacking research problems of appropriate size and scope.

A Ph.D. is a small but significant contribution to human knowledge. Impact is something students should aim for over a lifetime of research. Making a big impact with a Ph.D. is about as likely as hitting a bullseye the very first time you’ve fired a gun. Once you know how to shoot, you can keep shooting until you hit it. Plus, with a Ph.D., you get a lifetime supply of ammo.

It does not matter at all what you get your Ph.D. in. All that matters is that you get one. It’s the training that counts–not the topic.

(via ycombinator)

The Data Encryption Standard has been one of the most successful ciphers in history, and is still in use today, especially in its Triple DES variant. The Data Encryption Standard is officially described by FIPS 46-3, though if you are not fond of reading algorithm descriptions written by government lawyers there are many other descriptions available on the internet.

DES is a block cipher, operating on 64 bits at a time. Here is an example:

PT  P  r  o  g  P  r  a  x
HEX 50 72 6F 67 50 72 61 78
KEY 01 23 45 67 89 AB CD EF
CT  CC 99 EA 46 B1 6E 28 90

There is more than one way to encrypt a message longer than 64 bits; we will examine them in a later exercise.

Your task is to write the code to encipher and decipher a single 64-bit block using the Data Encryption Standard. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Just posted the updated version of DrSync for Racket on PlaneT.

Buck Sport Touring sells reflective stickers called Tailbrights that stick to the rear and side portions of the hard bags. Tonight I installed them. Installation was pretty simple; only had one or two bubbles on each of the stickers. I guess that you could make these yourself; but Buck Sport figured out the right shape, and I like to support companies that fill a niche like they do. The cool thing about them is that the stickers are black; so during the day you don’t even see them.

Here are some photos:

In ancient China, two thousand years ago, a general wanted to count his troops. He first had them line up in ranks of eleven, and there were ten troops left over in the last rank. Then he had his troops line up in ranks of twelve, and there were four left over in the last rank. Finally he had them line up in ranks of thirteen, and there were twelve troops remaining in the last rank.

Your task is to determine how many troops the general had under his command. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Barcamp Milwaukee 5 will be held from Saturday October 2, 2010 at 10AM through Sunday October 3, 2010 at 4PM.

Mike plans to present on Clojure, which should be pretty fun to attend.

Tonight after removing some of the caked-on dust from under the seat, I decided to investigate the gravel rash on the right of the lower fairing of the bike.

Getting down on my hands and knees to take a look, expecting deep grooves, I was shocked to instead find something like silver paint stuck to the fairing. It was caked on there, maybe one or two millimeters. Using a damp paper towel though I was able to remove all of the shiny crud.

My best guess is that the previous owner rode into something, or something rode into him, that left the material there.

I like easy fixes!

A library of purely functional data structures in Typed Racket. Data structures in the library are based on Chris Okasaki’s book Purely Functional Data Structures, work by Phil Bagwell and others

(via racket)

(define (compute-nodes-size! gc tree-node level)
  (compute-node-size! gc (get-graph-node tree-node))
  (set-level! tree-node level)
  (for-each (lambda (child)
       (compute-nodes-size! gc child (+ level 1)))
            (get-node-children tree-node)))

function computeNodesSize(ctx, treeNode, level) {
    computeNodeSize(ctx, treeNode.graphnode);
    treeNode.level = level;
    treeNode.children.forEach(function(child) { 
          computeNodesSize(ctx, child, level + 1); 
    });
}

(apply max nodes-y)

var maxY = 0;
nodesY.forEach(function(y) { if (y > maxY) { maxY = y; } });

Math.max.apply(this, nodesY)

function variadic(fun, val0f, val1f) {
  return function() {
    var len = arguments.length;
    if (len == 0) {
       return val0f();
    } else if (len == 1) {
       if (val1f != undefined) {
         return val1f(arguments[0]);
       }
       else {
         return arguments[0];
       }
    } else {
      var tmp = fun(arguments[0], arguments[1]);
      for (index = 2; index < len; index++) {
        tmp = fun(tmp, arguments[index]);
      }
      return tmp;
    }
  };
}

var sum = variadic(function(x,y) {return x+y;},
                   function() { return 0;},
                   function(x) { return x;});

var div = variadic(function(x,y) {return x/y; },
                   function() { throw "not enough arguments to div"; },
                   function(x) { return 1/x;});

div.apply(this, [1,2,3,4,5])

In the mid-1970s, Daniel Shanks exploited the binary quadratic forms introduced by Legendre in the late eighteenth century and perfected by Gauss in the early nineteenth century to create a method of factoring integers. Binary quadratic forms are expressions of the form Ax² + Bxy + Cy² with A, B and C integers, normally represented as the triple (A, B, C). Binary quadratic forms are often called square forms.

We won’t discuss the mathematics of square forms, but we do need to know how to reduce a square form. A discriminant delta is calculated as Δ = b² − 4ac. A single reduction step is called a rho reduction, and is given by ρ(a, b, c) = (c, r, (r²−Δ)/4c) where r is that unique integer b mod 2c such that −|c| < r <= |c|, if √Δ < |c|, or √Δ − 2|c| < r < √Δ, if |c| < √Δ.

A square form is in reduced form if |√Δ−2|a|| < b < √Δ; this reduction is accomplished by continually applying ρ until the reduced form is achieved.

Shanks’ method uses two loops. First, an initial square form is calculated, based on the number to be factored, which must be odd, composite, and not a perfect square; the details of that initialization are tedious, and appear in the solution on the next page. Then the square form is repeatedly reduced (this is the “forward” loop) until it is in proper form, which is described below. Then the reduced inverse square root of the square form calculated in the forward loop is reduced in a “backward” loop until a factor is identified when two successive square forms (A, B, C=c²) have the same B; the factor is then c, if c is odd, or c/2, if c is even. The reduced inverse square root of (A, B, C=c²) is initially (−c, B, −cA), which is then put into reduced form as described above.

Shanks defined a square form as proper using a queue of values derived in a rather complicated way. We will use a simpler method known as a sufficient list. Let L be the integer square root of the square root of the discriminant. If a square form (A, B, C) is encountered with |C| < L with C even, or |C| < L/2 with C odd, then C is placed on the sufficient list. Then a square form (A, B, C=c²) is proper if c is not on the sufficient list.

Your task is to write a function to factor integers using Shanks’ square form algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

This past May, I completed the Simulation and Parallel and Distributed Systems class that I was attending. While taking two classes while working full time was challenging; the pure fun of it all more than made up for the challenge! I will have fond memories of that semester for a long time.

I can’t wait to get started with Applied Mathematical Analysis next week.