Function EXpression Language
Function EXpression Language
Fexl is a programming language based on pure functions. The name "Fexl" (pronounced Fex' - uhl) stands for Function EXpression Language. It's an accurate name, because Fexl is indeed a language for expressing functions. As you will see, everything in Fexl is a function.
RULE 1: EVERYTHING is a function.
This means everything, including data. A list is a function. A boolean value is a function. A number is a function. A string is a function. An entire program is a function. You name it, it's a function.
Exactly how data are represented as functions is the subject of another discussion (see below). Fexl uses the method described in the Jan 1989 issue of ACM Transactions on Programming Languages and Systems, in an article titled "Typed Representation of Objects by Functions," by J. Steensgaard-Madsen. Suffice it to say it's incredibly elegant.
"RULE 2: Side effects happen."
Ultimately the entire purpose of a computer program is to interact with its environment -- in other words, to create side effects. This includes drawing on a screen, reading a keyboard and mouse, sending messages to other computers, moving robot arms, etc.
In spite of this, a Fexl interpreter has no side effects. Fexl only does symbol manipulation, reducing a function to a final normal form. At that point it is up to the programming environment to look at that normal form and see if it needs to draw something on the screen, get some input, play a sound, or whatever. So you can write code which looks very ordinary and procedural, like this:
print "Hello, world"; nl; beep; beep; # beep the speaker twice getline \line print "You typed: "; print line; exit;
However, the beauty of it is that functions such as "print" and "beep" and "getline" do not have hard-coded meanings, so that program fragment can run inside any kind of safe "sandbox" you like. The programming environment surrounding the Fexl interpreter could even use different sorts of definitions for print, getline, beep, and exit. This is very useful for creating test environments, or environments that limit what certain users can do.
With this kind of thing, it is actually possible to download a function from the internet and run it in a protected way that is guaranteed to be safe. Or, if that function is from a highly trusted source, you can run it directly "on the iron" so to speak, calling the operating system and hardware directly.
What Does Fexl Really Do?
Fexl is just a bunch of functions being applied to other functions to produce more functions. In that sense, a Fexl program is just "swimming on air." However, what it's really doing is serving as a general-purpose "sequencer" for an arbitrary set of primitive routines and data types written in C.
The goal is to do only the low-level code in C, and migrate more and more of the serious application logic into your Fexl sequencer.
Why Isn't Fexl More Conventional, Like C, Perl, Ruby, Python, or even Lisp?)
What would be the point? Those languages already rule at what they do. Fexl has to be different. But Fexl does not compete with other languages, it complements them. You can call the Fexl interpreter from any language you prefer. You can fold more and more of your code into Fexl if you like, completely at your leisure and discretion. Eventually you may end up with all your code in Fexl, at which point you can dispense with the other scripting language altogether.
How Do Functions Work?
A function is something that is applied to an input value to produce an output value. In general you take a function f, apply it to an input x, and it produces an output y.
f x = y
For example, you might apply a function called "twice" to the input 7, producing the output 14:
twice 7 = 14
You can also have functions that take more than one input value:
add 3 5 = 8
Actually, all functions take only one input. The add function only appears to take two inputs. In reality, when you apply add to 3, you get the function (add 3). The (add 3) function adds 3 to whatever input you give it. So the next step is to apply (add 3) to the input 5. This yields the final output 8.
The expression (add 3 5) is actually a shorthand for the fully parenthesized expression ((add 3) 5). The longer form makes it clear that we are applying the function (add 3) to the value 5.
Because function application is left-associative, we can dispense with any extra parentheses that group things toward the left. So these expressions are all equivalent:
(((a b) c) d) ((a b) c d) (a b c d) a b c d
Of course, when you have grouping toward the right you cannot simply drop the parentheses. For example, you could not drop the parentheses in this expression:
a (b c) d (e f (g h i))
However, I have devised a neat syntactical trick that lets you express right-grouping without parentheses. If you have something grouped off to the right as in (e f (g h i)), you can rewrite this as (e f; g h i). The semicolon acts as a "fulcrum" pivot point meaning "wrap parentheses around everything that follows." So all of these expressions are equivalent:
a (b c) d (e f (g h i)) a (b c) d (e f; g h i) # right-pivot after the f a (b c) d; e f; g h i # right-pivot after the d
The pivoting semicolon neatly expresses the notion of sequentiality in procedural programming. For example:
print "hello"; print "how are you?"; exit 0
If we removed the pivoting semicolons from this function, we would have:
print "hello" (print "how are you?" (exit 0))
That expression has the form (print string next), which prints the string as a side-effect and then returns the value next.
So here's what happens when this function is run. We demonstrate the behavior of Fexl by showing the reduction sequence starting from an initial expression marked with ':', and continuing to each subsequent equivalent expression marked with '='.
: print "hello" (print "how are you?" (exit 0)) # (prints "hello") = print "how are you?" (exit 0) # (prints "how are you?") = exit 0 # (exits with code 0)
Of course, it's more natural just to preserve the semicolons and view it as a simple procedural computation sequence:
: print "hello"; print "how are you?"; exit 0 # (prints "hello") = print "how are you?"; exit 0 # (prints "how are you?") = exit 0 # (exits with code 0)
How are Functions Evaluated?
When you apply a function to an input, the result is a new function with the input "absorbed" or "incorporated" into it. You can think of the input value as being "substituted" into the function wherever the input name appears. Fexl doesn't actually use substitution, it uses combinatorics instead. Nevertheless, substitution is a very handy way of thinking about how functions are evaluated.
Let's say we have a function f defined as follows. Nevermind what it means; it's just a random example.
\f=(\x\y x 3 (y x))
That function f takes two inputs x and y and produces the result (x 3 (y x)), where the x and y are replaced with whatever you supplied as inputs.
Let's say you apply f to the inputs A and B, where A and B are any arbitrary values. Here's the reduction sequence:
: f A B = (\x\y x 3 (y x)) A B # expand f = (\y A 3 (y A)) B # substitute A for x = (A 3 (B A)) # substitute B for y
This sequence establishes that (f A B) equals (A 3 (B A)). Of course, A itself will also be a function, and the reduction sequence will continue from there.
For example, let's say A is the function (\p\q\r q r p). Then we have the sequence:
: A 3 (B A) = (\p\q\r q r p) 3 (B A) # expand A = (\q\r q r 3) (B A) # substitute 3 for p = (\r (B A) r 3) # substitute (B A) for q = (\r B A r 3) # drop left-associative parens
Note that at this point we cannot go any farther. We have reached an expression that insists on receiving an input called r. You can't go any further than this, unless you go ahead and supply a value for r. An expression that starts with an input name like this is called a normal form. For historical reasons, it is also known as a lambda expression.
The core Fexl engine doesn't actually use substitution. Instead, it uses the principle of combinatorics first devised by a hero of mine Moses Schönfinkel in a landmark 1924 paper. But you can think of Fexl as using substitution.
But since we're on the subject of combinatory logic, here it is in a nutshell. All computable functions can be defined in terms of just two primitive functions C and S, defined by the following equations:
C x y = x S x y z = (x z) (y z)
What's amazing is that this can be done without the use of variables. Any computable function you can possibly imagine can be built up by applying the functions C and S to each other in some combination.
One tiny example of this is the identity function I which we might define in Fexl as:
\I = (\x x)
But in terms of C and S we can define it without using any variables as:
\I = (S C C)
The core evaluation engine does not have to reduce everything down to C and S. It can use higher level functions which theoretically can be reduced to C and S but in practice can be evaluated in a single large step, without going through all the unnecessary motions.
Here is an example of combinator evaluation.
(Incidentally, on 2008-08-14 I found this article on alternative combinatorics which I'll have to review: The Theory of Concatenative Combinators.)
So If Everything is a Function Then What is Data?"
Always remember Rule 1: Everything is a function. This means everything, including data. You name it, it's a function.
To represent all data as functions, Fexl uses the method described in the 1989 article "Typed Representation of Objects by Functions," by J. Steensgaard-Madsen. The concept is simple once you get the hang of it, but subtle when you first see it. It is best illustrated by example. Here's a simple grocery list.
item "apples"; item "cereal"; item "toothpaste"; end
Without the semicolon feature we would would have to express the list like this:
item "apples" (item "cereal" (item "toothpaste" end))
In that expression you'll notice we use two functions called "item" and "end". The item function is defined as:
\item = (\head\tail \end\item item head tail)
The end function is defined as:
\end = (\end\item end)
You are free to use names other than "item" and "end" if you like. Usted puede usar Español si le gusta. Una rosa por otro nombre es una rosa.
Here's how the function (item H T) is reduced:
: item H T = (\head\tail\end\item item head tail) H T # expand item = (\tail\end\item item H tail) T # subst for head = \end\item item H T # subst for tail
Examining the List
To look at a list, you apply it to two "handler" functions, one to handle the end case and another to handle the item case:
list do_end do_item
Of course, you don't actually have to define named functions do_end and do_item. You can put the handler functions directly inline after the list, as parenthesized expressions. But named functions are handy for the purpose of this discussion.
The end case
So here is how (list do_end do_item) reduces when the list is empty:
: list do_end do_item = end do_end do_item # expand list = (\end\item end) do_end do_item # expand end = (\item do_end) do_item # subst for end = do_end # subst for item (not used)
So now computation proceeds with whatever do_end is.
The item case
Next, let's examine the case where the list is (item H T).
: list do_end do_item = (\end\item item H T) do_end do_item # expand list = (\item item H T) do_item # subst for end (not used) = do_item H T # subst for item
Computation now proceeds with the do_item function applied to the head H and the tail T. You would write the do_item function with two inputs to grab the head and tail. For example, you might use something like this:
\do_item=(\head\tail print_item head; print_list tail)
Now let's pick up where we left off above with (do_item H T):
: do_item H T = (\head\tail print_item head; print_list tail) H T # expand do_item = (\tail print_item H; print_list tail) T # subst for head = print_item H; print_list T # subst for tail
We have now determined that (list do_end do_item) equals (print_item H; print_list T).
Example of a Function that Does Something with a List
Let's look at how the print_list function might be defined:
\print_list=(\list\next list next \head\tail
print_item head;
print_list tail;
next)
This function says that if the list is empty, simply proceed with whatever is next. But if the list has a head and tail, print the head item and then print the remaining list.
Here is how the print_list function might be used:
print_list (item 1; item 2; item 3; end); exit 0
Let's look at how this function reduces:
: print_list (item 1; item 2; item 3; end); exit 0
# First remove the ';' notation to make the functional structure very obvious.
= print_list
(item 1 (item 2 (item 3 end))) (exit 0)
# Now replace print_list with its definition.
= (\list\next list next
\head\tail
print_item head;
print_list tail;
next)
(item 1 (item 2 (item 3 end))) (exit 0)
# Substitute for the list input.
= (\next (item 1 (item 2 (item 3 end))) next
\head\tail
print_item head;
print_list tail;
next)
(exit 0)
# Substitute for the next input.
= (item 1 (item 2 (item 3 end))) (exit 0)
\head\tail
print_item head;
print_list tail;
exit 0
# For clarity, let's put parentheses around the lambda expression (\head\tail ...).
# We can do this because the scope of a lambda expression always extends as far
# right as possible.
= (item 1 (item 2 (item 3 end))) (exit 0)
(\head\tail
print_item head;
print_list tail;
exit 0)
# Remove unnecessary parentheses around the first function.
= item 1 (item 2 (item 3 end)) (exit 0)
(\head\tail
print_item head;
print_list tail;
exit 0)
# Substitute the definition of the item function at the front, then
# go ahead and reduce that to its normal form.
= (\end\item item 1 (item 2 (item 3 end))) (exit 0)
(\head\tail
print_item head;
print_list tail;
exit 0)
# Substitute (exit 0) for the end input, which is not used.
= (\item item 1 (item 2 (item 3 end)))
(\head\tail
print_item head;
print_list tail;
exit 0)
# Substitute the entire (\head\tail ...) for the item input.
= (\head\tail
print_item head;
print_list tail;
exit 0)
1 (item 2 (item 3 end))
# Substitute for the head input.
= (\tail
print_item 1;
print_list tail;
exit 0)
(item 2 (item 3 end))
# Substitute for the tail input.
= print_item 1;
print_list (item 2 (item 3 end));
exit 0
# Now it's obvious we're on the right track. We're going to print the first item 1,
# then print the remainder of the list (item 2; item 3; end), and finally exit with
# code 0.
Now that may seem like a lot of work to you, but it is incredibly fast when a computer does it.