7

There is a piece of source-code that originated in an answer to another one of my questions,

infFromPrefix :: Eq a => ([a] -> [a]) -> [a] -> [a] 
infFromPrefix rules prefix = inf where
    inf = prefix ++ case stripPrefix prefix (rules inf) of
        Just suffix -> suffix
        Nothing     -> error "Substitution does not preserve prefix"

where I am pretty sure that inf must be a closure as it has access to variables from its enclosing scope in the sense that it uses the parameters passed to infFromPrefix, but am unsure since essentially infFromPrefix and inf is the same function, the inf only allows a more succinct definition. An equivalent definition would be 

infFromPrefix rules prefix = prefix ++ case stripPrefix prefix (rules $ infFromPrefix rules prefix) of
        Just suffix -> suffix
        Nothing     -> error "Substitution does not preserve prefix"

Am I correct, is inf a closure?

Community
  • 1
  • 1
Filip Allberg
  • 3,941
  • 3
  • 20
  • 37
  • I'd say "no" because `inf` is not a function; it's a list. – melpomene Oct 23 '15 at 15:22
  • 5
    @melpomene I think in eager languages it makes sense to restrict closures to contain functions; in lazy languages I'm not so sure. At the very least I would be willing to bet that GHC has a data structure it calls "closure" that's involved in representing `inf` at some level. – Daniel Wagner Oct 23 '15 at 15:28
  • @melpomene You are right, as otherwise rules would not accept it as input. Cheers. – Filip Allberg Oct 23 '15 at 15:33
  • 7
    Since Haskell doesn't have a notion of a 'closure', you'd better tell us what you mean by 'closure' if you expect an accurate answer. The notion of a closure is usually something that refers to a language implementation. So you could ask if some particular implementation of Haskell uses a closure to represent inf. – augustss Oct 23 '15 at 15:38
  • 2
    @augustss If you know the definitive answer for GHC, I think that would make a fine answer to this question. I know I'd upvote it. – Daniel Wagner Oct 23 '15 at 15:40
  • @augustss I did not know this, so I am clearly barking up the wrong tree. As you stated, there may be some particular implementation that does this but that is not why I asked the question. Although learning about such a thing would surely be interesting. As Daniel Wagner said, the definitive answer for GHC is fine. – Filip Allberg Oct 23 '15 at 15:43
  • Since I wrote that code piece in my answer, I'll point out that the most important reason to use `inf` rather than recursing with `infFromPrefix rules prefix` is to ensure that the work of calculating the list is not duplicated - in GHC `inf` ensures sharing, but recursing with a function does not. – Ørjan Johansen Oct 24 '15 at 00:58
  • @FilipAllberg: I think you should have accepted the other answer as mine is not specific enough to Haskell... or did you have a particular reason to choose mine over Roman's? – Erik Kaplun Oct 24 '15 at 11:32
  • @erik-allik: Your answer is the one I felt aligned best with the intent I had posing the question. I was approaching the subject from a [Closures in programming](https://en.m.wikipedia.org/wiki/Closure_%28computer_programming%29) stand-point. Had I been more explicit and asked, "Is this a closure in Haskell?", I would have chosen Roman's answer. – Filip Allberg Oct 24 '15 at 12:43

2 Answers2

10

I would agree with Lennart and Daniel that closure is an implementation-specific term and is not something well-defined in general. Moreover, I don't hear Haskellers talk about closures a lot outside of the implementation issues; when programmers in other languages casually talk about "closures", they usually mean what we call "lambdas". (As in "does that language have closures?".)

Anyway, let's talk about GHC.

GHC (or, more precisely, STG) calls a closure any heap object that is not a constructor application.

(In case you think this is a broad definition, compare this with the original STG paper where even constructors were called closures.)

Your inf is certainly an STG closure; it is a thunk that will be allocated on the heap and returned to the caller.

Roman Cheplyaka
  • 37,738
  • 7
  • 72
  • 121
  • _"returned to the caller"_ — the caller of which function? `inf` or `infFromPrefix`? I'm not sure how to put your answer in the context of how [wikipedia defines a closure](https://en.m.wikipedia.org/wiki/Closure_(computer_programming)). – Erik Kaplun Oct 23 '15 at 17:16
  • `infFromPrefix` constructs a closure/thunk on the heap, `inf` and returns (the pointer to) it to its (`infFromPrefix`'s) caller. The caller will then enter the closure to evaluate it to the necessary degree. – Roman Cheplyaka Oct 23 '15 at 18:13
  • 2
    @ErikAllik Perhaps part of the problem is that people here (and in the Wikipedia article) are not being careful about the difference between static objects -- chunks of syntax in a language -- and dynamic objects -- things that get built and inspected at runtime. To say that `inf` itself is not a closure seems technically correct, since it is a static object, and only dynamic objects can be closures; but to say that at runtime the expression `inf` gets turned into a closure when `infFromPrefix` is called also seems correct. – Daniel Wagner Oct 23 '15 at 18:16
  • @DanielWagner: agreed, that's a useful distinction and can be a source of confusion. At the same time, STG-the-language uses the term closure for its static objects too, although not in the same sense as the wikipedia article. This is because STG is designed to map rather closely to the dynamic semantics. – Roman Cheplyaka Oct 23 '15 at 18:21
5

Based on the Wiki article on Closures in programming, I think it can be said that inf is indeed not a closure:

Note especially that the nested function definitions are not themselves closures: they have a free variable, which is not yet bound. Only once the enclosing function is evaluated with a value for the parameter is the free variable of the nested function bound, creating a closure, which is then returned from the enclosing function.

Erik Kaplun
  • 37,128
  • 15
  • 99
  • 111
  • I agree with you, as Haskell is Lazy, everything can be seen as a closure, as even a value can be seen as a function without argument waiting to be evaluated (and so capturing it's environment until it gets evaluated). – mb14 Oct 23 '15 at 17:46
  • 2
    "[A]s even a value can be seen as a function without argument." Not really, no. – Rein Henrichs Oct 23 '15 at 20:18