FL versus Joy

[John Nowak]

Here's a quick example to support the claim I've made previously that  
having all terms denote functions throughout the reduction process  
greatly simplifies things.

Here's the Joy version:

   PRIMITIVES:
   [X] dup      ==  [X] [X]
   [X] i        ==  X
   [X] [Y] dip  ==  Y [X]

   USER-DEFINED:
   twice  = dup dip i
   square = dup mul
   double = dup add

   EVALUATE:
   5 [sq] twice double
   5 [sq] dup dip i double
   5 [sq] [sq] dip i double
   5 sq [sq] i double
   5 dup mul [sq] i double
   5 5 mul [sq] i double
   25 [sq] i double
   25 sq double
   25 dup mul double
   25 25 mul double
   625 double
   625 dup add
   625 625 add
   1250

And here's the FL version:

   PRIMITIVES:
   (C:f):x:y  ==  (f . [~x, id]):y  ==  f:<x:y>

   USER-DEFINED:
   twice  = C:(apply.[a, apply])
   square = mul . [id, id]
   double = add . [id, id]

   EVALUATE:
   (double . twice:sq) : 5
   (double . (C:(apply . [a, apply])):sq) : 5
   (double . apply . [a, apply] . [~sq, id]) : 5
   (double . apply . [a, apply]) : [~sq, id] : 5
   (double . apply . [a, apply]) : <~sq:5, id:5>
   (double . apply . [a, apply]) : <sq, id:5>
   (double . apply . [a, apply]) : <sq, 5>
   (double . apply) : [a, apply] : <sq, 5>
   (double . apply) : <a:<sq, 5>, apply:<sq, 5>>
   (double . apply) : <sq, apply:<sq, 5>>
   (double . apply) : <sq, apply:<mul . [id, id], 5>>
   (double . apply) : <sq, (mul . [id, id]) : 5>
   (double . apply) : <sq, mul : <id:5, id:5>>
   (double . apply) : <sq, mul : <5, id:5>>
   (double . apply) : <sq, mul : <5, 5>>
   (double . apply) : <sq, 25>
   double : sq : 25
   double : ((mul . [id, id]) : 25)
   double : mul : [id, id] : 25
   double : mul : <id:25, id:25>
   double : mul : <25, id:25>
   double : mul : <25, 25>
   double : 625
   (add . [id, id]) : 625
   add : [id, id] : 625
   add : <id:625, id:625>
   add : <625, id:625>
   add : <625, 625>
   1250

Forgive me for not explaining how FL works again. If you're  
interested, see this paper:
http://www.cs.berkeley.edu/~aiken/ftp/FL.ps

- John

[John Nowak]

And just to really waste everyone's time...

Here's the same reduction in my proposed FL variant. Here, all terms  
denote functions, parentheses are quotation, square brackets are  
construction, and juxtaposition is composition.

   PRIMITIVES:
   i [(F), X] = F X
   hd [A, B]  = A

   USER-DEFINED:
   dup    = [id, id]
   square = mul dup
   double = add dup
   twice  = i [hd, i]

   EVALUATE:
   double twice [(square), id] 5
   double twice [(square) 5, id 5]
   double twice [(square), id 5]
   double twice [(square), 5]
   double i [hd, i] [(square), 5]
   double i [hd [(square), 5], i [(square), 5]]
   double i [(square), square 5]
   double i [(square), mul dup 5]
   double i [(square), mul [id, id] 5]
   double i [(square), mul [id 5, id 5]]
   double i [(square), mul [5, id 5]]
   double i [(square), mul [5, 5]]
   double i [(square), 25]
   double (square) 25
   double mul dup 25
   double mul [id, id] 25
   double mul [id 25 , id 25]
   double mul [25 , id 25]
   double mul [25 , 25]
   double 625
   add dup 625
   add [id, id] 625
   add [id 625, id 625]
   add [625, id 625]
   add [625, 625]
   1250

Very straightforward, if a little long because I was very explicit.  
Here's the same thing removing some of the trivial steps involving  
construction:

   double twice [(square), id] 5
   double twice [(square), 5]
   double i [hd, i] [(square), 5]
   double i [(square), i [(square), 5]]
   double i [(square), square 5]
   double i [(square), mul dup 5]
   double i [(square), mul [id, id] 5]
   double i [(square), mul [5, 5]]
   double i [(square), 25]
   double square 25
   double mul [id, id] 25
   double mul [25, 25]
   double 625
   add dup 625
   add [id, id] 625
   add [625, 625]
   1250

Definitely a lot nicer than FL I think. One thing you'd want is a  
syntax for '[(F), id]', probably ':(F)' or something along those  
lines. 'twice:(square)' is better than 'twice [(square), id]'. Of  
course, other options exist.

- John