Monthly Archives: December 2013

Lambda-calculus recursion with factorial example (Part 2, anonymous recursive function – fixpoint)

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)

On my last post I presented a solution to write the recursive factorial function with anonymous recursive function, but there is a better and more general way to write recursive functions, it is called fix-point combinator and one well-known (and perhaps the simplest) fixed-point combinator in the untyped lambda-calculus is called the Y combinator. It was discovered by Haskell B. Curry, and is defined as:

Y = {lambda}f.({lambda}x.f (x x)) ({lambda}x.f (x x))

Translating lambda-calculus to JavaScript is not a easy task because they do not operate in the same way. JavaScript is a practical programming language and lambda-calculus is a theoretical language that is much more close to a simple mechanical operation.

Example:

function add (a, b) { return a + b;}

In lambda-calculus this should be written in JavaScript as:

function add (a) {
   return function (b) {
        return (a+b)
   }
}

And execution is like this:

add (1) (2);

Everything in lambda-calculus is mostly functions, and all function are lazy evaluated, this is important when we want to translate lambda-calculus to JavaScript because JavaScript evaluates most of expression early.

Fixpoint Y-Combinator in JavaScript

This is one of does examples that are much more simple in lambda-calculus that are in JavaScript or maybe I am just misunderstanding the Y fix-point combinator…
Anyway this is what I got:

function Y (f) 
  {return function (x) {
    return function () { 
      return f (
	function () {return x (x);}
      )
      (
        function (x) {
	  return function () {
	    return f (
	      function (x) {return x(x);}
	    );
	}
      }
    );
   }
  }
}

You can see that all functions return a function as result but this is mostly because we don’t want the function to be executed right away, we want to return a function as result and then apply it if necessary, otherwise we will make a infinity function call that would result in stack overflow.

Writing Factorial with Fixpoint Y-Combinator in JavaScript

The factorial function,

function factorial (n) {
  if (n === 0) {
     return 1;
  }
  else if (n > 0) {
     return factorial (n-1) * n;
  }
}

Now I need to change the function to work with the Y combinator, something like this:

function fact (self) {
	return function () {
        // I think this dummy function is unnecessary 
        // but this is executed with no argument at 
        // initialization and I don't know why...
		return function (n) {
			if (n === 0) {
				return 1;
			}
			else if (n > 0) {
				return (self () (self) (n-1)) * n;
			}
		}
	};
}

Once again I return functions to avoid early execution. The function self is not really the function itself but the function constructed with the Y combinator.

The recursive function is initialized like this:

var factorial = Y (fact) (Y (fact)) ();

console.log (factorial (0)); // print 1
console.log (factorial (4)); // print 24

Putting it all together!

Next code is kind of messy thats why I am wondering if this is the correct way to do it, but it works…

console.log (

function (
  Y
) {
  return function (fact) {
    return function (factorial) {
      return "factorial (0) = " + factorial(0) + "n" +
	     "factorial (1) = " + factorial(1) + "n" +
	     "factorial (2) = " + factorial(2) + "n" +
	     "factorial (3) = " + factorial(3) + "n" +
	     "factorial (4) = " + factorial(4) + "n" +
	     "factorial (5) = " + factorial(5) + "n" ;
    } (
      Y (fact) (Y(fact)) ()
    )
 } (
   function (self) {
     return function () {
       return function (n) {
	 if (n === 0) {
	   return 1;
	 }
	 else if (n > 0) {
	     return (self () (self) (n-1)) * n;
      	 }
       }
     };
   }
   );
}
(
  function (f) {
    return function (x) {
      return function () { 
	return f (
	  function () {return x (x);}
	)
	(
	  function (x) {
	    return function () {
	      return f (
		function (x) {return x (x);}
	      );
	    }
	  }
	);
      }
    }
})

);

The output would be

factorial (0) = 1
factorial (1) = 1
factorial (2) = 2
factorial (3) = 6
factorial (4) = 24
factorial (5) = 120

Other way

When I was playing with fix-points I made a code prototype that actually works, but is much more simple than the code above so something must be wrong,
anyway the code is very simple,

function (
  fixpoint	
) {
  return function (
    factorial
  ) {
    // execute factorial  
    return factorial (4); // return 24
  } (
    fixpoint (function (fact) {
      return function (n) {
	if (n === 0) {
	  return 1;
        }
	else if (n > 0) {
	  return fact (fact) (n-1) * n;
	}
      }
    })
  );
} (
	function fixpoint (f) {
		return function (x) {
			return x (x);
		} (
			function (x) {
				return f (x);	
			}
		)
	}
};
)
What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)

Lambda-calculus recursion with factorial example (Part 1, Recursive anonymous functions)

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)

Hi,

My last post about lambda-calculus just sucks, I know that because most of my readers (almost 3 people) voted that it sucks. So this time I will try to write a more interesting and fun post :) and whats better than recursive functions, especially if they are anonymous.

First lets write a nice factorial function in JavaScript:

function factorial (n) {
    if (n === 0) {
        return 1;
    }
    else if (n > 0) {
        return factorial (n-1) * n;
    }
};

Recursive anonymous functions

Now the interesting part is that lambda-calculus only uses anonymous functions, so the
above function must be rewritten, the next section is a solution that I came up with:

  1. A function parameter can be used to “name” a function like this,

    function (factorial, n) { ... }
    
  2. Since we added a new argument to the function we need to modify the call to reflect the changes,

    function (factorial, n) {
        if (n === 0) {
            return 1;
        }
        else if (n > 0) {
            return factorial (factorial, n-1) * n;
        }
    };
    
  3. now we only need a function to call the recursive process,

    function (factorial, n) {
        return factorial(factorial, n);
    }
    (
        function (factorial, n) {
            if (n === 0) {
                return 1;
            }
            else if (n > 0) {
                return factorial (factorial, n-1) * n;
            }
        },
        3 // Calculate 3!, result 6
    );
    
  4. and just for convenience we can use parameters to give a function “name” instead of applying values directly to the definition,

    alert (
    function (factorial) {
       return " => " + factorial (0) + ", " + factorial (1) + ", " + factorial (3);
    } (
        function (n) {
            return function (factorial, n) {
                return factorial (factorial, n);
            }
            (
                function (factorial, n) {
                    if (n === 0) {
                        return 1;
                    }
                    else if (n > 0) {
                        return factorial (factorial, n-1) * n;
                    }
                },
                n
            )
        }
    )
    );

Using a mix of JavaScript and lambda-calculus the previews function will look like this:

(
  {lambda}factorial.factorial 3 // calculate 3!
)(
  // function (n)
  {lambda}n.
    // function (factorial, n) {return factorial(factorial,n)}
    ({lambda}factorial n.factorial factorial n)
    // and finally the actual factorial function,
    (
       {lambda}factorial n.
           if (n === 0) {lbrace} 1 {rbrace} 
           else if (n > 0) {lbrace} (factorial factorial n-1) * n {rbrace}
    )
)

And thats it, on next parts I will talk about lambda-calculus logical expression like if-then-else and natural numbers representation and handling.

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)