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
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 PMI 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 PMWhere 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 AMI'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!
Maybe you'd prefer...
nub2 == [] [[has] [pop] [swons] ifte] fold;
Posted by: Greg Buchholz at June 10, 2005 10:13 AMHere's a long discussion on concatenative languages: http://lambda-the-ultimate.org/node/view/900
Posted by: Kim at January 10, 2006 11:15 PMugg boot australia
bailey button ugg sale
ugg classic cardy cheap
classic cardy ugg sale online
ugg unique bailey button
عقارات عام
عقارات عام
عقارات عام
عقارات عام
عقارات عام
عقارات عام
عقارات عام
عقارات عام
عقارات عام
عقارات عام
عقارات عام
Thanks for your useful info, I think it’s a good topic. So would you like the info about the
jordan shoes
Air jordan shoes
cardy ugg boots
Tiffany Jewelry
ugg bailey button boots
cheap jordan shoes
ugg boots uk
Michael jordan shoes
ugg london
ugg nightfall boots
ugg boots sale
classic ugg boots
sundance ugg boots
air jordan fusion 6
air jordan 6 rings
jordan shoes for sale
Ugg
Ugg Boots
Cheap Ugg
New Ugg Boots
Ugg Boot
Ugg Classic Boots
Cheap Ugg Boots
Uggs on sale
Uggs
Ugg Boots
Cheap Ugg Boots
Ugg Classic Boots
Ugg Boots Sale
Supra Shoes
Mens Supra Cruizer Shoes ---Special
Men's Supra Cruizer Red Shoes
Mens Supra Cruizer Cool Shoes
Mens Supra Cruizer Shoes --Charming
Mens Supra Cruizer Pure black Shoes
Mens Supra Cruizer Shoes --Leisure
Man's Supra Cruizer Shoes
Men's Supra Muska Skytop Shoes
Men's Supra Skateboarding Shoes
Men's Supra Strapped Shoes
Men's Supra Suprano High Shoes
Women's Supra Muska Skytop Shoes
cheap ugg boots sale
uggs classic mini sale
UGG Ultra Tall Boots
Cheap Ugg Boots
UGG Classic Tall Boots
UGG Classic Cardy
UGG Classic Short Boots
Supra Shoes
Mens Supra Cruizer Shoes ---Special
Men's Supra Cruizer Red Shoes
Mens Supra Cruizer Cool Shoes
Mens Supra Cruizer Shoes --Charming
Mens Supra Cruizer Pure black Shoes
Mens Supra Cruizer Shoes --Leisure
Man's Supra Cruizer Shoes
Men's Supra Muska Skytop Shoes
Men's Supra Skateboarding Shoes
Men's Supra Strapped Shoes
Men's Supra Suprano High Shoes
Women's Supra Muska Skytop Shoes
cheap ugg boots sale
uggs classic mini sale
UGG Ultra Tall Boots
Cheap Ugg Boots
UGG Classic Tall Boots
UGG Classic Cardy
UGG Classic Short Boots
Supra Shoes
Mens Supra Cruizer Shoes ---Special
Men's Supra Cruizer Red Shoes
Mens Supra Cruizer Cool Shoes
Mens Supra Cruizer Shoes --Charming
Mens Supra Cruizer Pure black Shoes
Mens Supra Cruizer Shoes --Leisure
Man's Supra Cruizer Shoes
Men's Supra Muska Skytop Shoes
Men's Supra Skateboarding Shoes
Men's Supra Strapped Shoes
Men's Supra Suprano High Shoes
Women's Supra Muska Skytop Shoes
cheap ugg boots sale
uggs classic mini sale
UGG Ultra Tall Boots
Cheap Ugg Boots
UGG Classic Tall Boots
UGG Classic Cardy
UGG Classic Short Boots
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 AMUGG 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 AMLouis 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.
www.enjoywholesale.com
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
forture
ugg boots
Discount store
replica watch
replica A.Lange & Sohne
replica Alain Silberstein
Supra Shoes
Supra Skytop Shoes
Supra Society
Supra Thunder
Supra Suprano Hi
Supra Strapped
Supra Trinity
Supra Skylow 1.5
Supra Dixon
Diablo 1.5
Supra Cruizer
Supra Vaider Shoes
Supra Cuban
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.
discount nike air yeezy
china wholesale online
discount ugg boots
nike free shoes
furture
ugg boots
Discount store
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
rongTiffany Jewelry Online - Discount Tiffany & Co Jewelry On Sale
Hot Sell Tiffany Jewelry - Tiffany Jewelry Online
Return To Tiffany Double Heart Detachable Pendant Necklace - Tiffany Jewelry Online
Tiffany&Co 1837 Titanium I.D. Bracelet - Tiffany Jewelry Online
Tiffany & Co Bead Bracelet - Tiffany Jewelry Online
Tiffany&Co Atlas Round Pendant Necklace - Tiffany Jewelry Online
Tiffany&Co Bar Pendant Necklace - Tiffany Jewelry Online
Tiffany&Co Bead Necklace(N242) - Tiffany Jewelry Online
Tiffany&Co Bean Pendant Necklace(N157) - Tiffany Jewelry Online
Tiffany&Co Elsa Peretti Apple Pendant Necklace - Tiffany Jewelry Online
Tiffany&Co Butterfly Pendant Necklace - Tiffany Jewelry Online
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 PMJust 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.
cheap replica watches
replica Rolex Submariner
Rolex Masterpiece watch for sale
replica Lady Watch
Rolex GMT watch for sale
balenciaga handbags
Replica Louis Vuitton Speedy 30
Louis Vuitton Replica Speedy 30
Posted by: fanqin at December 1, 2009 03:26 AMBurberry Handbags|
Burberry Handbag|
Burberry bags|
Burberry bag|
Chloe Handbags|
Chloe Handbag|
Chloe bags|
Chloe bag|
Christian Dior Handbags|
d&g Handbags|
d&g Handbag|
d&g bags|
d&g bag|
Hermes Handbags|
Hermes Handbag|
Hermes bags|
Hermes bag|
replica Hermes|
replica Hermes Handbags|