L4Ka – a New Methodology for System Construction

L4Ka – L4Ka Project
Don’t have much interest in OSes or OS research, but this is an interesting project.

Mandatory Error Codes

////////////////////////////////////////////////////////////////////////////////////
// MANDATORY ERROR CODES REVISITED.
// http://www.ddj.com/dept/cpp/191601612
//
// This is implementation is copied from an article I had read about forcing the use of
// error codes in C++ programs. I'm not a fan of error codes in general,
// because I think people should use exceptions instead, but the exception
// model in C++ is so hard to get right, that sometimes I have no choice but to
// use error codes. However, even error codes lose their so called convenience when
// not taken care of. Hence the use of this framework.
//
////////////////////////////////////////////////////////////////////////////////////
#pragma once
#include <string>
#include <stdexcept>

namespace return_code_usage
{
    ///////////////////////////////////////////////////////////////////////////////
    // A simple class to indicate that a return value can be ignored. Used by a
    // programmer who is sure about s/he is doing.
    ///////////////////////////////////////////////////////////////////////////////
    struct ignore_return_code{};

    ///////////////////////////////////////////////////////////////////////////////
    // Simple exception class  that is thrown when a return value is not handled
    // correctly.
    ///////////////////////////////////////////////////////////////////////////////
    class unhandled_return_code_exception
        : public std::exception
    {
    public:
        unhandled_return_code_exception()
            : err_text_("")
        {
        }
        unhandled_return_code_exception(const std::string &err_text)
            : err_text_(err_text)
        {
        }

        const char *what( ) const{
            return err_text_.c_str();
        }

        ~unhandled_return_code_exception(){/* */}
    private:
        std::string err_text_;

    };
    ///////////////////////////////////////////////////////////////////////////////
    // This is the class that wraps the return code. If its not recieved by a
    // return_code class then the exception will not be disarmed, and an exception
    // will be thrown in the destructor.
    //
    // By having a sepereate class with a exception-throwing exception, it is ensured
    // that should a function returning a throwable_return_code object, throws an exception,
    // then an exception from throwable_return_code's destructor is not thrown, when
    // the stack is unwinding.
    ///////////////////////////////////////////////////////////////////////////////
    template <class CODE>
    class throwable_return_code
    {
        template<class CODE> friend class return_code;
    public:
        // constructor recieve the code and arm the exception
        throwable_return_code(CODE r_code)
            : code_(r_code)
            , throw_(true)
        {
        }
        //explicitly ignore error codes and avoid exception
        operator ignore_return_code(){
            throw_ = false;
            return ignore_return_code();
        }

        ~throwable_return_code(){
            //will throw unless something is done to prevent it.
            if (throw_){
                throw unhandled_return_code_exception();
            }
        }
    private:
        CODE code_;
        bool throw_;
    };

    ///////////////////////////////////////////////////////////////////////////////
    // Simple class that recieved the throwable_return_code, and disarms the
    // throwable_return_code exception-throwing destructor. This class is only used
    // by a developer who knows what s/he is doing when disarming the exception.
    ///////////////////////////////////////////////////////////////////////////////

    template<typename CODE_T>
    class return_code
    {
        typedef CODE_T code_type;
    public:
        // Explicit ctor to make sure that hte user of this class
        // knows what s/he is doing
        explicit return_code(throwable_return_code<code_type> &code)
            : code_(code.code_)
        {
            code.throw_ = false;
        }
        ~return_code(){ }
        operator code_type (){
            return code_;
        }
    private:
        code_type code_;
    };
}

Here is test implementation.

#include <iostream>
#include "return_code_usage.hpp"

using namespace std;
using namespace return_code_usage;

void print_function_name(std::string function_name)
{
    std::cout
        << std::string(function_name.size(), '-')<<std::endl
        << function_name                         <<std::endl
        << std::string(function_name.size(), '-')<<std::endl;
}

#define PRINT_FUNCTION_NAME print_function_name(__FUNCTION__)


throwable_return_code<int> fallible_function(){
    PRINT_FUNCTION_NAME;
    return 1;
}

struct point_class{
    int x,y;
    point_class(int x_, int y_)
        : x(x_), y(y_){}
};

