# A Functional Programming Language

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.

## Overview

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".

```plaintext
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.

```plaintext
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.

```plaintext
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:

```plaintext
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.

```plaintext
3 -> double -> double -> result
```

This will store `12` in the new variable `result`.

Here are some additional simple function definitions:

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

Using these, I can contrive this silly example:

```plaintext
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:

```plaintext
(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:

```plaintext
(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:

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

**note:***spaces don't matter*

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

```plaintext
(?, 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:

```plaintext
((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:

```plaintext
(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:

```plaintext
(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:

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

I expect `sumResult` to contain `5` and `productResult` to contain`6`.

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:

```plaintext
[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:

```plaintext
[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.

```plaintext
[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:

```plaintext
[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...

4. The successive recursive calls are evaluated and eventually `h` is returned and returned and returned and returned until everything unwraps.
    
5. 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.

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