Age of Reason

Random musing of books and stuff I am reading.

2010/10/27

Mastermind Puzzle Generator

Mastermind Puzzles, generated by mmind2.

For details see Wikipedia entry on mastermind game.

For more puzzles and free mastermind source code in C and pascal.


Puzzle: guess the 4 hidden pegs, numbered 1..6
Hints:
B: a correct pin in correct position.
W: a correct pin in wrong position.

problem 1 {
1, -2245-BB---
2, -1652-W----
3, -3131------
4, -1334-W----
5, -4516-WW---
}
problem 2 {
1, -4134-B----
2, -4242-BW---
3, -2434-BB---
4, -5622-BW---
}
problem 3 {
1, -1356-W----
2, -5426-WW---
3, -6561-B----
4, -2442-BW---
5, -5352-WB---
}
problem 4 {
1, -5522-B----
2, -6131-W----
3, -3126-W----
4, -3131------
5, -3643-WW---
6, -2542-WW---
}
problem 5 {
1, -1635-WW---
2, -4242-B----
3, -2241-W----
4, -2542-W----
5, -2466-BW---
}
problem 6 {
1, -6451-WW---
2, -3611-BB---
3, -6124-W----
4, -3365-BB---
}
problem 7 {
1, -6613-WW---
2, -1452-BBW--
3, -3335-BW---
4, -6631-WW---
5, -2352-BBW--
}
problem 8 {
1, -2553-BB---
2, -5352-WW---
3, -2412-BB---
4, -5256-W----
5, -4162-WW---
6, -6631-BWW--
}
problem 9 {
1, -3331------
2, -3334------
3, -2253-WW---
4, -1322-B----
5, -1554-B----
6, -2416-WW---
}
problem 10 {
1, -6122-WW---
2, -1264-WW---
3, -1551-W----
4, -4431-WW---
5, -2464-W----
6, -5621-BW---
7, -2463-BW---
}


Solutions to Mastermind Puzzles above.
(numbers indicate how many choices at each step)

solution 1: -5445------ (105 19 6 4 1 )
solution 2: -2332------ (182 21 6 1 )
solution 3: -4544------ (152 32 7 2 1 )
solution 4: -5464------ (256 38 11 4 2 1 )
solution 5: -4363------ (312 60 14 2 1 )
solution 6: -3515------ (312 19 5 1 )
solution 7: -3152------ (222 10 4 2 1 )
solution 8: -2433------ (105 48 7 3 2 1 )
solution 9: -6562------ (256 81 11 10 2 1 )
solution 10: -3613------ (222 36 5 4 3 2 1 )

2006/05/21

G.B.Shaw's full cast plays on audio tapes

The CBC audio tapes of Shaw plays, performed by a full cast are superb,
avoid the ones read by a single narrator. Get these from Amazon:

Candida

Arms and the man
Pygmalion

Man and Superman

Saint Joan

Doctor's Dilema

Caesar and Cleopatra


The texts of the plays are availabe online here
G.B.Shaw on Gutenberg

2005/07/15

Truth and Proof in Shakespeare

Shakespeare's could have been a mathematician,
here is what his plays contain (all quotes are
taken out of context):

OTHELLO: I'll have some proof.
DUKE OF VENICE To vouch this, is no proof,

Cymbeline:
CAIUS LUCIUS: Let proof speak.
GUIDERIUS : Out of your proof you speak:

Measure for Measure
POMPEY: Proof?

And Pedro spoke both of truth and proof in Much Ado:
DON JOHN: What proof shall I make of that?
LEONATO: we have ten proofs to one
DON PEDRO : But what was true and very full of proof.

This guy ruins a proof by sorting in Taming the Shrew:
PETRUCHIO: is sorted to no proof.

Cressida [T&C], Olivia, Olivia [12th Night] are real Math teachers,
and Nestor seems to be a bit in water:

CRESSIDA Troilus will stand to the proof, if you'll prove it so.
NESTOR: That proof is call'd impossibility.

OLIVIA Make your proof.
OLIVIA Well, sir, for want of other idleness, I'll bide your proof.
VIOLA No, not a grize; for 'tis a vulgar proof,

The Gentlemen of Verona don't seem to like proofs:
SPEED Such another proof will make me cry 'baa.'

Winter's tale has this quote about elegant proofs:
Third Gentleman Most true, if ever truth ..
there is such unity in the proofs.

Henry IV, has proof by handwaving by Falstaff:
PRINCE HENRY Well, we leave that to the proof.
MISTRESS QUICKLY Come, I'll drink no proofs nor no bullets:

Henry 8th and R&J have proof personified
BUCKINGHAM: And proofs as clear
He shall appear in proof.
ROMEO: And I am proof
FLAVIUS: And set me on the proof.

And GLOUCESTER doesn't like the first proof in Richard 3rd
The play has several references re-proofs:
GLOUCESTER: Or bitterly to speak in your reproof.

Hamlet shames Zeno:
HAMLET: this was sometime a paradox,
but now the time gives it proof.

Some Real Analysis from Julius Caesar
BRUTUS But 'tis a common proof,
PORTIA I have made strong proof of my constancy,

KING LEAR I'll put 't in proof;

Sonnet CXVII -- And on just proof surmise accumulate;
Sonnet CXXIX -- A bliss in proof, and proved, a very woe;


---
Q. Why were the mathematicians covered with cake at the end of their tea party?
A. Because the secretary brought some cake, and no one wanted it, so he divided
it by zero and ended up with an infinity amount of cake.

