Sunday, January 20, 2019

Syntax for composition of functions

Whenever I see function composition in a new context, I make sure to look up its precise definition.  There is a choice that must be made in the definition that has always seemed arbitrary to me...at least until now.  I no longer think the choice is completely arbitrary, and I have an opinion about which choice is better.

The choice that I am referring to is about the order in which the two functions being composed appear next to the composition operator (which I find is always an infix operator).  Typically when defining function composition, the names given to the two function being composed are f and g.  Since I am trying to contrast two possible orderings, I don't want the implied alphabetic ordering between f and g to introduce bias.  So instead, I will use the symbols # and & to denote the two functions being composed.

For a set S, suppose # : S -> S and & : S -> S are two unary functions from S to S (i.e. they are endofunctions).  Furthermore, let's have the function composition operator be implicit, which just means that #& is a composition of these two functions.  The ambiguity is this: does #& mean that # is evaluated first and then & or is it the other way around?  More specifically, is the composition operator defined so that #&(s) = &(#(s)) or is it defined so that #&(s) = #(&(s))?

In my experience with mathematics, I have seen it defined both ways.  If I try to mentally convert my experiences to statistics, the anecdotal conclusion I reach is that I have seen it defined each way about half the time.  That is one reason why the choice seemed arbitrary to me.  If there was an overall advantage with one definition, I would expect to see more of a consensus.

The other reason that this choice seemed arbitrary to me is that I could think of exactly one argument in favor of each definition, and these two arguments seemed about equally strong to me.

The advantage of #&(s) = &(#(s)) is that the order in which the functions are evaluated is the order in which they appear in the composition syntax.  Technically, this latter ordering depends on the implicit assumption that we are encountering this notation in the context of a natural language like English where the implied ordering is left-to-right (and then top-to-bottom).

On the other hand, the advantage of #&(s) = #(&(s)) is that when expanding the left side into the right side, the order in which the functions appear does not need to change.

So until recently, I assumed that the first definition was likely used more often in situations that involved more functions being composed while the second definition was used more in situations that involved more functions being decomposed in order to evaluate them both one at a time.

But now I think the first choice of #&(s) = &(#(s)) is superior.

To explain why, let's start with just a single function f.  It is very common to see the evaluation of f on an input x written as f(x).  Sometimes the input to f is not a single value like x but an expression like a + b as in f(a + b).  In this case, a + b is computed first then f is evaluated on the resulting value.  But this means that the computation is not occurring in order implied by English: the computation is happening from right-to-left, but we read this expression from left-to-right.

The placement of the function (or operator) f before its input x as in f(x) is called prefix notation.  If f appears after its input x as in (x)f then it is called postfix notation.  If we were using postfix notation for function application (and kept using an implicit infix notation for function composition), then the two potential definitions for function composition would be (s)#& = ((s)#)& and (s)#& = ((s)&)#.  Now (s)#& = ((s)#)& is the obvious winner.  It has both of the advantages that we pointed out before (namely, the functions appear in the "English" left-to-right order in which they are evaluated and the order of the functions is unchanged when decomposing the composition) leaving no advantages for the other definition.

With this in mind, I can rephrase the advantage that preserves the syntactic ordering when decomposing.  A single function is written with its input using prefix notation.  So to define function composition as #&(s) = #(&(s)) is to be more consistent with the prefix notation for function evaluation.  I have to admit, that is a very convincing reason to go with this definition.

When I design a software application, I try break up the problem into several loosely coupled pieces.  One reason for this is to help isolate any bad choices.  In this case, I am suggesting that using prefix notation for function evaluation was a bad choice.  As such, I don't want to feel obligated to perpetuate that bad choice into the definition of function composition as well.  Instead, I want to reconsider the advantages and disadvantages and give #&(s) = &(#(s)) a reasonable chance at being the chosen definition.

C# doesn't have a function composition operator.  It is easy to define an extension method to do this, but I haven't found it to be that useful.  Instead, I often use an extension method called Apply that acts as an infix operator taking a unary function on its right and the input to the unary function on its left.  If you squint so that Apply disappears, then this is a way to expression function application in C# using postfix notation.  Then instead of first composing two functions f and g and then evaluating the result on an input x, I use Apply twice by writing x.Apply(f).Apply(g).  Now the computation occurs in essentially the same ordering implicit in English, namely left-to-right.

