The Artima Developer Community
Sponsored Link

Weblogs Forum
The Joy of Joy

11 replies on 1 page. Most recent reply: Feb 9, 2006 6:38 PM by Christopher Diggins

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 11 replies on 1 page
Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

The Joy of Joy (View in Weblogs)
Posted: Feb 4, 2006 2:12 PM
Reply to this message Reply
Summary
I have recently discovered the somewhat unknown and understated language, Joy. A pure functional language, without lambda operations!
Advertisement
The Joy programming language is an intriguing beast in the programming language menagerie. It is an exceedingly powerful little language. Joy is based on the idea of "function-level programming" outlined by Backus which is distinct from "functional programming". Here is a short synopsis from the language designer, a philosophy professor named Manfred von Thun:
Whereas all other [note: should be 'most other'] functional programming languages are based on the application of functions to arguments, Joy is based on the composition of functions. All such functions take a stack as argument and produce a stack as value.
Here is a simple Joy program for performing a quick sort, taken from the Wikipedia article about Joy:
DEFINE qsort ==
   [small]
   []
   [uncons [>] split]
   [[swap] dip cons concat]
   binrec .
That is very elegant, even if somewhat cryptic on first glance. Here is the explanation from Wikipedia
"binrec" is one of Joy's many recursive combinators, implementing binary recursion. It expects four quoted programs on top of the stack which represent the termination condition (if a list is "small" (1 or 0 elements) it is already sorted), what to do if the termination condition is met (in this case nothing), what to do by default (split the list into two halves by comparing each element with the pivot), and finally what to do at the end (insert the pivot between the two sorted halves).
The Joy language bears some obvious similarities to Forth. Forth has decent recognition as an efficient language. I wonder how efficient a Joy interpreter and/or compiler could be? How small? I am building one right now, just for the fun of it. For those that remember my little foray into a functional programming dialect in C++, called Unimperative, I am resucitating it as a Joy dialect.

At this point, I am still exploring the possibilities of using some dialect of Joy for different purposes. Here are some ideas:

  • Joy could possible be used as a virtual machine language, perhaps as a target for Heron, which itself can be easily retargetted
  • Maybe a Joy dialect could be useful as a pre-processor language for defining macros.
  • The Joy syntax itself could probably be significantly improved by using a sufficiently powerful pre-processor (implemented itself in Joy?!? Now I have a headache)
I wonder why more people don't talk about Joy. Perhaps it just isn't cool ... yet.


Keith Gaughan

Posts: 17
Nickname: kgaughan
Registered: Feb, 2003

Re: The Joy of Joy Posted: Feb 4, 2006 7:36 PM
Reply to this message Reply
You should subscribe to the concatenative languages list: http://groups.yahoo.com/group/concatenative/

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: The Joy of Joy Posted: Feb 5, 2006 11:01 AM
Reply to this message Reply
> You should subscribe to the concatenative languages list:
> http://groups.yahoo.com/group/concatenative/

Done, just waiting for my approval by the moderator.

Achilleas Margaritis

Posts: 674
Nickname: achilleas
Registered: Feb, 2005

Re: The Joy of Joy Posted: Feb 7, 2006 6:57 AM
Reply to this message Reply
For all practical purposes Joy is exactly like Lisp. The only real difference between Joy and Lisp is that Joy finds its parameters on the stack, whereas Lisp has named parameters.

Achilleas Margaritis

Posts: 674
Nickname: achilleas
Registered: Feb, 2005

Re: The Joy of Joy Posted: Feb 7, 2006 9:37 AM
Reply to this message Reply
Actually it is very easy to define Joy in C++. Here is some preliminary untested code for the basic functions of joy:


#include <list>
#include <iostream>
using namespace std;

enum type_t {
type_integer,
type_function
};

typedef void (*function_t)();

union elem_t {
type_t type;
int val;
function_t fun;
elem_t(int v) : type(type_integer), val(v) {}
elem_t(function_t f) : type(type_function), fun(f) {}
operator int() const { return val; }
};

typedef list<elem_t> stack_t;

stack_t stack;

stack_t &operator << (stack_t &st, int v) {
st.push_front(v);
return st;
}

stack_t &operator << (stack_t &st, function_t f) {
st.push_front(f);
return st;
}

void pop() {
stack.pop_front();
}

void popd() {
stack.erase(++stack.begin());
}

void popop() {
stack.pop_front();
stack.pop_front();
}

void dup() {
stack.push_front(stack.front());
}

void dupd() {
stack.push_front(*++stack.begin());
}

