Readings in 2018


Following is the list of books, stories, and essays I read in 2018.

BOOKS:

(I) Non-Fiction:

  1. The Undoing Project, by Michael Lewis
  2. Engines of Creation, by K. Erik Drexler
  3. The Age of Em: Work, Love, and Life When Robots Rule the Earth, by Robin Hanson
  4. Data Feminism, by Catherine D’Ignazio and Lauren F. Klein
  5. How Professors Think, by Michelle Lamont
  6. The Sense of Style, by Steven Pinker
  7. In Spite of Gods, by Edward Luce

(II) Fantasy Fiction:

  1. Alloy of Law – Book 1 of Mistborn Era 2 (Wax and Wayne Series), by Brandon Sanderson
  2. Shadows of Self – Book 2 of Mistborn Era 2 (Wax and Wayne Series), by Brandon Sanderson
  3. The Shadow Rising – Book 4 of the Wheel of Time Series, by Robert Jordan
  4. The Dragonbone Chair – Book 1 of the Memory, Sorrow and Thorn Trilogy, by Tad Williams
  5. The Wise Man’s Fear – Book 2 of The Kingkiller Chronicle, by Patrick Rothfuss
  6. The Fires of Heaven – Book 5 of the Wheel of Time Series, by Robert Jordan
  7. Lord of Chaos – Book 6 of the Wheel of Time Series, by Robert Jordan
  8. A Crown of Swords – Book 7 of the Wheel of Time Series, by Robert Jordan
  9. A Darker Shade of Magic – Book 1 of The Shades of Magic Trilogy, by V.E. Schwab
  10. The Colour of Magic – Book 1 of the Discworld Series, by Terry Pratchett
  11. Elantris, by Brandon Sanderson
  12. The Armored Saint, by Myke Cole

(III) Science Fiction:

  1. The Long Way to a Small, Angry Planet – Book 1 of the Wayfarers Series, by Becky Chambers
  2. The Ninefox Gambit – Book 1 of the Machineries of Empire Trilogy, by Yoon-Ha Lee
  3. Semiosis, by Sue Burke
  4. Children of Time, Adrian Tchaikovsky
  5. Autonomous, Annalee Newitz

(IV) Speculative Fiction:

  1. Station Eleven, by Emily St. John
  2. Winter Tide, by Ruthanna Emrys
  3. The Obelisk Gate – Book 2 of the Broken Earth Trilogy, by N.K. Jemisin
  4. The Stone Sky – Book 3 of the Broken Earth Trilogy, by N.K. Jemisin
  5. All The Birds in the Sky, by Charlie Jane Anders
  6. Too Like The Lightning – Book 1 of the Terra Ignota Series, by Ada Palmer

(V) Rational Fiction:

  1. Luminosity – Book 1, by Alicorn

(VI) Historical Fiction:

  1. The 7th Function of Language, by Laurent Binet

NOVELLAS:

(I) Science Fiction:

  1. And Then There Were (N-One), by Sarah Pinsker
  2. Binti – Book 1 of the Binti Trilogy, by Nnedi Okorafor
  3. A Series of Steaks, by Vina Jie-Min Prasad
  4. All Systems Red – Book 1 of the Murderbot Series, by Martha Wells

(II) Speculative Fiction:

  1. Envy of Angels, by Matt Wallace
  2. The Slow Regard of Silent Things, by Patrick Rothfuss

(III) Rational Fiction:

  1. The Dark Lord’s Answer, by Eliezer Yudkowsky
  2. The Metropolitan Man, by Alexander Wales
  3. Branches on the Tree of Time, by Alexander Wales

SHORT STORIES:

(I) Speculative Fiction:

  1. Mono No Aware, by Ken Liu
  2. The Book of Sands, by Jorge Luis Borges
  3. Is God a Taoist?, by Raymond Smullyan
  4. The Sword of Good, by Eliezer Yudkowsky
  5. A Space of One’s Own, by Steve Rasnic Tem
  6. Vault, by D.A. Xiaolin Spires
  7. There Will Come Soft Rains, by Ray Bradbury
  8. When We Were Starless, by Simone Heller
  9. The Falls: A Luna Story, by Ian McDonald
  10. The Birding: A Fairy Tale, by Natalie Theodoridou
  11. Octo-Heist in Progress, by Rich Larson
  12. The Love Letters, by Peng Simeng

ESSAYS:

  1. Lessons Learned from Feminist Film Studies, by Tara McPherson
  2. Artificial Intelligence Policy in India: A Framework for Engaging the Limits of Data-Driven Decision-Making, by Vidushi Marda
  3. You and Your Research, by Richard Hamming
  4. Tolkien, Lewis and the explosion of genre fantasy, by Edward James
  5. Magical Realism, by Sharon Sieber
  6. Science Fiction and the Life Sciences, by Joan Slonczewski and Michael Levy
  7. In Praise of the Research University, by Harry Mairson
Advertisements

Book Review: The Liar’s Weave by Tashan Mehta

When asked why he wrote science fiction, Isaac Asimov replied, “It works up an artificial society, one which doesn’t exist, or one that may possibly exist in the future, but not necessarily. And it portrays events against the background of this society in the hope that you will be able to see yourself in relation to the present society… That’s why I write science fiction — because it’s a way of writing fiction in a style that enables me to make points I can’t make otherwise.” This fascination of SF to engage with the cultural dominant by layering and embedding in the fantastical has come to define the genre over the past century, particularly in western fiction. However, such stories can sometimes become subservient and formulaic either because they lack the nuance to adumbrate or the capacity to transcend their immediate social surroundings. Tashan Mehta’s debut novel, The Liar’s Weave, carefully sidesteps this trap and embarks on an extraordinary enterprise to create an outstanding fictionalization of the contemporary world.

