bash tricks

This post is to be an ongoing post on the things I find cool in bash.

Brace completion:

This is really neat. You can make braces expand all possible completions of a name, space separated.

For example:

cp file.c{,.bak}

expands to:

cp file.c file.c.bak

That makes a backup. Each comma separated option within braces is substituted once. That is why the first option copies file.c as is, since its adding nothing.

CDPATH:

CDPATH is a really cool way of quickly going to directories. The idea is simple -cdpath is a list of paths through which directories are searched, not just the current directory. So, for example, if my CDPATH is:

export CDPATH=.:~:/cygdrive/c/code:/cygdrive/c/Documents

And say I have a directory "ftpapp" in code, and "Training", in documents, I can do this:

$ pwd
/cygdrive/c/work/misc/tada

$ cd ftpapp
/cygdrive/c/code/ftpapp

$ pwd
/cygdrive/c/code/ftpapp

$ cd Training
/cygdrive/c/Documents/Training

$ pwd
/cygdrive/c/Documents/Training

CDPATH allows a list of directories to be searched for the directory you are cd-ing to. Tres cool.

Model View Controller

The model view controller is a compound pattern. Its three parts are described as:

Model: This is the business logic of the application - things like its data, its underlying rules, things like that.

View: A view is a representation of the data to the user. For example, it could be a graphical widget that shows the current data, and updates itself when the data changes.

Controller: Controller deals with user input and handles the complexity of decision making on how to transform user actions into operations on the model.

So, what design patterns are we talking about?

- First off, the interface between the model and its clients (both view and controller) follows the Observer pattern. Both views and controllers register as observers on the model. This way when data changes, the view can update itself automatically. Also, the controller can transform the view based on certain things in the model changing.

- Second design pattern is Strategy. The controller is a strategy, that the view is composed with. A view can be composed with a different controller to get different behavior.

- Third design pattern is Composite, used by the view in its internal implementation. Typically view is a tree of menus, controls, etc. By telling the top level control to draw itself, the view can make the entire UI draw itself (for example) by using the Composite pattern.

More design patterns

Factory method:
"The Factory method pattern defines an interface for creating an object, but lets subclasses decide which class to instantiate. Factory method lets a class defer instantiation to subclasses."

Abstract factory:
"The abstract factory pattern provides an interface for creating families of related or dependent objects without specifying their concrete classes"

Singleton:
"The singleton pattern ensures that a class has only one instance, and provides a global point of access to it."

Command:
"The Command pattern encapsulates a request as an object, thereby letting you parameterise other objects with different requests, queue or log requests, and support undoable operations."

Adapter:
"The adapter pattern converts the interface of a class into another interface the clients expect. Adapter lets classes work together that couldn't otherwise because of incompatible interfaces."

Facade:
"The Facade pattern provides a unified interface to a set of interfaces in a subsystem. Facade defines a higher-level interface that makes the subsystem easier to use."

Template method:
"The Template method pattern defines the skeleton of an algorithm in a method, deferring some steps to subclasses. Template method lets subclasses redefine certain steps of an algorithm without changing the algorithm's structure."

Iterator:
"The Iterator pattern provides a way to access the elements of an aggregate object sequentially without exposing its underlying representation."

Composite:
"The Composite pattern allows you to compose objects into tree structures to present part-whole hierarchies. Composite lets clients treat individual objects and compositions of objects uniformly."

State:
"The State pattern allows an object to alter its behavior when its internal state changes. The object will appear to change its class."

Proxy:
"The Proxy pattern provides a surrogate or placeholder for another object to control access to it."

Sorting a file in C++

I always get amazed when I see the conciseness of this code (from The C++ programming language, by Bjarne Stroustrup). Its C++, not supposed to be as concise as a non statically-typed, typically interpreted, language.

This code will read in the names of two files, open the first file, read all the words in it, sort them alphabetically, remove duplicates, and write it to the second file.



int main()
{
string from, to;
// Read input filenames
cin >> from >> to;

// Open the input file as an ifstream
ifstream is(from.c_str());
// Get a string iterator over input file
istream_iterator ii(is);
// The default istream_iterator indicates EOF
istream_iterator eos;

// Read each word of the file into the vector
vector b(ii, eos);

// Sort all the words
sort(b.begin(), b.end());

// Open output file
ofstream os(to.c_str());

// Create an output iterator for the file, which will write a "\n" each time along
// with the string
ostream_iterator oo(os, "\n");

// Copy the vector into the file, skip dups
unique_copy(b.begin(), b.end(), oo);

// Error code - return 0 for successful completion
return( !is.eof() || !os);
}


