Programming with Fexl

Fexl is a programming language based on the concept of functions, and is an extension of the notation known as the lambda calculus, devised by Alonzo Church in the 1930s. The name is an acronym for "Function EXpression Language," and is pronounced fex'-uhl, somewhat similar to "pixel."

A function is something that is applied to an input and returns a corresponding output. In effect, a function is something that answers questions: the input is the question, and the output is the answer to that question.

For example, you might have a function which takes a number as input and returns twice that number as output. Apply the function to 1 and you get 2. Apply it to 2 and you get 4. Apply it to 27 and you get 54. When you apply the function to a number, you are asking the question "What is twice the value of this number?", and the function gives you the answer.

The lambda calculus is a notation capable of expressing any computable function one might conceive. Fexl extends the notation in small but powerful ways to make it more practical for writing real world programs.

Biographical Note

My name is Patrick Chkoreff, and I began programming in BASIC at Marist High School in 1974. I quickly progressed from Fibonacci on a teletype, to writing Space War games on a CRT. In 1980 I began programming in C at Georgia Tech. From 1982 to 1985 I did a good bit of scientific programming in Fortran. In 1984 I did AI programming in Lisp. In 1996 I began doing web programming in Perl, and in 2004 I started doing investment fund accounting in Perl as well.

My initiation to functional programming (not counting Lisp) came in 1989, when I read an article titled "Typed Representation of Objects by Functions", by Jørgen Steensgaard-Madsen. This introduced me to the notion that the dividing line between function and data could be blurred: i.e., that even data objects could behave like functions: most notably things like boolean values, lists, and tuples. I found that this has amazing expressive power, eliminating the need for traditional "accessor" functions (such as Lisp's car, cdr, and nullp) to examine and process data.

From 1996 to 2012 I continued to use Perl for all my work. I had an implementation of Fexl, but the momentum to stick with existing technology was great. Finally one day I was writing a new report for our investment accounting business, and I asked myself, "Why not just write this one report in Fexl?" I never looked back. Since then, I have been systematically replacing all our Perl code with Fexl, and writing all new code in Fexl. Fexl has a highly concise and precise expressive power, making it very amenable to refactoring and progressive refinement, and its module system based on the concept of context allows me to build any enhanced or restricted computing environment I need for any application domain.

Lambda Calculus Syntax

The lambda calculus is a notation capable of expressing any computable function. Although Fexl extends this notation to make it more convenient to write programs, it is always possible to define the extensions in terms of the basic lambda calculus.

In the lambda calculus, a function takes one of three forms: (1) a symbol, (2) a function application, or (3) a lambda expression.

Symbol

The first form of a function is a symbol. A symbol is either a name or a string. In the original lambda calculus there are only names, but I take the liberty of including strings right up front in this presentation. I also pin down the rules of what constitutes a name.

Name

The first form of a symbol is a name. A name is any sequence of characters except for white space, NUL, backslash, left or right parentheses, semicolon, double quote, tilde, pound, or equal sign. Examples:

x
37
+
twice
append

String

The second form of a symbol is a string. A string is a way of expressing a string value, which is any sequence of zero or more arbitrary bytes (NUL is allowed). A byte is an 8-bit unsigned machine number in the range 0 to 255.

There are two ways of specifying string values: a quote string or a tilde string.

Quote String

The first way of expressing a string value is a quote string. A quote string is a string value enclosed within a pair of double quotes, with the restriction that a double quote cannot appear within the string value. Examples:

""

"hello world"

"This is a multi-
line string."
You can also use characters from other languages and notations through the use of UTF-8 encoding. Example:
"hej
åabcüdef
ghij
üä
1≠0
封
"

Tilde String

The second way of expressing a string value is a tilde string. A tilde string is a string value enclosed within a pair of delimiters of your own choice. You can choose any delimiter which does not appear within the string value.

The tilde string starts with a tilde (~), then zero or more non white-space characters. That sequence, including the tilde, constitutes the delimiter. The white space character which terminates the delimiter is ignored. This is followed by the desired string value, and finally a repeat occurrence of the original delimiter. Examples:

~ This has "quotes" in it.~

~| This has "quotes" in it.~|

~END
Anyone familiar with "here is" documents
should easily understand the rule.
~END

~~
Usually just a single tilde "~" will suffice as a delimiter, or if the string
contains a tilde like this one, then a double tilde will suffice.
~~

Function Application

The second form of a function is a function application. If F and X are arbitrary functions, then the following expression represents the application of F to X:
(F X)

In that expression, F is typically called the function, and X is called the argument.

Examples:

(twice 27)

(add (twice x) ((mul y) y))

((say "Hello world.") (say "Goodbye."))

(((a b) (c d)) (e (f (g (h i)))))

Lambda Expression

The third and final form of a function is a lambda expression. This introduces a new name, known as a parameter, which can be used in the body of the expression. When you apply a lambda expression to an argument, all free occurrences of the name inside the body of the expression are replaced with that argument, in a process known as substitution. A free occurrence is anywhere the name appears except inside another lambda expression introducing the same name.

If X is an arbitrary name, and F is an arbitrary function, then the following is the lambda expression which introduces X as a parameter to F:

(\X F)

The backslash character '\' indicates that the name X is to be treated as a parameter name, distinguishing it from a function application. The original lambda calculus uses the Greek character λ to introduce a parameter, but I use '\' instead because it is easier to type, and is the ASCII character which most closely resembles λ. Examples:

(\x 2)

(\x x)

(\x (x x))

(\x (\y ((add (twice x)) ((mul y) y))))

(\x (x (\x ((mul x) x))))

Note that the last expression has two different declarations of parameter x. In the following expression, I have highlighted the outer parameter x along with its sole free occurrence:

(\x (x (\x ((f x) x))))

In the next expression I have highlighted the inner parameter x along with its two free occurrences:

(\x (x (\x ((f x) x))))

A lambda expression binds the parameter name, so occurrences outside the body of the expression are no longer considered free. A lambda expression is also known as an abstraction, because the body of the expression is defined abstractly, in terms of a parameter name whose value is not yet specified.

Lambda Calculus Semantics

An function expressed in the lambda calculus notation is evaluated according to simple and predictable rules. The expression is reduced one step at a time until it reaches a final value that cannot be reduced any further, known as a normal form.

Consider first a lambda expression:

(\X F)

That function is considered to be in normal form, meaning that no further evaluation is possible. The value of the expression is itself.

Now consider a function application:

(F X)

In this case F is evaluated first, typically resulting in a lambda expression. Then the argument X is substituted into the body of the lambda expression, replacing all free occurrences of the lambda parameter. Evaluation then continues with the resulting expression.

Finally, consider the evaluation of a symbol. The value of a string is always itself. But note that you will never have to evaluate a name, because a name is always replaced with some other functional value before it is evaluated.

Example Evaluation

To illustrate the process of evaluating a function, I use a notation where I put ":" in front of the original expression, and "=" in front of each reduction step. Comments are indicated with "#".

Here's an example which uses three names add, twice, and mul which are not defined within the example itself. Assume that those names have already been replaced with suitable definitions from an outer context.

: (((\x (\y ((add (twice x)) ((mul y) y)))) 3) 7)  # Original expression
= ((\y ((add (twice 3)) ((mul y) y))) 7)           # Replace x with 3.
= ((add (twice 3)) ((mul 7) 7))                    # Replace y with 7.
= ((add 6) ((mul 7) 7))   # The add function evaluates its first argument.
= ((add 6) 49)            # The add function evaluates its second argument.
= 55

Extensions to the Lambda Calculus

The basic lambda calculus has the minimal syntax needed to express arbitrary computation in an unambiguous form. But minimal is not the same as optimal.

Function Application is Left-Associative

The first problem is there are too many parentheses. Every individual lambda expression or function application must be grouped with a pair of matching parentheses. That is easy to fix.

First consider this expression which adds x and y:

((add x) y)

The first simplification is that the topmost expression need not appear inside parentheses.

(add x) y

The next simplification is that function applications are left-associative, meaning that if you omit parentheses, they group toward the left by default.

add x y

In general, ((f x) y) can be written more simply as (f x y). So these two expressions are equivalent:

(((((a b) c) d) e) f)

a b c d e f

That doesn't mean you can eliminate all parentheses though. These two expressions are equivalent, and that's as far as the rule can be applied:

(((a b) (c d)) (e (f (g (h i)))))

a b (c d) (e (f (g (h i))))

Lambda Abstraction is Right-Associative

Consider this lambda expression:

(\x (A B))

There is no particular need for the inner parentheses, so you can write it as:

(\x A B)

Now consider this:

(\x (\y A))

Again there's no need for the inner parentheses, so you can write it as:

(\x \y A)

Furthermore, there's no need for a space between the parameters:

(\x\y A)

The rule can be extended to any number of parameters:

(\x\y\z A)

Alternative Syntax for Definitions

Imagine you are using the arithmetic functions add and mul in several places:

add 4 (add (mul 23 8) (mul 3 5))

Assume for a moment that those are not predefined, and you have to define them yourself. So far it looks like you'd have to say something like this:

(\add\mul
add 4 (add (mul 23 8) (mul 3 5))
)
(... definition of add ...)
(... definition of mul ...)

That way the occurrences of the names add and mul would be replaced with their respective definitions, and evaluation could proceed. However, putting the definitions of symbols at the end is quite counterintuitive and unwieldy. For this reason I introduce a special syntax for definitions, so the example above can be written more simply as:

\add==(... definition of add ...)
\mul==(... definition of mul ...)
add 4 (add (mul 23 8) (mul 3 5))

Now a symbol and its definition appear together, at the top, before those symbols are used. You use "==" to mean that the definition of the symbol is not evaluated first, but is simply passed in normally just like any lambda substitution. If you use a single "=", that represents an evaluated definition, as described below. As it turns out, evaluated definitions are usually what you want, so I reserved the simpler syntax for that.

In general, these expressions are equivalent:

(\X F) D

\X==D F

Evaluated Definitions

In most cases, you want the definition D to be evaluated first, before being substituted in for the symbol X. Consider what happens here:

\x==(add 2 3)
mul x x

The definition of x would be subtituted, resulting in:

mul (add 2 3) (add 2 3)

Everything will work just fine, and you'll get the value 25 as expected, but there's one problem: the expression (add 2 3) will be evaluated twice. In this case that's not too big a deal, since (add 2 3) is evaluated very quickly. But imagine if the definition takes a very long time to run, or if evaluating the definition has side effects, such as printing output, writing to a file, or opening a window on the screen. In that case you definitely do not want the definition evaluated twice.

In a case like that, or indeed in most cases, you can use a single "=" to indicate that the definition should be evaluated only once:

\x=(add 2 3)
mul x x

When that is evaluated, the expression (add 2 3) is evaluated to produce the final value 5, and that final value is then substituted for x:

mul 5 5

Recall that every expression in the extended Fexl syntax can be rephrased in terms of the basic lambda calculus syntax. The same goes for evaluated definitions, which can be expressed in terms of a named function "eval". In general, the following two expressions are equivalent:

\X=D F

eval D \X F

The eval function evaluates its first argument, then it passes that final value to its second argument. Here is the expression with a couple more parentheses to show the two arguments more explicitly:

eval D (\X F)

Now let's see how that rule applies to this expression:

\x=(add 2 3)
mul x x

Applying the rule, that is equivalent to:

eval (add 2 3) (\x mul x x)

When the eval function runs, it evaluates its first argument (add 2 3) one time, producing the value 5. It then passes 5 to its second argument:

(\x mul x x) 5

The x is then replaced with 5, yielding the following:

mul 5 5

Evaluation proceeds from there to yield the final answer 25.

Eliminating Parentheses on the Right

Consider this example:

(a (b (c (d (e (f g))))))

Is there any way of eliminating all those bunched up parentheses on the right? Note that you cannot do this:

a b c d e f g

Because that is equivalent to:

((((((a b) c) d) e) f) g)

We need some way of indicating that expressions are to be grouped on the right side. For this purpose I introduce the ';' (semicolon) notation which acts like a pivot in the expression, in effect automatically wrapping everything following the ';' inside a pair of matching parentheses. In general, the following expression:

A (B C)

Is equivalent to this:

A; B C

So the example above can be properly rewritten as:

a; b; c; d; e; f g

You can even put a ';' before the very last argument g, though it is not strictly necessary:

a; b; c; d; e; f; g

This doesn't mean you can always eliminate all parentheses. Consider:

(((a b) (c d)) (e (f (g (h i)))))

First we can apply the left-associative rule for function application to eliminate some parentheses:

a b (c d) (e (f (g (h i))))

Then in the third expression we can apply the pivot syntax to eliminate some more parentheses:

a b (c d) (e; f; g; h i)

You can even take it one step farther if you like:

a b (c d); e; f; g; h i

But that's as far as you can go. You cannot eliminate the parentheses around the (c d) term.

Side Effects

In the previous section I mentioned the notion of side effects. Side effects include such things as printing output, writing to a file, opening a window on a screen, reading input from the keyboard, and many other ways of interacting with the environment in which a function is evaluated. Fexl is not "purist" in its approach to functional programming: it recognizes that the entire point of running a computer program is to produce useful side effects. Many functional programming languages go to great lengths to hide or obscure the production of side effects, but Fexl does not bother.

"Hello world"

The classic example for all programming languages is the "Hello world" program. This program simply prints "Hello world" to the output device, followed by a new line, and then stops. In Fexl, that program is:

say "Hello world"

That is as simple as it can get. The say function prints its argument to the screen. But in functional programming, every function evaluation produces a value. So what is the value of (say "Hello world")? And if all we really care about is the side effect, why does it even need to return a value? Well, consider this expression:

say "Hello world"
say "Goodbye"

Here's what happens. The (say "Hello world") is evaluated, printing that message to the screen. The value of that expression is something we call I, representing the identity function. The identity function is the function which returns the value of any argument you pass into it, and can be defined in the lambda calculus as:

(\x x)

So after the (say "Hello world") is evaluated, the expression becomes:

I
say "Goodbye."

The I applied to say gives us the value say, so now we have:

say "Goodbye."

Now the message "Goodbye." is written to the screen, and the final value of the whole expression is:

I

If you're familiar with normal procedural languages, think of I as the value returned when all you want to do is continue evaluating the next thing, in sequence. You shouldn't have to think about it too much. If you're evaluating functions which have side effects and don't really return a value as such, you can just string them together in a linear sequence, just as you would do in an ordinary procedural language. The reason I emphasize that these actually return a value I is to show that all types of programs, including procedural ones, can ultimately be expressed in the notation of lambda calculus. In Fexl, all evaluation is done in terms of lambda substitution and function application, and there is no exception for so-called "procedural" programs.

All Functions Have Side Effects

Quite simply, the evaluation of any function in Fexl can have side effects. In fact, if you get right down to it, even the evaluation of a so-called "pure" function like (add 2 3) has side effects too. You might think all that does is return the value 5, but in point of fact the evaluation both (1) consumes time, and (2) produces heat inside the computer: both of which are side effects. The point here is to emphasize that Fexl is a language for controlling the behavior of a physical device, even though it is based on the mathematical concept of functions.

However, Side Effects are Manageable

The beauty of a language with lambda abstraction is that it allows you to isolate side effects however you like, making more of your code look "pure". So instead of a traditional piece of code going through a bunch of data, processing and filtering the data, and printing as it goes, you can instead very easily do the processing and filtering in an entirely separate section of code, and do the printing in a very simple section that expects perfectly groomed input.

The one kind of side effect that can be extremely malignant in a traditional programming language is mutable data, which is data that can be changed during processing right "under your feet" so to speak. That can lead to very confusing code. However, Fexl is not dogmatic on this issue either. Many things in the real world do in fact behave like mutable data: the file system being a prime example. Another example is any kind of payment API, where you send transactions to a remote server. In that case the entire remote database behaves like a giant global variable, albeit with a very well-defined interface.

Fexl does provide a "var" (variable) data type which you can use to model mutable data. A var is a pointer to a value, and you can change what the var points to. However, there is no way to alter a value itself. In my extensive programming with Fexl, I have found very few cases where I need to use a var. The main use is when I am emulating a database in memory, and I don't often need to do that.

In virtually 100% of my code, I use only immutable data — and that includes cases where you might immediately think to use mutable data in a normal programming language. A prime example is how I use Fexl to do accounting for investment partnerships. In a traditional language, you might implement each event such as security trades, dividends, and partner deposits or withdrawals using a routine that modifies a data structure such as a nested hash table. In Fexl, I implement each event as a function which takes in the original data structure as input, and produces a new structure as output. An experienced programmer may worry about excessive copying, however, that is not a problem in Fexl because vast swaths of the input and output structures are shared via direct pointers. And, because those structures are immutable, such sharing is always safe.

Furthermore, Fexl takes care of all memory management for you, using the technique of reference counts, so you never have to worry about memory leaks, or accidentally using memory that has already been freed.

Arithmetic functions

In this example I have used the name add for addition and mul for multiplication. I could also use sub for subtraction and div for division. However, I prefer to use the common operator symbols + * - /. So here is a function which adds its first two arguments together, and multiplies that sum by its third argument:

(\x\y\z * (+ x y) z)

Note that I have expressed the function as a closed form, i.e. as a standalone entity. I haven't bothered to give it a name. If I wanted to name it as "G", I would do this:

\G=(\x\y\z * (+ x y) z)

# ... Then I could use G repeatedly down here.

No doubt at this point a lot of people are going to object to putting + and * in front of its inputs instead of between them. However, I am aiming for the simplest possible notation, based on the concept that a function is always applied to an input, expressed as f x. Given that premise, putting the function between its inputs makes no sense. If you write this:

2 + 3

Then what you're trying to do is take the value 2, apply that to the value +, and then apply that to the value 3. It's utter nonsense to apply the number 2 to the input +. You might object that I should make an exception for "special symbols" such as + and *. My reply is (1) I don't want any concept of special symbols, and (2) even if I had them things would get very complicated and irregular. I have been doing functional programming for a long time and I'm completely comfortable with expressions like (+ x y). I don't miss the "infix" notation one single bit. The grammatical and conceptual simplicity is totally worth it.

Void

There is a special value called void which a function can return if there is no sensible output for a given input. For example if the function does an ordinary square root, it can return void if you give it a negative number. Another example is trying to open a file that doesn't exist.

The nice thing about void is that it eliminates the need for an "exception" mechanism present in some programming languages. If a function returns void and your code goes on to apply that to another value, the result is still void. That way an entire block of computation can just "void out" on a bad input, and the void result percolates all the way up. At any stage you can check for void if you like, for example if you wanted to issue an error message — but you don't have to check for void at every stage.

The void value behaves like a function which takes any input you give it, and always returns void itself as the output. So for any input x, it is always true that:

void x = void

Logical functions

All programming involves logical functions, which return a value of T (true) or F (false). For example there is a function eq which decides if its two inputs are equal. The inputs can be either numbers or strings. Here are a few examples:

eq 1 1 = T
eq 1 2  = F
eq 27 27 = T
eq 27 32 = F

eq "" ""  = T
eq "" "a" = F
eq "abc" "abcd" = F
eq "abcd" "abcd" = T
eq "Abcd" "abcd" = F

Now the question is, once you have a logical value T or F, what can you do with that value? You need to be able to do one thing if it's true, and another thing if it's false. Most languages have an "if" statement to do that kind of branching. Fexl takes a different approach. The logical values T and F behave like functions which give you either the first or second input. In other words, for any inputs x and y, the logical values behave like this:

T x y = x
F x y = y

The true value gives you the first input, and the false value gives you the second input. There is no need for a special keyword like "if" used in virtually every other programming language under the sun. In fact, there are no special keywords at all in Fexl. Any time you see a symbol, it refers to a value or function, period. No symbol has any special significance outside of that.

So let's say you want to write a function called is0 that returns "YES" if its input is 0, and "NO" if its input is not zero. That would be:

\is0=(\n eq n 0 "YES" "NO")

In a more traditional programming language like C, you could say:

const char *is0(int n)
    {
    if (n == 0) return "YES";
    return "NO";
    }

Or you could get cute and use the "ternary" operator:

const char *is0(int n) { return (n == 0) ? "YES" : "NO"; }

Recursion

The "fixpoint" function @ is the foundation of recursion. It allows you to create a function that can refer back to itself. It is defined in such way that for any function F, this is always true:

@ F = F (@ F)

In other words, the fixpoint of F passes its entire self in as the input to F! This means that F now has a "handle" on its own fixpoint. It's almost like pointing two mirrors at each other, so you get a reflection of a reflection of a reflection, ad infinitum.

For example, let's say I wanted to write a function tally that takes an input number n and adds up all the numbers from 1 through n. Of course, I could use the standard formula for that, which doesn't involve any recursion:

(\n / (* n (+ n 1)) 2)

But for the purposes of this discussion I want to do it by actually adding up all the numbers. When the function gets the input n, it first decides if it's less than or equal to 0. If so, it returns 0. If it's greater than 0, it subtracts one from it, calculates that tally, and adds n to the result.

I need to be able to call the tally function from within the function itself. To do that, I declare tally as a parameter to the function, and apply @ to that function:

(@\tally\n
le n 0 0;
\m=(- n 1)
+ n (tally m)
)

Now that is a completely closed-form expression for the function that adds up all the numbers from 1 through the input n. But the syntax is unfamiliar: what does it mean to jam the @ function right up against the parameter like that? As it turns out, there's another syntax feature which makes it possible. Any time you have an expression like this:

F (\x ...)

You don't need to group the lambda expression on the right, so you can write it more simply like this:

F \x ...

Furthermore, because "\" cannot be used within a symbol, you can write it:

F\x ...

Ordinarily that would look a little obscure but for @ it's perfect:

@\tally ...

That syntax feature turns out to be incredibly useful for other reasons which I'll get to later. But it's particularly useful for this example too, because otherwise I'd have to write the tally function more clunkily as:

@
(\tally\n
le n 0 0;
\m=(- n 1)
+ n (tally m)
)

Why not just name the function and dispense with @?

An experienced programmer might cleverly suggest that I assign a name to the function like this:

\tally=
    (\n
    lt n 0 0;
    \m=(- n 1)
    + n (tally m)
    )
[code using tally]

However, believe it or not, that accomplishes nothing. Recall that the "=" sign used for definitions is just a shorthand for a lambda expression. So the suggestion above is equivalent to:

(\tally [code using tally])
    (\n
    lt n 1 0;
    \m=(- n 1)
    \total=(tally m)
    + n total
    )

The expression below the first line still refers to tally, which is not defined within the expression. The definition of the function must be a closed-form expression which can be lifted out, passed around, and substituted just like any other value.

On the other hand, it is useful to define the name tally for the closed form definition, so you can use it in multiple places just like the G function in an earlier example. I could then say something like:

\tally=
    (@\tally\n
    le n 0 0;
    \m=(- n 1)
    + n (tally m)
    )

* (tally 10) (tally 7)

The value of that expression is then:

1540

Is there an easier way to think about recursion?

I do understand all the splendid logic behind the @ function. But honestly, I tend to think of it as introducing a label in the code. When I refer to that label, I "jump" to that place in the code. That is a very old-school way of thinking about it, but I like it because it's very concrete. The difference is that in Fexl, when you do the "jump", you can pass along other parameters as you go. In the tally function where it says tally m, I am indeed "jumping" to the label called tally, but I'm also carrying in the new value m as I go.

What's really happening when I refer to tally within the code is that I'm in effect getting an entire copy of the whole function, including the @ itself. That may seem a little mind-bending at first, but if you're going to do functional programming, you'd better get used to it.

Can you illustrate how recursion works?

All right, we have a definition of tally. Now I'll show how the expression tally 3 is evaluated, giving the result of 6. In effect, it will be a mathematical proof that:

tally 3 = 6

I'll show you the reduction sequence for that, but first I'd like to express the definition of tally like this:

\Q=
    (\tally\n
    le n 0 0;
    \m=(- n 1)
    + n (tally m)
    )

\tally=(@ Q)

The reason is that when you're dealing with fixpoints, it's not convenient to copy the entire definition every time in the reduction sequence. So I introduce a new symbol Q to refer to the large blob of code there. WARNING: This reduction sequence will look very long and boring, but it will give you some insight into how a functional expression, even one involving recursion, can be evaluated symbolically, by a human being, "on paper" so to speak.

# Here's the original expression
: tally 3

# Replace tally with its definition.
= (@ Q) 3

# Invoke the rule for @.
= Q (@ Q) 3

# Replace the first Q with its definition.
=
    (\tally\n
    le n 0 0;
    \m=(- n 1)
    + n (tally m)
    )
    (@ Q) 3

# Replace the tally parameter with the input value.
=
    (\n
    le n 0 0;
    \m=(- n 1)
    + n ((@ Q) m)
    )
    3

# Replace the n parameter with the input value.
=
    (
    le 3 0 0;
    \m=(- 3 1)
    + 3 ((@ Q) m)
    )

# Evaluate (le 3 0), which returns F (false).
=
    (
    F 0;
    \m=(- 3 1)
    + 3 ((@ Q) m)
    )

# Invoke the rule (F x y) = y.
=
    (
    \m=(- 3 1)
    + 3 ((@ Q) m)
    )

# Evaluate m.
=
    (
    \m=2
    + 3 ((@ Q) m)
    )

# Replace m with its value.  Also use the ";" notation here to eliminate some
# parentheses.
= (+ 3; (@ Q) 2)

# Invoke the rule for @.
= (+ 3; Q (@ Q) 2)

# Replace the first Q with its definition.
= (+ 3;
    (\tally\n
    le n 0 0;
    \m=(- n 1)
    + n (tally m)
    )
    (@ Q) 2
    )

# Replace the tally parameter with the input value.
= (+ 3;
    (\n
    le n 0 0;
    \m=(- n 1)
    + n ((@ Q) m)
    )
    2
    )

# Replace the n parameter with the input value.
= (+ 3;
    le 2 0 0;
    \m=(- 2 1)
    + 2 ((@ Q) m)
    )

# The (le 2 0) returns F, which chooses the second input.
= (+ 3;
    \m=(- 2 1)
    + 2 ((@ Q) m)
    )

# Replace m with its value, and use another ";".
= (+ 3; + 2; (@ Q) 1)

# Invoke the rule for @.
= (+ 3; + 2; Q (@ Q) 1)

# Replace the first Q with its definition.
= (+ 3; + 2;
    (\tally\n
    le n 0 0;
    \m=(- n 1)
    + n (tally m)
    )
    (@ Q) 1
    )

# Replace the tally parameter with the input value.
= (+ 3; + 2;
    (\n
    le n 0 0;
    \m=(- n 1)
    + n ((@ Q) m)
    )
    1
    )

# Replace the n parameter with the input value.
= (+ 3; + 2;
    le 1 0 0;
    \m=(- 1 1)
    + 1 ((@ Q) m)
    )

# The (le 1 0) returns F, which chooses the second input.
= (+ 3; + 2;
    \m=(- 1 1)
    + 1 ((@ Q) m)
    )

# Replace m with its value, and use another ";".
= (+ 3; + 2; + 1; (@ Q) 0)

# Invoke the rule for @.
= (+ 3; + 2; + 1; Q (@ Q) 0)

# Replace the first Q with its definition.
= (+ 3; + 2; + 1;
    (\tally\n
    le n 0 0;
    \m=(- n 1)
    + n (tally m)
    )
    (@ Q) 0
    )

# Replace the tally parameter with the input value.
= (+ 3; + 2; + 1;
    (\n
    le n 0 0;
    \m=(- n 1)
    + n ((@ Q) m)
    )
    0
    )

# Replace the n parameter with the input value.
= (+ 3; + 2; + 1;
    le 0 0 0;
    \m=(- 0 1)
    + 0 ((@ Q) m)
    )

# This time the (le 0 0) return T, which chooses the first input.
= (+ 3; + 2; + 1; 0)

# Evaluate the (+ 1 0).
= (+ 3; + 2; 1)

# Evaluate the (+ 2 1).
= (+ 3; 3)

# Evaluate the (+ 3 3).
= 6

I have now proven that:

tally 3 = 6

Keep in mind that a computer processor, using direct pointers in memory, can do this kind of thing in a flash, with no need to copy the intermediate values at every step. I only did that here to illustrate the logic of each step.

What about efficiency?

Experienced programmers will immediately note that the way I defined tally will pile up n stack frames as it evaluates. For large numbers that might be an issue. As it turns out, you can write it differently so it carries a "running total" as it goes. This makes it entirely "tail recursive" so it doesn't use any extra stack space regardless of how large the input number is.

\tally=
    (@\loop\total\n
    le n 0 total;
    \total=(+ n total)
    \m=(- n 1)
    loop total m
    )

\tally=(tally 0)

Note that I used the name loop there. Sometimes I don't bother to name the recursion parameter the same as the function being defined, and I just use "loop". It doesn't make any difference. Sometimes it even seems clearer to me that way.

That first definition of tally takes in a running total and the current number n. It adds n to the total, subtracts 1 from n, and then loops with the new total and number. The second definition simply redefines tally so it always starts with a running total of 0.

If you prefer, you can write the definition the "minimalist" way:

\tally=
    (
    (@\loop\total\n
    le n 0 total;
    \total=(+ n total)
    \m=(- n 1)
    loop total m
    ) 0
    )

Or if you'd like to make that loop a bit more explicit, you can say:

\tally=
    (
    \accumulate=
        (@\loop\total\n
        le n 0 total;
        \total=(+ n total)
        \m=(- n 1)
        loop total m
        )
    accumulate 0
    )

A lot of this is stylistic. As Larry Wall the author of Perl likes to say, "There's More Than One Way to Do It." (TMTOWTDI) On the other hand, the "Zen of Python" argues that "There should be one — and preferably only one — obvious way to do it." In that case I'd go with the minimalist way, on the basis that it has fewer visual "moving parts" so to speak.

Note how the loop takes in the initial running total of 0 and "absorbs" it, returning a function which then accepts the parameter n. In the functional programming literature this is called a "closure". The function has the initial running total "baked into" it, and now it's sitting there waiting for you to give it a number so it can run with it.

That won't be as fast as C!

You got me there. In C you could just write the tally function as:

int tally(int n)
    {
    int total = 0;
    int i;
    for (i = 0; i <= n; i++)
        total += i;
    return total;
    }

So if that's what you need to do, then go ahead and do it. You can write a function in C and link it into Fexl. I've already done that for several functions that need the efficiency of bit-bashing in C, e.g. for cryptography functions. Fexl coexists with C. I designed Fexl to be the thinnest possible functional programming layer on top of C that I could possibly conceive. That way I can get the best of both worlds, and the worst of neither.

Modularity

TODO Here I will discuss how Fexl allows the modular construction of programs using the precise mathematical concept of context. A context is, quite simply, a function which maps a name to its definition. Any program text in Fexl is first resolved in a specific context, which provides definitions for any free symbols used in the text, but not defined within the text itself.

Because a context is just a function, this allows you to control and compose a set of useful definitions using Fexl itself, with the full power of the programming language. With this power, you make an entire suite of useful functions available instantly and effortlessly anywhere you like. You can evaluate different programs in different contexts, depending on the problem domain. You can implement familiar features such as "search paths" using Fexl itself. You can extend a context for convenience, or restrict a context for safety, or both. You can write an ultra-portable, "abstracted" program, where the definitions of key symbols are provided outside the program itself, and can be changed or swapped at will.

© 2019 Patrick Chkoreff