Credit Card numbers as syntactic data type

As pointed out to me by the late, and greatly missed, Michael Sperberg-McQueen, checking that the sum of the digits of a number match a certain value can be seen as a syntactic as well as an arithmetic problem.

For instance, if a number is divisible by 3, the sum of digits of that number are also divisible by three. So here is the syntax of all numbers divisible by three (using the syntax notation of ixml). This grammar accepts a list of numbers, and succeeds if all the numbers are divisible by 3.

input: (three, spaces)+.
three: ["0369"], -three?;
       ["147"], one;
       ["258"], two.
-one:  ["0369"], one;
       ["147"], two;
       ["258"], -three?.
-two:  ["0369"], two;
       ["147"], -three?;
       ["258"], one.
-spaces: -[" "; #a]+.

How it works: you start off in the state "divisible by 3", every new character moves you into a new state: a "1", "4", or "7" takes you into the "modulo 1" state, "2", "5", or "8" takes you into the "modulo 2" state, and "0", "3", "6", or "9", keeps you in the "divisible by 3" state.

If you are in "modulo 1" state, then a "1" would take you to "modulo 2", and a "2" would take you to "divisible by three". And so on.

Well, this is generalisable to any target sum.

A credit card number is checked for small typing errors using the Luhn algorithm (https://en.wikipedia.org/wiki/Luhn_algorithm), which simplified says: taking the digits from the right-hand end, add the odd-numbered digits, and twice the even numbered digits, except if twice times the digit is greater than 9, sum the digits of the result before adding to the total. So 8 doubled is 16, which gives 7. The resulting sum must be a multiple of 10.

Consequently, I have succeeded in creating a syntax of credit cards. There are two intermingled states: the divisible, mod 1, mod 2, etc. up to mod 9 states, and "the next digit is doubled" and "the next digit is not doubled" states.

So s0 means: this is a single digit in divisible state, and d1 means this is a digit to be doubled in modulo 1 state.

Thus in state s3, a "1" will take you into d4, and a "7" into d0.
Similarly in state d1, a "1" will take you into s3, and a "6" will take you into (6×2=12, 1+2=3) state s4.

But remember, we are going from right to left, so the syntax rules look like:

 s1: d1, "0"; d2, "1"; ...

which means we are going from s1 to d2 when we get a "1" (read it right to left if you like).

Also note that d0 and s0 are the success states, so they also have an empty alternative that marks success when there are no more digits. All the other states require more digits.

What this means is that a creditcard number can be a data type, with no function needed to check that the digits sum correctly.

So here is the grammar (as you can see it is very regular, and almost mechanical):

input: cc++-#a, -#a?.
cc: s0.

-s0: d0, "0"; d1, "1"; d2, "2"; d3, "3"; d4, "4"; d5, "5"; d6, "6"; d7, "7"; d8, "8"; d9, "9"; .
-d0: s0, "0"; s2, "1"; s4, "2"; s6, "3"; s8, "4"; s1, "5"; s3, "6"; s5, "7"; s7, "8"; s9, "9"; .

-s1: d1, "0"; d2, "1"; d3, "2"; d4, "3"; d5, "4"; d6, "5"; d7, "6"; d8, "7"; d9, "8"; d0, "9".
-d1: s1, "0"; s3, "1"; s5, "2"; s7, "3"; s9, "4"; s2, "5"; s4, "6"; s6, "7"; s8, "8"; s0, "9".

-s2: d2, "0"; d3, "1"; d4, "2"; d5, "3"; d6, "4"; d7, "5"; d8, "6"; d9, "7"; d0, "8"; d1, "9".
-d2: s2, "0"; s4, "1"; s6, "2"; s8, "3"; s0, "4"; s3, "5"; s5, "6"; s7, "7"; s9, "8"; s1, "9".

-s3: d3, "0"; d4, "1"; d5, "2"; d6, "3"; d7, "4"; d8, "5"; d9, "6"; d0, "7"; d1, "8"; d2, "9".
-d3: s3, "0"; s5, "1"; s7, "2"; s9, "3"; s1, "4"; s4, "5"; s6, "6"; s8, "7"; s0, "8"; s2, "9".

-s4: d4, "0"; d5, "1"; d6, "2"; d7, "3"; d8, "4"; d9, "5"; d0, "6"; d1, "7"; d2, "8"; d3, "9".
-d4: s4, "0"; s6, "1"; s8, "2"; s0, "3"; s2, "4"; s5, "5"; s7, "6"; s9, "7"; s1, "8"; s3, "9".

-s5: d5, "0"; d6, "1"; d7, "2"; d8, "3"; d9, "4"; d0, "5"; d1, "6"; d2, "7"; d3, "8"; d4, "9".
-d5: s5, "0"; s7, "1"; s9, "2"; s1, "3"; s3, "4"; s6, "5"; s8, "6"; s0, "7"; s2, "8"; s4, "9".

-s6: d6, "0"; d7, "1"; d8, "2"; d9, "3"; d0, "4"; d1, "5"; d2, "6"; d3, "7"; d4, "8"; d5, "9".
-d6: s6, "0"; s8, "1"; s0, "2"; s2, "3"; s4, "4"; s7, "5"; s9, "6"; s1, "7"; s3, "8"; s5, "9".

-s7: d7, "0"; d8, "1"; d9, "2"; d0, "3"; d1, "4"; d2, "5"; d3, "6"; d4, "7"; d5, "8"; d6, "9".
-d7: s7, "0"; s9, "1"; s1, "2"; s3, "3"; s5, "4"; s8, "5"; s0, "6"; s2, "7"; s4, "8"; s6, "9".

-s8: d8, "0"; d9, "1"; d0, "2"; d1, "3"; d2, "4"; d3, "5"; d4, "6"; d5, "7"; d6, "8"; d7, "9".
-d8: s8, "0"; s0, "1"; s2, "2"; s4, "3"; s6, "4"; s9, "5"; s1, "6"; s3, "7"; s5, "8"; s7, "9".

-s9: d9, "0"; d0, "1"; d1, "2"; d2, "3"; d3, "4"; d4, "5"; d5, "6"; d6, "7"; d7, "8"; d8, "9".
-d9: s9, "0"; s1, "1"; s3, "2"; s5, "3"; s7, "4"; s0, "5"; s2, "6"; s4, "7"; s6, "8"; s8, "9".

Received on Tuesday, 26 August 2025 20:08:12 UTC