digitalmars.D.learn - Memoization in compile-time
- Dennis Ritchie (23/23) Mar 12 2015 Is it possible to run this code in compile-time?
- Rikki Cattermole (18/39) Mar 12 2015 Here is an example I have in my Developing with compile time in mind
- Dennis Ritchie (17/19) Mar 13 2015 And this code can be rewritten to D?
- Meta (42/62) Mar 13 2015 You can translate it directly:
- Dennis Ritchie (2/68) Mar 13 2015 Thanks.
- Dennis Ritchie (1/1) Mar 13 2015 And you can somehow memoization stuff at compile time?
- Meta (5/6) Mar 13 2015 If you want memoization at compile time I would suggest using the
- =?UTF-8?B?QWxpIMOHZWhyZWxp?= (29/30) Mar 13 2015 Scarily simple. :D
- =?UTF-8?B?QWxpIMOHZWhyZWxp?= (14/15) Mar 13 2015 Oops! That's generally a trap! The array better be 'static' because a
- Dennis Ritchie (4/20) Mar 13 2015 Thanks.
- =?UTF-8?B?QWxpIMOHZWhyZWxp?= (4/6) Mar 13 2015 Yes, run-time is always possible and if it can be computed at compile
- Dennis Ritchie (2/8) Mar 13 2015 Thanks.
- weaselcat (8/28) Mar 13 2015 confusingly, D uses enum for named compile-time constants.
- weaselcat (3/35) Mar 13 2015 woops, walked away to get coffee before I submitted and got
- =?UTF-8?B?QWxpIMOHZWhyZWxp?= (13/15) Mar 13 2015 Actually, 'static' works as well. I have enumerated the cases here:
Is it possible to run this code in compile-time?
import std.stdio, std.functional;
ulong fact(ulong n)
{
alias mfact = memoize!fact;
return n < 2 ? 1 : n * mfact(n - 1);
}
void main() {
writeln(fact(10));
}
In CommonLisp variable *factorial-cache* available in CT, and RT.
Moreover, in the compiler environment of your *factorial-cache*
and RT. Thus we memoires as calculations in CT (constants), and
RT.
(eval-always
(defparameter *factorial-cache* (make-hash-table))
(defun factorial (n)
(if (< n 1)
1
(setf (gethash n *factorial-cache*) (* n (factorial (1-
n)))))))
(define-compiler-macro factorial (&whole whole n)
(if (constantp n) (factorial n) whole))
Mar 12 2015
On 13/03/2015 2:23 p.m., Dennis Ritchie wrote:
Is it possible to run this code in compile-time?
import std.stdio, std.functional;
ulong fact(ulong n)
{
alias mfact = memoize!fact;
return n < 2 ? 1 : n * mfact(n - 1);
}
void main() {
writeln(fact(10));
}
In CommonLisp variable *factorial-cache* available in CT, and RT.
Moreover, in the compiler environment of your *factorial-cache* and RT.
Thus we memoires as calculations in CT (constants), and RT.
(eval-always
(defparameter *factorial-cache* (make-hash-table))
(defun factorial (n)
(if (< n 1)
1
(setf (gethash n *factorial-cache*) (* n (factorial (1- n)))))))
(define-compiler-macro factorial (&whole whole n)
(if (constantp n) (factorial n) whole))
Here is an example I have in my Developing with compile time in mind
book[0]:
size_t factorial(size_t n) pure {
assert(n < 11);
if (n == 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
static assert(factorial(5) == 120);
Notice how it is in a static assert? Yeah that is at compile time.
You could assign it to e.g. an enum. Or force it over using
meta-programming.
If you haven't already, I would strongly recommend that you read my book
on the subject.
[0] https://leanpub.com/ctfe
Mar 12 2015
On Friday, 13 March 2015 at 02:38:18 UTC, Rikki Cattermole wrote:You could assign it to e.g. an enum. Or force it over using meta-programming.And this code can be rewritten to D? template <int n> struct Factorial { enum { value = n * Factorial<n - 1>::value }; }; template <> struct Factorial<0> { enum { value = 1 }; }; int main() { constexpr auto x = Factorial<5>::value; constexpr auto y = Factorial<7>::value; }
Mar 13 2015
On Friday, 13 March 2015 at 12:49:48 UTC, Dennis Ritchie wrote:On Friday, 13 March 2015 at 02:38:18 UTC, Rikki Cattermole wrote:You can translate it directly: template Factorial(int n) { static if (n == 0) { enum Factorial = 1; } else static if (n > 0) { enum Factorial = n * Factorial!(n - 1); } else { static assert(false, "n cannot be negative"); } } int main() { //Calculated at compile time auto x = Factorial!5; auto y = Factorial!7; } However, it's much easier to just write a function and decide whether you want to calculate its value at runtime or compile time. int factorial(int n) in { assert(n >= 0, "n cannot be 0"); } body { return n == 0 ? 1 : n * factorial(n - 1); } void main() { //Evaluated at compile time enum x = factorial(5); //Evaluated at runtime auto y = factorial(7); }You could assign it to e.g. an enum. Or force it over using meta-programming.And this code can be rewritten to D? template <int n> struct Factorial { enum { value = n * Factorial<n - 1>::value }; }; template <> struct Factorial<0> { enum { value = 1 }; }; int main() { constexpr auto x = Factorial<5>::value; constexpr auto y = Factorial<7>::value; }
Mar 13 2015
"Dennis Ritchie" <dennis.ritchie mail.ru> On Friday, 13 March 2015 at 12:58:13 UTC, Meta wrote:On Friday, 13 March 2015 at 12:49:48 UTC, Dennis Ritchie wrote:Thanks.On Friday, 13 March 2015 at 02:38:18 UTC, Rikki Cattermole wrote:You can translate it directly: template Factorial(int n) { static if (n == 0) { enum Factorial = 1; } else static if (n > 0) { enum Factorial = n * Factorial!(n - 1); } else { static assert(false, "n cannot be negative"); } } int main() { //Calculated at compile time auto x = Factorial!5; auto y = Factorial!7; } However, it's much easier to just write a function and decide whether you want to calculate its value at runtime or compile time. int factorial(int n) in { assert(n >= 0, "n cannot be 0"); } body { return n == 0 ? 1 : n * factorial(n - 1); } void main() { //Evaluated at compile time enum x = factorial(5); //Evaluated at runtime auto y = factorial(7); }You could assign it to e.g. an enum. Or force it over using meta-programming.And this code can be rewritten to D? template <int n> struct Factorial { enum { value = n * Factorial<n - 1>::value }; }; template <> struct Factorial<0> { enum { value = 1 }; }; int main() { constexpr auto x = Factorial<5>::value; constexpr auto y = Factorial<7>::value; }
Mar 13 2015
And you can somehow memoization stuff at compile time?
Mar 13 2015
On Friday, 13 March 2015 at 13:51:43 UTC, Dennis Ritchie wrote:And you can somehow memoization stuff at compile time?If you want memoization at compile time I would suggest using the template version of Factorial as template instantiations are cached by the compiler. However, std.functional.memoize may work as well at compile time, I don't know.
Mar 13 2015
On 03/13/2015 06:51 AM, Dennis Ritchie wrote:And you can somehow memoization stuff at compile time?Scarily simple. :D import std.stdio; enum N = 15; enum int[] factorials = memoizeFactorials(N); int[] memoizeFactorials(int n) { if (!__ctfe) { // Make sure that this function is never called at run time assert(false); } int[] result = new int[n]; result[0] = 1; foreach (i; 1 .. n) { result[i] = result[i - 1] * i; } return result; } int fact(int n) { return factorials[n]; } void main() { foreach (i; 0 .. N) { writeln(fact(i)); } } Ali
Mar 13 2015
On 03/13/2015 11:28 AM, Ali Çehreli wrote:enum int[] factorials = memoizeFactorials(N);Oops! That's generally a trap! The array better be 'static' because a manifest constant like 'enum factorials' would be inserted everywhere it is used. (Similar to a C macro.) I've been scratching my head why the assertion below was failing. It sould be 'static': static int[] factorials = memoizeFactorials(N); If it's an enum, the following assert will fail: foreach (i; 0 .. N) { assert(factorials.ptr + i == &(factorials[i])); } Make it a 'static', it will pass because then there will be just one factorials array. Ali
Mar 13 2015
On Friday, 13 March 2015 at 18:38:16 UTC, Ali Çehreli wrote:On 03/13/2015 11:28 AM, Ali Çehreli wrote:Thanks. And you can make the same memoized variable was available at compile time and at run time? :)enum int[] factorials = memoizeFactorials(N);Oops! That's generally a trap! The array better be 'static' because a manifest constant like 'enum factorials' would be inserted everywhere it is used. (Similar to a C macro.) I've been scratching my head why the assertion below was failing. It sould be 'static': static int[] factorials = memoizeFactorials(N); If it's an enum, the following assert will fail: foreach (i; 0 .. N) { assert(factorials.ptr + i == &(factorials[i])); } Make it a 'static', it will pass because then there will be just one factorials array. Ali
Mar 13 2015
On 03/13/2015 12:09 PM, Dennis Ritchie wrote:And you can make the same memoized variable was available at compile time and at run time? :)Yes, run-time is always possible and if it can be computed at compile time, compile-time is also possible. Ali
Mar 13 2015
On Friday, 13 March 2015 at 21:16:24 UTC, Ali Çehreli wrote:On 03/13/2015 12:09 PM, Dennis Ritchie wrote:Thanks.And you can make the same memoized variable was available atcompiletime and at run time? :)Yes, run-time is always possible and if it can be computed at compile time, compile-time is also possible.
Mar 13 2015
On Friday, 13 March 2015 at 12:49:48 UTC, Dennis Ritchie wrote:On Friday, 13 March 2015 at 02:38:18 UTC, Rikki Cattermole wrote:confusingly, D uses enum for named compile-time constants. http://ddili.org/ders/d.en/enum.html If you take Rikki's example and apply it to an enum(i.e, enum x = factorial(5); ) the program will fail to compile if it can't be computed at compile-time.You could assign it to e.g. an enum. Or force it over using meta-programming.And this code can be rewritten to D? template <int n> struct Factorial { enum { value = n * Factorial<n - 1>::value }; }; template <> struct Factorial<0> { enum { value = 1 }; }; int main() { constexpr auto x = Factorial<5>::value; constexpr auto y = Factorial<7>::value; }
Mar 13 2015
On Friday, 13 March 2015 at 13:16:27 UTC, weaselcat wrote:On Friday, 13 March 2015 at 12:49:48 UTC, Dennis Ritchie wrote:woops, walked away to get coffee before I submitted and got beaten to the punch by a better answer : )On Friday, 13 March 2015 at 02:38:18 UTC, Rikki Cattermole wrote:confusingly, D uses enum for named compile-time constants. http://ddili.org/ders/d.en/enum.html If you take Rikki's example and apply it to an enum(i.e, enum x = factorial(5); ) the program will fail to compile if it can't be computed at compile-time.You could assign it to e.g. an enum. Or force it over using meta-programming.And this code can be rewritten to D? template <int n> struct Factorial { enum { value = n * Factorial<n - 1>::value }; }; template <> struct Factorial<0> { enum { value = 1 }; }; int main() { constexpr auto x = Factorial<5>::value; constexpr auto y = Factorial<7>::value; }
Mar 13 2015
On 03/13/2015 06:16 AM, weaselcat wrote:confusingly, D uses enum for named compile-time constants. http://ddili.org/ders/d.en/enum.htmlActually, 'static' works as well. I have enumerated the cases here: http://ddili.org/ders/d.en/functions_more.html#ix_functions_more.CTFE <quote> For a function to be executed at compile time, it must appear in an expression that in fact is needed at compile time: - Initializing a static variable - Initializing an enum variable - Calculating the length of a fixed-length array - Calculating a template value argument </quote> Are there other cases that is worth adding to that list? Ali
Mar 13 2015