February 28, 2014
Monads tend to come up a lot in functional programming. All you need to know about functional programming for now is that it’s a paradigm in which mutable data is generally discouraged, or even forbidden. Computation generally happens by composing pure functions together. A pure function is one that does nothing but return the result of a computation. It doesn’t print anything, store anything, ask for user input, etc. It just manipulates the data you pass it and returns more data.
You may be more familiar with object-oriented programming. Let me translate monads into OOP-speak.
Monadis an interface, or an abstract class if you like. It has a constructor and a
class Monad: def __init__(self, x): raise NotImplementedError def bind(self, f): raise NotImplementedError
xcan be anything.
fis a function that takes something of the same type as
x(presumably from the monad) and returns a new monad. Lastly,
bindalso returns a new monad (often from the result of
f). Literally that’s it. Maybe you don’t know what it’s used for, but at least now you’ve seen the interface.
Typically, a monad acts as some sort of container, and
bindapplies a function to what it contains. Let’s make a monad that stores a single element:
class SimpleMonad(Monad): def __init__(self, x): self.x = x def bind(self, f): return f(self.x)
To make this a little more concrete, this is how you use it:
def double(x): return SimpleMonad(x * 2) def add1(x): return SimpleMonad(x + 1) foo = SimpleMonad(5).bind(double).bind(add1)
Okay, so you can chain functions together with
bind. But why would we do that? Equivalently, we could have just written
add1(double(5)), which is much shorter.
The main idea is that monads don’t have to just call the functions you pass to
bind. They can change the rules. For example, here is a monad that allows you to chain operations without worrying about null pointer errors.
class MaybeMonad(Monad): def __init__(self, x): self.x = x def bind(self, f): if self.x is None: return self else: return f(self.x)
If any intermediate computation in a sequence of operations results in
None, the entire expression becomes
Noneand no further operations are performed (much like how
NaNworks in floating-point arithmetic, if you’re familiar with that). If you spend more time with monads, you’ll find that you can also use them to implement exception handling, mutable state, concurrency, and a bunch of other things.
Remember: functional programming is all about writing programs by composing functions together. The power of monads is that they allow you to change the rules for how functions are composed.
When I was learning about monads, the main things I was confused about were:
- It seems like using monads requires you to write a lot of code, e.g.,
add1(double(5)). Do people really go through all this trouble?
- How do I get the value out of the monad? Can I access it like
- I hear that Haskell doesn’t let you write “impure” functions that have side effects, but I know for a fact that Haskell programs can print to the screen and write to files. What’s the deal? Do monads somehow resolve this?
Well, I know the answers now, so let me share the love:
- Haskell has a special syntax for monads and Python doesn’t—so that’s why they don’t look very nice in Python. It’s actually quite brilliant. Check it out if you have time. Using it feels very natural and it looks a lot like imperative code.
- Some monads provide a “getter” function that allows you to get the value back out. But a monad is not required to have one. For some monads, it doesn’t make sense to take a value out of it. A monad is not required to act like a container. See #3.
- Yep—all functions in Haskell are pure. Haskell has a neat trick for doing I/O. You can think of a Haskell program as a pure computation that returns a tree-like data structure, and this tree represents another program that does impure things.Now, building this tree can be done in a purely functional way—as is required in Haskell. But when you “run” a Haskell program, two things happen: 1) your pure Haskell computation is executed, resulting in this tree-like data structure, 2) the tree-program from step 1 (which can print to the screen and write to files) is also executed.It just so happens that a certain monad, especially when combined with Haskell’s special monad syntax, makes it easy to build this tree. This monad is called
IOin Haskell. The bind operation does not call the function you pass it, as it did in our monad examples above. Rather, it just stores it in the tree. The runtime will call it when interpreting the tree. That’s the high-level idea. In this post, I implement this idea in Python, which will probably make it a little more clear for you.Lastly, the
IOmonad does not have a “getter” function. For example, if you have an
IOaction that asks a user for a string of input, you cannot extract the string from the monad. This is because the
IOaction doesn’t actually have a string to give you—it only represents a computation that returns a string. When you
fto this monad, you’re building a new
IOaction that asks the user for a string and then calls
To summarize, monads let you change what it means to compose functions together. You might want to keep track of some extra information, store the functions in a tree, call them in a different order, call them multiple times, skip some functions entirely (based on the value being passed to them), etc.
You don’t have to use them, but now you don’t have to fear them either!
EDIT: Fixed a typo and added the
MaybeMonadexample at /u/wargotad’s suggestion.
February 27, 2014
I’m working on an a cappella cover of Say Something, by A Great Big World and Christina Aguilera. Here’s a very early preview:
February 1, 2014
Over the last few days I built Kitestring, a mobile-friendly web application that checks up on you when you go on unsafe trips.
You tell the application that you’re going on a trip, and then it checks up on you (via SMS) to make sure you haven’t been mugged or assaulted. You reply to the SMS messages (or check in on the website) to confirm your well-being. If you fall off the radar, the application alerts a list of emergency contacts that you set up ahead of time.
January 7, 2014
After moving into a new dorm at MIT, I just had to try out my new kitchen. Today’s menu: Cajun jambalaya. Start with a pair of breasts.
Dice some kielbasa.
Sauté the meat. It looks like I put too much in! But I stirred it a lot; it was fine.
Chop some peppers and onions.
Don’t forget the garlic.
This much seems about right:
Some rice and chicken stock.
A few bay leaves.
Captain Worcestershire and his side kick, Sriracha!
A dash of these things for good luck:
Simmer like there’s no tomorrow!
November 12, 2013
My ideas often come on a grand scale, and many of the ambitious projects I want to tackle require a fundamental paradigm shift in some field/industry. I’ll list a few of them here. I didn’t invent most of them (even though I thought I did), and some of them are partially-solved (but none are in widespread use).
- In an earlier post I wrote about a future world where meetings are scheduled by a computer system that knows everyone’s time constraints. The system should be able to automatically shuffle around everyone’s schedules to make all kinds of crazy things possible. For example, suppose a musician gets sick right before a rehearsal. The system could reschedule the rehearsal for a later date, in a way that works for everyone in the band. If there is no time that works for the whole group, the system controls each member’s schedule and re-optimizes it to make a time. Or on a bigger scale: think about an entire university using this to schedule class times (dynamically). There’s a lot more to this idea, so check out that blog post for details.
- Unit tests are often used not to assert that a function is correct, but rather to detect when its behavior has been changed (possibly by a seemingly-unrelated change somewhere else in the codebase). It seems like these kinds of tests could be automatically generated. I could imagine a build system that automatically generates random inputs to every function and then records their outputs. Then whenever you build/deploy the application, the system runs the new code against these inputs and checks that the outputs match what was previously recorded. This doesn’t guarantee correctness, but it hopefully tells you when you’ve broken something.
- A type system that allows you to prove that function calls will not allocate memory and forget to release it. I’ve worked out a system where this is possible in another blog post. Similarly, a type system that lets you prove termination or get bounds on the asymptotic resource (CPU/memory) usage of a procedure. Or a type system that models latency in network requests (see my notes above about auto-generating AJAX calls). I have a lot of ideas for type systems. Some type system ideas that I thought I came up with (but didn’t): types that distinguish between unsafe vs. escaped strings (e.g. to prevent injection attacks), types that let you create ad-hoc subsets of types (e.g. even integers, sorted lists, etc.), and using monads for resource management.
- Software for life-critical systems, such as airplane autopilots, medical devices, etc. are often formally-verified—meaning that a computer program checks that the software matches the specification exactly (so it should be bug-free, so long as the specification is correct). Yet tons of life-critical software runs on unverified kernels, and so are fundamentally unsafe. Understandably, it would be near-impossible to verify a large kernel like Linux, but why can’t we have completely verified microkernels for use in these safety-critical applications? I know, easier said than done.
- Of course, it would be nice if every piece of software running on a machine was formally-verified. From the kernel, to the compiler, to the web browser. Pretty unrealistic, I know, but think for a second about what this means. Yes, your computer system would be bug-free—but there’s something else I want to draw attention to. If all software was formally-verified, it could all run in kernel mode. Similarly, all programs could share the same address space (no need for virtual memory). We could even eliminate the need for a task scheduler—all programs could implement cooperative multitasking, and we could be sure that no program would hang and bring the system down. Together, these facts would allow software to be vastly more performant than today’s computer systems. Modern hardware is very underutilized.
- Self-balancing electric unicycles. Unicycles very space efficient, but exhausting to ride (if you can even ride them at all). An electric one could be a very energy-efficient, compact mode of transportation, and the self-balancing system means that even non-unicyclers could ride it. Before you say it’s impossible, I built one and it worked really well before it was stolen from me. I could ride over 5 miles on a single charge, at about 15 mph. For longer trips I could easily take it on the subway with me. With only one wheel, they can be made cheaper than Segways.
- I have to remember a zillion different passwords for all my online accounts. If I could compute cryptographic hashes in my head, I could eliminate this need—I would simply have to remember a single master password, and my password for each website would be the hash of the master password concatenated with the name of the website. But no human is capable of this—but why should they be? That’s what computers are for. All web browsers should automatically implement this behavior for every password field—they should compute the hash of the password you enter concatenated with the website domain and send that to the server. The password you type in should NEVER make it to the server. Currently no browsers do this—why not? There are browser extensions that do this, but the fact that they are extensions means that most people aren’t benefitting from the idea.
- Algorithms theoreticians probably don’t spend a lot of time thinking about UTF-8 encodings for strings. We have a large theory of string algorithms, but they all assume indexing is constant-time. For a naive UTF-8 implementation of strings, indexing is linear-time. I bet we could come up with a clever string data structure for variable-width encodings. It should have worst-case logarithmic-time indexing (like a balanced tree), linear-time traversal, and its space usage should be better than just using fixed-width characters (that’s the whole point of variable-width encodings, after all). Or can we do even better, with average-case constant-time random access?
- Web applications depend on the browser to faithfully execute front-end code. Part of the reason that business logic typically resides on the server is because of security—front-end code can easily be modified by the user and shouldn’t be trusted. What if there was a way for the browser to keep track of the computation, and build a cryptographic proof that it was executed faithfully? Then the browser sends this “certificate of computation” along with the computed result back to the server, which checks that they match up (without actually re-executing the computation). Is this even possible? I recently discovered that I didn’t invent this idea—it’s called verifiable computing.