The Liar’s Weave, set in early 20th century India, is a story about a stratified society comprising of three main classes of peoples; the In-Betweens who can accurately predestine the futures of people, the Fortunates who have been blessed with good luck, and the Hatadaiva who are ill-fated. The In-Betweens  form an ecclesiastical order of astrologers trained at the powerful Sapta Puri universities, seven institutions, “… that have perfected the art of reading the handwriting of the gods…” (p. 29) and practicing at the oft-adversarial Association. This grants them a position of incredible affluence even as they aim to adhere to a laissez-faire attitude towards the lives of their subjects, not unlike the Watchers from the Marvel Universe or the ideal of the Prime Directive from Star Trek (“The sacrosanct perspective of impartiality, of only dipping your fingertips into the pool of life, not the whole hand, is transforming.” (p. 100)). This policy of non-interference causes internal tension amongst their ranks and the manner in which they inevitably fail in this endeavour is embodied captivatingly through the narratives of utterly human characters such as Narayan Tarachand, Krishna, Svasa, and Govind, among others.

The second, and larger source of conflict comes from the rebellious faction of the Hatadaivas gathered in the heart of the Vidroha forest. This repressed group of outcasts led by their much-maligned leaders, Yaatri and Liling, seeks to wrest back control of their own destinies from the established order that told them the moment they turned eighteen, that their life was doomed. Reminiscent, at times, of Neal Stephenson’s Seveneves (2015), the defiance and mental fortitude of these human beings to stare down certain calamity and embrace a sense of self results in a cornucopia of emotional actions. These bring about an uneasy consistency that is congenial amongst the central characters, even if the purpose and message are beguiling; enchanting but in a deceptive way.

The Vidroha forest and its inhabitants are composed through brilliant evaluative and reflective streaks. Their rough, coarse exterior is slowly peeled back by showing their loneliness, their struggles and their inner beauty to reveal their supremely vulnerable identities. Uma, an elderly woman who suffered horrible violence and Dhani, a young child slated to die within six months, were shunned in the outside world despite having done nothing wrong: “He gestures to his small form, proud ‘I die in six months. I’m not crying. I’m going to eat all the fish and mangrove leaves I can.” (p. 142) Both find refuge and comfort here amongst other hatadaiva even on the bleakest of occasions like the Death Feast where they gather to commemorate a predicted death date, even in the most treacherous of forests. “Porthos moves, cracking a fallen branch, and the noose around a ringmaster opens to reveal a head, fangs and a forked tongue. The snake aims for Porthos’s shoulder.” (p. 106) They identify themselves with fiery pride as a people of their origins and imagined futures. It is easy to change oneself to suit anyone else, it is the hardest thing to reveal oneself as one is. Even if it is a simple self, care is in being that and not what is deemed worthy of perceived greatness. Mehta proffers this with acute acumen and elegance by drawing gorgeous imageries and metaphors.

Into the centre of these two complex and warring societies is thrust our hapless protagonist, a young boy named Zahan Merchant, with the supernatural ability to invent entire alternate realities by simply verbalizing his lies. He poses a unique threat to the astrologers’ way of living and offers a unique opportunity to the hatadaiva leaders in their pursuit of peace, divinity and control. Zahan barely stumbles from crisis to crisis with nary a clue as to what’s going on. Zahan’s powers are the stimuli that evoke a bewildering, yet exhilarating range of connections which, when the two societies ultimately collide, result in a sense of the sublime, subverting habitual narratives. The transition of differing ideas happens sans gaucherie even as the anarchical symbol of what to resist and what to fight against, parallels effectively against the backdrop of the national freedom movement.

Yuval Noah Harari’s Sapiens : A Brief History of Humankind (2011), casts ‘fiction’ as the real hero of what he calls the Cognitive Revolution in his Darwinian narrative of human society. What differentiated our human species, the Homo Sapiens, (that survived then and thrives now) from the other human species that populated Earth 200,000 years ago, is our language and related means of communication to build even that which does not exist. Sharing fictions and stories across diverse communities to coordinate and organize, according to Harari, was a key part of this cognitive revolution which in turn led to the agricultural and scientific revolutions, ultimately enhancing our emergence as the dominant organism on the planet. Alasdair MacIntyre drew equivalent interpretations of the importance of myths in modern societies as a way to gain sovereignty with absolute power. Similarly, the central motif, in Zahan’s world that is already taut with tension, is the power to create by storifying. Mehta does well to encapsulate this quintessential nature of evolution and injects events with moral and ethical discipline.

The Liar’s Weave does have its shortcomings, though. It struggles with pacing, particularly towards the end when there just isn’t enough time left for Zahan, Narayan Tarachand or Yaatri to allow for the resolutions to become satisfactory. It’s not that the conclusion is open-ended, in fact that ambiguity does justice to “… hold contradictions in balance …”, it’s the rushed ending that leaves much to be desired for. It suffers from being maddeningly overcrowded with numerous fringe characters which leaves important moments and relationships with unfulfilled potential. At times, the beautifully descriptive writing becomes laborious due to lack of restraint. However, these failings are easily overshadowed by the ambitious plot settings, well-developed primary characters and Mehta’s attention to tonal and thematic consistency.