void swap() {
swap(*stack.begin(), *++stack.begin());
}

void swapd() {
swap(*++stack.begin(), *++++stack.begin());
}

void rollup() {
stack.insert(++++stack.begin(), stack.front());
stack.pop_front();
}

void rolldown() {
stack.push_front(*++++stack.begin());
stack.erase(++++++stack.begin());
}

void choice() {
elem_t e = *++++stack.begin();
if (e) {
stack.erase(++++stack.begin());
pop();
}
else {
popop();
}
}

void put() {
elem_t e = stack.front();
stack.pop_front();
cout << e.val;
}

void get() {
int i;
cin >> i;
stack.push_front(i);
}

void add() {
stack.push_front(*stack.begin() + *++stack.begin());
}

void sub() {
stack.push_front(*stack.begin() - *++stack.begin());
}

void mul() {
stack.push_front(*stack.begin() * *++stack.begin());
}

void div() {
stack.push_front(*stack.begin() / *++stack.begin());
}

void mod() {
stack.push_front(*stack.begin() % *++stack.begin());
}

void min() {
int v1 = *stack.begin();
int v2 = *++stack.begin();
stack.push_front(v1 < v2 ? v1 : v2);
}

void max() {
int v1 = *stack.begin();
int v2 = *++stack.begin();
stack.push_front(v1 > v2 ? v1 : v2);
}

void succ() {
stack.push_front(stack.front() + 1);
}

void pred() {
stack.push_front(stack.front() - 1);
}


Here is an example that adds two numbers:


int main()
{
stack << 1 << 2 << add << mul << put;
getchar();
return 0;
}


The above prints 6 in the console.

Actually, this is a very cool way to program!

Andy Dent

Posts: 165
Nickname: andydent
Registered: Nov, 2005

Re: The Joy of Joy Posted: Feb 7, 2006 1:26 PM
Reply to this message Reply
Check out False and particularly the Nano-False implementation by Willow Fung (a copy is cached on the False page, down the bottom).

http://wouter.fov120.com/false/index.html

This is more of a Forth implementation than Joy but is tiny - you can write and run code on a mobile phone.

The key difference from Forth is being able to push code blocks on the stack rather than having to use named references.

The most disturbing and obfuscating thing is that spaces are utterly optional!

Yes it looks like line noise but because the number of operators is so small it doesn't take long to get used to it and it is certainly a great demo of the UI issue of how to have a compact language that can be entered with minimal characters on a phone keypad!

annotated recursive example: the fac() function.

[$1=$[\%1\]?~[$1-f;!*]?]f:

thus we call fac(6) (=720) like:

6f;!

no range checking is done by the "f" function, that is what
is done by the fac.f example program.

Well, how does it work? (does it?) First recognise the f;! within
the function implementation: that's the recursion. Let us recall what
fac() looks like in a hypotheticall procedural/functional programming
language:

fac(n) = if n=1 then 1 else n*fac(n-1)

our FALSE code goes just along these lines, only we use two "if"'s (hence
the two [] blocks) insteas of one if-then-else.
we start with (n-) on the stack:

$1=$

duplicate the n, and compare it with 1, and leave a second truthvalue (t),
thus: (n,t,t-)

[\%1\]?

first push the [], and after the "if" (=?) we have (n,t-). we won't
be needing the lower n anymore, so we swap and drop. then we push the
final result "1", and swap it below the truthvalue for the second "if".
(1,t-)

~[$1-f;!*]?

we first have to negate the truthvalue, because this is the else part.
in the "if"-body, we have just (n-), and we add a "n-1" to that as argument
for the recusive call. after f;! we have (n,r-) (r is result of the call),
and we simply multiply the two together as result of the whole.

Achilleas Margaritis

Posts: 674
Nickname: achilleas
Registered: Feb, 2005

Re: The Joy of Joy Posted: Feb 8, 2006 4:57 AM
Reply to this message Reply
I wonder if the Joy paradigm can be used for real world programming. I am thinking of doing a complete C++ framework based on Joy and Lisp:

a) code and data and data as code, as in Lisp.
b) functions made out of combinators as in Joy.

The stack will be a list, of course.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: The Joy of Joy Posted: Feb 8, 2006 4:27 PM
Reply to this message Reply
> Actually, this is a very cool way to program!

I like your approach of using <<. How would you define and name a new program using your sytem?

for instance:


define dupd == [dup] dip;


I am doing something similar with the Unimperative. It uses "," instead of "<<". So the above code would be writtten:


#include "unimperative.hpp"

def dupd = (q(dup), dip);


