Monthly Archives: May 2011

callable entity

  By Sarang Baheti | 31 May, 2011 - 9:25 PM | ,
2 Comments

C++ is language of functions – global, instance or class functions. However it is not just functions that are callable. C++ provides an operator() to make even objects behave as if they were functions, affectionately known as functors, function objects to be more precise. With C++0x lambda’s have been added to callable entity’s list.

Overall here is the summary of the callable objects:

#include <algorithm>
//
//
template
int length(T (&arr)[N] )
{
    return N;
}
//
//
template
T* end(T (&arr)[N])
{
    return arr+N;
}
//
//
template
struct Comparator
{
    const Type& _comparisonObject;
    Comparator(const Type& obj) : _comparisonObject(obj)
    {}
    bool operator()(const Type& other) const
    {
        return other == _comparisonObject;
    }
};
//
//
int tobefound = 0;
//
//
bool find_function(int val)
{
    return tobefound == val;
}
//
//
int main()
{
	//
    int arr[] = {0,1,2,3,4,5,6,7,8,9};
    //  using function
    //  tobefound is global variable
    //
    //  Readability/Maintainability -- (Ok)
    //
    tobefound = 5;
    auto iterator1 = std::find_if(arr, arr + length(arr), find_function);
	//
    bool found1 = iterator1 != end(arr);
	//
	//
    //  using function_pointer
    //  uses the find_function's pointer to
    //  find the object, one can change the function used on fly
    //
    //  Readability/Maintainability -- (Ok--)
    //  function pointer can get ugly very quickly
    //
    typedef bool(*CompareFunc_t)(int);
    CompareFunc_t compareFunc1 = find_function;
	//
    auto iterator2 = std::find_if(arr, arr + length(arr), find_function);
	//
    bool found2 = iterator2 != end(arr);
	//
	//
    //  using functor (function object)
    //  comparator object stores state of what needs to be found
    //
    //  Readability/Maintainability -- (Good)
    //  can change the object that compares, plus no global state to be
    //  maintained
    //
    Comparator comparator(tobefound);
	//
    auto iterator3 = std::find_if(arr, arr + length(arr), comparator);
    bool found3 = iterator3 != end(arr);
	//
	//
    //  using lambda's
    //
    //  benefits of functor - functor class definition
    //
    //  Readability/Maintainability -- (Better)
    //
    auto iterator4 = std::find_if(arr, arr + length(arr),
                                [](int val) {return val == tobefound;});
	//
    bool found4 = iterator4 != end(arr);
	//
	//
    return 0;
}
//

The last bit of code demos the newly added functionality in C++0x, lambda. Lambda’s are un-named function objects that can maintain state (optional). They promote use of functional programming and the use of small un-named functions that we generally need with STL.

Lets look at this lambda:

[](int val) {return val == tobefound;}

[] – indicates start of a lambda, un-named local function object

(int val) – takes one parameter of type int by value

{return val == tobefound;} – defines function body. Here the variable tobefound is captured by value, for this un-named function object and it returns bool.

Here is what compiler generates for lambda’s:

	//
	int tobefound = 5;
    auto lambda1 = [tobefound](int val) {return val == tobefound;};
    //
	//
	class UnNamedLocalFunction
    {
        int localVar;
		//
    public:
        UnNamedLocalFunction(int var) : localVar(var)
        {}
		//
        bool operator()(int val)
        {
            return val == localVar;
        }
    };
	//
	//
    UnNamedLocalFunction lambda2(tobefound);
	//
    bool is5_one = lambda1(5);
    bool is5_two = lambda2(5);

Here both lambda1 and lambda2 are equivalent. Thus lambda’s are syntactic sugar. Note this is one of the vary basic usage of lambda.

This post is one of the basic post for upcoming ones on functional programming and lambdas.

Stay tuned…

Related articles

The Pentium: An Architectural History of the World’s Most Famous Desktop Processor

  By Sarang Baheti | 30 May, 2011 - 10:50 PM |
1 Comment


Introduction

I’ll never forget when Intel first announced that the name for the successor to the 486 would be “Pentium.” I and most of my fellow computer nerds thought the name was silly and not suitably geeky. Everyone knew that computer components were supposed to have names with numbers in them; after all, Star Wars droids, Star Trek ships, software versions, Compuserve e-mail addresses, and every other kind of computer-related thing you could think of had a moniker consisting of some mix of numbers and letters. So what’s with a name that vaguely suggests the concept of “fiveness,” but would be more appropriate for an element or a compound?

To this day, I still have no idea who or what was responsible for the name “Pentium,” but I suppose it no longer matters. A question that’s still worth asking, though, is why the Pentium name has stuck around as the brand name for Intel’s main processor product line through no less than four major architectural changes. In a nutshell, the answer is that the Pentium brand name, having somehow made the transition from the original Pentium architecture to the radically different Pentium Pro (or P6) architecture, became synonymous with the most successful desktop microprocessor architecture of all time ? in fact, in its heyday “Pentium” became virtually synonymous with “PC.”