Perhaps most importantly, The Liar’s Weave asks the basic and immediately recognizable SF question “what if” (in this case, what if we actually had the Gift to predict the futures of people?), and draws its sense of wonder by ably exploring this thought experiment. It delicately teases out a dissonance between the fictive world and the reader’s real world in the mold of the Suvinian concept of cognitive estrangement (cf. Metamorphosis of Science Fiction, 1979) through a rational extrapolation of the Indian social conditions. And in doing so, it brings historical innovation that is almost introspective and strikingly poignant. That’s what engenders cogitation and makes it such a worthwhile read.

Sage Project Log

In order to help plan better, work in a more structured fashion and have a record of the work we did during the GSoC 2016 in Sage, we maintained a daily project log. This was institutionalised starting with Week 4 and we reproduce the log below.

Week 12:

16th, 17th August:

  1. Made all the remaining changes, and pushed the changes to the Gabidulin Ticket. Added the code to the catalog files. There are a couple of issues that need to be resolved based on feedback and then the changes can be made. Commit can be found here.
  2. Started writing documentation for the ARMC class. Will push everything I have on that on 18th.
  3. Created three new tickets for the stuff left over from the original 13215 ticket and pushed all the relevant code.
  4. Started preparing presentation for Sage Days 75. Will share the first draft of outline and ideas on 18th.

15th August:

  1. Finished writing documentation and tests for #20970. Finished channel class for the code. After one final pass, will push everything on 16th. There are two tiny issues. One is given a matrix in Sage, how to find a specific non-trivial solution for it. I.e. for matrix A, find non-trivial x_0 s.t. A*x_0 = 0. Currently, the parity evaluation points method is failing because of this. This also causes the channel to fail at times. And the second is suggestions for better names in a couple of places.
  2. Created the second ticket from the leftover stuff from #13215. Will push karatsuba and centering tickets on 16th and the last one as well if possible. Otherwise, this will be done by 17th.
  3. Updates to the ARMC class. Specifically, adding documentation and tests, and fixing some bugs that were causing incompatibility issues with the Gabidulin Code class.

11th, 12th August:

  1. Made changes to 21131. It is open for review.
  2. Made changes to finite field ticket. It is open for review. 21088
  3. Solved some pickling errors and other comments by Travis. The remaining ones are due to Frobenius it seems. Once it’s decided, whether or not to add experimental decorator, I will update it. Almost open for review.
  4. Gabidulin, channel class ready. After one final pass, that ticket will be ready to be done.
  5. Prepared Tickets C and D. Will create them and push after one final pass.
  6. Weight enumerator and additional methods in ARMC.

9th, 10th August:

  1. Created rank_metric.py. Deleted methods according to discussions based on recommended schema. Verified docstrings of inherited methods. Worked on rank support and weight enumerator. Started testing a little. Stuff is not working correctly. Hence the delay in pushing.
  2. Gabidulin inherits from this. Removed rank related methods from there. Made that compatible with this.
  3. 21088 – finite fields ticket. nearly done. Will push that tomorrow.
  4. Made changes to 21131 as per discussion
  5. Created Ticket C (karatsuba stuff).

Week 11:

8th August:

  1. Further fixes to 13215. (1.5 hrs)
  2. Worked on the channel class. But in order to use that in the way David mentioned, I need random element. So I figured it would be better to have a few methods of the ARMC class implemented first. Added new file, inherits from ALC. Basic getter methods, moved matrix to vector and vice versa from Gab. Random element. And Gab inherits from ARMC. (6hrs)
  3. Worked on the 21131 ticket. That’s now open for review. (4hrs)

4th August:

  1. Wrote channel class for Gabidulin code. Testing continued. Added some checks. Started adding final documentation for every method. (~5hrs)
  2. Moved MPE to skew poly. Continued with MVP and interpolation based on comments on trac. (~2.5hrs)

3rd August:

  1. Made changes based on comments by Jeroen on Ticket #13215 (~4.5hrs)
  2. Fixed Gao Decoder. Edited the construction of Gabidulin Codes to include twist homomorphism. (~3hrs)
  3. Made changes to #21131 based on latest comments. (~2hrs)

Week 10:

28th, 29th July:

  1. Worked on Ticket #21088. Commits can be found here.
  2. Worked on Ticket #21131. Commits can be found here.

27th July:

  1. Worked on the comments and discussions on Ticket 13215. (~6hrs)
  2. Rewrote and am testing ticket 21088. (~2hrs)

26th July:

  1. Fixed documentation build errors from 13215. (~3hrs)
  2. Added documentation for interpolation, MSP and MPE. Added documentation for Gao decoder in Gabidulin Codes. (~1.5hrs)
  3. Worked on additional polishing of Ticket 13215 based these comments. (~3hrs)

25th July:

  1. Resolved single and double backtick inconsistencies from the various files of ticket 13215. Replaced method _cmp_ with _richcmp_ based on recommendations from mentors. removed some latex imports. Commits can be found here. (~3hrs)
  2. Worked on adding minimum subspace polynomial, multi-point evaluation and interpolation methods for Ticket 21088. Fixed the various bugs and incompatibility errors. Commit can be found here. (~4hrs)
  3. Added documentation and tests for the Gabidulin Code class. Will proceed with the verification of Gao decoder implementation once MPE, MSP and Interpolation are resolved. (~1hr)

Week 9:

20th, 21st, 22nd July:

  1. Several threads of discussion regarding the Ticket A were discussed and worked upon. These changes which included removing double imports and unused classes and methods, adding a section in the index file for documentation, improved module description and definition, across various files and finally documentation, tests and code clean up. The commits can be found here.
  2. Created ticket B based on past discussions and pushed changes. Added documentation, tests, fixed doctests and removed unused methods. The ticket can be found here.
  3. Worked on the Gao Formulation decoder for the Gabidulin Code class.

