Fexpr

Fexpr is a noun.  It's pronounced FEKSper.  A fexpr is a procedure that acts on the syntax of its operands, rather than on the values determined by that syntax.

This is only in the world of Lisp programming languages — not that only Lisps happen to have fexprs, but that having fexprs (and having the related characteristics that make them a really interesting feature) seemingly causes a programming language to be, at some deep level, a dialect of Lisp.  That's a clue to something:  although this acting-on-syntax business sounds superficial, it's a gateway to the deepest nature of the Lisp programming-language model.  Fexprs are at the heart of the rhyming scheme of Lisp.

Data as programs

When Lisp reads a syntax (i.e., source code) expression, it immediately represents the expression as a data structure; or at least, in theory it does.  For fexprs to even make sense, this would have to be true:  a procedure in a program acts on data, so if you're passing the operand syntax expressions to a procedure, those expressions have to be data.  The Lisp evaluator then interprets the syntax expression in data form, and that's the whole of Lisp:  read an expression and evaluate it, read another and evaluate it, and so on.

But Lisp was designed, from the start, specifically for manipulating an especially simple and general kind of data structures, essentially trees (though they can also be viewed as nested lists, hence the name of the language, short for LISt Processing).  And syntax expressions are represented as these same trees that are already Lisp's native data structure.  And, the Lisp evaluator algorithm isn't limited to data that started life as a representation of syntax:  any data value can, in principle, be evaluated.  Which means that a fexpr doesn't have to act on syntax.

The theory of fexprs

One reason it matters that fexprs can act on non-syntax, is because of a notorious theoretical result about fexprs.  Proving programs correct usually makes heavy use of determining whether any two source expressions are interchangeable.  When two source expressions may be operands to a fexpr, though, they won't be interchangeable in general unless they're syntactically identical.  So with fexprs in the language, no two distinct operands are ever universally interchangeable.  This was famously observed by Mitch Wand in a journal article back in 1998, The Theory of Fexprs is Trivial.

But while a fexpr can analyze any syntactic operand down to the operand's component atoms, computed operands are a different matter.  It's almost incidental that some computed data structures are encapsulated, so can't be fully analyzed by fexprs.  The more important point is, even if the structure resulting from computation can be fully analyzed, the process by which it was computed is not subject to analysis.  If a fexpr is given an operand 42, the fexpr can't tell how that operand was arrived at; it might have been specified in source code, or computed by multiplying 6 times 7, or computed in any of infinitely many other possible ways.

So, suppose one sets up a computational calculus, something like lambda-calculus, for describing computation in a Lisp with fexprs.  Source expressions are terms in the calculus, and no two of them are contextually equivalent (i.e., interchangeable as subterms of all larger terms).  But —unless the calculus is constructed pathologically— there are still very many terms in the calculus, representing intermediate states of subcomputations, that are contextually equivalent.

I've developed a calculus like that, by the way.  It's called vau-calculus.

Deep fexprs

We're about to need much better terminology.  The word fexpr is a legacy from the earliest days of Lisp, and procedure is used in the Lisp world with several different meanings.  Here's more systematic terminology, that I expanded from Scheme for use with the Kernel programming language.

A list to be evaluated is a combination; its first element is the operator, and the rest of its elements are operands.  The action designated by the operator is a combiner.  A combiner that acts directly on its operands is an operative.  (Legacy terms: an operative that is a data value is a fexpr, an operative that is not a data value is a special form.)  A combiner that isn't operative is applicative; in that case, the operands are all evaluated, the results of these evaluations are called arguments, and the action is performed on the arguments instead of on the operands.

It might seem that applicative combinations would be more common, and far more varied, than operative combinations.  Explicitly visible operatives in a Lisp program are largely limited to a small set, used to define symbols (in Kernel, mainly $define!  and $let), construct applicatives ($lambda), and do logical branching ($if  and $cond) — about half a dozen operatives, used over and over again.  The riotous variety of programmer-defined combiners are almost all applicative.

But looking closely at the above definition of applicative, it implies that every applicative has an operative hiding inside it.  Once an argument list has been computed, it's just another list of data values — and those values are then acted on directly with no further processing, which is what one does when calling an operative!  Applicative +, which evaluates its operands to arguments and then adds the arguments, has an underlying operative that just adds its operands; and so on.

Vau-calculus