2005/07/13

Mgrep Find-Grep-Filter-Edit in QT

Here is a QT program mgrep with source to
find-grep-filter-edit for files on your disk.

Why is it better than 'gnu find and gnu grep'?
It keeps history of all options and grep/find out text across sessions.
The earlier version used external process to launch gnu grep and gnu find,
then I decided to use QRegExp and simplify the source.
Feel free to improve on it, I will move it to source forge later.

Here is the source mgrep.cpp mgrep.h and download the whole mgrep.zipt
The zip file contains the vc6 project (dsp,dsw,cpp,h,exe) for windows.
Linux users can use the GPL version of the QT to compile it.

To compile on windows, you will need QT library, which
comes with Blanchette's QT book. You can get this book with QT CD
from Nerdbooks.com. If just want to run the mgrep.exe on windows,
you will need QT-MTNC321.DLL for windows, download it from here.
The CD on the book comes with Borland C++ bcc 5.5; or
you can use VC++6 with sp6.

> tail mgrep.txt

PROS and CONS to Mgrep

Mgrep has session history, small customisable QT C++ GPL source,
ability to filter and refine searches, quicker preview than launching vi,
but not as many options as gnu grep and gnu find.

Alternatives

GNU emacs has grep-find, delete-matching-lines,dired
GVIM has :grep, filter :v/keep/d :g/filter/d,preview, gf (edit file).
GNU BASH : find dir -prune skip | grep keep | grep -v ignore | xargs grep text | gvim -
CYGWIN for windows comes with all the gnu tools and X server!
OPERA look for your files on google.com, it works.

2005/07/05

Satyajit Ray

Satyajit Ray is the master builder of Indian movies,
and his movies in Bengali are highly recommended:

Uppal Dutt in "The Stranger" and "Two Daughters".
The Stranger examines modern middle class values
prevalent in Calcutta. While two daughters is about
rural Bengal of 1960s.

The Apu Triology: Pather Panchali, Apu Sansar, Aparajito.
We studied Pather Panchali for ICSE, and also saw
this triology at British Council Library as part of school work
at Cathedral and John Connon School. This series traces
the life of Apu from childhood in a rural village in Bengal with his
sister Durga, to his student life in Calcatta.

I have lived in Calcutta and it is culturally vibrant city
unlike any other in India, and Bengali is easy to understand.

You can get all the Satyajit Ray movies on DVD or VCD
with English Subtitles at a good price from BdBazar.com

The other recommened movies is by Arthur Miller and Henrik Ibsen,
from Broadway Theatre Archive: An Enemy of the People from 1966.

The other profound movie is "Rosencrantz and Guildenstern Are Dead",
a Absurd Drama by Tom Stoppard. A roller coaster tempo of wit.
Here is a summary.
It has a few allusions to science thrown in --
Galileo's feather and ball, Archimedes
water displacement, Newton's apple and probability
theory. The existential wordplay is amazing,
you may want to read the text separately.

2005/06/14

Interview with Sadhu Shiva Shankar




"If I could talk you would not understand me."
"I am known only through becoming me".
"If you have nothing to say, don't say it."

- Sant Jogeshwar

2005/06/12

Advanced Debugging -- Prologue and Epilog

Compile the code with 'cl /ZI main.cpp'
or by pressing F5.
Press F10 to begin debugging.
Press F9 to on fx() to set breakpoint.
Press F5 to run till the breakpoint.
Press A-8 to switch to Assembly mode.

You are now in the prologue of the function:


