India's China war

Its 1914 and the British are making a royal mess, that has continued to trouble several generations in India, Tibet and China !

Henry McMahon had just drawn a line stretching from near Bhutan to the forests near Burma and was supposed to mark the border between India and China. This McMahon line was to be ratified in a tripartite agreement between British India, China and the ruling classes of Tibet. The underhandedness of the British was in that China, which never agreed to the demarcataion at that time was left out, the agreement was reached with just Tibetan rulers and thereafter propagated as the border. Tibet was a signatory but never followed the line in practice as it involved a partition on the Tawang tract - a wedge shaped land that was a passage from Assam to Tibet and never really considered part of India but very much a part of Tibet. The British wanted a buffer zone between the India and China and therefore chose to put large parts of Tawang tract inside the Indian borders. For similar reasons, British wanted a buffer area further north in Ladakh and avoid sharing a direct border with Russia and thereafter laying the seeds of an Indian claim to Aksai Chin. Earlier, in 1899, the British had concluded agreements with Russia without involving China in the fate of Aksai Chin and simply included it inside Indian borders. China considered entire Tibet, including Tawang and Aksai Chin as its own province and had sent conquering armies to Tibet in 1909. This unfortunate backdrop forms the historical perspective in Neville Maxwell's book "India's China War".

Neville Maxwell worked as a journalist for 'The Times' in New Delhi, in the years preceding the 1962 war. Most of the events in the book describe the details of what happened in India, the statements from Indian government, opposition leaders and the people. On the other hand, very little has been written about how the Chinese government came to decide and act in the way it did. There are merely the official chinese government statements tell us anything about the thinking on the chinese side and only in cases such as when the chinese premier, Chou en Lai visited New Delhi in 1959, to discuss the border issue, that we get more insight into how the chinese side worked. Overall, the book is very India centric, and because in this case, the Indian leadership happened to show maximum possible incompetence and naivette, the Indian side of the dispute is seen in poor light, while the chinese aggression and war crimes are covered up in fleeting mentions. It is indeed quite damning of the Indian political as well as military leadership just prior to and during the 1962 border debacle with China. The title of the book itself suggests that it was plainly the Indian side that indulged in a fantastic overestimation of their own military capabilities, failed to even agree to negotiate with the Chinese and then triggerred a war on long unresolved border issues with a dim-witted "forward policy".

Post independence from the British, the British commission office in Lhasa was simply taken over by an Indian commissioner and only visible change was in the flag that flew over. The government of India simply chose to maintain the ambiguity around the northern boundaries with China, presumably considering that such boundary negotiations are best done from a position of strength which India clearly wasn't in, at the time. China, too, played very passively and never raised the border fixation formally right through the years from 1949 to 1959. On official Indian maps, the Indian border was a rough demarcation indicating an indeterminate situation, but it still included Aksai Chin. It also included a highway that China had build from Xinjiang to Tibet, that passed through Aksai Chin and China considered that road as a vital connection to Tibet. The first prime minister of independent India - Jawaharlal Nehru, indicated to the parliament that India intended to hold and defend all the land marked south of the McMahon line as its own but also included Aksai Chin that the Chinese held. Nehru seemed to be in two minds even on a question of whether the border issue should be discussed and negotiated with China and got nowhere to making a mutually acceptable negotiation. So incredible was the level of indecision that Chou Enlai spent a week in New Delhi meeting the higher ups in Indian government trying to negotiate a border agreement but all he got was pleasantries, promises and zero commitments. Right when Chou Enlai boarded a plane back to China, the Indian side went back to making claims on land in chinese control, something that the chinese never agreed even if at that point the Chinese did accept that the land south of McMahon line was India's.

The height of the tomfoolery was India's forward policy, that is to have the army slowly and steadily establish posts and patrolling in areas such that they expand the Indian borders. The top politicians - Nehru and the defence minister V.K.Menon had total disregard to the objections of Gen. Thimayya when he stated that in case the chinese retailiated, the Indian Army was in no position to hold the forward areas due to lack of equipment, personnel and over-stretched logistics in the remote, hilly and forested land. The general resigned and was replaced by a political lackey, along with another curious character, B.M Kaul, who got a fast promotion to the Chief of General Staff and who was a favourite of Nehru.

