3 ms·

John's Lambda Calculus and Combinatory Logic Playground

97 points by mmphosis 4y ago

deleted 4y ago
[deleted]
tromp 4y ago
I happen to be preparing an upcoming talk about this on Pi day [1]. Happy to answer any questions! [1] https://www.meetup.com/lispnyc/events/290789901/ https://www.meetup.com/lispnyc/events/290789901/
- Y_Y 4y ago
  Before I spend a big pile of CPU time trying to find a shorter BLC self-interpreter, why won't it work?
  - tromp 4y ago
    It might just work, if you find a smarter approach than I did. Will buy you a dozen beer if you succeed!
    - djedr 4y ago
      Hey, just want to say that BLC is a remarkable artifact -- to me it's an art piece in computational minimalism. I actually got so obsessed with it last year that I worked out a variant of lambda calculus[0] in which, with some trickery, a port of the BLC interpreter could be squeezed into 194 bits. Which would be only 2 bits more than the intriguing conjecture from your paper[0] says to be optimal: > We conjecture that any self-interpreter for any binary representation of lambda calculus must be at least 24 bytes in size, which would make E close to optimal. I wonder what are the assumptions behind this conjecture. Surely my trickery broke some of them. [0] https://xtao.org/blog/last-intro.html https://xtao.org/blog/last-intro.html [1] https://tromp.github.io/cl/LC.pdf https://tromp.github.io/cl/LC.pdf
      - sargstuff 4y ago
        Conjecture on why 194 bits[0] and not 192 bits[1]: a) CS off by one error (started bit count at 1 instead of 0 ) b) Included 'NIL' as a bit. [0] https://xtao.org/blog/last-intro.html https://xtao.org/blog/last-intro.html [1] https://tromp.github.io/cl/LC.pdf https://tromp.github.io/cl/LC.pdf
        sargstuff 4y ago
        Snarky conjecture: 7bit ascii in-ram version of "λm.m(λx.x)(λx.x)" is mxx which if hardware supports bit addressing only uses 21 bits. Smallest ascii lisp is 14bits though.
      - tromp 4y ago
        LAST is an interesting variation, that is in essence identical to the oddly named "Real Fast Nora's Hair Salon 3: Shear Disaster Download" language [1]. Instead of L A S T, it names the 4 tokens LAMBDA APP ONE_MORE_THAN ZERO. I noticed that using two separate tokens for variable handling allows BLC to interpret LAST in only 193 bits. Still, I suspect that for most programs, the savings from S-optimization do not quite make up for the (n-1) extra bits needed for every occurrence of variable n. What would for instance be the length of the shortest LAST program for the prime number character sequence, which takes 167 bits in BLC? > I wonder what are the assumptions behind this conjecture. I chose 24 bytes because it's a nice round number (3 * 2^3 * 2^3 bits) that sat a seemingly comfortable 14 bit margin below my best effort. The conjecture assumes a binary input, that must be read bit-by-bit. How long is your LAST self-interpreter with a binary rather than quaternary input? [1] https://esolangs.org/wiki/Real_Fast_Nora%27s_Hair_Salon_3:_Shear_Disaster_Download https://esolangs.org/wiki/Real_Fast_Nora%27s_Hair_Salon_3:_S...
        djedr 4y ago
        I replied in Markdown here: https://gist.github.com/djedr/4ae1373faa7d43f359a2a245132341a0 https://gist.github.com/djedr/4ae1373faa7d43f359a2a245132341...
        4y ago
b1c1jones 4y ago
It has a beat, and you can dance to it.

97 points by mmphosis 4y ago

deleted 4y ago

[deleted]

I happen to be preparing an upcoming talk about this on Pi day [1]. Happy to answer any questions! [1] https://www.meetup.com/lispnyc/events/290789901/ https://www.meetup.com/lispnyc/events/290789901/

Y_Y 4y ago
Before I spend a big pile of CPU time trying to find a shorter BLC self-interpreter, why won't it work?
- tromp 4y ago
  It might just work, if you find a smarter approach than I did. Will buy you a dozen beer if you succeed!
  - djedr 4y ago
    Hey, just want to say that BLC is a remarkable artifact -- to me it's an art piece in computational minimalism. I actually got so obsessed with it last year that I worked out a variant of lambda calculus[0] in which, with some trickery, a port of the BLC interpreter could be squeezed into 194 bits. Which would be only 2 bits more than the intriguing conjecture from your paper[0] says to be optimal: > We conjecture that any self-interpreter for any binary representation of lambda calculus must be at least 24 bytes in size, which would make E close to optimal. I wonder what are the assumptions behind this conjecture. Surely my trickery broke some of them. [0] https://xtao.org/blog/last-intro.html https://xtao.org/blog/last-intro.html [1] https://tromp.github.io/cl/LC.pdf https://tromp.github.io/cl/LC.pdf
    - sargstuff 4y ago
      Conjecture on why 194 bits[0] and not 192 bits[1]: a) CS off by one error (started bit count at 1 instead of 0 ) b) Included 'NIL' as a bit. [0] https://xtao.org/blog/last-intro.html https://xtao.org/blog/last-intro.html [1] https://tromp.github.io/cl/LC.pdf https://tromp.github.io/cl/LC.pdf
      - sargstuff 4y ago
        Snarky conjecture: 7bit ascii in-ram version of "λm.m(λx.x)(λx.x)" is mxx which if hardware supports bit addressing only uses 21 bits. Smallest ascii lisp is 14bits though.
    - tromp 4y ago
      LAST is an interesting variation, that is in essence identical to the oddly named "Real Fast Nora's Hair Salon 3: Shear Disaster Download" language [1]. Instead of L A S T, it names the 4 tokens LAMBDA APP ONE_MORE_THAN ZERO. I noticed that using two separate tokens for variable handling allows BLC to interpret LAST in only 193 bits. Still, I suspect that for most programs, the savings from S-optimization do not quite make up for the (n-1) extra bits needed for every occurrence of variable n. What would for instance be the length of the shortest LAST program for the prime number character sequence, which takes 167 bits in BLC? > I wonder what are the assumptions behind this conjecture. I chose 24 bytes because it's a nice round number (3 * 2^3 * 2^3 bits) that sat a seemingly comfortable 14 bit margin below my best effort. The conjecture assumes a binary input, that must be read bit-by-bit. How long is your LAST self-interpreter with a binary rather than quaternary input? [1] https://esolangs.org/wiki/Real_Fast_Nora%27s_Hair_Salon_3:_Shear_Disaster_Download https://esolangs.org/wiki/Real_Fast_Nora%27s_Hair_Salon_3:_S...
      - djedr 4y ago
        I replied in Markdown here: https://gist.github.com/djedr/4ae1373faa7d43f359a2a245132341a0 https://gist.github.com/djedr/4ae1373faa7d43f359a2a245132341...
        4y ago

b1c1jones 4y ago

It has a beat, and you can dance to it.