Recs

recs is 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

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

<variable>

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

(Call by name)

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 compose.

((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 xn-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.

Other

+ - * / √

(+ 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

(Note: it is similar to szudzik pairing function)

(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)

Interpreter

A interpreter written by Python3(I'm not sure if there are any bugs)

functions = [
 'S', 'Z', 'if', '+', '-', '*', '/',
 '=', '√', 'left', 'right', 'cons',
 'car', 'cdr', 'pair'
]
def sqrt(x):
 res=0;digit=1
 while digit<x:
  digit*=10
 while digit>0:
  while res**2<=x:
   res+=digit
  res-=digit
  digit=digit//10
 return res
def pair(x,y):
 if x>=y:return x**2+y
 return y**2+2*y-x
def left(p):
 k=sqrt(p)
 q=k**2+k
 if p>=q:return k-(p-q)
 return k
def right(p):
 k=sqrt(p)
 q=k**2+k
 if p>=q:return k
 return p-k**2

def pop(l):
 e=l+[]
 t=e.pop()
 if t!='(':return e
 i=1
 while i:
  t=e.pop()
  if t=='(':i+=1
  if t==')':i-=1
 return e
def top(l):
 e=l+[]
 t=e.pop()
 if t!='(':return [t]
 i=1;res=[t]
 while i:
  t=e.pop()
  if t=='(':i+=1
  if t==')':i-=1
  res.append(t)
 return res[::-1]
def token(string):
 a=(string
     .replace('(',' ( ')
     .replace(')',' ) ')
     .replace('\\\n','')
     .replace('\n',' ')
  )
 return list(filter(
          lambda x:x!='',
          a.split(' ')
        ))[::-1]
def isNum(x):
 nums='0123456789'
 return all(map(lambda x:x in nums,x))

def parse(string):
 def rec(tokens):
  last=tokens[-1]
  if last!='(':
   if isNum(last):return 'num',int(last)
   if last in functions:return(last,)
   return 'symbol',last
  l=tokens[1:-1]
  o=top(l);l=pop(l)
  if o==['lam']:
   para=top(l)[0];l=pop(l)
   body=top(l)
   return 'lam',para,rec(body)
  if o==['fn']:
   body=top(l)
   return 'fn',rec(body)
  if o==['P']:
   m=top(l);l=pop(l)
   n=top(l)
   return 'P',int(m[0]),int(n[0])
  if o==['C']:
   tmp=[]
   while l:tmp.append(rec(top(l)));l=pop(l)
   return 'C',tmp
  if o==['R']:
   h=top(l);l=pop(l)
   g=top(l)
   return 'R',rec(h),rec(g)
  if o==['M']:
   f=top(l)
   return 'M',rec(f)
  if o==['Z']:
   tmp=[]
   while l:tmp.append(rec(top(l)));l=pop(l)
   return 'app',('Z',),tmp
  if o==['let']:
   tmp=[]
   while l:tmp.append(rec(top(l)));l=pop(l)
   [*xs,res]=tmp
   while xs:
    arg,para=xs.pop(),xs.pop()[1]
    res=('app',('lam',para,res),[arg])
   return res
  if o==['list']:
   tmp=[]
   while l:tmp.append(rec(top(l)));l=pop(l)
   return 'list',tmp
  if o==['if']:
   cond=top(l);l=pop(l)
   t=top(l);l=pop(l)
   f=top(l)
   return 'app',('if',),[rec(cond), rec(t), rec(f)]
  if o[0]in{'=','+','-','*','/','cons','pair'}:
   a=top(l);l=pop(l)
   b=top(l)
   return 'app',(o[0],),[rec(a), rec(b)]
  if o[0]in{'√','car','cdr','left','right'}:
   a=top(l)
   return 'app',(o[0],),[rec(a)]
  tmp=[]
  while l:tmp.append(rec(top(l)));l=pop(l)
  return 'app',rec(o),tmp
 return rec(token(string))
def lam_rewrite(body,para,arg):
 t=body[0]
 if t=='symbol':
  if body[1][0]=='#'and isNum(body[1][1:]):return  body
  if body[1]==para:return arg
  return body
 if t=='num':return body
 if t=='list':return (
  'list',list(map(
   lambda x:lam_rewrite(x,para,arg),
   body[1]
  ))
 )
 if t=='lam':
  if body[1]==para:return body
  return (
   'lam',body[1],
   lam_rewrite(body[2],para,arg)
  )
 if t=='P':return  body
 if t=='C':
  return (
   'C',
   list(map(
    lambda x:lam_rewrite(x,para,arg),
    body[1]
   ))
  )
 if t=='app':
  return (
   'app',lam_rewrite(body[1], para, arg),
   list(map(
    lambda x:lam_rewrite(x,para,arg),
    body[2]
   )))
 return (
  body[0],
  *tuple(map(
   lambda x:lam_rewrite(x,para,arg),
   body[1:]))
 )
def fn_rewrite(body,args):
 t=body[0]
 if t=='num':return body
 if t=='list':return (
  'list',list(map(
   lambda x:fn_rewrite(x,args),
   body[1]
  ))
 )
 if t=='symbol':
  if body[1][0]=='#'and isNum(body[1][1:]):
   return val(args[int(body[1][1:])-1])
  return body
 if t in['fn','P']:return body
 if t=='app':
  return (
   'app',fn_rewrite(body[1],args),
   list(map(
    lambda x:fn_rewrite(x,args),
    body[2]
   )))
 if t=='lam':return (
  'lam',body[1],
  fn_rewrite(body[2],args)
 )
 return (
  body[0],
  *tuple(map(
   lambda x: fn_rewrite(x,args),
   body[1:]))
 )

def app(f,x):
 t=f[0]
 if t=='S':return 'num',val(x[0])[1]+1
 if t=='Z':return 'num',0
 if t=='if':
  if val(x[0])[1]:
   return val(x[1])
  return val(x[2])
 if t=='=':return (
  'num',
  int(val(x[0])[1]==val(x[1])[1])
 )
 if t=='+':return (
  'num',
  val(x[0])[1]+val(x[1])[1]
 )
 if t=='-':return (
  'num',
  max(0,val(x[0])[1]-val(x[1])[1])
 )
 if t=='*':return (
  'num',
  val(x[0])[1]*val(x[1])[1]
 )
 if t=='/':return (
  'num',
  val(x[0])[1]//val(x[1])[1]
 )
 if t=='cons':return (
  'list',
  [val(x[0])]+val(x[1])[1]
 )
 if t=='pair':return (
  'num',
  pair(val(x[0])[1],val(x[1])[1])
 )
 if t=='√':return (
  'num',
  sqrt(val(x[0])[1])
 )
 if t=='left':return (
  'num',
  left(val(x[0])[1])
 )
 if t=='right':return (
  'num',
  right(val(x[0])[1])
 )
 if t=='car':return val(x[0])[1][0]
 if t=='cdr':
  l=val(x[0])[1]
  if l:return 'list',l[1:]
  return 'list',l
 if t=='lam':
  return val(lam_rewrite(f[2],f[1],x[0]))
 if t=='fn':
  return val(fn_rewrite(f[1],x))
 if t=='P':
  return x[:f[1]][f[2]-1]
 if t=='C':
  fn=f[1][0]
  gs=f[1][1:]
  return app(
   fn,
   [app(g,x)for g in gs]
  )
 if t=='R':
  h=f[1];g=f[2]
  res=app(h,x[:-1])
  for i in range(x[-1][1]):
   res=app(g,x[:-1]+[('num',i)]+[res])
  return res
 if t=='M':
  fn=f[1];cnt=0
  while True:
   value=app(fn,x+[('num',cnt)])
   if value[1]==0:return 'num',cnt
   cnt+=1
 if t=='app':
  return app(val(f),x)
 return 'app',f,x

def val(exp):
 t=exp[0]
 if t=='app':
  return app(exp[1],(exp[2]))
 if t=='list':
  return 'list',list(map(val,exp[1]))
 return exp
def show(exp):
 t=exp[0]
 if t in functions:return t
 if t=='symbol':return exp[1]
 if t=='num':return str(exp[1])
 if t=='list':return f'(list {" ".join(map(show,exp[1]))})'
 if t=='app':return f'({show(exp[1])} {" ".join(map(show,exp[2]))})'
 if t=='P':return f'(P {exp[1]} {exp[2]})'
 if t=='C':return (
  '(C '+(' '.join(map(show,exp[1])))+')'
 )
 if t=='lam':
   return f'(lam {exp[1]} {show(exp[2])})'
 return f'({t} {" ".join(map(show,exp[1:]))})'

exp='''
(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)
)
'''
print(show(val(parse(exp))))