Fexl (Function EXpression Language) http://fexl.com

AUTHOR

Patrick Chkoreff wrote this software.  Please see the NOTICE file for terms of
use.


CREDITS

I thank Moses Schönfinkel, who in 1924 wrote a paper titled "On the building
blocks of mathematical logic".  I found this paper in "From Frege to Gödel, A
Source Book in Mathematical Logic, 1879-1931".

Mr. Schönfinkel observes that all computable functions can be defined in terms
of just two primitive functions C and S applied together in various
combinations.  This is a profound and magnificent insight for which I am very
grateful.

The C function is governed by the rule ((C x) y) = x.  This is known as the
"constancy function", or "Konstanzfunktion" in the original German.

The S function is governed by the rule (((S x) y) z) = ((x z) (y z)).  This is
known as the "fusion function", or "Verschmelzungfunktion" in the original
German.

I also thank Jørgen Steensgaard-Madsen, who in 1989 wrote a paper titled
"Typed Representation of Objects by Functions".  I found this paper in the
"ACM Transactions on Programming Languages and Systems, January 1989, Volume
11 Number 1".

Mr. Steensgaard-Madsen observes that all of what we ordinarily understand as
"data" can be represented as pure functions.  Even a piece of data as humble
as a single bit is in essence just a function.


HOW TO INSTALL

Run this command:

  ./build install

That creates /usr/bin/fexl, /usr/lib/fexl, and /usr/share/fexl.  You may be
prompted for your sudo (superuser) password during this process.

Note that you should NOT preface the command with "sudo", because you don't
want to create the local build objects with root permissions.

If you need to install into a different place, change the dir_install
variable inside the build script.


HOW TO BUILD LOCALLY

If you wish to enhance or test the program, you might prefer to build it
locally in the bin directory and run it from there, without installing into
/usr/bin.  You do that with this command:

  ./build


HOW TO RUN

To run a fexl program which is read from standard input:

  fexl

To run a fexl program which is read from a file named "script":

  fexl script

You may also use the "shebang" method to create an executable fexl file.  For
example, create a file named "script" and put this on the first line:

  #!/usr/bin/fexl

Then make your script executable with:

  chmod +x script

Now you can run your script directly this way:

  ./script


HELPFUL INFORMATION

On 2012-04-03 a colleague asked:  "Is there a collection of short Fexl programs
that can be used as a guide of sorts of learning the language?"  Here's my
reply.

Thanks for asking -- actually there's a collection of not-so-short programs
which I use as regression tests:

	test/a1.fxl
	test/a2.fxl
	test/a3.fxl
	test/a4.fxl

In the shell, I do a ". alias" to read in some handy shell functions, and then
I can run my tests like this:

	.run a1    # to run a1.fxl and see the output
	.check a1  # to diff the output against a1.out
	.time a1   # to diff the output *and* time the run

(Those are nice because they automatically run "build" on fexl itself so I can
hack the C code and immediately check my test cases without thinking about re-
building.)

However, the problem with those programs as a tutorial is that I'm deliberately
testing all sorts of intricate stuff, so it's very programmer-geeky.

I suppose one could start with this:

	print "Hello world."; nl;
	\x = (+ 4 3)
	\x = (* x 5)
	print "x = "; print x; nl;

Maybe you'll find that "multiplying by 5" is something you do a lot, so you can
define a function like this:

	\quintuple = (\x * x 5)

Or, if you cleverly fancy the "point free" style:

	\quintuple = (* 5)


And then you can say:

	print "Hello world."; nl;
	\x = (+ 4 3)
	\x = (quintuple x)
	print "x = "; print x; nl;


Or even:

	print "Hello world."; nl;
	print "x = "; print (quintuple (+ 4 3)); nl;

Note by the way that ';' is just the "right-pivot" operator which allows you to
avoid many parentheses when grouping things on the right.  For example, instead
of this:

	(+ 2 (+ 3 (+ 5 (+ 7 (+ 11 13)))))

You can say this:

	(+ 2; + 3; + 5; + 7; + 11 13)

It's mostly a matter of style, though in same cases it's obvious you should use
';' and in other cases it's obvious you shouldn't because you've pushed it too
far.


Now since you're a highly experienced programmer with a strong intuition
about things, let me fast-forward to a few functions which deal with lists:

	\append == (\xs\ys xs ys \x\xs item x; append xs ys)

	\map == (\f\xs xs end \x\xs item (f x) (map f xs))

	\fold == (\f\z\xs xs z \x\xs \z=(f z x) fold f z xs)

Note the use of "==" because those are recursive definitions.  When you define
a function that refers to itself, you must use "==".  If you mistakenly use "="
like this:

	\my_append = (\xs\ys xs ys \x\xs item x; my_append xs ys)

You'll get an error message "Undefined symbol my_append" because Fexl thinks
you're trying to redefine my_append in terms of the *previous* definition of
my_append, which of course does not exist.


Now consider some Boolean operators:

	\and  = (\x\y x y F)
	\or   = (\x\y x T y)
	\not  = (\x x F T)

	\xor  = (\x\y x (not y) y)
	\xnor = (\x\y x y (not y))


Now what if you need functions that operate on a list of booleans, reducing
the list with either "and" or "or":

	\list_and = (fold and T)
	\list_or  = (fold or F)


It's also handy to have functions like this:

	\all = (\f\xs list_and (map f xs))
	\some = (\f\xs list_or (map f xs))


So you can say:

	all good list (print "all good!") (print "some bad!")

or equivalently:

	some bad list (print "some bad!") (print "all good!")

Note that these are all built into the standard share/fexl/main.fxl which comes
with the distribution.


I'm finding that Fexl is an open-ended scratch-pad for computation which allows
me to refactor and compress code down to its incompressible essence.  The
process is challenging, but also rewarding because the result can be like a
diamond of conceptual thought.

For example, I can capture the "ultimate essence" of the Fibonacci series like
this:

	# This is the infinite list of all Fibonacci numbers.
	\fibonacci =
		(\1\add

		\fibonacci ==
			(\x\y
			item x;
			\z = (add x y)
			fibonacci y z
			)

		fibonacci 1 1
		)

Note that you *pass in* the definitions of "1" and "add" there.  That allows
you to define fibonacci either in terms of built-in long numbers like this:

	\fibonacci = (fibonacci 1 long_add)

Or in terms of unlimited precision natural numbers like this:

	\fibonacci = (fibonacci nat_1 nat_add)

In fact, when you do this:

	.run a2

You will see a long series of high-precision Fibonacci numbers produced.


I trust that this will serve as a decent top-level introduction and survey of
the possibilities.