The actual trigger to the war was the attempt to cross over a bridge near Thag La. Thag La itself is a remote, high altitude, thickly forested area, reachable only by a minimum two day march on foot from the Indian side but which was reachable in a few hours from the Chinese side courtesy of a proper road inside the Chinese border. The Indian defence minister with bright ideas was pushing for a forward take on Thag La brushing aside the advice of the commanders on the ground, such as Brig. Dalvi, whose book "Himalayan Blunder" also traces this period in accurate detail. At Thag La, the Indian army was neither as equipped as the Chinese but also short of personnel. CGS Kaul availed the luxury of a horse side instead of a two day trek to Thag La and then immediately returned to Tezpur citing altitude sickness. As the misadventure at Thag La became evident when the Chinese finally retaliated with overwhelming force, the CGS was quick to fly away to Delhi citing more serious health problems though he had no formal relieve. The Indian forward posts were quickly and easily wiped out, and in the next few weeks, the chinese army took over Tawang, Walong and even the 13000 feet high Se La pass, where the Indian army was looking to hold fort. There was panic setting in to an extent that even Tezpur in today's Assam was at the point of desertion and capituation. The situation in the western sector (Ladakh) was better than NEFA, where the soldiers of fallen Indian posts were scattered and frantically retreating towards home but still in a loss. The Indian army faced a comprehensive rout with 2000 to 3000 dead and missing, and the chinese seemed to have achieved all of their objectives by November 1962. Nehru seemed still dithering on reaching out to USA and Russia for military help because he could not get off the tall horse of non-alignment. When he did reach out to President Kennedy, it was late enough because China had announced a unilateral ceasefire shortly afterwards.

The Chinese ceasefire announcement was unexpected but the real rub was that they also announced their intention to withdraw completely from conquered lands and go back to positions that were held in 1959! That was exactly the Chinese view of the Indo-China border on the negotiation table at that time. It implied that the only reason for China to start the war was to teach a lesson and establish once and for all the right Indo-China border. Any further negotiations with India would be from a position of strength for the Chinese.

Were there proper lessons learnt from the disaster in India ? The high political leadership that was debating about how to beat back the enemy in the blink of an eye went into a shock. Nehru got a resignation from Krishna Menon and both Nehru and Krishna Menon were reluctant about it. Nehru himself was on the wane since then until his death in 1964. There was a shuffle in the army leadership and the succeeding prime minister Lal Bahadur Shastri made it a point to listen better to the army generals in the 1965 war with Pakistan. But the detailed findings and investigations into the 1962 loss remain unimplemented, and misunderstood even today as the Indian polity prefers to bury the dirty linen instead of cleaning and letting it dry in open air. You won't find a chapter in the regular history books about 1962 and will read about it only in books like Neville Maxwells's.

I liked this book but it tells a dark tale and a stark warning for people who are unprepared, who prefer to remain out of touch with reality and yet bear pride on their sleeves.

Efficiency pitfalls in Haskell

This is my third note on programming in Haskell that has performance centric commentary. First two are here and here. In this post, I hope to consolidate in one place several best practices and gotchas regarding runtime performance in Haskell, at an elementary level.

When I first learned Haskell, I would tend to solve any problem involving speed by going through the same old imperative tricks and techniques, with just a 'for loop' replaced by a map, aggregating actions replaced by fold and of course, using explicit recursion. If there was some data that had to be mutated, I would tend to introduce additional arguments to the function involved to bypass the need to mutate data.

Example,

raisedToLinear :: Int -> Int -> Int
raisedToLinear _ 0 = 1
raisedToLinear x 1 = x
raisedToLinear 1 _ = 1
raisedToLinear x y = x * raisedToLinear x (y - 1)

-- Linear time w.r.t exponent. To make it efficient...
-- Divide and Conquer makes this logarithmic time
raisedTo :: Int -> Int -> Int
raisedTo _ 0 = 1
raisedTo x 1 = x
raisedTo 1 _ = 1
raisedTo x y
| y `mod` 2 == 0 = sq * sq
| otherwise = x * sq * sq
where sq = raisedTo x (y `div` 2)


Here is another example where carrying forward the problem solving thinking from imperative languages can still help obtain an efficient solution using Haskell. It is a O(N) time solution for the maximum subarray problem, that every job applicant to the tech companies has learned how to write while asleep,


