[HN Gopher] Binary Lambda Calculus (2012)
       ___________________________________________________________________
        
       Binary Lambda Calculus (2012)
        
       Author : tosh
       Score  : 14 points
       Date   : 2021-04-11 11:54 UTC (11 hours ago)
        
 (HTM) web link (www.ioccc.org)
 (TXT) w3m dump (www.ioccc.org)
        
       | lifthrasiir wrote:
       | John Tromp is an active HN user and he almost surely replies to
       | any mention to BLC or similar. I personally find Jot [1] more
       | elegant though, where every bit sequence is a valid program. (I'm
       | not very qualified to say which one is more compact in general
       | however.)
       | 
       | [1] https://en.wikipedia.org/wiki/Iota_and_Jot#Jot
        
       | bediger4000 wrote:
       | It's worth reading Tromp's paper on BLC:
       | http://tromp.github.io/cl/LC.pdf
       | 
       | Lots of info about Lambda Calculus itself, the closely-related
       | Combinatory Logic, and how Tromp arrived at his tiny little BLC.
       | Pretty much a tour de force of mathematical logic.
        
       | peter_d_sherman wrote:
       | PDS: My new all-time favorite article on HN in the field of
       | Turing Machines, Lambda Calculus, Tiny Languages, etc.
       | 
       | >"This program celebrates the close connection between
       | obfuscation and conciseness, by implementing the most concise
       | language known,
       | 
       |  _Binary Lambda Calculus (BLC)_. "
       | 
       | [...]
       | 
       | >"The BLC universal machine may be small at 650 bytes of C (952
       | bytes including layout),
       | 
       |  _but written as a self interpreter in BLC it is downright
       | minuscule at 232 bits (29 bytes):_ "
       | 
       | [...]
       | 
       | >"A half byte `cat' The shortest (closed) lambda calculus term is
       | \x x (\ 1 in De Bruijn notation) which is the identity function.
       | When its encoding 0010 is fed into the universal machine, it will
       | simply copy the input to the output. (well, not that simply,
       | since each byte is smashed to bits and rebuilt from scratch)
       | Voila: a half byte cat:"
       | 
       | [...]
       | 
       | >"A BLC assembler Writing BLC programs can be made slightly less
       | painful with this parser that translates single-letter-variable
       | lambda calculus into BLC:"
       | 
       | PDS: Opinion: Not just brilliant -- but insanely, utterly,
       | astronomically brilliant!
       | 
       | My hat, as someone deeply interested in the fundamentals of
       | computation, and as someone who could never accomplish what you
       | did -- goes off to you!
       | 
       | Again... utterly, utterly brilliant!
        
       ___________________________________________________________________
       (page generated 2021-04-11 23:02 UTC)