feat(sterni/nix/fun): implement tail call “optimization” for Nix r/3834

I've had the notion that builtins.genericClosure can be used to express
any recursive algorithm, but a proof is much better than a notion of
course! In this case we can easily show this by implementing a function
that converts a tail recursive function into an application of
builtins.genericClosure.

This is possible if the function resolves its self reference using a
fixed point which allows us to pass a function that encodes the call to
self in a returned attribute set, leaving the actual call to
genericClosure's operator. Additionally, some tools for collecting meta
data about functions (argCount) and calling arbitrary functions (apply,
unapply) are necessary.

Change-Id: I7d455db66d0a55e8639856ccc207639d371a5eb8
Reviewed-on: https://cl.tvl.fyi/c/depot/+/5292
Tested-by: BuildkiteCI
Reviewed-by: sterni <sternenseemann@systemli.org>
Autosubmit: sterni <sternenseemann@systemli.org>

1 files changed, 53 insertions, 0 deletions

diff --git a/users/sterni/nix/fun/tests/default.nix b/users/sterni/nix/fun/tests/default.nix
index f02f199433..6b1e6fcc7b 100644
--- a/users/sterni/nix/fun/tests/default.nix
+++ b/users/sterni/nix/fun/tests/default.nix
@@ -7,6 +7,8 @@ let
     assertEq
     ;
 
+  inherit (depot.nix) escapeExecline;
+
   inherit (depot.users.sterni.nix)
     fun
     ;
@@ -23,7 +25,58 @@ let
     (assertEq "Ellipsis" true
       (fun.hasEllipsis ({ depot, pkgs, ... }: 42)))
   ];
+
+  argCountTests = it "checks fun.argCount" [
+    (assertEq "builtins.sub has two arguments" 2
+      (fun.argCount builtins.sub))
+    (assertEq "fun.argCount has one argument" 1
+      (fun.argCount fun.argCount))
+    (assertEq "runTestsuite has two arguments" 2
+      (fun.argCount runTestsuite))
+  ];
+
+  applyTests = it "checks that fun.apply is equivalent to calling" [
+    (assertEq "fun.apply builtins.sub" (builtins.sub 23 42)
+      (fun.apply builtins.sub [ 23 42 ]))
+    (assertEq "fun.apply escapeExecline" (escapeExecline [ "foo" [ "bar" ] ])
+      (fun.apply escapeExecline [ [ "foo" [ "bar" ] ] ]))
+  ];
+
+  unapplyTests = it "checks fun.unapply" [
+    (assertEq "fun.unapply 3 accepts 3 args" 3
+      (fun.argCount (fun.unapply 3 fun.id)))
+    (assertEq "fun.unapply 73 accepts 73 args" 73
+      (fun.argCount (fun.unapply 73 fun.id)))
+    (assertEq "fun.unapply 1 accepts 73 args" 1
+      (fun.argCount (fun.unapply 1 fun.id)))
+    (assertEq "fun.unapply collects arguments correctly"
+      (fun.unapply 5 fun.id 1 2 3 4 5)
+      [ 1 2 3 4 5 ])
+    (assertEq "fun.unapply calls the given function correctly" 1
+      (fun.unapply 1 builtins.head 1))
+  ];
+
+  fac' = self: acc: n: if n == 0 then acc else self (n * acc) (n - 1);
+
+  facPlain = fun.fix fac' 1;
+  facOpt = fun.tailCallOpt fac' 1;
+
+  tailCallOptTests = it "checks fun.tailCallOpt" [
+    (assertEq "optimized and unoptimized factorial have the same base case"
+      (facPlain 0)
+      (facOpt 0))
+    (assertEq "optimized and unoptimized factorial have same value for 1"
+      (facPlain 1)
+      (facOpt 1))
+    (assertEq "optimized and unoptimized factorial have same value for 100"
+      (facPlain 100)
+      (facOpt 100))
+  ];
 in
 runTestsuite "nix.fun" [
   hasEllipsisTests
+  argCountTests
+  applyTests
+  unapplyTests
+  tailCallOptTests
 ]