Although JavaScript interpreter does not have to be tail call optimized, and I believe most of them are not, JavaScript have closures and functions are first class objects. Hence it is possible to write in JavaScript applicative Y combinator.
In this short text I will start with a simple recursive factorial function written in JavaScript and by modifying it again and again I will transform the code into two methods Y and F such that Y handles the recursion and F handle the factorial logic.
It is worth to mention that once one have those methods, they can be used without naming (anonymously).
Starting with:
var factorial = function(n) {
if (n === 0) {
return 1;
} else {
return n * factorial(n - 1);
}
};
The first change is to create a factorial factory and use it instead the direct call.
var f = function() {
return function(n) {
if (n === 0) {
return 1;
} else {
return n *f( )(n - 1);
}
};
};
Now instead of factorial(6) we call f()(6).
Next we change the factory method r to receive one argument, this argument will be always a factorial factory itself.
var f = function(f) {
return function(n) {
if (n === 0) {
return 1;
} else {
return n * f(f)(n - 1);
}
};
};
Now the call has changed to something like f(f)(6).
When substituting r’s body with r in the call above we have:
When substituting r’s body with r in the call above we have:
function(f) {
return function(n) {
if (n === 0) {
return 1;
} else {
return n * f(f)(n - 1);
}
};
}
(function(f) {
return function(n) {
if (n === 0) {
return 1;
} else {
return n * f(f)(n - 1);
}
};
})(6)
The next transformation is reverse eta conversion (η-conversion)
f(f)(n) => function(a){ return f(f)a}(n), this delays the computation of f(f(n) and prevent infinite loop because of the evaluation order in applicative order.
function(f) {
return function(n) {
if (n === 0) {
return 1;
} else {
return n * ((function(a) {
return f(f)(a);
})(n - 1));
}
};
}
(function(f) {
return function(n) {
if (n === 0) {
return 1;
} else {
return n * ((function(a) {
return f(f)(a);
})(n - 1));
}
};
})(6);
Now (function(a) {
return f(f)(a);
})
can be extracted out we will do that by wrapping everything in a new function call with param r and passing it the expression (function(a) {
return f(f)(a);
})
To the function
function(f) {
return function(r) {
return function(n) {
if (n === 0) {
return 1;
} else {
return n * r(n - 1);
}
};
}(function(a) {
return f(f)(a);
});
}
(function(f) {
return (function(r) {
return function(n) {
if (n === 0) {
return 1;
} else {
return n * r(n - 1);
}
};
})(function(a) {
return f(f)(a);
});
})
Now we do the same with the pink expression and have:
function(m) {
return function(f) {
return m(function(a) {
return f(f)(a);
});
}(function(f) {
return m(function(a) {
return f(f)(a);
});
})(function(r) {
return function(n) {
if (n === 0) {
return 1;
} else {
return n * r(n - 1);
}
};
});
Hence we have 2 functions
var y = function(m) {
return function(f) {
return m(function(a) {
return f(f)(a);
});
}(function(f) {
return m(function(a) {
return f(f)(a);
});
});
and:
var fact = function(r) {
return function(n) {
if (n === 0) {
return 1;
} else {
return n * r(n - 1);
}
};
}
and
y(fact)(6) => 720
Great information, glad to find your post! Kentico Development
ReplyDeleteIt is quite beneficial, thank you. rental lease agreement form
ReplyDeleteThanks for sharing the information through the article. last will and testament form
ReplyDeleteThanks for sharing the information through the article. Residential property management Toronto
ReplyDeleteGreat post! Nice information keep sharing, Thank you. first class flights to san francisco
ReplyDeleteBursa
ReplyDeleteMersin
izmir
Rize
Antep
VFMJE
bilecik
ReplyDeletevan
elazığ
tokat
uşak
KQL7BX
ankara parça eşya taşıma
ReplyDeletetakipçi satın al
antalya rent a car
antalya rent a car
ankara parça eşya taşıma
1UA
44896
ReplyDeleteRize Parça Eşya Taşıma
Çorum Parça Eşya Taşıma
Konya Parça Eşya Taşıma
Burdur Lojistik
Malatya Lojistik
91750
ReplyDeleteMuş Evden Eve Nakliyat
Denizli Parça Eşya Taşıma
Tekirdağ Şehir İçi Nakliyat
Sivas Şehir İçi Nakliyat
Antep Lojistik
Nevşehir Şehirler Arası Nakliyat
Karabük Lojistik
Çorum Lojistik
Eskişehir Parça Eşya Taşıma
6AFCD
ReplyDeleteBinance Referans Kodu
Iğdır Şehirler Arası Nakliyat
Ünye Organizasyon
Samsun Evden Eve Nakliyat
Çankaya Parke Ustası
Rize Parça Eşya Taşıma
Batıkent Fayans Ustası
Coinex Güvenilir mi
Adana Şehir İçi Nakliyat
946CA
ReplyDeletedeca durabolin
dianabol methandienone
trenbolone enanthate for sale
buy parabolan
Sinop Evden Eve Nakliyat
buy turinabol
order peptides
Kırşehir Evden Eve Nakliyat
Rize Evden Eve Nakliyat
86789
ReplyDelete%20 indirim kodu
D8B06
ReplyDeleteKilis Sesli Sohbet Odası
bartın random görüntülü sohbet
çorum rastgele canlı sohbet
ücretsiz sohbet odaları
Karaman Canli Sohbet Chat
aydın telefonda sohbet
manisa parasız sohbet
Çorum Telefonda Kadınlarla Sohbet
Ardahan Kadınlarla Rastgele Sohbet
شركة عزل اسطح بالمزاحمية EHFeYpoIzZ
ReplyDelete