Searchable Data Types
A few years ago, MartÃn Escardó wrote an article about a seemingly-impossible program that can exhaustively search the uncountably infinite "Cantor space" (infinite streams of bits). He then showed that spaces that can be thus searched form a monad (which I threw onto hackage), and wrote a paper about the mathematical foundations which is seemingly [...]
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 “align” 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 machines, [...]
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 algorithm. A [...]
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 | … | 9 I have a challenge for you: write [...]
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 match the [...]
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 could coerce Haskell [...]
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 a [...]
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 life: [...]
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 motion [...]
Recent Comments