"q" is the quote operator, or "[]" in Joy.

The next step is that I am looking at introducing an explicitly typed version of Unimperative


def<int> square = (dup, multiply);


I have written some code for efficient dynamically typed variant objects which you might find useful. It's at:

http://www.codeproject.com/cpp/dynamic_typing.asp

Essentially the same thing as boost::any but much faster.
Are you interested in collaborating on the idea of creating a Joy dialect in pure C++?

Here is how an Unimperative file might look (it can be included directly in a C++ project.


namespace standard
{
def<any, any>
popd = (q(pop), dip);

def<any, any>
dupd = (q(dup), dip);

def<any, any>
swapd = (q(swap), dip);

def<any, any, any>
rollup = (swap, q(swap), dip);

def<any, any, any>
rolldown = (q(swap), dip, swap);

def<any, any, any>
rotate = (swap, q(swap), dip, swap);

def<any>
unitlist = (emptylist, cons);

def<list>
unitlistlist = (emptylist, cons);

def<list, list>
pairlist = (emptylist, cons, cons);

def<list>
unpair = (uncons, uncons, pop);

def<list>
second = (rest, first);

def<list>
third = (rest, rest, first);

def<list>
uncons2 = (q(uncons), dip, uncons, swapd);

def<list>
unswons2 = (q(unswons), dip, unswons, swapd);
}

Achilleas Margaritis

Posts: 674
Nickname: achilleas
Registered: Feb, 2005

Re: The Joy of Joy Posted: Feb 9, 2006 7:38 AM
Reply to this message Reply
> I am doing something similar with the Unimperative. It
> uses "," instead of "<<". So the above code would be
> writtten:

Yeap, another choice is operator ','. It may feel more natural, especially in the context of a LISP like approach.

> "q" is the quote operator, or "[]" in Joy.

How about using an unary operator? examples:


def dupd = (!dup, dip);
def dupd = (~dup, dip);
def dup3 = (&(dup, dup), dip);


I think operator '&' would be better as the quote operator, since it there is an analogy of 'address of' to 'value of'.

>
> The next step is that I am looking at introducing an
> explicitly typed version of Unimperative
>
>

> def<int> square = (dup, multiply);
>


I think some type information would definitely help towards less bugs.

>
> I have written some code for efficient dynamically typed
> variant objects which you might find useful. It's at:
>
> http://www.codeproject.com/cpp/dynamic_typing.asp

Clever idea to use the pointer itself to store values that their size is <= to sizeof(void *).

A small note though: since a functional approach means 'no assignment', would it be more practical that values are shared between instances of class 'any' (using reference counting)? If I understood your code, each time 'any' is copied, the value is cloned.

> Are you interested in collaborating on the idea of
> creating a Joy dialect in pure C++?

Sure!

>
> Here is how an Unimperative file might look (it can be
> included directly in a C++ project.
>
>

> namespace standard
> {
> def<any, any>
> popd = (q(pop), dip);
>
> def<any, any>
> dupd = (q(dup), dip);
>
> def<any, any>
> swapd = (q(swap), dip);
>
> def<any, any, any>
> rollup = (swap, q(swap), dip);
>
> def<any, any, any>
> rolldown = (q(swap), dip, swap);
>
> def<any, any, any>
> rotate = (swap, q(swap), dip, swap);
>
> def<any>
> unitlist = (emptylist, cons);
>
> def<list>
> unitlistlist = (emptylist, cons);
>
> def<list, list>
> pairlist = (emptylist, cons, cons);
>
> def<list>
> unpair = (uncons, uncons, pop);
>
> def<list>
> second = (rest, first);
>
> def<list>
> third = (rest, rest, first);
>
> def<list>
> uncons2 = (q(uncons), dip, uncons, swapd);
>
> def<list>
> unswons2 = (q(unswons), dip, unswons, swapd);
> }
>


I think it is the appropriate approach.

Some (maybe silly) notes/questions/ideas:

1) What does 'dip' do? for example, popd would be defined as (pop, pop), wouldn't it?

2) wouldn't 'let' be a more appropriate name instead of 'def' and 'pop_twice' instead of 'popd'? in fact, wouldn't it be better to give better names instead of those cryptic ones? how about 'join' instead of 'cons'? I never agreed with the LISP naming: I find it cryptic and weird and puzzling, especially for newcomers.

3) I think that the reverse polish notation is difficult to stomach, especially if someone is a newbie in this domain (which most certainly it would be the case for most of us!). How about normal left-to-right notation?

For example, instead of adding two numbers like this:


let three = (1, 2, add);


