John’s Combinatory Logic Playground

John’s Lambda Calculus and Combinatory Logic Playground

000100011001100101000110100 000000101100000100100010101 11110111 101001000 11010000 111001101 000000000010110111001110011 11111011110000000011111001 10111000 00010110 0000110110 0011010100 0101000101 0001000001 0100000100 0101000100 0001000001 0100000100 0101000001 0001000001 0000000100 0101000101 0001000000 0000000100 0100000101 0000000001 0100000100 0001000100 0001000001 0100000000 0101000101 0000000000 0100000000 0001000101 0001000001 0100000000 0100000100 0001000001 0100000100 0101000000 0001000000 ...

Pictured above you possibly can see on the left the 206 bit binary lambda calculus (blc) self-interpreter
in graphical notation, and on the precise a 167 bit primes program,
in each binary and graphical notation, along with the primary 300 bits of output.
You may run this immediately by feeding primes.blc into
the tiny blc interpreter in perl with

  perl blc.pl -b 
(Outputting far more than 300 bits in Perl will land your pc in swap hell.)
or into the blc interpreter in C with
  cc -DM=999999 -m32 -std=c99 uni.c -o uni
  ./uni -b 
Possibility -b denotes bit-oriented IO moderately than the default byte-oriented mode.
An obfuscated version of this interpreter
received as Most functional
within the 2012 Worldwide Obfuscated C Code Contest.


Binary lambda calculus is defined intimately in my newest paper obtainable in
PostScript and PDF,
and in considerably much less element in this former Wikipedia entry.

I just lately proposed a functional Busy Beaver which led to this OEIS entry.

Impressed by an April 13, 2008
FP Lunch weblog by
Thorsten Altenkirch,
I used to be in a position to enhance the fixed within the symmetry-of-information theorem
from 1876 all the way down to 1636, and once more on Mar 3, 2009 all the way down to 1388.
On September 3, 2011, Bertram Felgenhauer got here up with a monadic evaluator that permits one
to maintain monitor of the bits of enter learn up to now, which avoids the necessity for symbolic discount,
and minimize the fixed all the way in which all the way down to 667 bits. Bertram additionally improved the brainfuck interpreter
by 64 bits.

On Mar 10, 2009, I made up my mind the primary 4 bits of the halting chance: .0001.
On June 17, 2011, following a suggestion by Chris Hendrie, I modified the integer/string correspondence to keep away from reversing. This big-endian illustration makes lexicographic order on delimited numbers coincide with numeric order.

In March 2012 I labored out this easiest stepwise lambda calculus reducer,
a mandatory ingredient in a proof of the Symmetry of Info theorem.


This design of a minimalistic common pc was motivated by
my need to provide you with a concrete definition of

Kolmogorov Complexity, which research randomness of particular person
objects.
All concepts within the paper have been
implemented
within the the splendidly elegant Haskell
language, which is principally pure typed lambda calculus with numerous
syntactic sugar on high. An instance session:
# alias uni8="./blc run8 uni8.lam"
# cat > stutter.lam
let
  stutter = l l(crdz z c (z z c (stutter r)))l
in stutter
^D
# make stutter.Blc
./blc Blc stutter.lam > stutter.Blc
# od -Advert -x stutter.Blc
0000000 8446 0016 c25b 3fdf 9ade
0000010
# cat stutter.Blc - | uni8
whats up
hheelllloo

# make primes.Blc
./blc Blc primes.lam > primes.Blc
# od -Advert -x primes.Blc
0000000 9911 8046 2458 de57 a191 00cd ce2d 787f
0000016 cd07 b0c0 006c
0000021
# cat primes.Blc - | uni8 | head -c 50
00110101000101000101000100000101000001000101000100
# make bf.Blc
./blc Blc bf.lam > bf.Blc
# wc bf.Blc
  0   2 104 bf.Blc
# cat hw.bf
# ++++++++++[>+++++++>++++++++++>+++>+++.>+.+++++++..+++.>++..+++.------.--------.>+.>.]
# cat bf.Blc hw.bf | uni8
Howdy World!

exhibiting a ten byte program for ``stuttering'', a 21 byte program for primes,

and a 104 byte Brainfuck interpreter.

This

online course at Oberlin School

offers a really readable introduction to combinators.

Colin Taylor has written a really comparable

interpreter

for the Lambda Calculus, whereas

Gregory Chaitin,

promotor of algorithmic info principle, wrote

one

for LISP.

The

Unlambda

Programming Language is a combinator based mostly language with enter, output,

delayed analysis, and call-with-current-continuation. Interpreters

have been

written in lots of languages, together with c, java, perl, scheme, SMLNJ, CAML,

and even in unlambda

itself!

Lately, Ben Rudiak-Gould (benrgATdarkDOTdarkwebDOTcom)

made obtainable a



most complete combinatory logic interpreter, utilizing

Church numerals for character encodings. By tying the combinator code to

customary enter/output, his Lazy K language

helps acquainted utilities reminiscent of type! To high it off, he

offers a compiler (itself written in Scheme) from (a subset of)

Scheme into Lazy Ok.

Chris Barker additionally has a number of

pages of curiosity, together with a 

Lambda tutorial and a few 

highly minimalistic languages.


Earlier than discovering how you can interpret lambda calculus in binary,

I discovered how you can make a common machine in binary combinatory logic.

The previous seems to be much more descriptive, i.e. usually needing

fewer bits. However for historic curiosity, I preserve this outdated applet right here:

Truly, it slows down web page loading an excessive amount of, so I remark it out.


  See Also
  

    
  
  

    		
		    
The Bees of Childeric I – Simply Historical past Posts
  


This program is an interpreter for the only language doable:

each capabilities and information are represented by combinators, constructed up

from S and Ok by utility.

The primitive combinators are outlined by

Combinator identifiers are all a single character.

Other than the primitive combinators S and Ok, the interpreter has

the next predefined combinators:

 I=SKK

 Y=SSK(S(Ok(SS(S(SSK))))Ok)

 Pxyz=zxy

 0xy=x

 1xy=y

 ?$=0

 ?(Pxy)=1


Within the textual content enter subject, you possibly can enter definitions such because the

above, or mixtures to be evaluated. In case the result’s too giant

to be proven intimately, components of it are proven as asterisks.

If the end result will be interpreted as an inventory, that is proven as an output string

with bits 0,1 and once more asterisks indicating non-bit parts.
An instance session is (enter strains proven with a > immediate):
> 2fx=f(fx)
defines 2 as (S(S(KS)Ok)I)
> 222(P0)$
of dimension 46
head reduces in 53 steps to S(S(Ok(S(SKK)))KK)(Ok(SKK(S(Ok(S(*Ok)))Ok)(SKK(S(Ok(*Ok))(SKK(S(*)Ok)))(SKK(S(Ok(*))(*Ok(*(*))))(SKK(S(*)(*(*)))(KK)))))) of dimension 167
outputs 16 bits "0000000000000000"