Alaska Ataca a Kamtchatka

File Sharing on the Spot

2012-01-12T14:37:00.000-03:00

Last time I complained that I couldn't find an easy way to share a source code archive that didn't involve signing up for a service I didn't care for. Blogging platforms only make easy to attach images to posts, so why not pack a file as a PNG? Enter PNGPack. I tried finding OCaml bindings to libpng; after a disheartening exploration I realized that Java is (for me at least) the ideal platform to

Eighteen Million Noises

2012-01-11T10:02:00.001-03:00

Update: Here is the PNGPack source-code archive: Per second. Yes, it's benchmark time. I pitted Prof. Perlin's original implementation against Stefan Gustavson's, and the results are in! I ran two sets of benchmarks, one in Java and the other in OCaml. In both cases I compared three versions of Simplex Noise: Perlin's pipelined 3D Noise, and Gustavson's 2D Noise and 3D Noise: noisep: Perlin's 3D

Putting Noise to the Test

2012-01-09T11:22:00.000-03:00

So how do you use Perlin's Simplex Noise? By using the GIF encoder, of course! I generated the test image shown in the last post: with a minimal application of both modules in test.ml (source code follows). For a visually richer but not much more complicated example, I also tried replicating Iñigo Quílez's turbulent textures in fbm.ml. The animation traces a tiny loop in noise space so that it

Perlin's Simplex Noise

2012-01-06T13:39:00.000-03:00

Graphics pioneer Ken Perlin is well-known for his work on procedural generation of textures. Recently he rewrote his classic Noise algorithm to reduce the complexity of generating pseudorandom gradients in higher dimensions by transforming a problem on N-cells to one on N-simplices. I couldn't find on his NYU home page a write-up by his own hand; apparently the only implementation exists in his

(One by) Four by Nine

2011-12-30T15:50:00.000-03:00

The four nines puzzle asks which positive numbers can be obtained from arithmetic expressions involving four "9" digits and an assortment of operations, minimally "+", "-" (binary and unary), "×" and "/", also frequently "√" and sometimes "!" (factorial). I'll show how to find them by brute force. In this case, I'll forgo using factorials; this means that not every number under 100 can be so

Vose's Alias Method

2011-12-29T14:12:00.002-03:00

This is a note regarding the implementation of Vose's Method to construct the alias tables for non-uniform discrete probability sampling presented by Keith Schwartz (as of 2011-12-29). Mr. Schwartz otherwise very informative write-up contains an error in the presentation of the Method. Step 5 of the algorithm fails if the Small list is nonempty but the Large list is. This can happen either: if

A Better (Gauss) Error Function

2011-12-21T11:53:00.000-03:00

