Software Development Reference

Contents

• Hash Functions
  • Cryptographic Hash Functions
    • SHA-1
• Booleans
• Numeral Systems
  • Positional Notation
  • Binary - Base 2
  • Octal - Base 8
  • Hexadecimal - Base 16
  • Conversions
• Powers of 2
• Powers of 10
• Units
  • Why 8 bits to a byte?
• Bit Shifting
• Encoding
  • ASCII
• Permission Bits
• Software Development Terminology
• Git Workflows
  • Fork and Pull / Integration Manager / Integrator
  • Centralized / Shared Repository
    • git-flow
    • GitHub Flow
  • Others
• Versioning
  • For Libraries
  • For Applications
  • Best Practices
  • Schemes
• Software Versioning Terminology
  • Additional Resources
• Code Review
  • Gerrit
    • Resources
• Networking
  • OSI Model
• Data Structures
  • Array
• Computational Complexity
• Algorithms
  • Graph Traversal
• FAQ
  • How to handle validating state?
  • What does the “rc” of files like .bashrc mean?

Hash Functions

h: 2n → 2k

Generally:

• 2 ^k/2 operations before seeing collision, due to birthday paradox

Non-exhaustive list of desirable properties, depending on the application:

• avalanche effect - where output changes significantly relative to input
• randomness - can we predict output?
• uniformity - for every possible value are there the same number of inputs?
• one-way function - easy to compute, hard to invert

Applications:

• verification:
  • file / data integrity
  • password
  • digital signature
• data identifier

Cryptographic Hash Functions

SHA-1

• fixed 160-bit (20 byte, 40 hex digits) message digest
• demonstrates good avalanche effect, where output changes significantly relative to input
• deprecated in 2017

$ echo -n 'hello world' | sha1sum
2aae6c35c94fcfb415dbe95f408b9ce91ee846ed  -

$ echo -n 'hello world!' | sha1sum
430ce34d020724ed75a196dfc2ad67c77772d169  -

Booleans

Beware! Unix command exit codes are:

Numeral Systems

Positional Notation

ijkradix ⇒ (i × radix2) + (j × radix1) + (k × radix0)

Binary - Base 2

1012 ⇒ (1 × 22) + (0 × 21) + (1 × 20)

Octal - Base 8

1018 ⇒ (1 × 82) + (0 × 81) + (1 × 80)

• 3-bit encoding

Hexadecimal - Base 16

10116 ⇒ (1 × 162) + (0 × 161) + (1 × 160)

• 4-bit encoding
• capitalization is by convention; it does not matter
• considered “binary shorthand” because of the ease in exchanging 4 bits for 1 hex digit
• “hexa” is Greek for “six”, “decimal” is derived from Latin; the etymology is confusing

Conversions

Powers of 2

Powers of 10

Units

Why 8 bits to a byte?

Convenience given that 8 is 2³ and history with 7-bit ascii.

Bit Shifting

For int-like types, left bit shifting by n multiplies the value by 2n :

10 << 1 # 10 * 2^1 = 20
10 << 2 # 10 * 2^2 = 40
10 << 3 # 10 * 2^3 = 80
10 << 4 # 10 * 2^4 = 160

Encoding

ASCII

• 7 bits wide, 8th can be used as parity bit
• American Standard Code for Information Interchange

Permission Bits

Selected common permissions:

Directory permissions have special meanings:

• read: user can read filenames
• write: user can [add,rename,delete] files if execute also set
• execute: user can enter directory and access files

This StackOverflow answer goes into more detail.

Software Development Terminology

abstraction

the separation of the use from the implementation

angle brackets

< >

backtick (diacritical mark term: grave accent)

^

braces (AKA “curly braces”, “curly brackets”, “moustache brackets”)

{ }

brackets (AKA “square brackets”)

[ ]

caret

the text cursor

caret (diacritical mark term: circumflex)

^

declarative programming

code style that expresses logic without specifying control flow

dynamic programming language

a programming language that defers certain programming behaviors until runtime; not to be confused with a dynamically typed language

functional programming

programs constructed by the application and composition of functions

imperative programming

code style that expresses desired changes in program state

paradigm

the classification of a programming language according to its features; e.g. “functional”

parens

( )

peek

return value at location; could be by index (e.g. an array) or by operation (e.g. via top on a stack)

robustness

the likelihood that small changes in a specification will require correspondingly small changes in the program

runtime configuration / feature flags

the ability to modify settings and behavior for live traffic and usage

static programming language

a programming language that performs certain programming behaviors at compilation time

stream

a sequence of data objects

telemetry

timing data

transpiler

a source-to-source converter; a type of compiler

Git Workflows

Fork and Pull / Integration Manager / Integrator

Contributors do not (necessarily) have commit access to a repository and instead fork it to create their own copy, work within that forked version, and communicate to the original repo’s maintainer (possibly through pull requests) that their forked repository’s branch has contributions ready for pulling and merging into the original repository.

Centralized / Shared Repository

Multiple contributors have commit access to a repository and work on clones of it.

git-flow

Useful for:

• aggregating multiple features into a single, testable, isolated release branch
• maintaining specific release versions
• unambiguous process steps

Consider alternatives if:

• git rebase is preferred

• a lightweight workflow is needed

• Authoritative:

  • A Successful git Branching Model by Vincent Driessen (nvie)
  • nvie/gitflow GitHub repo with git extensions implementing the branching model

• Perspectives:

  • Why aren't you using git-flow? | Hacker News (2010 August)
  • GitFlow considered harmful | Hacker News (2015 June)
  • That "git-flow” (2016 February)
  • What is wrong with “A successful Git branching model”? | Hacker News (2016 February)
  • Please stop recommending Git Flow! | Hacker News (2020 March)

GitHub Flow

Useful for:

• continuous deployment to production, like with a web app
• code review through GitHub’s Pull Requests

Consider alternatives if:

• specific releases must be maintained

• Authoritative:

  • Understanding the GitHub Flow
  • GitHub Flow

• Perspectives:

  • Git email flow vs Github flow | Hacker News (2021 March)

Others

• Git workflows - The Linux Kernel Archives
• GitLab Flow
• Comparing Workflows
• Git Feature Branch Workflow
• Trunk Based Development
• a simple git branching model (written in 2013)
• Patterns for Managing Source Code Branches
• Fossil vs Git | Hacker News

Versioning

For Libraries

Recognize:

• library versioning is about compatibility first, and new functionality second
• the main consumers are other software maintainers and package managers

Preferred versioning policy:

• use Semantic Versioning
• if you want to break backwards compatibility (e.g. increment the MAJOR version), create a new, differently named library instead
• avoid an automated determination and change of version; a human should be in the loop

Strive for:

• a publically declared versioning scheme
• a publically declared compatibility guarantee
• a unit test suite determining version compatibility
• a detailed CHANGELOG

For Applications

Recognize:

• application versioning may have many varying consumers:
  • end users
  • the organization that creates and maintains the application, which itself may be split into:
    • engineering interests
    • product interests
    • business interests
    • marketing interests
  • entities—which may be software themselves—that manage the application on behalf of the end users (e.g. an app store or an operating system)

Strive for:

• a context-appropriate scheme, like:
  • MAJOR.MINOR, where MAJOR increment indicates a major product change and MINOR indicates a minor product change or bugfix
  • Calendar Versioning, for when releases have a dependency or relationship to time
  • channel-based releases, like ALPHA or BETA
  • named releases
  • target-based versioning, like for operating systems (e.g. macOS-10.15) or other software

Best Practices

Recognize:

• Hyrum’s Law, which states: “With a sufficient number of users of an API, it does not matter what you promise in the contract: all observable behaviors of your system will be depended on by somebody.”
• the human consumer:
  • comparing two integers for which is larger is straightforward
  • “Spring 2021” means different things to a United States vs. an Australian audience
  • some may view the next logical sequence member of 2.8, 2.9, ?? to be 3.0, not 2.10

Strive for:

• a versioning policy reflective of use and context
• making a human ultimately responsible for the version change decision; being informed by automated processes, like passing a test suite, is encouraged
• committing version metadata to source code
• automatically generating a build identifer using SCM software (e.g. git describe --first-parent or git describe --tags) for easy reference

Consider:

• The One Version Rule

Schemes

Software Versioning Terminology

bug-for-bug compatibility

preserving aberrant behavior in new implementations to not disrupt compatibility with consumers

dependency hell

the frustration from problems involved in managing software dependencies; Dependency hell Wikipedia article

diamond dependency

a problem where two dependencies have sub-dependency version conflicts

evergreen software

constantly updated software, possibly without user control

transitive dependency

a sub-dependency not directly referenced or used by the grandparent

upgrade cliff

releasing beta or early access APIs to versions so that libraries can support multiple versions

Additional Resources

• Spec-ulation Keynote - Rich Hickey
• The Principles of Versioning in Go
• CppCon 2017: Titus Winters “C++ as a "Live at Head" Language”

Code Review

Gerrit

Resources

• Gerrit Code Review
• openstack/nova code review
• OpenDev Developer’s Guide using a gerrit-based development and review workflow
• Abandoning Gitflow and GitHub in favour of Gerrit | Hacker News (2016)

Networking

OSI Model

OSI Model Wikipedia article

Data Structures

Array

For dynamic (growable) arrays:

Computational Complexity

Algorithms

Graph Traversal

FAQ

How to handle validating state?

Scenario:

An object exists, and its state is valid. An object is modified, is its state valid?

The questions arise:

• should proposed state changes be validated in the modification method?
• if they are validated in the modification method, how could we really know if the object would have been invalid, were it given a chance to assume the new state?
• if they validated after modification, why is the object allowed to exist in an invalid state?
• how does the logic for what constitutes validity be used in all appropriate cases?
• how to handle atomic updates where multiple components of state may be modified at once? and if updated individually would constitute an invalid state?

This leads to an alternative path:

Create an immutable object which validates its state on construction, failing to create the object if invalid.

What does the “rc” of files like .bashrc mean?

The “rc” suffix stands for “run commands”.