starchy thoughts

I gave a tech talk on web and mobile accessibility during my internship this summer. Hopefully the slides will help people who want to learn more about a11y, or are also giving a presentation.

I did demos using VoiceOver showing the differences between good and bad websites (see examples in the slide notes). I didn’t have enough time, but the same can be done with mobile apps using VoiceOver or TalkBack on iPhone and Android. Hopefully the Windows phone will get a screen reader in the near future.

Some important links:

• Web Content Accessibility Guidelines (WCAG) 2.0
• Apple Accessibility Resources
• Google Accessibility Resources

Some tools for testing accessibility:

• Vischeck, which simulates colorblindness
• Fangs, a Firefox add-on that emulates a screen reader
• Web Accessibility Evaluation Tool (WAVE), which also has a nice Firefox toolbar add-on
• Also see WebAIM’s list of web evaluation tools
• Apple’s Accessibility Inspector
• Using your website or app with accessibility technology yourself!

Accessible design is universal design. Designing for accessibility shouldn’t be limiting. It should help you focus on what’s really important – what’s the main goal of your product, and how can users achieve this goal?

We’ve made some great changes in the physical world to promote accessibility. The virtual world should be just as accessible.

A good overview of Android is in this lecture by Yoni Rabkin, which explains the different parts of an app.

• An Intent is a description of an operation. It conveys requests between all different components of the system; an important thing intents do is launch Activities.
• An Activity is a single, focused thing that a user can do. It presents a visual user interface for a single task.
• One activity calls another activity (stack).
• A Fragment is a piece of the interface or behavior that can be placed in an Activity.
• A View is a basic component of the user interface, responsible for drawing and event handling. It defines the visual content of an Activity.
• A Service runs in the background for an indefinite period of time. It’s like an Activity without a UI.
• A BroadcastReceiver broadcasts and reacts to intents sent by sentBroadcast().
• A ContentProvider makes data available to other applications.

Layouts are determined by .xml files in the res directory.

Android documentation is super helpful, especially the Application Fundamentals. Eclipse is actually pretty easy to set up, and worth it when you’re doing a lot of Java programming (alt+shift+R to the rescue!).

I finally bought a new laptop! A 13-inch Macbook Air*.

I previously had a HP tx2000 tablet PC**. It lasted me nearly four years, with a motherboard replacement after 2.5 years. :/ (The model has major heat issues.)

I had made a list of software I had installed; I figure I should update it for Mac.

I mapped the Caps Lock to the Apple key and now I am happy. :) Here’s everything I have installed now:

• Alfred
• Arduino
• Chrome
• Dropbox
• Eclipse
• Evernote
• Firefox
• Git
• Homebrew
• Illustrator
• JDK
• Keynote
• LaTeX
• Microsoft Office
• Paintbrush
• Processing
• Pencil (animation)
• Pencil (mockup)
• Photoshop
• Python
• Skype
• Sublime Text
• Xcode

* 256GB SSD, 8GB RAM, 2.0GHz Intel Core i7 running Mountain Lion
** 300GB HDD, 4GB RAM, AMD Turion X2 Dual-Core Mobile RM-72 2.10GHz running Windows Vista Home Premium

First, what’s pass by value and what’s pass by reference? This Stack Overflow answer sums it up quite nicely:

• Pass by reference is like sharing an URL. If you and I both have the URL, we’re viewing the same web page. If changes are made to the page, we both see it. If you delete your URL, the page is still there.
• Pass by value is like having a printout of the page. If changes are made to the original web page, you can’t see it. If you make changes to the printout, the original doesn’t change. If you destroy your printout, the page is still there.

I came by this question because I’m doing some Android programming. I wanted to store a reference (which, in Java, is really just a pointer to an object) to a button to access later; however, I would be left with a dangling pointer if the Activity containing the button is destroyed! Anyways, this somehow devolved into finding out more about Java, and that it’s pass by value.

A swap function is the simplest test for whether a language is pass by value or pass by reference.

So for Java…

public class PassByValue {

    static void swap(int a, int b) {
        int temp = a;
        a = b;
        b = temp;
    }

    public static void main(String[] args) {
        int var1 = 1, var2 = 2;
        System.out.println("Before swap:");
        System.out.println("var1 = " + var1);
        System.out.println("var2 = " + var2); 
        swap(var1, var2);
        System.out.println("After swap:");
        System.out.println("var1 = " + var1);
        System.out.println("var2 = " + var2);  
    }
}

Before swap:
var1 = 1
var2 = 2
After swap:
var1 = 1
var2 = 2

That’s what we expected, since Java is pass by value.

To have a valid swap method in Java, the variables you want swapped must be in a class. Then your method would take in the class references as its arguments. This still isn’t pass by reference, though - it’s passing the references by value.

What about Python?

