tl;dr: This post talks about various languages, though mostly Haskell. I started playing with Parsec and Stack, that led to writing my own language. Some lessons learned.
Intro
As a Haskell rookie I read and followed the free online book Write Yourself a Scheme in 48 Hours, which helped me understand a lot of features of Haskell. However when you have a book to follow I find that it’s hard to ask yourself some questions, and far too easy to just follow along1.
After having finished reading and following Write Yourself a Scheme, along with thinking that all this time I’ve been complacently using Cabal for my builds, I thought a cool project would be to make my own language. This would allow me to attempt Parsec on my own and also start getting used to the Stack build tool, which is the preferred way of working in professional Haskell environments2.
Bonlang
For the aforementioned purpose I decided to implement my own programming language, which would feature some of my favorite aspects found in other languages.
Choosing a name
It’s just a name, to be honest. Though the actual story is that when I was thinking about a name, I was also about to have dinner and my roommate said “bonap!”, which is short for bonappetit. So… ¯\_(ツ)_/¯
Choosing a style
In regards to the style, I decided to go with a mix of my favorite languages: Lisp(s), Scala, and of course Haskell.
Variadic functions… or lack thereof
In regards to Lisp, I first wanted to have variadic functions, that is, functions that have indefinite arity (number of arguments). For example, in Clojure (a Lisp for the JVM), and in most Lisp flavors you can do:
However I had to desist on that idea because it’s hard to have that play along with another feature I really like, which comes from Haskell, and it’s called automatic currying.
Automatic Currying? Is it delicious?3
Currying is delicious, but does not come from curry the spices, rather it comes from Haskell Curry, a great mathematician and logician. Though in those links you can find yourself great information and follow from there to your heart’s content, currying is quite simple in usage, and in my opinion tremendously powerful.
A simple demo of currying is below:
Seeing this behavior it’s perhaps easier to understand currying with its alternate name: partial function application. As you can see, addtwoIntsAnd10 is nothing more than addThreeInts with the first parameter applied and the other two are “pending”, in a matter of speaking.
Some languages provide a way to curry, but in my experience it’s rarely as straightforward as it is with Haskell, which is why I call it automatic. Bonlang behaves like Haskell in this regard (superficially, not internally).
You can however see how it’s hard to combine variadic functions with automatic currying; in other words: how do you manage automatic partial function application when you have an indefinite amount of arguments? That’s not to say there’s no solutions, but I decided to not implement variadic functions4.
In Haskell, in fact, all functions take a single parameter, and simply keep returning functions until an actual value is ready to be returned. That is, a value that doesn’t require any further arguments, which leads me to the next feature desired in languages I normally use.
Functions as first-class citizens
Another feature that I love to program with is using functions as first-class citizens. This makes for really elegant and a lot of times simpler-to-understand code.
Programming with functions as first-class citizens means that I can mention an identifier in my code referring to a function, and that carries no special syntax. For example, PHP does not treat functions as first class citizens because you have to point to them with a string or use a closure.
Treating functions as first-class citizens can even vary across different Lisp flavors, for example here’s a mapping over an array in Clojure:
And in Common Lisp:
So you can see that they’re different. My favorite approach however is to simply treat functions like any other identifier. After all, they’re the same as numbers, strings, …, in other words: they’re no different from any other “citizen”.
On that note: lambdas
So from the previous point we gather that we want to refer to functions by their identifiers. But giving a name to every function is sometimes annoying when we need functions in specific scopes and are ready to throw them away once we’re done with a specific procedure.
That’s the purpose of lambdas, unnamed functions that can be assigned to a local identifier, or simply used as a parameter of other higher order functions (i.e.: functions that take other functions as arguments); like map.
In Bonlang, of course, I decided to add support for lambdas. In fact, there’s no such thing as a function, but internally it binds closures to identifiers in a somewhat-generalised scope (more on that on later posts).
As a demo of a lambda, here’s one of my favorite code snippets. It calculates the factorial for any number n in linear time. It’s in Clojure and ripped directly from Structure And Interpretation of Computer Programs.
But of course, if you ask me, the best language for lambdas is, to date, Haskell:
If you can’t see it, it’s as easy as \param1 param2 -> ... where ... is an equation where you manipulate the function arguments to your liking.
Achieving that level of elegance is quite hard from a parser point of view, so in Bonlang it’s not so nice, I’m afraid.
Last but not least: Pattern Matching
Another tremendously powerful feature found in languages like Scala and Haskell, but not many Lisps, is Pattern Matching. Below is a quick (trivial) example of how that works:
Where the _ (underscore) symbol means “whatever” (otherwise known as a wildcard pattern). So the method isCarlos will only return true for a value that matches the “pattern” specified in the first binding.
There is one Lisp flavor that has pattern matching, though it’s not as complex as Haskell’s. It’s Shen5, and below is an example of how you’d reverse a list in Haskell and in Shen6, using pattern matching:
In Haskell:
In Shen:
More on Shen pattern matching here.
Some code examples
While that’s not the complete list of elements found in Bonlang, I believe I’m close to boring the hell out of you so it’s better to jump into some code samples.
Automatic currying, as mentioned, is quite straightforward:
Support for lambdas:
There’s a higher-order function: map. I’ll add more with time.
Combining currying with higher order functions, addFive is a partial application of adding (+), with the number 5.
Here’s that SICP factorial calculation:
And here’s a sample of a classic recursive Fibonacci, which has a terrible performance, but that’s kind of the point of this algorithm:
The language features pattern matching on a primitive level
Lastly, this is an example that I really like, and if you’re a SICP person you’ll recognize it. You can check the reference material here.
The purpose of the example is to show that data can take the form of procedures. Effectively, with support for lambdas we can create pairs.
This is one of my favorite examples and it is, as the book says, mind-boggling.
That’s it for now
If you’re familiar with the languages which I have been mentioning, you’ll see how where a lot of the inspiration comes from.
Mainly, I think, is the fact that function application is done with the $ symbol, and using Polish/prefix notation like in Lisp. I did it like this because it’s really easy to implement a parser that does this. While I do want infix operators in the future, that’s still a work in progress.
Check it out
Always read the README!
carlosdagos/bonlang
bonlang - Minimalist language created at ZuriHac 2016 in Zurich, CH
If you learned/liked anything from this post, make sure to star it so I get a little bit of an ego boost :D
As you can see from the description, this all started with ZuriHac! I was a mentor along with some cool and clever people. Great event!
Quick words on internals
I haven’t spoken much about the internals, as this is just an introduction post, but since it’s all a work in progress, in the future I’ll discuss some of the more fun parts of the language.
Conclusions
Definitely a lot, but the most mentionable are:
I had an idea of how Abstract Syntax Trees worked, but had never decided to get my hands dirty with them. This experience has definitely taught me a lot about that. Parsec goes a long way towards reading text into an AST.
There’s a huge difference between what you parse, that is what the program says, and what the program means. And that’s where runtime errors come in, which add another level of difficulty to the implementation themselves. In other words, I can say val sum = + $ x "a", which is syntactically correct, but it doesn’t make sense semantically.
I’m not even through realizing how hard error messages are, and in that context one of the biggest lessons from all of this is to not take for granted the excellent work done in most major programming languages.
Further work
- Better parser error messages.
- Better runtime error messages.
- More primitive functions.
- Importing other modules.
- Syntax support for Atom, is dead easy to get working.
Listening to
Saw them recently in a small pub in Karlsruhe!
Amendments
As is usual, any and all amendments to this post can be found here.
Footnotes
At least for me, anyway. Normally I will read things all the way through before I start to ask questions, or start to wonder about further material/functionality/etc.↩︎
On that note, I recommend you watch Simon Meier’s talk on commercial Haskell programming. I find that his tips, the code shared, and the style guide, are quite comprehensive and have helped a lot these past few months.↩︎
I had to make the pun, sorry.↩︎
Though in the code examples there’s still some legacy examples with some variadic functions, I’m removing those; and it only works for primitives.UPDATE: I’ve removed all variadic functions.↩︎I’ve barely mentioned Shen here and that’s because I’m still quite new to it, but it’s very functional and seemingly has a lot of great features.↩︎
Keep in mind these implementations are not optimal. In the Haskell example, we’re appending a single-element list to the reversed tail of the current list, in Haskell this is an
O(n)operation wherenis the length of the first argument and we’re doing this for all elements of the list!↩︎