This series of articles takes a look at the consumer desktop processors that have borne the Pentium name, beginning with the original Pentium up through today’s Pentium 4 (Prescott) and Pentium M divisions. The overview is general enough that for the most part it should be accessible to the nonspecialist, and it should give you a sense of the major differences between each generation of Pentiums. In keeping with the Ars tag line, the article does not attempt to tell you everything about every iteration of the Pentium; instead, it covers only what you need to know.

continue reading…

A History of the GUI

  By Sarang Baheti | 29 May, 2011 - 10:36 PM |
Comments Off

Introduction

Today, almost everybody in the developed world interacts with personal computers in some form or another. We use them at home and at work, for entertainment, information, and as tools to leverage our knowledge and intelligence. It is pretty much assumed whenever anyone sits down to use a personal computer that it will operate with a graphical user interface. We expect to interact with it primarily using a mouse, launch programs by clicking on icons, and manipulate various windows on the screen using graphical controls. But this was not always the case. Why did computers come to adopt the GUI as their primary mode of interaction, and how did the GUI evolve to be the way it is today?

In what follows, I’ll be presenting a brief introduction to the history of the GUI. The topic, as you might expect, is broad, and very deep. This article will touch on the high points, while giving an overview of GUI development.

Prehistory

Like many developments in the history of computing, some of the ideas for a GUI computer were thought of long before the technology was even available to build such a machine. One of the first people to express these ideas was Vannevar Bush. In the early 1930s he first wrote of a device he called the “Memex,” which he envisioned as looking like a desk with two touch screen graphical displays, a keyboard, and a scanner attached to it. It would allow the user to access all human knowledge using connections very similar to how hyperlinks work. At this point, the digital computer had not been invented, so there was no way for such a device to actually work, and Bush’s ideas were not widely read or discussed at that time.

However, starting in about 1937 several groups around the world started constructing digital computers. World War II provided much of the motivation and funding to produce programmable calculating machines, for everything from calculating artillery firing tables to cracking the enemy’s secret codes. The perfection and commercial production of vacuum tubes provided the fast switching mechanisms these computers needed to be useful. In 1945, Bush revisited his older ideas in an article entitled “As We May Think,” which was published in the Atlantic Monthly, and it was this essay that inspired a young Douglas Englebart to try and actually build such a machine. (more…)

30 years of personal computing

  By Sarang Baheti | 29 May, 2011 - 10:29 PM |
Comments Off

Electronic digital computers moved out of science fiction and into reality during World War II. Less powerful than a modern pocket calculator, the first real job for these massive machines was to speed up the calculation of artillery firing tables.

Thirty years later, computers had firmly cemented themselves in the public imagination. They were huge boxes, covered with blinking lights and whirring reels of tape. Banks and big corporations all had computer rooms, closely guarded by a priesthood of programmers and administrators. Science fiction novels and movies imagined impossibly brilliant supercomputers that guided spaceships and controlled societies, yet they were still room-sized behemoths. The idea of a personal computer, something small and light enough for someone to pick up and carry around, wasn’t even on the radar.

Even the major computer companies at the time didn’t see the point of small machines. The mainframe industry was dominated by IBM, who was the Snow White to the Seven Dwarves of Burroughs, CDC, GE, Honeywell, NCR, RCA and Univac. Mainframes took up entire floors and cost millions of dollars. There was also a market for slightly smaller and less expensive minicomputers, machines the size of a few refrigerators that sold for under a hundred thousand dollars. This industry was dominated by Digital Equipment Corporation (DEC), with strong competitors such as Data General, Hewlett-Packard and Honeywell-Bull. None of these companies considered the personal computer to be an idea worth pursuing.

It wasn’t that the technology wasn’t ready. Intel, at the time primarily a manufacturer of memory chips, had invented the first microprocessor (the 4-bit 4004) in 1971. This was followed up with the 8-bit 8008 in 1972 and the more-capable 8080 chip in 1974. However, Intel didn’t see the potential of its own product, considering it to be useful mainly for calculators, traffic lights, and other embedded applications. Intel had built a reference design with a microprocessor and some memory that could be programmed using a terminal, but it was used for testing purposes only. An Intel engineer approached chairman Gordon Moore with the idea for turning it into a consumer product, but Moore, with a rare lack of insight, couldn’t see any practical purpose for such a device and decided not to go ahead with the project.

The task of inventing the personal computer, and with it the personal computer industry, was left instead to the manager of a small, little-known calculator company in Albuquerque, New Mexico. His name was Ed Roberts.

continue reading…

auto and decltype

  By Sarang Baheti | 28 May, 2011 - 5:59 PM |
1 Comment

auto

In one of the previous posts we have explored auto in detail, however there are few places where auto cannot be used. One of them happens to be the function argument and return type:

Consider some code:

auto function(auto var)
{
    return var;
}

int main()
{
    int var = function(4);
    double d = function(8.9);

    return 0;
}

Here compiler cannot deduce the argument type. As in both the case args are being passed by value, and double is 8 bytes while int is 4 bytes. This cannot work as compiler needs to allocate memory for args passed by value and they have to be of same type (or convertible) but in case of auto compiler won’t look for implicit conversion.

