sinq — Shoddy INtegrated Query — is the half of
a query the rest of the library could not express: ordering by a
key (the value you sort or group on), grouping into groups,
joining two sequences, the set words, and walking a record graph that holds
itself.
It is deliberately small, and the reason is worth stating up front:
almost every query word you want already exists somewhere else.
Map, Filter, Fold and Sort
are builtins. Any, All, CountIf,
Contains, Taken, DropN,
Flatten and Zip are seq's.
Sum, Average, Maximum,
Median and Freq are stats'.
This machine re-declares none of them. It adds the six things that were
genuinely missing and stops.
Shoddy · The MachinesInclude "sinq.shoddy"
Let best = OrderByDesc(staff, Pay)
Let dept = GroupBy(staff, Dept)
Let both = OrderWith(staff, ThenBy(ByKey(Dept), Descending(ByKey(Pay))))Two traditions had to meet before a line like OrderByDesc(staff, Pay)
could exist. For about thirty-five years they barely spoke to each other.
The first begins in 1970 with Edgar Codd, an English
mathematician at IBM's San Jose laboratory, and a paper with the forbidding
title A Relational Model of Data for Large Shared Data Banks. Codd's
argument was that programs should stop walking to their data. Every database of
the day made you thread pointers from record to record by hand. So the shape of
the files was welded into the shape of the program, and moving a file broke the
lot. Codd said: describe the data as plain tables of rows, then ask a
question and let the machine work out the walking. IBM built a language
on it. Donald Chamberlin and Raymond Boyce
called it SEQUEL in 1974, and renamed it SQL when the original
name turned out to belong to a British aircraft firm. What survived is not any
of the engines it was written for but its vocabulary:
SELECT, WHERE, GROUP BY,
JOIN, ORDER BY. Half a century on, those words are
still how people say what they want from a pile of records.
The second tradition is older and comes from the opposite direction. In the 1930s Alonzo Church was after the foundations of mathematics rather than anybody's payroll file. He built the lambda calculus: an entire theory of computation out of one idea, that you can name an argument and substitute for it. A function became a thing you could hand about like any other value, with no name of its own if it did not want one. John McCarthy put it into a real language with LISP in 1958, and for decades that was where it stayed. The anonymous function was a functional-programming idea, databases were an industrial one, and the two communities shared conferences with nobody in common.
They were married in LINQ, designed by Erik Meijer and colleagues at Microsoft and shipped with C# 3.0 in 2007. The move that made it work was noticing that Codd's clauses were never really about tables. They were about sequences, and each clause needs exactly one small piece of caller-supplied code to say which or by what — which is precisely what a lambda is. So a query written in SQL's vocabulary could be translated into ordinary method calls taking anonymous functions. Suddenly the same five words worked on a list in memory, an XML document, or a table across a network.
Shoddy arrives at that junction already holding both halves. It has had the
lambda since the beginning — Fn(x) => … is Church's
idea with a BASIC accent. It has had the chain, because the
pipeline form already lets a deeper-indented line
read as the next stage. What it did not have was Codd's little word
by. So sinq adds no query syntax at all: no
from, no select, no string for anything to parse. It
adds the missing vocabulary as ordinary words, and the two-hundred-year-old
arithmetic of the mill accounts comes out reading like this:
| SQL | Shoddy | Whose word |
|---|---|---|
SELECT price * qty | Map(os, OrderValue) | builtin |
WHERE value >= 100 | Filter(os, Fn(o) => OrderValue(o) >= 100) | builtin |
ORDER BY value DESC | OrderByDesc(os, OrderValue) | sinq |
ORDER BY a, b DESC | OrderWith(os, ThenBy(ByKey(A), Descending(ByKey(B)))) | sinq |
GROUP BY area | GroupBy(cs, Area) | sinq |
JOIN book ON sku | JoinOn(os, book, Sku, CatSku, pick) | sinq |
SELECT DISTINCT | Distinct(xs) | sinq |
SUM(price) | Sum(Map(os, Price)) | stats |
FROM orders | — the sequence you started with | — |
There is no FROM because there is nothing to name: the query
begins with the value itself. And there is no query language here at
all. This machine's whole argument is that the words mostly existed already, so
that absence is the point rather than an omission.
The one query verb the standard library lacked is by. Every existing sequence word takes a predicate — a function answering true or false — or nothing at all.
Sort is the sharpest case. It is a builtin, it is
ascending-only, and it takes no key selector. Handed a record it does not sort
badly — it stops the program:
ERROR: SORT expects all NUMBERs or all STRINGsSo "the staff, highest paid first" — the most ordinary report there is — could not be written without hand-rolling a sort. Several machines did exactly that, and a couple wrote an apology into the source while they were at it.
The same gap runs through the rest. stats'
Freq gives you key → count; nothing gave
you key → the items themselves. Nothing joined two
sequences on a key. json's JPath and
xml's XPath walk their own formats. But a
record type of your own — the thing the language most encourages —
had no walker at all.
Every word here takes its sequence as the first argument. That is not decoration. It is what lets the language's own pipeline form — a statement continued on deeper-indented lines — read top to bottom like a method chain.
Def LargeOrders(cs As List Of Cust) As List Of Order
cs
SelectMany(Orders)
Filter(Fn(o) => OrderValue(o) >= 100)
OrderByDesc(OrderValue)Orders and OrderValue are passed as bare names:
an accessor — a word that reads one field out of a record — is an
ordinary function value. The accessors are the schema, and
unlike a query typed as a string they are checked when the program is
built.
A comparer is [ t t -- Number ]: negative if the first sorts
first, zero if neither does, positive otherwise. Four words build and combine
them, and one runs one.
OrderBy(staff, Pay) ' by one key
OrderByDesc(staff, Pay) ' the same, reversed
OrderWith(staff, ThenBy(ByKey(Dept), ByKey(Name))) ' by twoC# hangs ThenBy off an IOrderedEnumerable that
OrderBy hands back — a type whose only job is to remember
the comparison so far. Here the comparer is an ordinary value, so
ThenBy composes two of them and no such type is needed. It also
means a custom order — rank by an arbitrary scale, say — needs no
new machinery.
The sort is stable — a stable sort keeps tied
elements in the order they arrived — and that is load-bearing rather
than a nicety. A tie takes from the left run, which is exactly what makes
ThenBy produce the right answer.
GroupBy answers a list of Group, each with a
GKey and its GItems. Groups come back in
first-appearance order and their items in source
order. That is what C# guarantees, and it is what makes a grouped report
reproducible run to run.
Map(GroupBy(cs, Area), Fn(g) => Pair(GKey(g), Sum(Map(GItems(g), Spend))))JoinOn is the inner join: one result per matching pair, in left
order, dropping unmatched elements from both sides. GroupJoinOn
gives one result per left element with the whole list of its matches,
empty where there are none. That is the left outer join, and it is the reason
JoinOn needs no "OrDefault" twin.
The name Join was not available: str
owns it, for joining strings with a separator.
Descendants takes a root and a child selector. So it
works on any type that holds a list of itself, without this machine knowing
anything about it.
Type Unit
UnitName As String
Headcount As Number
Subs As List Of Unit
Sum(Map(Descendants(org, Subs), Headcount))Cycles cannot happen, and that is a guarantee rather than an assumption. Nothing mutates in Shoddy — no value can be changed after it is built — so a record cannot be made to refer to itself. There is no way to tie the knot after construction. A graph of records is therefore always a finite tree, which is why there is no visited-set here and none is needed.
There are no adapter words for these, on purpose, because none is needed.
Map, Filter and Sort keep the input's
kind, so an array is already a sequence. A vector is
Array Of Number — matrix declares no
separate type. And a Matrix's Cells is an array
already:
Filter(ToList(Cells(m)), Fn(v) => v <> 0) ' the nonzero cells
Map(Range(1, Rows(m)), Fn(r) => Sum(ToList(MatRow(m, r)))) ' a sum per rowA CsvSheet is queried through CsvDicts,
and a Json document through JItems and
JMembers, both of which hand back ordinary lists. An adapter layer
here would have bought nothing and cost a dependency.
Everything above, in one program that runs. It is
tst/sinq-demo.shoddy in the repo, and the gate runs it on every
release. So what follows cannot drift from a program that no longer
compiles:
Rem ==================================================================
Rem sinq-demo.shoddy -- the worked example for the sinq machine.
Rem
Rem This is a sample of USE, and it is documentation that has to keep
Rem working: docs/machines/sinq.html reproduces it line for line, and
Rem the gate runs it, so the page cannot drift from a program that no
Rem longer compiles. It ASSERTS NOTHING -- tst/sinq.shoddy is where
Rem the behaviour is graded. What this file proves is that a query
Rem against a real graph still READS the way the page says it does.
Rem
Rem One deep type graph (customers -> orders), one catalogue to join
Rem against, one self-holding type (an org tree), and one matrix. Every
Rem query below is written out of EXISTING library words plus the ones
Rem sinq adds. Note what is NOT here: no adapter for the Matrix, no
Rem cast, no schema declaration, no query string. The accessors --
Rem Orders, Area, Sku, Subs -- are the schema, and they are checked at
Rem compile time.
Rem
Rem mill run tst/sinq-demo.shoddy
Rem ==================================================================
Rem The paths are spelled out because a bare Include resolves against
Rem THIS directory first, and tst/sinq.shoddy would shadow the machine.
Rem seq is asked for in its own right: sinq includes it, but a machine
Rem hands over the words it DECLARES and not the ones it includes in
Rem turn, so Pair, Fst and Snd have to be named here.
Include "../machines/sinq.shoddy"
Include "../machines/seq.shoddy"
Include "../machines/stats.shoddy"
Include "../machines/matrix.shoddy"
Include "../machines/str.shoddy"
Rem ---- the graph --------------------------------------------------------
Type Order
Sku As String
Qty As Number
Price As Number
Type Cust
CustName As String
Area As String
Orders As List Of Order
Type Cat
CatSku As String
CatTitle As String
Rem a type that holds itself -- the deep graph case
Type Unit
UnitName As String
Headcount As Number
Subs As List Of Unit
Rem ---- the words a query is written out of ------------------------------
Def OrderValue(o As Order) As Number
Qty(o) * Price(o)
Def CustSpend(c As Cust) As Number
Sum(Map(Orders(c), OrderValue))
Rem ---- the queries ------------------------------------------------------
Rem Every large order, biggest first. The language's own pipeline form,
Rem reading exactly like a LINQ chain. The threshold is a lambda because
Rem it is used once and nowhere else; OrderValue is a named word because
Rem three separate queries below read it.
Def LargeOrders(cs As List Of Cust) As List Of Order
cs
SelectMany(Orders)
Filter(Fn(o) => OrderValue(o) >= 100)
OrderByDesc(OrderValue)
Rem Revenue by area. GroupBy is sinq's; Sum is stats'.
Def RevenueByArea(cs As List Of Cust) As List Of Pair
Map(GroupBy(cs, Area), Fn(g) => Pair(GKey(g), Sum(Map(GItems(g), CustSpend))))
Rem Two keys: spend descending, then name ascending for the ties.
Def Ranked(cs As List Of Cust) As List Of String
Map(OrderWith(cs, ThenBy(Descending(ByKey(CustSpend)), ByKey(CustName))), CustName)
Rem An inner join onto the catalogue.
Def Titled(os As List Of Order, book As List Of Cat) As List Of String
JoinOn(os, book, Sku, CatSku, Fn(o, p) => CatTitle(p) & " x" & Str(Qty(o)))
Rem The whole org tree flattened, then totalled with stats' Sum.
Def TotalHeads(root As Unit) As Number
Sum(Map(Descendants(root, Subs), Headcount))
Def Main()
Rem HOW A LITERAL MAPS TO A TYPE. A record is built POSITIONALLY: the
Rem constructor takes the fields in the order the Type declares them
Rem and NOTHING names them at the call site, so a reader has to count.
Rem That is why the columns below are lined up and each block is headed
Rem by the fields filling it. It is also why inserting a field into a
Rem Type is a silent break -- every later argument shifts one place and
Rem still compiles, so long as the kinds happen to match.
Rem
Rem A literal continues across lines only because it is inside open
Rem brackets; there is no continuation character in the language.
Rem CatSku CatTitle
Let book = {
Cat("WARP", "Warp beam"),
Cat("WEFT", "Weft yarn"),
Cat("SHOD", "Shoddy bale")
}
Rem Dyson is listed BEFORE Brook and both spend exactly 120, so the
Rem tie-break is doing real work: a correct ThenBy answers "Brook,
Rem Dyson" by name, and a sort that merely inherited source order
Rem would answer "Dyson, Brook".
Rem
Rem CustName Area Orders, each Order(Sku, Qty, Price)
Let cs = {
Cust("Ackroyd", "Dewsbury", { Order("WARP", 4, 30), Order("WEFT", 2, 15) }),
Cust("Dyson", "Batley", { Order("SHOD", 10, 12) }),
Cust("Crowther", "Dewsbury", { Order("WEFT", 1, 15), Order("WARP", 20, 30) }),
Cust("Brook", "Batley", { Order("SHOD", 10, 12) })
}
Print("-- large orders, biggest first --")
Each(LargeOrders(cs), Fn(o) => Print(" " & Sku(o) & " " & Str(OrderValue(o))))
Print("-- revenue by area --")
Each(RevenueByArea(cs), Fn(p) => Print(" " & Fst(p) & " " & Str(Snd(p))))
Print("-- ranked: spend desc, then name asc --")
Print(" " & Join(Ranked(cs), ", "))
Print("-- orders joined to the catalogue --")
Each(Titled(SelectMany(cs, Orders), book), Fn(s) => Print(" " & s))
Print("-- distinct skus, and set words --")
Let skus = Distinct(Map(SelectMany(cs, Orders), Sku))
Print(" distinct: " & Join(skus, ", "))
Print(" except: " & Join(Except(skus, { "WEFT" }), ", "))
Print(" intersect: " & Join(Intersect(skus, { "WEFT", "JUTE" }), ", "))
Rem The self-holding type. Subs is a List Of Unit, so a Unit's third
Rem argument is another literal of exactly this shape, all the way
Rem down -- the indentation on the page IS the tree in the data.
Rem
Rem Unit(UnitName, Headcount, Subs)
Let org = Unit("Mill", 3, {
Unit("Spinning", 12, {
Unit("Nights", 4, { })
}),
Unit("Weaving", 9, { })
})
Print("-- org tree --")
Print(" units: " & Str(Length(Descendants(org, Subs))))
Print(" heads: " & Str(TotalHeads(org)))
Rem a Matrix needs no adapter: its Cells are already an Array, and an
Rem Array is already a sequence. Same for a vector.
Let m = Mat(2, 3, { 5, 0, 7, 0, 2, 0 })
Print("-- matrix --")
Print(" nonzero cells: " & Str(Length(Filter(ToList(Cells(m)), Fn(v) => v <> 0))))
Print(" sorted desc: " & Str(First(OrderByDesc(ToList(Cells(m)), Fn(v) => v))))
Print(" row sums: " & Join(Map(Map(Range(1, Rows(m)), Fn(r) => Sum(ToList(MatRow(m, r)))), Str), ", "))-- large orders, biggest first --
WARP 600
WARP 120
SHOD 120
SHOD 120
-- revenue by area --
Dewsbury 765
Batley 240
-- ranked: spend desc, then name asc --
Crowther, Ackroyd, Brook, Dyson
-- orders joined to the catalogue --
Warp beam x4
Weft yarn x2
Shoddy bale x10
Weft yarn x1
Warp beam x20
Shoddy bale x10
-- distinct skus, and set words --
distinct: WARP, WEFT, SHOD
except: WARP, SHOD
intersect: WEFT
-- org tree --
units: 4
heads: 28
-- matrix --
nonzero cells: 3
sorted desc: 7
row sums: 12, 2Five lines of that output are doing real work rather than decorating the page:
Crowther, Ackroyd, Brook, Dyson — Dyson
is listed before Brook in the source and the two spend exactly the
same. Answering Brook, Dyson is what proves the tie-break ran at
all. An implementation that quietly inherited source order says
Dyson, Brook and looks just as plausible.Dewsbury before Batley —
groups come back in first-appearance order, which is neither alphabetical nor
the order the keys were first hashed into anything.JoinOn is an inner join in left order.row sums: 12, 2 — a Matrix
queried with no adapter at all, through Cells and
MatRow, both of which are already sequences.LargeOrders is a lambda and
OrderValue is a named word — the house rule
(Fn(x) => … for a predicate used once, a name for
anything read more than once), and evidence that taking the sequence first
lets a lambda sit in a pipeline stage without ceremony.Two properties of the runtime shape nearly every word in this machine. Both were measured rather than assumed, and a natural-looking implementation hits both.
A Shoddy list is contiguous underneath — one solid block of memory
— so Rest hands back a copy of the tail. Walking n
elements that way copies about n²/2 of them, and the cost grows with the
square of the length:
| Elements | A tail-recursive First/Rest walk |
|---|---|
| 6,250 | 40 ms |
| 12,500 | 74 ms |
| 25,000 | 636 ms |
| 50,000 | 3,585 ms |
Nothing here walks a list that way. Words that must visit every element
either Fold — a builtin loop — or ToArray
once and index with Nth, which is O(1) on an array — the
same cost however long the array is. The sort is a merge sort over an array
for the same reason.
This is entirely separate, and nothing to do with lists. A recursive call
that is not the last thing a word does costs a live stack frame per element,
and the ceiling is around twenty thousand frames. A stack
overflow is a hard process kill — not an Error, not
catchable, and with no line number to point at.
Mutual recursion is not optimised either. So the
tidy-looking shape — a chain of small Defs that hands back to the first
— is exactly as fatal as the untidy one. Every recursive word here calls
itself, as the very last step, carrying an accumulator — a
running answer built as it goes — that Reverse puts right
at the end.
The one deliberate exception is the sort's divide-and-conquer, which is mutually recursive between two words. That is safe because its depth is log₂(n) — seventeen frames for a hundred thousand elements — not n. Depth, not shape, is what matters there.
| Operation | Cost | Why |
|---|---|---|
OrderWith and friends | O(n log n) | merge sort over an array |
GroupBy | O(n × groups) | a scan of the groups per element |
JoinOn, GroupJoinOn | O(n × m) | nested loop; no hash index |
Distinct and the set words | O(n²) | Contains per element |
SelectMany, Choose, Descendants | O(n) | one pass |
There is no hashing here, for the same reason dict is an association list and says so in its own header. That is the right trade at the scale this library is written for — hundreds of rows, not millions — and it is written down so nobody has to measure to find out.
There is no deferred execution and no query object: every word computes its
whole answer at once. OrderBy, GroupBy and
JoinOn must all see every element before they can yield the first
one, so a lazy pipeline — one that computes elements only when asked
— could not stream through the operators that matter anyway.
FindOpt, TakeWhile and Choose are the
words that stop early, and they stop early by indexing rather than by being
lazy.
Shoddy has one flat word namespace: Include splices names in,
so a machine's helpers are exactly as public as its headline words, and there
is no such thing as a private Def. The words you are meant to type
are named plainly. Everything that is only scaffolding is prefixed
Snq, so the surface to learn is the unprefixed list and nothing
more. If you have a clashing name of your own, take the machine under a
namespace: Include "sinq.shoddy" As Q, then
QOrderBy.
| Word | What it does |
|---|---|
Compare(a, b) | −1, 0 or 1. The ordering under every comparer; works on Numbers and Strings, which is what < accepts. |
ByKey(keyOf) | A selector becomes a comparer. |
Descending(cmp) | A comparer, flipped. |
ThenBy(lead, tie) | One comparer that consults tie only where lead answers zero. |
OrderWith(xs, cmp) | Stable merge sort. Answers a List whatever it was handed. |
OrderBy(xs, keyOf) | Ascending by key. |
OrderByDesc(xs, keyOf) | Descending by key. |
stats' Minimum answers the smallest number in a list.
These answer the item whose key is smallest, which is a different
question and the one a query usually asks. Ties go to the earliest, matching the
sort.
| Word | What it does |
|---|---|
MinByOpt(xs, keyOf) | Some the item with the smallest key, None on an empty sequence. |
MinBy(xs, keyOf) | The same, aborting on empty. Written over the Opt twin, so there is one set of rules and not two. |
MaxByOpt(xs, keyOf) / MaxBy | The same pair, largest key. |
| Word | What it does |
|---|---|
Type Group | GKey and GItems. |
GroupBy(xs, keyOf) | Groups in first-appearance order, items in source order. |
JoinOn(xs, ys, xKeyOf, yKeyOf, pick) | Inner join, one result per matching pair, left order. |
GroupJoinOn(xs, ys, xKeyOf, yKeyOf, pick) | One result per left element with its whole match list — the left outer join. |
Records compare structurally, so these mean what they should on a record.
Lists compare by identity: two separately built lists of the
same items are not equal. So a sequence of lists is the one shape these
words cannot speak about. Use DistinctBy with a Number or String
key when that comes up.
| Word | What it does |
|---|---|
Distinct(xs) | Later repeats dropped; the first sighting stays in place. |
DistinctBy(xs, keyOf) | The earliest per key wins. |
Union(xs, ys) | Everything in either, once each. |
Intersect(xs, ys) | Only what is in both, in left order. |
Except(xs, ys) | In the first and not the second, in left order. |
| Word | What it does |
|---|---|
SelectMany(xs, f) | The one-to-many hop: Flatten of a Map. |
Thru(f, g) | Two selectors composed into one deep read. |
Descendants(root, kidsOf) | Root first, then each child's whole subtree, depth first. Costs a frame per level of depth, not per node. |
Offspring(root, kidsOf) | The same without the root. |
Option has no accessor word by design, so Select Case
is the only way in. These words are where that is written once instead of at
every hop.
| Word | What it does |
|---|---|
OptMap(o, f) | Apply f inside a Some. |
OptBind(o, f) | The same where f itself answers an Option. |
OptOr(o, dflt) | The value, or the fallback. |
ThruOpt(f, g) | Thru for steps that can fail; stops at the first None. |
Choose(xs, f) | Map and filter in one pass — keep only what f had an answer for, unwrapped. |
seq has Taken and DropN for a count. These
stop on a condition, which nothing had.
| Word | What it does |
|---|---|
TakeWhile(xs, p) | The run at the front that passes p. |
SkipWhile(xs, p) | Everything from the first failure onwards. |
Chunk(xs, n) | Fixed-size batches, the last one short. Refuses a size below one, which would never finish. |
FirstOpt(xs) / LastOpt(xs) | First and Last without the abort. |
SingleOpt(xs) | Some only when there is exactly one — for the query that expects a unique answer and wants to be told when it did not get one. |
FindOpt(xs, p) | The first element passing p, without visiting the rest. |
| User | How | |
|---|---|---|
 | alg | OrderWith replaced the hand-written insertion sort that canonicalisation ran on every simplify, and Distinct the dedupe loop beside it. |
 | bool | Quine–McCluskey rounds gather with SelectMany and Distinct, and pick their best implicant with MaxBy. |
 | json | OrderBy sorts an object's members by key directly, where canonicalisation used to sort the keys and map them back. |
 | xml | The same, for an element's attributes. |
 | reckoner | WORDS is a GroupBy over the dictionary, and RckFind a FindOpt over it. |
| Machine | How | |
|---|---|---|
 | seq | Pair carries a decorated element, Contains is what the set words ask, and Append and Last do the rest. seq is the only thing sinq stands on, which is what lets any machine take sinq without dragging a tree in behind it. |