FL versus Joy

John Nowak — 2009-03-20 10:21:15

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 — 2009-03-20 10:52:51

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