BAM Weblog

Polymorphic Programming

Brian McKenna2018-01-07

I am convinced the way I program is broken. At work I write a lot of Scala, Haskell and Nix. Almost all of the functions I write are representing the problem I'm solving; not many functions have anything to do with the language itself. Sometimes I have to consider or concede to the language or runtime. I should be able to write programs by abstracting over language, precisely up to the considerations I have to make.

For example, I have written the identity function many times. I have written it in Nix, JavaScript, Java and many more:

a: a

function(a) { return a; }

A id(A a) { return a; }

\a -> a

That code increments my "implemented the identity function" counter by four.

Each line represents the same function but with slightly different runtime behaviour. When writing Nix or JavaScript, I have to remember syntax. When writing Java I have to remember rules around methods vs functions, where generics can be declared, etc. These don't really matter to the problem I'm solving, but I have to think about them.

I would like to write the identity function just once:

makeIdentity :: (HasVariables lang, HasParametricTypes lang) => lang
makeIdentity =
  lam # do
    t <- newTypeVar
    a <- newVar t
    var # a

We can argue about the DSL that I've imagined but my point is the type of the program. It is polymorphic - we can instantiate the program to anything which has variables and parametric types. I should be able to say:

makeIdentity :: Nix
makeIdentity :: Scala
makeIdentity :: Haskell
makeIdentity :: JavaScript
makeIdentity :: Python

But maybe there's more than one way to implement our functions. In strict languages like Scala I have to sometimes trampoline my code to stop it from hitting stack overflow errors (this has been especially annoying since I've moved to Site Reliability Engineer) and this is a mostly mechanical transformation. Could we represent trampolining as just an instantiation of our program?

makeMyStackSafeProgram :: Trampolined Scala

If I use a feature which isn't supported by the language, I should get a compilation error:

makeTraverse :: (HasHigherKindedTypes lang) => lang

-- makeTraverse :: Java
-- error: Could not deduce (HasHigherKindedTypes Java)

If I get the above error telling me that Java has no higher kinded types, I should then be able to work around Java by instantiating specific code:

makeTraverseFor javaOptional javaList

It might be useful to start more concretely; I have an example of instantiating a class to both Java and Python on Bitbucket.

There are some projects that I think are going in the right direction:

  • Compiling to categories by Conal Elliott takes functions and instantiates them to any closed cartesian category (his Lambda Jam video shows some awesome examples)
  • Dhall is a common language for configuration; compiles to JSON/YAML, Bash and text templates
  • Isomorf abstracts away syntax, uses a core language to give automatic refactoring and code reuse

I've talked to people at Queensland Functional Programming Lab and they are working towards this idea. They are starting with a library for working with Python code. They will eventually make another language library and then abstract the similarities. I think this is a pretty good approach.

It might seem inconvenient to program one language to program another, but I think enough optics and combinators, writing code using GHCi would be more convenient than using Emacs.

This is a massive project but I'm fairly confident this is how I'd like to program. I'm not confident on exactly what this would look like, what abstractions would appear between languages or which libraries would be necessary first. I'd love to hear what you think.

Please enable JavaScript to view the comments powered by Disqus.