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
(<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))))
Category: LanguagesCategory: Turing completeCategory: 2024Category: Functional paradigmCategory: Implemented