This is very similar to the way pipelines are created in Unix.  As such, I find piped Unix commands natural to read (well...expect for the abundant use of acronyms).

Recall that Apply is a binary function and f and g are unary functions.  We can improve readability (by reducing the noise) with bit more work.  If we turn f and g in to extension methods (and capitalize them as is convention), then we can write x.F().G().  And now we can increases the expressiveness by passing in additional values to F and G.  This type of syntax is called method chaining and is used to create fluent interfaces.  In his book Functional Programming in C#, Enrico Buonanno recommends this style saying
The method chaining syntax...provides a more readable way of achieving function composition in C#.
[Section 5.1.2 on Page 104]
Notice that sometimes the method chaining is written with x, F, and G each on their own lines.  This is still consistent with the implicit ordering in English since we read top-to-bottom.

As a final example, consider the function composition operators $ and . in Haskell.  (These operators just vary in precedence.)  When writing code in Haskell that uses these operators, you will tend to write code that effectively executes in the "wrong" order, i.e. from right-to-left.  As an alternative, you can compose the functions in the opposite order using the >>> operator.

The ultimate goal here is to write readable code.  We often say things like "this code is readable" or "that code is not readable" as though readability is a binary condition.  In fact is in a continuum for each person and also varies between people.  What we all (well, many of us) have in common is fluency with a natural language like English that reads left-to-right and top-to-bottom.  By tapping into that common shared experience, we can design programming languages and write code that is more readable for all of us.

Saturday, January 19, 2019

Minimal and intuitive type parameter naming

I would like to suggest an alternative to the standard ways of naming type parameters when nothing is known about the types being identified.

In C#, type parameter names typically start with T and are written in PascalCase.  When nothing (or almost nothing) is known about the type identified by the type parameter, it is common to see the single letter T as the identifier.  When many type parameters show up and nothing is known about any of them, then I usually see one of two conventions for naming them.

One way is to stick with T as the first letter and simply append a number to distinguish it.  A good example of this is multi-parameter versions of Func.  The problem with this approach is that the initial T becomes noise.  When every type parameter in this densely packed space starts with T, this letter doesn't convey anything.  It is clear from context that we are dealing with type parameters, so the T becomes redundant information.  Syntactically, it is merely allowing the name to be a legal identifier; in this case, to start with a letter or underscore.  Removing each T results in a number, which is not a legal identifier.  The names for the variables of each type are equally bad.  In the Func example, they are named arg1, arg2, etc.  Another common naming convention for this is t1, t2, etc.

Another approach to this naming is to stick with single letters like T and then pick surrounding letters such as S, T, U, etc. or T, U, V, etc.  I like style better.  These single letter identifiers are getting closer to the essential need here, which is merely to distinguish themselves from each other.  The identifiers for the variables follow suit and are the lowercase equivalents.  Both this style and the previous one convey order: the previous one did so explicitly with numbers while this style does so more intuitively by using a subsequence of letter from the alphabet.  The downside with this convention though is that it can be difficult to remember where the sequence starts (is it at S or T?) as well as have a good intuition for how far along the sequence a particular letter is.

The approach that I prefer makes an additional improvement that removes the downsides of the previous approach.  Instead of starting with S or T, start with A.  If four type parameters are needed, then in this conversion, they would be A, B, C, and D.  Now suppose that you just glanced at the last type parameter without scanning though the whole list.  You would instantly know that there are four type parameters involved; no conscious mental effort is required.

Now that we have sufficiently defined these three type parameter naming conventions, let's give them identifiers of their own.  Let's call the first one the numeric convention, the second one the mid-alphabetic convention, and the last one the alphabetic convention.  (I just made these names up as I am writing this.  If these type parameter naming conventions have, well, conventional names, I would love to hear about that.)

Often there is one crucial difference among the type parameters: one is the return type and the rest are input types.  In the numeric convention, the return type is often called TResult.  In the other two conventions, I usually see the return type identified with R.  This leads to another advantage of the alphabetic convention over the mid-alphabetic convention.  If R is the return type, then there is some cognitive dissonance with seeing the inputs type names be letters that come after R in the alphabet.  Instead, when starting with A in the alphabetic convention, all of the input types names come before R in the alphabet (even in the case of 16 input type parameters that last name is the letter Q, which still leaves a gap of size one before R).

