Fexl

You can now download or peruse the Clump source code at github. I'll keep the old download link alive for a while, but that will soon be obsolete.

Loom

Fexl

The name "Fexl" (pronounced Fex' - il) 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.

Fexl may one day become a powerful and secure basis for executable content on the internet. I believe it has advantages over XML and Java. XML is merely a nice file format with a growing body of standard functions and tools. There's a lot to be said for that, but I think Fexl can go further because it provides a mechanism for defining and communicating those functions and tools. Java is a nice try, but I think Fexl is leaner, cleaner, and meaner.

Note: If you want to skip all this detail just go directly to the Fexl Summary.

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.

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.

Fexl uses a very simple, elegant, and powerful model of side effects. A Fexl "program" is, quite simply, a function of the world which yields a new world as its value. But through the use of what are often called "monadic" techniques you can a program in such a way that you never explicitly mention the "world" as a named value, and you don't have to chain the state of the world from function to function. It sounds complicated but the bottom line is you can say ordinary procedural things like this:

        print "Hello, world\n";
        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. You can even pass in a purely functional model of the "world" which saves the output from "print", returns specific test values for "getline", and counts the number of times "beep" was called. And of course "exit" can be defined however you like, for example to show a summary of the final "world" value after the program is run.

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.

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 general idea of course is to do only the low-level stuff in C and do all the really serious application logic in Fexl. If you find a performance bottleneck, you might consider coding just that part in C.

What would be the point? C and Perl already absolutely rule at what they do. Fexl has to be different.

A function is something that is applied to an argument to produce a value. You take a function f, apply it to an argument x, and it produces a value y.

For example, you might apply a function called twice to the argument 7, producing the value 14:

Actually, all functions take only one argument. The add function only appears to take two arguments. In reality, you are applying add to 3, and this yields the value (add 3). The (add 3) function is the function that adds 3 to whatever argument you give it. So the next step is to apply (add 3) to the argument 5. This yields the value 8.

The expression add 3 5 is actually ((add 3) 5) if you show all the parentheses. This form makes it clear that we are applying the function (add 3) to the argument 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

As it turns out, the pivoting semicolon neatly expresses the notion of sequentiality so common in procedural programming. For example:

        print "hello"; print "how are you?"; exit 0

        print "hello" (print "how are you?" (exit 0))

This 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)

When you apply a function to an argument, the result is a new function with the argument "absorbed" or "incorporated" into it. You can think of the argument value as being "substituted" into the function wherever the argument name appears. However, in reality Fexl does not 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):

This function f takes two arguments x and y and produces the result x 3 (y x), where the x and y are replaced with whatever you supplied as arguments. (Note: for historial reasons, an expression that starts off with an argument such as "\x ..." is known as a lambda expression).

Let's say you apply f to the arguments 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 is equivalent to 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 \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 argument r. You can't go any further than this, unless you go ahead and supply something for r. An expression that starts with a parameter like this is called a normal form.

As it turns out, 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. As it turns out, 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 (typically dizzying) combination.

One tiny little example of this is the identity function I which we might define in Fexl as:

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.

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 very simple once you get the hang of it, but very subtle when you first see it.

The method is best illustrated by example. Here is how we represent lists as functions.

A list is just a sequence of one or more items of any kind. The list [1,2,3] is the sequence of numbers 1, 2, and 3. The list ["apples","cereal","toothpaste"] might be somebody's grocery list. The list ["apples"] is a very short grocery list consisting of just one item. The list [] is completely empty; we call this the null list.

Notice that any non-null list can always be broken down into two pieces, which we call the head and tail. The head is the first element of the list. The tail is the list of elements after the head.

For example, the head of the list ["apples","cereal","toothpaste"] is "apples" and the tail is ["cereal","toothpaste"].

Therefore, a non-null list can be represented as cons H T, where H is the head and T is the tail. (The name "cons" is a historical artifact from the Lisp language, and is derived from the verb "construct.")

