A Functional Programming Language

A fun experiment on a lazy Sunday afternoon.

Featured on Hashnode

For some inexplicable reason, I suddenly became interested -- and for a short time, engrossed -- in creating my own programming language. And of course, like many things, my interest waned. However! Before that happened, I was able to settle on some general syntax and write a few functions that could conceivably work.

All of this was, of course, done for no other reason than fun and games. The coolest part of all was when I showed my kids (7 and 9) on a lazy Sunday afternoon. Within five minutes, they were able to understand it and even started writing simple functions on paper!

So here it is. I'm not sure what to call it, if it even deserves a name. I probably will never write the compiler for it either. None of that really matters. It was fun.


The "big idea" is that everything is expressed as a transformation that takes a single input and generates a single output. While I like to think of this thing in the middle as a "transformation", it's more-or-less analogous to a "function".

input -> transformation -> output

Everything builds off of this idea.

Given this, I added a few additional rules (constraints) for myself:

  1. No if/then/else

  2. No ternaries

  3. No "double logical operators" like ==, !=, <=, >=, &&, ||

  4. Few datatypes (I eventually found that I need tuples, lists, and single values)

  5. Data is immutable

  6. Functions can be chained together with successive arrows

Starting Simple

I want to imagine that I have a simple function that doubles a number. I would call it like this.

3 -> double -> result

In this example, I put 3 into the double function and direct its output 6 to a new variable called result. Additionally, I imagine that if I didn't redirect its output to a variable, then it would just be printed to console.

3 -> double

That ^ would just print 6 to the console.

So, it seems like variables are instantiated and initialized directly as the output of a function... or at least maybe I could say at the end of an arrow.

Naturally, it should follow that function names are defined in the same way. Here is how I would define the double function:

n -> n*2 -> double

Because n is not already defined in scope, the compiler knows that it should represent the function argument. Then, given that n, it performs a transformation n*2, and outputs the result to the new variable double. This is generally how functions are defined.

One other key aspect of the language is chaining. Now that I have a double function, I can call it successively.

3 -> double -> double -> result

This will store 12 in the new variable result.

Here are some additional simple function definitions:

n -> n/2 -> halve
n -> n+1 -> increment
n -> n-1 -> decrement

Using these, I can contrive this silly example:

3 -> double -> increment -> double -> halve -> decrement -> result

This is essentially the same as doing this: (((((3*2)+1)*2)/2)-1) and storing 6 into result.

Slightly More Complicated

Any good language needs a way to compare things and branch. This is where I introduce a new data type: the tuple. It's essentially the same idea as a tuple in Python.

I want to write a greater-than-or-equal-to function, but I don't want to use >=. I have = for equality and > for greater-than. Also, for some inexplicable reason, I don't want to have syntax for and or or.

Here's what I want to write:

(5, 3) -> gte -> x
(5, 5) -> gte -> y
(3, 5) -> gte -> z

When I write this, I want both x and y to contain 1 and z to contain 0. Given all of my constraints, here's how I have decided to write this function:

(a, b) -> (a > b) + (a = b) -> gte

The trick here is that booleans are simply 1 or 0, allowing you to do arithmetic with them. C works the same way. Given this, I'm sure you could imagine how the math works out (remember, = is not an assignment operator; it is a logical equality operator).

So, given this, I could also invent less-than-or-equal-to like this:

(a,b) -> (a<b)+(a=b) -> lte

note:*spaces don't matter*

OK cool! Now what about branching? Here's what I imagine:

(?, a, b) -> a*? + b*(1-?) -> branch

The argument is a tuple consisting of three variables: ?, a, and b. The ? is meant to be an evaluated condition. If ? is "true", then a is returned. Otherwise, b is returned. This works out well for numbers, but some special rules have to be made for tuples and other data types.

For those situations, I think I could just represent tuples and other data types using two values: its actual value and it a "boolean" where 0 represents emptiness and 1 represents "fullness". Then, when you perform arithmetic operations on it, it can switch between the two values under the right circumstances.

So, using what I've come up with so far, here is a contrived example:

((2,5)->lte, 3, 4) -> branch -> double -> result

This says, "if two is less-than-or-equal-to five (which it is), then send three to the double function and send the double function's output to result. In this case, I expect result to contain 6.

With this design, I can even make min and max functions:

(a, b) -> ((a, b)->lte, a, b) -> branch -> min
(a, b) -> ((a, b)->gte, a, b) -> branch -> max

That's not bad, but I kind of think the extra (a, b) is redundant. I feel like I should be able to implicitly pass the original input to functions directly... so maybe more like this:

(a, b) -> (lte, a, b) -> branch -> min
(a, b) -> (gte, a, b) -> branch -> max

Maybe either way could be supported.

Working With Lists

Let's say I want to perform an operation on a list of numbers. For instance, let's say I want to create a sum or product function and I want to call them like this:

[2, 3] -> sum -> sumResult
[2, 3] -> product -> productResult

I expect sumResult to contain 5 and productResult to contain6.

In order for this to work, I need a special way to work with lists. I came up with a way that is similar to Go slices.

The idea is that I can slice a list into two pieces: the head and the tail. Both the head and tail can be single numbers or a list of numbers at their respective ends. To extract that information, I imagine passing a list through a special transformer like this:

[1, 2, 3] -> [0:0] -> result

Given this, result would be a tuple (1, 3). The [0:0] transformer took the zeroth element from the head and the zeroth element from the tail and output a tuple.

Here's another example:

[1, 2, 3] -> [0:] -> result

In this example, result contains (1, [2, 3]). It took the zeroth element from the head and put the rest into the tail.

Here are some more examples. I added some comments after each line so you can see what result contains.

[1, 2, 3] -> [1:] -> result    # ([1,2], 3)
[1, 2, 3] -> [:0] -> result    # ([1,2], 3)
[1, 2, 3] -> [1:1] -> result   # ([1,2], [2,3])
[1, 2 ,3] -> [:] -> result     # ([1,2,3], [1,2,3])

That's generally how it is meant to work. So now, using that syntax, I can construct my sum and product functions like this:

[0:] -> (h, t) -> (t=[], h, h+(t->sum)) -> branch -> sum
[0:] -> (h, t) -> (t=[], h, h*(t->product)) -> branch -> product

Since the product function is the same as sum, I'll just walk through sum.

  1. Given a list, take the zeroth element from the head and the rest of the list and output a tuple (h, t) where h contains a number and t contains a list.

  2. Send that tuple into another tuple to get it ready for the branch function.

  3. The branch function determines if t is an empty list. If it is, then it outputs h. Otherwise, it adds h to (t->sum).

WAIT! That's right. Recursion. Did I mention I don't want explicit loops in my language?

Not just recursion, but it's recursion before sum is even defined. I imagine that the body of the function is lazily evaluated. I don't think implementing that would be a big deal.

OK... back to it...

  1. The successive recursive calls are evaluated and eventually h is returned and returned and returned and returned until everything unwraps.

  2. It stores this transformation into the sum variable, which becomes the function name.

It's a little crazy, I know... but it works for me.

The Factorial Function

Now with all of these things, I finally have the means by which I can write a factorial function! I will leave this up as an exercise to the reader to evaluate. That being said, I was able to work through it on pencil and paper and found that it actually works! Give it a try yourself if you're bored one lazy Sunday afternoon.

n -> ((n, 1)->lte, 1, [n, n->decrement->factorial]->product) -> branch -> factorial