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.

Enjoy Clump!

Fexl™ is a brand new programming language. It is not quite ready for release yet, but it's getting closer.

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 Quick Summary.

Last updated 2002-11-09 03:29:00 EST (GMT-5). Fexl now has a logo.

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.

The Basics

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.

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.

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

Why Isn't Fexl More Conventional, Like C or Perl?

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

How Do Functions Work?

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.

        f x = y
      

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

        twice 7 = 14
      

You can also have functions that take more than one argument:

        add 3 5 = 8
      

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
      

If we removed the pivoting semicolons from this function, we would have:

        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)
      

What is Substitution?

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

        \f=(\x\y x 3 (y x))
      

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.

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

Or we could use the semicolon to get rid of the parentheses:

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

Without further ado, here are the definitions of null and cons:

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

Any list will be one of two forms: null or cons H T.

The null list is simply this function:

        \null\cons null
      

The non-null list cons H T is this function:

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

Examining the List

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
      

The null case

First, let's examine the case where List is null.

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

So now computation proceeds with whatever handle_null is.

The cons case

Next, let's examine the case where List is cons H T.

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

Now let's pick up where we left off above with handle_cons H T:

        :   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).

Fexl Does Have a Convenient List Notation

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.

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)
      

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.

Here is how the print_list function might be used:

        print_list [1,2,3]; exit 0
      

Now let's take a very detailed look at how this is evaluated:

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