Looking for needles in haystacks

Paul Crowley wrote “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.”

Something about early, and often?

Tony Garnock-Jones wrote “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…”

pregexp over streams, and other random hackery

Tony Garnock-Jones wrote “Over at eighty-twenty I recount a couple of recent random excursions into various bits and pieces of code. Besides those developments, I also spent some time on Sunday morning modifying Dorai Sitaram‘s pregexp version 20050502 to operate over streams as well as strings, so that I could use it for lexing arbitrary character sources (for…”

JSON, Squeak, and Seaside

Tony Garnock-Jones wrote “Today I implemented a JSON reader/writer library for Squeak, and a small extension to Seaside‘s existing LivePage features for doing XMLHttpRequest-based server-push. The JSON code is available on Squeakmap and also via SqueakSource, under either SqueakL (see here) or the MIT license. The Seaside extension is still in flux, but I’ll release something as soon…”

From Stateful Parsing to Transactional Parsing

Tony Garnock-Jones wrote “Thinking further on the problem of stateful parsing (from yesterday’s article), the way we’ve done it in the past (essentially by using Scheme’s parameter mechanism) is a special case of a transactional system, with rollback on error and commit after each toplevel expression parsed. This suggests that if Scheme had an implementation of a Software…”

Extensible Parsing Systems

Tony Garnock-Jones wrote “Francis reminded me of the Packrat Parsing algorithm the other day, so I took another look at the Scheme implementation I’d thrown together a few months ago for my ThiNG prototype. Currently, it’s just the basic parsing combinators and support data-structures, but I’d like to make it into an extensible reader, just like for codename.…”

Sound Conclusions in Scala

Matthew Sackman wrote “Scala is a programming language which tries to mix pure object orientation (data only) and functional programming styles. It currently compiles to Java bytecode but there are plans to enable compilation to the .Net CLR bytecode too. It supports generics/templates within Scala but does not support Java’s generics so you’re back to the pre-1.5 Java…”

The Web interface divide

Michael Bridgen wrote “Matthias and I were talking about website ‘templating’ — that is, making Web pages parameterised on the content. We weren’t discussing the technical rationale behind it — constructive laziness is axiomatic — but how best to accomplish a separation of concerns between contributors. For example, frequently we co-operate with companies or individuals that specialise in…”

The Design of a Pretty-printing Library

Tony Garnock-Jones wrote “This paper is hard going, but very rewarding. The author concentrates on two ways of transforming a formal, algebraic specification into an implementation, starting with very simple examples and working up to a pretty-printing library. The reason this paper is worthwhile is that, by moving very slowly and by demonstrating the same theme over and…”

A Lisp Interpreter for Squeak

Tony Garnock-Jones wrote “This is a simple-minded (and slightly weird) Lisp interpreter for Squeak Smalltalk. It doesn’t have a REPL under Morphic, but I’ve hacked on it to provide a minimal Morphic UI. It got me thinking about Lisp Machines again. What if the existing Squeak infrastructure could be exploited to build a Scheme Machine? The minimal addition…”