From 36f6322d16ad0c2341bc37235bf327db516ef97d Mon Sep 17 00:00:00 2001 From: sterni Date: Mon, 14 Feb 2022 12:01:50 +0100 Subject: feat(sterni/nix/fun): implement tail call “optimization” for Nix MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit 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 Autosubmit: sterni --- users/sterni/nix/fun/tests/default.nix | 53 ++++++++++++++++++++++++++++++++++ 1 file changed, 53 insertions(+) (limited to 'users/sterni/nix/fun/tests') diff --git a/users/sterni/nix/fun/tests/default.nix b/users/sterni/nix/fun/tests/default.nix index f02f19943373..6b1e6fcc7b0b 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 ] -- cgit 1.4.1