19th July:

  1. Noted down comments from the review of Ticket #13215 and implemented most of the changes. Once the doubts are clarified tomorrow, I’ll submit the edits. (~4hrs)
  2. Started working on Ticket B and comparing with its “polynomial” equivalent to identify the problem areas. (~2hrs)

18th July:

  1. Fixed final documentation, tests and errors. Cleaned up code and pushed changes. (~5hrs)
  2. Edited Gabidulin Codes to adapt to the updated 13215 ticket. Pending: edit minimum subspace polynomial and multi-point evaluation.(~2hrs)
  3. Started preparing creation of Ticket B. (~1hr)

Week 8:

16th July:

  1. Picked up from the pending work from Friday (yesterday). Added all remaining documentation to the skew_polynomial_element.pyx file. Added all missing tests. (~2.5hrs)
  2. Fixed errors in implementation of a couple of methods (is_gen, section). (0.5hrs)
    Phased out side from the _pow_ function. (~1hr)
  3. Added small tests and fixes to skew_polynomial_ring_constructor.py. (~1hr) [Only documentation and a couple of tiny methods remain to be added for the Class SkewPolynomialRing_general. Should not take more than an hour or two. Will try and finish this on Sunday. If not, first thing on Monday.]

15th July:

  1. Went through the skew_polynomial_element.pyx, skew_polynomial_ring.py and skew_polynomial_ring_constructor.py file to identify the remaining tasks so as to reach the “needs review” state. (~2hrs)
  2. Added missing methods in skew_polynomial_element.pyx based on discussions. (~2hrs)
  3. Added documentation for some private methods. (~1hr)

14th July:

  1. Cleaned up code, refactored and added some tests and documentation in the skew_polynomial_element.pyx file. (~2hrs)
  2. Removed def gcd, xgcd, quo_rem and monic. Renamed lgcd as left_gcd and respectively for all other methods. (~2hrs)
  3. Phased out “side” arguments. (~1hr)
  4. Solved some bugs that had come up because of the edits and deletions made above. (~1hr)
  5. Went through “polynomial_element.pyx” to compare which methods were missing in the skew_polynomial_element.pyx file. Added some. (~2hrs)

13th July:

  1. Cleaned up, refactored and added some tests and documentation in the skew_polynomial_element.pyx file. (~2hrs)
  2. Implemented a special case of the is_unit method for skew polynomials. General case requires support for finding the order of automorphisms. (~1hr)
  3. Fixed the final remaining doctests. (~1hr)
  4. Finished setting up Sage in Emacs and Sage Notebook. Learning how to use them… (~2hrs)
  5. Started phasing out side.py in 13215. (~1hr)

12th July:

  1. Sorted out cherry pick and pushed changes here. (~1hr)
  2. Decided on the most primary cuts to form Ticket A (as per discussions). Pushed changes here. Other files such as side.py are kept for now and will be phased out during refactoring.(~2hrs)
  3. Fixed NotImplementedError and other standalone failing doctests from skew_polynomial_element.pyx. See commit here. 127 doctests remain. All of them are caused by some invalid homomorphism problem. Started looking into that. (~3.5hr)
  4. Started setting up sage-mode in Emacs and started acquainting myself with it. (~1hr)
    Cleaning up skew_polynomial_element.pyx. (~1 hr)