Here is an example of me standardizing a file to use the alphabetic type parameter naming convention.  In fact, I first encountered the alphabetic convention in that GitHub project, which is called language-ext.  The author Paul Louth has used multiple type parameter naming conventions while developing that project but currently prefers the alphabetic convention as well.

I am a strong advocate for the alphabetic convention over the other two.  It uses a minimal amount of characters to distinguish the types while also being intuitively clear by relaying on our deeply seeded memory of the alphabet.  I hope I see this convention used more often.

Tuesday, December 25, 2018

Data Neutrality

Persisting data is a double-edged sword.  The benefit is that the data continues to exist after power is lost.  The cost is that some space is consumed.  Luckily we live in the "Space Age" where storage space for data is dirt cheap.  Nevertheless, persisting data is still a side effect; it is an action that changes state.  As such, there must exist (at least in principle) a dual action to undo the effect.

When I review code, I want to be aware of all its side effects, and I check if there exists code to undo these side effects.  If an application automatically persists some data, it is not necessary that this application will eventually delete this data automatically, but if that is not the case, then I want it to be the case this application provides the user the ability to delete this data.

Consider collections of persisted data that can grow arbitrarily large.  A common example of this is an application's logs.  If an application will delete (automatically or manually) all such persisted data, then I consider this application "data neutral", which is a play on the phrase carbon neutral.  In this case, the only a constant amount of the application's data will never be deleted.  Otherwise, an application is data positive, which is a bad thing.  Eventually, such an application will consume all of its storage space, even if it began with lots of it.

Don't let your applications be data positive.  Ensure that they are data neutral.

Sunday, May 20, 2018

Troubleshooting "Not Sent. Tap to try again." error in Android Messages

I use Android Messages to send SMS messages on my phone.  Sometimes I have a problem sending a message to a specific person.  I can still send messages to others, and I can still receive messages from everyone.  When this happens, it says "Not Sent. Tap to try again." underneath the message (see an example screenshot) about 20 seconds after attempting to send the message.  Once this problem starts, it does not go away on its own.  It will always happen when trying to send a message from within the app as well as from the reply feature on the notification of a new incoming message from the specific person.  It will not happen if I tell the Google Assistant to send them a message to the specific person and then dictate that message.

Here is a good sequence of troubleshooting steps for this problem (which can also be found elsewhere).

  1. Restart phone
  2. Clear app cache
  3. Clear app data
  4. Uninstall then reinstall app
I have tried all of these troubleshooting steps, and none of them deleted my conversations.  They are probably backed up somewhere.

This problem has happened to me twice.  The first time, I think I solved it by uninstalling and reinstalling the app.  The second time, I know that restarting my phone didn't fix the problem.  What did fix it was both clearing the cache and clearing the data.  I didn't try just clearing the cache.  If I am so mildly unfortunate as to experience this problem again, then I should check if just clearing the cache suffices.

Thursday, March 3, 2016

My Intellectual Health

As my life continues to get fuller, time for myself continues to decrease.  Most recently, this has been the addition of my third child Nolan.  Of course I love him dearly, but that doesn't negate the fact that there is no free lunch.

With less time to myself, I have thought more about the various ways in which I spend my time and what purpose they serve.  Some of them are more selfish, while others fill me up so that I can continue to pour my life back into others.

Below, I have listed seven categories that consume my time.  The list is roughly sorted by the following criteria: (1) what keeps me alive and (2) decreasing order of how much time is spent in each category (and, getting rather meta, the order of the items in this list of length two is also intentional). Each item also includes two words to describe what my mind is like when I don't and do (respectively) get enough time for that item. After the list, I give examples from my life of something in each category.
  1. Time to eat (good) food
    1. Scale from distracted to focused
  2. Time to sleep (without interruptions)
    1. Scale from cloudy to clear
  3. Time to rest
    1. Scale from distant to near
  4. Time to learn
    1. Scale from stale to fresh
  5. Time to understand
    1. Scale from messy to organized
  6. Time to share knowledge
    1. Scale from full to empty
  7. Time to exercise
    1. Scale from dull to sharp
