From: jweirich@...
Date: 2001-08-28T21:13:27+09:00
Subject: [ruby-talk:20469] Re: recursive lambda forms

>>>>> "Alexander" == Alexander Schofield <theschof@cs.com> writes:

    Alexander> It occurs to me that being able to create recursive
    Alexander> lambda forms should be possible in any language where a
    Alexander> method is an object.  Just as "self", refers to the
    Alexander> object a method belongs to, shouldn't there be a
    Alexander> reserved word (or optional argument specified with
    Alexander> different syntax, maybe %?) for the Method or Proc
    Alexander> object itself?  This way a method could call itself
    Alexander> without knowing in advance what it was going to be
    Alexander> called.

    Alexander> Aside from defining a named method and creating a
    Alexander> reference to it, is there any already existing way to
    Alexander> do what I'm think of?

This isn't exactly what you want, but it reminds me of a "problem"
involving a Y-Combinator.  This was a fun puzzle, so I'll post it here
for entertainment purposes only.

The Y-Combinator "solves" the problem of recursive anonymous lambda
functions (proc's), with the additional constraint that lamdba binding
is the only way to associate values and names.  In other words,
assignments are not allowed.

If assignments are allowed, a recursive version of factorial can be
done like this ...

fact = proc { |n|
  if n == 0
     1
  else
     fact.call(n-1)
  end
}

If we using only lambda binding, then we would have to write something
like

proc { |fact|
  proc { |n|
    if n == 0
      1
    else
      fact.call(n-1)
    end
  }
}

where "fact" is bound to the factorial function.  Unfortunately, it
seems we have a chicken and egg problem because the factorial function
is exactly what we are trying to write in the first place.

The Y-combinator will take the above form and turn it into a real
factorial without infinite recursion or exploding (just kidding about
the exploding part).

The following code will demonstrates the Y-combinator written in Ruby.
If this hurts your head, you should see the version done in Java using
inner classes!

######################################################################
# Program: Y
# Purpose: Demonstrate the Y-Combinator in Ruby
# Author:  Jim Weirich
# Why:     Because everybody else was doing it in Perl and I wanted
#          to be different.
# Usage:   java Y `number'
#
# Discussion:
#
# The Y-Combinator is a way of using lambda calculus to bind
# functions to names for recursive calling.  Its purpose is to
# demonstrate that Lambda calculus is theoritically sufficient for
# all compuational processes.
#
# I used the definition of the Y-Combinator from Friedman's "The
# Little Schemer", page 172.  He defines it (in Scheme of course) as:
#
# (define Y
#   (lambda (le)
#    ((lambda (f) (f f))
#     (lambda (f)
#       (le (lambda (x) ((f f) x))) ) ) ) )
#
# Y takes an argument that is a function generator.  To use Y, just
# define a function that takes an function as an argument and then
# codes the recursive definition using the argument.  For example,
# the recursive factorial function generator could be defined ...
#
# (define F
#   (lambda (proc)
#     (lambda (n)
#       (if (zero? n)
#	     1
#	     (* n (proc (- n 1))) ))))
#
# In order to calculate the factorial of 5, you would invoke:
#
#     ((Y F) 5)
#
# A fully expanded Y-Combinator/Function-generator expression would
# look like:
#
#      (((lambda (le)
# 	   ((lambda (f) (f f))
# 	    (lambda (f)
# 	      (le (lambda (x) ((f f) x))) ) ) )
# 	 (lambda (proc)
# 	   (lambda (n)
# 	     (if (zero? n)
# 		 1
# 		 (* n (proc (- n 1))) ))) ) 5)
#
# Evaluating the above expression yields: 120
#
# Translation to Ruby
# -------------------
#
# The following Ruby program is a fairly straightforward translation
# of the above Scheme expressions.  We shall use proc's as the Ruby
# version of lambda expressions.  
#
# The following bit of code creates a lambda function that adds 1 to
# its argument and applies the newly created function to the number 5:
#
#    proc {|arg| arg+1}.call(5)
#
# Scheme Equivalent:
#    ((lambda (arg) (+ arg 1)) 5)
#
# The following calculates the factorial of the command line argument
# using only Lambda functions.
#
# Are you ready?  First, we will do it the easy way, using Y to hold
# the combinator expression and F to hold the factorial proto
# function.
# --------------------------------------------------------------------

F = proc { |recurse|
  proc { |n|
    if n == 0 then
      1
    else
      n * recurse.call (n-1)
    end
  }
}

Y = proc { |builder|
  proc { |f| f.call(f) } \
  .call ( proc { |f|
	   builder.call (proc { |x| f.call(f).call(x) }) })
}

p Y.call(F).call(5)		# prints "120"

# --------------------------------------------------------------------
# Now the hard way, in a single expression without any free variables.
# This is the same as the above expression, except that we have
# explicitly replaced the variables Y and F with their expressions.
# --------------------------------------------------------------------

p proc { |le|
  proc { |f| f.call(f) } \
  .call ( proc { |f|
	   le.call (proc { |x| f.call(f).call(x) }) })
}.call(proc { |recurse|
  proc { |n|
    if n == 0 then
      1
    else
      n * recurse.call (n-1)
    end
  }
}).call(5)			# prints "120"


-- 
-- Jim Weirich     jweirich@one.net    http://w3.one.net/~jweirich
---------------------------------------------------------------------
"Beware of bugs in the above code; I have only proved it correct, 
not tried it." -- Donald Knuth (in a memo to Peter van Emde Boas)