Logical Joy

I came across Joy again recently. I've stumbled across it a few times over the years, but this time I finally understood the distinction that the Joy FAQ makes between compositional and applicative languages. So I decided to play around with making a Joy version for the Inverted Index Language Shootout. For example, here's a Joy function to remove all duplicate elements in a list:

(* Removes duplicate elements in a list.  The name "nub" comes from the 
   function of the same name in haskell.  This implementation is O(n^2) *)
nub ==  
        [] swap         (* the accumulator for step begins as an empty list *)
        [ [swap in]     (* if the current element is already in the list, *)
          [pop]         (* ignore it *)
          [swons]       (* otherwise add it to the list *)
          ifte]
        step;           (* repeat for each element in the input list *)

The conciseness of the language is more impressive (and opaque) if you remove the comments:

nub == [] swap [[swap in] [pop] [swons] ifte] step;

Unfortunately, the reason that the language is so concise is because it avoids all use of variables. This has two main effects in terms of writing programs in Joy. First, the order of arguments to a function strongly impacts the implementation of that function; notice the three instances of swap in the above definition (one is combined with cons and called swons). Second, your program is always manipulating a stack that isn't actually visible anywhere in the source code; this makes programming in Joy feel a lot more indirect than languages that use variables. This is directly contrary to what I described in Put it in the Syntax.

So I found myself wondering about ways to add variables to Joy. First I wondered whether it would be possible to automatically translate Joy-with-variables into Joy-without-variables. Here's Joy-with-variables:

List nub == [] List [[swap in] [pop] [swons] ifte] step;

I've added an explicit argument to the nub function, and then made use of it instead of having to rearrange the stack so that it's accessible. If it's not possible to automatically translate this into Joy-without-variables (and to some degree even if it is possible), it destroys a significant part of the theoretical motivation for Joy, because it reintroduces lexical environments.

You'll also notice that I decided to use capitalized names for variables, and lower-case names for functions (currently Joy uses lower case for all functions). I figured that the interpreter would probably need to make a syntactic distinction based on case, so that it would know that I intended List to be a variable name. It's only a short jump from there to noticing that this naming convention is exactly the same as what Prolog uses. And at that point it's almost impossible not to wonder what Joy might look like if it had logic variables, with unification.

And as long as we're at it, why not add pattern matching too? Pattern matching on structured types requires data constructors, so let's assume "cons" is a data constructor. Here we go:

             [] nub == [];
(Head Tail cons) nub == [Head Tail in] 
                         [Tail nub]
                         [Head Tail nub cons] 
                      ifte;

I'm not sure this train of thought makes sense though, because Joy is predicated on the idea that literals (like 31 or "foo") are actually nullary functions that push their value onto a stack. But if you assume that variables are also functions, then there's no theoretical reason why they should only push one variable on the stack. Which means that they should be able to pattern-match more than one element. Perhaps the fact that I felt compelled to put my data constructor inside parentheses, even though Joy has no need of parentheses, is trying to tell me something.

This is the point where I realize that my theoretical knowledge is spread too thin to hold me up anymore, and I suspect I may have walked into quicksand.

Posted on October 2, 2003 12:19 PM
More languages articles