Using the cons and null functions, here is what the grocery list looks like:

        cons "apples" (cons "cereal" (cons "toothpaste" null))

        cons "apples"; cons "cereal"; cons "toothpaste"; null

        \null=(\null\cons null)
        \cons=(\head\tail\null\cons cons head tail)

        :   cons H T
        =   (\head\tail\null\cons cons head tail) H T     # expand cons
        =   (\tail\null\cons cons H tail) T               # subst for head
        =   \null\cons cons H T                           # subst for tail

So the normal form of a list is either \null\cons null or \null\cons cons H T.

To look at a list, you apply it to two "handler" functions, one to handle the null case and one to handle the cons case:

        List handle_null handle_cons

        :   List handle_null handle_cons
        =   null handle_null handle_cons                    # expand List
        =   (\null\cons null) handle_null handle_cons       # expand null
        =   (\cons handle_null) handle_cons                 # subst for null
        =   handle_null                                     # subst for cons (not used)

        :   List handle_null handle_cons
        =   (\null\cons cons H T) handle_null handle_cons   # expand List
        =   (\cons cons H T) handle_cons                    # subst for null (not used)
        =   handle_cons H T                                 # subst for cons

Computation now proceeds with the handle_cons function applied to the head H and the tail T. You would write the handle_cons function with two arguments to "grab" the head and tail. For example, you might use something like this:

        \handle_cons=(\head\tail print_item head; print_list tail)

        :   handle_cons H T
        =   (\head\tail print_item head; print_list tail) H T   # expand handle_cons
        =   (\tail print_item H; print_list tail) T             # subst for head
        =   print_item H; print_list T                          # subst for tail

So, to summarize, evaluating (List handle_null handle_cons) turned out to be equivalent to evaluating (print_item H; print_list T).

This example uses null and cons to represent lists. However, because lists are so common in programming (and life, for that matter), Fexl does support the ordinary list notation [1,2,3]. Keep in mind though that the list [1,2,3] is equivalent to cons 1 [2,3]. Also, the list [2,3] is equivalent to cons 2 [3]. Also, the list [3] is equivalent to cons 3 []. And finally, the list [] is equivalent to null.

        \print_list=(\list\next list next \head\tail
            print_item head; print_list tail next)

Essentially, this function says that if the list is null, simply proceed with whatever is next. If the list has a head and tail, print the head item and then print the tail list.

        print_list [1,2,3]; exit 0

        :   print_list [1,2,3]; exit 0
        
        # First let's get rid of the ';' to make the functional structure very obvious.
        
        =   print_list [1,2,3] (exit 0)
        
        # Now replace print_list with its definition.
        
        =   (\list\next list next \head\tail print_item head; print_list tail next)
                [1,2,3] (exit 0)
        
        # Substitute [1,2,3] for list.
        
        =   (\next [1,2,3] next \head\tail print_item head; print_list tail next) (exit 0)
        
        # Substitute (exit 0) for next.
        
        =   [1,2,3] (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.
        
        =   [1,2,3] (exit 0) (\head\tail print_item head; print_list tail; exit 0)
        
        # Replace the list [1,2,3] with the equivalent form (cons 1 [2,3]).
        
        =   cons 1 [2,3] (exit 0) (\head\tail print_item head; print_list tail; exit 0)
        
        # Replace cons 1 [2,3] with its normal form (\null\cons cons 1 [2,3]).
        
        =   (\null\cons cons 1 [2,3])
                (exit 0) (\head\tail print_item head; print_list tail; exit 0)
        
        # Substitute (exit 0) for the null parameter (which is not used).
        
        =   (\cons cons 1 [2,3]) (\head\tail print_item head; print_list tail; exit 0)
        
        # Substitute (\head\tail print_item ...) for the cons parameter.
        
        =   (\head\tail print_item head; print_list tail; exit 0) 1 [2,3]
        
        # Substitute 1 for the head parameter.
        
        =   (\tail print_item 1; print_list tail; exit 0) [2,3]
        
        # Substitute [2,3] for the tail parameter.
        
        =   print_item 1; print_list [2,3]; exit 0
        
        # Now it's obvious we're on the right track.  We're going to print the first item 1,
        # print the remainder of the list [2,3], and then exit with a code of 0.

Author:	Patrick Chkoreff PGP Key
Email:	0ca355c7@fexl.com