11th July:

  1. Prepared notes on the five-way split of the original 13215 ticket and discussed with mentors. (~3hrs)
  2. Set up sage notebook. It was giving some error with openssl and required it to be switched off. (~1hr)
  3. Using cherry-pick to add commits from public branch test_13215_interactive (not merging properly. it is giving some weird error with the test.sheet file. (~1hr)
    Running doctests on skew_polynomial_element file after the aforementioned commits gives 334 errors. Fixed some very simple basic ones just to see how I can proceed here. (~1hr).
  4. Started cutting away portions of 13215_original to form Ticket A. (~2 hrs)

10th July:

  1. Got an overview of the classes of the ticket and the dependencies between them.
  2. Noted down purpose of each. (~2hrs)
  3. Wrote down observations about what seems redundant and what needs work in every class. Also made a list of all the classes and methods and functions that have missing docstrings and doctests. (~2.5hrs)
  4. Started adding the missing tests and docs for the skew_polynomial_ring.py file. (~1hr)

Week 7:

9th July:

  1. Made final edits to the rank-metric conversion and properties. Wrote documentation and tests. Pushed commit here. (~1.5 hr)
  2. Removed some of the compile errors from the unencode_nocheck method and supporting methods. Finished writing multi_point_evaluation method. I was using the zero element of Fqm to initialize while I was actually supposed to use the zero element of the message_space (skew polynomial ring). Apart from the main error in #13215, the rest of these methods seem to have no errors. Will confirm once resolved. Pushed commit here (~3 hrs)
  3. Made final edits to the documentation and tests of the skew_polynomial_ring_constructor.py file from #13215. Ready to commit. (~1 hr)

8th July:

  1. Edited gabidulin.py based on comments.
  2. Continued writing interpolation of skew_polynomials.

7th July:

  1. Fixed one more of the two remaining errors in #13215. It seems that the ‘Left’ object has not been implemented in a lot of places in the skew polynomial ticket.
  2. Completed reading relevant sections of the paper mentioned below. Started writing code. Placing it in gabidulin.py for now.

6th July:

  1. Wrote conversion for matrix form back into vector form. Added support for computing rank-distance, rank-weight.
  2. Started reading this for how to interpolate a skew polynomial for the unencode and (future) decode methods.

5th July:

  1. Fixed the tiny compile errors that were induced in the Skew Poly ticket due to Sage upgrade.
  2. Testing of code that was written last Friday and Monday that had gone unchecked. Fixed errors.
  3. Wrote conversion into matrix form from vector form of a Gabidulin codeword. Takes a basis as argument.

4th July:

  1. Added support for generator matrix, dual code and parity check matrix of Gabidulin Code.

Week 6:

1st July:

  1. Continued porting to inheritance from SageObject.

30th June:

  1. Fixed bugs in the evaluation_points, encode, message_space and operator evaluation method for skew polynomials (this bit still needs more work).
  2. Based on discussions, removed inheritance of Gabidulin Code class from AbstractLinearCode class. Now moving towards a stand-alone class that inherits from SageObject.

29th June:

  1. Added support for the default option from below.
  2. Created a method for the “ext” function from Lemma 2.1 (of the PhD thesis) on Mapping to Ground Field.

28th June:

  1. Started adding some tests for the various methods.
  2. Added support for an optional argument that can be supplied to the constructor for the code. This allows them to provide a set of linearly independent elements of F_{q^m} over F_q if they choose. Need to add support for default option.

27th June:

  1. Continued working on constructing a codeword.
  2. Trying different input arguments to see which is most convenient to use and still allows flexibility for user.

Week 5:

24th June:

  1. Evaluated linearized polynomials (sample examples) at various random points.
  2. Called relative finite field extension ticket for the vectorial representation of big field in small field in an attempt to form a codeword. This is not working properly. But I think I should have something to present on Monday.

23rd June:

  1. Tested construction of linearized polynomials from skew polynomials. By putting in a zero derivation and a Frobenius endomorphism (for a finite field, Frobenius endomorphism is a Frobenius automorphism and hence this is a linearized polynomial ring), it seems to be constructing a ring. Will have to test addition and multiplication once the doctests are solved.

22nd June:

  1. Submitted Midterm Evaluation. Prepared blog post. Nearly ready to put it up.
  2. Read relevant sections of the following papers: Coding with Skew Polynomial Rings, Welch-Berlekamp Like Decoding Algorithm for Gabidulin Codes, Fast Encoding of Gabidulin Codes
    Started designing basic outline of gabidulin.py. Prepared classes for the Code, Encoder and Decoder. I will have a several more details in a design document by tomorrow.

21st June:

  1. Continued to fix errors. And pushed recent commits to Ticket 13215. Down to final 2 types of errors.

19th June:

  1. Caught a bug. Came down with a flu. Stuck in bed all day.

Week 4:

17th June:

  1. Continued fixing doctest errors. Relatively slow day, managed to get about 70 solved today. Still about 330 to go. Starting to get the hang of this now. I think.
  2. Started drawing up design document for Gabidulin codes. The aim is to try and get all the errors resolved by this weekend and scrub the patch and get it accepted by Monday.

16th June:

  1. Continued fixing doctest errors. Managed to get about 200 solved today. Still 400 to go.

15th June:

  1. Continued fixing doctest errors in the Skew Polynomial patch. Reported no_attribute_found errors in richcmp, init_cache, and other ValueErrors.
  2. Read the Skew Polynomials patch to try and understand what can be used and how for the construction of Gabidulin codes.

14th June:

  1. Began fixing doctest errors in the Skew Polynomial patch. There were about 650 errors to begin with.
  2. Solved some very simple errors such as Deprecation warnings, errors with “interrupt.pxi” etc. About 600 more to go.

13th June:

  1. Fixed Cython function declaration compile errors from Skew Polynomials patch.
  2. Pushed changes to Ticket #13215

12th June:

  1. Successfully merged Skew Polynomials patch on local system
  2. Fixed deprecated PY_NEW_SAME_TYPE and PY_TYPE_CHECK_EXACT

 

Project Linear Rank Metric Codes in Sage – GSoC 2016

 

Introduction:

This document is meant to be a reference for people who want to understand the work done on implementing Skew Polynomials and Rank Metric Codes in Sage as a part of this GSoC 2016 project. My mentors for this project are Johan Rosenkilde and David Lucas. This post provides a brief mathematical background, summary and status of the tickets related to the project and further links to detailed discussions and the code. It is assumed that the reader is familiar with the basic concepts of abstract algebra, coding theory and Sage itself.

Background:

A Skew Polynomial is given by the equation:

        F(X) = a_{n} \times X^{n} + ... + a_0

where the coefficients a_i \in R and X is a formal variable. Let R be a commutative ring equipped with an automorphism \sigma. Addition between two skew polynomials is defined by the usual addition operation and the modified multiplication is defined by the rule X \times a = \sigma(a) \times X for all a in R. Skew polynomials are thus non-commutative and the degree of a product is equal to the sum of the degrees of the factors. Then the ring of skew polynomials can be written as R[X, \sigma].

Linear Rank Metric Codes are linear error correcting codes over the rank-metric and not the Hamming metric. The distance between two matrices is defined as the rank of the difference between them. And this forms a metric. They are a way to build codes that can detect and correct multiple random rank errors. Gabidulin Codes are an example of linear rank metric codes.

A Gabidulin Code Gab[n, k] over \mathbb{F}_{q^m} of length n (at most m) and dimension k (at most n) is the set of all codewords, that are the evaluation of a skew polynomial f(x) belonging to the skew polynomial constructed over the base ring \mathbb{F}_{q^m} and the twisting automorphism \sigma.

        \text{Gab[n, k]} = \big\{ (f(g_0) f(g_1) ... f(g_{n-1})) = f(\textbf{g}) : \text{deg}(f(x)) < k \big\}

where the fixed evaluation points g_0, g_1,..., g_{n-1} are linearly independent over \mathbb{F}_{q}. These codes are the rank-metric equivalent of Reed Solomon Codes.

Implementation:

During the community bonding period, we started with a small fix to the wtdist_gap method from the module linear_code.py. This involved improving its documentation, changing to a better name and making the method private. We also opened a ticket for a new abstract class for Golay Codes. However, there was not enough time to finish this ticket since the coding period started. 

David had already implemented a class to manage representation of elements of a field extension into a smaller field. We went through the review checklist in Sage. This has now been merged into Sage.

Xavier Caruso had authored a ticket on Skew Polynomials about four years ago. This was not reviewed at the time. And the category framework in Sage underwent massive restructuring and change since then. As a result, this ticket was very incompatible. We first started by resolving the several hundred doctest errors some of which were due to deprecated syntax errors while others were more technical. This ticket was the most difficult and complicated module and it took a lot longer than originally anticipated. Debugging the code ended up breaking Sage several times before all originally present doctest errors were resolved. Once the ticket started working, a lot of the methods and classes still did not have proper documentation and/or tests and we added those. Since this was a huge ticket, we then decided to break it up into five smaller tickets based on the content and dependencies to make the work more manageable. We majorly refactored the code in the first ticket to make it cleaner and then added methods such as operator evaluation, interpolation, minimum vanishing polynomial, etc to the appropriate various classes. For the purposes of the other targets for the GSoC project, we practically needed only the first of the five tickets (mentioned above) which dealt with the basic implementation of skew polynomials and skew polynomial rings. So the primary focus has been to get that merged. The second ticket based on skew polynomials over finite fields has also been worked upon. The remaining three tickets were more or less lifted directly from the original skew polynomial ticket and no effort has been made yet to accommodate for changes to these.

We then created a new abstract base class for Gabidulin Codes and implemented Generator Matrix based and Skew Polynomial Evaluation based encoders for it. This module also included a Gao Decoder for the Gabidulin Code and a Channel class to introduce random rank errors. Along with all of this, basic getter methods and methods to compute some basic combinatorial properties were also implemented. 

Lastly, we worked on a new base class called AbstractLinearRankMetricCode that inherits from the AbstractLinearCode class and from which Gabidulin Code inherits. This class provides methods that are common to any Linear Rank Metric Code so as to facilitate the creation of other such codes. It also deletes those methods from the general linear code class that are not valid in the case of rank metric codes.

Current Status: The tickets related to skew polynomials, Gabidulin Codes and AbstractLinearRankMetricCode are currently still open. We believe that the skew polynomial ticket is almost ready to be merged into Sage. It has been well tested and we believe it is in stable condition. The Gabidulin Code ticket is not as rigorously tested and the Gao decoder in particular needs to be examined further. The completion of this ticket depends on the AbstractLinearRankMetricCode class which requires also requires some work.

I am currently attending Sage Days 75 in Paris to which I was invited by my mentors. We have coding sprints all week long and we aim to wrap up all of the starred tickets (see below) this week. The next section provides links to more elaborate details about the work done during the project.

Code:

All relevant tickets, bug reports and code commits can be found below:

  1. #20565 – Fix LinearCode.wtdist_gap method (enhancement)
  2. #20787* – A class to manage Golay Codes (new)
  3. #20284 – A class to manage representations of elements of field extensions (review)
  4. #13215* – Skew polynomials (enhancement)
  5. #21088* – A class for skew polynomials over finite fields (enhancement)
  6. #21131* – Interpolation/evaluation methods for skew polynomials (content)
  7. #21259* – Karatsuba-based methods for skew polynomials (content)
  8. #21262* – Center-related content for skew polynomials (content)
  9. #21264* – Factoring/irreducibility methods for skew polynomials (content)
  10. #20970* – A class for Gabidulin codes (feature)
  11. #21226* – An abstract class for rank-metric codes (feature)

Tickets in green represent merged code, tickets in blue represent mature code and the ones in brown represent immature tickets.

The daily project progress log that provides further details about the project can be found at the following link:

https://arpitdm.wordpress.com/sage-project-log/

The blog posts related to Sage can be found here:

https://arpitdm.wordpress.com/category/open-source/sage/

 

Skew and Linearized Polynomials

Gabidulin Codes, one of the primary modules of my GSoC project, are Maximum Rank Distance (MRD) codes analogous to Reed Solomon in Rank-Metric. In this post, I give a basic overview of the one of the preliminaries, Skew and Linearized Polynomials, required in their construction in Sage.

Consider a non-commutative ring {R = \mathbb{F}[X; \sigma, \delta]} where we have a ring A of usual polynomials in variable X, a ring endomorphism {\sigma} on A and a {\delta}-derivation which is essentially a map {\delta: A \rightarrow A} such that for all a, b in A,

{\delta(a + b) = \delta(a) + \delta(b)}
{\delta(a + b) = \delta(a)b + \sigma(a)\delta(b)}
This ring with the usual addition and modified multiplication subject to the relation above is called a Skew Polynomial Ring of Endomorphism type. Recall that, a Homomorphism is a structure preserving map from one mathematical object (such as group, ring, vector space) to another. And an Endomorphism is a homomorphism from a mathematical object onto itself.

Given a finite field {\mathbb{F}_q} of order q and its extension field {\mathbb{F}_{q^m}} for some fixed positive integer m, a Linearized Polynomial in variable X is given by

{L(X) = \sum_{i=0}^{n-1} a_i X^{q^i}}

where each of the coefficients {a_i} belongs to {\mathbb{F}_{q^m}} and the exponents of the monomials are powers of q. The degree of this polynomial, also called the q-degree, is n-1. The non-commutative univariate Linearized Polynomial Ring consisting of all such polynomials L(X) over {\mathbb{F}_{q^m}} is denoted by {\mathbb{L}_{q^m}}[X]. Ernst Gabidulin used this ring to build Gabidulin codes where codewords are given by the coefficients of the polynomials, i.e. {C = (a_0, a_1, . . . , a_{n-1}) \in \mathbb{F}_{q^m}^{n} }.

Linearized and Skew Polynomial Rings are isomorphic with matching evaluation maps. More specifically, when the derivation {\delta} is 0 and the endomorphism {\sigma} is a Frobenius Automorphism (recall that an automorphism is an endomorphism that admits an inverse and for a finite field, a Frobenius Endomorphism is always also a Frobenius Automorphism), the Skew Polynomial Ring becomes a Linearized Polynomial Ring. That is to say, the latter are a special case of the former.

Sage has an open ticket that already implements the Skew Polynomial Ring and provides functionality to evaluate a given polynomial and perform basic operations such as addition, subtraction, multiplication and division. Our aim therefore, is to complete the open ticket and use that to create the appropriate, required linearized polynomial ring.

 

 

First Contributions

Setting up for developing Sage is one thing, actually contributing to the development is a completely different ball game. The development process, broadly speaking, consists of the following steps:

  1. Identify a defect, bug, enhancement or new feature that Sage has or requires.
  2. Open a ticket on Trac describing the exact problem.
  3. Enter discussions with other community members on clarifying the issue and discuss solution and implementation ideas.
  4. Write code and submit.
  5. Get it reviewed by other at least one other independent programmer.
  6. If review is positive, the ticket is closed and code is successfully merged. Otherwise, go back to step 3 and repeat.

As a contributor, one needs to know how to do both, review as well as successfully write code. And that is what this post describes. I’ll use tickets that I worked on, to illustrate these aspects of development in further detail. In order to avoid confusion, I’ll use Code while talking about Coding Theory and code to talk about programming.

Reviewing a Ticket:

David and Johan (my mentors for the project) suggested Ticket #20113. The zero method in the linear_code.py file was supposed to return the zero vector of the associated Code. The original implementation called the gens method (the generators of the Code), took the first element of the returned list, multiplied it by 0. This resulted in all zero vector of length of the Code. While the solution wasn’t incorrect, this was a rather tedious way of obtaining it. David had already submitted a patch that simply called the zero element from the ambient space of the Code to produce the answer.

My job was to review this new code and at first glance, this seems trivially correct. And it was. But this may not always be the case. Sage is a massive beast and a small change in one part of the code could break something in some other seemingly unrelated part of the code. There are a lot of things that need to be verified and the best way is to simply follow the Reviewer’s Checklist. I’ll clarify some of the terms from there first and then provide a general rule-of-thumb workflow on how to interact with the git-trac system to review.

  • Doctests and Coverage: The documentation for each of the methods in Sage contains examples of code that explains how to use the method. Python can search for and extract these commands, run them and compare the output to the one mentioned in the documentation. If the patch changes code, the doctests for all the changed methods must still hold true. To do this, run the command `./sage --coverage src/sage/coding/linear_code.py.
  • Manuals and Building: Manuals serve as a reference book and can be incredibly useful for quick reference. Sage adds material to its manuals from the documentation in the source code itself. Which is why the documentation should follow a specific template. See here for examples and notice the formatting and indentation. Run `./sage –docbuild reference html` to build the html version of the “Reference” Manual. Others include _tutorial, developer, constructions and installation_. These are also available in pdf versions.
  • Speedup: Generally, it is hard to check the speed. Standard Python time-management (import time, time_clock()) can be used. The main idea is to ensure that the new code does not utterly slow down Sage. Patchbot reports can also be used but caution should be exercised and error reports should be double-checked. Run methods on large inputs, compare to other softwares that offer similar functionality, try boundary cases and consistency checks based on mathematical foundations.

Review Workflow:

  1. git trac checkout TICKET_NUM (This will create a local branch say t/20113)
  2. git checkout t/20113
  3. ./sage -b (See if the code builds without errors)
  4. Run through the Checklist above and note down errors, if any.
  5. Run various test examples in an attempt to “break” the code.
  6. Go to Trac and write comment(s).
  7. Change ticket status.
  8. Write your full name in the Reviewer field of the ticket.

Writing a Ticket:

David and Johan suggested improving the efficiency of the decode_to_code method of the Nearest Neighbour Decoder. I opened a Ticket #20201 on Sage to fix this. The previous implementation created and stored the distances between the received word and every codeword. It then sorted the entire list in order to find the closest codeword. This took exponential memory and time in the size of the Code which can be very inefficient for large input. An obvious solution is to compute the Hamming weight for the first codeword and set that as the minimum. Then, iterating over the rest of the codewords and updating the minimum drastically brings down the memory and run time requirements.

There are some major differences when it comes to actually opening a new ticket and writing code for it. Whenever you write new code in Sage, you might want to add some print statements and code, run the files, test, make small changes and test again. In that case, you have to build sage (./sage -b) or in some cases even run make distclean &amp;&amp; make which can take a very long time. Instead, the best way is to write your new code in a myfile.sage file and then run ./sage myfile.sage.

Write Workflow:

  1. Open a new ticket on Sage. Or if a ticket that has commits already exists, create a local branch on your system. And then pull the changes from the ticket onto your branch. Do not directly checkout the ticket. It can result in very weird errors.
  2. Discuss solution idea on trac.
  3. On the local branch (NOT master) corresponding to the ticket, write your code.
  4. Test your code.
  5. git add <changed_file(s)>
  6. git commit -m "insert detailed message here."
  7. `git trac push TICKET_NUM`
  8. Once you’re satisfied with your commits, set the ticket field to “needs_review”.
  9. If positive, ticket closed. Else, go back to step 2.

As a final note, Sage is guaranteed to break down at any point for seemingly no valid, discernible reason and I’ve lost track of the time I’ve spent in trying to fix it. But in doing so, I’ve learnt a lot about the codebase and once you successfully manage to rebuild Sage, there is a weirdly awesome feeling of accomplishment!

On Applying to Sage for GSoC

Sage is a viable open source mathematics software package that offers an extensive toolbox
for algebra, combinatorics and numerical computations. This massive project can seem daunting to someone who wants to begin contributing to it, especially in the short GSoC application period. In what follows, I cover a constantly updating collection of advice for new programmers, to simplify the process of applying to Sage.

1) Where to find Sage

Mailing Lists:

The following are the primary ones:

  • sage-devel – development discussion group of Sage
  • sage-support – help in running/using Sage
  • sage-gsoc – related discussions regarding the GSoC program

Apart from these, there are tons of other topic based lists dedicated to specific modules. For example, sage-coding-theory. When applying to GSoC, find a project from the Ideas page and post on sage-gsoc (with a cross post on the related topic-based list, if it exists) indicating your interest in the project and request more details; instead of simply asking for help in “getting started” since one is “very interested in contributing to open source”.

Source Code:

  • Source Code – Download your copy of Sage from here
  • git.sagemath.org – Online Sage repository. A good way to read the code online
  • Documentation – Developer’s guide to the Sage
  • Trac – Organizing development and code review through tickets

2) Contributing to Sage

The following is more of a cheat sheet to setup everything you need so you can begin contributing. When in doubt or need of further clarity, always refer to the official documentation. It is really well written!

Installation:

  1. Install Sage: Assuming the source code is downloaded, unzip it and go inside the directory. And run “make”. This should take a few hours. Once it finishes, you can run it by typing “./sage” on the command prompt.
  2. Configure git: Assuming you have git installed, run the following two configuration commands (if you haven’t already)

    git config –global user.name “Your Name”
    git config –global user.email you@yourdomain.example.com

  3. Install git-trac:Now, all development tasks can be performed in the usual way using git and a browser. Alternatively git-trac can simplify the communication process between git and trac. To use this, run:

    git clone https://github.com/sagemath/git-trac-command.gitsource
    git-trac-command/enable.sh (enables it temporarily)
    cd git-trac-command
    sudo python setup.py install

  4. Obtain Sage Trac account: Development happens through tickets on Trac. In order to comment, review, commit or interact in any other active way with the source code, a Trac account is required. To do that, send an email to sage-trac-account@googlegroups.com, containing your full name, preferred username, contact email and reason for needing an account. Once the request is approved, a username and password will be assigned.
  5. Configure git-trac: Authentication mechanism is required for read-write access. Simply put, sage needs to be told about trac with verification. To do this, run:

    git trac config –user USERNAME –pass ‘PASSWORD’
    ssh-keygen (to generate a public/private rsa key pair)

    Run the Sage prompt (./sage) and upload it to trac using the command “dev.upload_ssh_key()“. Use the credentials obtained above for completing the authentication.

Again, the Sage documentation is magnificent and it should be referred to in case of doubts or further explanations. Once all this is done, one can start contributing by checking out an existing ticket or opening a new one. There is a lovely cheat sheet on how to do all that, already available. The way development happens is, someone opens a ticket regarding a bug, defect, new feature or enhancement and writes code for it. Once the commit is ready, it is opened for review whereupon an independent second programmer checks it and suggests changes or gives it a thumbs up.

Communicating with the Sage community:

While the people in the community are extremely helpful, it is necessary to ask for help wisely. Through the communications, three aims need to be achieved:

  1. Form a positive impression on the mentors and admins: Ask precise questions (and don’t hesitate to ask them), ask for help if you don’t understand something but do your homework before asking. For instance, I was asked to review a tiny patch and I didn’t know what review entailed. Sage documentation has a Reviewer’s Checklist and I tried to follow that and asked questions when I didn’t understand something from there.
  2. Make a small contribution(s) to the code: Ask for tickets related to the project you are applying for since that will not only help you understand the development process better, but also the module itself. Ideally, I’ve found that a review of one ticket and writing another new ticket on an associated module can suffice.
  3. Understand and further define the project: Mentors have usually given the project more thought and therefore it is a good idea to talk to them and get an idea about what they have in mind for it first. What is not available, is an exact statement on what all needs to be added and how. Ask for reading material, get clarity on the various modules that need to be implemented as part of the project and come up with a plan on what needs to be done to achieve that.

3) Writing a GSoC Proposal

A good proposal cannot be prepared without a proper understanding of the organization and the project idea itself. And simply having a good understanding is not enough, if that is not visible through the proposal. There is no right way of preparing a proposal. The best way is to go over as many of them as you can find and then suitably adapting elements from each to suit the particular project in question. Here’s mine for what it’s worth: Rank-Metric Codes in Sage

There’s plenty of other advice on how to write a good proposal available; the recurring points being concise writing, clarity on project deliverables, structured timeline and review from mentors.