Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Using Monads in C++ to Solve Constraints: 1. The List Monad

bartoszmilewski.com

Post reply on HN
Print view View original

61–70 of 73 posts

Re: Using Monads in C++ to Solve Constraints: 1. The List Monad

#61

Post by mafribe »

dllthomas wrote: post #58
mafribe wrote: post #57

Earlier quoted context omitted.

Sure, if you use some of the unsafe stuff ... but what about the safe core of Haskell, do you consider that pure?

What's needed here is ST. It permits local O(1) mutable vectors, while enforcing referential transparency when viewed from outside the runST. ST is clearly not pure in the sense that theory requires to make "can we implement this algorithm with the same complexity" an interesting question. It seems wrong to consider it part of "the unsafe stuff", however - it doesn't have the same kind of unenforced caveats as unsafe…

By ST you mean Haskell's StateT monad transfomer?

Are you suggesting to define purity by the inability to define O(1) mutable vector-like operations? That would be an interesting proposal. But I wonder if it captures the conceptual content of the informal concept of purity. Maybe a time complexity restriction should be provable from purity?

Re: Using Monads in C++ to Solve Constraints: 1. The List Monad

#62

Post by dllthomas »

mafribe wrote: post #61
dllthomas wrote: post #58

Earlier quoted context omitted.

What's needed here is ST. It permits local O(1) mutable vectors, while enforcing referential transparency when viewed from outside the runST. ST is clearly not pure in the sense that theory requires to make "can we implement this algorithm with the same complexity" an interesting question. It seems wrong to consider it part of "the unsafe stuff", however - it doesn't have the same kind of unenforced caveats as unsafe…

By ST you mean Haskell's StateT monad transfomer? Are you suggesting to define purity by the inability to define O(1) mutable vector-like operations? That would be an interesting proposal. But I wonder if it captures the conceptual content of the informal concept of purity. Maybe a time complexity restriction should be provable from purity?

"By ST you mean Haskell's StateT monad transfomer?"

No, I mean ST. An entirely different monad: http://hackage.haskell.org/package/base-4.7.0.0/docs/Control...

"Are you suggesting to define purity by the inability to define O(1) mutable vector-like operations?"

"Define", no, as that certainly doesn't encompass the full scope of purity. I think mutability runs counter to most people's notion of purity, particularly when they say "Haskell isn't pure". Of course, we can fake mutability at a cost of O(log n), which is what makes the O(1) notable.

If you do think ST is "pure" then it's not an open question whether you can implement update-heavy array based algorithms in a pure language without algorithmic penalty - you clearly can.

Re: Using Monads in C++ to Solve Constraints: 1. The List Monad

#63

Post by tome »

mafribe wrote: post #56
tome wrote: post #54

Earlier quoted context omitted.

What do "pure" and "lazy" mean to you?

Lazy is easy: it's call-by-name evaluation, i.e. (lambda x.M)N -> M[N/x] with caching, ie. each argument is evaluated at most once. Purity is more subtle. I don't think there's an agreed upon definition. [1] essentially ties purity to the equivalency of call-by-name, call-by-need and call-by-value evaluation orders (ignoring divergence and errors). I'm not totally sure that is the right definition. [1] A. Sabry, What…

With those definitions pure and lazy languages can certainly do mutation and have effects, viz. the IO and ST monads.

Re: Using Monads in C++ to Solve Constraints: 1. The List Monad

#64

Post by mafribe »

dllthomas wrote: post #62
mafribe wrote: post #61

Earlier quoted context omitted.

By ST you mean Haskell's StateT monad transfomer? Are you suggesting to define purity by the inability to define O(1) mutable vector-like operations? That would be an interesting proposal. But I wonder if it captures the conceptual content of the informal concept of purity. Maybe a time complexity restriction should be provable from purity?

"By ST you mean Haskell's StateT monad transfomer?" No, I mean ST. An entirely different monad: http://hackage.haskell.org/package/base-4.7.0.0/docs/Control... "Are you suggesting to define purity by the inability to define O(1) mutable vector-like operations?" "Define", no, as that certainly doesn't encompass the full scope of purity. I think mutability runs counter to most people's notion of purity, particularly wh…

SPJ and J Launchbury seem to think ST is pure.

Looking over the PLDI paper, I get the impression that the key difference between ST and the usual State monad is (1) the ability to name state, and (2) the use of parametric polymorphism to prevent scope-extrusion of state.

Of course ML has scope-extrusion of state, and one of my questions/examples upthread was about the ability of Haskell's monadically controlled effects to implement such scope extrusion without 'tricks'.

