The column mainly describes the topic on how to write a correct program.

Writing a program
On writing programs, it illustrates a top-down way: write high-level descriptive (declarative) p-code; and then for each p-code statement, break it into next level with more details; continue the process until the program is composed.

While top-down way in general is effective especially when you are solving algorithm problems where problem can be clearly defined (at some level…). Paul Graham and other lisp hackers usually like to mention the way bottom-up. IMHO, the bottom-up way, is generally applied in cases where the problem you try to solve is too big (like for example, design a CAD software) and unclear at some point. For such kind of problems, it is hard to grasp or define the problem clearly. The bottom-up will start by exploring problem domain, defining domain primitives and ‘buzzword’ (like to to rotate a line, then you discovered there will be strong need on matrix calculation features), helping you to capture and really understand the domain, and then finally solve the problem while defining / discovering it (meaning, define a IT solution for given business requirement, mostly described by business / domain people).

That went too far so I’ll stop here…

Validate a program
Mostly it’s bottom up and is based on assertions on invariants. According to different program structures, the invariants vary. Like typically for a loop structure, the invariants can be divided into – init, preserve and termination. For a function, (contract-based) it is more on input params and return values (output params). Anyway, words do not mean anything so I’ll just give an example of an incorrect program where the error is actually caused because function invariable is not maintained. It’s a simple recursive based binary search.

def prog_2_A_binary_search_recur_incorrect(l, a):
    # termination
    if len(l) == 0:
        return -1
    # binary search
    mid = (len(l) - 1) >> 1
    mid_val = l[mid]
    if a > mid_val:
        return prog_2_A_binary_search_recur(l[mid + 1 : ], a)
    elif a == mid_val:
        return mid
    else:
        return prog_2_A_binary_search_recur(l[ : mid], a)

The error is “mid” is actually related to current input l related to current recursive level, not the original l. So the fix is to add a ‘ref’ in there and maintain the offset like:

def prog_2_A_binary_search_recur(l, a, ref = 0):
    """
    >>> l = [1,20,34,45,76,87,90,100,103,298,500]
    >>> print(prog_2_A_binary_search_recur(l, 298))
    9
    >>> print(prog_2_A_binary_search_recur(l, 999))
    -1
    """
    # termination
    if len(l) == 0:
        return -1
    # binary search
    mid = (len(l) - 1) >> 1
    mid_val = l[mid]
    if a > mid_val:
        return prog_2_A_binary_search_recur(l[mid + 1 : ], a, ref + mid + 1)
    elif a == mid_val:
        return ref + mid
    else:
        return prog_2_A_binary_search_recur(l[ : mid], a, ref)