TIL: How to Design Programs, Raft Consensus Algorithm, DWIM Philosophy, and The Jargon File

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

;; Data Definition
;; A List-of-Numbers is one of:
;; - empty
;; - (cons Number List-of-Numbers)

;; Contract and Purpose
;; sum : List-of-Numbers -> Number  
;; Computes the sum of all numbers in the list

;; Examples
;; (sum empty) should produce 0
;; (sum (cons 3 (cons 7 empty))) should produce 10

;; Template (follows the data structure)
(define (sum lon)
  (cond
    [(empty? lon) ...]
    [(cons? lon) (... (first lon) ... (sum (rest lon)) ...)]))

;; Body (fill in the template)
(define (sum lon)
  (cond
    [(empty? lon) 0]
    [(cons? lon) (+ (first lon) (sum (rest lon)))]))

;; Testing
(check-expect (sum empty) 0)
(check-expect (sum (cons 3 (cons 7 empty))) 10)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

;; Binary Tree data definition
;; A BT is one of:
;; - 'leaf
;; - (make-node Number BT BT)

(define-struct node (value left right))

;; Template automatically follows data structure
(define (bt-template bt)
  (cond
    [(symbol? bt) ...]                          ; leaf case
    [(node? bt) (... (node-value bt)           ; node case
                     (bt-template (node-left bt))
                     (bt-template (node-right bt)))]))

;; Count nodes in binary tree
(define (count-nodes bt)
  (cond
    [(symbol? bt) 0]
    [(node? bt) (+ 1 
                   (count-nodes (node-left bt))
                   (count-nodes (node-right bt)))]))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

;; When structure doesn't follow data: generative recursion
;; Example: Collatz conjecture

;; collatz : Number -> Number
;; Counts steps to reach 1 in Collatz sequence
(define (collatz n)
  (cond
    [(= n 1) 0]
    [(even? n) (+ 1 (collatz (/ n 2)))]
    [else (+ 1 (collatz (+ (* 3 n) 1)))]))

;; Need termination argument since structure doesn't follow input

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# HtDP principles in Python

from typing import List, Union
from dataclasses import dataclass

# Data Definition
@dataclass
class Empty:
    pass

@dataclass  
class Node:
    value: int
    rest: Union['Node', Empty]

ListOfInts = Union[Node, Empty]

# Contract and Purpose
def sum_list(lst: ListOfInts) -> int:
    """Computes the sum of all integers in the list."""
    
    # Examples (as doctests)
    """
    >>> sum_list(Empty())
    0
    >>> sum_list(Node(3, Node(7, Empty())))
    10
    """
    
    # Template follows data structure
    if isinstance(lst, Empty):
        return 0
    elif isinstance(lst, Node):
        return lst.value + sum_list(lst.rest)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

# Pseudo-code for election logic
class RaftServer:
    def __init__(self):
        self.state = "follower"
        self.current_term = 0
        self.voted_for = None
        self.log = []
        self.election_timeout = random_timeout()
    
    def start_election(self):
        self.state = "candidate"
        self.current_term += 1
        self.voted_for = self.server_id
        votes_received = 1  # Vote for self
        
        for server in other_servers:
            vote_granted = server.request_vote(
                term=self.current_term,
                candidate_id=self.server_id,
                last_log_index=len(self.log) - 1,
                last_log_term=self.log[-1].term if self.log else 0
            )
            if vote_granted:
                votes_received += 1
        
        if votes_received > len(all_servers) // 2:
            self.become_leader()
        else:
            self.become_follower()
    
    def request_vote(self, term, candidate_id, last_log_index, last_log_term):
        # Only vote if:
        # 1. Haven't voted in this term, or voted for this candidate
        # 2. Candidate's log is at least as up-to-date as ours
        if (term > self.current_term and 
            (self.voted_for is None or self.voted_for == candidate_id) and
            self.log_is_up_to_date(last_log_index, last_log_term)):
            self.voted_for = candidate_id
            self.current_term = term
            return True
        return False

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class LogEntry:
    def __init__(self, term, command):
        self.term = term
        self.command = command

class RaftLeader:
    def replicate_entry(self, command):
        # Append to local log
        entry = LogEntry(self.current_term, command)
        self.log.append(entry)
        
        # Send to followers
        responses = []
        for follower in self.followers:
            response = follower.append_entries(
                term=self.current_term,
                leader_id=self.server_id,
                prev_log_index=len(self.log) - 2,
                prev_log_term=self.log[-2].term if len(self.log) > 1 else 0,
                entries=[entry],
                leader_commit=self.commit_index
            )
            responses.append(response)
        
        # Check for majority
        success_count = sum(1 for r in responses if r.success) + 1  # +1 for leader
        if success_count > len(self.all_servers) // 2:
            self.commit_index = len(self.log) - 1
            return True
        return False

1
2
3
4
5
6
7
8
9

;; Original DWIM in LISP
;; If user types (CAR X Y) instead of (CAR (X Y))
;; System might auto-correct to intended meaning

;; But ambiguity arises:
(SETQ FOO (CAR X Y))  ; What did user mean?
;; Option 1: (SETQ FOO (CAR (X Y)))
;; Option 2: (SETQ FOO (CAR X) Y)  
;; Option 3: Syntax error

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

# Python's flexible type system
def add_items(items):
    # Works with lists, tuples, strings, etc.
    result = []
    for item in items:  # DWIM: iterate over any iterable
        result.append(item)
    return result

# Shell command completion
$ git co<TAB>     # Expands to 'git commit' or 'git checkout'
$ ls /us/lo<TAB>  # Expands to '/usr/local'

# URL autocomplete in browsers
"github.com/user/repo" → "https://github.com/user/repo"

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// JavaScript's type coercion (too much DWIM)
"5" + 3    // "53" (string concatenation)
"5" - 3    // 2 (numeric subtraction)  
[] + []    // "" (empty string)
[] + {}    // "[object Object]"
{} + []    // 0 (in some contexts)

// PHP's magic (inconsistent DWIM)
$array = [1, 2, 3];
echo $array;        // "Array" (not very helpful)
echo json_encode($array);  // "[1,2,3]" (more useful)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

# pandas DataFrame - good DWIM
import pandas as pd

df = pd.DataFrame({'A': [1, 2, 3], 'B': [4, 5, 6]})

# These all "do what you mean" intuitively:
df['A']           # Column access
df[0:2]           # Row slicing
df[df['A'] > 1]   # Boolean indexing
df['A'] + df['B'] # Element-wise addition

# Git - good DWIM examples
git add .              # Add all changed files
git commit -am "msg"   # Add all and commit
git push              # Push to tracked upstream branch
git checkout main     # Switch to main branch

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# Examples of hacker aesthetic values:

# Elegance - simple, clean solution
def factorial(n):
    return 1 if n <= 1 else n * factorial(n - 1)

# vs. verbose alternative
def factorial_verbose(n):
    if n < 0:
        raise ValueError("Negative input not allowed")
    if n == 0 or n == 1:
        return 1
    result = 1
    for i in range(2, n + 1):
        result = result * i
    return result

# Cleverness - non-obvious but brilliant
def reverse_bits(n):
    return int(bin(n)[2:].zfill(32)[::-1], 2)

# Orthogonality - tools that compose well  
# Unix philosophy: do one thing well
cat file.txt | grep "pattern" | sort | uniq -c | head -10