All in all I feel that the notion of purity is controversial, insufficiently theorised, and that the community would benefit from a clearer understanding of the trade-offs involved in the different notions of purity

Re: Using Monads in C++ to Solve Constraints: 1. The List Monad

#65

Post by dllthomas »

mafribe wrote: post #64
dllthomas wrote: post #62

Earlier quoted context omitted.

"By ST you mean Haskell's StateT monad transfomer?" No, I mean ST. An entirely different monad: http://hackage.haskell.org/package/base-4.7.0.0/docs/Control... "Are you suggesting to define purity by the inability to define O(1) mutable vector-like operations?" "Define", no, as that certainly doesn't encompass the full scope of purity. I think mutability runs counter to most people's notion of purity, particularly wh…

SPJ and J Launchbury seem to think ST is pure. Looking over the PLDI paper, I get the impression that the key difference between ST and the usual State monad is (1) the ability to name state, and (2) the use of parametric polymorphism to prevent scope-extrusion of state. Of course ML has scope-extrusion of state, and one of my questions/examples upthread was about the ability of Haskell's monadically controlled effec…

You are infuriating.

If you object to notions of purity, why did you bring it up in the first place?

The first place it was used in this thread was your citing a paper entitled "Pure versus Impure Lisp".

In that paper, it was used to mean prohibiting "set-car!" and "set-cdr!". ST provides the equivalent of "set-car!" and "set-cdr!", so in the presence of ST the result you were citing in the paper doesn't even apply to a strict version of Haskell.

Please just stop making claims about Haskell until you have some sense of what you're talking about (or at least add a caveat warning others that you might not).

Re: Using Monads in C++ to Solve Constraints: 1. The List Monad

#66

Post by dllthomas »

mafribe wrote: post #64
dllthomas wrote: post #62

Earlier quoted context omitted.

"By ST you mean Haskell's StateT monad transfomer?" No, I mean ST. An entirely different monad: http://hackage.haskell.org/package/base-4.7.0.0/docs/Control... "Are you suggesting to define purity by the inability to define O(1) mutable vector-like operations?" "Define", no, as that certainly doesn't encompass the full scope of purity. I think mutability runs counter to most people's notion of purity, particularly wh…

SPJ and J Launchbury seem to think ST is pure. Looking over the PLDI paper, I get the impression that the key difference between ST and the usual State monad is (1) the ability to name state, and (2) the use of parametric polymorphism to prevent scope-extrusion of state. Of course ML has scope-extrusion of state, and one of my questions/examples upthread was about the ability of Haskell's monadically controlled effec…

"I get the impression that the key difference between ST and the usual State monad is (1) the ability to name state, and (2) the use of parametric polymorphism to prevent scope-extrusion of state."

The key difference between ST and the State monad is that the State monad is simply sugar for a function call of the form (s -> (a, s)), whereas ST allows for actual mutability. This is what changes the asymptotic complexity.

ST also does things to prevent references from leaking, and that's valuable and more useful in the context of ST, but that's irrelevant to our questions up-thread.

"Of course ML has scope-extrusion of state, and one of my questions/examples upthread was about the ability of Haskell's monadically controlled effects to implement such scope extrusion without 'tricks'."

That wasn't this thread.

I still think scope extrusion - without asking for it - would be a bug not a feature; particularly so in the case of a multithreaded, lazily evaluated language with inlining and CSE - where you really have little control over what gets executed when if you're ducking the features that guide what gets executed when.

This doesn't limit expressibility, because you do have the ability to ask for it, using those "tricks" that you keep excluding for no good reason. "How expressive is Haskell if it lacked those" is an interesting question, but not am immediately practical one, and you should be clear that that is the question you're asking.

Re: Using Monads in C++ to Solve Constraints: 1. The List Monad

#67

Post by mafribe »

dllthomas wrote: post #65
mafribe wrote: post #64

Earlier quoted context omitted.

SPJ and J Launchbury seem to think ST is pure. Looking over the PLDI paper, I get the impression that the key difference between ST and the usual State monad is (1) the ability to name state, and (2) the use of parametric polymorphism to prevent scope-extrusion of state. Of course ML has scope-extrusion of state, and one of my questions/examples upthread was about the ability of Haskell's monadically controlled effec…

You are infuriating. If you object to notions of purity, why did you bring it up in the first place? The first place it was used in this thread was your citing a paper entitled "Pure versus Impure Lisp". In that paper, it was used to mean prohibiting "set-car!" and "set-cdr!". ST provides the equivalent of "set-car!" and "set-cdr!", so in the presence of ST the result you were citing in the paper doesn't even apply t…

