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

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


I'd recommend hitting the mailing list at http://groups.yahoo.com/group/concatenative/ - the participants are /very/ erudite and enjoy discussing exactly such things.

If you want to do some background reading, I'd recommend snarfing the archives. Yahoo2mbox does this quite well (see http://www.lpthe.jussieu.fr/~zeitlin/yahoo2mbox.html for details).

Posted by: Gnomon at October 2, 2003 04:09 PM

I just remembered that Joy doesn't allow recursion, except via combinators. That's why I used "step" in the original version. I'm not up to rewriting the pattern matching example right now.

Posted by: kim at October 2, 2003 05:51 PM

Where did you hear that Joy does not allow recursion? There are indeed special-purpose combinators - genrec, linrec, binrec, tailrec and primrec come to mind, as well as the infamous Y combinator, as detailed and implemented at http://www.latrobe.edu.au/philosophy/phimvt/joy/j05cmp.html - but Joy is certainly not constrained to using them, to the best of my knowledge.

Do you have an implementation with which to play? There are a few binaries available in the "Files" section of the mailing list, and several toy implementations exist in various languages.

Joy is interesting in that it tends to attract implementations in unusual languages: ML, K, Prolog and some others. The concept is so bare-bones simple that it is usually mapped by the implementors onto their favourite paradigms rather than the other way 'round. I'm very interested to see where you're going with this.

Posted by: Gnomon at October 3, 2003 01:39 AM

I've been playing with the joy1 version written in C, which is accessible from the Joy main page as "current joy.tar.gz".

I was wrong when I said Joy didn't support recursion. I guess I had some other bug in my program when first tried to use recursion -- it kept telling me that the function wasn't defined. Sorry!

Posted by: kim at October 3, 2003 11:10 AM

Maybe you'd prefer...

nub2 == [] [[has] [pop] [swons] ifte] fold;

Posted by: Greg Buchholz at June 10, 2005 10:13 AM

Here's a long discussion on concatenative languages: http://lambda-the-ultimate.org/node/view/900

Posted by: Kim at January 10, 2006 11:15 PM

Uggs on sale now.UGG Classic Cardy Boot makes me different form the other

girls. The UGG Bailey Button Boot is a good choice for female.

Posted by: ugg classic cardy boots at November 17, 2009 12:32 AM

UGG Bailey Button bootsis a new style in 2009.The classic cardy uggs boots is another hot boots that worth of buying.And the classic tall ugg boots will make your winter amusing.And now uggs on sale,if you are looking for such a boot,the ugg boots is good choice this year.

Posted by: UGG Bailey Button Boots at November 17, 2009 01:16 AM

Louis Vuitton , commonly referred to as Louis Vuitton Handbags and Louis Vuitton Purse, or sometimes shortened to Louis Vuitton Custom Case has become one of the most Louis Vuitton Graffiti Handbag Agendas luxurybrands discount Louis Vuitton bags.

Posted by: 1 at November 17, 2009 01:52 AM


china wholesale clothing,china wholesale shoes,china wholesale electronics,china wholesale suppliers,china manufacturers

china wholesale products,light in the box,wholesale lots,wholesale ipod
china direct,china dropship,china trade,made in china

electronics wholesaler,ebay wholesaler,financial wholesaler
fashion wholesaler,clothing wholesaler,wholesaler magazine

computer wholesaler,external wholesaler,dvd wholesaler,wholesaler definition,china wholesaler,mutual fund wholesaler,define wholesaler,insurance wholesaler

discount ugg boots
ugg boots
Discount store

Posted by: wholesaler business website, net shopping site, external wholesaler,dvd wholesaler,wholesaler definition,china wholesaler,mutual fund wholesaler,define wholesaler,insurance wholesaler at November 18, 2009 03:02 AM

We are the best online sales for the china wholesale . Here you can have a large of choices of kinds Ugg Boots,Converse Shoes,Timberland Boots,puma shoes,Nike Shox Shoes ,Nike Dunk SB Shoes,Nike Air Max,Links Of London,Tiffany Jewelry,Dior Handbags?,jimmy choo handbags ,Cartier Watches, 8GB Mp4 Players,Bluetooth Car DVDs. All our cheap online cheap goods are high quality and original packages, and best service. We offer our customers the best service, 7 days arrive at your door.Enjoy your easy and happy shopping with us.

Posted by: cheap goods sale. at November 20, 2009 12:47 AM

Laptop Battery Laptop Battery Laptop Batteries
Laptop Batteries discount laptop battery
discount laptop battery
notebook battery notebook battery
computer battery computer battery
replacement laptop battery replacement laptop battery
notebook batteries notebook batteries

Posted by: Laptop Battery at November 25, 2009 12:16 AM

People all over the world know the abercrombie and fitch,but not everyone really knows how fashion the abercrombie is,hollister is the Legend maker. Everybody wears the hollister clothing would be the abercrombie mens and the abercrombie womens, if you want know you can search the Ruehl No.925 or abercrombie outlet in the www.google.com .

Posted by: fitch at November 25, 2009 10:23 PM

Ugg Classic Cardy


Ugg Classic Tall


Ugg Classic Short


Posted by: topuggshoes at November 26, 2009 03:18 AM

Just wanted to say great job with the blog, today is my first visit here and Iíve enjoyed reading your posts so far
ugg bailey button
Wow, my ugg classic mini will not be coming off now! Iíve had them on for 12hrs strait and I do not want to take them off. Thanks for everything, well worth the wait.

Posted by: ugg bailey button boots at November 30, 2009 06:01 AM
Post a comment

Remember info?

Prove you're human. Type "human":