Recs

recsis a esolang created by User: Jan jelo.The whole program is a expression,interpreter evaluate it and print the result. It combines partial recursive function and lambda calculus,and also some extensions.

Expression

A expression can be

<variable>

<natural number>

<function>

(list <expression> <expression>...)

(<function> <expression> <expression>...)

(let <name> <expression>...<name> <expression> <expression>)

Function

A function can be

Z S (P <natural number> <natural number>)

(C <function> <function>...)

(R <function> <function>)

(M <function>)

(lam <parameter> <expression>)

(fn <expression>)

+-*/√

pairleftright

conscarcdr

=

(if <expression> <expression> <expression>)

Reduce

Partial Recursive Function

Z

Z is zero function.

(Z x y z w...) will reduce to 0

S

S is successor function.

(S x y z w...) will reduce to x+1

P

(P m n) is projection function

((P m n)x1 x2...xn...xm) will reduce to xn

C

C is function combination.

((C f g1 g2...gm)x1 x2...xn) will reduce to (f (g1 x1...xn) (g2 x1...xn)...(gm x1..xn))

R

R is primitive recursion.

((R h g)x1...x_n-1 0) will reduce to (h x1...x_n-1)(base case)

((R h g)x1...x_n-1 xn) will reduce to (g x1...x_n-1((R h g)x1...x_n-1 xn-1))(recursive case)

M

M is minimalization.

((M f)x1...xn) will reduce to the smallest A that makes (f x1...xn A) reduce to 0

Lambda

lam

((lam x exp)x1...) will reduce to the exp that replace free x in exp into x1.

= + - * / √

(+ x1 x2...) will reduce to x1+x2

(- x1 x2...) will reduce to max(0,x1-x2)

(* x1 x2...) will reduce to x1*x2

(/ x1 x2...) will reduce to floor(x1/x2)

(√ x1...) will reduce to floor(sqrt(x1))

cons car cdr

(cons x (list a b c...)...) will reduce to (list x a b c...)

(car (list a b c...)...) will reduce to a

(cdr (list a b c...)...) will reduce to (list b c...)

pair left right

pair is a pairing function,it encodes two natural numbers into one natural number.

  0  1  2  3
  -----------
0|0  3  8  15
1|1  2  7  14
2|4  5  6  13
3|9  10 11 12

(pair l r...) will reduce to l^2+r if l>=r

(pair l r...) will reduce to 2*r+r^2-l if l<r

let K be floor(sqrt(p)),Q be K^2+K,then

(left p...) will reduce to K-p+Q if p>=Q

(left p...) will reduce to K if p<Q

(right p...) will reduce to p-K^2 if p>=Q

(right p...) will reduce to K if p<Q

= if

(= x1 x2...) will reduce to 1 if the value of x1 is equal to the value ofx2,otherwise it will reduce to 0

(if cond t f...) will reduce to f if the value of cond is equal to (list) or 0,otherwise it will reduce to t

let

(let x1 f1 x2 f2...xn fn e) will reduce to ((lam x1((lam x2(...((lam xn e)fn)...))f2))f1)

fn

((fn exp)x1...xn) will reduce to the exp that replace the free #<N> in exp into N-th argument in the arguments-list (((fn((fn #2)3 4))1 2) will reduce to 4,not 2)

Turing Completeness

Because Lambda calculus and partial recursive function are Turing complete,recs is turing complete.

Example

(let
 omega
 (lam x(x x))
 fix
 (omega
  (lam f
   (lam x
    (x((f f)x)))))
 fact
 (fix
  (lam fact
   (lam x
    (if x
     (* x(fact(- x 1)))
     1))))
 map
 (fix
  (lam map
   (fn
    (if #2
       (cons(#1(car #2))(map #1(cdr #2)))
       (list)))))
 lst
 (list 0 1 2 3 4 5 6 7 8 9)
 (map (C fact S) lst)

will output (list 1 2 6 24 120 720 5040 40320 362880 3628800)