I don't object to purity, I want to know what it means. I didn't realise that this is not a well-understood concept. (I mentioned Sabry's definition of purity which I found surprising.)

The original discussion started because somebody complained that Haskell programmers often appear unable to transliterate imperative algorithms. I assume that this complaint was about transliteration into pure Haskell (whatever that may mean exactly). Clearly transliteration into full Haskell with actual mutability is possible. I mentioned Pippenger's article to bring to the debate the idea that the question whether such transliteration is always possible is an open research problem.

Re: Using Monads in C++ to Solve Constraints: 1. The List Monad

#68

Post by tome »

mafribe wrote: post #67
dllthomas wrote: post #65

Earlier quoted context omitted.

You are infuriating. If you object to notions of purity, why did you bring it up in the first place? The first place it was used in this thread was your citing a paper entitled "Pure versus Impure Lisp". In that paper, it was used to mean prohibiting "set-car!" and "set-cdr!". ST provides the equivalent of "set-car!" and "set-cdr!", so in the presence of ST the result you were citing in the paper doesn't even apply t…

I don't object to purity, I want to know what it means. I didn't realise that this is not a well-understood concept. (I mentioned Sabry's definition of purity which I found surprising.) The original discussion started because somebody complained that Haskell programmers often appear unable to transliterate imperative algorithms. I assume that this complaint was about transliteration into pure Haskell (whatever that m…

I don't think anyone knows a solid definition of purity. It certainly refers to at least two things (1. independence of order of evaluation, 2. no side effects) and informally speaking we often "know" what it is in a particular context, but writing down a formal definition is very hard. I'm certainly not satisfied with Sabry's definition. I don't like the idea that you have to have both a strict and a non-strict evaluation for your language.

Re: Using Monads in C++ to Solve Constraints: 1. The List Monad

#69

Post by mafribe »

tome wrote: post #68
mafribe wrote: post #67

Earlier quoted context omitted.

I don't object to purity, I want to know what it means. I didn't realise that this is not a well-understood concept. (I mentioned Sabry's definition of purity which I found surprising.) The original discussion started because somebody complained that Haskell programmers often appear unable to transliterate imperative algorithms. I assume that this complaint was about transliteration into pure Haskell (whatever that m…

I don't think anyone knows a solid definition of purity. It certainly refers to at least two things (1. independence of order of evaluation, 2. no side effects) and informally speaking we often "know" what it is in a particular context, but writing down a formal definition is very hard. I'm certainly not satisfied with Sabry's definition. I don't like the idea that you have to have both a strict and a non-strict eval…

If nobody knows what purity means, then what are all those tortured discussions on whether Haskell is pure or not about? ...

Anyway, I'm a bit unhappy about the requirement of full evaluation order independence, because even the purest of pure languages (e.g. the untyped lambda-calculus or PCF) don't have full evaluation order independence. I guess you mean evaluation order independence modulo termination?

My intuition is that pure means that all language expressions M can always be evaluated locally by just looking at the meaning of all subterms of M. In terms of Hoare logic (for total correctness) that would mean that the pre-condition speaks only about the termination of the free variables of M (sorry for being so terse, I think this can be made formal).

Re: Using Monads in C++ to Solve Constraints: 1. The List Monad

#70

Post by dllthomas »

mafribe wrote: post #67
dllthomas wrote: post #65

Earlier quoted context omitted.

You are infuriating. If you object to notions of purity, why did you bring it up in the first place? The first place it was used in this thread was your citing a paper entitled "Pure versus Impure Lisp". In that paper, it was used to mean prohibiting "set-car!" and "set-cdr!". ST provides the equivalent of "set-car!" and "set-cdr!", so in the presence of ST the result you were citing in the paper doesn't even apply t…

I don't object to purity, I want to know what it means. I didn't realise that this is not a well-understood concept. (I mentioned Sabry's definition of purity which I found surprising.) The original discussion started because somebody complained that Haskell programmers often appear unable to transliterate imperative algorithms. I assume that this complaint was about transliteration into pure Haskell (whatever that m…

"I assume that this complaint was about transliteration into pure Haskell (whatever that may mean exactly). Clearly transliteration into full Haskell with actual mutability is possible."

Ah, if you'd made that assumption explicit I would not have objected.

I don't see anywhere the querent suggesting that his translation demand invoked any notion of purity. If it did, then certainly he was asking a harder question than he presented, although even in that case a naive translation could have trivially produced an O(m n lg(n)) solution and O(m^n) should quite reasonably be considered failure.

I think the issue in the main is that relatively novice Haskell developers are likely to be the most eager to try and translate arbitrary code on demand in #haskell.

Post reply on HN