in Code

Recent Entries (Page 3)

  • "Interpreters a la Carte" in Advent of Code 2017 Duet

    This post is just a fun one exploring a wide range of techniques that I applied to solve the Day 18 puzzles of this past year’s great Advent of Code. The puzzles involved interpreting an assembly language on an abstract machine. The twist is that Part A gave you a description of one abstract machine, and Part B gave you a different abstract machine to interpret the same language in.

    This twist (one language, but different interpreters/abstract machines) is basically one of the textbook applications of the interpreter pattern in Haskell and functional programming, so it was fun to implement my solution in that pattern — the assembly language source was “compiled” to an abstract monad once, and the difference between Part A and Part B was just a different choice of interpreter.

    Even more interesting is that the two machines are only “half different” – there’s one aspect of the virtual machines that are the same between the two parts, and aspect that is different. This means that we can apply the “data types a la carte” technique in order to mix and match isolated components of virtual machine interpreters, and re-use code whenever possible in assembling our interpreters for our different machines! This can be considered an extension of the traditional interpreter pattern: the modular interpeter pattern.

    This blog post will not necessarily be a focused tutorial on this trick/pattern, but rather an explanation on my solution centered around this pattern, where I will also add in insight on how I approach and solve non-trivial Haskell problems. We’ll be using the operational package to implement our interpreter pattern program and the type-combinators package to implement the modularity aspect, and along the way we’ll also use mtl typeclasses and classy lenses.

    The source code is available online and is executable as a stack script. This post is written to be accessible for early-intermediate Haskell programmers.

    Read more … Comments

  • Introduction to Singletons (Part 2)

    Welcome back to our journey through the singleton design pattern and the great singletons library!

    This post is a direct continuation of Part 1, so be sure to check that out first if you haven’t already! If you hare just jumping in now, I suggest taking some time to to through the exercises if you haven’t already!

    Again, code is built on GHC 8.6.1 with the nightly-2018-09-29 snapshot (so, singletons-2.5). However, unless noted, all of the code should still work with GHC 8.4 and singletons-2.4. All of the code is also available here, and you can drop into a ghci session with all of the bindings in scope by executing the file:

    $ ./Door2.hs

    Read more … Comments

  • Introduction to Singletons (Part 1)

    Real dependent types are coming to Haskell soon! Until then, we have the great singletons library :)

    If you’ve ever run into dependently typed programming in Haskell, you’ve probably encountered mentions of singletons (and the singletons library). This series of articles will be my attempt at giving you the story of the library, the problems it solves, the power that it gives to you, and how you can integrate it into your code today!1 (Also, after my previous April Fools post, people have been asking me for an actual non-joke singletons post)

    This post (Part 1) will go over first using the singleton pattern for reflection, then introducing how the singletons library helps us. Part 2 will discuss using the library for reification, to get types that depend on values at runtime. Part 3 will go into the basics of promoting functions values to become functions on types in a usable, and Part 4 will go deeper into the lifting of functions, using singleton’s defunctionalization scheme to utilize the higher-order functions we love at the type level. Part 3 will go into the basics singleton’s

    I definitely am writing this post with the hope that it will be obsolete in a year or two. When dependent types come to Haskell, singletons will be nothing more than a painful historical note. But for now, singletons might be the best way to get your foot into the door and experience the thrill and benefits of dependently typed programming today!

    1. This series will be based on a talk I gave over the summer, and will expand on it.↩︎

    Read more … Comments

  • Advent of Code 2017! Ongoing solutions and explanations

    Just a short post to share that I started a github repository of my Advent of Code 2017 Solutions, as I write them!

    I also am including my reflections and explanations on my solutions, explaining my thought processes and how the solutions work.

    Yes I definitely spent a bit too much time writing the executable, which is an automated (cached) downloader, test suite runner (on sample inputs), and benchmark suite.

    I originally was only going to casually try the problems (like I did last year), but I hit a decent global rank by accident on Day 4 (which was very suited for Haskell!), and since then I’ve been taking things seriously to try to aim for the global leaderboard (top 100). This is a struggle for me because I’m not really the fastest algorithm person, but I think it’s a fun goal for me to try to hit this year.

    Wish me luck! And if you haven’t started yet, it’s not too late to join in the fun! glguy has been maintaining the semi-official Haskell Leaderboard (join code 43100-84040706) – come join us!

    Read more … Comments

  • Hamiltonian Dynamics in Haskell

    As promised in my hamilton introduction post (published almost exactly one year ago!), I’m going to go over implementing of the hamilton library using

    1. DataKinds (with TypeLits) to enforce sizes of vectors and matrices and help guide us write our code
    2. Statically-sized linear algebra with hmatrix
    3. Automatic differentiation with ad
    4. Statically-sized vectors with vector-sized

    This post will be a bit heavy in some mathematics and Haskell concepts. The expected audience is intermediate Haskell programmers. Note that this is not a post on dependent types, because dependent types (types that depend on runtime values) are not explicitly used.

    The mathematics and physics are “extra” flavor text and could potentially be skipped, but you’ll get the most out of this article if you have basic familiarity with:

    1. Basic concepts of multivariable calculus (like partial and total derivatives).
    2. Concepts of linear algebra (like dot products, matrix multiplication, and matrix inverses)

    No physics knowledge is assumed, but knowing a little bit of first semester physics would help you gain a bit more of an appreciation for the end result!

    Read more … Comments

  • Fixed-Length Vector Types in Haskell (an Update for 2017)

    This post is a follow-up to my fixed-length vectors in haskell in 2015 post! When I was writing the post originally, I was new to the whole type-level game in Haskell; I didn’t know what I was talking about, and that post was a way for me to push myself to learn more. Immediately after it was posted, of course, people taught me where I went wrong in the idioms I explained, and better and more idiomatic ways to do things. And that’s great! Learning is awesome!

    Unfortunately, however, to my horror, I began noticing people referring to the post in a canonical/authoritative way…so the post became an immediate source of guilt to me. I tried correcting things with my practical dependent types in haskell series the next year. But I still saw my 2015 post being used as a reference even after that post, so I figured that writing a direct replacement/follow-up as the only way I would ever fix this!

    So here we are in 2017. GHC 8.2 is here, and base is in version 4.10. What’s the “right” way to do fixed-length vectors in Haskell?

    This post doesn’t attempt to present anything groundbreaking or new, but is meant to be a sort of reference/introduction to fixed-length vectors in Haskell, as of GHC 8.2 and the 2017 Haskell ecosystem.

    We’ll be looking at two methods here: The first one we will be looking at is a performant fixed-length vector that you will probably be using for any code that requires a fixed-length container — especially for tight numeric code and situations where performance matters. We’ll see how to implement them using the universal native KnownNat mechanisms, and also how we can implement them using singletons to help us make things a bit smoother and more well-integrated. For most people, this is all they actually need. (I claim the canonical haskell ecosystem source to be the vector-sized library)

    The second method is a structural fixed-length inductive vector. It’s…actually more like a fixed-length (lazily linked) list than a vector. The length of the list is enforced by the very structure of the data type. This type is more useful as a streaming data type, and also in situations where you want take advantage of the structural characteristics of lengths in the context of a dependently typed program. (I claim the canonical haskell ecosystem source to be the type-combinators library)

    Read more … Comments

  • Verify your Typeclass Instances in Haskell Today!

    One of the most common gripes people have when learning Haskell is the fact that typeclass “laws” are only laws by convention, and aren’t enforced by the language and compiler. When asked why, the typical response is “Haskell can’t do that”, followed by a well-intentioned redirection to quickcheck or some other fuzzing library.

    But, to any experienced Haskeller, “Haskell’s type system can’t express X” is always interpreted as a (personal) challenge.

    GHC Haskell’s type system has been advanced enough to provide verified typeclasses for a long time, since the introduction of data kinds and associated types. And with the singletons library, it’s now as easy as ever.

    (The code for this post is available here if you want to follow along!)

    Read more … Comments

  • Introducing the Hamilton library

    My name is William Rowan Hamilton

    Hamilton: README / hackage / github

    The hamilton library is on hackage! It was mostly a proof-of-concept toy experiment to simulate motion on bezier curves, but it became usable enough and accurate enough (to my surprise, admittedly) that I finished up some final touches to make it complete and put it on hackage as a general-purpose physics simulator.

    The library is, in short, a way to simulate a physical system by stating nothing more than an arbitrary parameterization of a system (a “generalized coordinate”) and a potential energy function.

    I was going to write a Haskell post on the implementation, which was what interested me at first. I wanted to go over –

    1. Using automatic differentiation to automatically compute momentum and the hamilton equations, which are solutions of differential equations.

    2. Using type-indexed vectors and dependent types in a seamless way to encode the dimensionality of the generalized coordinate systems and to encode invariants the types of functions.

    Read more … Comments