JSON as Functional Progamming Syntax

A parser, interpretter, and compiler for a functional programming language with the same grammar as JSON.

This project started as something of a joke: Could I use JavaScript Object Notation as a way of describing not just standard arrays and objects, but also functions and other data types? Bascially, could I turn JSON into a programming language which compiles to JavaScript?

The answer, it turns out, is yes!

Example

In video form (+repl)

In text form

Here's a simple example: Let's define a simple fibbonacci function:

[
	"slow_fibb",
	{
		"0": 0,
		"1": 1,
		"n": ["+", ["slow_fibb", ["+", "n", -2]], ["slow_fibb", ["+", "n", -1]]]
	}
]

Our fibbonacci function, called "slow_fibb" has two base cases: If 1 is passed, it returns 1, and if 2 is passed, it returns 2. Otherwise, it recursively calls slow_fibb on n-1 and n-2, then adds the results together.

If you need to take some time to understand what's going on here, feel free to pause and work through it. Further down in this README, you can find a walkthrough of what various different language features do, and what the syntax looks like. If you're familiar with ML-style languages and Lisps, parts might feel familiar to you. If you're more used to imperative languages like C or Python, one thing to keep in mind is that all operations are prefix. This means that to add together 1 and 2, we write ["+", 1, 2] rather than [1, "+", 2].

Got it (mostly) figured out? Sick! Now let's try running our code through the compiler (with pretty-printing turned on for our sake) and see what we get:

$ python3 compile.py slow_fibb.json | npx uglify-js -c evaluate -m --beautify
function slow_fibb(b) {
    return 0 == b ? 0 : 1 == b ? 1 : slow_fibb(b - 2) + slow_fibb(b - 1);
}

Just what we ordered! But let's try it out to make sure it works.

> function slow_fibb(b) {
...     return 0 == b ? 0 : 1 == b ? 1 : slow_fibb(b - 2) + slow_fibb(b - 1);
... }
undefined
> slow_fibb(10)
55

Perfect!

Ready for something a little more complex? How about an O(n) fibbonacci function:

[
	"fast_fibb",
	[
		"fibb_helper",
		{
			"a": {"b": {
				"0": "a",
				"1": "b",
				"S S n": ["fibb_helper", ["+", "a", "b"], ["+", ["+", "a", "b"], "b"], "n"]
			}}
		},
		["fibb_helper", 0, 1]
	]
]

Wondering about those S patterns? Those denote a predecessor. So S S n only matches integers greater than 1, and binds n to 2 less than the input.

Alright, let's try compiling that!

$ python compile.py fast_fibb.json | npx uglify-js -c evaluate -m --beautify
const fast_fibb = function n(i) {
    return f => b => 0 == b ? i : 1 == b ? f : n(i + f)(i + f + f)(b - 2);
}(0)(1);

Nice!

Want to mess around with things yourself? Both of these fibbonacci functions can be found in the fibb.json file in this repository, and all you need to run it is a recent-ish version of python! Check out the next section for more details.

Setup

This project has no dependencies, just Python3! That means all you have to do to run is install Python3 and clone the repository. Once you have the code, you can either run:

python3 main.py # Open a REPL with only the built-ins

OR

python3 main.py example.json # Evaluate some code and either print the results or open a REPL

OR

python3 compile.py fibb.json # Compile some code to JavaScript
python3 compile.py fibb.json | npx uglify-js -c evaluate -m # Compile some code to JavaScript and tidy it up a bit

Syntax Rundown

Functions / Lambdas

A function is defined using a standard JavaScript object with string keys. The simplest function you can write is the identity function:

{"x": "x"}

(equivalent JavaScript code:)

x => x

This function takes in one argument (called "x") and returns it unmodified. The "x" on the left defines the argument, and the "x" on the right is the return value. You'll notice we're also introducing the syntax for variables: Strings! While there are some times that strings don't function as variables (such as that first "x" on the left, which is an argument), most of the strings you'll see are variables. They refer to some previous value, and resolve to that. Here, the "x" on the right refers to the "x" on the left.

If you type this code into the repl, however, you'll see this output:

{"x": "x"}

Unchanged! In order to do something with this function, we'll need...

Function Application

Function application! (Meaning calling functions or passing them arguments). For this, we borrow JSON's array syntax. The first element of the array is the function being applied, and all things to the left are the arguments, which are passed in order from left to right.

Let's try applying our identity function to a number (new syntax! numbers are just JSON numbers!):

[{"x": "x"}, 4]

(equivalent JavaScript code:)

(x => x)(4)

Let's try putting this new expression into the REPL!

4

Now we get just 4! Our code worked! The four was returned unmodified.

This is a little bit boring though. We can start to make things more interesting by applying some of the built-in functions. One simple example is the "S" (or successor) function. Let's write a function which applies the S function twice:

{"x": ["S", ["S", "x"]]}

and now apply it:

[{"x": ["S", ["S", "x"]]}, 4]

(output:)

6

Nice!

Pattern Matching

Much like in other functional languages, all functions can perform case matching. By adding additional key/value pairs to the function (object), we can pattern match on different terms. All keys still need to be strings, but the contents of the string represent the pattern sub-language. For example, this function subtracts one from a number, unless that number is zero:

{"0": 0, "S x": "x"}

Note: The documentation for this section and the following sections are currently incomplete. While I aim to finish eventually, for now this is all there is. I encourage you to play around with the examples in example.json as well as on your own. If you're comfortable with Python, you can also poke around in the source code to find out how things work!

Let Bindings

["x", 3, "y", ["+", "x", 5], ["+", "x", "y"]]

Equivalent JavaScript:

{
	const x = 3;
	const y = x + 5;
	return x + y
}

Bind values in REPL

aka a let binding without an "in" clause

["addTwo", {"x": ["S", ["S", "x"]]}]

Multi-argument functions

{"x": {"y": ["+", "x", "y"]}}

Equivalent JavaScript:

x => y => x + y

(note: produces curried JS)

More language features remain undocumented :(