Fexl

The Clump program is a handy tool for all you C programmers tired of makefiles.

A lot of people have been downloading clump lately. Evidently clump is doing its job, saving programmers many hours of their precious time on earth!

Fri 2006-10-20: Version 06 is now available. This fixes a tiny compilation problem caused by a slightly different system header file on Linux ("dirent.h"). This is the first change in clump since it was first published on 2003-12-17.

I'm pleased to see that good old version 06 is still being downloaded, even after all these years.

Loom

You need "usage tokens" to do anything there, and the only way to get usage tokens is from someone who is already using the system. In effect, you must be invited. This is good because it means the system is economically self-regulating.

The web interface at loom.cc has obviously been designed for the simplest movement of assets with the fewest possible keystrokes and clicks. I believe that it is optimal when measured purely in terms of time and motion.

What's interesting is that the web interface you see there is merely an add-on product. It is built on top of a very solid API which is the real heart and soul of the server. In fact, the entire web interface could be stripped away, leaving only the API running on the server. You could run the interface on another server or even your own local machine. Moreover, you are free to write your own interfaces if you have the skill and inclination.

When you click over to loom.cc you go directly to the Login screen. That's because loom.cc is "all business" and it's about getting in and doing the job. But if you click over to the "Home" page you will see several links, including documentation for the "Grid API" which is where the rubber meets the road.

So what's it all about? It warrants further explanation. I'll be writing about it here, so check back in a few days.

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.

Updated 2002-11-07 14:17:00 EST (GMT-5). Extended the discussion of concurrency, modularity, "here-is" documents, and embedded applications. Also cleaned up the print_list example a bit.

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.

Traditionally the word "function" means an operation without side effects and the word "procedure" means an operation with side effects. In Fexl we just use the word "function" for everything and simply say that some functions have side effects and some don't.

Although a computer program must have side effects in order to be at all useful, side effects cause problems when you try to use a function for anything other than its originally intended purpose. You often discover that the function is good for only one specific purpose and cannot be used for anything else.

Fexl is known as a "high-order" programming language. In layman's terms this means you can easily lift the side effects out of a function to make it reusable and portable. When you want to use the function for a specific purpose, you simply "plug in" whatever side effects you want. To use the function for a different purpose, just plug in different side effects.

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. This happens by the mechanism of substitution.

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:	fb2122dc@fexl.com