def swap(a, b):
    temp = a
    a = b
    b = temp

var1 = 1
var2 = 2
print "Before swap:"
print "var1 =", var1
print "var2 =", var2
swap(var1, var2)
print "After swap:"
print "var1 =", var1
print "var2 =", var2

Before swap:
var1 = 1
var2 = 2
After swap:
var1 = 1
var2 = 2

Python is also pass by value! But hmm…

def swap(a, b):
    temp = a[0]
    a[0] = b[0]
    b[0] = temp

var1 = [1] var2 = [2] print "Before swap:"
print "var1 =", var1
print "var2 =", var2
swap(var1, var2)
print "After swap:"
print "var1 =", var1
print "var2 =", var2

Before swap:
var1 = [1]
var2 = [2]
After swap:
var1 = [2]
var2 = [1]

Yeah, Python is still pass by value. It’s like Java, though, in that it has object references. Everything in Python is an object; however, objects can be mutable or immutable. Lists are mutable, so they can changed in place.

Fortran is pass by reference, C is pass by value (though you can imitate pass by reference through pointers), C++ is both, etc. Fun stuff!

I’m thinking of getting a new laptop, so I compiled a list of all software on my current computer (Windows Vista).

• Arduino
• AutoHotKey
• Chrome
  • Pocket
  • Tab Scissors
  • Tab Glue
  • WhatFont
  • ZhongWen
• Corel Painter Essentials
• Cygwin
• Dropbox
• Evernote
• Firefox
  • Firebug
  • Firefinder
  • WAVE Toolbar
• Git and GitHub
• Inkscape
• LaTeX
• Microsoft Office
• Perky Duck
• Processing
• Pencil (animation)
• Pencil (mockup)
• Putty
• PuttyTabs
• Python
  • easy_install
  • pip
• Skype
• Sublime Text

Question of the Day! Count ALL the calories.
(06.19.12)

The Calorie unit on most food packages is actually a kilocalorie. A calorie is a unit used to measure energy - specifically, the amount of energy needed to raise one kilogram of water by one degree Celsius.

The original method to measure the number of kcals in food directly measured the energy it produced by placing it in a bomb calorimeter (a sealed container surrounded by water), burning it completely, and measuring the rise in water temperature.

Nowadays, most calorie values are estimated using the Atwater system, which calculates the calories provided by energy-containing nutrients in the food: protein, carbohydrates, fats, and alcohol. Since fiber is not digested and utilized by the body, the fiber component of foods is usually subtracted from the total amount of carbohydrates.

The Atwater system uses 4 kcal/g for protein, 4 kcal/g for carbohydrates, 9 kcal/g for fats, and 7 kcal/g for alcohol. These numbers were originally obtained by the bomb calorimeter method.

(Source: scientificamerican.com)

This is a really interesting talk, given by Felix von Leitner at the 2009 Linux-Kongress. It has great examples and tests, using various versions of gcc, icc, llvm, suncc, and msvc.

The main points are 1) optimization is important, 2) readable code is often more important, and 3) know how your compiler optimizes code, and let it optimize.

Some definitions:

• out-of-order superscalar execution - out-of-order execution is where the processor executes instructions based on the availability of data rather than the original order in the program; a superscalar processor executes more than one instruction per clock cycle by simultaneously dispatching instructions to multiple execution units (instruction level parallelism).
• register renaming - changing the name of some registers to decrease the need for serialization of program operations imposed by the reuse of registers by those operations.
• cache associativity - associativity deals with the number of places a particular entry can be mapped to. A direct mapped cache means an entry has only one place in the cache it maps to, a two-way set associative cache means an entry has two places it can map to, etc. Caches with more associativity have a lower cache miss rate, but it takes longer to check whether an entry is in the cache or not.
• strength reduction - a compiler optimization where expensive operations are replaced with equivalent and less expensive operations (e.g. bit shift for multiplcation)
• tail recursion - when a subroutine call happens inside another procedure as its final action (i.e. the call site is at the tail position)

Some C stuff:

• #define - uses the C preprocessor; the compiler doesn’t see it, so it’s not visible in the debugger. Basically a “find and replace.”
• const - declares something as unmodifiable; it cannot be assigned to after it’s initialized. Visible in the debugger, but it takes up memory (unless static is used).
• static - allows a variable inside a function to keep its value between calls, and allows global variables to be “seen” in only the compilation unit it’s declared in. (Using it to keep state between function calls is not thread-safe!)
• enum - a way to map identifiers to integer values. Visible in the debugger and uses no memory.
• volatile - tells the compiler not to optimize anything that has to do with a variable. Usually, a compiler caches variables in registers for optimization purposes.

Now for optimization!

1. Inlining
   
   • the compiler will usually inline
   • destroys code locality
   • make helper functions static
   • difference between gcc and C99
