Re: knapsack problem solved by regex

[Dominus]

Have you seen I refuse to explain this?

Although I refused to explain it at the time, here is the summary: It is an interpreter for combinatory logic, a version of the λ-calculus that omits λ.

Each character in the output with ASCII code n is represented by a number 120-n, which is then represented in the program as an expression involving sums and products of Church numerals in whatever way yields an expression of minimal length.

The regex repeatedly evaluates the combinator expression, which has the effect of putting the Church numerals into normal form. A Church numeral n is actually a function which, given some other function f and an argument a, computes f(f(f(...f(a)...))). Once a Church numeral is normalized, it is applied to the function i, which increments the variable $R; the Church numeral iterates the i function the right number of times. Then the p function is called on the output of the is to actually print a character of output and reset $R.

The program actually looks like this:

``As`SB``Ad``S``BS`BBI``Ae``B`SI`Ed``A?``C``CIi`pI``E?``Es``B``Es``Es`
+`Es``Es``Es`KI```CI``Es``Es``Es`KI``Es``Es`KI``E?``Es``Es``Es`KI``E?`
+`Es``Es``Es``Es``Es`KI``E?``Es``Es``Es``Es`KI``E?``Es``B``Es``Es```CI
+``Es``Es``Es`KI``Es``Es``Es`KI``Es``Es``Es`KI``E?``Ee``Ee``Es``Es``Es
+``Es``Es`KI``E?``Es```CI``Es``Es``Es`KI``Es``Es`KI``E?```CI``Es``Es``
+Es`KI``Es``Es`KI``E?``Es``Es``Es``Es`KI``E?```CI``Es``Es``Es``Es`KI``
+Es``Es`KI``E?``Ee```CI``Es``Es``Es`KI``Es``Es`KI``E?``Ed``Es``Es``Es`
+KI``E?``Es``B``Es``Es```CI``Es``Es``Es`KI``Es``Es``Es`KI``Es``Es``Es`
+KI``E?``B``Es```CI``Es``Es``Es`KI``Es``Es`KI``Es``Es``Es``Es`KI``E?``
+Ee```CI``Es``Es``Es`KI``Es``Es`KI``E?``Ed``Es``Es``Es`KI``E?``B``Es``
+Es``Es``Es`KI``Es``Es``Es`KI``E?``Es``B``Es``Es```CI``Es``Es``Es`KI``
+Es``Es``Es`KI``Es``Es``Es`KI``E?``B```CI``Es``Es``Es``Es`KI``Es``Es`K
+I``Es``Es``Es`KI``E?``Ee``Ee``Es``Es``Es``Es``Es`KI``E?``B``Ee``Es``E
+s``Es`KI``Es``Es``Es`KI``E?``Ee``Ed``Es``Es``Es`KI``E?``Ee```CI``Es``
+Es``Es`KI``Es``Es`KI``E?``Ed``Es``Es``Es`KI``E?``Ed``Ee```CI``Es``Es`
+`Es`KI``Es``Es``Es`KI

` is the function application operator; `xy applies function x to argument y. Since the notation is prefix, parentheses are not required; one writes ``xyz or `x`yz as necessary.

The A operator performs a macro assignment, and the program starts by defining macros called s, d, e, and ?. I think these are probably the successor (x → x+1) function, addition, multiplication, and equal-to-zero, but I'm no longer sure.

The E operator retrieves a macro with a particular name, so that ``Esx applies the macro s to the argument x.

The V operator does nothing, but it's not used.

The S, K, I, B, and C operators are the important ones. They are explained in the Wikipedia article. As you can see from the code, ``Sxyz is just ``xz`yz, ``Cxyz is just ``xzy, ``Bxyz is just ``x`yz, ``Kxy is just x, and `Ix is just x. From this very thin base one can build addition and multiplication functions and indeed any function that one needs.

I used Church numerals so that I wouldn't have to define a fixed-point combinator.

I guess this probably all goes into the more-than-you-wanted-to-know file.

Addendum 1: Macro s is the successor function. `KI is the Church numeral zero. So when you see something like ``Es``Es``Es`KI, that is the successor of the successor of the successor of zero, which is 3.

Addendum 2: Macro ? is the printing routine, apparently named as a nod to Microsoft BASIC. It evaluates the following expression to a Church numeral, applies the numeral to i to set up $R, invokes the printing primitive p, and then continues with the rest of the program.