Introducing Mappy

During my nice little break last week I figured, why not? I'll make my toy programing language more real! The result is a functional programming language that is similar to Lisp, except maps (aka dictionaries, aka HashMaps, aka Hashes) are the core primitive, rather than lists.

You're probably thinking to yourself, "what's the point in yet another Lisp-like language?" Well, that's a great question! Mappy's really a breakable toy for my amusement (i.e. in its current state, Mappy's definitely not ready for production). That being said, here are some interesting design choices in the language

• I decided to go with maps rather than lists, because maps are more closely related to functions
• Keeping expressions simple and singular (a la Lisp) makes parsing and grammar rules trivial
• (Bias alert) Haskell is an amazing language in which to implement compilers
• I didn't want to implement if as a core primitive, so I had to choose between non-strictness and auto-closure function arguments (the latter won for simplicity reasons)
• Parsec and QuickCheck can really save you when you're trying to keep complex rules consistent (e.g. parsing)
• Github issues and milestones are an excellent way to break a problem into small chunks and really focus
• Implementing IO as a map has had constraining effects (no pun intended) that are similar to the IO monad

If you're interested in contributing, have a peek at the issues or feel free to play with it, see the README, and/or file some issues!

Functional Programming Aha! Moments

In the past couple of years, I've dedicated a fair amount of time to closet-functional-programming. Although I haven't gotten an opportunity to use a more purist functional programming language (e.g. not FrameWorkOfTheDay.JS) in my day-to-day day, industry work, I believe some of the values of functional programming have bled into my daily practice, for the better.

Industry aside, I want to share some of the "Aha! moments" I've had while learning about functional programming. These are moments where something just clicked for me; some part of me almost can't help but share them.

Lets Can Be Described by Anonymous Functions

Although "functional programming" is one of those things were if you ask five people for a definition you are likely to get six different definitions, one general consensus seems to hold: assignment should be reduced, minimally scoped or eliminated entirely in functional programming.

The let macro/expression/sugar is basically a means of reducing assignments into minimally scoped, (generally) non-mutative expressions with a set of bindings. Here's a contrived example of what this might look like in Clojure

Here we're saying, let's bind `x` to `35` then `y` to a value calculated from `x`, then we'll use `y` to calculate some result. This entire expression is just that, it's an expression. This `let` is evaluated as a whole, and the result is simply `42`.

So, here comes the first "Aha!" This same kind of scoped assignment can be done through applying anonymous functions! Here's what that looks like for the above example

Basically the pattern here is just, for each bound symbol (in this case `x` and `y`) nest and call an anonymous function, passing the bound value down (`35` and `(- x 14)`)! I found this discovery exceptionally cool because it further emphasized the power of these functional languages: something as simple as anonymous functions can be combined to form powerful abstractions. 

Monadic Bind Is Like Method Chaining

Monads, in general, have provided many an "Aha" for me. They're definitely one of those constructs where, once you get passed the initial "this is slightly out of my comfort zone" feeling, you are ready to embrace an overwhelming amount of power.`bind` (looks like `>>=`) is one of the crucial operations implementable by a monad, it has the following type signature

Ignoring currying and some other subtleties, if I'm thinking in an "object oriented mindset" I might reason about this as follows:

• `bind` is a function that take 2 arguments
• a generic wrapper around some type `a`
• a function which takes some `a` and returns some generic wrapper around type `b` (where `b` may be the same type as `a`)
• `bind` returns some generic wrapper around type `b`

To me, this sounds exactly like a single call that enables method chaining! Think a la calling `bind` to transform from monad to monad to monad... In my mind, `bind` is an enabling feature, that allows Haskell code to be elegant, expressive and powerful without lacking type safety (see `do` notation).

To visualize how this is kind of like method chaining, observe the following Ruby code

We can imagine these calls (with the exception of `count`) being like a type-not-so-safe version of Haskell's `bind` applied a couple of times (2 to be exact). Here are what the steps might look like

1. `m a` is a range of `Fixnum` (e.g. `Range Fixnum`)
2. `map` applies a block that takes the `Range Fixnum` and returns an `Array Fixnum`
3. `select`, with its block, takes an `Array Fixnum` and returns an `Array Fixnum`
4. Finally, `count` is simply applied to the `Array Fixnum`

Message Passing (OOP Style) Can Be Achieved via Closures

Disclaimer/Plug: this last "Aha" is shamelessly ripped off from The Structure and Interpretation of Computer Programs (SICP). I am over half way through this book, it is wonderful, please consider showing the authors your support by buying it.

The authors of SICP take the reader through a fantastic journey in which the powers of LISP and functional programming are clearly displayed through examples in the Scheme dialect. One piece of this journey that recently blew my mind was when the authors used closures to define a mutable bank account that responds to different messages. Here's the code (again shamelessly ripped)

What you're seeing here is basically a constructor that builds objects, given a beginning balance, that respond to the `'withdraw` and `'deposit` messages.

Frankly, I don't really know what I can say about this that the authors haven't already said (1) more articulately, (2) more clearly and (3) in a more inspirational manner.

In conclusion, these are just a few of the awesome concepts I've picked up in my pursuit of functional programming. If you have any thoughts on these, or my description of them, don't hesitate to comment.

LISP Core in Less Than 100 Lines of Haskell

A couple of months ago, I built a LISP core engine in about 100 lines of Haskell code (of course, just for the fun of it). I thoroughly enjoyed the challenge, and with the help of techniques from the awesome Programming Languages MOOC I was taking, I felt ready to take it on. In conclusion, it was truly a fun project and I thought I'd share some things I learned along the way.

LISP's Core Primitives are Easily Implemented Recursively

In the simplest terms, the LISP core engine I built is simply a function that operates, with a specific environment (variable bindings) in mind, on the LISP syntax tree. Because of this I was able to implement primitives like label (aka define) simply with pattern matching and the cons (: in Haskell) operator!

To show how simple these primitives were to define, here's eq? (checks equality)

aux env (AList (Atom "eq?":a:b:_)) =
  if aux env a == aux env b then aTruthyValue else theFalseyValue

Note that aux is the name of the helper function called by the executor.

Haskell Code Can Be Very Elegant

There aren't many languages in which code as elegant as this can be written:

executeText env = execute env.parseMany.tokenize

In my opinion, it doesn't get much more straight forward than this. The dots may throw C-style programmers, but to a Haskell programmer they're pure gold.

Additionally refactoring in Haskell is extremely powerful. Consider the evolution of my bind function (takes names and values and adds them to an environment). It started as this:

bind [] [] env = env
bind (name:names) (value:values) env = bind names values ((name, value):env)

then was transformed to this:

bind names values = (++) $ zip names values

and ended up as:

bind names = (++) . zip names

In Haskell, it seems, there is a function for everything. Honestly, there's probably even one out there that can replace my bind function, I just haven't found it yet!

The Macro System is Pretty Cool

At the moment, the macro system in this LISP is pretty tight. Macros are written in Haskell code (I would like to eventually add support in the language) and are provided with (1) and "eval" which encapsulates the current environment and can run code and (2) a list of the arguments passed to the macro.

All registered macros are simply added to a list, and are thus loosely coupled to the actual core engine (but tightly coupled to the AST since they are essentially generating new portions of it).

Here's an example of how I defined if, in terms of the cond primitive:

structuralMacros = [(
  "if", \_ (p:a:b:_) -> AList [Atom "cond", p, a, Atom "1", b]),
  ...]

Parting Words

If you're interested in the full code, it's on github. Also the project has a REPL whose build step is at the bottom of "README.md."