This is truly a brilliant demonstration of abstraction. By creating iterators to deal with the input and output files, we can use the C++ standard library algorithms to do a variety of useful things. Truly beautiful.

How to create a linked list in Perl

Just love how concise this code is:

Say you wanted to create a linked list of the first five squares...


$list = [$list, $_*$_] for reverse(1 .. 5);


Of course that would mean making the linked list the king of the data. Sometimes you want to concentrate on the data, and worry about the linked list structure less. In that case, you can simply add a "next" field to each element, and store a reference to the next element.

Here is another way to create the linked list if you wanted to maintain a tail pointer.



$list = undef;
$tail = \$list;

for(1 .. 5) {
$elem = [undef, $_ * $_];
$$tail = $elem;
$tail = \$elem->[0];
}



In this case, we're setting $tail to be a reference to the "thing that needs to change when a new element is appended to the list". The thing that needs to change is of course the "next" reference of the last element. So we always keep $tail pointing to that. The first $$tail is following that reference and storing a reference to the newly created element there. The next $tail is updating the tail to point to the "next" of the element we just added.

Some quotes

Algorithms with Perl has some very fun quotes in the beginning of each chapter:

"What is the sound of Perl? Is it not the sound of a wall that people have stopped banging their heads against?" - Larry Wall

"Computer science is no more about computers than astronomy is about telescopes" - E.W. Dijkstra

"I wonder what happens if I connect this to this?" - the last words of too many people

Perforce and Cygwin

There are multiple posts (saw one with a complex Python script) on how to make perforce windows command line client (p4.exe) behave with cygwin.

The main issue is paths - p4.exe expects paths like "c:\depot\project1code", whereas cygwin would provide it paths like "/cygdrive/c/depot/project1code". So how do you deal with that?

The simplest solution, at least to me, is to write a wrapper script that invokes cygpath -aw to get windows path from cygwin path, and then use it on p4.exe.


p4 edit `cygpath -aw myfile.c`


Of course that becomes tedious in no time. Hence the script.


#!/usr/bin/perl
use warnings;

$path = $ARGV[1];
$adjpath = `cygpath -aw $path`;
$command = "p4 $ARGV[0] $adjpath";
$command =~ s/\\/\\\\/g;
$output = `$command`;
print $output;



The other problem with using P4 and Cygwin is the p4config file. By setting P4CONFIG=.p4config in the environment, and then having a .p4config file at the root of each clientspec home directory, you can get perforce to automatically change clientspec when you change into that directory (no need for an explicit call to p4 set p4client).

Well this doesn't quite work with cygwin.

There is a cygwin client given by Perforce, that works well with this. But that does not work well with P4V/P4Win for Windows, so you need to have separate clients for cygwin and windows. Haven't found a solution to make .p4config work on cygwin with Windows-native p4.exe.

Patterns

"Decoupling objects so that changes to one can affect any number of others without requiring the changed object to know the details of others" - Observer pattern

"Group objects and treat them the group like an individual object. Create a class hierarchy in which some subclasses define primitive objects and other classes define composite objects that assemble the primitives into more complex objects" - Composite pattern

"An object that represents an algorithm is a strategy. When you want to replace the algorithm(s) used for a task, either statically or at runtime, you can encapsulate the algorithm within an object" - Strategy pattern

do { } while(0);

This is often seen in kernel code. Here's a nice explanation from the linux kernel newbies FAQ:

http://kernelnewbies.org/FAQ/DoWhile0

Python's "for-else" and "while-else" loops

