You are currently browsing the tag archive for the ‘Anonymous recursion’ tag.

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.

Advertisements

Remixes

DJ Kirarin☆Snow ☃'s remixes are now appearing at K!☆Mixed.
October 2017
S M T W T F S
« Feb    
1234567
891011121314
15161718192021
22232425262728
293031  

Categories

Blog Stats

  • 70,484 hits