int fx(int a, int b,int c){
-> push ebp // save the base pointer
mov ebp,esp // point ebp to stack frame.
sub esp,44h // make space for new frame.
push ebx // save original registers on stack.
push esi
push edi

The frames form a linked list on the stack, with ebp pointing to
the previous frame above it. Local variables are created on the
stack, usually with a stack guard and a signature fence to detect
stack overruns (have you ever called sprintf on a locally declared string
or declared a local array inside a function?).
VC++ is very good at finding stack thrashing in debug mode.

Press F10 to single step through the frame setup (prologue)
till the end of the function (epilog), where the registers are
restored:


pop edi
pop esi
pop ebx
add esp,44h // destroy the frame.
pop ebp // restore the frame pointer.
ret

In C (cdecl) functions, the caller cleans up the stack. That is, the caller
will pop out the parameters after the call.
This allows varargs (printf( fmt, i,...)), the callee
doesn't have to know how many parameters are
on the stack.

The default return type of a C function is int,
because the return value comes for free in register eax.
In VC, you can watch '@eax' to see the implicit
return values.

Earlier languages like Pascal and lisp from 1970s
with heavy emphasis on tail recursion optimization
let the callee clean the stack, so the stack would not
grow (but was reused) in recursive calls.

To be continued.

2005/06/11

Advanced Windows Debugging -- 1

This is a short tutorial for debugging C/C++ code on
Windows with VC++ (and windbg,ntsd,cdb) on x86.

You can download the free debugger windbg from msdn.
It is more powerful than VC++ in terms of scripting,
but less convinient GUI.

We will not cover gdb(linux), dbx(solaris), wdb(hp),
in this article, they also offer equivalent functionality.
If you use .Net or C# or Java or VB, this tutorial is not
for you.

The source was converted to html for the blog, by vim :TOHtml

> cat main.c


#include <stdio.h>
extern int errno;
int fx(int a, int b,int c){
int d;
d = a + b; // stop on 5th call.
printf("a=%d,b=%d,c=%d,d=%d\n",a,b,c,d);
return d+c;
}
void bad_open(void){
FILE *f,*g;
f=fopen("/","r");
g=fopen("/dev/null","w");
printf("f=%p g=%p, errno=%d\n",f,g,errno);
}
int main(){
int a=1,b=2,c=3,i,e;
for(i=0;i<1000;i++){
if( i*i % 100 == 1 ) e = fx(a,b,c), e++, printf("fx=%d\n",e);
else a++, b++, c++;
}
bad_open();
}


When you have a cryptic error message, you can look at the
preprocessor output with:

> cl /E main.c | vim -

Now let's examine the assembly listing main.cod generated with:

> cl.exe /Fc main.c

Now is a good time to brush up your x86 assembly,
a good reference is "Art of Assembly" by Randall Hyde at UC Riverside.

> vim main.cod

Start with compiling your C program with Debugging
information on. In the next posting we will dissect and
debug it.


> cl.exe /ZI main.c


The /ZI switch creates main.pdb (program database).

To be continued.

2005/05/29

Oxymorons

"Pascal was a Mathematician long before he became a
programming language" -- Skiena and Revilla in the
book Programming Challenges.

Humour is defined as a correction in a line of reasoning,
a twist of words, a pun, a double entendre. A person without
humour is a dull indeed, and medically speaking without life
(no pun intended). Laughter denotes a flexible mind.

Analyse following sentences:
  • Haven't I told you a million times not to exaggerate! -- Hally.
  • "No truth is ever a lie" - Barbara Streisand.
  • It is true that X is true -- Heard in IITB.
  • He caught a cold and a bus -- Wren and Martin.

A professor once wrote a theorem on the board
and said, "The proof is trivial for large N, say 3",
he then stared at the board for half an hour
and finally said "I was right, it is trivial".
So the student asked, "Is the proof trivial or not?"
The professor replied "Yes".

It has to be a Math or CS professor,
probably a knot theorist. Which other
discipline has a concept of a proof?
EE doesn't even have the concept of correctness.

Logic of Knowledge and Time

Monk 1: "How happy are the butterflies in the meadow!"
Monk 2: "You don't know the butterflies are happy,
you think they are happy."
Monk 1: "How can you know what I don't know?"
Monk 2: "I believe in the principle of common knowlege."
A this point Monk 1 hits Monk 2 with his staff.

A host of questions come to mind:
  1. Is belief different from knowledge?
  2. Do you believe in what you know?
  3. Do you know what you believe in?

Let us write B(X) if you believe in X,
and K(X) if you know X,
now are the following true:
  1. X -> B(X)
  2. B(X) -> X
  3. K(X) -> B(X)
  4. B(X) -> BB(X)
Is this possible:
  1. B(X) & B(~(B(X))

Note that I haven't defined what is true and what is possible.
Which brings us to the epistemology and logic of beliefs.

Get some of Raymond Smullyan's popular books:
These cheap paperbacks are very good introduction to logics, and you
can get them from Amazon or bookfinder.com

After reading Smullyan, you will believe you believe in logic of beliefs.
Smullyan opens can after can of worms, raising more questions:
  • What is truth?
  • What is a proof?
To evaluate statements in a language you need a
world model in which the statement will be true or false.

The first person to define the concept of
truth on a firm ground was Alfred Tarski in 1940s.
You can look up Alfred Tarski's monograph "Truth and Proof".

Enderton's "Mathematical Logic" is an
Undergraduate introduction to logic.

Barwise's "Handbook of Mathematical Logic"
is a Graduate level survey.


Modal Logics

You can model beliefs, knowledge, time and proofs in modal logic.

Modal qualifies logical statements with modalities and quantifiers:
"Sometimes it rains". Here Sometimes is a modality on the statement.
"Whenever it rains, the ground is wet" Here whenever is the
universal quantifier over time.

Boolos (The Logic of Provability),
Chellas, and Hughes and Cresswell are
some of the good books on Modal logics.

I still haven't covered Byzantine general's problem
of common knowledge and free will,
and what is "free will"? I am not talking Kant or Russell.

Real life quotes you don't want to hear:

Support engineer: "Our tool works great,
except for the
crazy customers who keep crashing it."

Hiring manager asking about an employee referral: "If he
is really good, why does he want to work here?"

Problem: "tool xyz consistently crashes on my computer."
Suggestions "Reboot windows, if that doesn't work
reinstall windows."

2005/05/20



Making (sesame) til chikki,
the ancient art from India. Posted by Hello

2005/05/17

Mulliner Nights

Recommended Video

P.G.Wodehouse's Mulliner series is hilarious.
Pauline Collins and John Alderton are just great actors.

Mulliner reminds me of David D'lima, former
Championite, Cathedralite and IITian.

Recommended books, see their reviews on Amazon.

The Algorithm Design Manual by Steven Skiena is an excellent
book. It complements Cormen/CLR book nicely.

Origin of Species by Charles Darwin,
Abridged and Introduced by Richard E. Leakey, 1979.

The Same and not the same
, by Roald Hoffmann.

Molecules, by Atkins (no, this Author is not the diet nutcase).

The Stuff of Life, Eric P. Widmaier.

Connections by Burke.

Geometry, Geometry Revisted and Essays by Coxeter.

Recommended new software:

Kdiff3 and the new windmerge are nice diff and merge programs.
Of course, I have stuck to Gnu Emacs' Ediff/Emerge/gnu diff, because they
has been there forever.

If you need to run xfig on ms windows, just install cygwin right
off the internet. Cygwin's comes with an X server,
bash, gcc, grep, perl and everything else for windows.

With Cygwin, you can say goodbye to the buggy, out of sync ports
of perl, grep, and all other unix tools on windows.

2005/05/08

Purity of the Turf.

Reading QT 3.3 book by Jasmin Blanchette and Mark Summerfield.
Managed to write two 2D board games using QCanvas.

The CD with the book has the free Borland 5.5
C++ compiler, very compact, fast and useful.
I didn't try the evaluation version of BCC 6.0.

The html documentation is excellent, plus the unique name qt
helped in searching relevant docs on Google. Only
QSound gets ranked 6th in the search. Most of my questions
were already asked and answered on their mailing lists.

Interestingly all google ads are about cookery when
searching for QPtrQueue, even when there are no
matches for the misspelled word QPtrQueu.

I am using tortoise CVS frontend,
highly recommended for windows users, even
if you are a season command line CVS users.
Makes it a breeze to put files under CVS control.

The other book I am reading is
"Design and Validation of Computer Protocols"
by Gerald Holzmann, a well written book
about networking and protocol verification.
The price is steep at $80. It could have been
course textbook for theory of networking.
Tanenbaum's networking classic
seems like a databook in comparison.
Of course this book too contains a large
appendix of C source printout, must be
the effect of the times (1992).

There is always the rerun of P.G.Wodehouse's
"Jeeves and Wooster" series with
Stephen Fry and Hugh Laurie. Just
finished "Purity of the Turf". The noted
newt fancier Gussie Finknottle, Spod,
Boko Fiddleworth and Barmy Fungy Fipps
are some of the characters you will meet.
Definitely worth the money.

The 1953 Julius Caesar in B&W
with Marlon Brando and John Gielgud
is also rerunning.

2005/03/10



Cooking Gur (jaggery, raw cane sugar) to make chikki, cook at 300F to remove water, before adding dry roasted Til (sesame), Peanuts, grated coconuts.

2005/03/09

Prize for largest error message goes to STL


// WHAT: 290000 char long error message from 8 line program with one error.
// HOW: cl /GX biggest_error.cpp 241 char src gives 291201 char long error message,
// AUTHOR: GPL(C)2005Mosh

#include <map>
#include <string>
#include <algorithm>
using namespace std;
void main( int argc, char *argv[] ){
map< map<string,string>, map<string,string> > hoh; // 10K long warning message
sort( hoh.begin(), hoh.end() ); // error line .. 280K long error message
}


Borland C++ 5.5 did a little better with 62K error message.

2005/01/26

Halftone Dithering for Printing

Instructions for printing B&W photo
on ordinary 8x11 paper on a low resolution
ink jet printer with minimum black ink usage.

The trick to get perfect b&w 8x11 inch prints
in less than 10-seconds is to resize, sharpen,
lighten and dither in the correct order.

Here are the steps:

1. Image -> mode -> grayscale.

2. Filter -> sharpen -> unsharp mask
Adjust for contrast here and clear edges.

3. Image -> adjust -> curves
Pull the graph downwards to make the picture
much lighter, as it comes out better on printer.

Experiment by printing a lighter picture
and you will see that the printed picture will
come better than it looks on screen.

4. Image -> Crop
Image size: 11x8 inches (max of height or width).

5. Image -> mode -> bitmap -> halftone screen 600dpi
halftone settings: Freq 60 dot/inch, 45 degrees, round.

6. Optionally save as image.psd (bitmap).
File -> print -> printer setup, Portrait or
Use landscape if width greater than width.


2005/01/22

The Noble Kinsmen

Just finished the play "The Noble Kinsmen"
by Shakespeare and John Fletcher. The 1400s
version of this story by Chaucer was known
as The Knight's Tale in Canterbury Tales.

In this play the two knights and cousins
Palamon and Arcite vie for the love of
fair Emilia from a jail.
The unreality is balanced by the unbalanced
their gaoler's daughter. The greek gods
Mars and Venus symbolize the two knights
and their qualities, prayers and hopes.

The Knighthood bit and Greek setting
is overdone in this quick paced play.

The Knights are shown to be totally self centered
and selfish. They would rather kill their cousin
and noble friend for a lady they never spoken to.
Their caste system will not allow Palamon to fall
in love with a commoner, the jailer's daughter.

In a Hindi movie version of this play,
replete with the motifs of nobility, sacrifice
and equality, Palamon would be the winner of
the jousting and end up marrying the jailer's
daughter and Arcite would marry pricess Emilia.

The play gives you an idea what history was like
400 years back. Knights in ancient Greece?

This one is not difficult nor boring
unlike Shakespeare's history plays.

I should know, since I read Henry V last
week and Henry was the leading bore. Somehow
Henry 5th comes out as a plastic character.
And Kate, Princess Katherine of France comes
out as a dummy. Maybe that was the intention
of the Bard to show the superiority of the
British Army and Language over the French.

2005/01/21

Forgotten promise of the PC

Essential features missing on the PCs:

1. Switch to write-protect the hard disks.

2. Readonly system directory or system on CD.
Go Knoppix.

3. Not crashing or hanging windows on a bad/scratched CD.
No excuse for this one.

4. Trusted portable USB keyboards.
If you can't login securely, what can you do?

5. Switch to power cycle hung laptops.
My Toshiba laptop came with an XP, it used to hang
atleast once a day.

6. User control to underclock CPU, NIC, IDE
No reason for PC to be computing when I don't want it to.

7. Focus-lock for 400ms when fingers are near keyboard.
Don't you hate the pop-up "Press Cancel", suddenly appear
and vanish while you are typing something else in another window?

8. Light touch mouse-buttons and keyboard.
There is no reason the mouse button is so hard to press.
The mouse is really a bad idea, touch screen is the right solution.

9. Instant On/Off, RAM disk for windows.
Linux should fit into 16Mb CF BIOS (maybe also Win95).

10. Read-only and Write-Only switches on USB drives.
Write-only switch is needed when plugging the drive into public machines.

11. All power adaptors (5v..12V) clutter inside the PC.


2005/01/10

Enquire within for LP64

The program enquire.c will tell you a lot about your machine.
Here is how to compile it on HP/UX
> cc +DA2.0W +w1 +M2 enquire.c     


Use the flags +w1 for warnings, +M2 for 64bits

These are the kind of problems you should look out for:


/714: Function "malloc" called with no prototype or definition inscope
/724: Initialization converts default int return type to pointer
/722:.*cast converts 32 bit constant to pointer
/725:.*cast converts 32 bit integer to pointer
/727:.*cast truncates pointer into 32 bit integer
/729:.*converts int* to long*
/732:.*different types treated as unsigned
/740:.*casting to a smaller size may truncate
/530:.*casting from loose to strict alignment
/720:.*Assignment may overflow
A simple example that has many of the problems
> pr -n x.c

1 void main(){
2 int *x, *q, i;
3 long l=-1;
4 x = malloc(sizeof(int)*10);
5 (int*)i;
6 (int) &i;
7 (long*)&i;
8 i = l;
9 }

hp64> cc +DA2.0W +M2 +w1 -Aa x.c

line 4: warning 714: Function "malloc" called with no prototype or definition in scope.
line 4: warning 724: LP64 migration: Assignment converts default int return type to pointer "x".
line 5: warning 725: LP64 migration: Cast converts 32 bit integer to pointer.
line 6: warning 727: LP64 migration: Cast truncates pointer into 32 bit integer.
line 7: warning 530: LP64 migration: Casting from loose to strict alignment: Resulting pointer may be misaligned.
line 7: warning 729: LP64 migration: Cast converts int* to long*.
line 8: warning 720: LP64 migration: Assignment may overflow integer "i".


Sorting LP64 warnings by problem types for ease in fixing

> make 2>&1 | grep LP64 | xsort 'warning:\s+\S+:' | align warn > lp64.log
> vim -q lp64.log
> emacs lp64.log
> M-x compilation-minor-mode
> M-x next-error
; if emacs can't find files, set
; (setq compilation-search-path '("dir1" "dir2")) C-x C-e
To be continued.

2005/01/08

Shakespeare on Screen

Just finished reading "Richard II" in Folger paperback.
Nice piece of lyrical work.
This is the story of the downfall of a foolish English King,
he is confused by his belief that God has made him the King
and he can do no wrong.

It whetted my appetite for more, so I am starting on
King Henry V, Oxford large print, edited by Roma Gill.
Earlier I tried watching Kenneth Branagh as Henry V on DVD,
it was a colourful melodrama with incoherent dialogues.
Proving that media is not the message.
However Kenneth's other movie "Much Ado about Nothing" was
very well done and worth watching.

If you are a language fan (rather than a movie buff)
these are also worth watching:
Mel Gibson as Hamlet,
Brando in Julius Caesar,
Zeffirelli's Romeo and Juliet
Midsummer night's dream 1999,
As you like it
from 1937.
Taylor and Burton in Taming the Shrew, 1967.

I remember seeing Twelfth Night and Merchant of Venice,
and a few more, but recall nothing notable to recommend.

2005/01/04

Double Quoted Shells.

Ever had trouble putting quotes inside bash aliases?
Then read on, for Bash and sh allow extra ordinary
levels of quotations. The examples below would be
unthinkable in csh and other simplistic shells.

Of course DOS users would rather drag and drop
filenames with spaces in them.



To avoid the disease quototitis we will use the
abbreviations dq (") and sq('). Note that dq
inside sq strings are ignored.

1. To expand a shell variable inside a 'string':
1.1 End the sq string.
1.2 Put the variable in dq (to prevent extra spaces),
1.3 Start sq string again.

> perl -e 'print("...'"$HOME"'...\n");'
...c:/mosh...

2. To insert sq inside a sq-string:
2.1 close sq string.
2.2 put standalone backslashed sq
2.3 start sq string again.

> perl -e 'print "I just can'\''t do that!\n";'
I just can't do that!

> echo 'aaa'"'"'bbb'
aaa'bbb

3. To use single quotes inside an alias,
3.1 close quote,
3.2 dq sq dq
3.3 open quote

> alias nut='net use |perl -lne '"'"'print("$1=$2") if s,\\,/,g && m@\s([A-Z]):\s+(//\S+)@'"'"
^^^^^ (close sq, open dq, insert sq, close dq, open sq again).

> alias vq='vim +'"'"' ":call Mosh_Quick_Fix()" '"'"' '
^^^^^ (close sq, open dq, insert sq, close dq, open sq again).
> alias vq
vq="vim +'\" :call Mosh_Quick_Fix()\" ' "

4. Use dq to preserve spaces:
> x='A
B'
> echo $x # single line, newlines in $x are converted to spaces.
A B
> echo "$x" # newlines \n are preserved.
A
B

5. Passing dq to emacs from a function:
ediff(){ ${EMACS:=emacs} --eval "(ediff-files \"$1\" \"$2\")" }

6. Passing arguments to perl
> echo PWDLEN=$(perl -e 'print length(shift);' $PWD)
> echo PWDLEN=$(perl -e 'print length($ARGV[0]);' $PWD)



Well you knew that? If not, get a copy of "Kernighan and Pike".
However Regexp are better done with expr and perl. ATT made
the perfect shell, but the implementation of regexp eluded them
until Henry spencer wrote the free bugfree regexp library.
Finally Larry Wall perfected the Camel (no relation of Caml).

Traditionally you can do plain literal subst OLD by NEW in VAR.

>VAR=${VAR/OLD/NEW}

You will have to come out of your shell to play with regexps:

subst(){
eval "VAL=\$$1"
VAL2=$(perl -e '($f,$a,$b)=(shift,shift,shift);$f=~s/$a/$b/gi;print $f' $VAL $2 $3)
eval "$1=\"$VAL2\""
}
>subst PATH '/usr/\w+/bin' '/usr/bin' # changes PATH =~ s,/usr/\w+/bin,/usr/bin,ig


Regexp can be eagerly quantified. see 'man perlre' for details.

2004/12/30

Suffix trees and Shattered Perls

I had to Postpone the reading of Richard II
due to the technical problems. Instead I took
libstree for BSD and compiled it on Windows.
Since I boot into BSD only occasionally.

Pulled in bsd net/queue.h into win32/sys/queue.h,
a few typedefs into dummy win32/unistd.h,
dropped the buffer overflow check from snprintf to sprintf,
and voila everything compiled without warnings.
VC did catch one sizeof(void*) problem.

Shattered Perls

Windows has a dozen ports of perl, and all of them are broken,
one of them died on this:
c:\libstree-0.4.0\src> perl -ne 'print if m/\r/' *.c
It seems this windows port of perl converts all backslashes
in the arguments to forward slashes "@ARGV =~ s,\\,/,g"
assuming all arguments are dos paths.

2004/12/29

Tsunami in Chennai

Another harmonic of the Tsunami in Chennai.

Tsunami

After the first Tsunami (tidal wave) in Madras.

2004/12/24

Christmas Reading

Bought DK's "Essential Shakespeare Guide" on a Borders gift card.
The book has excellent pictures, but not much information on language.
Probably popular book with party goers and trivia droppers, kind of people
who talk about Shakespeare rather than read his plays.

That is the problem with gift cards -
you have to carry it around, you feel obliged to cash it,
it was useless at a Barnes and Noble with a larger book selection.

Also Plodding thru Gusfield's explanation of Ukkonen's algorithm to
build suffix trees in linear time.

Also reading "World of Nagaraj" by R.K.Narayan. Nagaraj is building up
suspense by doing nothing, the reader is waiting for something to happen,
why is the tao silent? R.K. is a master writer.


2004/12/22

Rabin Karp Fingerprinting

Dan Gusfield presents Rabin & Karp's fingerprinting algorithm for
string matching in expected linear time.

Fingerprinting and Signatures are sparse hashing,
while parity check is dense hashing.

The idea is this.
If the parity of pattern and text differ,
there can be no match.
Otherwise the probability of a false
match is given by the compression ratio
of the parity, 1/2 in this case.

match(pattern,text)
for(i=1 to |text|)
if( hash(pattern[1..n]) == hash(text[i..i+n]) ){
pattern =~ text[i] with
probability of false match being #patterns / #hash
else
no match at i.

Other idea is to compute the sliding hash incrementally inside the loop:

hash(text[i..i+n]) = hash(text[i-1..i+n-1]) + incremental effort.

Rabin and Karp use numbers mod p as the hashing function,
where p is a random prime < maxint on the computer.
Computation mod p is fast and there is
no need to carry around bignums.

The probability of error falls quickly
by hashing w.r.t. multiple random primes.

2004/12/17

Parsing in 21st century -- "possible unbalanced brace in comment" -- tcl error message.

A real life Tcl error message goes:
"Possible unbalanced brace in comment".
It got me wondering "is nothing sacred?"
Why cannot I comment out a piece of tcl code
without eliciting rude comments from my interpreter?

It reminded me of command dot com, where
the implementation is the spec and the spec is
a collection of examples on the web.

Don't you love software that is just a collection of
special cases, and as the product grows, you just have
to add more cases. Finally you get the big bank theory
of software management.

One exception in the family is the language "Expect" by Don Libes.
Expect is a beautiful extension based on tcl, but that is just
the genius of Libes. Libe's books "Exploring Expect" and "Obfuscated C
and other mysteries
" are exceptionally good.
See my review of the latter book on Amazon.
It is pity the book is out of print.

2004/12/16

Cycle stealers fight back the keyjackers

The latest process explorer from sys internals is awesome,
it is free, and shows everything about the system (win9x/2k/xp).

The CPU graph shows process hog history,
process paths/tcpip ports/file handle/strings,
right click and find about that process on google!
It did find a keyboard logger -- user32.exe on my win2k.

I can see that the antivirus CPU usage jumps in lock step
with my own program CPU usage. Who says anti-virus programs
don't steal cycles?


2004/12/14

Books I am reading - King John ..

I never seem to get down to write about books I am reading.

King John by Shakespeare. I was following the Cambridge Shakespeare by John Dover Wilson. Yesterday I switched to the Folgers edition, since I like the notes on the side and the smaller size.

The play is never mentioned in recent times,
because it religiously deals with power and
politics, and maybe too close to reality.
The Protagonist Bastid saves the
day for England while John wavers.
It has other strange characters like
the Prophet of Pomfret and Lord Bigot.

See http://www.online-literature.com/shakespeare/kingjohn
and http://ise.uvic.ca/Library/SLT/history/kingjohn.html

Also reading Dan Gusfield's classic. Aho Corasick's algorithm is cute, and now I can see why agrep is blindingly fast. Bit-Shift-Anding is kind of multiplication, and that leads to FFTing the bits in m.log(m) time, interesting. So far, so good. Gusfield is great writer, his book could be taught to Btechs, though the price is steep at ~$50.

The third book I am reading is R.K.Narayan's "World of Nagaraj", not much happening, but that is the way I like my novels to be. I finished "Waiting for Mahatama" last month, very touching. The book gives a personal view of South India in 1940s thru the eyes of Sriram, that no history book can match.

I am once again reading Hardi's book, stiring a healthy mix verilog and vhdl for the hardware debugger's compiler.

Agrep got me thinking, that vim needs a dynamic spell check against a dictionary or words in current buffer. String searching can be very fast, especially the bit-shift-and algorithms of agrep. The other option is dynamically lookup esoteric words in google as I type. For example, what is the Latin name of pipal tree in Mumbai.

I try to cross check proper names when I am photo blogging.

Usually I search in a tabbed window of Opera in text mode. Today I tried wget google and got back over-htmlized unreadable text. That's when I found google apis - not fast enough to complete as I type, but certainly plug-able into emacs and gvim to do lazy-lookups in a secondary buffer, while I type ahead. The CPU and network capacity and already there.

- M.

2004/12/11

File Descriptors in Bourne shell (sh,ksh,bash).

In the 1980s Steve Bourne in 11 pages specified the grammar for
a functionally complete shell (see original ATT Unix manual).
It is a tribute to his foresight, that those 11 pages still
suffice to write arbitarily complex shell scripts in 2004.

Marc Rochkind's Advanced Unix Programming book fills in the
elegant plumbing details, and how pipes in sh work.

Compare that to csh and msdos shell, where quoting/aliasing/redirection are
broken, and work only for special common cases. For details read
Tom Christiansen's csh write up
http://www.faqs.org/faqs/unix-faq/shell/csh-whynot

That is the difference between Computer Science (rather mathematical training) grammar and bad engineering hacks. What is a good grammar? It is being able to write arbitarily complex scripts, without having to wonder if it will work.

The elegance of sh has been continued in Perl, while the tradition of csh
has been carried into tcl (in tcl, the parser cannot deal with unbalanced
braces inside comments, and all data is a null terminated string).

If you find sh redirection in configure files spinning your head, read on:



Notation:
FD is file descriptor [0-9-].
&FD is reference to a file descriptor.
WORD is an unglobbed filename.

&- NULL # closed FD.
E<&- FD[E] := NULL # close fd E (default is stdin /0). E>&- FD[E] := NULL # close fd E (default is stdout/1).
<&- FD[0] := NULL # Close stdin >&- FD[1] := NULL # close stdout

FD[-] NULL # closed fd).
FD[0] stdin # default for input
FD[2] stderr

E<>F FD[E] := open(F,rw) # Redirect E to file F in read-write mode
E>&D FD[E] := FD[D] # fd D is duped and result is fd E (default is stdout).
>&D FD[1] := FD[D]
E> F FD[E] := open(F,w) # Redirect fd E to file F (default is stdout).
> F FD[1] := open(F,w) # Redirect stdout to file F.
E>>F FD[E] := open(F,a) # fd E is appeneded to F.

E<&D FD[E] := FD[D] fd D is duped and result is fd E (default is stdin). E<&- FD[E] := NULL, fd E closed. E<<<\STR \n(HERE DOCUMENT $XYZ not expanded\n)*STR E<< -STR \n(\t*HERE DOCUMENT\n)*STR .. Leading \t will be stripped from each line. Notes: > is really 1>
<>/dev/null Leaves STDOUT open
2>/dev/null Discard STDERR
2>&1 Send STDERR to STDOUT instead
2>&- Close STDERR (not recommended)
3<>/dev/tty Open fd 3 to /dev/tty in read-write mode

Only param and command subst,
Not filename or blank interpretations (no globbing).
Eg. $ >b cat a .. copies a to b.
Eg. $ echo x > *.c .. creates '*.c'

Shell ReDirection Examples: moshtag=redirection

Think of each FD as a variable pointing to a fileio_data_buffer.

N>&M FD[N] := FD[M].
N> M FD[N] := open(M,w);
2>&1 Means FD[2] := FD[1].
Now FD[2] stream is lost,
and anything written to FD[2] is sent to FD[1],
since FD[2] is pointing to the FD[1] fileio_data_buffer.

Think of redirection as connecting pipes?
2>&1 Means dup the RHS pipe and connect the LHS source to it.

Eg. $ gcc x.c 2>&1 | grep errors
Eg. $ 2>&1 gcc x.c | grep errors

Order of redirection is always left to right.
Eg. $ gcc x.c > log 2>&1
FD[1] := open(log,w) # 1. First send stdout 1> to ./log
FD[2] := FD[1]; # 2. Then send stderr 2> to &1 (ie. ./log)
# Both FD[1] = FD[2] =

Eg. $ gcc x.c 2>&1 > log
FD[2] := FD[1]; # FD[2] = FD[1] =
FD[1] := open(log,w); # FD[1] =

Eg. $ exec 5>./config.log ; echo "into config.log" 1>&5
FD[5] := open(config.log,w); # Connect pipe 5 to config.log,
FD[1] := FD[5]; # then send pipe 1 data into pipe 5.

Eg. $ cmd 3>&1 1>&2 2>&3 3>&- # Swap stdout and stderr for cmd
# fd3 = fd1 = stdout
# fd1 = fd2 = stderr
# fd2 = fd3 = stdout
# fd3 = null
1. First save stdout as &3 (&1 is duped into 3).
2. Next send stdout to stderr (&2 is duped into 1).
3. Send stderr to &3 (stdout) (&3 is duped into 2).
4. close &3 (&- is duped into 3)

Eg. stderr_output=`cmd 3>&1 1>&2 2>&3 3>&-` moshtag=stderr_output

$ 2>b ls xxx # redirect stderr,
$ cat b
ls: "xxx" not found

# close stdout .. FD[1] :=
$ exec >&-
$ cat b
cat: write error on standard output.

# close stdin .. FD[0] :=
$ exec <&- ... shell exits
Easiest way to learn is to try these in bash.
The firefox is mangling the ampersands in the posting (so watch out).

mosh

Debugger Command Cross Reference

Feature Desc vc dbx gdb windbg ntsd edebug perld i386kd wdeb386
Lang - c c c c c elisp perl c c
OS - win unix unix win win all all win win
GUI - Y N N Y N emacs N N N
Alt GUI - N emacs ddd emacs N N N ddd N N
Vendor GUI - Y Sun/workshop HP/wdbg Y N emacs N N N
Cmdline - N Y Y Y Y - Y Y Y
Alias - N alias/define command N ini Y = N N
Completion N Y YY N N YY - N N
script script VbPerlOle ksh Y dll dll Y Y $< file dll
Actions When .. do when a<>{}
history cmd history N Y Y Y Y Y ! Y Y
init setup regedit .dbxrc .gdbinit regedit ini .emacs - ENV -
Options config regedit dbxenv set O
help ? msdn help i info ? .hlp ? info h pod ? msdn ? msnd
Feature Desc vc dbx gdb windbg ntsd edebug perld i386kd wdeb386
bp break F9 stop at b bp bp - - bp bp
ba hardware A-F9 stop access hbreak/b *addr br ba - N ba br
bl handlers list stops A-F9 status i b - - l L bl -
bd delete F9 delete N delete break N - - u d D - -
bc clear del current C-F9 clear clear - - - - bc -
bp once break once F9 F5 F9 stop -temp tbreak - - - c .. - -
be on enable C-F9 - enable - - - - be -
bd off disable C-F9 -disable disable - - - - bd -
bp if conditional C-F9 cond -if condition J - - - J -
bp --k==0 count to bp C-F9 #NAME? ignore .. k J - - - J -
bp do act action on b N when..{..} command ... J - - - J -
Unassemble disassemble C-F11/A-8 dis $pc disassem addr u - - - U -
bt backtrace A-7 where bt kd kb kd - - T ~k ln -
frame A-7 frame up/down - - - - - -
Locals vars - A-4 dump - - - - V - -
Feature Desc vc dbx gdb windbg ntsd edebug perld i386kd wdeb386
regs registers A-5 regs -F info regs - #R - - - -
expr eval expr F8 print print ?expr - e/R x m p ?expr -
change var F8 p x=y p x=y - - - = E F -
trace single step VC trace trace - - - t tr -
Examine Mem - A-6 x addr/fmt x/fmt addr dw db dc - - - D -
Threads - A-6 - - - ~*KB - - ~ -
Symbols - - - i - X C-h - X -
Watch - A-3 display - - - - w - -
typeof whatis -t ptype - - - - - -
exe - Menu debug a.out file a.out - - - - ini win.com
args - Menu runargs set args Menu cmd - cmd Kernel Kernel
src - vc pdb dir ~/src pathmap ~/src - - - - - -
edit - builtin list list - - - - - -
go - S-F5 run [args] run G - - - G -
Feature Desc vc dbx gdb windbg ntsd edebug perld i386kd wdeb386
step into - F11 step step T - d s T -
stepi instruction - stepi stepi - - - - J -
step over - F10 next next P - - n P -
step if - - - - - - - - J -
finish till return F12 step up finish - - r r - -
continue - F5 cont continue - - c c - -
until till cursor F6 - - - - bc - - -
jump - F2 cont at jump - - - - - -
pop return now \jump pop return - - - r - -
repeat redo - !! - - - - -
quit - MENU quit q q q q C-] - q q
Feature Desc vc dbx gdb windbg ntsd edebug perld i386kd wdeb386


Corrections welcome, it is out of date, but nevertheless useful when switching platforms. Debugger command cross reference, GPL(C) Mohsin Ahmed.

- M