Looking for needles in haystacks

Here's a proper programming challenge, simple to state, and in the end quite challenging to solve. A function produces a 64-bit output given a 64-bit input. It mostly behaves like a random function, so given a random input, most outputs occur with probability between 0 and 2-63; in other words, for a randomly-chosen 64-bit y, there are usually between 0 and 2 solutions to the equation f(x) = y. However, a few occur with much greater frequency - more like 2-32 or so. The function is pretty quick and easy to calculate, but its internal structure defies direct analysis. How would you identify these more frequent occurrences by experiment? How big a computer would you need to do it in something like a few hours to a few days? Think about it for a while before you read on.

Slate

I’ve just taken another look at where the Slate language project has gotten up to. Last time I looked was almost a year ago now. There’s been a lot of progress! The time seems ripe for Slate to get an event loop, so that proper networking and threading can be built on it.

Big bucks for big bugs

I was recently working on a project where the client wanted us to add some features and updates to a web-facing database which they had paid some big name consultants to develop for them. Wow, did what we received look impressive. It used some of the latest industry buzz-words: SQL Server, ASP.NET, Web services, to…

Truncated differential cryptanalysis of five rounds of Salsa20

eSTREAM have just put my paper online: Truncated differential cryptanalysis of five rounds of Salsa20 (PDF) (discussion, Wikipedia on Salsa20). This doesn’t break the whole cipher, just a seriously reduced version. Experimentation played a key role in finding this result. I found the first differential by writing a short Python program that implemented a pretty…

Spoon and the Object Visualiser

Take a look at this part of NetJam.ORG, in which Craig Latta builds a visual display of a running Smalltalk Image. Be sure to check out the movie of the first 50ms or so of a running image. Smalltalk gets all the cool toys.

Something about early, and often?

Naturally, almost as soon as I’d posted about my extensions to pregexp, I discovered a bug in said extensions. It was something I should have caught, too: in the code I had a constant (3) which I couldn’t explain. I had expected it to be 2, not 3, and the need for the extra increment…

When will the Haskell community finally get their act together

…and produce a usable package system? The absence of a standardised and user-friendly mechanism to package & distribute libraries, and to locate and install such libraries has been a major stumbling block in the adoption of non-mainstream programming languages for a long time. I wrote about it [here](https://www.lshift.net/news.20030928lispconference.html) in the context of Scheme. Haskell is…

xxexpr.ss – an SXML-to-XML converter

The SSAX XML parsing- and processing-library provides robust, high-quality XML reading tools for Scheme, but doesn’t include a general purpose XML writer. Over the past couple of years, a few of my projects have had a need to convert SXML-like data to an XML 1.0 external representation, and so I’ve written a portable SXML-to-XML printing…

A SRFI-10-style extension to JSON

Background The data language JSON is a great replacement for XML for many applications. It’s very similar in spirit to Lisp and Scheme S-expressions, as well as to XML: it is a pure data language, with no intrinsic semantics. XML doesn’t allow direct literal representation of any data types other than strings and XML nodes…

Continuation-Passing Style in Javascript

As part of my recent experiments with Javascript, I happened to want a sleep function. Interestingly, there isn’t one available in browser-side Javascript environments – instead, there are four functions setInterval clearInterval setTimeout clearTimeout and they take functions to call after a certain number of milliseconds have gone by. This leads to programming in continuation-passing…