Backslash Calculus

From Esolang
Jump to: navigation, search

Backslash Calculus is a programming language invented by User:Tailcalled after reading this reddit comment.

Syntax

Backslash Calculus is based on lambda calculus, but it only uses two characters: backslash and space. This is the basic syntax:

   E = \ \ E    - abstraction
     | \ \\ E E - application
     | \\       - innermost variable
     | \\\      - the variable one level more out
     | ...      - ...

Computational Class

Backslash Calculus is clearly Turing-complete, even if one ignores its simple translation to lambda calculus. Here are the SKI combinators:

   S = \ \ \ \ \ \ \ \\ \ \\ \\\\ \\ \ \\ \\\ \\
   K = \ \ \ \ \\\
   I = \ \ \\

Alternative alphabets

Tailcalled imagined a few alternative alphabets for Backslash Calculus.

Unreadable

One can replace backslash with ' and space with ". The SKI combinators will look like this with that alphabet:

   S = '"'"'"'"'"'"'"''"'"''"''''"''"'"''"'''"''
   K = '"'"'"'"'''
   I = '"'"''

Brainfuck

One can change the syntax a bit to make Backslash Calculus look more like brainfuck:

   E0 = + E1 -
      | [ E0 E0 ]
      | .
      | ,.
      | ,,. <- unary-ish
      | ...
   E1 = > E0 <
      | [ E1 E1 ]
      | .
      | ,.
      | ,,. <- unary-ish
      | ...

The SKI combinators will look like this:

   S = +>+[[,,..][,..]]-<-
   K = +>[,.]<-
   I = +.-

See also