 Recursion Theory and Joy
started 1/13/2003; 5:09:55 AM - last post 1/15/2003; 5:24:26 PM
|
|
Ehud Lamm - Recursion Theory and Joy 
1/13/2003; 5:09:55 AM (reads: 1792, responses: 6)
|
|
| Recursion Theory and Joy |
|
Joy is a functional programming language which is not based on the application of functions to arguments but on the composition of functions. Many topics from the theory of computability are particularly easy to handle within Joy. They include the parameterisation theorem, the recursion theorem and Rice's theorem. 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.
A short discussion of such cool things as fixed point combinators, Kleene's S-m-n theorem, and Rice's theorem.
Along the line you are introduced to Goedel numbering and self-reproducing programs.
Posted to theory by Ehud Lamm on 1/13/03; 5:12:15 AM
|
|
|
|
Michael Vanier - Re: Recursion Theory and Joy
1/14/2003; 1:05:57 AM (reads: 769, responses: 1)
|
|
|
Very neat stuff. Thanks for adding yet another language to the ever-growing list of languages I absolutely *must* learn ;-)
Seriously, Forth was the first computer language I really fell in love with. Joy is a very pretty creation indeed, unifying many of the things I liked about Forth with functional programming and combinators, two other favorite subjects of mine.
|
|
Ehud Lamm - Re: Recursion Theory and Joy
1/14/2003; 1:26:29 AM (reads: 798, responses: 0)
|
|
|
Yeah, I did find find the similarity to Forth disturbing.
|
|
Noel Welsh - Re: Recursion Theory and Joy
1/14/2003; 5:51:04 AM (reads: 771, responses: 0)
|
|
|
|
Michael Vanier - Re: Recursion Theory and Joy
1/14/2003; 9:24:49 AM (reads: 730, responses: 0)
|
|
|
Ehud, I take it you *didn't* fall in love with Forth as a kid ;-)
Forth and Joy may share some features, but the philosophy is totally different. Joy is a functional language, whereas Forth is basically a user-extensible virtual machine architecture. In Forth, you can hack the internals of the Forth interpreter and compiler; it's virtually the only language where this is possible. This is enabled by the incredibly simple interpretation and compilation semantics.
I find Forth to be very beautiful, especially considering its age, but it's not really useful for anything I do.
|
|
Isaac Gouy - Re: Recursion Theory and Joy
1/15/2003; 9:04:38 AM (reads: 665, responses: 0)
|
|
|
you can hack the internals of the Forth interpreter and compiler; it's virtually the only language where this is possible
There's probably quite a list of languages which allow the interpreter/compiler to be modified - that's beyond my knowledge.
I do know that you can change the VW Smalltalk compiler and the Squeak compiler.
|
|
Michael Vanier - Re: Recursion Theory and Joy
1/15/2003; 5:24:26 PM (reads: 663, responses: 0)
|
|
|
Yes, Smalltalk is an exception. Certainly Squeak was designed to be hackable at all levels. I can't think of another exception out of the >30 languages I know; can you? Some languages give you different ways to achieve similar power (lisp macros, C++ templates), but that's another subject.
|
|
|
|