2. Range Checks
   
   • compilers optimize away superfluous checks
   • CSE (common subexpression elimination) eliminates duplication
   • invariant hoisting moves loop-invariant checks out of the loop
3. Dead Code
   
   • the compiler and linker can sometimes remove
   • …unreachable code
   • …a static function that is never used
   • …whole .o/.obj files that are not referenced
4. Pre- vs. Post-Increment
   
   • use ++a instead of a++, since 
   • this rarely matters today (useful in the 90’s)
5. Fancy-Schmancy Algorithms
   
   • use a list for 10-100 elements 
   • fancy data structures help on paper, but rarely in reality
   • more space overhead for the structure means less L2 cache left for data
   • if you manage a million elements, use a proper data structure
   • if you can’t explain it on a beer coaster, it’s too complex
6. Memory Hierarchy
   
   • important optimization goal these days! 
   • use multiplication instead of shifting costs five cycles
   • conditional branch misprediction costs ten cycles
   • cache miss to main memory costs 250 cycles
7. Pre- vs. Post-Increment
   
   • use ++a instead of a++, since 
   • this rarely matters today (useful in the 90’s)

In short - if you do an optimization, test it on real world data. If it’s not drastically faster and makes the code less readable, don’t use it.

Question of the Day! Unroll ALL the loops.
(06.18.12)

Loop unrolling is a form of loop optimization. It increases a program’s execution speed by reducing loop overhead (instructions that perform loop control and access), and control hazards and stalls (the need to wait until a branch is computed and resolved). This is usually done by an optimizing compiler, but you can manually unroll loops as well.

An interesting and notable implementation of loop unrolling is Duff’s device, discovered by Tom Duff in 1983, which takes advantage of fall-through in a switch statement. It lowers the number of branches a serial copy has to make by assigning up to eight values in one iteration.

Manual unrolling loops is uncommon these days. There’s a space-time tradeoff, and the compiler usually unrolls loops for optimization anyways. However, it does make sense when you can break dependency chains. An out-of-order CPU can perform other calculations, even when one of the branches has stalled.

Watched Thomas Wouter’s Google talk on Python today. The pace was pretty fast for me, but it’s a good video. I went back and reviewed a couple things to make sure I understood it.

Here’s the first snippet of code he gave:

def func(arg1, arg2=Foo()):
    print "Entering func"
    def inner_func(arg3=arg2):
        print "Entering inner_func"
        return arg1, arg3
    arg1 = arg2 = None
    return inner_func


And here it is with my added comments:

def Foo():
    return "Foo()"

def func(arg1, arg2=Foo()):
    print "Entering func"
    print "arg1 =", arg1, "; arg2 =", arg2
    def inner_func(arg3=arg2):
        print "\nEntering inner_func"
        print "arg1 =", arg1, "; arg3 =", arg3
        return arg1, arg3
    print "arg1 is still", arg1, "and arg2 is still", arg2
    arg1 = arg2 = None
    print "arg1 =", arg1, "; arg2 =", arg2
    return inner_func


print 'Calling f = func("hello")'
f = func("hello")

a, b = f()
print "f() returns", a, "and", b

arg1 = "good"
c, d = f(arg3="bye")
print 'f(arg3="bye") returns", c, "and", d 

Which outputs:

Calling f = func("hello")
Entering func
arg1 = hello ; arg2 = Foo()
arg1 is still hello and arg2 is still Foo()
arg1 = None ; arg2 = None

Entering inner_func
arg1 = None ; arg3 = Foo()
f() returns None and Foo()

Entering inner_func
arg1 = None ; arg3 = bye
f(arg3="whoa") returns None and bye

This shows some important aspects of Python, notably that everything is runtime, executed top-to-bottom. def and class define functions at runtime. Function code is compiled into a “code object”, then wrapped in a function object when def is executed.

In my example, Foo() is another function, so when def func(arg1, arg2=Foo()) is executed, Foo() is evaluated and gets assigned to arg2.

When func is called, inner_func is created. The default for the arg3 argument is assigned arg2, which is currently "Foo()".

arg1 and arg2 are then reassigned. This shows nested scopes pretty nicely - although both of them were changed, only arg1 will be None.

Execution happens in namespaces (which are dicts) - modules, functions, and classes all have their own namespaces.

Method A. Perforin and granzymes

1. T_CTL binds to the target cell due to class I MHC interaction as well as other adhesion proteins.
2. T_CTL release perforin by fusion of membrane vesicles with the cell membrane of the infected cell.
3. Perforin generates a pore in the target cell, allowing entry of granzymes (a class of proteases).
4. Proteolytic action of granzymes induce apoptosis in the target cell.

Method B. Fas L and Fas

1. Fas L on the surface of T_CTL binds to the Fas ligand on the infected cell.
2. Trimerizaion of Fas on the target cell results in activation of the proteolytic signaling pathway.
3. Target cells dies from apoptosis.

