tag:blogger.com,1999:blog-58886582951824808192015-10-03T21:13:51.192-03:00Alaska Ataca a KamtchatkaUnder the spell of Dijkstra's dreamMatías Giovanninihttps://plus.google.com/109173757899411658539noreply@blogger.comBlogger161125tag:blogger.com,1999:blog-5888658295182480819.post-30202457230347817592012-10-25T11:58:00.000-03:002012-10-26T12:44:28.086-03:00How to Write a Simple Web Application Using OcamlnetThis post might seem to be in apparent contradiction: Ocamlnet is a large, very opinionated framework for network programming that solves most, if not all, those infrastructure issues that need to be taken care of when writing a networked, distributed, fault-tolerant server, from process management to string decoding and including protocol parsing and building. The fact is that Ocamlnet is not Matías Giovanninihttps://plus.google.com/109173757899411658539noreply@blogger.com2tag:blogger.com,1999:blog-5888658295182480819.post-82407707654476583202012-08-06T21:15:00.003-03:002012-08-06T21:21:31.378-03:00Merge RightThe so-called master-transaction update is one of the, if not the defining algorithms of the discipline formerly known as "data processing". Given two sorted files of records with increasing keys, the process applies each record in the transaction file to each record of the the master file and outputs the result, if any, to the updated master file in one pass over each input. The same algorithm Matías Giovanninihttps://plus.google.com/109173757899411658539noreply@blogger.com2tag:blogger.com,1999:blog-5888658295182480819.post-4185179621174351352012-08-02T10:59:00.002-03:002012-08-02T10:59:25.604-03:00A Helping Phantom HandYou don't have to be writing an interpreter or some other kind of abstract code to profit from some phantom types. Suppose you have two or more functions that work by "cooking" a simple value (a float, say) with a lengthy computation before proceeding:
let sun_geometric_longitude j =
let je = to_jcen (to_jde j) in
(* … computation with je … *)
let sun_apparent_longitude j =
let je = Matías Giovanninihttps://plus.google.com/109173757899411658539noreply@blogger.com2tag:blogger.com,1999:blog-5888658295182480819.post-73115514104434169072012-07-19T12:00:00.000-03:002012-07-19T12:00:11.506-03:00Theorems for Free: The Monad EditionThis is for the record, since the derivations took me a while and I'd rather not lose them.
A functor is the signature:
module type FUNCTOR = sig
type 'a t
val fmap : ('a -> 'b) -> ('a t -> 'b t)
end
satisfying the following laws:
Identity: fmap id ≡ id
Composition: fmap (f ∘ g) ≡ fmap f ∘ fmap g
An applicative structure or idiom is the signature:
module type APPLICATIVE = Matías Giovanninihttps://plus.google.com/109173757899411658539noreply@blogger.com3tag:blogger.com,1999:blog-5888658295182480819.post-38313128588004615442012-07-17T14:36:00.000-03:002012-07-17T17:14:47.045-03:00An Odd LemmaWhile proving that every monad is an applicative functor, I extracted the following derivation as a lemma:
fmap f ∘ (λh. fmap h x)
≡ { defn. ∘, β-reduction }
λg. fmap f (fmap g x)
≡ { defn. ∘ }
λg. (fmap f ∘ fmap g) x
≡ { Functor }
λg. fmap (f ∘ g) x
≡ { abstract f ∘ g }
λg. (λh. fmap h x) (f ∘ g)
≡ { defn. ∘, η-contraction }
(λh. fmap h x) ∘ (f ∘)
for all f, x. This is the YonedaMatías Giovanninihttps://plus.google.com/109173757899411658539noreply@blogger.com0tag:blogger.com,1999:blog-5888658295182480819.post-83979168451845136242012-07-12T12:00:00.000-03:002012-07-12T12:00:11.010-03:00A minor branch off Braun TreesRevisiting the post on Braun Trees I noticed that, while pedagogical, the implementation of the root replacement operation rep can be streamlined a bit. By inlining the mutually recursive siftdown, specializing on the matches and adding guards, the result is as follows:
let rec rep compare e = function
| N (_, (N (el, _, _) as l), E)
when compare el e < 0 ->
N (el, rep compare e l, E)
| N Matías Giovanninihttps://plus.google.com/109173757899411658539noreply@blogger.com0tag:blogger.com,1999:blog-5888658295182480819.post-73832923640376030812012-07-09T12:00:00.000-03:002012-07-09T12:00:06.038-03:00Existential CrisisIn a long discussion at LtU, user Jules Jacobs advances a use-case that for him would have been difficult to solve in a statically-typed language. I focus on his first two points:
A data structure that is a container of T plus a function on T's. I would have needed existential types to hide the T, which I don't get in many languages.
A couple of functions that take heterogeneous list of items Matías Giovanninihttps://plus.google.com/109173757899411658539noreply@blogger.com2tag:blogger.com,1999:blog-5888658295182480819.post-1077937843976597102012-07-02T12:00:00.000-03:002012-07-03T01:44:48.435-03:00Assessing AbstractionsBack to OCaml! Catching up with StackOverflow's OCaml questions, I found an interesting one about private type abbreviations in module signatures. One thing in that conversation that struck me as odd was the assertion that the compiler optimizes single-constructor variants, thereby subsuming the semantics of Haskell's all three declarators, data, type and newtype, into one. Definitive proof wouldMatías Giovanninihttps://plus.google.com/109173757899411658539noreply@blogger.com2tag:blogger.com,1999:blog-5888658295182480819.post-13434316582506269552012-06-29T12:00:00.000-03:002012-06-29T14:52:38.849-03:002D Interpolation, Part 5: Final OptimizationsThe code has now the proper shape to carry out optimizations to their logical consequences, to the point that I question the wisdom in some of the previous transformations. It is true that in compiler construction some passes introduce constructs only for latter passes to eliminate them, in the hope of an overall simplification. In this case the starting point will be the elimination of the Matías Giovanninihttps://plus.google.com/109173757899411658539noreply@blogger.com0tag:blogger.com,1999:blog-5888658295182480819.post-58202786093258823372012-06-28T12:00:00.000-03:002012-06-28T12:00:10.956-03:002D Interpolation, Part 4: ARGB InterpolationAfter linearizing all array accesses, interpolating ARGB values is easy from the algorithmic side of things; so easy things first. I'll handle the pixel interpolation proper by abstracting them away in their own little functions. Processing an ARGB source array is just a matter of changing the variable declarations:
final int[] srcpix = {
0xff0051ff, 0xff00fffb, 0xff9cff00, 0xff0051ff,
Matías Giovanninihttps://plus.google.com/109173757899411658539noreply@blogger.com0tag:blogger.com,1999:blog-5888658295182480819.post-40685271024611500222012-06-27T12:00:00.000-03:002012-06-27T12:31:36.607-03:002D Interpolation, Part 3: Linear Array AccessesLast time I've hoisted all accesses to the source array. This opens the door to being able to process linear arrays representing a matrix in row-major order by stenciling. Not only that, but I was able to completely eliminate the need to have a bordered array on input by explicitly replicating elements as needed. The first step is to use a row buffer into which to copy the elements to be Matías Giovanninihttps://plus.google.com/109173757899411658539noreply@blogger.com0tag:blogger.com,1999:blog-5888658295182480819.post-18679278931458734582012-06-26T10:00:00.000-03:002012-06-26T13:26:48.353-03:002D Interpolation, Part 2: Minimizing Array AccessesLast time I massaged the interpolator to avoid computing every time the linear transformation from destination space to source space, using only integer variables. With that rewriting, it is time to avoid referencing source values more than is needed. First thing we do, let's name all elements:
void interp0() {
int offset = 0;
int yn = 0;
int yi = 1;
for (int i = 0; i < height; i++) {
Matías Giovanninihttps://plus.google.com/109173757899411658539noreply@blogger.com0tag:blogger.com,1999:blog-5888658295182480819.post-36876000985566768842012-06-25T12:00:00.000-03:002012-06-25T12:20:46.905-03:002D Interpolation, Part 1: The Digital Differential AnalyzerTo my Planet OCaml readers, I apologize for veering into Java. I've been playing with Processing of lately, because it's far easier to prototype silly, simple animations (fractals! Fractals everywhere!) in it than by using OCamlSDL, say. Last time I showed a basic 2D interpolator; now it's time to start massaging it into shape. Let's recall the original code:
void interp0() {
final float dy =Matías Giovanninihttps://plus.google.com/109173757899411658539noreply@blogger.com0tag:blogger.com,1999:blog-5888658295182480819.post-18129198244071370042012-06-22T14:51:00.000-03:002012-06-22T14:57:23.618-03:002D Interpolation, Part 0: The Groundwork(First of a series) My process for going from a textbook implementation of an algorithm to an efficient production-grade version of it is to methodically apply meaning-preserving transformations that make the code progressively tighter. In this case I'll massage a naïve 2D interpolator that selectively uses nearest-neighbor, bilinear and bicubic interpolation. I started by studying a basic Matías Giovanninihttps://plus.google.com/109173757899411658539noreply@blogger.com2tag:blogger.com,1999:blog-5888658295182480819.post-49530784180620936262012-02-22T10:43:00.000-03:002012-02-22T10:44:23.305-03:00For the Right HandUseful generic functions are usually the result of composing useful generic functions; the fact that these are easy to write is, however, not an excuse for not having them in a rich prelude. Given a total function for splitting a list at a given point:
let rec split_at n = function
| [] -> [], []
| l when n == 0 -> [], l
| x :: xs ->
let l, r = split_at (pred n) xs in
x :: l,Matías Giovanninihttps://plus.google.com/109173757899411658539noreply@blogger.com1tag:blogger.com,1999:blog-5888658295182480819.post-8426757566575103792012-01-12T14:37:00.000-03:002012-06-22T17:07:15.517-03:00File Sharing on the Spot(now with highlighting!) 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 Matías Giovanninihttps://plus.google.com/109173757899411658539noreply@blogger.com6tag:blogger.com,1999:blog-5888658295182480819.post-74333271969965340192012-01-11T10:02:00.001-03:002012-01-12T14:40:36.965-03:00Eighteen Million NoisesUpdate: 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 Matías Giovanninihttps://plus.google.com/109173757899411658539noreply@blogger.com0tag:blogger.com,1999:blog-5888658295182480819.post-11005183529927077682012-01-09T11:22:00.000-03:002012-01-09T11:55:50.913-03:00Putting Noise to the TestSo 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 Matías Giovanninihttps://plus.google.com/109173757899411658539noreply@blogger.com4tag:blogger.com,1999:blog-5888658295182480819.post-39430320838447502372012-01-06T13:39:00.000-03:002012-01-06T13:39:26.680-03:00Perlin's Simplex NoiseGraphics 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 Matías Giovanninihttps://plus.google.com/109173757899411658539noreply@blogger.com3tag:blogger.com,1999:blog-5888658295182480819.post-23532327662565023502011-12-30T15:50:00.000-03:002011-12-30T15:50:32.002-03:00(One by) Four by Nine
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 Matías Giovanninihttps://plus.google.com/109173757899411658539noreply@blogger.com2tag:blogger.com,1999:blog-5888658295182480819.post-46299962558908338162011-12-29T14:12:00.002-03:002011-12-29T14:15:24.965-03:00Vose's Alias MethodThis 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 Matías Giovanninihttps://plus.google.com/109173757899411658539noreply@blogger.com3tag:blogger.com,1999:blog-5888658295182480819.post-38689320932408969852011-12-21T11:53:00.000-03:002011-12-21T11:53:54.270-03:00A Better (Gauss) Error FunctionIf 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 Matías Giovanninihttps://plus.google.com/109173757899411658539noreply@blogger.com1tag:blogger.com,1999:blog-5888658295182480819.post-14321109598959517462011-11-17T18:45:00.001-03:002012-05-03T10:55:30.384-03:00Brainfuck in Java
(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 Matías Giovanninihttps://plus.google.com/109173757899411658539noreply@blogger.com4tag:blogger.com,1999:blog-5888658295182480819.post-9751388615903695362011-11-11T11:05:00.001-03:002012-05-03T10:47:55.570-03:00Modular Semantics for Brainfuck
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 Matías Giovanninihttps://plus.google.com/109173757899411658539noreply@blogger.com1tag:blogger.com,1999:blog-5888658295182480819.post-11233803975866018842011-10-28T16:58:00.001-03:002012-01-06T13:43:05.173-03:00A First-Principles GIF EncoderAlso, 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 : ?Matías Giovanninihttps://plus.google.com/109173757899411658539noreply@blogger.com0