// For custom types, need to have overloaded operators for comparison
// not needed for basic types.
bool operator == (const point_class &a, const point_class &b){
    return (a.x == b.x) && (a.y==b.y);
}

throwable_return_code<point_class> another_fallible_function(){
    PRINT_FUNCTION_NAME;
    point_class p(1,2);
    return p;
}

int main(int argc, char *argv[]){
    // Okay
    return_code<int> result1(fallible_function());
    //This doesn'nt work with an explicit constructor
    return_code<int> result2 = (return_code<int>)fallible_function();

    // OK
    if((return_code<int>(fallible_function()) == 0)){

    }

    // OK
    if (0==(return_code<int>)fallible_function()){
    }

    //OK because explicitly ignoring error
    (ignore_return_code)fallible_function();

    //OK
    return_code<point_class> result3 = (return_code<point_class>)another_fallible_function();

    //OK - with thedefinition of overloaded equality operator
    if (return_code<point_class>(another_fallible_function())==point_class(1,2)){
    }

    // OK with overloaded equality operator.
    if (point_class(1,2) == (return_code<point_class>)another_fallible_function()){
    }

    // will throw an exception
    fallible_function();
    return 0;
}

C# training: Days 4 & 5

My week-long training in C# and .Net came to an end today. Today the main topic of discussion was Interop, some form controls that might be interesting, brief coverage of topics like the use of attributes and multithreaded.

While I’m going to give high marks to the instructor, in hindsight the course material should have been selected with some care. The impression that was prevalent in the group was that the course was actually designed for people who had been programming in VB6 and had not heard of the newer technologies. This is probably the reason why the instructor went into painstaking detail about the C#’s language constructs and ridiculous amounts of details on .Net features that seemed to be trivial.

Inspite of all that, I think I gained some information that was of value. One thing that I learnt was about data visualizers. That is something that can be really useful. One way data visualizers can be used is related to debugging intermediate steps for image processing.

Next week, its Winforms training March 28th through March 30th, 2007.

Blog Posts to Note today

Coding Horror has an interesting post on how users are still stuck using JPEG (a standard that dates back to ’80s) and how we should start moving towards JPEG2000 that uses more modern algorithms and achieves better compression and image quality.

On an another note, Programming Musings has done a survey of programming languages for quantum computing. Interest in quantum computing has gone up dramatically since a Candian company called D-Wave recently announced that they had successfully built a quantum computer with a viable design.

http://pipes.yahoo.com/ The next big thing???

I checked this right now.

NI and Labview programmers knew about dataflow programming for more than than a decade before this came out on the scene, and it served the same purpose that pipes is going to serve, mainly trying to get non-programmers to use their imaginations and build nifty new applications. The trouble is that if non-programmers wanted to build new applications, they would’nt be non-programmers but programmers in the first place. Just like non-programmers who used Labview became labview programmers in the end, so will non-programmers who use pipes will become “pipes” programmers.And then, engineers will start looking for the next flashy programming interface.

Closures vs. Objects

A closure is a function that refers to a free lexical variable defined outside it, and that variable must persist as long as the function does.

Paul Graham in “Ansi Lisp”

By that definition, would’nt a pointer to member function that refers to a member variable of a object also be a closure, since its referring to a variable defined in the lexical scope of the class. Thinking about this, I googled it and looked about some comparisons of how closures are done. I realized that the code in the 2nd cut of my solution in this post was a a sort of closure. If you look at the definition of the source code of the nested class,

    template<typename SequenceIterator>
    struct find_max_sum_range_helper
    {
    public:
        find_max_sum_range_helper
            ( typename SequenceIterator::value_type &max_so_far_
            , typename SequenceIterator::value_type &max_ending_here_
            , std::pair<SequenceIterator, SequenceIterator > &p_
            , typename SequenceIterator &current_)
            : max_so_far(max_so_far_)
            , max_ending_here(max_ending_here_)
            , p(p_)
            , current(current_)
        { /* Do nothing else */}

        void operator()(typename SequenceIterator::value_type val){
            if(max_ending_here==0){
                p.first = p.second = current;
            }

            max_ending_here =
                std::max<typename SequenceIterator::value_type>(max_ending_here + val, 0);

            if (max_ending_here > max_so_far){
                max_so_far = max_ending_here;
                p.second = current;
            }
            //increment the current operator;
            ++current;
        }

    private:
        typename SequenceIterator::value_type &max_so_far;
        typename SequenceIterator::value_type &max_ending_here;
        typename std::pair<SequenceIterator, SequenceIterator> &p;
        SequenceIterator &current;
    };