acf :: Int -> (Int, Int) -> (Int, Int)
acf elem (rs, best)
| (rs + elem <= 0) = (0, best) | otherwise = (rs + elem, max (rs + elem) best) maxsub :: [Int] -> Int
maxsub a = snd (foldr acf (0, 0) a)



It is the same logic expressed in Haskell, as is well known except that modification of variable that sums up incoming list elements is now handled as an accumulator while 'reducing' in a foldr. Its linear time alright but space ? Refer here for implications of using foldr on memory requirements in a lazy setting.

Also observe how passing an 'accumulator' argument helps the function acf improve efficiency. It uses a common technique of tupling the argument to include the best result so far as well as the ongoing accumulation.

Well, it makes for a rough and ready solution not involving too much knowledge of Haskell and making do with as much generic logical skills as possible. It would still work well as long as one is properly cognizant of mistakes usually made by beginners involving lazy evaluation and space leaks.

However, the techniques described by good books in Haskell approach problems differently. They tend to go strong on first defining types involved, writing composable functions that do a small single thing and then intelligently compose them. It makes the solution difficult to read and understand for someone fed on imperative algorithms and leaves us wondering why the paraphernalia is needed.

Under strict evaluation and in pure languages, one is forced to use explicit recursion to define functions for reasons of efficiency. It does not allow composing program logic out of simple library functions like folds, maps and filters.

Example,


-- With eager evaluation, code to select first element of a list that passed a filter would be -
first :: (b -> Bool) -> (a -> b) -> [a] -> b
first p f xs
| null xs = error "Empty List"
| p x = x
| otherwise = first p f (tail xs)
where x = f (head xs)

-- However, under lazy evaluation, happyness looks like ...
first :: (b -> Bool) -> (a -> b) -> [a] -> b
first p f = head (filter p) (map f)
-- Under eager evaluation, first p f = head (filter p) (map f) makes us
-- evaluate entire list and not stop where
-- the filter returns a single item that the head really needs.

Now, an example where seemingly innocuous code can deliver a painful bite when you least expect,

sum = foldl (+) 0

-- If sum is defined as above,
sum [1..10000]
-- consumes 10000 units of memory before it actually adds anything at all


If you are coming from a Scala background, foldl is known to be much more efficient than foldr because it does not need to consume space due to eagerly evaluating the passed function on elements of the list starting at the beginning. Tail recursively implemented functions were supposed to be memory efficient in a guaranteed manner. foldr was supposed to be the problem which required evaluating the list from the rightmost/last element and thus consuming stack space.

In Haskell, even foldl doesn't cure all ills.

Space Leak ?

Misunderstanding the term 'Space Leak' with the usual 'Memory Leak' leaves most C++ programmers dumbfounded. First, they see a mention of space leak as a problem with automatically garbage collected Haskell programs. Actually space leak should clearly refer to the fact that badly written Haskell code can end up consuming a lot more memory than should be needed. Lazy evaluation can blow up memory requirements and can make writing what should be simple 'bread and butter' code really tricky to get correct. What is worse, the problem doesn't show up until you pass a really large input dataset and track the memory consumption closely. Runtime failures such as stack overflows can be easily triggered.

Here is how it can hurt,


-- We want to compute the simple average of a list of Ints ...
average :: [Double] -> Double
average [] = 0
average xs = sum xs / fromIntegral (length xs)
-- Has a rookie mistake, consumes too much memory when it doesn't need to
-- and has unnecessary list traversals.


