How to resolve the algorithm Y combinator step by step in the Verbexx programming language
How to resolve the algorithm Y combinator step by step in the Verbexx programming language
Table of Contents
Problem Statement
In strict functional programming and the lambda calculus, functions (lambda expressions) don't have state and are only allowed to refer to arguments of enclosing functions. This rules out the usual definition of a recursive function wherein a function is associated with the state of a variable and this variable's state is used in the body of the function. The Y combinator is itself a stateless function that, when applied to another stateless function, returns a recursive version of the function. The Y combinator is the simplest of the class of such functions, called fixed-point combinators.
Define the stateless Y combinator and use it to compute factorials and Fibonacci numbers from other stateless functions or lambda expressions.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Y combinator step by step in the Verbexx programming language
Source code in the verbexx programming language
/////// Y-combinator function (for single-argument lambdas) ///////
y @FN [f]
{ @( x -> { @f (z -> {@(@x x) z}) } ) // output of this expression is treated as a verb, due to outer @( )
( x -> { @f (z -> {@(@x x) z}) } ) // this is the argument supplied to the above verb expression
};
/////// Function to generate an anonymous factorial function as the return value -- (not tail-recursive) ///////
fact_gen @FN [f]
{ n -> { (n<=0) ? {1} {n * (@f n-1)}
}
};
/////// Function to generate an anonymous fibonacci function as the return value -- (not tail-recursive) ///////
fib_gen @FN [f]
{ n -> { (n<=0) ? { 0 }
{ (n<=2) ? {1} { (@f n-1) + (@f n-2) } }
}
};
/////// loops to test the above functions ///////
@VAR factorial = @y fact_gen;
@VAR fibonacci = @y fib_gen;
@LOOP init:{@VAR i = -1} while:(i <= 20) next:{i++}
{ @SAY i "factorial =" (@factorial i) };
@LOOP init:{ i = -1} while:(i <= 16) next:{i++}
{ @SAY "fibonacci<" i "> =" (@fibonacci i) };
You may also check:How to resolve the algorithm Disarium numbers step by step in the Go programming language
You may also check:How to resolve the algorithm Euler's sum of powers conjecture step by step in the REXX programming language
You may also check:How to resolve the algorithm Password generator step by step in the FutureBasic programming language
You may also check:How to resolve the algorithm Substring/Top and tail step by step in the Logo programming language
You may also check:How to resolve the algorithm Probabilistic choice step by step in the Nim programming language