Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?

Comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
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 (xx+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.

In reply to Re: knapsack problem solved by regex by Dominus
in thread knapsack problem solved by regex by rubasov

Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?

    What's my password?
    Create A New User
    and all is quiet...

    How do I use this? | Other CB clients
    Other Users?
    Others about the Monastery: (7)
    As of 2018-02-23 05:08 GMT
    Find Nodes?
      Voting Booth?
      When it is dark outside I am happiest to see ...

      Results (300 votes). Check out past polls.