Monday, June 22, 2015

SHA1 compile time checked literals: F# vs Nemerle vs D

I've always been interested in metaprogramming. Sooner or later, I'm starting to feel constrained within a language without it. F# is a really nice language, but I'm afraid I'd have got bored with it if it'd not have Type Providers, for example. Why metaprogramming is so important? Because it allows changing a language without cracking the compiler. It allows making things which seemed to be impossible to implement.

I'm dealing with cryptography hashes a lot at work, nothing rocket since, just MD5, SHA-1 and so on. And I write tons of tests where such hashes are used in form of string literals, like this:

The problem with this code is that the compiler cannot guarantee that the hex string in the last line represents a valid SHA-1. If it does not, the test will fail at runtime for a reason it's not intended to.

OK, now we can formulate our task: provide a language construct to enforce a string literal being a valid SHA-1 hexadecimal, at compile time. We will explore how much work it's required to implement such a simple feature in F#, Nemerle and D. It's also interesting how well the development workflow is for each of this languages - IDE integration, error reporting and testing cycle.


Using Type Providers is the only way to check (at compile time) that a string is a valid hex one and that it's length is exactly 40 characters (SHA-1 is a 20-bytes hash). Actually, I've written this type provider before. The interesting part looks like this:

It includes caching, and `HexParser` module is not shown, but those details are not important here. It's simple and it generates Value property which directly returns byte array, created in compile-time.

Error reporting:


Nemerle has full fledged macros, which strictly more powerful than F#'s Type Providers. Let's see if they allow solving the task in an elegant way:

Error reporting:


The code does not use any unusual stuff and does not manipulate AST. Just plane D code. Very elegant. Note that the template is defined in the same file as its usage. Contrast this with F# and Nemerle where you have to place your Type Provider / macros into a dedicated assembly.

Error reporting:

The error is located in the template itself, not at the instantiation point though.


I added 1000 usages of the TP, macro and template and measured compilation time.

  • F# - 5 seconds
  • Nemerle - 2 seconds
  • D - the compiler crashes with "Error: out of memory" after 1 minute work.


Павел Мартынов said...

My feelings:
* D: clearest solution, looks just usual code but runs in compile time, wow!
* Nemerle: more verbose, but still readable and understandable. ~30 lines of almost buisness logic code + some syntatic garbage (curly braces, etc)
* F#: a 25 lines of low-level magic and this is without buisness logic, only TP-related stuff (in contrast to Nemerle and D)

Macroses really interesting topic.

Павел Мартынов said...

It would be interesting to see how this can be done in Scala, which has macro system from the box in recent versions AFAIK.