It would be better if it was like this:


let three = (add, 1, 2);


'1' and '2' would still be pushed to the stack, and 'add' would be executed after the push operations, of course.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: The Joy of Joy Posted: Feb 9, 2006 10:47 AM
Reply to this message Reply
> I think operator '&' would be better as the quote
> operator, since it there is an analogy of 'address of' to
> 'value of'.

Excellent idea!

> Clever idea to use the pointer itself to store values that
> their size is <= to sizeof(void *).

Thanks.

> A small note though: since a functional approach means 'no
> assignment', would it be more practical that values are
> shared between instances of class 'any' (using reference
> counting)? If I understood your code, each time 'any' is
> copied, the value is cloned.

Either approach would be fine, as long as the semantics of the language are respected. I implement big structures like lists as being internally reference counted. This keeps things simple.

> > Are you interested in collaborating on the idea of
> > creating a Joy dialect in pure C++?
>
> Sure!

Excellent! I have just created a mailing list: http://groups.google.com/group/unimperative .
I am hoping we can continue this discussion there? I should have a web site up by the weekend at Unimperative.com.

> I think it is the appropriate approach.

Good!

> Some (maybe silly) notes/questions/ideas:

Silly is completely welcome ;-)

> 1) What does 'dip' do? for example, popd would be defined
> as (pop, pop), wouldn't it?

Dip is one of the fundamental combinators of Joy, it takes a quoted program and applies it to the element just below the top of the stack.

http://www.latrobe.edu.au/philosophy/phimvt/joy/j06prg.html

> 2) wouldn't 'let' be a more appropriate name instead of
> 'def' and 'pop_twice' instead of 'popd'?

'popd' was taken from the Joy lexcion, I don't care too much for it. As for 'def' versus 'let' it is interesting. At this point I am not sure I love 'let' but I am not firm on the idea.

> in fact, wouldn't
> it be better to give better names instead of those cryptic
> ones? how about 'join' instead of 'cons'? I never agreed
> with the LISP naming: I find it cryptic and weird and
> puzzling, especially for newcomers.

I agree. I think the solution is to have alternative namespaces for the programmer to choose from. For example "common_joy" and "common_unimperative". One set can be trivially defined from the other.

> 3) I think that the reverse polish notation is difficult
> to stomach, especially if someone is a newbie in this
> domain (which most certainly it would be the case for most
> of us!). How about normal left-to-right notation?

I agree that reverse polish is hard to swallow. But I really like the fact that programs can be concatenated.

let AB = (A, B)
let CD = (C, D)
(A, B, C, D) === (AB, CD)

I want to support an obvious mapping from Joy to Unimperative, and to be able to use the concatenative style of syntax.

However I am already supporting the following dual syntax in my prototype:

(1, 2, add)

is equivalent to

add(1, 2)

These two approaches can be mixed. The following are all equivalent

(1, 2, add, 3, multiply);
(add(1, 2), 3, multiply);
multiply((1, 2, add), 3);
multiply(add(1, 2), 3);

For machine manipulation (analysis, optimization, etc) it will be convenient to support a pure concatenative approach.

Achilleas Margaritis

Posts: 674
Nickname: achilleas
Registered: Feb, 2005

Re: The Joy of Joy Posted: Feb 9, 2006 10:52 AM
Reply to this message Reply
After careful thinking I realized that the template parameters must belong to the functions inside expressions and not to the declarations.

For example, when adding 3 integers, the function should be:


let add3 = (add <int>(), add<int>());


When adding 3 doubles, the function should be:


let add3 = (add<double>(), add<double>());


The reason for the template declaration in expressions is that it is more useful to have template expressions than template definitions: with template expressions, the definitions can be reused (i.e. customized at point of usage), whereas with template definitions one needs to declare several different versions. Example:


def<int, int> add3 = (add, add);
def<double, double> add3 = (add, add);


The above of course does not compile, since it has two symbols with the same id. It would be interesting if functions where templates, then, when used, instantiated to specific types. Therefore one could write:


(add3<int>(), 1, 2, 3);
(add3<double>(), 1, 2, 3);


We shall also need a framework for declaring new 'unimperative' functions declared in C++, for performance reasons.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: The Joy of Joy Posted: Feb 9, 2006 6:38 PM
Reply to this message Reply
For those interested, the conversation has moved to http://groups.google.com/group/unimperative . I hope to see you there!

Flat View: This topic has 11 replies on 1 page
Topic: Collection overused as an argument in Java Libraries? Previous Topic   Next Topic Topic: Mutable Types


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us