Skip to content

fixpoint: infinite recursion #1

@milahu

Description

@milahu

currently this breaks the interpreter

# fix: Take a function and evaluate it with its own returned value.
let
  fix = f: let x = f x; in x;
in
fix (self: { x = "abc"; x2 = self.x + "123"; })
git checkout 765e68957948f1d6721e6278fce1469c8f544d4a

./bin/nix-eval -e "let fix = f: let x = f x; in x; in fix (self: { x = ''abc''; x2 = self.x + ''123''; })"

throws RangeError: Maximum call stack size exceeded

the original nix interpreter needs only one call:

nix-repl> let fix = f: let x = builtins.trace ''call'' f x; in x; in fix (self: { x = ''abc''; x2 = self.x + ''123''; })
trace: call
{ x = "abc"; x2 = "abc123"; }

this will take me some time to fix, so im leaving this issue here

see also my notes in docs/todo.md#fixpoint

i hope that this will do (nix thesis, pdf page 82)

So if we desugar

x: rec { inherit x; y = 123; }

to

x: rec { x = x; y = 123; }

we have incorrectly created an infinite recursion: the attribute x now evaluates to itself,
rather than the value of the function argument x. For this reason rec is actually internally
stored as two sets of attributes: the recursive attributes, and the non-recursive attributes.

plan B: implement caching. this requires a stringifyToAterm function

for now, the fixpoint test is skipped

nix-eval-js/test/nix-eval.snapshots.txt

# SKIP FIXME fixpoint recursion
"let fix = f: let x = f x; in x; in fix (self: { x = ''abc''; x2 = self.x + ''123''; })"
==>
{"x":"abc","x2":"abc123"}

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions