xkcd 1313 by simulated annealing in Clojure

Like any red-blooded American, I find regex golf fascinating. The idea, to paraphrase the comic strip, is to find a regular expression that matches all members of a group of related terms, but not any members of a different group. The hover text on the strip suggests a regex that matches all winning presidents.

Peter Norvig went to town on this, first clarifying the problem and then building an algorithm to search for the shortest solution that matches all mainstream presidential candidates who eventually won, but not such candidates who never won. (So Perot, Nader, Anderson et al don't figure …

more ...

Headfirst Search

In another post, I prattled on at some length about the scala Set class. To understand its nuances, it was helpful to print out a graph of class and trait inheritance. Here's a contrived example that's simpler than Set:

trait C1 {}
trait C2 {}
trait D extends C1 with C2 {}
trait E1 extends D {}
trait E2 extends D {}
trait E3 extends C2 {}
trait F extends E1 with E2 with E3 {}

The hierarchy of F looks like:

           C1   C2
             \ / \
              D   \
             / \   \
           E1  E2  E3
             \ /__/

which the proposed utility will display as:

interface F
  interface E1
    interface D
      interface C1
      interface C2 …
more ...

Game, Set, Match

Around a year ago, there was a lively debate about the type invariance of the immutable Set in Scala. Dogpile argumentation on a subject far outside the popular interest is of course thrilling in itself, but the topic also provides a nice focal point for exploring and clarifying some important aspects of the Scala type system.

We recall that Scala collections (and other higher kinded classes) can be invariant, covariant or contravariant in their type parameters, corresponding repectively to declarations as class Whatever[A], class Whatever[+A] or class Whatever[-A].

  • In the case of covariance, a Whatever[B] will …
more ...

Making a pretentious logo using CSS

My pride in not being a "front end guy" is notoriously obnoxious and obviously compensatory. On the other hand, having crappy front ends for my projects might help disguise deeper flaws and thus actually be an advantage.

Came a time, however, when I wanted to make myself a logo. Faced with the horrific prospect of doing actual art, I had no real choice but to use markup. Make no mistake, the linguae francae of our browsable universe -- html, css and javascript -- are a collective insult to science and beauty. But you can do cool stuff sometimes.

My new company, is …

more ...

Typecasting, part 2

Some time after my recent fiddles with IMDB, I read an interesting article about using a perceptron to classify words as parts of speech based on features that precede them in text. It's all done in python or some such sh*t, but whatever. Still very cool. Since I had all of this IMDB data accumulated in Mongo, I thought I would try to play with it, and the idea I had was to predict metacritic scores from the actors that appeared in each film. In retrospect, it's far from clear that such a prediction can be made and especialy …

more ...

What if John Conway Wrote Esolangs?

This is about a month old.

Actually, scrap that. This kind of thing never gets old.

To wit, a presentation on implementing and "using" Fractran, via clojure of course.

The least silly aspects of the show are (1) that we can implement the language very concisely and functionaly, and (2) to interpret the results, there's a nifty sieve of Eratosthenes - the real one.

The code is on github.

more ...

Hollywood Typecasting - Adventures with typed clojure and IMDB

I am broadly sympathetic to view that scalable systems must be built with statically typed langages, for reasons outlined in this wonderful screed, and, until recently, that has made it difficult for me to recommend clojure for institutional use.

With the introduction of core.typed, that has changed. The author has says that core.typed is now production-ready, and I agree. It's not perfect, but it will find bugs in your code without breaking it or causing performance problems. It's also pretty cool, and in many ways more expressive than type declarations in "normal" statically typed languages.

That said, the …

more ...

Deriving the Y-Combinator in Clojure

At some point, everyone wakes up in the middle of the night, in a cold sweat of panic that they don't truly understand how to derive the Y-combinator. Well maybe not everyone, but at least me. (Note that I'm talking about the higher order function, not the startup incubator.) I ended up reading through quite a few web pages, all of which presupposed a slightly different background, before I finally understood. This post distills my understanding, expressed in clojure, which happens to be what I'm into now. It can now be one of the pages that someone else finds not …

more ...

Varieties of laziness: clojure reducers, scala views and closure functors

This is very cool.

(Thanks to David Nolen, who pointed out errors in the original.)

I hadn't realized that the standard higher order sequence functions compose in a manner that requires quite a bit of run-time machinery. For example nested map calls will cause a separate lazy sequence to be instantiated at each level of nesting, with each level "pulling" results from the next innermost as needed. The function calls are thus temporally interleaved, but the functions are not actually composed. We can see this happening by adding some printlns to some unary functions and then running a nested …

more ...