find_max_range_helper refers to variables that are defined outside its lexical scope in find_max_range2, using C++ references as shown below.

...
        typename SequenceIterator::value_type &max_so_far;
        typename SequenceIterator::value_type &max_ending_here;
        typename std::pair<SequenceIterator, SequenceIterator> &p;
        SequenceIterator &current;
...

Finding the Maximum Sum of a Contiguous Subvector of an Input Vector

I had a phone interview around mid-October. In the second half of the interview I was asked the obligatory programming question as follows,

Given an input vector, find the maximum sum of a contiguous sub-vector in that vector. Your algorithm should be in linear time.

This was taken verbatim from the Jon Bentley’s excellent book “Programming Pearls” (2nd. Ed.). I coud’nt solve the problem at the time (and I kicked myself because I owned and had read the book), but it got me thinking about the problem again.

I thought that even though the problem did’nt ask for it, the maximum sum is not very useful. What would be more useful is the actual range of the sub-vector. After all the problem itself was a simplified version of the (as yet open) problem for finding the largest sum of 2-D matrix. I’m not going to go into various details on how the problem can be solved, but I did think about how I could implement a generic version of the algorithm that would dove-tail nicely with various sequences in the STL. (If any reader is interested, I strongly suggest you buy the book). Here is my first cut,



template<typename SequenceIterator>
struct find_max_sum_range
{
    std::pair<SequenceIterator, SequenceIterator>
       operator () (typename SequenceIterator first, typename  SequenceIterator end)
    {
        SequenceIterator::value_type max_so_far = 0;
        SequenceIterator::value_type max_ending_here = 0;
        std::pair<SequenceIterator, SequenceIterator> p;
        for (;first!=end; ++first){
            if (max_ending_here==0){
                p.first = p.second = first;
            }
            max_ending_here =
                std::max<typename SequenceIterator::value_type>(max_ending_here + *first, 0);
            if (max_ending_here > max_so_far){
                max_so_far = max_ending_here;
                p.second  = first;
            }
        };
        //Have to increment STL iterator because the end always points to
        //one incrment beyond
        ++p.second;
        return p;
    }
};

I was’nt very happy with this version. I thought that to keep it in the spirit of STL, I needed to use the proper STL library functions, and in this case the right algorithm to use would be the std::for_each function. The problem with this function is that there is no way to access the current iterator while the algorithm is being executed. (Actually this is a general weakness in the otherwise very powerful STL iterator concept). My second solution got around the problem by using a functor that held a reference to a local iterator that got updated whenever the functor got executed. Hence the second cut of the solution.

template<typename SequenceIterator>
struct find_max_sum_range2
{
private:
    template<typename SequenceIterator>
    struct find_max_sum_range_helper
    {
    public:
        find_max_sum_range_helper
            ( typename SequenceIterator::value_type &max_so_far_
            , typename SequenceIterator::value_type &max_ending_here_
            , std::pair<SequenceIterator, SequenceIterator > &p_
            , typename SequenceIterator &current_)
            : max_so_far(max_so_far_)
            , max_ending_here(max_ending_here_)
            , p(p_)
            , current(current_)
        { /* Do nothing else */}

        void operator()(typename SequenceIterator::value_type val){
            if(max_ending_here==0){
                p.first = p.second = current;
            }

            max_ending_here =
                std::max<typename SequenceIterator::value_type>(max_ending_here + val, 0);

            if (max_ending_here > max_so_far){
                max_so_far = max_ending_here;
                p.second = current;
            }
            //increment the current operator;
            ++current;
        }

