As noted in my last post , I recently released ppad-fixed , a high-performance fixed-width word library meant for use in cryptographic applications. At present I use this library to drive elliptic curve arithmetic in ppad-secp256k1 , as well as stuff that depends on that, e.g. ppad-bip32 . It’s safe to say I have few users at the moment, but, as they say, “the way you do anything is the way you do…
I’ve just released a new version of ppad-secp256k1 that supports dramatically faster Schnorr and ECDSA signature schemes, powered by faster elliptic curve arithmetic under the hood. This follows on my previous posts in what are starting to constitute a sort of secp256k1 series. In the last post I had used the wNAF method for elliptic curve scalar multiplication to glean a large performance boost…
Taproot Assets endeavours to provide completely reproducible and verifiable build artifacts for all releases. These include binaries for a number of target architectures/platforms, along with source code and vendored dependencies, all packaged up in gzipped tarballs, or in zip(1) files. Each release comes with a manifest of these artifacts along with accompanying SHA256 digests. To attest the…
I wanted to make a quick addendum to my last post in that I did some further experimenting with Data.ByteString.Builder on both the base16 encoding and decoding tasks, comparing results with the impure direct-allocation-and-write-based implementations I mentioned previously. I had remarked that builders can be pretty efficient if you’re careful to pack your data aggressively, such that you don’t…
In this post I’m going to incrementally optimise a simple base16 (hexadecimal) encoding routine and illustrate what sort of performance boost each optimisation yields. Hopefully it can be used to glean a bit about what tends to make Haskell code fast – especially code that deals with bytestrings. You can think of this as a kind of supplement to Chris Done’s Fast Haskell: Competing with C at…
( UPDATE 2026/02/06 : the nukes were redeployed; I rode the bomb down whooping, Major Kong style.) I nuked all of my social media accounts years ago and never looked back. My general take is that all legacy web 2.0-style social media stuff needs to be ground under a boot, and then the boot filled with cement and sank to the bottom of a particularly deep ocean. Just in case. That said, I recently…
In my last post I mentioned that both the Schnorr and ECDSA signature schemes on secp256k1 could be made faster via the so-called wNAF method for elliptic curve point multiplication (short for the cumbersome “w-ary non-adjacent form”). I implemented wNAF for ppad-secp256k1 afterwards, adding a bunch of functions that use it internally. The only “downside” to the use of wNAF is that one needs to…
I’ve released a library supporting BIP340 Schnorr signatures and deterministic ECDSA on the elliptic curve secp256k1. Get it while it’s hot – for when you just aren’t feeling libsecp256k1! This is another “minimal” library in the ppad suite of libraries I’m working on. Minimal in the sense that it is pure Haskell (no FFI – you can check out ppad-csecp256k1 if you want that) and depends only on…
Just FYI, I’ve dropped a few simple libraries supporting SHA-{256,512} , HMAC-SHA{256, 512} , and HMAC-DRBG . You can find the repos here: ppad-sha256 ppad-sha512 ppad-hmac-drbg Each is packaged there as a Nix flake , and each is also available on Hackage. This is the first battery of a series of libraries I’m writing that were primarily inspired by noble-cryptography after the death (or at least…
I have a little library called sampling floating around for general-purpose sampling from arbitrary foldable collections. It’s a bit of a funny project: I originally hacked it together quickly, just to get something done, so it’s not a very good library qua library – it has plenty of unnecessary dependencies, and it’s not at all tuned for performance. But it was always straightforward to use, and…
Some years ago I wrote about using recursion schemes to encode stochastic processes in an embedded probabilistic programming setting. The crux of it was that recursion schemes allow one to “factor out” the probabilistic phenomena from the recursive structure of the process; the probabilistic stuff typically sits in the so-called coalgebra of the recursion scheme, while the recursion scheme itself…
Long ago, in the distant past, Curtis introduced the idea of kelvin versioning in an informal blog post about Urbit . Imagining the idea of an ancient and long-frozen form of Martian computing, he described this versioning scheme as follows: Some standards are extensible or versionable, but some are not. ASCII, for instance, is perma-frozen. So is IPv4 (its relationship to IPv6 is little more than…
( UPDATE 2024/09/08 : while hosting your own mailserver is not covered in this post, I recommend you check out Simple NixOS Mailserver for a borderline trivial way to do it.) A couple of people recently asked about my email setup, so I figured it might be best to simply document some of it here. I run my own mail server for jtobin.io, plus another domain or two, and usually wind up interacting…
In my last post I first introduced hnock , a little interpreter for Nock , and then demonstrated it on a hand-rolled decrement function. In this post I’ll look at how one can handle the same (contrived, but illustrative) task in Hoon . Hoon is the higher- or application-level programming language for working with Arvo , the operating system of Urbit . The best way I can describe it is something…
I wrote a little Nock interpreter called hnock some months ago and just yesterday updated it to support the latest version of Nock, 4K. Nock – the base layer VM of Urbit – is a very simple little “functional assembly language” of sorts. It is of particular interest in that it is capable of practical computation (indeed, it is Turing complete) but is not defined in terms of the lambda calculus. So,…
( UPDATE 2020/06/30 : the good people at tweag.io have since published a Nix shell environment that appears to make testing arbitrary PRNGs much less of a pain. I recommend you check it out!) I recently needed a good cryptographically-secure and seedable pseudorandom number generator for Javascript. This didn’t turn out to be as trivial a procedure as I figured it’d be: most Javascript CSPRNGs I…
I recently picked up Appel’s classic Compiling with Continuations and have been refreshing my continuation-fu more generally. Continuation-passing style (CPS) itself is nothing uncommon to the functional programmer; it simply involves writing in a manner such that functions never return, instead passing control over to something else (a continuation ) to finish the job. The simplest example is…
Why does my blog often feature its typical motley mix of probability, functional programming, and computer science anyway? From 2011 through 2017 I slogged through a Ph.D. in statistics, working on it full time in 2012, and part-time in every other year. It was an interesting experience. Although everything worked out for me in the end – I managed to do a lot of good and interesting work in…
Take an iterated integral, e.g. \(\int_X \int_Y f(x, y) dy dx\). Fubini’s Theorem describes the conditions under which the order of integration can be swapped on this kind of thing while leaving its value invariant. If Fubini’s conditions are met, you can convert your integral into \(\int_Y \int_X f(x, y) dx dy\) and be guaranteed to obtain the same result you would have gotten by going the other…
You can recognize truth by its beauty and simplicity. – Richard Feynman (attributed) In one of his early emails on the Cryptography mailing list, Satoshi claimed that the proof-of-work chain is a solution to the Byzantine Generals Problem (BGP). He describes this via an example where a bunch of generals – Byzantine ones, of course – collude to break a king’s wifi. It’s interesting to look at this…
Last week Dan Peebles asked me on Twitter if I knew of any writing on the use of recursion schemes for expressing stochastic processes or other probability distributions. And I don’t! So I’ll write some of what I do know myself. There are a number of popular statistical models or stochastic processes that have an overtly recursive structure, and when one has some recursive structure lying around,…
In my last two posts about the Giry monad I derived the thing from its categorical and measure-theoretic foundations. I kind of thought that those posts wouldn’t be of much interest to people but they turned out to be a hit. I clearly can’t tell what the internet likes. Anyway, something I left out was the theoretical foundation of the Giry monad’s Applicative instance, which seemed a bit odd. I…
In my last post I went over the categorical and measure-theoretic foundations of the Giry monad, the ‘canonical’ probability monad that operates on the level of probability measures. In this post I’ll pick up from where I left off and talk about a neat and faithful (if impractical) implementation of the Giry monad that one can put together in Haskell. Measure, Integral, and Continuation So. For a…
The Giry monad is the canonical probability monad that operates on the level of measures, which are the abstract constructs that canonically represent probability distributions. It’s sort of the baseline by which all other probability monads can be judged. In this article I’m going to go through the categorical and measure-theoretic foundations of the Giry monad. In another article, I’ll describe…
Here’s a short one. I use Colin Percival’s Hacker News Daily to catch the top ten articles of the day on Hacker News. Today an article called Why Recursive Data Structures? popped up, which illustrates that recursive algorithms can become both intuitive and borderline trivial when a suitable data structure is used to implement them. This is exactly the motivation for using recursion schemes. In…
To the.. uh, ‘layperson’, pre- and postpromorphisms are probably well into the WTF category of recursion schemes. This is a mistake - they’re simple and useful, and I’m going to try and convince you of this in short order. Preliminaries: {-# LANGUAGE DeriveFunctor #-} {-# LANGUAGE LambdaCase #-} import Data.Functor.Foldable import Prelude hiding ( sum ) For simplicity, let’s take a couple of…
Some time ago I came across a way to in-principle perform inference on certain probabilistic programs using comonadic structures and operations. I decided to dig it up and try to use it to extend the simple probabilistic programming language I talked about a few days ago with a stateful, experimental inference backend. In this post we’ll Represent probabilistic programs as recursive types…
What does a dead-simple probabilistic programming language look like? The simplest thing I can imagine involves three components: A representation for probabilistic models. A way to simulate from those models (‘forward’ sampling). A way to sample from a conditional model (‘backward’ sampling). Rob Zinkov wrote an article on this type of thing around a year ago, and Dan Roy recently gave a talk on…
Randomness is a constant nuisance point for Haskell beginners who may be coming from a language like Python or R. While in Python you can just get away with something like: In [ 2 ]: numpy . random . rand ( 3 ) Out [ 2 ]: array ([ 0.61426175 , 0.05309224 , 0.38861597 ]) or in R: > runif ( 3 ) [ 1 ] 0.49473012 0.68436352 0.04135914 In Haskell, the situation is more complicated. It’s not too much…
.. this one is pretty dry, I’ll admit. David Williams said it best: .. Measure theory, that most arid of subjects when done for its own sake, becomes amazingly more alive when used in probability, not only because it is then applied, but also because it is immensely enriched. Unfortunately for you, dear reader, we won’t be talking about probability. Moving on. What does it mean for something to be…
Suppose you’re in the derivatives business. You are interested in making a market on some events; say, whether or not your friend Jay will win tomorrow night’s poker game, or that the winning pot will be at least USD 100. Let’s examine some rules about how you should do business if you want this venture to succeed. What do I mean by ‘make a market’? I mean that you will be willing to buy and sell…
I’ve updated my old flat-mcmc library for ensemble sampling in Haskell and have pushed out a v1.0.0 release. History I wrote flat-mcmc in 2012, and it was the first serious-ish size project I attempted in Haskell. It’s an implementation of Goodman & Weare’s affine invariant ensemble sampler , a Monte Carlo algorithm that works by running a Markov chain over an ensemble of particles. It’s easy to…
Applicative functors are useful for encoding context-free effects. This typically gets put to work around things like parsing or validation , but if you have a statistical bent then an applicative structure will be familiar to you as an encoder of independence . In this article I’ll give a whirlwind tour of probability monads and algebraic freeness, and demonstrate that applicative functors can be…
In Practical Recursion Schemes I talked about recursion schemes , describing them as elegant and useful patterns for expressing general computation. In that article I introduced a number of things relevant to working with the recursion-schemes package in Haskell. In particular, I went over: factoring the recursion out of recursive types using base functors and a fixed-point wrapper the ‘Foldable’…
I have another few posts that I’d like to write before cluing up the whole recursion schemes kick I’ve been on. The first is a simple note about monadic versions of the schemes introduced thus far. In practice you often want to deal with effectful versions of something like cata . Take a very simple embedded language, for example (“Hutton’s Razor”, with variables): {-# LANGUAGE DeriveFunctor #-}…
I previously wrote about implementing merge sort using recursion schemes . By using a hylomorphism we could express the algorithm concisely and true to its high-level description. Insertion sort can be implemented in a similar way - this time by putting one recursion scheme inside of another. Read on for details. Apomorphisms These guys don’t seem to get a lot of love in the recursion scheme…
I noticed this article by Tom Ellis today that provides an excellent ‘demystified’ introduction to automatic differentiation. His exposition is exceptionally clear and simple. Hopefully not in the spirit of re-mystifying things too much, I wanted to demonstrate that this kind of forward-mode automatic differentiation can be implemented using a catamorphism, which cleans up the various let…
I’m presently at NIPS and so felt like writing about some appropriate machine learning topic, but along the way I wound up talking about parameterized recursive types, and here we are. Enjoy! One starts to see common ‘shapes’ in algebraic data types after working with them for a while. Take the natural numbers and a standard linked list, for example: data Natural = One | Succ Natural data List a =…
Merge sort is a famous comparison-based sorting algorithm that starts by first recursively dividing a collection of orderable elements into smaller subcollections, and then finishes by recursively sorting and merging the smaller subcollections together to reconstruct the (now sorted) original. A clear implementation of mergesort should by definition be as faithful to that high-level description as…
I’ve released a number of libraries for doing Markov Chain Monte Carlo (MCMC) in Haskell. You can get at them via a ‘frontend’ library, declarative , but each can also be used fruitfully on its own. À la carte, if you will. Some background: MCMC is a family of stateful algorithms for sampling from a large class of probability distributions. Typically one is interested in doing this to approximate…
Recursion schemes are elegant and useful patterns for expressing general computation. In particular, they allow you to ‘factor recursion out’ of whatever semantics you may be trying to express when interpreting programs, keeping your interpreters concise, your concerns separated, and your code more maintainable. What’s more, formulating programs in terms of recursion schemes seems to help suss out…
Automatic differentiation is one of those things that’s famous for not being as famous as it should be (uh..). It’s useful, it’s convenient, and yet fewer know about it than one would think. This article (by one of the guys working on Venture ) is the single best introduction you’ll probably find to AD, anywhere. It gives a wonderful introduction to the basics, the subtleties, and the gotchas of…
Lately I’ve been trying to do some magic by way of nonstandard interpretations of abstract syntax. One of the things that I’ve managed to grok along the way has been the problem of sharing in deeply-embedded languages. Here’s a simple illustration of the ‘vanilla’ sharing problem by way of plain Haskell; a function that computes 2^n: naiveTree :: ( Eq a , Num a , Num b ) => a -> a naiveTree 0 = 1…
( UPDATE 2016/08/15 : Here be monsters. This code is ancient, the style is not really idiomatic Ansible, and it’s likely that nothing works anymore.) EC2 is cool. The ability to dynamically spin up a whack of free-to-cheap server instances anywhere in the world at any time, is.. well, pretty mean. Need to run a long computation job? Scale up a distributed system? Reduce latency to clients in a…