Lambda (was: Refactoring in Tunes)

[John Carter]

On Thu, 13 Jan 2000, Massimo Dentico wrote:

> John Carter wrote:
> > Careful, as far as I can see Joy has one good idea and that is superb,
> > but it is not an idea that will solve all the problems Tunes is
> > addressing.
> 
> > The heart and joy of the Joy idea, (correct me if I'm wrong), is that
> > by creating  a simple homomorphism between the syntatic  operation of
> > putting one symbol  next to another and the function  composition you
> > create something which is trivial to create an extensive algebra on.
> 
> As a side note this abstraction maps directly to machine language also:
> a composition  of N instructions  is given  by putting one  instruction
> next to another in memory. In your opinion, what is the consequences of
> this? (or .. please can you elaborate on "which is trivial to create an
> extensive algebra on."? I'm interested.)

The crucial paper is
  http://www.latrobe.edu.au/www/philosophy/phimvt/j04alg.html

Firstly lets discuss why having such a tidy algebra is so nice. 
  1) It allows extensive automagic rewriting of a Joy program without
     changing the semantics. ie. Automated refactoring becomes a
     relatively simple branch of algebraic simplification.
  2) It allows far larger degree of program proving.
  3) If its simpler to prove things about your program, its simpler to
     understand and debug it.
  4) One of the hairier features in a Scheme implementation seem to be
     the hygienic macros. (You have to "rename" variables to prevent
     accidental clashes with variables outside the macro. Having done
     so the resulting code is full of generated bindings that is not
     so nice to understand.) The "namelessness" of Joy gives you the
     hygiene for free.
 
Now lets pick up the things in Joy that gives us this. 

a) You're right. Each patch of machine code can be considered as a
unary function from the entire state of the machine to the new state
of the machine. And concatenation strings of machine code maps to
function composition. Simplification number one to note is that Joy
maps stack to stack rather than random access memory + bizarre
registers to RAM + bizarre registers.

b) Whilst machine code has this property, most HLL like
C/Ada/etc. explicitly do _not_ have this property. I claim
that to use reflection in any language that doesn't have this
property is difficult.

c) Related to this is this quote from "The Algebra of Joy"....

  If Q1 and Q2 are programs which denote the same function and P and R
  are other programs, then the concatenations P Q1 R and P Q2 R also
  denote the same function.

To get this behaviour in anything with variable names is actually
quite tricky. We do it, yes, but not nearly so simply. Its the utterly
profound simplicity here that is absolutely striking.

Its so blooming simple that you have to sit back and try this in
whatever other language you can think of to realise how gobsmackingly
profoundly simple this is. It looks trivial but try it in anything else
you care to shake a stick at to realise that deep deep magic is going
on here. 
p( q1( r( x))) = p( q2( r( x))) for all x OK that was easy.

p(a, b, q1( c, d, r( e, f), g)) == p(a, b, q2( c, d, r( e, f), g))
whoopsy we now saying a lot about the arity of the functions p,q1,q2,r
that we didn't want to get involved with.

I'll admit to still being in deep thought as to whether Joy adds
anything to the whole business of Category theory or not. I suspect
not. I suspect better semantics for Joy would do a lot more in that
department.

d) Combinators and eval.

If you want to write a very obfusticated Perl program, make sure you
use the eval function. In fact every truly obfusticated program I have
seen has some form "eval" in it. There is something truly evil about
eval.

The only useful uses I have seen of eval have been for ...
  i)  Allowing users to enter expressions instead of just numbers, you
      can then eval the expressions entered.
  ii) Working around language misfeatures.
  iii) Language extensions.

Yet Joy centers around combinators and combinators are merely fancy
forms of eval! If eval is evil in other languages, why does
it become "good" here? 

Because in Joy reflection is so simple and hence ingrained that the
operations of macro expansion, constant folding and code generation
can be folded into concept of combinators.

Because the algebra is so simple and Joy is so trivially reflective,
the clean algebra I talked of earlier extends to the
combinators. ie. There is a clean algebra giving you the effects of
your evals. In Joy eval is not evil, its as clean as the rest of Joy.

Forth and Postscript have similar properties.

The Bottom Line
===============

The problem I foresee is that any HLL built on the LLL risks
destroying these properties and hence something precious. ie. I would
predict that for Tunes to succeed in its stated aims the HLL _will_ be
exactly the LLL, but with a excellent suite of library routines.

======================================================================
  
The main area of thought I think is needed is how do you create a good type
system and genericity on top of the Joy basis.


John Carter

The Cybernetic Entomologist - cyent@mweb.co.za

http://www.geocities.com/SoHo/Cafe/5947

"If man realized that the universe, like him, can love and suffer, he
 would be reconciled." - Camus