Lighter Concepts
Article Thesis: Finding a good set of primitives which describes the domain is the goal of a library. You can thus make a library which even introduces someone to the topic, they see the core concepts and how they interrelate! This should be the goal of architecture/design: Isolating meaningful concepts and removing implementation cruft etc.
Vocab:
- primitive - language/library building block
- concept - domain idea
- ontology/conceptual vocabulary/catalogue
I hypothesize the underlying value of tacit programming is reducing the conceptual inventory of a program, not the number of characters or tokens, but the size of the ontology. Less things exist in that universe when you remove a name in favor of a common pattern of function application. That’s what I want to compress. - zdsmith
What you already know
Lazy reduce/fold builds all maping primitives map is equivalent to a for loop with one less name:
(def adjusted-scores @[])
(each score scores # i.e. for score in scores
(array/push adjusted-scores (math/abs score)))
(def adjusted-scores (map math/abs scores))
We can isolate the different logic:
(seq [i :range [0 5]] (+ i 1)) # i names a position
(map (fn [x] (+ x 1)) (range 5)) # x names the element
(map |(+ 1 $) (range 5)) # |(...) is an anonymous function
$ is a short anonymous function’s parameter, a pronoun, letting us replace a novel name with structural syntax, Search “closed class” words yet not entirely tacit. (This means I’m arguing for a 3rd category between named and tacit code, explained .)
better-cond
Well designed APIs reduce the need for names, simplifying their callers. Most lisps have cond like:
(def x 5)
(cond
((odd? x) "odd") # note wrapping around each test-result pair
((even? x) "even"))
Whereas Clojure (and Janet) don’t wrap the pairs:
(def x 5)
(cond
(odd? x) "odd"
(even? x) "even")
better-cond (defined here) doesn’t require a name at all (but may still use one) and is simply a function which you can map over etc.:
(map (better-cond
string? "not a number"
odd? "odd"
even? "even") [1 2 3 "cat"])
((better-cond # accepts 2 or more arguments!
< "first is smaller"
> "second is smaller")
5 3)
The elegance is palpable.
(map (fn [n]
(cond
(zero? (% n 15)) "FizzBuzz"
(zero? (% n 5)) "Buzz"
(zero? (% n 3)) "Fizz"
(number? n) n))
(range 1 16))
(map (better-cond
|(zero? (% $ 15)) "FizzBuzz"
|(zero? (% $ 5)) "Buzz"
|(zero? (% $ 3)) "Fizz"
number? identity)
(range 1 16))
An API decides which names its callers must invent. cond makes you bind the tested thing, better-cond doesn’t.
If every user of an application needs to write the same code, your API is wrong. If you abstract away the boilerplate and reuse that abstraction, you’ve made the world better. If you create a tool that generates the boilerplate, you’ve made the world more fragile. - David Chisnall
The reader only has to learn a library name (like better-cond) once, but
deftrecord 2
Similarly, while working on a type system for Janet, zzkt proposed a compacted predicate API:
(deftrecord :rainfall-report # sad
(field rainfall :number)
(guard (fn [v] (and (< (get v :rainfall) 1000)
(> (get v :rainfall) 0)))))
(deftrecord :rainfall-report # sleek and sexy
(field rainfall :number)
(guard (and (< rainfall 1000)
(> rainfall 0)))) # indeed (< 0 rainfall 1000) works
Hunting to fatten this article, I asked for details:
Seeing that almost every record I made only used a single var (essentially a ‘self’) the 2nd form makes sense. The only place where I was using more args than ‘self’ it could be reduced to single arg. It just means that the guard fn only has access to the record declaration scope, which is probably for the best and covers almost all cases. The enforced limit would reduce unexpected weirdness. Sometimes that can be useful. My thinking would be for simpler guard predicates for records, if the guard needs env scope wider than the deftrecord it might suggest a new type? - zzkt
When a guard requires outside names, the concepts (names) require further work ??? replaced reification but not great phrasing/not clear
Great, so we have reduced names. Have we lost anything? Perhaps we shouldn’t be too hasty. What does a name actually do? Names BCKW calculus, plus recombine allow you to:
- reorder arguments
flipor⍨ - use a value multiple times
duplicate - feed the result to another func
compose - ignore a value (
K) - feed one input to two functions
recombine/forks
Schönfinkel showed S and K combinators cover every case, reduce with accumulators covers everything on lists. See Hutton and Bird but we don’t want to argue for replacing every name. Replacing everything with only S and K would blow up combinatorially. With less concepts, we have more total tokens. Facing this while compiling SASL to combinators, Turner created new ones to shrink his programs. Abstraction is important! Isolating ideal primitives and representations gives us the tools to better grasp and manipulate a topic. ??? this doesn’t quite fit order-wise, or where to place what
Tacit programming allows you to replace bespoke things with manufactured parts from an engineering catalogue. Quite the opposite of our normal thoughts about Haskell and BQN wizards hand building everything!
Eliminating boilerplate and bookkeeping, the program only contains meaningful decisions.
When should names survive? When do they improve things?
At the right level of abstraction, chemists prefer to talk of elements like Hg, Mg instead of the hundreds of protons and electrons (S and K) particle physicists view.
We want an ideal mapping to our problem’s domain. An ideal mapping which we can learn to better understand the field, just like a good notation expands your view, just like the periodic table of elements made people better understand chemistry, elements and realize things were missing! Mendeleev’s table predicted properties and missing elements e.g. gallium because it surfaced gaps. Gaps in a domain’s catalogue predict missing concepts and interactions!
Similarly, Juggling notation revealed many tricks no one had performed before. (I wrote about notation for discovery here.)
If we can create the laws/dimensions for our notation, we can know precisely what primitives it needs.
State
If two states don’t interact, each is its own reduce and they fork. For hours of fun for the whole family consult Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire For example, the typical |(/ (sum $) (length $)) forks 2 reduces while this rather horrid mean implementation merges them with t and c:
(defn mean [xs]
(let [[total n] (reduce (fn [[t c] x]
[(+ t x) (+ c 1)])
[0 0] xs)]
(/ total n)))
Such tacit code leverages tree-shaped dataflow, with forks and duplicate letting adjacent branches share. But the further apart branches are, the more tedious to share with combinators (or stack manipulations). Names help share a value at multiple distant points along the tree, (hence Factor’s locals (::).)
Names share a value across distance in a dataflow tree; mutable names share a value across time. Are We There Yet? separates “identity”, value and state.
Arity and Pronouns
At some point our pronoun inventory is exhausted. Hungarian only has ő while English has he, she and it. But “he said that he saw him yell at him” is not especially clear. K offers x, y, z, APL only has ⍺ & ⍵. While Janet short functions offer $ and positional pronouns like $0, $1, $2 etc. and amp; showing where a value came from, but not what it is.
This means we actually have:
- unique names (open class)
- pronouns (fixed names, closed class)
- tacit code lacks any reference (via position or combinators) (“zero anaphora” like pro-drop Spanish not requiring “yo” in “te amo”)
K eschews J’s trains for x, y, z, a comfortable middle point.
Domain Vocabulary
“Ubiquitous language” doesn’t grow the ontology; vat-rate costs accounting software nothing. Indeed, it makes things clearer:
(map |(* $ (+ 1 vat-rate)) prices)
(map |(* $ 1.19) prices) # 1.19 obscures a domain concept
Anonymous abstractions are not very discoverable. Stitch compresses its corpus into things like fn_532. [LILO](https://arxiv.org/abs/2310.19 791) named and documented them improving the synthesizer’s usage. Compression finds the concept and naming makes it a primitive/retrievable/usable. ???
Edit Locality
Refactoring tacit code may require rewriting the whole train. Names help make things local or add printf when debugging.
how do we choose the optimal set of primitives?
Let compression algorithms choose an alphabet/catalogue, then you can just look at that and know what the good concepts are ???
Rissanen’s Minimum Description Length, DreamCoder used a Bayesian versionI want a shorter (+ (length library-definitions) (length all-code-using-library)).
Given a sequence, Identifying Hierarchical Structure in Sequences inferred a grammar whose rules often land on word boundaries. On the other hand Byte-Pair Encoding tokenizers convert text into a sequence of int IDs whose tokens don’t always align with morphemes, but programming languages tend towards isolation so it’s not tragic.
A compressor finds frequent patterns, and frequency is only a proxy for meaning. Coincidental duplication compresses the corpus as well as a true abstraction: two functions sharing five lines by accident look identical to it. (Sandi Metz’s “The Wrong Abstraction” describes the aftermath.) Two things separate a concept from a coincidence. Structure: Stitch abstracts over syntax trees, so every abstraction is a well-formed expression with holes, while a BPE token like “)) " is frequent and meaningless. And generalization, which is decisive: a concept compresses programs outside the corpus, while a coincidence only compresses the corpus. This is overfitting, the failure of a trading strategy tuned on historical data. DreamCoder’s loop approximates the test, since each round’s library is judged by the next round’s unsolved tasks. ??? fix Compression finds frequent patterns, not concepts. Frequency is only a proxy for meaning. Coincidental duplication compresses as well as true abstraction, which is Sandi Metz’s “The Wrong Abstraction” in information-theoretic dress.
- Stitch works on tree structure respecting syntax while BPE tokens don’t (just compressing strings)
- a real concept compresses later programs, overfit abstractions only work on the training corpus Improved efficiency may lead to increased errors, just as overfitting trading algorithms to test data may boost returns but produce horrible later results. ???
DreamCoder then Stitch did this as a library, factoring repeated subexpressions into a library, solving new problems with said library and repeating towards the perfect fit. Babble did similar via E-Graphs and Anti-Unification.
Fewer well-chosen primitives make for shorter standard programs (frequency weighted with rare programs maybe being longer.)
Density shrinks the distance between correct and incorrect programs. In J, the 3 train (+/ % #) is a fork finding the mean and the 2 train (% #) is a hook dividing each element by length, not typing one verb gives a valid program with the wrong meaning.
Shannon’s result cuts both ways. A code without redundancy is as short as possible, and every corruption of it decodes to a different valid message. Human languages keep redundancy so messages survive noisy channels. Agreement is a type check: a gender or case mismatch signals an error the listener can detect and often repair. Spanish can drop “yo” in “te amo” precisely because the conjugation already marks person; the redundancy lets one marker go missing. Dense code gives this up. Drop one verb from J’s (+/ % #) and (% #) still runs. Programmers want the redundancy without the repetition, so we move it into types and tests, which detect errors without lengthening every expression. ???fix this section, not quite sure what to do with it, the above is a quote someone suggesteds In verbose systems like human languages, redundancy increases comprehension in lossy (e.g. loud) enivornments for example pronouns and verbal conjugations both indicating person (Are personal, gender or case agreement type checks?) In programming, we prefer to express redundancy for error detection with types and tests instead of repetition and boilerplate.
Iverson suggested:
- ease of expressing common constructs (primitives should cover frequent patterns e.g.
mapmeans “do this to every”) - suggestivity (
+/suggests that you can do-/too. Likewise, gaps imply other primitives. Taking it further J exposes obverses syntactically.) - hiding incidental detail (
$instead of a new name) - economy (a few things handle many things)
- amenability to formal proofs (e.g. if primitives leverage algebraic laws, you can more easily rewrite programs e.g.
filter p ∘ filter q = filter (q and p)a la Bird & Meertens)
I volunteer structural criteria:
- closure - outputs are valid inputs (e.g. APL arrays in and out, UNIX text streams, Clojure hashmaps everywhere)
- primitives shouldn’t express the same concept
A good notation turns recall into perception. Roman and Arabic numerals notate the same numbers but positional notation makes multiplication a mechanical procedure. A good diagram like the periodic table groups related facts together, so you can search by looking (e.g. on the valence column). With map/filter/reduce, the first element shows the algorithm’s shape (instead of hunting around for recursion in the body.)
By relieving the brain of all unnecessary work, a good notation sets it free to concentrate on more advanced problems, and in effect increases the mental power of the race. - Whitehead
The reader only has to learn a language or library name once; such knowledge compounds/amortizes across every program using it, while a parameter definition must be learned and forgotten outside of its function’s body. Tacit code moves the ontology cost from the program, repaid by every reader, to a library, paid once.
Tacit programming allows you to replace bespoke things with manufactured parts from an engineering catalogue. - me, above
About naming:
- Zipf’s Law of Abbreviation - We should of course make the more frequent names shorter
??? This stuff isn’t the focus yet, but some ideas/corrections are fine.
Addendum
What tools do we have to reduce names?
Iterators
Built from lazy reduce, we find a small group of useful primitives:
mapfilterfindtake-whileaccumulate
(But Janet’s reduce is eager and can’t build find nor take-while without a sentinel (e.g. prompt and return) or full iteration.)
Combinators
Of the many, many combinators in the forest, there are some that are useful to programmers. These are the ones that correspond to the most common patterns of function application that your average programmer tends to encounter - zdsmith
His https://git.sr.ht/~subsetpark/apcl-janet has:
identityconstantcomposeapplyflipduplicateleftrightrecombineunder
In a stack language like Factor or Colorforth you accept parameters by position (in the stack). Concatentation is composition. Factor’s shuffle words are the BCKW calculus: dup, swap, drop, jusxtaposing and bi.
点赞
收藏
点踩
分享