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.

THIS IS NOT A REVIEW

 

CUZ I DONT DO REVIEWS YO

this is a DIALOGUE on the nature of computation brought to you by °C-ute or actually just THE AIRI AND MAIMI SHOW cuz everybody else is like wut im a computer n00b i dont even know how to type zomgwtf but AIRI AND MAIMI are like SUPER FREAKING GENIUSES or something and they totally know everything about computers and programming and data structures and algorithms and complexity theory and all that

because contrary to popular belief °C-ute is actually short for

°COMPUTE

thats right THATS A DASH your supposed to fill in the missing letters duh

(betcha didnt know that huh?)

WUT

 

oh hay look its °C-ute in the middle of their STRUCTURE AND INTERPRETATION OF COMPUTER PROGRAMS class and today their going over HIGHER ORDER PROCEDURES and how to call a procedure using another procedure as an argument or even reflexively using the procedure itself

 

so erika and mai are like WUUUHHHHHH???? but airi and maimi totally know wuts going on cuz their like SUPER FREAKING GENIUSES and their already jumping ahead to next weeks topic…..

 

and airi goes hey check this out zomglolololololol

 

… one level of embedding …

 

….. TWO levels of embedding …..

 

……. FOUR LEVELS OF EMBEDDING ……..

 

……… EIGHT LEVELS OF EMBEDDING IS THAT AMAZING OR WUT OMG???!!! ………

 

XDDDDDDDDDDDDDDDDDDDDDD

 

and maimis like WUT

 

and airis like RECURSION B****ES!!!

 

but maimis like STFU N00B that terminates after only eight iterations

betcha cant do an infinite loop wut

 

so airi sez OH YEAH WELL CHECK THIS OUT

 

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

 

SEE IT PRINTS OUT LOVE AND RECURSIVELY CALLS ITSELF SO IT CAN PRINT OUT LOVE AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN

its like LOVE …….. FOREVER!!!!!

 

wut

 

FOREVER LOVE

get it? GET IT??!!!

 

but maimis like SRSLY zomgrofl THAT IS SO TRIVIAL IT MAKES THE TRIVIAL GROUP LOOK NONCOMMUTATIVE lol

 

NONCOMMUTATIVE?????!!!!!!!

I OWN TSUUGAKU VECTOR☂

I AM THE LIVING EMBODIMENT OF THE INNER PRODUCT OF ANY TWO VECTORS IN A HILBERT SPACE

 

cuz thats like CONJUGATE SYMMETRY

which when restricted to a real scalar field means that under the inner product any two vectors COMMUTE

FOR REAL

 

oh yeah well thats nothing compared to the Y COMBINATOR

 

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

 

your procedure is so weak it needs a name zomglol

WITH THE Y COMBINATOR YOU CAN DO ANONYMOUS RECURSION ZOMGAWESOME

 

(((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 ")

LOOK NO NAMES WUT

 

………………… O__________________O ……………………

 

THATS RIGHT THE Y COMBINATOR IS SHORT FOR YAJIMA COMBINATOR!!!!!!

 

o rly?

 

YA RLY LAMBDA CALCULUS FTW

 

well lambda calculus is ok but….

 

KAPPA CALCULUS IS THE BEST!!!!!! =(^w^)=

 

and maimis like *facepalm*

 

but then saki butts in and is like

i like SKI calculus cuz its like SAKI but like without the A

 

and airi and maimi are like LOLWUT

 

 

NEXT TIME ON THE AIRI AND MAIMI SHOW FEATURING °C-UTE

WTFAWESOME BATTLE OF THE BRAINZ LIKE ZOMG

 

SUPER FREAKING GENIUS IDOLS DISCUSS COMBINATORY LOGIC AND FORMAL GRAMMARS AND THE CHOMSKY HIERARCHY AND THE COMPUTATIONAL EQUIVALENCE OF RECURSION AND TURING MACHINES!!!!!!

 

and °C-ute perform AN INTERPRETIVE DANCE interpreting THE RUNTIME EXECUTION OF A SCHEME INTERPRETER INTERPRETING ITS OWN SOURCE CODE

 

LOLWUT kthxbai <33333333 XD