python to c++?

[Dy7SLyTq]

so im learning how to build a web browser through udacity (its actually teaching you how to interpret javascript/html and javascript is very similar to the language im making so it works great) except udacity is a huge python fan and i want to write mine in c++. im not a novice to python, however i havent done anything too advanced in it. so anyways my question is how difficult is it (usually) to convert python statements to equivalent c++ ones? i would prefer to do it by hand because ive read that translators like that dont usually work well, and it would be good practice

[ResidentBiscuit]

If you're making a web browser, you're going need to several languages. I think Firefox is written in a combination of four different languages.

This comes back down to pick the right tool for the job. C++ isn't the be all - end all language.

[Dy7SLyTq]

i understand that. thats not why i picked c++. the web browser is just to teach people lexers parsers and the such. its not actually to teach how to build top of the line products

[m4ster r0shi]

the web browser is just to teach people lexers parsers and the such

I saw in your other thread that you're using PLY for this. Do you absolutely have to use it (i.e. is this a course requirement)? I've written a toy language compiler using flex and bison and it was a painful experience. I'll never do it again, especially now (that I know) that we have GLL [1]:

This paper introduces a new algorithm, Generalised LL (GLL) parsing, which handles all (including left recursive) context free grammars; runs in worst case cubic time; runs in linear time on LL grammars and which also allows grammar rule factorisation, with consequential speed up. Most importantly, the construction is so straightforward that implementation by hand is feasible: indeed we report on the performance of a hand constructed GLL parser for ANSI C. The resulting code has the RD-property that it is essentially in one-to-one correspondence with the grammar, so parsers may be debugged by stepping through the generated code with a conventional debugger. We believe that GLL will become the generalised parsing algorithm of choice.

In general, top-down parsers (like LL) are much easier to write (as they closely follow your grammar's structure), easier to add semantic actions to, and easier to debug (no cryptic shift-reduce or dreaded reduce-reduce conflicts) than bottom-up (like LR) parsers. The main advantage LR parsers have over LL parsers is that they can parse a bigger subset of context-free grammars. Well, this changed with GLL. GLL can parse any context-free grammar, even ones with hidden left recursion, which GLR can't handle. Plus, it's easy to write parser combinators that use GLL, and there's this really cool guy who even made a step by step tutorial on how you can do that -> [2].

how difficult is it (usually) to convert python statements to equivalent c++ ones?

They're both imperative languages, which is a good thing. Imperative constructs (assignments, conditionals, procedures, loops) should be straightforward to translate from one language to the other. Python is also functional in that it treats functions as first class citizens (you can pass them as arguments to and return them as results from other functions), which may be a small problem. A possible solution could be to use function objects (objects that overload the () operator) instead of functions in C++. Lastly, if the python code uses some exotic library, you'll have to google for its C++ equivalent.

I think using both languages would be a good exercise. Follow the course's flow and do it in python first.
Then, think about what parts could be better if they were written in C++ and do the conversion.

[1] http://dotat.at/tmp/gll.pdf
[2] https://github.com/epsil/gll

[m4ster r0shi]

I see that my words haven't reached you (yet), so, I'll just leave this -> [1] here
in case you change your mind and I promise that I won't bother you anymore :P

I believe it is possible to convert it (almost) verbatim to C++ with some help from boost. Here's my initial approach -> [2] (it can already handle right recursive grammars - which isn't a big feat, though). I decided
to define the generators and combinators this way, because it is possible to write a generic memoization
routine that can be used with functions defined this way. Example:

#include <functional>
#include <iostream>
#include <map>

template <class R, class V>
std::function<R (V)> memo(std::function<R (V)> fn) {

    std::map<V, R> cache;

    return [=](V arg) mutable {

        if (cache.find(arg) == cache.end()) {
            cache[arg] = fn(arg);
        }

        return cache[arg];
    };
}

typedef unsigned long long ull;

std::function<ull(ull)> fib = [](int n) {

    return (n == 0 || n == 1) ?
                1ull :
                fib(n - 1) + fib(n - 2);
};

int main()
{
    fib = memo(fib);

    for (int i = 0; i < 90; ++ i)
        std::cout << fib(i) << std::endl;
}

However, I realized that this would not fit my needs, after all, as it's also necessary to be able to use functions as keys for the original code to work, and it's not possible to hash or compare (an) std::function(s) the way I want (or at all, for that matter), AFAIK. I think I'll have to write a new class for each function and somehow provide a unique id for each class (not instance), essentially wrapping std::function with extra functionality.
I'll give it a try when I find more time. Meanwhile, if anyone has a better idea, I'd like to know it.

[1] http://ideone.com/nEcJBD
[2] http://ideone.com/ie0B5g

[Dy7SLyTq]

sorry master roshi. i actually had clicked on this post and saw that you gave what looked like a good explanantion, but only had time to skim it. when i was able to read it, it was the next day and i had forgotten it (i rely on the [new] icon, which i see now is a bad habit) i didnt mean any disrespect to your help.

thanks. yes ply is a course requirement. and i realized that i made a mistake in what i was asking. i decided to write my own lexer based on ply, which hasn't been too difficult so far, and as a result can't do a line to line translation, as i thought i could. i know that compiler development is hard, but its an area of programming i want to get in and i would learn better if i write most of the code myself than use a lot of libraries (i am using boost for the regex, because there is no way in hell that i can write one myself (yet)). that paper looks interesting and ill read it. thanks for the recommendation. about your code, could you explain some of it? maybe its just pseudo code and i didnt see that, but a lot of the expressions you used i dont really understand

