Functional Programming in C++ (2013) • Hacker News Board

Re: Functional Programming in C++ (2013)

#31

Post by varelse » Sat, Jul 25, 2015, 6:53 PM UTC

peterfirefly wrote: post #28

varelse wrote: post #26

Earlier quoted context omitted.

There is a very active attempt to make GPUs FP-friendly called C++AMP. And for streaming transformation tasks, it's a nice abstraction. https://en.wikipedia.org/wiki/C%2B%2B_AMP However, my best algorithms are stylistically equivalent to a map-reduce with combiners entirely in GPU-space. The map tasks themselves carry all the scope I need. They are independent units of work executed by independent warps (synchronized…

map-reduce is already functional, isn't it? Who cares if you implement the combining with atomic ops or by sending data to a process that does the combining or whether you stuff the data in a buffer and then reduce it afterwards? (Of course you might care for performance reasons -- but conceptually it's the same thing.)

Yes, it is true conceptually, but:

1) "Who cares" is not the sort of thing you want to say to someone who cares about performance because:

2) Sending the data to buffers for subsequent reduction was the first implementation (2009). But it was a memory hog and a 5% or so slowdown to perform the reduction subsequently rather than concurrently with Atomic Ops and 64-bit Fixed Point (2012).

But I guess what we're arriving at is that this is essentially a functional design using imperative code? I can live with that.

Re: Functional Programming in C++ (2013)

#32

Post by peterfirefly » Sat, Jul 25, 2015, 7:35 PM UTC

varelse wrote: post #31

peterfirefly wrote: post #28

Earlier quoted context omitted.

map-reduce is already functional, isn't it? Who cares if you implement the combining with atomic ops or by sending data to a process that does the combining or whether you stuff the data in a buffer and then reduce it afterwards? (Of course you might care for performance reasons -- but conceptually it's the same thing.)

Yes, it is true conceptually, but: 1) "Who cares" is not the sort of thing you want to say to someone who cares about performance because: 2) Sending the data to buffers for subsequent reduction was the first implementation (2009). But it was a memory hog and a 5% or so slowdown to perform the reduction subsequently rather than concurrently with Atomic Ops and 64-bit Fixed Point (2012). But I guess what we're arrivin…

> But I guess what we're arriving at is that this is essentially a functional design using imperative code? I can live with that.

Yep. That's precisely what it is.

Re: Functional Programming in C++ (2013)

#33

Post by nly » Sat, Jul 25, 2015, 7:35 PM UTC

femngi wrote: post #29

overpaidgoogler wrote: post #4

One difficulty with functional style c++ is just how verbose it is. Every time I tried to use std::transform (the equivalent of "map") I had to delete it and rewrite as a loop because it was just too hard to read. Functional style on a large scale is still possible.

It really irks me that the std algorithms library seems to have been designed without any consideration for usability given how much I would love to rely heavily on the generic algorithms it contains. For example consider the simple task of testing to see if an element exists in a container: if (std::find(container.begin(), container.end(), element) != container.end()) My fingers are now cramping and my eyes are cros…

Well the containers that have fast lookup (set, map and their unordered_ and multi_ counterparts), all have efficient .find() member functions. The general philosophy of the idealised STL is not to provide you with anything you can compose efficiently yourself.

A 3-4 line template will will give you a terse boolean contains() method, but it won't give you any big-O guarantees, and having such a thing would encourage very inefficient patterns (like calling contains() and then doing a find() if it's true, which effectively does the lookup twice). Why introduce a weak abstraction? If you're forced to write it yourself you're more likely to understand the implications.

Alex Stepanov, who wrote the original STL, is very much a believer in fundamental indivisible building blocks like iterators and algorithms and careful API design. To grok more about why things are the way they are, I recommend watching his "Efficient Programming with Components" lectures[0]. Over the course he builds up, in excruciating detail, an implementation of merge sort, reasoning about, and discussing with his students, the implications of almost every line of code.

And yes, Stepanov complains about the lack of terseness and expressiveness in C++ as well.

[0] https://www.youtube.com/playlist?list=PLHxtyCq_WDLXryyw91lah...

Re: Functional Programming in C++ (2013)

#34

Post by its_me_ken_lai » Sat, Jul 25, 2015, 7:48 PM UTC

varelse wrote: post #13

brador wrote: post #6

I've noticed hackers/self taught prefer functional programming styles and CS degree holders prefer the more common style.

I'm self-taught and while I can see the formal appeal of functional programming, I'm a low-level coder that implicitly reduces state to bare-metal registers and cache in GPUs and embedded systems. Since I'm already sweating bits over state down to the byte-level, I just don't see what FP would improve on this.

