trip logs / gnuvola


Trip Log 2021-12-31 h08 -- Indices Style Upgrade Part 7

In this episode of the recently revived Indices Style Upgrade series, we pick up the pace and cover two patches (4 and 5).  This is because they are both “internal”, and relatively simple to analyze.  (Plus, we have a lot of exhaustive experience under our belts now, and can thus move w/ sure-footed ease going forward.) 

Unlike previous trip logs, this time you are encouraged to only briefly look at the accompanying tarball for patches 4 and 5.  In this case, the unified diff format is a bit difficult to understand.  Instead, let's look at the same information, presented in the context diff format

Here's an excerpt of patch 4, converted to context diff format, with convenient line numbers prefixed: 

 4	Subject: [PATCH 4/8] [tl-mkindex int] Add abstraction: sort/car
[...]
 9	* sub/tl-mkindex (sort/car): New proc.
10	(sort/car<): Use ‘sort/car’.
[...]
17	*** a/sub/tl-mkindex
18	--- b/sub/tl-mkindex
19	***************
20	*** 209,218 ****
21	                                    (list txt)))))
22	              url txt)))
23
24	! (define (sort/car< ls)
25	    (sort ls (lambda (a b)
26	!              (string<? (car a)
27	!                        (car b)))))
28
29	  (define (consult-db upath-ignored where-clause)
30
31	--- 209,221 ----
32	                                    (list txt)))))
33	              url txt)))
34
35	! (define (sort/car bef ls)
36	    (sort ls (lambda (a b)
37	!              (bef (car a)
38	!                   (car b)))))
39	!
40	! (define (sort/car< ls)
41	!   (sort/car string<? ls))
42
43	  (define (consult-db upath-ignored where-clause)
44
45	--

There is only one hunk, between lines 20 and 45, and it shows the code before (lines 20-31) and after (lines 31-45) the change.  Pretty straightforward, right?  It's no surprise the context diff is the preferred format for many projects.  Anyway, as indicated in the patch title (line 4), the change is “internal”, not visible to the user.  We see in the before section one procedure: ‘sort/car<’, and in the after section, two: ‘sort/car’ and ‘sort/car<’, and that the second does indeed “use” (call) the first one.  (So the description (line 10) checks out.) 

The crux of the matter is the term “abstraction”.  Apparently the new procedure ‘sort/car’ (line 9) is one of these.  Well, here is where I save you from a long, boring, technical explanation and give instead an analogy from the kitchen.  Sometimes a recipe is very specific: “Add 2 tsp sugar.”  But as a cook, you know that sugar is just one of many sweeteners possible, each w/ its own particular flavor and texture profile (or whatever, I'm a terrible cook :-D).  So, when you describe the recipe to another cook, you substitute “sweetener” in your description, and leave it to the other cook to figure out what is best for their situation.  That substitution is a form of abstraction. 

Here, instead of specifying everything (in before-section ‘sort/car&lt;’), we add a procedure (that just happens to be higher-order function) that handles most of the computation but leaves the caller (i.e., after-section ‘sort/car<’) the choice (or responsibility, is another way to look at it) of customizing its behavior depending on its situation.  In this case, that choice is to pass procedure ‘string<?’ as the ‘bef’ parameter when it calls ‘sort/car’. 

Abstraction increases work a little bit, but has the advantage of focusing the remaining work (choosing the customization wisely) on what is really important.  Additionally, it makes the abstraction (procedure ‘sort/car’) available for other callers.  That's the primary reason for patch 4. 

Now on to patch 5!  Here's a context diff excerpt: 

 4	Subject: [PATCH 5/8] [tl-mkindex int] Add abstractions:
 5	 lexicographically-ordered, oldest-first
[...]
10	* sub/tl-mkindex (lexicographically-ordered): Rename from ‘sort/car<’.
11	(oldest-first): New proc alias.
12	(consult-db): Use ‘oldest-first’, ‘lexicographically-ordered’.
13	(interesting-elements): Use ‘oldest-first’.
[...]
20	*** a/sub/tl-mkindex
21	--- b/sub/tl-mkindex
22	***************
23	*** 214,222 ****
24	               (bef (car a)
25	                    (car b)))))
26
27	! (define (sort/car< ls)
28	    (sort/car string<? ls))
29
30	  (define (consult-db upath-ignored where-clause)
31
32	    ;; Aside from the "lift" comment below, it would be nice to be
33	--- 214,224 ----
34	               (bef (car a)
35	                    (car b)))))
36
37	! (define (lexicographically-ordered ls)
38	    (sort/car string<? ls))
39
40	+ (define oldest-first lexicographically-ordered)
41	+
42	  (define (consult-db upath-ignored where-clause)
43
44	    ;; Aside from the "lift" comment below, it would be nice to be
45	***************
46	*** 252,260 ****
47	                        *text)))))
48
49	    (define (one tag upath title)
50	!     (cons tag (sort/car< (map cons upath title))))
51
52	!   (sort/car<
53	     (apply map one (cols<-tuples-result
54	                     (fetch-tuples)))))
55
56	--- 254,262 ----
57	                        *text)))))
58
59	    (define (one tag upath title)
60	!     (cons tag (oldest-first (map cons upath title))))
61
62	!   (lexicographically-ordered
63	     (apply map one (cols<-tuples-result
64	                     (fetch-tuples)))))
65
66	***************
67	*** 285,291 ****
68
69	    (let-values (((leaf? tag refs) (context)))
70	      (let* ((distinct-refs (delete-duplicates
71	!                            (sort/car< (apply append refs))))
72	             (url (map car distinct-refs)))
73
74	        (define (leaf-entries)
75	--- 287,293 ----
76
77	    (let-values (((leaf? tag refs) (context)))
78	      (let* ((distinct-refs (delete-duplicates
79	!                            (oldest-first (apply append refs))))
80	             (url (map car distinct-refs)))
81
82	        (define (leaf-entries)
83	--

As the patch title (lines 4-5) indicates, this is more of the same: adding abstractions.  Unlike patch 4, however, there are two additions instead of one, which are reflected in more hunks, as well: hunk 1 (lines 23-45), hunk 2 (lines 46-66), hunk 3 (lines 67-83).  Still, the motivation, technique, and outcome are the same, so we can breezily gloss over the detailed analysis and stop only to point out one new aspect. 

In hunk 1, after-section, we see ‘oldest-first’ defined (line 40), but it is a definition w/o the usual parentheses and sub-forms.  What's the deal?!  It turns out, this kind of abstraction is called an “alias”, kind of like that (American) TV series, but for code instead of people.  In our kitchen analogy, this is like saying “sweetener” but implying strongly “sugar”.  The user (hunk 3, line 79) of the alias doesn't actually make a choice, but instead is forced to “think” with the new term.  In this way, aliases help move communication of algorithms towards expression in the solution domain rather than the (purely) implementation domain.  You know what I mean?  :-D

See, we covered two patches in one trip log!  Amazing!  Hopefully this momentum can be maintained... 


Copyright (C) 2021 Thien-Thi Nguyen