Lunar Lockout

Lunar Lockout is a simple logic game, which was shown to me by a primary school teacher who bought it for the kids in her class. A few pieces are placed on a 5x5 board. The goal is to place a particular piece at the center, while being allowed to move any piece only if it can be blocked by another piece. It's a classic example of a game that can be solved by brute-force search.

I programmed a simple solver in Python. The method by which I programed this solver could be used to solve many other logic games. In fact, you could easily abstract the pieces away. You need:

1. a representation for a state of game (here, I use a list of cartesian coordinates, one per piece, the first element being for the piece that has to be moved to the center),
2. a function to generate all legal moves for a given state game,
3. a function that applies a move to a given game state, returning a new game state (it's easier than mutating the given game state for searching many alternatives at once).
4. a predicate to test whether a game state is a solution (here, I simply check whether the first coordinate is the center of the board).

With this pieces, it's easy to do a brute-force search (here, I use a breath-first search which skips already seen game states).

Probabilistic Modeling in Haskell

I translated the probabilistic modeling example from F# to Haskell. I ran into the restricted monad problem, because Support implemented as a Set requires the type class Ord. Perhaps, this problem is a step up from F#: if one uses a set with a type that doesn't implement Comparable, the error only appears at run-time in F#! 

I don't think this sample as translated does justice to Haskell. I ought to look at the Haskell implementation in the original paper by Ramsey and Pfeffer. In addition, the blog randomhacks.net has a whole series about probabilistic monads in Haskell, culminating in a paper (PDF). There also a functional pearl about probabilistic functional programming in Haskell.

Error Estimation in Scala

At github.

Implementing Probabilistic Modeling Using Monads in F# and Scala

For my induction into Scala, I wanted to translate the probabilistic monad of Chapter 9 of Expert F# (Introducing Language-Oriented Programming). The idea, based on the paper Stochastic Lambda Calculus and Monads of Probability Distributions, is to define a probability monad to compute over distributions of a domain instead of the domain itself. We limit ourselves to distributions over discrete domains characterized by three functions:

1. sampling


2. support
   (i.e. a set of values where all elements outside the set have zero chance of being sampled)


3. expectation of a function over the distribution
   (e.g. the probability of selecting element A by evaluating the function f(x) = 1 if x equals A and 0 otherwise)

Contrast the F# implementation with the Scala implementation. The Scala implementation closely follows the F# one, except for one major frustration: the type inference is not as powerful in Scala, as all function arguments must be declared.

Perhaps, I am missing a few tricks because I am new to Scala. If anyone has any suggestions for improving the Scala implementation, please share.

Cross-posted to the Scala wiki.

the killer combination for programming languages or why I like F#

I've been using F# to develop a plug-in to AutoCAD for designing microfluidic chips (user site, developer site). I came to F# because my project required an implementation in a .NET language, and I felt that a functional language would be a good match for my problem domain. Now, it's my language of choice, and I feel guilty for tying myself to a closed platform. What do I like about F#?

Type inference, static typing & visual type feedback. The code is more concise, because type declarations can be omitted. This conciseness also makes it easier to modify the code, and static typing ensures that modifications are safe. This comes at no loss in clarity, because Visual Studio supplies the inferred type on demand. In addition, Visual Studio continuously informs of type errors, which allows an instantaneous overview of the consequences of a modification. Code can easily be drastically modified, even if maintainability was not consciously thought of during the development process. Haskell and OCaml also have this combination of type inference and static typing, but without the instantenous type feedback leveraged by the Visual Studio integration.

Language-oriented programming. In F# like "in Lisp, you don't just write your program down toward the language, you also build the language up toward your program" (Paul Graham in Programming Bottom-Up). In F#, like in Haskell and OCaml, you build an abstract representation of your domain using algebraic data types and analyze it with pattern matching. Functional programming with higher-order abstractions also help in this regard (not to mention that it's fun).

Python-like syntax. With the #light option, F# becomes indentation-sensitive, allowing for more conciseness and readability. Haskell has a similar option.

F# Interactive. It's nice to have a REPL sometimes.

.NET and Visual Studio integration. Unlike its cousins, F# is eminently practical just by virtue of being a .NET language. You can easily mix and match components written for the CLR. In addition to the type feedback, Visual Studio has a great debugger. I also like the C#-like classic object-oriented system, though probably because it's familiar rather than superior.

In conclusion, programming in F# feels fun & productive and (yet) professional & practical. I used to be content programming an esoteric Scheme system in Emacs. Now, I am convinced by the killer combination of (1) a fun functional language (2) a widely-used platform with a rich library (3) an IDE with a good visual debugger. With (1) ML-like, (2) CLR, (3) Visual Studio, you get F#. With (1) Lisp, (2) JVM, (3) Eclipse, I guess you get Clojure. That's the future.

The Curry-Howard Isomorphism, a Tiny Appetizer

Enjoy these two facts.

Amazing fact 1: Any combinator (i.e. lambda-definable term) can be written using only the two combinators S (lambda (x) (lambda (y) (lambda (z) ((x z) (y z))) and K (lambda (x) (lambda (y) x). For a cute exploitation of this fact, see Iota and Jot: the simplest languages?.

Amazing fact 2 (The Curry-Howard Isomorphism): The types of combinators correspond to tautologies of propositional logic. For example, the type of K is A -> (B -> A). Read A, B as variables and -> as implication. Try S: (A -> (B -> C)) -> ((A -> B) -> (A -> C)). Even more, any tautology can be derived from S and K using modus ponens. Why? The rules (for abstraction and application) in typed lambda-calculus correspond to the rules (for introduction and elimination of implication) in a natural deduction system. For a whirlwind tour of lambda-calculus which mentions the Curry-Howard isomorphism, see the paper Church's Thesis and Functional Programming (PDF). For an exposition of a natural deduction system, see the book Building Problem Solver, section 4.4 Natural Deduction.