edit: do you ride a turtle?

[m4ster r0shi]

i didnt mean any disrespect to your help

Oh, no, no, I didn't see it that way. I just thought that you were skeptical about whether
you should use GLL combinators and decided to 'help' you decide in a more concrete way.

yes ply is a course requirement

Ok, no need to bother with my recommendation then.

i would learn better if i write most of the code myself than use a lot of libraries

I agree with this. This is why I recommended GLL combinators. PLY is a parser
generator library. The combinators are something you would write yourself
and learn something about functional programming in the process.

maybe its just pseudo code

All my snippets (python and C++) are actual code. The github repository I linked to also contains
actual code. Since you decided to go with PLY, you can ignore them for now and revisit them later.

do you ride a turtle?

Only occasionally.

Perhaps I should have just made a new thread...

[Dy7SLyTq]

yeah it looks interesting. ill read it tomorrow when my brain isnt fried. and the only reason why im using ply is because its a course requirement, but im more than happy to intergrate into my c++ one. alright if they are actual code then i have some questions. firstly, could you explain the declaration of fib? i have never used <functional> before. secondly what do the various lambda expressions do? i never used functional expressions before and still a little confused by them

[m4ster r0shi]

<functional> is required for std::function. std::function is a wrapper for 'callable things' (i.e. usual functions, functors (aka function objects (i.e. objects that overload the () operator)), lambda expressions). A lambda expression essentially is an anonymous function object. They are especially convenient when used with higher order functions (functions that take other functions as arguments) that operate on containers (e.g. sort, find_if, ... etc.) Googling for introductory examples on the terms above will yield results much faster than I can type, so, I'll just focus on explaining the fibonacci snippet.

Consider a simple fibonacci function:

#include <iostream>

typedef unsigned long long ull;

ull fib(int n) {

    return (n == 0 || n == 1) ?
                1ull :
                fib(n - 1) + fib(n - 2);
}

int main()
{
    for (int i = 0; i < 90; ++ i)
        std::cout << fib(i) << std::endl;
}

Executing this will take some time (if it doesn't, try increasing the upper limit for i I'm in love with your pc).
This is because many of the fibonacci terms are evaluated over and over again. It can be made faster by
simply caching the results of fib calls and using them later, when required:

#include <iostream>
#include <map>

typedef unsigned long long ull;

ull fib(int n) {

    static std::map<int, ull> cache;

    if (n == 0 || n == 1)
        return 1ull;

    if (cache.find(n) == cache.end())
        cache[n] = fib(n - 1) + fib(n - 2);

    return cache[n];
}

int main()
{
    for (int i = 0; i < 90; ++ i)
        std::cout << fib(i) << std::endl;
}

There is a special term for this tranformation and it is 'memoization'. Notice that the
program executes instantly now. There are two problems with this approach though:

(1) The memoized function definition is somewhat ugly.
(2) You have to do this for every function you want to memoize.

Fortunately, both these problems can be solved by encapsulating the memoization transformation
into a separate function. That function will accept any function and return a memoized version of it:

#include <functional>
#include <iostream>
#include <map>

template <class R, class V>
std::function<R (V)> memo(std::function<R (V)> fn) {

    std::map<V, R> cache;

    return [=](V arg) mutable {

        if (cache.find(arg) == cache.end()) {
            cache[arg] = fn(arg);
        }

        return cache[arg];
    };
}

typedef unsigned long long ull;

ull fib(int n) {

    return (n == 0 || n == 1) ?
                1ull :
                fib(n - 1) + fib(n - 2);
}

int main()
{
    auto fib_m = memo(std::function<ull(int)>(fib));

    for (int i = 0; i < 90; ++ i)
        std::cout << fib_m(i) << std::endl;
}

Hmm.... There's something wrong here. This executes at the speed of the original (unmemoized) version. The problem is that only the first call to fib is memoized. The recursive calls fib(n - 1) and fib(n - 2) use the original, unmemoized function. The next and final step is this:

#include <functional>
#include <iostream>
#include <map>

template <class R, class V>
std::function<R (V)> memo(std::function<R (V)> fn) {

    std::map<V, R> cache;

    return [=](V arg) mutable {

        if (cache.find(arg) == cache.end()) {
            cache[arg] = fn(arg);
        }

        return cache[arg];
    };
}

typedef unsigned long long ull;

std::function<ull(ull)> fib = [](int n) {

    return (n == 0 || n == 1) ?
                1ull :
                fib(n - 1) + fib(n - 2);
};

int main()
{
    fib = memo(fib);

    for (int i = 0; i < 90; ++ i)
        std::cout << fib(i) << std::endl;
}

This works as expected, because now fib itself is redefined. And for this to be possible, it was
necessary to change fib's way of definition, as you can't redefine a normal function in C++.

EDIT:

DTSCode (below) wrote:

thanks for this... once again im grateful that there are
smarter people than me willing to share their knowledge.

There are no smarter people than you.
You are as smart as anyone else.
You just don't know it yet ;)

[Dy7SLyTq]

thanks for this... once again im grateful that there are smarter people than me willing to share their knowledge.