Almost every imperative procedural language has a for and while kind of loop. But Python is the only language that has an "else" attached to for or while. And the else does not have what you would think is the intuitive meaning (it doesn't get executed only if the for or while is never executed i.e. the condition is false to begin with). Rather, if the for or while ends normally without a break statement (i.e. it ends because its condition becomes false), the else is executed.

To me with my beginners knowledge of Python, it seems a bit unclean, and out of place for a precise and tightly controlled feature set language like Python. Let's see if I am proven wrong when I know more.

Edit on 4/8:
As expected, I was proven wrong. Turns out there is a very useful common idiom that is addressed by this. We typically code a "did_it_happen_flag" in a for or a while loop (pseudocode)


while(...) {

  if(...) {

    did_it_happen = TRUE;

    break;

  }

}



if(!did_it_happen) {

  printf("It didn't :-(");

  // Do something useful

}








This can be coded in Python like this:


while (...):

  if(...) : break

  ...

else:

  print "It didn't :-("



This way that extra check is not required - if the break were never hit, the else associated with the while takes care of taking the action we need.

What makes a good software developer?

From a professional software engineer point of view:

http://blogs.msdn.com/natbr/archive/2007/07/23/what-makes-a-good-software-developer.aspx

When does a cast change the address

Typically, when you cast an address to a type, you are simply changing how that address is being interpreted - that does not change the address. But in the case of C++, casting can actually change the address.

Say you have this hierarchy:

class C : public A, B
{
};

Then if you do this (not necessarily the recommended way, static_cast is better because it makes your intentions clearer and it is a bit safer):

C c;
A *a = (A *)&c;

Then, if the members of c started at 0xa34c0000 (on a 32-bit machine say), the physical contents of a will be the same i.e. (void *)a == (void *)&c.

But if you do this:

C c;
B *b = (B *)&c;

Then, if c started at 0xa34c0000, b will start at 1 beyond 0xa34c0000 + size of class A members.

That means, that say if A were a pure virtual class with only a vptr as a data member, B would start at 0xa34c0004. Thus the above cast would change the memory address in the result, and rightly so.

Probably something that is trivial for the experienced C++ programmer, but does trip you up when you are accustomed to casts not changing addresses on you - in C land, for example.

*PS: In the virtual base class example above a reinterpret cast would actually put 0xa34c0000 in b as well:
B *b = reinterpret_cast<B*>&c;
But that is disastrous because class B does not start at that address. In general, reinterpret_cast means you are telling the compiler that you know more about the underlying type then the compiler does. If you use a direct C-style cast, C++ first tries to do a static_cast, which is why it ends up doing the right thing - incrementing the address by 4.

Getting from a structure member pointer to the structure pointer

This is typically something that is required in system software - where you have a pointer to a member of a structure, and you want to get to the base address of the structure itself. Generally speaking this should be easy enough - since you know the offset of the member, you simply subtract the sizes of every member that comes before the member whose pointer we have, and we should have a pointer to the base.

Generally speaking, there are more elegant ways of doing this. One way I have seen is this:

Consider a structure like this:

struct mystruct {
member *a;
another_member b;
something *c;
...
};

So, if you have a pointer to c, to get a pointer to mystruct, you could do this:

mystruct *s = (mystruct *)(( (byte *)c - (byte *)((mystruct *)0)->c)

What this is doing is casting the address 0 to the type mystruct. Then, if you are pointing to the "c" member, that gives you the actual relative offset of "c" in the structure. All that remains is to subtract this offset from "c" itself, in order to get a pointer to the containing structure.

Linux kernel does something similar - the macro container_of provides this functionality:

#define offsetof(TYPE, MEMBER)
  ((size_t) &((TYPE *)0)->MEMBER)

/**
* container_of - cast a member of a structure out to the containing structure
* @ptr:        the pointer to the member.
* @type:       the type of the container struct this is embedded in.
* @member:     the name of the member within the struct.
*
*/
#define container_of(ptr, type, member) ({ \
        const typeof( ((type *)0)->member ) *__mptr = (ptr); \
        (type *)( (char *)__mptr - offsetof(type,member) );})

It does the same thing if you ignore all the casting. It first gets a pointer to the member of a 0-based structure, and then subtracts the offset of the member from this address to get the base.

ARM RISC philosophy

It is interesting how ARM does not take the RISC philosophy too far. Yes, it does believe in single simple instructions that execute in one CPU cycle. But it does allow you to have complex instructions. For example, instructions that allow you to operate on multiple memory locations - possibly contiguous. The instruction may be a simple STR and does fit into 32 bits with the op-code + operand, but it may take longer than one CPU cycle to execute. This is ok - because ARM does not take RISC too far.

Also, the load-store architecture is cool. This is to guarantee that processing instructions always operate on registers - never directly on memory. Memory access is slow, it is better to have instructions that access memory work separately. This also allows some pipelining - because it may be possible that you issue a LDR on one instruction, while you are trying to execute a non-data dependent instruction at the same time.

Another point is code density - if ARM took the RISC architecture too seriously, then the code density would take a hit, because each instruction requires 32 bits (at least in the ARM instruction set, ignoring the 16-bit Thumb set), so if you need a lot more instructions to say something, your code becomes that much bloated.