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

Destroy All Ifs – A Perspective from Functional Programming

degoes.net

Post reply on HN
Print view View original

181–190 of 226 posts

Re: Destroy All Ifs – A Perspective from Functional Programming

#181

Post by wyager »

cousin_it wrote: post #159
eru wrote: post #127

Earlier quoted context omitted.

In a language like Haskell you wouldn't want to prove the absence of recursion, but that all recursions in the program fit into a handful of patterns. (Eg 'structural-recursion' or 'tail-recursion'.) Some type systems are strong enough to put that kind of analysis / constraints directly into the language. (Haskell might already be strong enough with GADTs and other language extensions enabled.) In any case, the Adden…

Tee hee, Haskell doesn't have tail recursion (e.g. foldl takes linear space), and structural recursion in Haskell isn't guaranteed to terminate (e.g. if you're given an infinite list). If I were in charge of developing a safety critical system, and someone came to me with a proposal to write it in Haskell, I'd be very skeptical.

??? Haskell absolutely has tail recursion; foldl just evaluates non-strictly and therefore can leave thunks in memory. This is fine for e.g. reversing a cons-list. Regardless, it is tail recursive (and uses constant stack space). foldl' is also tail recursive and has strict semantics.

Structural recursion can't be guaranteed to terminate in any language that supports codata unless you have some sort of totality checker (e.g. via a monotonically structurally decreasing requirement imposed at the type or value level). I don't think any mainstream language supports this out of the box. Liquid Haskell does offer this, though.

I agree that standard Haskell is inappropriate for safety critical software, but only because it allows dynamic allocation. Any program using dynamic allocation is probably unsuitable for safety critical software. Now, a terminating and fixed-memory subset of Haskell a la Clash would be interesting for safety critical software...

Re: Destroy All Ifs – A Perspective from Functional Programming

#182

Post by steveklabnik »

steveklabnik wrote: post #175
dan00 wrote: post #157

Earlier quoted context omitted.

Why can't it be written as: .map_err(to_string) When using the lambda the type is inferred, so why should there be a need for the ToString?

If `to_string` was a function that was imported into the local namespace, you could. But since it's a method, you can't; you need to provide the trait name.

To follow up on this slightly, it's not really that this is special syntax. It's that map_err takes a function as an argument, and this is how you refer to this method by name.

Re: Destroy All Ifs – A Perspective from Functional Programming

#183

Post by steveklabnik »

MichaelGG wrote: post #180
steveklabnik wrote: post #110

Earlier quoted context omitted.

It does. This could have been written .map_err(ToString::to_string) as well. Works just fine with methods.

But that's actually longer. It does look a bit better though, maybe.

Yeah, it's not about saving characters to me, it's about clarity.

Re: Destroy All Ifs – A Perspective from Functional Programming

#184

Post by ufo »

runeks wrote: post #149
ufo wrote: post #82

I'm surprised that the article and none of the comments so far mentioned the "Expression Problem": http://c2.com/cgi/wiki?ExpressionProblem Basically, if you structure the control flow in object oriented style (or church encoding...) then its easy to extend your program with new "classes" but if you want to add a new methods then you must go back and rewrite all your classes. On the other hand, if you use if-statemen…

> I think its because until recently pattern matching and > algebraic data types (a more robust alternative to > switch statements) [...] Could you elaborate a bit on what this accomplishes, eg. pattern matching vs a "case" statement? As I've programmed in Haskell for the past year or two, I've observed exactly this change in my style of writing - that I've started to get rid of "case" statements inside function defi…

I was just comparing the pattern matching from FP languages with the more primitive C-like switch statement. The big advantage comes from the algebraic data types (tagged unions), which let you model data with many "cases" in a type-safe manner. For example, in Haskell we don't have null pointers because we can use the Maybe type instead.

The case-expression vs function-definition difference you mentioned from Haskell is just syntactic sugar. In both situations you are doing exactly the same pattern matching under the hood.

Re: Destroy All Ifs – A Perspective from Functional Programming

#186

Post by cousin_it »

wyager wrote: post #181
cousin_it wrote: post #159

Earlier quoted context omitted.

Tee hee, Haskell doesn't have tail recursion (e.g. foldl takes linear space), and structural recursion in Haskell isn't guaranteed to terminate (e.g. if you're given an infinite list). If I were in charge of developing a safety critical system, and someone came to me with a proposal to write it in Haskell, I'd be very skeptical.

??? Haskell absolutely has tail recursion; foldl just evaluates non-strictly and therefore can leave thunks in memory. This is fine for e.g. reversing a cons-list. Regardless, it is tail recursive (and uses constant stack space). foldl' is also tail recursive and has strict semantics. Structural recursion can't be guaranteed to terminate in any language that supports codata unless you have some sort of totality check…

The point of tail recursion is using constant space, not constant stack space (does Haskell even have a stack?) Anyways, the Haskell spec allows foldl' to use linear space just like its lazier counterparts. The fact that it uses constant space is an implementation detail of GHC. Reference: https://github.com/quchen/articles/blob/master/fbut.md#seq-d...

Structural recursion always terminates in SML. Supporting infinite/cyclic values in algebraic data types is a misfeature, and they are trivial to rule out without using a totality checker. Heck, I can implement a guaranteed finite linked list in Java :-)

I think something like MLKit would be a more promising start for implementing a safety critical system. Tail and structural recursion actually work there, and it statically replaces most uses of GC with region inference. Though it's still a very long shot, I'd prefer something more proven.

Re: Destroy All Ifs – A Perspective from Functional Programming

#187

Post by MichaelGG »

steveklabnik wrote: post #183
MichaelGG wrote: post #180

Earlier quoted context omitted.

But that's actually longer. It does look a bit better though, maybe.

Yeah, it's not about saving characters to me, it's about clarity.

Actually, this suggestion does not even work. Writing trait::method is not equivalent to writing "|x|x.method()". The latter will use method lookup rules, the former requires the programmer to decide which impl. For instance, in the above example, if the type impl'd to_string, that would be the one used, not ToString's implementation. From what I can tell anyways: https://is.gd/E8pdWc

Edit: Also, auto-borrow does not seem to work with this syntax.

This is a common enough pattern that reducing the visual noise will increase clarity.

Re: Destroy All Ifs – A Perspective from Functional Programming

#188

Post by steveklabnik »

MichaelGG wrote: post #187
steveklabnik wrote: post #183

Earlier quoted context omitted.

Yeah, it's not about saving characters to me, it's about clarity.

Actually, this suggestion does not even work. Writing trait::method is not equivalent to writing "|x|x.method()". The latter will use method lookup rules, the former requires the programmer to decide which impl. For instance, in the above example, if the type impl'd to_string, that would be the one used, not ToString's implementation. From what I can tell anyways: https://is.gd/E8pdWc Edit: Also, auto-borrow does not…

Yes, this is correct. It's what I was getting at in the other thread; this is choosing a method manually.

Re: Destroy All Ifs – A Perspective from Functional Programming

#189

Post by MichaelGG »

dan00 wrote: post #157
steveklabnik wrote: post #110

Earlier quoted context omitted.

It does. This could have been written .map_err(ToString::to_string) as well. Works just fine with methods.

Why can't it be written as: .map_err(to_string) When using the lambda the type is inferred, so why should there be a need for the ToString?

It'd need syntax to distinguish from a local function called to_string. Anything less allows ambiguity and wouldn't be equivalent (like using type::method won't do auto-borrow). So it'd need to be "\to_string", "|to_string" or something. Ample opportunity for bikeshedding.

Functional style is hampered by excessive verbosity. (Non functional style is so verbose a bit of extra noise doesn't hurt _as much_.) Rust could use a lot more inference, custom operators[1], and so on. They seem to sort of agree, with auto-deref, auto-borrow, some type inference, but won't go all the way. I suppose being conservative can be defended -- can't go back without breaking code. Hopefully, in the future, the verbosity will annoy more people and there will be enough support to head in a more Haskell/ML direction. But they seem very opposed to it at the moment.

1: The rationale apparently being "someone might abuse it!" instead of "it makes good libraries even better". Parser combinators, UI toolkit code do great with custom operators. Require a method name (i.e. operator !!= as foo) if it's too great a concern. Can't save yourself from bad writers. Crippling yourself to avoid this seems like a poor tradeoff.

Re: Destroy All Ifs – A Perspective from Functional Programming

#190

Post by MichaelGG »

Rusky wrote: post #105
MichaelGG wrote: post #70

Earlier quoted context omitted.

The annoying part there is the repeated "|x| x.". Rust should have syntax to reference a method of an object, instead of having to write a wrapper. So it'd look like .map_err(???.to_string()).

Rust does have such a syntax: map_err(ToString::to_string).

It's not the same though; it can resolve to different methods based on non-local code. It also doesn't do autoborrow.
Post reply on HN