Grr

From Esolang
Jump to: navigation, search

Grr is a pure textual programming language that composes rules and functions inspired in macro and high-order programming. Exist two ways of define rules in Grr, first using a simple substitution in x to y (x <- y) or make a function f that receive x and return y (f(x) <- y), however in the interpreter language they are all same substitution procedure. Grr is by default a recursive language, then rules can be replaced by the same rules (y <- y).

Examples

Hello World

 [Ώ <- T
 T <- HelloWorld]

Naturals Numbers

The code below encodes natural numbers through of recursive functions.

[
  Ώ <- MUL(FOUR)(FOUR)
  FOUR <- INC(INC(INC(INC(N))))
  N* <- *
  INC(Y) <- Y*
  DEC(K) <- K-
  *- <- λ
  ADD(X)(Y) <- XY
  MUL(X)(Y) <- Y-REPEATZ(X)
  *REPEATZ(X) <- REPEATZ(X)X
  REPEATZ(X) <- X 
]

Reserved Notations

In grr there are some reserved notations that formalize some conceptions that grr leak, Ώ is the main function where the rules can be decomposed initially, λ is an empty string and brackets construct nested rules that control backing recursive rules. Comments can be inserted with space after the replaced rule.

[ (1)
  P <- F(F(x))x (x <- λ) (F(y) <- y) (only two rules) rules only of (1 + 1) = (2)
  x <- λ 
  [ if a string down in a rule here (2 + 1) = (3)
    F(y) <- y  (x <- K) (if a string down here the string gain a new rule of x)
    [ (3) 
      x <- K
    ]
  ]
]

Corresponding calculation

Grr rules are just string substitution, therefore are high-order objects like lambda functions, then it's possible to implement easily a lambda term, for example, SK combinators.

 s(x)(y)(z) <- x(z)(y(z))
 k(x)(y) <- x
 i(x) <- s(k)(k)(x)

Turing Completeness

This program below is Brainfuck interpreter (10 cells limit) :

[
  Ώ <- BRAINFUCK(>+<+++{-})
  Δ* <- * *Δ <- * *α <- λΔ α* <- λΔ INC(Y) <- Y* DEC(K) <- Kα
  ADD(X)(Y) <- XY MUL(X)(Y) <- Y-REPEATZ(X) *REPEATZ(X) <- REPEATZ(X)X REPEATZ(X) <- X
  FIVE <- INC(INC(INC(INC(INC(Δ)))))
  TEN <- ADD(FIVE)(FIVE)
  HUNDRED <- MUL(TEN)(TEN)
  THOUSAND <- MUL(HUNDRED)(HUNDRED)
  MULK(_)(X)(Y) <- _DEC(DEC(Y))REPEATZ(X)
  BRAINFUCK(x) <- 'BF(TAPE(x))'G___K 
  [
    TAPE(x) <- MULK(kPOINTER(x)(Δ))(POINTER)(TEN)
    kPOINTER(x)(y) <- yx|T(x)(y)(λ)(Δ)
    POINTER <- T(#)(Δ)(λ)(Δ)
    ç> <- move_cell ç< <- back_cell ç+ <- incre_cell ç- <- decr_cell ç{ <- init_loop ç} <- cond_loop
    Δ> <- ç>P Δ< <- ç<P Δ+ <- ç+P Δ- <- ç-P Δ{ <- ç{P Δ} <- ç}P
    P> <- P P< <- P P+ <- P P- <- P P{ <- P P} <- P
    *> <- *α *< <- *α *+ <- *α *- <- *α *{ <- *α *} <- *α
    *S| <- SX| *SX <- SX
    P| <- λ| PT <- T
    ΔS| <- CON_| SX| <- REP_|
    AA(D)l <- l AA(_)0 <- l_
    l* <- * lΔ <- Δ Δ| <- |
    move_cell|T(x)(y)(z)($)T(X)(Y)(Z)(_) <- T(#)(Δ)(z)($)y*x|T(x)(y*)(Z)(_)
    T(X)(Y)(Z)(_)back_cell|T(x)(y)(z)($) <- y*x|T(x)(y*)(Z)(_)T(#)(Δ)(z)($)
    incre_cell|T(X)(Y)(Z)(_) <- Y*X|T(X)(Y*)(Z)(_*)
    decr_cell|T(X)(Y)(Z)(_) <- Y*X|T(X)(Y*)(Z)(_α)
    init_loop|T(X)(Y)(Z)(_) <- Y*X|T(X)(Y*)(ZAA(Y))(_)
    cond_loop|T(X)(Y)(Z)(_) <- _S|T(X)(Y)(Z)(_)
    CON_|T(X)(Y)(Z)(_) <- Y*X|T(X)(Y*)(Zl)(_)
    REP_|T(X)(Y)(Z)(_) <- Z0X|T(X)(Z0)(Zl)(_)
    G___K <- ___END	 
    [
      'BF(x)'___END <- x
      [
        T(x)(y)(z)(_) <- (_)
      ]
    ]
  ]
]

Grr is able to compute a brainfuck interpreter with infinite numbers of cells, once brainfuck is Turing completeness, by consequence, Grr is Turing complete too.

Implementation

Grr interpreter is avaliable in : https://github.com/caotic123/Grr-Programming-Language