In a computational calculus for fexprs, it's a big advantage to represent each applicative explicitly as a wrapper (to indicate the operands are to be evaluated) around another underlying combiner.  That way, the calculus can formally reason about argument evaluation separately from reasoning about the underlying actions.  Vau-calculus works that way.  The whole calculus turns out to have three parts.  There's one part that only represents tree/list structures, and no computation takes place purely within that part.  There's one part that only deals with computations via fexprs.  And then, linking those two, there's the machinery of evaluation, which is where the wrapper-to-induce-operand-evaluation comes in.

Fascinatingly, of these three parts of vau-calculus, the one that deals only with computations involving fexprs is (give or take) lambda-calculus.  One could reasonably claim —without contradicting Mitch Wand's perfectly valid result, but certainly contrasting with it— that the theory of fexprs is lambda-calculus.

(Vau-calculus seems a likely topic for a future blog entry here.  Meanwhile, if you're really feeling ambitious, the place to look is my dissertation.)

[Note:  I've since blogged on vau-calculus here.]

Kernel

What works for a computational calculus also works for a Lisp language:  represent each applicative as a wrapper around an underlying combiner.  The Kernel programming language does this.  An applicative unwrap  takes an applicative argument and returns the underlying combiner of that argument; and an applicative wrap  takes any combiner at all as an argument, and returns an applicative whose underlying combiner is that argument.

This makes Kernel a powerful tool for programmers to fluently manipulate the operand-evaluation process, just as the analogous device in vau-calculus allows reasoning about operand-evaluation separately from reasoning about the underlying lambda-calculus computations.

Kernel (evaluator)

Here's the central logic of the Kernel evaluator (coded in Kernel, then put in words).

($define! eval
   ($lambda (expr env)
      ($cond ((symbol? expr)  (lookup expr env))
             ((pair? expr)
                (combine (eval (car expr) env)
                         (cdr expr)
                         env))
             (#t  expr))))

($define! combine
   ($lambda (combiner operands env)
      ($if (operative? combiner)
           (operate combiner operands env)
           (combine (unwrap combiner)
                    (map-eval operands env)
                    env))))

To evaluate an expression in an environment:  If it's a symbol, look it up in the environment.  If it's a pair (which is the more general case of a list), evaluate the operator in the environment, and combine  the resulting combiner with the operands in the environment. If it's neither a symbol nor a pair, it evaluates to itself.

To combine a combiner with an operands-object:  If the combiner is operative, cause it to act on the operands-object (and give it the environment, too, since some operatives need that).  If the combiner is applicative, evaluate all the operands in the environment, and recursively call combine  with the underlying combiner of the applicative, and the list of arguments.

Kernel (fluently doing nothing)

When evaluating syntax read directly from a source file, the default case of evaluation —the one explained in boldface— is why a literal constant, such as an integer, evaluates to itself.  What makes it worth boldfacing, though, is that when evaluating computed expressions, that case helps keep environments from bleeding into each other (in Lisp terminology, it helps avoid accidental bad hygiene).  Here's a basic example.

Lisp apply  overrides the usual rule for calling an applicative, by allowing a single arbitrary computation-result to be used in place of the usual list of arguments.  The first argument to apply  is the applicative, and its second argument is the value to be used instead of a list of arguments.  In Kernel, and then in words:

($define! apply
   ($lambda (appv args)
      (eval (cons (unwrap appv) args)
            (make-environment))))

To apply an applicative to an args-object, construct a combination whose operator is the underlying combiner of the applicative, and whose operands-object is the args-object; and then evaluate the constructed combination in a freshly created empty environment.  When the constructed combination is evaluated, its operator evaluates to itself because it's a combiner.  This defaulting operator evaluation doesn't need anything from the environment where the arguments to apply  were evaluated, so the constructed combination can be evaluated in an empty environment — and the environment of the call to apply  doesn't bleed into the call to the constructed combination.

In a standard Kernel environment, (apply list 2) evaluates to 2.

A more impressive illustration is the way $lambda  can be defined hygienically in Kernel using more primitive elements of the language.  I should make that a separate post, though.  The earlier parts of this post deliberately didn't assume Lisp-specific knowledge at all, and in the later parts I've tried to ease into Lisp somewhat gently — but $lambda  gets into a whole nother level of Lisp sophistication (which is what makes it a worthwhile example), so it just feels logically separate.

[Note: I did later post on Kernel hygiene and $lambda, here.]

Memetic organisms

When Richard Dawkins coined the word meme (back in 1976, in The Selfish Gene — a must read), I suggest he made one understandable mistake, an oversight that, as far as I can tell, has lingered ever since.  It might even explain why memetics hasn't become a viable field of scientific research.

A meme is roughly an idea that makes copies of itself, which compete with copies of other memes for available resources (basically, human hosts).  When a class of things self-copy and compete, they evolve; Dawkins used the general term replicators for any such things.  Genes are replicators, and he used memes as a second example of replicators, showing that the concept has some generality to it.  All good so far, but he also wrote that this second kind of replicator was "still in its infancy, still drifting clumsily about in its primeval soup".

Um, no.  It's very easy to think that, because the world that memes inhabit —the ideosphere— isn't directly visible to our senses.  Ask yourself, if the memetic equivalent of a tyrannosaurus were (metaphorically) standing right next to you, how would you know?

Memes are, I suggest, nowhere near the primeval-soup stage.  For thousands of years, memetic organisms have roamed the earth, with reproduction (as opposed to replication), death of individual organisms, inactive memes, and something like differentiated organs.  You are surrounded, at this moment, by memetic organisms.

What's an organism?

Some large groups of memes get copied together; the name memeplex  has been been suggested for such groups.  Astrology, say, or algebra.  But a biological organism isn't just a set of genes — it is, as Dawkins put it, a vehicle for genes.  The replicators have evolved the trick of building these vehicles for themselves.  Here are some things to expect of any kind of organisms.

• Each organism carries a reasonably stable set of replicators, some of which influence the organism's fitness.
• Organisms reproduce.  A child is created by a process involving one or more parents, from which the child inherits many (most?) of the replicators it carries.
• Organisms die.  When they do, some of the replicators they carried may be carried on by their descendants.
• Replicators with the potential to induce certain organism traits may be carried by organisms that don't exhibit those traits.  (Both recessive genes and junk genes spring to mind.)

So, when looking for memetic organisms, we want a class of entities that carry sets of memes; that exhibit reproduction and death, inheriting from their parent(s) and so preserving memes from deceased ancestors; and that carry along some memes across generations in some sort of "inactive" form.

Seeing a memetic organism

In 1994, there was much fanfare about the twenty fifth anniversary of the first moonwalk.  Footage of astronauts on the moon was replayed on television.  In one of these clips, an astronaut stood on the moon and did the classic experiment of dropping a light object and a heavy object to see if the heavy object fell faster.  (A feather and a wrench, I think they were.)  It wasn't well controlled; the point was evidently public education about science, for which it was preceded by a verbal explanation of the experiment — so it taught about scientific method as well as about universal gravitation.  Great stuff.

What left my jaw hanging was that the explanation started with (iirc) "Aristotle said".  Nobody was supposed to believe Aristotle's theory about falling objects, but this guy on the moon was deliberately teaching the general public about what they weren't supposed to believe.  Inherited memes systematically preserved in a sort of "inactive" form.

Thomas Kuhn described some aspects of this species of memetic organisms in 1962, in The Structure of Scientific Revolutions (another must read).  Notably, he described its reproductive process, which is what he called a scientific revolution.  Here's a rough portrait of a paradigm scientific field as a memetic organism.

The meme set carried by the organism includes a mass of theories, some of which contradict each other.  At the center of this mass is a nucleus of theories that are supposed to be believed (part of what Kuhn called a paradigm).  Surrounding the nucleus are theories that are meant to be contrasted with the paradigm and rejected, together with memes about how to conduct the contrast; one might call this surrounding material the co-nucleus.  While the organism thrives, the contrast with the co-nucleus strengthens belief in the nucleus, thus recruiting and retaining members of the organism's scientific community.  When the organism falters (the scientific community loses faith in the paradigm), eventually a new paradigm emerges, forming the nucleus of a new organism, while the new co-nucleus may contain both some nuclear and some co-nuclear material from the parent(s).

During reproduction, fragments may be drawn for the new nucleus (as "inspiration") from pretty much anywhere, even from non-sciences.  It seems that a thriving science may deliberately surround itself with a sort of third ring of memes, outside the co-nucleus and perhaps somewhat loosely coupled with the science itself (symbiotic?), that provide raw material for new co-nuclear or nuclear formations.  This third ring may include alternative, pseudo-, and fringe science; and science fiction, which can provide a venue for scientists within the community to explore new ideas without the ridicule or ostracism that would result if they prematurely proposed the same ideas in a scientific forum.

[I am, btw, not only let down but also rather fascinated, to find my memory of the moonwalk gravity demo does not match the footage I've found on YouTube [link]; besides being a hammer rather than a wrench, this footage doesn't have the explanation, nor the name Aristotle, that waxes so prominent in my recollection.  Either what I'm remembering is dominated by the epiphany I had while watching it rather than what was shown, or, not impossibly, there could be other footage floating around, either from a separate incident or (less expensively) with some sort of dubbed-over narration.]

Second example

Religion seems to be a second species (or genus, or some taxon anyway) of memetic organisms.  I may do even more poorly here, as I'm practically unread on comparative religion, but I'll take a stab at it anyway; hopefully, it will suffice to make the taxon plausible, even if my specific suggestions don't hold up at all.

The best fit for an organism seems to be below the scale usually called a sect, though conceivably somewhat above the scale of a congregation.  Part of the carried memetic material is a large mass I'll call a religious tradition, which may be written or oral.  The tradition is augmented by further memes, which I'll call an interpretation, determining what different parts of the tradition are supposed to mean.  The tradition and interpretation should be able to recruit and retain followers.  When changing societal environment makes those memes less effective, it becomes increasingly likely that the community will either splinter, or adjust its carried meme set, creating a new organism with perhaps some deletions or even additions to the tradition, but especially, changes to the interpretation that make it work better in the societal environment.

What makes for a successful religious organism?  A successful scientific organism features highly persuasive contrast between nucleus and co-nucleus, and there is presumably some of that in the religious case too, practices of other religions preserved as persuasive examples of what not to do; likely the scientific species is partly descended from the religious.  But there is also an interesting implication from the suggested religious model, that over many generations, a religious tradition will evolve to be amenable to a very wide range of interpretations, as this will allow the tradition to facilitate successful reproduction in a wide variety of societal environments.  A successful tradition would therefore be an ambiguous one.

Can memetics become a normal science?

There seem to be two problems with memetic research that have held it back.

One is that efforts in memetics have been dominated for decades by attempts to define what a meme is.  The definition of gene was arrived at after extensive study of biological organisms; so presumably, one should expect extensive study of memetic organisms to be a prerequisite for arriving at a really good definition of meme.  Identifying the organisms is a start.

The other has to do with what Kuhn called normal scientific research.  This is the sort of research that takes place within a paradigm scientific field (a thriving scientific organism, that is).  The paradigm usefully constrains the sorts of questions scientists are to ask and the sorts of answers they are to give (a nuance I didn't even try to capture in my rough portrait of scientific organisms, above).  Kuhn describes such research as "puzzle solving", and its narrow focus is its strength, allowing a very great deal of focused work to be done so that, eventually, flaws lurking in the paradigm become impossible to ignore and a reproductive event is triggered — a scientific revolution, shifting things to another paradigm better describing reality.

But memetics hasn't provided that sort of structure.

There seems to be some potential, in the ideas I've proposed here, to define how memetic organisms are to be identified and analyzed, sufficiently that researchers might proceed methodically to find and study organisms.  In other words, these suggestions might be developed into a functioning paradigm that could guide normal scientific research.

Maybe.

Prosaic first post

A favorite quote of mine is "History doesn't repeat itself, but it rhymes."  Attributed to Mark Twain, though I see Wikiquote says "Twain scholars agree that it sounds like something he would say, but they have been unable to find the actual quote in his writing."  Quote attributions are like that: them as has, gets.

The thing is, it doesn't just work for history.  It [works] for pretty much everything — if you're familiar enough with it to recognize the rhyming scheme.  For example, I've enough smattering of past and present physics to recognize when science fiction has an especially good, or bad, sense of its rhyming scheme.  Vernor Vinge's A Fire Upon the Deep has the most elegantly rhymed fictional physics I've ever encountered; and I've read SFF authors with no ear for physics at all, though I'll not name names.  On the non-fiction side of the same effect, I've long sensed that Albert Einstein's dissatisfaction with quantum mechanics was, at its most primordial, dislike of its rhyme (not to in any way disparage his more specific metaphysical writings on the subject).

So I gradually accumulate evidence, fodder for my intuition, and over years and even decades my intuition slowly learns to recognize rhymes, and starts answering me back with insights — into the rhyming structure of the various subjects of study, hence the blog title.  And the insights more or less gather dust, in my files or even just in my head.  I'm starting a blog to put those insights out in the open where, with luck, maybe one way or another some will be useful to someone besides me.  (If folks find them laughable, well, laughter is good exercise, so that's useful too.)

What have I been studying, that I can blog about?  Well, there's linguistics; both programming languages (within which is my academic expertise), natural and constructed languages, and connections between all three.  Mathematical physics.  A dash of magic.  Memetics, with both religion and science as subs under it.  Politics and economics.  And whatever else I'm forgetting (or haven't thought of yet).