I don't think this applies to you. The main message of the article/blog is that 1) Humans can't keep track of states well and 2) Machines can't create temporary states efficiently and since you're already keeping track of states manually and working at the low enough level where you're maintaining your temporary states, you don't apply.

Re: Functional Programming in C++ (2013)

#35

Post by agumonkey » Sat, Jul 25, 2015, 7:51 PM UTC

thesimpsons1022 wrote: post #11

brador wrote: post #6

I've noticed hackers/self taught prefer functional programming styles and CS degree holders prefer the more common style.

i think people probably just prefer whatever paradigm they used first or currently are comfortable with. I have a cs degree and we were taught scala at my school and now I use it everyday.

I woudln't say 'prefer' but it's a heavy influence on your view of the world. I think imperative programming fit our biological needs and reflex. We want to see results and effects. Functional programmers are up high in the world of platonic ideals. They delay effects by composing abstract logics and then ask for a result. No newbie wanna suffer that, but no newb want to suffer mutable state bug hunts either.. the learning excitement just shadow this issue for a while, and I bet somewhere deep inside, we're all mathematician in the closet.

Re: Functional Programming in C++ (2013)

#36

Post by pcwalton » Sat, Jul 25, 2015, 7:57 PM UTC

nly wrote: post #33

femngi wrote: post #29

Earlier quoted context omitted.

It really irks me that the std algorithms library seems to have been designed without any consideration for usability given how much I would love to rely heavily on the generic algorithms it contains. For example consider the simple task of testing to see if an element exists in a container: if (std::find(container.begin(), container.end(), element) != container.end()) My fingers are now cramping and my eyes are cros…

Well the containers that have fast lookup (set, map and their unordered_ and multi_ counterparts), all have efficient .find() member functions. The general philosophy of the idealised STL is not to provide you with anything you can compose efficiently yourself. A 3-4 line template will will give you a terse boolean contains() method, but it won't give you any big-O guarantees, and having such a thing would encourage…

There is a legitimate complaint with that specific example, though: having to write .begin() and .end() is obnoxious instead of using more modern iterators/ranges.

Re: Functional Programming in C++ (2013)

#37

Post by pcwalton » Sat, Jul 25, 2015, 7:58 PM UTC

phloxicon wrote: post #30

overpaidgoogler wrote: post #12

Earlier quoted context omitted.

I get that. But the two ideas are very closely related. See also my final sentence.

I'm really hopeful that Concepts will dramatically reduce the amount of code needed for std::transform. Imagine no begin() or end(). It would suddenly become less verbose than the classic for loop.

That problem is due to the STL not being built around iterators/ranges. I don't see how concepts enter into it (though contra Andrei Alexandrescu, I'm still a big believer in concepts).

Re: Functional Programming in C++ (2013)

#38

Post by its_me_ken_lai » Sat, Jul 25, 2015, 8:06 PM UTC

throwaway999777 wrote: post #16

brador wrote: post #6

I've noticed hackers/self taught prefer functional programming styles and CS degree holders prefer the more common style.

I thought functional programming[1] was associated with ivory tower CS researchers/enthusiasts? I guess it's been turned on its head for some reason. [1] At least the Haskell/ML kind.

The underlying concept will surface once you've had a chance to debug program states and that you realize you can't keep track of all program states. I had no idea about functional programming but soon realized that I was going for the same thing when trying my best to not keep instance variables in my objects.

Re: Functional Programming in C++ (2013)

#39

Post by rootlocus » Sat, Jul 25, 2015, 8:12 PM UTC

vivekian2 wrote: post #7

On an unrelated note, sad to see altdevblogaday has gone away :( Sure the pages are cached somewhere, but the posts always made for interesting reading.

Couldn't agree more. It went away shortly after I discovered it, and although there's a lot of awesome information in the archives, it's a shame no new content is being added.

Re: Functional Programming in C++ (2013)

#40

Post by nly » Sat, Jul 25, 2015, 8:15 PM UTC

pcwalton wrote: post #36

nly wrote: post #33

Earlier quoted context omitted.

Well the containers that have fast lookup (set, map and their unordered_ and multi_ counterparts), all have efficient .find() member functions. The general philosophy of the idealised STL is not to provide you with anything you can compose efficiently yourself. A 3-4 line template will will give you a terse boolean contains() method, but it won't give you any big-O guarantees, and having such a thing would encourage…

There is a legitimate complaint with that specific example, though: having to write .begin() and .end() is obnoxious instead of using more modern iterators/ranges.

well the slightly more concise way of writing it is this:

    auto e = end(container);
    if (e == std::find(begin(container), e, element)) { ... }

...but yeah, it sucks. If I were doing this though, i'd to be encapsulating things in to a higher level abstraction. Seeing std::find in more than 1 place in a file is a red light for me.