If your intention was to write a generic function that can deduce the argument and return type then better go with templates.

 

decltype

decltype and auto go hand-in-hand. auto means compiler should infer the type, while decltype means I already have an expression now deduce it’s type. Now here expression can be something that is a valid statement in C++, actually that evaluates to something.

int main()
{
    int i = 0;

    //  now j is of type int
    decltype(i) j = i;

    const int& k = i;

    //  var is of type const int&
    decltype(k) var = k;

    return 0;
}

decltype does not evaluate expression, rather it checks for the type of the expression.

Consider:

#include <vector>
#include <set>

std::vector<int> ToVector(const std::set<int>& vals)
{
    return std::vector<int>(vals.cbegin(), vals.cend());
}

int main()
{
    std::set<int> vals;
    
    //  here ToVector(vals) is an expression -- resulting in std::vector<int>
    //  
    decltype(ToVector(vals)) vec = ToVector(vals);

    //  also you could have written:
    //  fails to compile with error: "illegal use of this type as an expression"
    //
    decltype(ToVector(std::set<int>)) vec1 = ToVector(vals);

    //  however this would work:
    //  std::set<int>() is an expression
    //
    decltype(ToVector(std::set<int>())) vec2 = ToVector(vals);

    //  all of this can be achieved using auto as well
    //
    auto vec3 = ToVector(vals);

    return 0;
}

So what is the difference between decltype and auto? auto makes compiler infer types while decltype makes compiler evaluate type of an expression.

consider: (AutoDemo class comes from post on auto)

class AutoDemo
{
public:
    AutoDemo()
    {}

    operator double()
    {
        return 8.0;
    }
};

int main()
{
    //  autoVar1 is of type AutoDemo
    auto autoVar1 = AutoDemo();

    //  autoVar2 is of type double
    //
    auto autoVar2 = static_cast<double>(autoVar1);

    //  don't have to cast explicity to get the required type
    //  here double() is an expression as it default constructs
    //  a double on the fly and it's type evaluates to double
    //  so doubleVar is of type double and perator double() kicks in
    //
    decltype(double()) doubleVar = autoVar1;

    return 0;
}

 

decltype unleashed

Codes described above are simple examples to demonstrate decltype functionality, lets tackle one of the C++ Meta Programming problems to see the real power of decltype with templates.

Problem:

return true if the type has function push_back else false.

We are familiar with vector and list, both of these STL containers are sequential and have push_back function, while set is an associative container and does not have any function named push_back. We want to write program such that given a type we want to know if it has function named push_back or not. It should not fail to compile!

This problem comes from comp.lang.c++.moderated

Solution:

Note: The solution code works with GCC 4.6 only. VS 2010 SP1 can compile the code but is busted and does not evaluate the overload correctly.

See here for how to install GCC on windows

 

#include <iterator>
#include <vector>
#include <iostream>
#include <set>
#include <list>

template<class Cont>
struct has_back_insertion
{
    template <class U>
    static double test(...);

    //  this is equivalent to:
    //  
    //  static char test(void* ptr) 
    //  as vector::push_back returns void
    //  so does list::push_back
    //  
    //  have fun reading and making sense of this decltype declaration
    //
    template<class U>
    static char test(decltype(U().push_back(
                    decltype(typename std::iterator_traits<
                    decltype(U().begin())>::value_type())()))* ptr);

    enum
    {
        //  if the Cont has push_back function, then
        //  char test(void* ptr)  is preferred over double test(...);
        //  
        value = sizeof(test<Cont>(nullptr)) == sizeof(char)
    };
};


int main()
{
    //  vechasback -- true
    //
    bool vechasback = has_back_insertion<std::vector<int>>::value;

    //  sethasback -- false
    //
    bool sethasback = has_back_insertion<std::set<int>>::value;
    
    //  listhasback -- true
    //
    bool listhasback = has_back_insertion<std::list<int>>::value;

    //  doublehasback -- false
    //
    bool doublehasback = has_back_insertion<double>::value;

    std::cin.ignore();

    return 0;
}

Dissecting function match code:

  
//  U is the container being passed as types dont work with decltype
//  we create an object with U()
//  we want to enquire that push_back function is availabe so 
//  call push_back on U()
//
decltype(U().push_back(decltype(typename std::iterator_traits<
decltype(U().begin())>::value_type())()))* ptr);

//  but push_back function takes in 
//  value as well so 
//  typename because we are using generic type in a template
//  then we query the value_type from iterator, that's why
//  iterator_traits
//
decltype(typename std::iterator_traits<decltype(U().begin())>::value_type())

//  but it needs iterator type 
//  and again decltype comes in picture with
//  here we U().begin() returns U::iterator
//  again decltype does not work with types so expression
//
decltype(U().begin())

I have covered decltype and auto in sufficient detail for further exploration. has_back_insertion template uses a very powerful technique, overload-resolution, for use in C++ Templates and C++ Template Metaprogramming. We will see some of these in details in later posts.

Till then have fun…