These methods differ in terms of the recognition process. NK cells kill in these manners as well.

• Produced in the bone marrow, mature in the thymus. T-cells that recognize host peptides are killed - only those that recognize foreign peptides in complex with self MHC are allowed to leave the thymus.
• Surface T-cell receptor recognizes, with high specificity, a foreign peptide on a host MHC. Specificity applies to both the peptide and the MHC.
• Each T-cell has a homogenous population of TCRs on their surface, but diversity in an individual is around 10¹². Diversity in the population is low.
• Activation of T-cells leads to expansion of a specific T-cell population and generates memory T-cells for both types of T-cells (clonal selection).

T-helper cells (T_H) [CD4⁺].
Recognize a self MHC-II in complex with a foreign peptide on APCs (antigen presenting cells), leading to activation of the T_H cell. Activation causes the release of cytokines that activate B-cells, macrophages, and T_C cells.

Cytotoxic T-cells (T_C) [CD8⁺].
Recognize a self MHC-I in complex with a foreign peptide on any cell, leading to the formation of a cytotoxic T lymphocyte (T_CTL). T_CTL cells kill cells presenting foreign antigens.

Development of Acquired Cellular Immunity.

1. T_C cells recognize foreign peptides present on class-I MHCs (since they are CD8⁺). These peptides arose from viral replication, intracellular pathogens, or abnormal peptides in cancer cells. (Note: “normal” peptides are also displayed, but ignored by the immune system.)
2. T_C cells are activated
   • directly by APC cells by class-I MHC antigen presentation (usually by dendritic cells).
   • By T_H stimulation of APC cells, enhancing simulation of T_C cells by APC cells.
   • By cytokines released by activated T_H cells.
3. Activated T_C cells proliferate and develop in T_CTL cells.
4. Memory T_C cells are produced, which can be activated by interaction with the MHC-I and peptide alone, without T_H support.

• Mature in the bone marrow (or in the bursa for birds). Only B-cells that express an intact immunoglobulin that recognizes foreign molecules are allowed to leave the bone marrow. B-cells that recognize self are destroyed or non-functional.
• The BCR (B-cell receptor) binds foreign material (proteins, carbohydrates, etc.) via antibody component. These are highly specific interactions.
• All BCRs are identical on a single B-cell, but diversity is on the order of 10⁸ different B-cells in an individual. Diversity in the population is low (we all have pretty much the same antibodies).
• Activation leads to expansion of a specific B-cell population and generates plasma and memory cells. This is the basis of clonal selection theory.
• Activated B-cells produce memory B-cells.

MHCs are heterodimeric and membrane bound.

• Bind peptides with low specificity (length from 9-12 amino acid residues).
• Many different MHCs on one cell.
• Individuals have the same MHCs on all cells.
• Population is highly polymorphic, with many alleles.
• Both foreign and self peptides are presented indiscriminately.
• Only foreign peptides presented by self-MHC elicit an immune response.

Class I - MHC.
Found on all cells. The peptides presented are internally synthesized, and are recognized by TC cells (via CD8).

Class II - MHC.
Found on antigen-presenting cells (macrophages, dendritic cells, B-cells). The peptides presented are from outside the cell, via phagocytosis or receptor-mediated endocytosis.

For floating-point representations with a k-bit exponent and an n-bit fraction:

• +0.0 always has a bit representation of all zeros.
• The smallest positive denormalized value has a bit representation of a 1 in the least significant bit position and otherwise all zeros. It has a fraction and significand value M = f = 2-n and an exponent value E = -2^k-1 + 2. Its numeric value is V = 2^-n-2k-1+2.
• The largest denormalized value has a bit representation of an exponent field of all zeros and a fraction field of all ones. It has a fraction and significand value  M = f = 1 - 2^-n and an exponent value E = -2^k-1 + 2. Its numeric value is V = (1 - 2^-n) x 2^-2k-1+2, which is slightly smaller than the smallest normalized value.
• The smallest positive normalized value has a bit representation of a 1 in the least significant bit of the exponent field and otherwise all zeros. It has a significand value M = 1 and an exponent value E = -2^k-1 + 2. Its numeric value is V = 2^-2k-1+2.
• 1.0 has a bit representation with all but the most significant bit of the exponent field set to 1 and all other bits 0. Its significand value is M = 1 and an exponent value E = 0.
• The largest normalized value has a bit representation with the sign bit 0, the least significant bit of the exponent 0, and all other bits set to 1. It has a fraction value f = 1 - 2^-n, giving a significand M = 2 - 2^-n and an exponent value E = 2^k-1 - 1. Its numeric value is V = (1 - 2^-n-1) x 2^-2k-1.

(Source: csapp.cs.cmu.edu)