by

Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Activity
    Ed Browne
    @dabro

    @grantrostig concerning tail recursion, that means the very last thing called is the current function. So if you have some fun(T a), it would:

    U fun(T a)
    {
    …
    T b = …
    U c = ...
    …
    if (p(a)) return c;
    else return fun(b);
    }

    what would not work is if you had something like return fun(b-1) + fun(b-2), since + is the last thing called, not fun

    Ed Browne
    @dabro
    However, one means of handling this in a language where TCO is not supported is to move the recursion into a type/class. You can have an object which calls from one member method to another, which then returns back to that method, with NO local variables — all the state is maintained in the object members. With a good optimizing compiler, conceivably you could have just one void method call itself repeatedly in true recursive style — hopefully the optimizer would optimize away the calls when it saw no arguments being passed or returned.
    Ed Browne
    @dabro
    Of course, all one is doing there is moving the “stack frame” into an object; after a little bit of review, you realize that a stack/activation frame is just a “temporary object” placed on the stack, with a function definition providing the class definition, and the function parameters providing an initialization list, and the function prologue/epilogue (provided by the language runtime) being the ctor/dtor. The only difference in operational semantics is an object lays down all the field variables during construction, while a function lays down the local variables as they are reached during the flow of execution. That’s it.
    Another (usually simpler) way is simply to jump up a level of abstraction and avoid the recursion all together.
    1. FP languages will use recursion to provide operations like map or for_each
    2. Recursion with an “accumulator” == a while loop
    3. Simply wrap your imperative loop in a function call and move on with life, eg for_each
    Ed Browne
    @dabro

    The key concepts in converting from loops to recursion are:

    1. Recursion typically likes to “count down”, meaning largest context and decrementing the context until one reaches the base case (e.g. for (int i = n; i>0; --i){…})
    2. Looping typically likes to “count up,” meaning starting from the base case and say working up to n; this is actually formally corecursion
    3. Some problems are naturally recursive (e.g. tree traversal depth first); some are naturally corecursive (e.g. tree traversal breadth first); a few work equally well in both directions. For example, fibonacci is famously used for teaching recursion, but is far simpler and more algorithmically efficient as a corecursion (looping from 0 to n, only remembering the last value and current one).
    4. When you try to force a recursive problem into a corecursive structure, or vice versa, additional “state” is required (stack, vector, memoizing map, etc)
    5. Basically, this means add an “accumulator” variable to your loop or function call to convert from one to another. This may be a “scalar” (physics sense, not C++ sense) int or float for sum, vector or list for keeping track of where you are in a traversal (e.g. a stack of previous choices), or a vector or map for memoizing previous calculations (dynamic programming, making a recursive calculation of fibonacci efficient)

    In non-TCO recursion, the language is using the call stack as the accumulator; in TCO, the language is using the stack frame local variables; in our example shifting recursion into an object, we’re using the object as the accumulator...

    Grant Rostig
    @grantrostig
    called: In-depth: Functional programming in C++
    April 30, 2012 | By John Carmack
    Ed Browne
    @dabro
    @grantrostig very nice lecture by Nash
    Grant Rostig
    @grantrostig
    @AlanU , you asked about a book on functional programming, Here is the only one I have found specifically for c++. It only comes as a kindle, has only "fair" ratings and costs $5 for 150 pages : https://www.amazon.com/Functional-Programming-C-Chris-Weed-ebook/dp/B017AT4OMI
    I have not read it. I prefer paper. ;)
    Ed Browne
    @dabro
    persistent data structures in C++: https://www.youtube.com/watch?v=9nupb1SNo3Q
    Grant Rostig
    @grantrostig
    persistent data structures in C++: https://www.youtube.com/watch?v=9nupb1SNo3Q
    Yes, I posted the same video just above. I even gave a link for the library, see:
    Dec 02 23:02 in this group. We were interleaving comments and so I guess somehow you missed my post. LOL
    Grant Rostig
    @grantrostig
    @dabro see message above.
    Ed Browne
    @dabro
    @grantrostig duh, that’s how I got there :smile: . musta been tired… Good post, thanks.
    Cyrex
    @CyrexSec
    Hi guys
    Anyone online?
    I'm using WTSSendMessageA
    included Wtsapi32.h
    Yet I keep getting this error on build => unresolved external symbol WTSSendMessageA
    Anyone can help me out, can't find anything online
    Grant Rostig
    @grantrostig
    @dabro , I would be very interested in discussing the ideas behind this video: https://www.youtube.com/watch?v=a-RAltgH8tw
    "functional programming is a tool for thought"
    "imperative program is a tool for hacking (I think he means programming)"
    AlanU
    @AlanU
    @Cyrex i can help but i would need to see more of the compiler log to help
    o that was from may
    Grant Rostig
    @grantrostig
    @AlanU , please note that is "room" is for functional programming. Not sure what "cyrex" was talking about, sounds like debugging.
    AlanU
    @AlanU
    yeah just saw that my bad
    William Travis Guillett
    @hexagon62
    I'm not sure if this is the correct channel, but given my question (which has now been answered) is TMP heavy I figured this would be the best channel. I asked how to deduce the types of the parameters of a lambda (or particularly, how to extract their types into a parameter pack). If anybody has any further input on the solution I found, it'd be appreciated: https://gist.github.com/hexagon62/7866ce2b8d6f863919a3c55d1b60d87c
    Grant Rostig
    @grantrostig
    We tried to answer your question. ;) Is the answer "you found" still the same as the one you asked about today seeking for a better solution? Or did you discover something since the last meeting?
    Oh, I just looked at meetup and it appears you did make progress, very good!
    William Travis Guillett
    @hexagon62
    Yup, found a better solution. You guys did give me the mental momentum I needed to continue investigating it.
    It really was as simple as inspecting the operator() overload.
    I'd completely overlooked that you could pull the overload out via decltype(T)::operator()
    So it's as simple as getting a pointer-to-member to it and passing that along to another function. Getting the parameters of a pointer to a method is easy.
    William Travis Guillett
    @hexagon62
    It's still a bit messy if you want to cover everything that could be passed in. Run of the mill pointers-to-member, function pointers, etc. all need their own overloads.
    Nonetheless I am actually surprised how simple the code is.
    William Travis Guillett
    @hexagon62
    It definitely beats what I was already doing, which was explicitly specifying the template parameters. Not really a solution but a workaround.
    Grant Rostig
    @grantrostig
    So the above link is the best version with regard to the question at hand?
    Grant Rostig
    @grantrostig
    @hexagon62
    William Travis Guillett
    @hexagon62
    Right. The first file is the code is just to describe the problem. The second file showcases the solution, but I only bothered to write the overload that takes a lambda.
    So if you look at that link, you'll see both of those files.
    Grant Rostig
    @grantrostig
    I+LE
    Immediately-invoked, inline, initializing, …
    Bar b = [&] () {
    if (auto sp = wp.lock(); sp) return sp->bar();
    return Bar{};
    }();
    or the older way:
    Bar b = wp.lock() ? wp.lock()->bar() : Bar{};
    William Travis Guillett
    @hexagon62

    Doesn't the latter possibly result in two calls to wp.lock when only one is necessary? I suppose that's why it's the older way, but you can do this:

    auto sp = wp.lock();
    Bar b = sp ? sp->bar() : Bar{};

    And now you only make one call and the code is simpler.

    Grant Rostig
    @grantrostig
    The idea was to use declarative style and have definition and initialization on one line (which your version does do to some extent). Yes the two calls is a problem. @hexagon62
    from this video: https://youtu.be/2ouxETt75R4
    Grant Rostig
    @grantrostig
    @hexagon62 your version also creates a variable into the scope.
    William Travis Guillett
    @hexagon62
    Usually just a minor problem. The lambda helps to avoid that, yes. You can also default construct your Bar instance, but that may not be as efficient as using a lambda to initialize it. It may also be equally efficient, depending on how your compiler optimizes things.
    Bar b;
    if(auto sp = wp.lock(); sp) b = sp->bar();
    William Travis Guillett
    @hexagon62
    There are plenty of times where using a lambda in the way you did is a good idea though. I can see it being a useful pattern.
    BrsDreamer
    @BrsDreamer
    hey guys anybody around was wondering to get help on how to add library to C++