Monday, December 08, 2008

enJOY

Programming for the sole purpose of having fun with it - How does this sound ? We have been talking about learning a different programming language every year, taking on the pill of polyglotism, learning languages that inhabit the common runtimes like the JVM or the CLR. But all this for the purpose of making ourselves a better programmer and raising our programmer value index in today's market. Really how many of us can afford to do so ? Most of us have a day job where we work on mainstream programming languages, strive hard to meet up to the expectations of the enterprise client and ensure that each of us remain billable to the client in the foreseeable future.

If you thought you are having enough fun with lambdas, look out for more fun with functional programming without lambdas. Lambda calculus is about functions and applications of functions on arguments. I have been just been introduced to a functional programming language named Joy, which is NOT based on application of functions to arguments.

Holy crap ? No parameters .. what do functions do ?

They execute instructions on values that they find on the stack. And this post is about enjoying the beauty and savoring the fun that learning Joy has brought forth to me. And remember, you can have that too .. remove your day job hat for some time (maybe over a few weekends) and get immersed in the beauty of recursion and theory of computability.

Let us take an example ..

Suppose you want to write a function that computes the square of a number .. here is a Joy version for that ..

dup *

>> (dup)licate the element on top of the stack and apply multiplication operator (*) on the 2 top elements of the stack.

You can have a name for the function if you want to reuse it many times ..

square == dup *

and invoke it as

5 square

or without names

5 dup *

dup dup * *

Intuitive huh!

What does the following do ?

[dup dup * *] map

Ok .. possibly I have jumped too far ..

In Joy, programs evolve through 2 operations - quotation and concatenation.

Quotation can be thought of as a passive data structure and is indicated by surrounding the quoted program with square brackets. In the last example, [dup dup * *] is a quoted program. But it is also a list - in Joy lists are as well indicated within square brackets e.g. [1 2 4 6] is a list. So generically speaking lists are quoted programs in Joy. And a list can contain elements that are not literals and can be made to operate on values. And for that we need to activate the passive quotation.

Concatenation of two programs in Joy is effectively the composition of the functions denoted by the programs. Consider the example program ..

2 3 + dup *

which is effectively, the composition, denoted abstractly by *(dup(+(2, 3)))

In the above example that we left off without solving, the quoted program is activated by the combinator that follows it .. map. Combinator is another useful device that causes execution of the quoted program on top of the stack. There are a variety of combinators in Joy, the most trivial one being the i-combinator. i-combinator just dequotes the quoted program, i.e.

[dup dup * *] i

is equivalent to

dup dup * *

What about the map combinator ? Let us try to run the last example where we left off .. with some actual data ..

[4 6 8 9] [dup dup * *] map

Here is what happens ..

• Joy first pushes the list of integers on the stack

• Then the quoted program is pushed .. remember quoted programs are passive - hence nothing gets executed

• The map combinator then removes the list of integers and the quoted program and constructs a new list by applying the program to each element of the list. The usual stuff that map is so well-known to do ..

The result is a list that contains the cubes of the original elements.

I have only scratched the surface in order to tickle you towards a functional language that is not based on lambda calculus. I am sure you will also find Joy equally interesting, and loads of fun learning.

Tailpiece

Did you notice that we can have any element within a list ? Sounds familiar ? Yes, you got it right ! Program as data, as Joy would have it. A quoted program is data unless operated upon by a combinator. And, as this landmark paper suggests ..

"Since programs are data, it is possible to define a Y-combinator for recursion and several variants. It follows that there are self-reproducing and self-describing programs in Joy. Practical programs can be written without recursive definitions by using several general purpose recursion combinators which are more intuitive and more efficient than the classical ones."

Go read this paper .. it is an absolute joy (pun intended) if you want to learn more about recursion, combinators and computability. This paper was my starting inspiration in dabbling with Joy. You can also have it .. enJoy!

Mike Miller said...

Joy appears to be heavily influenced by FORTH. In FORTH (which dates from the late '70s) words had compile time and execution time semantics, analogous somewhat to the quotation and concatenation aspects of Joy.

I haven't played with FORTH in decades, but it was huge fun. I'll definitely have to give Joy a try.

Debasish said...

You are correct! Joy is said to be the functional cousin of Forth :-)

Ricky Clarkson said...

"You may be doing Java / C# in your day job, feel guilty about not yet joining the bandwagon of functional programming"

Actually, it's perfectly possible and even pleasant to do a lot of functional programming in C#.

Jonathan Pryor ported Haskell's Data.List library to C#, and the result is generally quite readable and efficient.

This is in stark contrast to Java, which is idiotic in many ways.

Krzysztof (Christopher) Kliś said...

It should be rather called Toy, not Joy... Seems like a reversed-notation Lisp to me, at least at the first glance. If you wanna play with twisted-syntax languages, you can as well try any other esoteric language.

Debasish said...

Ricky -

It is true that C# has introduced lots of functional programming features, of late. I have seen quite a few enterprise applications in C#, and the mainstream is still mostly imperative. Hence bulk of the programmers doing C# for day job are still in the imperative paradigm only. I am sure things will change with Microsoft patronizing FP these days.

Ricky Clarkson said...

Debasish,

One reason for that is that lots of C# programmers are locked to an older version of C#. Part of this is the usual stodge of companies delaying things, and part of it is that newer versions of .NET don't work on older versions of Windows.

Of course there are other reasons that C# programmers do it imperatively; there are always reasons to do things badly in enterprise programming. Or so it seems.

Dmitriy Kopylenko said...

Have you seen this post?

http://www.codecommit.com/blog/cat/the-joy-of-concatenative-languages-part-1

Debasish said...

Dimitry -

Indeed I saw it. Today only myself and Daniel were discussing this coincidence over Tweeter :-)

wtanksley said...

Seems like a reversed-notation Lisp to me, at least at the first glance.

I would suggest you take more than a glance. Try looking at the paper he referenced, for a start. Perhaps look around the rest of that site (there are many more).

Joy is an experimental language, but not a toy language. Forth is neither experimental nor a toy, and it has many fewer practical features than Joy.

Factor is another concatenative language that's been designed and tested to be highly practical.

Anyhow, the big reason why "backward Lisp" is a horrid name for concatenative languages is that Lisp is a fully applicative language (it's built around function application, and everything looks like a function call), while Joy and its cousins are non-applicative languages (they don't require function application at all).

wtanksley said...

BTW, Joy isn't influenced by Forth -- it's very similar, but the author doesn't know Forth and didn't research it. It's more influenced by Postscript. The similarity is largely coincidence, and perhaps partly because Postscript is influenced by Forth (although HP entirely denies that).

Peter said...

Hi Debasish,

I know it's been a long time since your post, but I'm trying to find that paper you reference. The link's broken. I see it was hosted by La Trobe in Australia. I don't suppose you recall the name of the paper, or the author?

Debasish said...

Hi Peter -

I could track down the paper from a mirror site - the original Joy site is broken. The paper is Recursion Theory and Joy by the man himself, Manfred von Thun. Here is the link .. http://www.kevinalbrecht.com/code/joy-mirror/j05cmp.html ..

Hope this helps ..