Of course, the summing and length calculation traverses the list twice so we try to fix it using a fold and get both together. As explained here, we use an eager version of left fold (foldl') defined as follows,


foldl' :: (b -> a -> b) -> b -> [a] -> b
foldl' f acc [] = acc
foldl' f acc (x:xs) = x `seq` acc `seq` foldl' f (f acc x) xs

sumlen :: [Int] -> (Int, Int)
sumlen = foldl' g (0, 0)
where g (s, n) x = s `seq` n `seq` (s + x, n + 1)

-- a fresh definition of average ...
mean [] = 0
mean xs = s / fromIntegral n
where (s, n) = sumlen xs


The above piece of code to calculate just an average contains a good number of concepts to grok. First it is the specially made eager version of foldl, that is memory efficient and uses a primitively implemented function 'seq'. seq simply evaluates its left argument and returns the right one as it is.

foldl' was used by another function sumlen so that sum of the input numbers and length of list could be calculated in one shot and using constant amount of memory.

Just knowing about the happy lever named 'seq' that turns on eager evaluation is not enough ! seq needs to be applied thoughtfully while implementing sumlen to take care that both 's' and 'n' are eagerly evaluated.

Purity does benefit Haskell code too, sometimes. It is able to cache values returned by functions in case the returned values do not depend on its arguments or if the returned value is "bound" to the function itself.

In the following example, the sum of first few prime numbers is calculated for the first invocation but running the same code again,


sumOfPrimes :: Int -> Int
sumOfPrimes n = sum (take n primes)

primes :: [Int]
primes = [x | x <- [2..], divisors x == [x]] divisors :: Int -> [Int]
divisors x = [d | d <- [2..x], x `mod` d == 0] -- the following blazes through... map (\x -> x + sumOfPrimes 1000) [1..1000]

-- but the following code is unable to re-use calculations of prime and crawls interminably,
sumOfPrimes2 :: Int -> Int
sumOfPrimes2 n = sum (take n primes2)
where primes2 = [x | x <- [2..], divisors2 x == [x]] divisors2 x = [d | d <- [2..x], x `mod` d == 0] map (\x -> x + sumOfPrimes2 1000) [1..1000]



Finally, read and interpret which of the following two versions of a function is more efficient.

The function basically calculates all possible subsequences of a list. So for any list of length N, it has exponential complexity. But still, one of these functions does the same job better -


subseq1 :: [a] -> [[a]]
subseq1 [] = [[]]
subseq1 (x:xs) = subseq1 xs ++ map(x:) (subseq1 xs)

subseq2 :: [a] -> [[a]]
subseq2 [] = [[]]
subseq2 (x:xs) = sxss ++ map(x:) sxss
where sxss = subseq2 xs


subseq2 is more efficient because it prunes repeat work of calculating subseq2 xs through reusing the common data sxss.

I learnt most of what I know about efficiency in Haskell programming from this excellent resource - Thinking functionally in Haskell by Richard Bird. The writing is quite comprehensive in coverage, precise and systematic.I encourage you all to proceed and read up.

How a simplistic pattern retains hold

It looks like a virus is going to help retain a commonly believed indicator of a recession.

As per this report of exactly a year ago, the US bond yield curve had inverted. Basically that meant that investors preferred to invest money with a 10 year maturity (a longer term bond) instead of a shorter term bond (say, a 3 month one). Investors would do that when they find that in the short term the uncertainties and risks are too high. So longer term investment in an instrument considered universally safe, such as US treasury, is better.

In each of the last 11 out of 11 instances of yield curve inversion, a recession has followed a few months to a year after that. The corona virus battered world is indeed staring at a recession now, exactly a year after the yield curve inversion. Several years later, would we say that this recession was indeed the 12 out of 12 success for the yield curve recession indicator ? We know that correlation does not imply causation but in this truly black swan case of the virus, even counting the correlation as the 12th success seems unwarranted. There is no common cause either for the inverted yield curve and the COVID 19 pandemic.

Folds unfolded

I wish that we, Haskell programmers, never fall into the ditch that Alan Perlis had imagined when he said that a functional programmer was someone who knew the value of everything and the cost of nothing. Haskell is a compiled language and runs with nearly as nice speed as C++. When I am learning Haskell, I do not want to take up learning a new language for merely the promise of elegant and short expression, but for comparable run time performance too. Ability to write concurrent processing code with no more difficulty than a single threaded program should be great for improving runtime performance. Over and above, it should also help deliver software with lesser development time and definitely lesser number of bugs. Haskell as a pure functional programming language promises all of that.

However, I would be far less obsessed with Haskell if I can't find a way to create software with superb runtime performance. Now, Haskell can show surprising runtime behavior and can shoot you in one foot and blow up the other one. For larger pieces of code, it can be tricky to predict runtime performance because of lazy evaluation and non-strict function arguments. I ran into such problems while understanding a very basic Haskell function that helps 'reduce' a list or some complex structure into a single value - "fold" and its variants foldl and foldr. An excellent introduction to the folds as well as comments on efficiency are written here. This writeup adds to the explanation with that wiki. Lazy evaluation is known to consume a lot of memory while holding references to pending computations so understanding how to use folds is critical.

To understand folds, it is necessary to also understand the two concepts of lazy evaluation and non-strict function arguments. Both of them are quite unusual for any programmer born and bred in C++ or Java.

Lazy evaluation - Haskell lazily evaluates expressions implying that it will do no processing until and unless the programmer needs to print the result to the console or save it to the database or some such thing. Further, Haskell will only evaluate to an extent the printing requires and no more. So it is possible to declare and manipulate an infinitely sized list of objects in Haskell as long as you require processing only a finite number of them -

sumOf10Primes = sum (take 10 primes)
    primes = [x | x <- [2..], divisors x == [x]]
    divisors x = [d | d <- [2..x], x `mod` d == 0]
    -- Dutifully prints 129

    last [1..]
    -- gone forever ! 

Non strict functions - The lazy evaluation described previously is made possible due to the non-strictness nature of some of the functions involved. The function 'take' did not touch the second argument it was passed the moment it has done returning 10 numbers. 'take' does not evaluate its second argument strictly, though it is strict about the first one. Basically, if a function is passed 'undefined' as one of the arguments and still sometimes completes successfully is non-strict in that argument.

Folds - Finally coming to the pitfalls for a novice programmer when using foldl or the foldr variant. The following piece of code taken from this wiki exhausts available RAM

-

foldl (+) 0 [1..100000000]
  -- Sum to 100M, are you crazy ? At least on my Ubuntu with GHCi ver 7.10.3
  -- bloats memory, freezes GHCi for several seconds even after a ^C...

  foldr (+) 0 [1..100000000]
  -- foldr doesn't help either ! 
  -- A stack overflow exception is seen fairly quickly. 

Well, both foldl and foldr failed but in apparently different ways. foldl tried to allocate memory for its so called thunks - unevaluated chain of functions piled up in memory. foldr exhausted stack while doing constructor replacement and not being tail recursive. A different implementation of the foldl described in the wiki works well in under 2 seconds, even for 100M numbers

-

foldl' f z []     = z
  foldl' f z (x:xs) = let z' = z `f` x in seq z' $ foldl' f z' xs

  sum' = foldl' (+) 0

Here, foldl' worked by suppressing lazy evaluation (or if you prefer, by forcing eager evaluation), through 'seq', a primitive function. Otherwise, foldl' is very much like foldl. what about foldr ? It works from the opposite end of the list and maintains the initial order of the list in case the output of the fold is another list. Also, foldr can short circuit evaluation in certain conditions but foldl is condemned to process the entire list before returning anything, always. This means foldr may be used to process an infinite list but foldl can never be. There are some intricacies in how the 'seq' function, it won't work as expected if used incorrectly but that is not the topic for now.

Here is an example where the short circuiting while using foldr makes a helpful difference.

foldr (\e a -> if mod e 10 == 0 then 0 else (mod e 10) * a) 1 [1..10000000]
  -- returns 0 instantly.
  -- Short circuting based on non-strict evaluation of the second argument 
  -- of the lambda function. 
  -- It works only because of the way the lambda is implemented.

  foldr (\e a -> (mod e 10) * a) 1 [1..10^7]
  -- Even foldr does NOT work well here. 
  -- The lambda "uses" both its arguments.

Recommendations - So here we are left with three possible choices whenever we want to fold or reduce some list or a complex structure.

Use foldl' when - Performing constant memory consuming operation on inputs where short circuiting is not going to work out. For possible infinitely sized inputs consider using foldr.

Use foldr when - Almost always if foldl' is not usable. If inputs are infinitely sized, or short circuiting will lead to better performance, this is only option.

Use foldl when - Almost never ! May be needed if there is some possibility that the input arguments are undefined and their evaluation can be skipped through lazy behavior of the function passed to foldl.

Consider this concocted example -

mult _ 0 = 0
  mult x y = x * y

  foldl mult 1 [2, 3, undefined, 5, 0]
  -- works and prints 0

  foldl' mult 1 [2, 3, undefined, 5, 0]
  -- blows up for working on undefined.

Haskell being lazy, garbage collected and coming from a C++ background, I personally prefer to use functions that have predictable and low memory consumption. Strictly evaluated foldl' serves such a purpose well. Unless of course, there is a good reason to use foldr or even the god forsaken foldl.