If you do statistics you know of erf and erfc; if you work in OCaml you surely miss them. It is not very difficult to port the canonical implementation given by Numerical Recipes (which I won't show and not just for licensing reasons); if you Google for a coefficient you'll see that this approximation is, indeed, ubiquitous. There exists a better approximation in the literature, one that is more

Brainfuck in Java

2011-11-17T18:45:00.001-03:00

(I don't feel like writing a punning title.) Last time I showed how the use of functors allows for modular and type-safe specification of semantics. I wrote I can't imagine this flexibility in object-oriented languages like Java or Python; fighting words for which I was justly taken to task. Here's my penance: a morally equivalent reimplementation in Java of the Brainfuck interpreter. The

Modular Semantics for Brainfuck

2011-11-11T11:05:00.001-03:00

The problem with Brainfuck is that its semantics are given by its different implementations but not all its implementations agree so that writing an interpreter is straightforward but writing portable Brainfuck programs is not. OCaml functors allows playing with pluggable semantics in a way that would be very difficult laborious with other languages. I can't imagine this flexibility in

A First-Principles GIF Encoder

2011-10-28T16:58:00.001-03:00

Also, quasicrystals. Have you ever found yourself wanting to do generated animations but didn't know how to visualize them? Since I couldn't find a self-contained GIF encoder, I made myself one. Even though it is not fast, I think its 220 lines are clear enough to be a good reference implementation to build upon. The encoder conforms to the following interface: type palette val palette : ?

Yield, Continue

2011-09-26T14:49:00.000-03:00

Roshan P. James and Amr Sabry show in "Yield: Mainstream Delimited Continuations" the interdefinability of yield-style generators and delimited continuations. Their encoding is at the same time simple and general, and even if the examples given in the paper are in Haskell, their translation into OCaml is straightforward. So much so that the result is essentially equivalent to ASAI Kenichi's

Higher Order Fun

2011-09-16T15:59:00.002-03:00

(the serious title of this post is "First-Class Modules Encode Type-Safe Reification of Types" or some such) After reading Kiselyov and Yallop's "First-class modules: hidden power and tantalizing promises", I wanted to understand how first-class modules relate to higher order types. They state that [f]irst-class modules — first-class functors — permit type constructor abstraction and polymorphism

A Note on Geomancy

2011-09-10T12:01:00.002-03:00

The Wikipedia article on Geomancy discusses the mathematical structure of the process. A passing mention to the fact that [d]ue to the mathematics of the chart, only figures that have an even number of points total can become Judges piqued my curiosity. I verified it by computer in an instant, but my curiosity was not satisfied: how can this fact be mathematically proven? It is rather simple,

4×4-Bit Matrix Transposition

2011-09-09T11:57:00.001-03:00

This is just a quick note to document a concrete variation of the technique for transposing a bit matrix via parallel bit operations in Hacker's Delight 7–3. In this case I needed to specialize it to 4×4 matrices represented by 16-bit integers. The underlying method is to recursively transpose each of the four 2x2-bit submatrices, and then block-transpose the 2x2-block matrix. Numbering the bits

Dynamically linked OCurl 0.5.3

2011-05-18T15:55:00.006-03:00

Apply this patch to Makefile.in: 15a16 > OCMKLIB = @OCAMLMKLIB@ 23c24 < CFLAGS = @CFLAGS@ @DEFS@ --- > CFLAGS = @CFLAGS@ @DEFS@ -fPIC -O2 -DPIC 30,31c31,32 < CURLFLAGS = -ccopt @CURLFLAGS@ < CURLCLIBS = -cclib -lcurl-helper -cclib "@CURLLIBS@" --- > CURLFLAGS = @CURLFLAGS@ > CURLCLIBS = @CURLLIBS@ 49c50 < $(OCBYTE) -custom -a $(FLAGS) $(CURLFLAGS) -o $@ $(CURLBCOBJS) $(CURLCLIBS) --- > $

And Yet They Complain

2011-05-17T18:35:00.002-03:00

Compare and contrast. PHP: Java: import java.io.IOException; import java.io.Reader; import java.io.Writer; import javax.servlet.ServletException; import javax.servlet.annotation.WebServlet; import javax.servlet.http.HttpServlet; import javax.servlet.http.HttpServletRequest; import

A Fork-Join framework on a budget

2011-05-07T13:20:00.003-03:00

And by "on a budget" I mean in under 150 lines of code. Commented, no less. Of course this comes with some limitations: I restrict myself to the embarrassingly parallel case where the client code wants to partition a computation equally among identical workers. I also restrict myself to pure OCaml without external dependencies. Furthermore, I have not been entirely diligent with either my error

Finding Duplicate Files, on Batteries

2011-02-05T12:26:00.001-03:00

I just got another machine. I had to migrate almost 18 years of backups, documents and other digital records. Many of these were duplicated; some I filtered by hand but I needed to automate the bulk of the process. Nothing fancy, just something to guide me in the pruning. To reduce the amount of code needed I dove head first on Batteries. Here is the result, in less than two pages of fully

OCaml 3.12 and ocamlfind ocamldoc

2011-02-03T16:47:00.002-03:00

Just a quick note: ocamldoc in 3.12 dumps its help to stderr, unlike every other tool in the distribution. The automatic argument detection of Findlib 1.2.6 fails to catch the output and so does not recognize any command line option. The quick fix is to edit and/or patch tools/extract_args/extract_args.ml, line 32 to read: Sys.command (sprintf "%s -help >%s 2>&1" before running ./configure

A jolt, or a shock?

2011-01-09T10:05:00.005-03:00

Things in OCaml Batteries that annoy me (i.e., this is merely opinion on my part, and not very informed at that. Caveat lector): It is incompatible with stdlib in minor random ways: List.sort requires label ~cmp Channels are not completely wrapped, so that in_channel_length (open_in_bin "foo") doesn't type Functional combinators are not what I've grown accustomed to. Turnstiles for

A First-Principles DNS Client

2010-11-13T11:48:00.000-03:00

Ever wondered how nslookup works? I'm a protocol junkie, and Domain Name (RFC 1035) has it all. It's a simple protocol with a highly structured message format, so the rich machinery of OCaml makes easy to build a simple but relatively complete client. The code is long for a blog post (a bit less than 500 lines), so I'll show the highlights and leave the rest for you to use as you see fit. Since

Text to PDF

2010-10-17T11:58:00.000-03:00

I find that the best way for me to learn is to reexpress what I read in a different but equivalent form. Transcribing notes and translation are two applications of this heuristic. In this case, I've translated this simple and pretty Factor PDF text formatter into OCaml. The result is almost as compact, at less than 200 lines of code, thanks to the compositional nature that OCaml and Factor share,

Parametric Modular Programming

2010-09-14T13:34:00.004-03:00

Generic programming as a concept popularized by Stepanov's STL is concerned with the uniform expression of algorithms decoupled from the specific data structures they operate on. By parametric modular programming I mean the uniform expression of a particular algorithm decoupling it from the specific shape of or rules obeyed by the objects it manipulates. It resolves the same driving forces behind

Rewriting the Rules

2010-09-01T14:04:00.001-03:00

The last article on pa_do sparked an interesting conversation with its author, Christophe Troestler, and reader bluestorm. It's true that pa_infix can establish optional rewrite rules for operators as a side-effect (or as an "added bonus" in the creator's words) of it installing new symbols with given arity, precedence and associativity. Given that rewrite rules are purely syntactical artifacts,

Polymorphic recursion with rank-2 polymorphism in OCaml 3.12

2010-08-22T11:34:00.000-03:00

Using polymorphic recursion in OCaml just got easy and direct! With the new syntax, Okasaki's binary random-access lists translate to OCaml 3.12 practically verbatim, without the need for cumbersome encodings. You should refer to the book (Purely Functional Data Structures, p. 147) for comparison, but here's the implementation in its entirety: type 'a seq = Nil | Zero of ('a * 'a) seq | One of

What can pa_do for you?

2010-08-18T11:13:00.002-03:00

(My puns are getting worse) A lot of things. Christophe Troestler pointed out that pa_do is a much more complete alternative to the new delimited overloading syntax in OCaml 3.12. In particular, it allows not only for the overloading of operators but of constants also, so that the following: # Num.(3**(561-1) mod 561);; - : Num.num = (561 = 3×11×17) works, with the simple (!)

Compiling OMake 0.9.8.5 with OCaml 3.12/MinGW under Cygwin

2010-08-16T14:47:00.001-03:00

Success! Since OMake doesn't really have a notion of a build environment, just one of platform (UNIX or Win32), compiling the latest release (0.9.8.5-3) from sources requires a number of modifications to the makefiles. Furthermore, OCaml has incorporated a number of warnings that make necessary adjusting some command-line parameters. Note: These steps are specifically for the MinGW port of

Smooth Operators

2010-08-14T01:29:00.003-03:00

Edit: Of course the module Num is already present in the standard library. I've renamed the module to Arith. The newly-released OCaml 3.12 includes many extensions to the sub-language of modules. One of the simplest but most practical is the syntax for locally opening modules (let open M in e), and for evaluating expressions in the context of an implicitly-opened module (M.(e), equivalent to the

Reviving an Old Tiger

2010-08-05T14:07:00.002-03:00

An old machine that proved its mettle on the line can be a handy development server, on a pinch. Especially if you're starting up by pulling your boot straps, as I currently am. I have this Blue & White G3 that served me faithfully for the last, say, 10 years. Bitrot, alas, is not a hardware problem: software version numbers climb and software authors drop support for older operating systems and

Sukhotin's Algorithm

2010-07-02T14:24:00.002-03:00

There is an obscure algorithm devised by one Boris Viktorovich Sukhotin, a Russian… linguist? mathematician? cryptographer? let's say researcher, in the early '70s, usually called Sukhotin's Vowel Identification Algorithm, whose initial aim was to quickly attack an alphabetic cyphertext encoded with an unknown substitution cypher. Jacques Guy, a linguist and programmer well-known for his interest

Diagonalize, Now!

2010-06-11T21:25:00.002-03:00

It is easy to append two lists, and the method is well-known: let rec append xs ys = match xs with | [] -> ys | x :: xs -> x :: append xs ys It is also easy to merge two lists, so that elements from the first are interleaved with those of the second: let rec merge xs ys = match xs with | [] -> ys | x :: xs -> x :: merge ys xs A simple matter of swapping two arguments! The

I am a terrible person: I read code, I think to myself "I can do better" and I set out thus, out of pride. I did just that with an OCaml implementation of the geohash geographical encoding. Even if the code I read was perfectly workable, I found it unidiomatic and somewhat bloated. I wrote two versions, the first one compact but impenetrable, the second one from first principles: what would be an

Gematric Search

2010-05-28T23:34:00.002-03:00

Given an array A.(0 ≤ i < N) of nonnegative integers, that is: (0) 〈∀ i : 0 ≤ i < N : A.i ≥ 0〉 and a positive integer s > 0, we want to find a segment of A that sums to s, if it exists. Define: S.i.j = 〈∑ k : 0 ≤ i ≤ k < j ≤ N : A.k〉 The gematric search for s in A is to find, if possible, a pair (p, q) such that S.p.q = s (it is hoped that conoisseurs would readily make the

Observable sharing and executable proofs

2010-05-15T22:06:00.002-03:00

Every rational number has an infinite repeating decimal expansion. In particular, every integer admits two decimal expansions: one with and one without a "tail of nines". This means that 1 = 0.9999…, a provable fact that many people still choose to disbelieve. What do I mean here by "provable"? I mean "provable by finitistic reasoning", that is, by a purely algebraic proof free of notions of

Properly Bound

2010-04-23T08:21:00.002-03:00

To all practitioners: the type of bind is not the type of >>=. For a monad α m, the latter has type: val (>>=) : α m → (α → β m) → β m only because >>= is used as a combinator that allows pipelining computations from left to right, as per usual convention: … m >>= fun x → n >>= fun y → … return f x y On the other hand, if you want to take maximum advantage of the Theorems for Free!

The elusive Binary Search

2010-04-22T20:44:00.001-03:00

Jon Bentley has scarred a couple of generations of programmers, or he was and continues to be right: I've assigned this problem in courses at Bell Labs and IBM. […] In several classes and with over a hundred programmers, the results varied little: ninety percent of the programmers found bugs in their programs (and I wasn't always convinced of the correctness of the code in which no bugs were

GADTs for the Rest of Us

2010-03-22T20:39:00.003-03:00

In a nutshell, generalized algebraic data types, or GADTs for short, are a first-class phantom type of sorts. The basic idea is to enrich the constructors of an ADT with a more expressive "return" type by allowing the instantiation of one or more type parameters. A simple motivating example is that of an abstract syntax in Peyton Jones's original paper:data Term a where Lit :: Int ->

Braun Trees

2010-02-21T12:37:00.002-03:00

I had a couple of interesting comments on my post about heaps and priority queues. The first is by Jérôme and is an indictment against my wrong, naïve use of Obj.magic to fake initializing extensible Vecs in the presence of double-word unboxed float arrays. There are a number of avenues to repair the defect: Use a functorial interface and monomorphize the type of vectors Use an exemplar of the

A Heap of (Regular) Strings

2010-02-16T17:38:00.003-03:00

Once you have a priority queue, suddenly it gets put to use more than once. Reading Pete Manolios' "Enumerating the strings of a Regular Expression", I found (§ 3.4) the following single-paragraph explanation of an algorithm for generating all the strings accepted by a DFA: Another approach is to […] enumerate the expression using the DFA. This can be done with a function enumDfa whose single

Heap Up (the Bernstein Sums)

2010-02-14T11:23:00.001-03:00

Happy Valentine's! The latest Programming Praxis calls for an implementation of the prime Sieve of Atkins. This sieve saves a bunch of operations with a preprocessing phase in which only square-free candidates are retained for latter sieving. For this to be efficient it is necessary to quickly count solutions to certain binary quadratic forms k·x² ± y² = n. Dan Berstein has published an elegant

A Staggering Sequence

2010-01-19T19:58:00.002-03:00

Happy new year! Inspired by N. J. A. Sloane's Seven Staggering Sequences, I started thinking about the Gijswijt sequence, A090822 in the OEIS. What appealed to me was the notion of "word logarithm" implicit in its definition: We begin with b(1) = 1. The rule for computing the next term, b(n + 1), is again rather unusual. We write the sequence of numbers we have seen so far, b(1), b(2),… b(n) in

Functional Macramé

2009-12-24T14:12:00.000-03:00

What is the meaning of an expression like let rec e = f … e … known Haskell is as "knot-tying"? As Lloyd Allison explains: A circular program creates a data structure whose computation depends upon itself or refers to itself. The technique is used to implement the classic data structures circular and doubly-linked lists, threaded trees and queues, in a functional programming language. These

Gained in Translation

2009-12-23T20:35:00.000-03:00

First of all, I'd like to apologize for the infrequent updates and the lightness of the last few entries. I seldom have time of late for anything but the quickest of finger exercises, but I wanted to put something on writing before the year is over. What better inspiration than one of Remco Niemeijer's terse solutions to the daily Programming Praxis. This week's asks for an implementation of

Reflecting on One-Liners

2009-11-06T20:42:00.000-03:00

The delightful Futility Closet posted a simple puzzler about the next year after 1961 that reads the same upside down. It is quite easy to see that it will be 6009, and to convince oneself that indeed no smaller number exists a dozen of lines of code suffice. The key to concision is to lift the syntax and semantics of monads into the problem. Since not every digit is itself a digit upon rotation

Fun with (Type) Class

2009-08-30T00:19:00.001-03:00

I'd like to motivate OCaml's object-oriented features (the "O" in "OCaml") by showing an encoding of (first-order) Haskell type classes. This will require making use of almost everything in OCaml's object buffet: class types, virtual classes, inheritance of class types and of classes, double dispatch and coercion. Haskell could be said to have the best type system among all languages in wide use

(Dis)Functional Bowling

2009-07-21T11:24:00.002-03:00

It is saddening to see people invested so heavily in cargo-cult programming practices that they cannot see natural solutions to simple problems after having their thoughts twisted by object-orientation as an ends and TDD as a fighting technique. Uncle Bob is struggling (and failing) to approach functional programming in the natural way by what seems to be his biases and commercial interests. His

Monadic Golf

2009-07-19T01:16:00.000-03:00

Reading Bonsai Code's solutions to Programming Praxis's weekly puzzles (which I can't recommend highly enough) makes me feel acutely aware of how verbose OCaml is, and how inadequate its standard library when compared to Haskell's. However, I've found that the latest puzzles yield concisely to a monadic style over the lists. Breaking with my usual literate top-down presentation I'll concentrate

The Tree Nursery

2009-06-17T23:48:00.003-03:00

On my last post, Benedikt Grundmann asked if changing representations for trie nodes, in particular eliminating 'a option-boxed references, would represent a speed-up or not. I started tinkering with a direct representation: type 'a t = { value : 'a option; split : char; lokid : 'a t; eqkid : 'a t; hikid : 'a t; } (call this representation trie1). This forces me to use a sentinel node

Simple, Efficient Trie Maps

2009-06-15T12:41:00.001-03:00

I became interested in implementing Bentley and Sedgewick's Ternary Trees by reading the challenge proposed on Programming Praxis (a great blog, by the way). I thought the algorithms would be a good fit for a purely functional data structure, and I am happy with the results. Here is my implementation. I follow the Map.S signature, so that this can be a drop-in replacement for string-keyed maps,

Algorithm-conscious, cache-oblivious

2009-06-14T23:19:00.003-03:00

No matter how credentialed a writer is, he is bound to make a mistake in print sooner or later. Raymond Chen's latest entry was for me oddly synchronous and oddly at variance with my own investigations on Bentley and Sedgewick's Ternary Trees. His apology of the hash table is technically sound, but only on the surface: there is not a single measurement to back up his assertions. Here is my data.

Hash 'n Mix

2009-06-12T21:32:00.003-03:00

How good is the hash function in your language of choice, particularly for strings? Chances are, not very. I applied the classical statistical tests popularized by Knuth and I was very surprised to see how bad OCaml's hash function on strings is. I applied the chi-square test on the distribution of hashes over /usr/share/dict/words, for almost 235.000 words. I binned the integers from the most

Euler's Power Riffs

2009-06-05T16:43:00.001-03:00

Ed Sandifer is an exegete of Euler's methods. In his latest "How Euler Did It", he shows the method through which he arrived at closed polynomials for the sums of n-th powers of the first x integers: In general, Euler has us multiply the terms of Σxn by (n + 1)/(n + 2) x, (n + 1)/(n + 1) x, (n + 1)/n x, … (n + 1)/2 x and (n + 1)/1 x, respectively, and add the appropriate linear term and to get

Immutability Redux

2009-06-05T15:11:00.003-03:00

My last post generated a ton of very interesting discussion. I'd like to summarize it here to bring the topic to closure. In view of the excellent analysis performed by Mauricio Fernández , Ketan's comment: At this point, you don't have the data to say what you said. You could just as easily say OCaml penalizes mutable data, or, less judgmentally, that it is less well-optimized for that use

Is Immutable Data Slow?

2009-05-26T01:15:00.000-03:00

Is immutatble data always slower than mutable state? I was challenged in a discussion over at Reddit about this issue, and I decided to perform a little experiment to back up a rough estimate with some numbers. I was surprised and delighted to see that I could make my case very strong indeed by showing that no, immutable data can be twice as fast as mutable data in a modern functional language.

A Polymorphic Question

2009-05-14T10:10:00.001-03:00

Chris Conway asked a question that I replied, unwittingly, with a reference to a thread he started on the OCaml mailing list exactly two years ago: what is the difference between types 'a . int -> 'a vec -> 'a and int -> 'a vec -> 'a? Strictly speaking, the latter is, in isolation, ill formed: the type variable 'a is unbounded! The convention is to implicitly universally quantify all unbound

Okasaki's Random Access Lists

2009-05-13T00:51:00.002-03:00

To close the chapter on Okasaki's Random Access Lists, I must record that there is an errata on the bottom of page 145 of his Purely Functional Data Structures. The argument to the recursive call to update it must read Zero (update (i div 2, p, ps)) end. It took me a while to figure it out, thinking that I had made a mistake. For completeness, here's the translation for the chapter's pseudo-SML

Rank-2 polymorphism and non-uniform types, revisited

2009-05-12T22:15:00.003-03:00

I've committed a number of errors and inaccuracies in my last post that warrant clarification. The most egregious and urgent is that the definition I gave for length is utterly wrong: the type encodes the length from the inside out, so that its "most significant bit" is the inner constructor. The recursion must take the form of a right fold, not of a left fold as I wrote. The correct function is

Polymorphic Recursion

2009-05-10T00:20:00.002-03:00

Re-reading for the n-th time Chris Okasaki's From Fast Exponentiation to Square Matrices: An Adventure in Types, I tried my hand at seeing how does the latest OCaml version cope with non-regular types and the consequent polymorphic recursion. I first scoped the terrain and Googled what others had to say about this topic. I found a ten-year old OCaml Mailing List post where Pierre Weiss mentions

Simple Future

2009-03-07T22:10:00.000-02:00

A future is a computation that encapsulates the notion of asynchronously computing a value. Let me deconstruct the buzzwords: By "computation" I mean a mechanism that, eventually, reduces to or contains a value By "value" I mean a primitive object that cannot be reduced further, or rather a computation that is trivial in the sense that it returns itself when run By "asynchronous" I mean that

Small Sorts

2009-03-05T11:19:00.003-02:00

I have seen in more than one occasion sorting problems of small sizes being solved with general-purpose sorting routines. The case should be analogous to FFTs of small size, where the cases for 1-point, 2-point and 4-point transforms are special, straight-line code segments; but I haven't found the equivalent special-casing of small-size sorts. One reason for that could be that the structure of

Why so Series

2009-01-09T12:00:00.001-02:00

Notational Notions has an entry raising to the challenge of showing with power series that (sin x)² + (cos x)² = 1. I jestingly but unfairly called the author a cheater for using what to me was an obvious appeal to Euler's formula (I made a mistake in naming it as De Moivre's). I reasoned thus: (sin x)² + (cos x)² = { Euler: e^ix - e^(-ix) = 2i sin x } [(e^ix - e^(-ix))/(2i)]² + [(e^ix + e^

The Essence of Concatenative Languages

2009-01-08T00:56:00.003-02:00

Andreas Rossberg defined a concise and elegant type system for the concatenative language Cat created by Christopher Diggins that makes clear, once and for all, that the nature of the paradigm is solidly functional, point-free and higher order in a way that, as John Nowak remarks, goes beyond the original conception of Backus' FP. Here I wish to contribute to fixing these important ideas by

The limits of Hindley-Milner

2009-01-07T17:30:00.003-02:00

The simplest thing in the world. Concatenate two pairs of lists component-wise: # fun (a, x) (b, y) -> (a @ b, x @ y) ;; - : 'a list * 'b list -> 'a list * 'b list -> 'a list * 'b list = Why, let's abstract out the concatenation part and call it thread, so that it lifts a binary function to operate on pairs component-wise: # let thread f (a, x) (b, y) = (f a b, f x y) ;; val thread :

Ring Laws

2009-01-05T14:38:00.001-02:00

This is a really basic derivation of elementary facts about rings, just for the record. I follow Milne's definition of a ring (R, +, 0, -, ⋅ 1) as a commutative group (R, +, 0, -) equipped with an additional operation ⋅ and a distinguished 1 ∈ R such that (R, ⋅, 1) is a monoid, and ⋅ distributes over + both on the left and on the right: for all a, b, c ∈ R (a + b)⋅c = a⋅c + b⋅c a⋅(b + c) = a⋅b

Proof-directed Debugging: A Real Example

2008-12-17T23:13:00.001-02:00

I was reading this excellent introduction to the K programming language (go ahead, get immersed into it. I'll wait for you) when I got piqued by the strange function where: &1 2 3 4 / where: returns the number of units specified 0 1 1 2 2 2 3 3 3 3 &0 1 1 0 0 1 / where: an important use to get the indices of the 1s 1 2 5 Beyond the need (or not) for such a function, my immediate

Stream of Consciousness

2008-12-02T00:36:00.002-02:00

Wouldn't you like to write code like this: reading "ebooks/345.txt" ( lines |> skip_until (matches "^\\*\\*\\* START OF") |> skip |> filter is_empty |> words |> fmap String.uppercase |> take 20 |> to_list ) and have it spit: - : string list = ["DRACULA"; "BY"; "BRAM"; "STOKER"; "1897"; "EDITION"; "TABLE"; "OF"; "CONTENTS"; "CHAPTER"; "1"; "JONATHAN"; "HARKER'S"; "JOURNAL"; "2"; "

(One Flew Over The) Cuckoo's Hash

2008-11-09T20:57:00.001-02:00

In a conversation over reddit, reader nostrademons suggested Cuckoo Hashing as a hash scheme with constant-time worst-case look-ups. References to the algorithm abound, but implementations are scarce, so I set out to write code. It turned out to be more difficult than I anticipated. The original article describing Cuckoo Hashing explains the basic scheme better than the Wikipedia article does,

Wordle

2008-11-09T12:37:00.003-02:00

Are wordles a novel visualization technique, or the Applet-equivalent of fridge magnet poetry? I'm not decided; meanwhile, I've compiled one of all my posts in the last year or so. Pure vanity, perhaps, but with pretty results:

Group-By Redux

2008-10-31T20:44:00.000-02:00

I sometimes like to defunctionalize a recursive function to see what shadow it projects against the wall of the cave. OCaml being strict, the tail recursive, eager, "imperative" version of the function is dual to the "pure", functional one. I've written before about the chain from direct style to CPS to defunctionalization, so I'll not make this a tutorial but a worked-out example. Starting from

Extreme Recursion

2008-10-29T21:21:00.000-02:00

For a data processing application, I needed a way to group data records together according to some criteria. This is the "reduce" phase of the map-reduce transformation, or the group-by phase of a select-project-group query. My specific problem called for a way to group records in an input list into output sublists by testing them against the first such record considered. More specifically, the

Top Drawing

2008-10-15T19:30:00.003-03:00

I wrote the last time about simple ways to "just get something onto the screen", and I ended by exploring a simple Top Draw program. I hinted at the ease with which Top Draw allows compositing a complex "painting", taking more or less by fiat the examples included with the program. I since took advantage of the basic rosette drawing subroutine to make a wallpaper that I could actually install:

Procedural Drawing

2008-10-13T12:49:00.005-03:00

Pretty pictures, again. There are now a number of "toys" with which to "recreate" the experience of turning on the old computer (C-64, Spectrum, Apple II or what had you) and being greeted with a BASIC prompt. I've written before about how SDL can give you a simple, direct (!) buffer to which to write pixels; the problem it has is that it does not know anything about drawing any object more

Just draw something on the screen!

2008-08-31T13:54:00.002-03:00

Nostalgia for times past sometimes leads to frustration and anger. Yes, times are harder for would-be pixel artists, but nothing a little work can't solve. Let's do fractals in OCaml! Suppose you've already installed the wonderful findlib (vielen Dank, Herr Stolpmann!). Suppose, furthermore, you've succeded in compiling OcamlSDL. This might look like a heavy prerequisite to fulfill before

Aperiodic Tilings

2008-08-17T22:14:00.004-03:00

When you thought that your obsession had run its course and left you in peace, finally, along comes something new and shiny to once more lead you astray. I've written half a dozen posts about sorting networks and genetic algorithms; I thought I had put that topic to rest. What am I to do when I find the Tilings Encyclopedia later the same week? How could I resist this aperiodic fest of

Monads are Plug-ins

2008-08-15T21:02:00.001-03:00

As Haskell gains popularity, a dozen articles or more a month about them make the front page at the Programming reddit. Most deal with the necessity of using and understanding monads to control side-effects in Haskell. This is only natural and to be expected since, in Haskell, they're a language design decision, and as such as inescapable as laziness and as structural as the predefined operator

A Family Portrait

2008-08-05T21:04:00.001-03:00

I succeeded in finding a minimal 8-element sorting network with 19 comparators grouped in 6 stages. For that, I needed a change in my fitness evaluation function to reflect an insight I had while preparing the last post. My original fitness evaluator was monotone first on size and then on depth, so that fitness(s, d) < fitness(s′, d′) ⇔ s < s′ ∨ s = s′ ∧ d < d′. It is, I found

Sorting out Creationism

2008-08-04T21:06:00.002-03:00

I told you there's no end to tweaking a Genetic Algorithm. As it is, the program is not very powerful; it cannot find minimal networks of width 7: % ./ganet -width 7 -pool 100 -seed 11 Searching for a 7-network of size 16 and depth 6 (fitness = 34.00000) 1 act = 3.00%, avg = 8.66667, max = 10.00000 (39/24) 2 act = 4.00%, avg = 9.25000, max = 11.00000 (38/23) 3 act = 6.00%,

Sorting out Evolution

2008-08-04T00:05:00.000-03:00

As a belated end to my exploration of sorting networks (1, 2, 3, 4, 5), I experimented with genetic algorithms to find minimal sorting networks for n elements. And when I write experimented, I mean a couple of weeks of tweaking parameters and code exploring ways for my program to run faster, and to find better and larger networks. Before you continue reading, let me warn you that I wasn't

Curried Intuitions

2008-07-30T20:54:00.003-03:00

This is not a culinary but a logical exploration. There is continuous interest on the Curry-Howard correspondence not only from logicians but also from practicioners of typeful programming. I link just to the last two to appear on Reddit; as Baader-Meinhof would have it, I was reading the entry about the development of intuitionistic logic on the Stanford Encyclopedia of Philosophy when it

Picturing Networks

2008-07-12T20:11:00.003-03:00

This is what a sorting network looks like: It is a sorting network of width 8 with a minimal number of 19 exchange boxes and 6 parallel stages. Each item to be sorted is represented by a horizontal line, and there are eight of them. Each exchange box is represented by a thicker vertical line between inputs. If the exchange boxes can be scheduled to run in parallel without interference, they

Sorting out Sorters

2008-07-09T19:12:00.002-03:00

Previously I proved how the zero-one principle can test if a comparator network is actually a sorting network or not. This can be efficiently implemented as a program. I'll represent a comparator network of width w as an array of exchange boxes: type network = (int * int) array Each entry of the array is a pair (i, j) with 0 ≤ i ≤ j < w, representing an exchange box between "wires" or indices

The Zero-One Principle

2008-07-09T14:08:00.002-03:00

Continuing my treatment of comparator networks, I've experimenting with the discovery of minimal sorting networks using evolutionary programming, about which I plan to write in the future. One of the things needed for that is a means of quickly evaluating if a given network actually sorts all sequences of a given length or not. There is a very powerful theoretical result, called the zero-one

Sorting out Sorting

2008-07-02T09:17:00.001-03:00

I believe that refactoring in the functional milieu is as important as it is in the object-oriented world. There's usually room for further improvement of one's definitions. Often, it is no more than the trivial application of selective inlining of definitions that clarify code that turned out more cluttered and opaque that it could have been, possibly from working at a remove from the problem

Bitonic Sorting

2008-06-27T19:28:00.006-03:00

The riffle shuffle I've written about is not a mere card trick. It is a basic building block in the art of devising parallel networks for efficient use of SIMD computers. A typical application is the so-called bitonic sort. An elementary introduction to the algorithm with animations might make its working clear, but I find Knuth's exposition transparent: Let us say that a sequence 〈z1, … zp〉 of

The Riffle Shuffle

2008-06-25T22:37:00.002-03:00

Take a deck of cards. Split it into halves having the same number of cards each, and put them together so that the first card of the first half goes first, the first card of the second half goes second, the second card of the first half goes third; and so on interleaving cards from each half until your deck is put together back again. This operation is called the riffle shuffle. It is easy to

When there's nothing on the other side

2008-06-16T20:45:00.005-03:00

Much has been written of how a Maybe monad translates cleanly into generic Java or C#. I have done so in this blog. The fact remains that, more often than not, it is not even necessary to wrap your code in a monad to avoid testing an object reference for null. There is a pattern language of object-oriented programming called null object. Whether it is well-known or not, I can't say; anecdotal

Random Experiments

2008-06-09T23:27:00.005-03:00

I often find it is much more rewarding to tackle an algorithmic or mathematical problem from an experiential perspective rather than from a formal one. Trying to get some test data for an earlier program, I thought about a couple of ways of generating random increasing sequences. Intent on generating n random points 0 = x0 ≤ x1 ≤ … ≤ xn-1 = 1 on the unit interval, I thought the most efficient

Monotone Cubic Interpolation

2008-06-06T12:56:00.001-03:00

(20090728 omission corrected.) The Wikipedia article on monotone cubic interpolation is, regrettably, not of very good quality. The idea is to precondition the derivatives (control points) for the cubic Hermite splines interpolating a monotonic data set so that the resulting piecewise cubic is also monotonic. The algorithm given is extracted from a paper which is not publicly available online.

A Circular Triviality

2008-06-05T10:49:00.002-03:00

(Minor corrections) This is my own take at the corollary to the Intermediate Value theorem on the unit circle. It is not substantially different to the proof linked to, so its value is zero everywhere (maybe except for a countable subset). In particular, this is a special case of the much more general Borsuk-Ulam theorem. Consider f a continuous function with domain on the unit circle. Then

Romantic, or Enlightened?

2008-05-04T10:40:00.000-03:00

It is not much of a confession to say that I'm of a rather dogmatic disposition regarding the need for strict, clear and unambiguous formalisms —let this serve— in the endeavors of formal thought. Mathematics are a testament to this, but, somewhat inexplicably, no other human science has gone as far. Computer Science, its little sibling, should have been expected to follow its steps; instead, it

Fixnum Figurations

2008-04-11T00:32:00.001-03:00

The polytopic numbers P.k.n are a kind of figurate numbers giving the number of lattice points on a k-dimensional simplex (a right triangle, tetrahedron, …) x0 + x1 + … + xk-1 ≤ n of integer side n. For k = 2 we have the Pythagorean triangular numbers 1, 3, 6, 10…, the last one called the tetractys. In general, the way to calculate P.k.n is to stack n simplices of dimension k - 1 with decreasing

OCaml and typeful programming: an annotated bibliography (of sorts)

2008-03-29T11:04:00.005-03:00

I cannot help but feel somewhat envious at the high level of expertise that the Haskell community display at effectively using the advanced type system the language provides. Many of the techniques are not applicable to OCaml, which lacks higher-ranked polymorphism. Some of these techniques, however, can be translated to OCaml, but these seem to be more folklore than codified practice, and

Splitting Hairs

2008-03-20T21:47:00.004-03:00

It is often claimed that the formal derivation of an algorithm hand-in-hand with its specification is too hard to do, so that it is only viable for toy examples. I have found, as Dijkstra repeatedly has, that discipline and restraint in the drive to "just code" are key to succeeding. As an example, I'll show the creation from scratch of a program I didn't know before.Aside: You'll have to believe

Generating Combinations

2008-03-19T10:53:00.002-03:00

Only for the record, and because I arrived at this form of the algorithm after massaging the one given in Algorithms for Programmers, Algorithm 6.1 "Lexicographic and Co-Lexicographic Order" and I find it very pretty. First the algorithm, then the explanation: let iter_comb n k (f : int array -> unit) = let v = Array.init k (fun i -> i) in f v; while v.(0) != n - k do let j = ref (k -

Bitwise Dice

2008-03-13T21:33:00.005-02:00

I'm rereading this paper by Knuth and Yao [1], which could be called "How to throw a die when all you have is a penny", or something. Its premise is, how can you generate a random variable with arbitrary distribution when all you have is a perfectly fair binary random variate? It begins with this blindingly eye-catching diagram: Every round node is a coin-toss (a bit-flip), and transitions

Thinking Inside the Box

2008-03-09T21:38:00.000-02:00

There's a non-trivial algorithm in Computer Graphics, the so-called Kay-Kajiya test, that is actually trivial to derive by carefully thinking about the problem it solves. A axis-aligned box is the 3-dimensional generalization of a closed interval. Intuitively, it's a rectangular box whose six sides are parallel to the three axes; formally, given points P = (px, py, pz) and Q = (qx, qy, qz), it is

The Castle of Glyphs

2008-03-06T00:15:00.005-02:00

Well, in English they're not called castles, but rooks. Surprisingly, the castling move is called enroque in Spanish, which is cognate to rook. Suppose you want to find non-self-intersecting closed rook's tours on a m-by-n chessboard. How would you go about it? But first, why would you want to do that? I've found they make pretty linear patterns, somewhat reminiscent of arabesques and square

ocamlsdl on MacOS X 10.5 "Leopard"

2008-03-03T21:33:00.002-02:00

I've found that there a number of pitfalls that make getting ocamlsdl up and running on Leopard a less than straightforward experience. For the record, here are a number of fixes I found I needed to apply. I'm reconstructing the process after the fact, so I apologize if anything is missing. 0. Prepare your environment You'll need to set up some environment variables first. I'm a tcsh user,

The (square) root of refinement

2008-02-27T19:51:00.000-02:00

There's this great little book, A Method of Programming by Edsger W. Dijkstra and Wim Feijen, which is dry and precise as a smack of a ruler against collected fingertips. Really, I cannot recommend it highly enough. It includes a little essay, Coordinate transformation that —for me— illustrates beautifully the methodical, stepwise refining of a program by meaning-preserving transformations. They

Pass the Bucket

2008-02-26T17:11:00.000-02:00

Although not without its problems, hash tables are a popular data structure for storage and retrieval of key/value pairs, otherwise known as finite maps or finite functions. It is the main data structure in dynamic languages like JavaScript, AWK, Arc, Io, Python, Perl and others. To recapitulate, the idea behind a hash table is to store data in an array (which is a finite map with domain a