fragmentary ideas ䷿ intellectual what-nots ䷷ and haskell programming ䷴

Like the Lambda Calculus (on which Lisp is based), Combinatory Logic is a formal system that can be used to model and study computation. What makes it fascinating is that it is as powerful as the (already simple) lambda calculus, but has no need for the variables that LC requires to perform substitution!

Here I show how we can use Haskell’s type classes and other language features to model the Combinator Calculus. The goals of this module were:

1. don’t force any one evaluation strategy
2. allow users to define new combinators without exposing the implementation
3. allow new combinators to be defined in terms of other already-defined combinators.
4. discourage creation of non-sensical combinator expressions, or possible mis-use of the module
5. hide existential types and anything else exotic

If you want to play with it, you can do a:

$> darcs get http://coder.bsimmons.name/code/CombinatorCalculus

Read the rest of this article »

Note: this is part of a series of posts is related to the “17×17 Challenge” posted by Bill Gasarch. The goal is to color cells of a 17 by 17 grid, using only four colors, such that no rectangle is formed from four cells of the same color.

Just a few follow-ups to my previous post in which I use a simulated annealing-type algorithm to find a good (hopefully complete) cover of a grid by swapping rows and columns from four identical sub-grids of 74 colors.

Easing into new thresholds

I modified my algorithm so that the likelihood of jumping into the highest permitted energy level is decreased over time; thus instead of having an abrupt transition to a new threshold, resulting in a steep dive, we instead ease into the new energy level.

Here is a graph of a run with the adjusted meta-heuristic (in blue) alongside a previous abrupt threshold transition run (in black). You can check compare it to the graph from the previous post:

Read the rest of this article »

Computer science is a fascinating and maddening thing. Even the most seemingly-esoteric topics turn out to be fundamental. Go out to the fringes of CS and you find yourself smack in the middle of Philosophy. You try to understand a single point and you suddenly find yourself embracing everything.

So this post comes from that infinitely-recursive rabbit hole of wikipedia topics I’ve been falling down for the last few weeks, and you can probably expect a few more like this one; I’ll try to keep focused.

We begin (as do All Good Things) with the Untyped Lambda Calculus:
Read the rest of this article »