Posted: Mar 11, 2012 12:35 am
by mizvekov
VazScep wrote:Interesting. I thought that GTK was the C library and Qt very much the modern C++ library. I suppose they've been around long enough to both be "outdated" in their own ways.

Yes, it is pretty outdated in terms of the c++ feature set it uses. And again, Qt needs a precompiler on top of it all, so you have to keep it in mind that it is even cheating :)

VazScep wrote:
Though since using languages outside the C family, I've come to appreciate technologies like GTK and OpenGL, which use such simple C code that they become almost trivial to bind to from other languages.

Yes, some languages do indeed make it very straightforward to bind to C, something that can't be done well with c++ due to the complex and compiler dependent abi. Don't think that is going to change in the next 20 years.

VazScep wrote:Ugh. No fucking idea, but you might well be right about Java's GUI situation. But I'm not sure Microsoft is doing any better. While looking into GUI development on Windows, I was put off by how quickly Microsoft moved from Windows Forms to Windows Presentation Foundation, and by rumours that Microsoft might be ditching Silverlight and moving to Javascript, and then with their rehaul of the look and feel of their widgets with Windows 8. I've read numerous concerns from developers saying "what does Microsoft want us to use?"

Yes I got the same reaction, although I thought that windows forms was just meant for "backwards compatibility" (for old programmers used to the native windows api)
VazScep wrote:
GUIs to me seem like a problem that no-one in the software industry has ever really figured out, possibly because a user's expectations of a GUI aren't particularly amenable to precise engineering. I'm only messing around with GUIs as part of a hobby project, and I'm doing it in Ocaml using the Ocsigen framework, which has so far blown me away. But even their framework has yet to commit on using callbacks for event handling or to go with the more declarative reactive frameworks.

The whole thing keeps changing a lot anyway. Few years ago most of us wouldn't consider touch screen interfaces, much less multitouch, and now in a few years we will have to consider haptic interfaces.

VazScep wrote:Ah, okay. It would probably vary with the universities anyway. Being at Edinburgh, ML and Haskell are a pretty big deal. Phil Wadler's the professor of computer science here, a position once held by Robin Milner.

Yes, also LUA was a pretty big deal here anyway.

VazScep wrote:Cool. Well, I don't know if I'm going to be able to explain it very well. But here's the most basic idea. Suppose you want to prove stuff in propositional logic. You could do this by writing a SAT solver, but this has a few drawbacks: firstly, the code is probably going to be very complicated, and there's every chance it will contain the odd bug, which is useless for mission-critical verification; secondly, it's not going to scale to logics which are undecidable, such as first-order logic. So you instead work from axiomatics. It turns out that everything in propositional logic can be proven by instantiating the following axioms, and applying modus ponens appropriately:

1) P -> (Q -> P)
2) (P -> Q -> R) -> (P -> Q) -> (P -> R)
3) (~P -> ~Q) -> (Q -> P)

You can code this up as follows:

Code: Select all
-- An encapsulated logical kernel for a Hilbert-style Propositional Calculus

module Propositional (Theorem, Term(..), axiom1, axiom2, axiom3, mp, instTerm, inst,
                      theoremTerm) where

infixr 8 :=>:

data Term a = Var a
            | Term a :=>: Term a
            | Not (Term a)
            deriving (Show,Eq,Ord)

newtype Theorem a = Theorem (Term a) deriving (Eq, Ord, Show)

theoremTerm :: Theorem a -> Term a
theoremTerm (Theorem t) = t

(p,q,r) = (Var "p",Var "q",Var "r")

axiom1 :: Theorem String
axiom1 = Theorem (p :=>: q :=>: p)

axiom2 :: Theorem String
axiom2 = Theorem ((p :=>: q :=>: r) :=>: (p :=>: q) :=>: (p :=>: r))

axiom3 :: Theorem String
axiom3 = Theorem ((Not p :=>: Not q) :=>: q :=>: p)

mp :: Eq a => Theorem a -> Theorem a -> [Theorem a]
mp (Theorem (p :=>: q)) (Theorem p') = [Theorem q | p == p']
                                                 
instTerm :: (a -> Term b) -> Term a -> Term b
instTerm f (Var p)    = f p
instTerm f (Not t)    = Not (instTerm f t)
instTerm f (a :=>: c) = instTerm f a :=>: instTerm f c

inst :: (a -> Term b) -> Theorem a -> Theorem b
inst f (Theorem t) = Theorem (instTerm f t)
Here, the syntax of propositional logic is captured by a simple data-type. The theorems are encapsulated as a type "Theorem" whose data constructors we do not export. Thus, the only theorems that clients can construct are "axiom1", "axiom2", "axiom3"; instantiations of the form "instTerm f thm"; and theorems resulting from modus ponens. It is impossible for a client to ever construct a theorem such as "p -> ~p", since this is not a tautology. The only theorems that can be constructed are precisely the theorems of propositional logic.

Heh pretty sweet. I already had an idea this kind of thing was possible, but I thought it would look much more complicated than that. Powerful type system indeed :)