Examples:

1) I would hope that this category is self explanatory given that everyone spends a significant portion of their time eating as well.  But I promised examples, right?  I have been eating more salads lately, including making them at home.  My preferred salad has everything in it, and it is not uncommon for me to prepare the salad for 30 minutes (and then eat it in 15 minutes more).  A second, more selfish, example involves my kids.  When they ask for more food, I usually take one more bite of my food before getting up.  Those seconds preparing that bite were spent on me, not them.

2) Almost everyone sleeps, so this should be rather clear as well.  Nevertheless, on to the examples.  Sleeping at night really doesn't need any further explanation.  If I don't get enough sleep at night, I can take naps, both on accident and on purpose.  When I lay down to take a nap on purpose, I immensely prefer to not need to be awake again before I would naturally wake up, which can vary from one to three hours depending on how sleepy I am.  If I only have an hour to nap, I usually pass up the opportunity to nap.

3) By resting, I literally mean not moving, especially in a comfortable position.  Examples include sitting on the couch, sitting down or laying awake in bed, getting my hair cut, or getting a massage.  In contrast, driving a car doesn't count because it is either not long enough to count as not moving or too long to be considered a comfortable position.  Sitting at my desk doesn't count either, even though I rock one of the most ergonomic chairs.  In addition to relaxing my whole body, these activities are particularly important for my legs and feet, especially when I am getting little or interrupted sleep.

4) I always want to learn new things, but they don't have to be technical things.  Good examples that would also appeal to a broad audience are TED talks.  I often try to accomplish this while also spending time with Shannon.  For example, together, we have wanted many documentaries on Netflix, watched many episodes of Crash Course (especially World History 1 and 2), and reading books together (especially about food, like Salt Sugar FatThe Omnivore's Dilemma, and In Defense of Food).

5) It is not enough to merely take in new information and facts.  I have to process these inputs in order to understand concepts.  This is probably my favorite thing to do.  Unfortunately, it is not possible to just do this at any moment.  It is a timely matter that requires the right subject and ripe material for my current level of understanding.  I spent most of my PhD studies doing this; trying to deepen my understanding.  I was also spending time in this way when forming the idea for this blog post in my head.  I was obtaining a better understanding of myself.

6) The output here is much more than the facts and information that I learned.  Instead, it is the conclusion of the previous time spent understanding.  Google defines knowledge in part by saying "the theoretical or practical understanding of a subject".  Yes, exactly.  The writing of my research publications and the writing of this blog post are both examples of time spent in this way.

7) My favorite form of exercise is playing pickup basketball (not formally structured with referees and such...it slows the game down and causes people to takes things too seriously).  And since this item is last in my list, it shouldn't come as too big a shock to learn that I haven't played pickup basketball now since last summer.  The biggest reason for this is moving out of Madison, WI.  I had established friendships and gatherings where I could play every week.  Someday I will be at that stage again in my new home of Coon Rapids, MN.  In the meantime, my formal exercise has been limited to shoveling snow, picking up trash in my neighborhood, and a walk around the block the other day.

Now that I have spent the time for myself to write this, I'm ready to go pour into other lives again.

Monday, August 18, 2014

Scanning to OCRed PDF in Ubuntu

When I want to scan a document to PDF with OCRed text in Ubuntu, here is how I do it.

