# Tag Info

### Why do functional programming languages require garbage collection?

All of the following comments are premised on the choice of a standard implementation strategy using closures to represent function values and a call-by-value evaluation order: For the pure lambda ...
• 31.8k
Accepted

### (How) Could we discover/analyze NP problems in the absence of the Turing model of computation?

You may wish to look at cost semantics for functional languages. These are various computational complexity measures for functional languages that do not pass through any kind of Turing machine, RAM ...
• 26.8k

### Are there any annotated formal verification systems for pure functional programming languages?

You might want to check out Liquid Haskell, which allow working with type refinements rather than dependent types. Type refinements can be seen as a restricted logical language that allow you to ...
• 13.3k

• 4,823
Accepted

### Typechecking liveness properties of coprograms

To expand on pedagand's answer: productivity is the term used for the computational dual (in some precise sense) of termination. Formally, a program f : CoData is ...
• 13.3k

### Category theory and parsers --- references wanted

It would appear that (context free) parsing a la Parsec is naturally expressed in terms of the Applicative type class. In turn, this class is described well by so-called strong lax monoidal functors, ...
• 13.3k