Fall-from-Grace: A ready-to-fork functional programming language

I’m publishing a repository containing a programming language implementation named Fall-from-Grace (or “Grace” for short). The goal of this language is to improve the quality of domain-specific languages by providing a useful starting point for implementers to fork and build upon.

You can visit the project repository if you want to cut to the chase. The README already provides most of the information that you will need to begin using the language. This announcement post focuses more upon the history and motivation behind this project. Specifically, I imagine some people will want to understand how this work relates to my work on Dhall.

TL;DR: I created a functional language that is a superset of JSON, sort of like Jsonnet but with types and bidirectional type inference.

The motivation

The original motivation for this project was very different than the goal I finally settled upon. My original goal was to build a type checker with type inference for Nix, since this is something that a lot of people wanted (myself included). However, I bit off more than I could chew because Nix permits all sorts of stuff that is difficult to type-check (like computed record fields or the callPackages idiom in Nixpkgs).

I lost steam on my Nix type-checker (for now) but then I realized that I had still built a fairly sophisticated interpreter implementation along the way that other people might find useful. In particular, this was my first new interpreter project in years since I created Dhall, and I had learned quite a few lessons from Dhall about interpreter best practices.

“So”, I thought, “why not publish what I had created so far?”

Well, I can think of one very good reason why not: I want to continue to support and improve upon Dhall because people are using Dhall in production and I have neither the time nor the inclination to build yet another ecosystem around a new programming language. But somebody else might!

So I took the project in a totally different direction: publish an instructive implementation of a programming language that others could fork and build upon.

Unlike Dhall, this new language would not be encumbered by the need to support a language standard or multiple independent implementations, so I could go nuts with adding features that I omitted from Dhall. Also, this language would not be published in any way so that I could keep the implementation clear, opinionated, and maintainable. In other words, this language would be like an “executable tutorial”.

The starting point

I designed the initial feature set of this new language based on feedback I had received from Dhall’s skeptics. The rough language these people had in mind went something like this:

• The language had to have bidirectional type inference

  The most common criticism I received about Dhall was about Dhall’s limited type inference.

• The language had to have JSON-compatible syntax

  One of the things that had prevented people from using Dhall was that the migration story was not as smooth as, say, CUE (which is a superset of YAML) or Jsonnet (which is a superset of JSON), because Dhall was not a superset of any existing file format.

  Also, many people indicated that JSON syntax would be easier for beginners to pick up, since they would likely be comfortable with JSON if they had prior experience working with JavaScript or Python.

• The language had to have JSON-compatible types

  JSON permits all sorts of silliness (like [ 1, [] ]), and people wanted a type system that can cope with that stuff, while still getting most of the benefits of working with types. Basically, they wanted something sort of like TypeScript’s type system.

• They don’t want to run arbitrary code

  TypeScript already checks off most of the above points, but these people were looking for alternatives because they didn’t want to permit users to run arbitrary JavaScript. In other words, they don’t want a language that is “Pac-Man complete” and instead want something more limited as a clean slate for building their own domain-specific languages.

What I actually built

I created the Fall-from-Grace language, which is my best attempt to approximate the Dhall alternative that most people were looking for.

Fall-from-Grace has:

• JSON-compatible syntax

• Bidirectional type-inference and type-checking

• A JSON-compatible type system

• Dhall-style filepath and URL imports

• Fast interpretation

• Open records and open unions

  a.k.a. row polymorphism and polymorphic variants

• Universal quantification and existential quantification

  a.k.a. “generics” and “typed holes”

One way to think of Grace is like “Dhall but with better type inference and JSON syntax”. For example, here is the Grace equivalent of the tutorial example from dhall-lang.org:

# ./users.ffg
let makeUser = \user ->
      let home       = "/home/" + user
      let privateKey = home + "/.ssh/id_ed25519"
      let publicKey  = privateKey + ".pub"

      in  { home: home, privateKey: privateKey, publicKey: publicKey }

in  [ makeUser "bill"
    , makeUser "jane"
    ]

… which produces this result:

$ grace interpret ./users.ffg

[ { "home": "/home/bill"
  , "privateKey": "/home/bill/.ssh/id_ed25519"
  , "publicKey": "/home/bill/.ssh/id_ed25519.pub"
  }
, { "home": "/home/jane"
  , "privateKey": "/home/jane/.ssh/id_ed25519"
  , "publicKey": "/home/jane/.ssh/id_ed25519.pub"
  }
]

Just like Dhall, Grace supports let expressions and anonymous functions for simplifying repetitive expressions. However, there are two differences here compared to Dhall:

• Grace uses JSON-like syntax for records (i.e. : instead of = to separate key-value pairs)

  Because Grace is a superset of JSON you don’t need a separate grace-to-json tool like Dhall. The result of interpreting Grace code is already valid JSON.

• Grace has better type inference and doesn’t require annotating the type of the user function argument

  The interpreter can work backwards to infer that the user function argument must have type Text based on how user is used.

Another way to think of Grace is as “Jsonnet + types + type inference”. Grace and Jsonnet are both programmable configuration languages and they’re both supersets of JSON, but Grace has a type system whereas Jsonnet does not.

The following example Grace code illustrates this by fetching all post titles from the Haskell subreddit:

# ./reddit-haskell.ffg
let input
      = https://www.reddit.com/r/haskell.json
      : { data: { children: List { data: { title: Text, ? }, ? }, ? }, ? }

in  List/map (\child -> child.data.title) input.data.children

… which at the time of this writing produces the following result:

$ grace interpret ./reddit-haskell.ffg

[ "Monthly Hask Anything (September 2021)"
, "Big problems at the timezone database"
, "How can Haskell programmers tolerate Space Leaks?"
, "async graph traversal in haskell"
, "[ANN] Call For Volunteers: Join The New \"Our Foundation Task Force\""
, "Math lesson to be learned here?"
, "In search a functional job"
, "Integer coordinate from String"
, "New to Haskell"
, "Variable not in scope error"
, "HF Technical Track Elections - Announcements"
, "Learning Haskell by building a static blog generator"
, "Haskell Foundation Board meeting minutes 2021-09-23"
, "Haskell extension 1.7.0 VS Code crashing"
, "[question] Nix/Obelisk with cabal packages intended for hackage"
, "George Wilson - Cultivating an Engineering Dialect (YOW! Lambda Jam 2021)"
, "A new programming game, Swarm by Brent Yorgey"
, "Scheme in 48 hours, First chapter issue"
, "Recursively delete JSON keys"
, "Issue 282 :: Haskell Weekly newsletter"
, "Haskell"
, "Yaml parsing with preserved line numbers"
, "I would like some input on my code if anybody have time. I recently discovered that i can use variables in Haskell (thought one could not use them for some reason). Would just like some input on how i have done it."
, "Diehl's comments on Haskell numbers confuse..."
, "Please explain this syntax"
, "Can Haskell automatically fuse folds?"
]

Here we can see:

• Dhall-style URL imports

  We can import JSON (or any Grace code) from a URL just by pasting the URL into our code

• Any JSON expression (like haskell.json) is also a valid Grace expression that we can transform

• We can give a partial type signature with holes (i.e. ?) specifying which parts we care about and which parts to ignore

Grace’s type system is even more sophisticated than that example lets on. For example, if you ask grace for the type of this anonymous function from the example:

\child -> child.data.title

… then the interpreter will infer the most general type possible without any assistance from the programmer:

forall (a : Type) .
forall (b : Fields) .
forall (c : Fields) .
  { data: { title: a, b }, c } -> a

This is an example of row-polymorphism (what Grace calls “open records”).

Grace also supports polymorphic variants (what Grace calls “open unions”), so you can wrap values of different types in constructors without having to declare any union type in advance:

[ GitHub
    { repository: "https://github.com/Gabriel439/Haskell-Turtle-Library.git"
    , revision: "ae5edf227b515b34c1cb6c89d9c58ea0eece12d5"
    }
, Local { path: "~/proj/optparse-applicative" }
, Local { path: "~/proj/discrimination" }
, Hackage { package: "lens", version: "4.15.4" }
, GitHub
    { repository: "https://github.com/haskell/text.git"
    , revision: "ccbfabedea1cf5b38ff19f37549feaf01225e537"
    }
, Local { path: "~/proj/servant-swagger" }
, Hackage { package: "aeson", version: "1.2.3.0" }
]

… and the interpreter automatically infers the most general type for that, too:

forall (a : Alternatives) .
  List
    < GitHub: { repository: Text, revision: Text }
    | Local: { path: Text }
    | Hackage: { package: Text, version: Text }
    | a
    >

Open records + opens unions + type inference mean that the language does not require any data declarations to process input. The interpreter infers the shape of the data from how the data is used.

Conclusion

If you want to learn more about Grace then you should check out the README, which goes into more detail about the language features, and also includes a brief tutorial.

I also want to conclude by briefly mentioning some other secondary motivations for this project:

• I want to cement Haskell’s status as the language of choice for implementing interpreters

  I gave a longer talk on this subject where I argue that Haskell can go mainstream by cornering the “market” for interpreted languages:

  • How to market Haskell to a mainstream programmer

• I hope to promote certain Haskell best practices for implementing interpreters

  Grace provides a model project for implementing an interpreted language in Haskell, including project organization, choice of dependencies, and choice of algorithms. Even if people choose to not fork Grace I hope that this project will provide some useful opinionated decisions to help get them going.

• I mentor several people learning programming language theory and I wanted instructive example code to reference when teaching them

  One of the hardest parts about teaching programming language theory is that it’s hard to explain how to combine language features from more than one paper. Grace provides the complete picture by showing how to mix together multiple advanced features.

• I wanted to prototype a few language features for Dhall’s language standard

  For example, I wanted to see how realistic it would be to standardize bidirectional type-checking for Dhall. I may write a follow-up post on what I learned regarding that.

• I also wanted to prototype a few implementation techniques for the Haskell implementation of Dhall

  The Haskell implementation of Dhall is complicated enough that it’s hard to test drive some implementation improvements I had in mind, but Grace was small enough that I could learn and iterate on some ideas more quickly.

I don’t plan on building an ecosystem around Grace, although anybody who is interested in doing so can freely fork the language. Now that Grace is complete I plan on using what I learned from Grace to continue improving Dhall.

I also don’t plan on publishing Grace as a package to Hackage nor do I plan to provide an API for customizing the language behavior (other than forking the language). I view the project as an educational resource and not a package that people should depend on directly, because I don’t commit to supporting this project in production.

I do believe Grace can be forked to create a “Dhall 2.0”, but if that happens such an effort will need to be led by somebody else other than me. The main reason why is that I’d rather preserve Grace as a teaching tool and I don’t have the time to productionize Grace (productionizing Dhall was already a big lift for me).

However, I still might fork Grace in the future for other reasons (including a second attempt at implementing a type-checker for Nix).