These steps are a modification of what I found here (which refer to [1]).
  1. Scanning
    1. I already owned a good scanner. Namely, Canon model (LiDe 210).
    2. I recommend cleaning the scanners glass bed before beginning. Any small "spots" that are removed now don't have to be removed later in post processing.
    3. I scan using the GUI XSane. The settings I used, as recommended by [1], are:
      1. Color: Gray
      2. DPI: 300 or 600 (low enough so your scanner doesn't pause while scanning)
      3. Gamma, brightness, and contrast: default enhancement values of (1,0,0)
      4. Save to TIFF: Type = TIFF
      5. 8-bit images: Preferences ==> Filetype ==> Reduce 16 bit image to 8 bit
      6. No compression: Preferences ==> Filetype ==> TIFF 8 bit image compression = no compression
  2. Post processing
    1. I use ScanTailor.  I recommend applying the same "Select Content" and "Margins" to all pages so that the content on each page is the correct location (modulo noise from scanning) and all pages have the same dimensions.  NOTE: The dimensions of these TIFF files will be the dimensions of the final PDF file.
  3. OCR
    1. I use tesseract.  Everyone says that tesseract dies a fantastic death if you are so bold as to pass it a file with extension "tiff" instead of one with "tif".  For later considerations, each page is OCRed individually (see below for explanation).  The OCR can take a long time, so the following command echos the name of the file currently being OCRed to give a show of progress.  Sometimes I have problems while OCRing individual files in this way.  It seems like tesseract randomly encounters problems.  Finally, the third or fourth execution of the following command was successful.  The command for this step is: for f in *.tif; do echo $f; tesseract $f $f -l eng hocr; done
    2. I use hocr2pdf to pair the OCRed data with the text image and create a PDF, all at the same time.  It seems that hocr2pdf cannot handle multi-page TIFF files, so each page is handled individually using a for loop (like above).
      1. Installation of hocr2pdf is achieved by installing exactimage: sudo apt-get install exactimage.
      2. The command for this step is: for f in *.tif; do hocr2pdf -i $f -o $f.pdf < $f.html; done
  4. Merge
    1. I use pdftk.  The command for this step is: pdftk *.pdf cat output merged.pdf
  5. Edit metadata
    1. The command to get the current metadata is: pdftk merged.pdf dump_data output metadata.txt
    2. Some of the valid keys can be found here.
    3. The command to save the modified metadata is: pdftk merged.pdf update_info metadata.txt output merged2.pdf
    4. Lastly, one might want to edit the page labels.  However, I was not happy with any of the Ubuntu solutions for this, so I used Adobe Acrobat Pro 9 to do this instead.

Saturday, December 22, 2012

Snow Adventures 2012

In 2009, we had a snow storm in Wisconsin that canceled classes. I reported about the snow adventures  I had that day.  In 2010, there was another big snow storm, but I must not have had anything to share about it.  The winter of 2011 was very mild.  Whatever snow fell would melt in a few days.

Now its 2012 and we had a really big snow storm (and apparently we are naming winter storms now and this one was called Draco).  The storm hit on Thursday during the middle of finals week.  The university canceled finals that day, but announced that finals were on for Friday.  I think the university got ahead of itself here because they made this announcement before the Madison bus system announced that it was not operating on Friday.  The university provost sent an email to the entire university both confirming that finals were still on and suggesting that students that normally require bus transportation to campus could call one of the four cab companies in town.

Shannon had Thursday off as well but went back to work on Friday.  I followed her outside 8:00 to make sure she could get our Prius out of our underground garage and onto the city streets safely.  She made it out of the garage ok (the key is not to chicken out by slowing down) but had to wait in the parking lot behind someone who got stuck.  I helped this person get unstuck.  It was only the first.

Behind Shannon was another person that got stuck coming out of the underground garage of the neighboring apartment building.  After this person, someone else got stuck in the same place as the first.  At this point, it was 8:30 and I went inside to rest and warm up.  Then at 8:45, I went back out to see if there was anyone else I could help.  I walked around our apartment complex several times and helped seven people in total that day.

In the middle of one parking lot was a car that had apparently been left there over night.  The picture below shows this car after we dug much of it out (someone that I had just helped get unstuck decided to help me).


On the inside of the left rear window was a note with the owners name, address, and phone number.  (I thought I had a closeup of the window and the message, but alas.)  That is a really good idea!  He didn't answer my call, but this other guy with me lived in his building and must have notified him because his car was gone during my next trip around our complex.

On Wednesday night, I had parked our Oldsmobile facing our garage door so that I could easily bring the car inside to warm up and have the snow melt off.


The reason that so many cars were stuck in our parking lots is that the people responsible for removing the snow got very far behind.  One of our maintenance workers that was also out and about said they were either getting suck themselves or their equipment was breaking.  I didn't bother removing the snow in front of our Oldsmobile in the hopes that they would clear out the rest of the snow that night.

No dice.  It only took about 20 minutes to dig it out.  Here is my car in our garage:





As you can see, I only cleared off the bare minimum of snow to get my car into the garage.  Furthermore, I only dug an Oldsmobile-size hole out of the drift in front of the car.



Here's to not having to do this again for another year.