The Yajima Combinator in Translation

This is a follow-up to my previous post, THIS IS NOT A REVIEW. I was inspired by a comment from Julia to translate the examples Airi and Maimi wrote (in the fictional universe depicted in my last post) into Turing, from the original Scheme.

The original snippets of code were:

(printing “LOVE” an infinite number of times using named recursion in Scheme)

(define (FOREVER x)
  (display x) (FOREVER x))
   
(FOREVER "LOVE ")

(the Y combinator in Scheme)

(lambda (f)
  ((lambda (x) (f (lambda (y) ((x x) y))))
   (lambda (x) (f (lambda (y) ((x x) y))))))

(printing “LOVE” an infinite number of times using the Y combinator to do anonymous recursion in Scheme)

(((lambda (f)
   ((lambda (x) (f (lambda (y) ((x x) y))))
    (lambda (x) (f (lambda (y) ((x x) y))))))
  (lambda (p) (lambda (s) (display s) (p s))))
 "LOVE ")

Of course, the latter two examples rely on unnamed functions (lambdas), which, as it turns out, appear not to be supported at all in Turing. As a result, I could only duplicate the first example:

(printing “LOVE” an infinite number of times using named recursion in Turing)

procedure forever(x : string)
   put x ..
   forever(x)
end forever
   
forever("LOVE ")

Feeling inspired, I decided to try this out in Python. Unfortunately, while lambdas are supported in Python, they are purely functional, meaning it’s impossible to get side effects out of the recursive process like printing “LOVE” every time. You’d have to generate an infinitely long string of these and then print it out:

(printing “LOVE” an infinite number of times using named recursion in Python)

def FOREVER(x):
   print x,
   FOREVER(x)
   
FOREVER("LOVE")

(the Y combinator in Python)

(lambda f: \
  (lambda x: f(lambda y: (x(x))(y))) \
  (lambda x: f(lambda y: (x(x))(y))))

(printing “LOVE” an infinite number of times using the Y combinator to do anonymous recursion in Python, theoretically)

(lambda f: \
   (lambda x: f(lambda y: (x(x))(y))) \
   (lambda x: f(lambda y: (x(x))(y)))) \
 (lambda p: (lambda s:(s + p(s)))) \
('LOVE ')

Of course, you won’t be able to see anything from running that last one. But you can use the Y combinator to print out “LOVE” a finite number of times:

(printing “LOVE” 17 times using the Y combinator to do anonymous recursion in Python)

(lambda f: \
   (lambda x: f(lambda y: (x(x))(y))) \
   (lambda x: f(lambda y: (x(x))(y)))) \
 (lambda p: (lambda s: (s==0 and ' ') or ('LOVE ' + p(s-1)))) \
(17)

Feeling even more inspired, I decided to tackle the task of translating this into PostScript, which is totally one of the awesomest programming languages ever, even though many people who are familiar with it don’t realize its programming complexity and dismiss it as a simple page description language … ahem. (It’s the language behind PS files, the precursor to PDF.)

And behold, it worked!

(printing “LOVE” an infinite number of times using named recursion in PostScript)

/FOREVER { dup print FOREVER } def
(LOVE ) FOREVER

(the Y combinator in PostScript)

{ [ exch 
   { [ exch
         { dup cvx exec exec } aload pop
     ] cvx } aload pop
      8 -1 roll
     { cvx exec } aload pop ]
  dup cvx exec }

(printing “LOVE” an infinite number of times using the Y combinator to do anonymous recursion in PostScript)

(LOVE )
{ [ exch
   { dup 5 string cvs print
      [ exch } aload pop 8 -1 roll
         [ exch cvx { exec } aload pop ] cvx
         { aload pop ] cvx exec } aload pop ] cvx } cvlit
{ [ exch
   { [ exch
      { dup cvx exec exec } aload pop ] cvx } aload pop
    8 -1 roll { cvx exec } aload pop ]
    dup cvx exec }
exec cvx exec

And just for fun, here’s computing the factorial of 6 using the Y combinator:

6
{ [ exch { dup 0 eq exch { 1 } exch [ exch } aload pop 
         9 -1 roll [ exch { dup 1 sub } aload pop
         4 -1 roll cvx { exec } aload pop { mul } aload pop ] cvx
      { aload pop ] cvx ifelse } aload pop ] cvx } cvlit
{ [ exch { [ exch
      { dup cvx exec exec } aload pop ] cvx } aload pop
      8 -1 roll {cvx exec } aload pop ] dup cvx exec }
exec cvx exec

PostScript rocks.