    private:
        typename SequenceIterator::value_type &max_so_far;
        typename SequenceIterator::value_type &max_ending_here;
        typename std::pair<SequenceIterator, SequenceIterator> &p;
        SequenceIterator &current;
    };
public:
    std::pair<SequenceIterator, SequenceIterator>
        operator() (typename SequenceIterator first, typename SequenceIterator end)
    {
        SequenceIterator::value_type  max_so_far = 0;
        SequenceIterator::value_type  max_ending_here = 0;
        std::pair<SequenceIterator, SequenceIterator> p;
        SequenceIterator current = first;

        std::for_each(first, end,
            find_max_sum_range_helper<SequenceIterator>(max_so_far, max_ending_here, p, current));

        //increment to make sure that it points to 1 element beyond the last element.
        ++p.second;
        return p;
    }
};

Comparing the various solutions, it seems the implementation using std::for_each was much more complicated, although it abstracted away the alogrithm for every element away from the iteration of the algorithm. My next step would be use to Boost::lambda to make the code somewhat more clearer while trying to stay in the STL spirit of things.

Usage is as follows

    /* TEST 1:
    * Test a sequence of ints using vectors
    */
    int a[]={-3, 2, 4, -7, 2, 6, 8, -3, 2};
    std::vector<int> x(a, a+sizeof(a)/sizeof(int));
    typedef std::pair<std::vector<int>::iterator, std::vector<int>::iterator> vector_iterator_pair;
    vector_iterator_pair vec_pair = find_max_sum_range<std::vector<int>::iterator>()(x.begin(), x.end());
    print_sequence(vec_pair.first, vec_pair.second);
    /* Test 2:
    *   Test a sequence of longs  using lists
    */

    long b[]={-3, 2, 4, -7, 2, 6, 8, -1, 2};
    std::list<long> list_of_longs(sizeof(b)/sizeof(long), 0);
    std::swap_ranges(list_of_longs.begin(), list_of_longs.end(), b);
    typedef std::pair<std::list<long>::iterator, std::list<long>::iterator> list_iterator_pair ;
    list_iterator_pair lp = find_max_sum_range<std::list<long>::iterator>()
        (list_of_longs.begin(), list_of_longs.end());    print_sequence(lp.first, lp.second);

    /* Test 3:
    * Test a single element sequence, using a set of flats
    */
    float ca[]={2.365f};
    std::set<float> set_of_floats(ca, ca + sizeof(ca)/sizeof(float));
    typedef std::pair<std::set<float>::iterator, std::set<float>::iterator> float_iterator_pair;
    float_iterator_pair cp = find_max_sum_range<std::set<float>::iterator>()
        ( set_of_floats.begin(), set_of_floats.end());
    print_sequence(cp.first, cp.second);

Another Day, Another Post…

Don’t have much to write. I might have an interview coming up, so I decided to brush my knowledge of data structures and algorithms. While I was working on link lists, I realized that a big change in how I approached to a data structure problem had come about. There was a time where I would always try to come up with a solution that was always iterative. I understood (or thought I understood) recursion and pointers, but didn’t dare to apply it in the problems I had to solve. I think the reason for that was that I always taught that in order to prove the correctness of a recursive algorithm, I should trace the series of recursive invocation of a recursive algorithm. Being somewhat inept at abstract thought, that was never a good experience.

Plus, the so-called rumor by some “experienced” people that recursion was bad, and that nobody used it in production code, left me biased against recursion.

My attitude towards recursion began to change when I begain to look at Haskell and Prolog. The best way of defining a recursive function was not to think of repeated invocations, but to define the various cases that the algorithm was supposed to cover. Suddenly the abstraction became easier to handle. The repeated invocation technique would actually decrease the abstraction, reducing “understandability”. Today, recursion tends to come to me more naturally than an iterative algorithm. When I looked over the link list excercises that I had coded, almost all of them where recursive. Now I have to convert them to an iterative form just to make sure I understand that bit too. Using recursion made me focus on the problem at hand, rather than coding intricate logic of if...else blocks for handling special conditions for handling the beginning and/or ending of link lists.

Technology Review: The Problem with Programming

Technology Review: The Problem with Programming

These dichotomies (between efficiency versus correctness, efficiency versus programmer time, efficiency versus high-level, et cetera.) are bogus.

– Bjarne Stroustrup

-I could’nt agree more

Read the rest of the interview ( Part 1 and 2 ), and a counter argument here

Good Math, Bad Math : Turing Equivalent vs. Turing Complete

Good Math, Bad Math : Turing Equivalent vs. Turing Complete

The computation theory in this  just flew over my head.