Now Reading
John’s Combinatory Logic Playground

John’s Combinatory Logic Playground

2023-03-12 15:29:20

John’s Combinatory Logic Playground

[picture of Ulambda]

Lambda Calculus
Combinatory Logic

     11110111          101001000
     11010000          111001101
    0000110110    [picture of Primes]

  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 -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
  stutter = l l(crdz z c (z z c (stutter r)))l
in stutter
# make stutter.Blc
./blc Blc stutter.lam > stutter.Blc
# od -Advert -x stutter.Blc
0000000 8446 0016 c25b 3fdf 9ade
# cat stutter.Blc - | uni8
whats up

# 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
# cat primes.Blc - | uni8 | head -c 50
# make bf.Blc
./blc Blc bf.lam > bf.Blc
# wc bf.Blc
  0   2 104 bf.Blc
# cat
# ++++++++++[>+++++++>++++++++++>+++>+++.>+.+++++++..+++.>++..+++.------.--------.>+.>.]
# cat bf.Blc | uni8
Howdy World!

exhibiting a ten byte program for ``stuttering'', a 21 byte program for primes,
and a 104 byte Brainfuck interpreter.

online course at Oberlin School
offers a really readable introduction to combinators.
Colin Taylor has written a really comparable
for the Lambda Calculus, whereas
Gregory Chaitin,
promotor of algorithmic info principle, wrote
for LISP
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
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

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"

Source Link

What's Your Reaction?
In Love
Not Sure
View Comments (0)

Leave a Reply

Your email address will not be published.

2022 Blinking Robots.
WordPress by Doejo

Scroll To Top