Opened 9 months ago

Last modified 9 months ago

#14527 new feature request

Warn on recursive bindings

Reported by: chrisdone Owned by:
Priority: normal Milestone:
Component: Compiler Version: 8.2.1
Keywords: Cc: saurabhnanda, nh2, goldfire, adamse
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description (last modified by chrisdone)

When you accidentally write something like let x = .. x ... it can take hours to realize where you made your mistake. This hits me once in a while, and my colleagues often.

I'd propose e.g. -Wrecursive-bindings that says:

warning: [-Wrecursive-bindings]
    Recursive binding for `x` in

    let x = length x

This applies to let, where and top-level pattern bindings.

I believe that in practice, I only actually use real recursive bindings once in a while. So I might be bold enough to encourage enabling it in -Wall for a future major GHC release.

With the compromise that if you have the warning enabled but in one specific place, you want a recursive binding, you can use the ~ tilde to say "I really mean it", e.g.

let ~ones = 1 : ones

That seems like a nice balance to say "I know what I'm doing in this case". So the warning could be more helpful, like:

warning: [-Wrecursive-bindings]
    Recursive binding for `ones` in

    let ones = length ones

    If intentional, use the tilde marker on the name like this:

    let ~ones = length ones

In Intero if I were to implement a prototype of this check, I'd probably do this, after renaming:

  1. Use SYB to collect all variable bindings from the pattern.
  2. Use SYB to listify all mentions of any of these variables in the RHS and any guards or where clauses.

If the list is non-empty, then trigger the error. A transformation function [Name] -> Pat -> Pat would provide the AST with the offending name(s) tilded as ~x for use in the error message.

If there's general agreement, I could implement this change.

EDIT: mutually recursive bindings apply here too. So let x = y; y = x by a regular occurs check.

Change History (15)

comment:1 Changed 9 months ago by chrisdone

Description: modified (diff)

comment:2 Changed 9 months ago by saurabhnanda

Cc: saurabhnanda added

comment:3 Changed 9 months ago by nh2

GHC 7.10 already had this feature, but it disappeared with 8.0, and it's not clear to me if intentionally or accidentally. It would be great to find out.

In 7.10, you could simply used a BangPattern to forbid recursive variable bindings. Example

    Recursive bang-pattern or unboxed-tuple bindings aren't allowed:
      !x = x

And it said in the manual:

    a bang-pattern binding must be non-recursive

It was removed for GHC 8.0 in these commits:

The question is: Why was this removed?

Was it accidental, or did people find a legitimate use case for strict recursive variable let bindings?

If not, we could simply re-introduce that, without a language extension (though we might still add the proposed language extension to get warnings even without bangs).

I've pinged the authors of these 2 commits (goldfire and adamse) on #ghc but I haven't got a response yet.

Last edited 9 months ago by nh2 (previous) (diff)

comment:4 Changed 9 months ago by nh2

Cc: nh2 goldfire adamse added

comment:5 Changed 9 months ago by adamse

I cannot remember removing this warning intentionally. It might have been part of the bigger plan around -XStrict and the changes to the semantics of bang patterns it introduced. I'll dig around and see if I can find out if it was unintentional. Sorry for not responding on IRC.

comment:6 Changed 9 months ago by adamse

It has come back to me: allowing recursive banged bindings was by design. See https://downloads.haskell.org/~ghc/8.0.1/docs/html/users_guide/glasgow_exts.html#recursive-and-polymorphic-let-bindings for details.

comment:7 Changed 9 months ago by chrisdone

For context, Niklas and I were discussing this problem and I mentioned the !x restriction, only to discover that the restriction wasn't present on GHC 8. So Niklas digged and found the commit, but we weren't sure why.

However, it's not quite true that GHC had this feature. Certainly, getting !x to disable recursion back into GHC should be much easier to convince GHC maintainers to add it back, assuming it was removed accidentally. Maybe that belongs in a separate but related ticket.

More generally speaking, self-referential variables in my experience are almost always a mistake and once in a while an intentional thing for me. So it would actually be nice if GHC warned about it and I had to put an explicit ~ in the few times I wanted it, rather than ! everywhere, just to avoid the problem.

comment:8 Changed 9 months ago by bgamari

Given that both the ticket summary and comment:7 are really asking for a new flag and new behavior for ~, I believe that this proposal falls within the scope of GHC's proposal process. Chrisdone, do you suppose you could submit a proposal?

comment:9 Changed 9 months ago by goldfire

In the levity polymorphism work, there were some annoying interactions between the treatment of strict and unlifted bindings and levity polymorphism. I don't recall the details, but it was necessary to edit the code in this area. As I was doing so, it seemed the code was confused around the restrictions on unlifted bindings vs. strict ones. There is no need to prevent strict recursive bindings, and so we don't.

In the end, though, I don't think that disallowing strict recursive bindings is the real answer to this need (which I've shared) -- the warning route originally proposed would be far better. I agree with Ben that posting a proposal is the best next step. If I may be so bold as to comment prematurely, I would likely support such a proposal.

comment:10 Changed 9 months ago by simonpj

Making it possible to have strict recursive bindings was by-design I believe, not accidental. Mostly, I think, for simplicity and uniformity rather than actual use-cases.

More importantly, not every non-recursive binding should be strict! And putting a bang on every single non-recursive binding would indeed be tiresome. So coupling this warning business with bang patterns would be a mistake, I think.

I rather like the idea of a tilde. It's allowed right now, but it's semantically a no-op. So using it as a per-binding way of disabling the warning would be quite neat.

It's worth a proposal though. Make sure you handle recursive pattern bindings like

(x,y) = f x

comment:11 Changed 9 months ago by nomeata

Just for clarification. Does

This applies to let, where and top-level pattern bindings.

Mean it applies to

let x = ones : x

and

let f = \n -> if n == 0 then 1 else n * f (n-1)

but not

let f n = if n == 0 then 1 else n * f (n-1)

right?

(I think I like the explicit ~ on recursive value bindings.)

comment:12 Changed 9 months ago by chrisdone

I think there's a spanner in the works because

print = \case ...
  App f x -> print f <> " " <> print x

is a common idiomatic way of writing functions these days. We wouldn't want a warning for that. So I'm afraid it's less straight-forward than I hoped.

comment:13 Changed 9 months ago by simonpj

So I'm afraid it's less straight-forward than I hoped.

It's only a warning so it's ok to have ad-hoc (but still well specified) conditions. For example: you get a warning if

  • The binding is recursive (or part of a recursive group)
  • It is a pattern or simple variable binding; that is there are no argument on the LHS
  • The LHS does not have a top-level tilde
  • The RHS is not a syntactic value.

Then define syntactic values to be: literal, constructor application, lambda, \case, etc. (This is the slightly ad-hoc bit.)

comment:14 Changed 9 months ago by goldfire

So, ones = 1 : ones wouldn't be warned? I suppose that's OK, but I would prefer that such a definition is indeed warned (without a ~).

comment:15 Changed 9 months ago by chrisdone

Right, I was aiming for ones = 1 : ones to be a warning.

How about we rephrase it as "function-like":

  • The RHS is not a function-like: either a lambda or a lambda-case.

(If the RHS is a literal then by-definition it's not recursive and wouldn't trigger the warning, I think.)

With an ad-hoc bit like that, I'm more convinced that this could be practical. I'll consider making a proposal for it. A draft implementation could be run against Stackage to see how many false-positives it flags up. Here and reddit provided enough concerns

Note: See TracTickets for help on using tickets.