Collision Detection with Enneatrees

Many of my games boil down to, at some level, a large collection of circles (or spheres) interacting with each other. I use circles for collision detection, and otherwise whenever I can for organization, because the results look more natural than using boxes. If you organize using boxes, your simulation will tend to [...]

Lazy Partial Evaluation

Inspired by Dan Piponi’s latest post, I have been looking into partial evaluation. In particular, I thought that a language which emphasizes currying really ought be good at partial evaluation. In this post I describe some ideas regarding partial evaluation in functional languages, and later sketch a partial evaluation machine I devised.
Supercombinator reduction [...]

Certificate Design Pattern

When working the latest incarnation of my System IG compiler, I used a thingy which I now realize ought to be characterized as a design pattern. It substantially changed the way I was thinking about the code, which is what makes it interesting.
Summary: separate an algorithm into certificate constructors and a search [...]

Enumerating a context-free language

Here is a familiar context-free grammar for arithmetic expressions:

S ::= add
add ::= mul | add + mul
mul ::= term | mul * term
term ::= number | ( S )
number ::= digit | digit number
digit ::= 0 | 1 | … | [...]

Set Selectors

I am writing a poker game, and I got mildly annoyed when I went to write the hand classification functions. There was a disparity between the specification and implementation of poker hands; I had to come up with an algorithm to match each type. I didn’t like this, I want the code to [...]

Call-by-Future

I was reading about evaluation strategies for lambda calculus on Wikipedia, and one caught my eye: “call-by-future”. The idea behind this strategy is that you evaluate the function and its argument in parallel. It’s like lazy evaluation, except you start evaluating earlier. Call by future semantics are non-strict, so I figured I [...]

No Total Function from Infinite Sequences of Booleans onto the Integers

Yesterday I found out about a remarkable algorithm which can take any total predicate (function returing true or false) on infinite sequences of bits and find an infinite sequence which satisfies it (and implemented it). It’s a counterintuitive result, since you’d think that you can’t search the (uncountably) infinite space of bit sequences in [...]

Abstract State Machines for Game Rule Specification

Jude has been working on the design of a general board game programming engine. We brainstormed a bit, and I remembered something I had read about a little while ago: Abstract state machines.
An ASM is really nothing more than a formalization of a simultaneous chain of if-then statements. A common example is Conway’s [...]

Sword Gestures

It has been two weeks since I have done the slightest amount of work on the sword game. Kudos to Ben for keeping it moving along. Anyway, it’s time for some brainstorming.
Our current idea (as of last week) for a control scheme for the sword game is (1) to have it in slow [...]

Generalization

Okay, here’s the latest on my type inference algorithm: (1) it rocks, (2) it is still having trouble with generalization. My current example is the following (using ML-style reference syntax):

fix \f x { x := !x + 1; if 10 < !x then x else f x }

That fix business [...]