VazScep wrote:
This is called a "logical kernel" and the advantage of it is that it is made up of very little code and it is easy to verify as bug-free (there isn't even a single loop to consider). So the security of the code here is very secure. You can be sure that clients cannot use this code in ways to generate non-theorems.

On top of this, you wrap a whole load of additional functionality, probably culminating in a complete tautology-checker. But the great thing about the tautology-checker is that its outputs are guaranteed correct with respect to the kernel. The tautology checker would probably input a Term, and if the term is a tautology, it would output a Theorem. And since the only ways to construct theorems are to apply the rules of kernel, you can be absolutely sure that if it does output a theorem, that theorem really is a tautology.

This is just the beginning. The design of the proof tools you build on top are something else.

Great, will start playing with it. Have to dust up the Haskell book to refresh my memory :)

VazScep wrote:Okay, so exponential_distribution is a first-class function? And one thing we're seeing here is the use of templates to parameterise a first-class function? And presumably, there is also partial specialisation going on, to tailor the implementation to doubles as opposed to some other type?

Well more or less. exponential_distribution is the template of a class, it's declaration looks something like:
Code: Select all
template<typename RealType> class exponential_dsitribution { ... }

So yes, it is parametrized to work with any of the float types.
The thing is that instances of classes can be used as functions, if you overload the function call operator '()' for them. These
kinds of classes are usually called Functors in the literature. Here is an example:
Code: Select all
struct B {
    int operator()(int a, int b) { return a + b; }
};

With this you can do:
Code: Select all
B b;
int c = b(2, 3); // c = 5

And indeed, these functors are what many people used to implement lambdas in the past before the standard supported it.
For example, here is how you would have written the example I gave using Functors instead:
Code: Select all
struct B {
        int val;
        B(int v) : val(v) {}
        ~B() { std::cout << "bye " << val << std::endl; }
};

std::function<int(int)> f(std::shared_ptr<B> b) {
        //here is different, we use Functors instead of
        //return [b](int a) -> int { return a + b->val; };
        //notice how it is much more verbose
        struct Functor {
                std::shared_ptr<B> b;
                Functor(std::shared_ptr<B> b_) : b(b_) {}
                int operator()(int a) { return a + b->val; }
        };

        Functor f(b);
        return f;
}

std::function<int(int)> g() {
        auto a = std::make_shared<B>(10), b = std::make_shared<B>(20);
        return f(a);
}
int main() {
        {
                auto foo = g();
                auto bar = std::bind(foo, 1);
                std::cout << foo(2) << ' ' << bar() << std::endl;
        }
        std::cout << "the end" << std::endl;
}

It's much more cumbersome, but you can think of it as essentially the same thing as lambdas. Indeed, this is probably how the compilers implement them internally. The differences though are that there is no "this" pointer of the lambda itself which you can access, and that the variables which are captured are declared as "const" by default.
The first point allows you to use the parents 'this' pointer seamlessly.
Example:
Code: Select all
struct Foo {
     int var;
     std::function<void()> bar() {
            return [this]() {
                 var = 10; // accessing the parents 'var' field implicitly through the this pointer
                               // it's something more cumbersome to do with Functors...
            };
     }
};

The second point can be changed by declaring the lambda mutable, like this:
Code: Select all
[b]() -> int mutable { return b++; }

With the above, only the lambda's internal copy of b changes.
So you can have lambdas with mutable state, which can sometimes be necessary.

By the way, as an aside, I have been declaring the lambdas to capture explicitly, just to be more clear what is happening,
but you can capture implicitly.
Examples:
Code: Select all
[=]( ... ) { ... } //capture all variables by value
[&]( ... ) { ... } //capture all variables by reference
[&, b]( ... ) { ... } //capture all variables by reference, except b, which is to be captured by value

And variables are only captured if either they are captured explicitly, or else there is a default capture AND they are actually used in the code.
So it is pretty safe to just capture by default.

VazScep wrote:Can you use bind with any function, or does it have to be declared in a special way? And how does this interact with the object system?

std::bind is actually declared as a template, but you don't have to specify the type manually because it can infer from the type of the target. That means that you can use it with any type which you can use the function call operator, and that means any conventional function, class methods, Functors (which are the classes that overload the function call operator, as I said above), lambdas, and most probably anything a future standard defines which satisfies the requirement.

VazScep wrote:
Can I get a virtual function of a class as a first-class function, and have it close over its instance?

I don't see why not, but I think you have to be careful there to pass the instance as a reference to bind, or else you would be passing it a copy of it's instance instead.

By the way, as another aside, I think I may have made that example more confusing by writing it as a one liner.
The below is equivalent:
Code: Select all
std::default_random_engine eng;
std::exponential_distribution<double> dist(1.0);
auto random = std::bind(dist, eng);
for (;;)
    std::cout << random() << std::endl;

When I originally wrote:
Code: Select all
auto random = std::bind(std::exponential_distribution<double>(1.0), std::default_random_engine());

I was actually constructing exponential_distribution and default_random_engine in place, so I did not have to name them.

VazScep wrote:
That is very sweet. Have you compared it much to the random generators in Haskell? It looks pretty competitive in terms of expressive power (speedwise, forget it).

Not yet, but I will.