# The use of this file under unix: % mupad < cs.test # read ("cs.mu"): cs::VERSION; #---------------------------------------------------------------------- Standard form ----------------------------------------------------------------------# # Plutarque numbers: # spec:={S = Union(x,Sn,Sa), Sa = Prod(S,Sequence(Sp,card>=1)), Sp = Union(x,Sequence(Sp,card>=2)), Sn = Prod(N, Sp), N=Epsilon, x=Atom}: cs::standardForm1(spec,unlabelled): if cs::standardForm1(spec,unlabelled)<> {T1 = ProdSeq(Sp, T2), S = Union(x, Sn, Sa), Sa = Prod(S, T1), Sn = Prod(N, Sp), T5 = ProdSeq(Sp, T4), x = Atom(x), T2 = Union(T3, T4), Sp = Union(x, T5), T3 = Epsilon(T3), T4 = ProdPrdSeq(Sp, T2), N = Epsilon(N)} then error("Plutarque numbers std form") end_if; # 1-2-3-arity trees: # spec:={T=Prod(Z,Sequence(T,card<=3))}: cs::standardForm1(spec,unlabelled): if cs::standardForm1(spec,unlabelled)<> {T6 = Union(T7, T12), T7 = Epsilon(T7), T9 = Union(T7, T8), T10 = ProdPrdSeq(T, T9), T12 = ProdSeq(T, T11), T8 = ProdPrdSeq(T, T7), T = Prod(Z, T6), Z = Atom(Z), T11 = Union(T7, T10)} then error("1-2-3-arity trees std form") end_if; #---------------------------------------------------------------------- compile - count - draw ----------------------------------------------------------------------# # Binary trees: # spec:={B=Union(Z,Prod(B,B))}: cs::compile(spec): if [cs::count([B,spec],size=i)$i=0..10]<> [0, 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862] then error("Binary trees") end_if; # Integer partitions: # spec:={P=Set(N),N=Sequence(Z,card>=1)}: if [cs::count([P,spec],size=i)$i=0..10]<> [1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42] then error("Integer partitions") end_if; # Idem with Predefined: # entier:=fun(1):entier(0):=0: spec:={P=Set(N),N=Predefined(entier)}: if cs::count([P,spec],size=10)<>42 then error("partitions with Predefined") end_if; # Motzkin trees: # spec:={M=Union(Z,Prod(Z,M),Prod(Z,M,M))}: if [cs::count([M,spec],size=i)$i=0..10]<> [0, 1, 1, 2, 4, 9, 21, 51, 127, 323, 835] then error("Motzkin trees") end_if; SEED:=1: if cs::draw([M,spec],size=3)<> Prod(Z, Z, Z) then error("Motzkin trees (draw1)") end_if; SEED:=2: if cs::draw([M,spec],size=3)<> Prod(Z, Prod(Z, Z)) then error("Motzkin trees (draw2)") end_if; # Schroeder trees: # spec:={S=Union(Z,Prod(S,U)), U=Union(Prod(Z,S),Prod(S,U))}: if [cs::count([S,spec],size=i)$i=0..10]<> [0, 1, 0, 1, 1, 3, 6, 15, 36, 91, 232] then error("Schroeder trees") end_if; # Integer partitions with odd summands: # isodd:=fun(args(1) mod 2): spec:={P=Set(N),N=Predefined(isodd)}: if [cs::count([P,spec],size=i)$i=0..10]<> [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10] then error("Integer partitions with odd summands") end_if; SEED:=2: if cs::draw([P,spec],size=3)<> Set(N(3)) then error("Integer partitions with odd summands (draw2)") end_if; SEED:=3: if cs::draw([P,spec],size=3)<> Set(N(1), N(1), N(1)) then error("Integer partitions with odd summands (draw3)") end_if; # General trees: # spec:={T=Prod(Z,Sequence(T))}: if [cs::count([T,spec],size=i)$i=0..10]<> [0, 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862] then error("General trees") end_if; if cs::draw([T,spec],size=2)<> Prod(Z, Sequence(Prod(Z, Epsilon))) then error("General trees (draw)") end_if; # (right) Schroeder trees: # spec:={S=Union(Z,Prod(Epsilon,Sequence(S,card>=2)))}: if [cs::count([S,spec],size=i)$i=0..10]<> [0, 1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049] then error("(right) Schroeder trees") end_if; if cs::draw([S,spec],size=2)<> Prod(Epsilon, Sequence(Z, Z)) then error("(right) Schroeder trees (draw)") end_if; # 3-arity trees: # spec:={T=Union(Z,Prod(Z,Sequence(T,card=3)))}: if [cs::count([T,spec],size=i)$i=0..10]<> [0, 1, 0, 0, 1, 0, 0, 3, 0, 0, 12] then error("3-arity trees") end_if; if cs::draw([T,spec],size=4)<> Prod(Z, Sequence(Z, Z, Z)) then error("3-arity trees (draw)") end_if; # 1-2-3-arity trees: # spec:={T=Prod(Z,Sequence(T,card<=3))}: if [cs::count([T,spec],size=i)$i=0..10]<> [0, 1, 1, 2, 5, 13, 36, 104, 309, 939, 2905] then error("1-2-3-arity trees") end_if; if cs::draw([T,spec],size=2)<> Prod(Z, Sequence(Prod(Z, Epsilon))) then error("1-2-3-arity trees (draw)") end_if; # A Sloane's example # spec:={N=Set(P), P=Prod(Z,Sequence(Z4)), Z4=Prod(Z$4)}: if [cs::count([N,spec],size=i)$i=0..10]<> [1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 4] then error("A Sloane's example") end_if; #---------------------------------------------------------------------- speciftoalgeq - algeqtodiffeq - diffeqtorec ----------------------------------------------------------------------# # Motzkin words: # sys:={M=Union(V,Prod(Z,M),Prod(Z,Z,M,M)), Z=Atom, V=Epsilon}: if cs::speciftoalgeq(sys,M)<>M*z-M+M^2*z^2+1 then error("speciftoalgeq for Motzkin words") end_if; # Motzkin trees: # sys:={M=Union(Z,Prod(Z,M),Prod(Z,M,M))}: if (eq:=cs::speciftoalgeq(sys,M))<>z-M+M*z+M^2*z then error("speciftoalgeq for Motzkin trees") end_if; if (deq:=cs::algeqtodiffeq(eq,M(z)))<>2*z-M(z)+z*M(z) -z*D(M)(z)+2*z^2*D(M)(z)+3*z^3*D(M)(z) then error("algeqtodiffeq for Motzkin trees") end_if; if cs::diffeqtorec(deq, M(z), v(n))<>v(n-1)-v(n)-n*v(n) +2*(n-1)*v(n-1)+3*(n-2)*v(n-2) then error("diffeqtorec for Motzkin trees") end_if; # Red-blue trees: # sys:={R=Union(Z,Prod(Z,B,B)),B=Union(Z,Prod(Z,R,R,R))}: if cs::speciftoalgeq(sys,B)<> B*(-1) + z + z^4 + B^2*z^4*3 + B^4*z^4*3 + B^6*z^4 then error("Red-blue trees: B") end_if; if cs::speciftoalgeq(sys,R)<>R*(-1) + z + z^3 + R^3*z^3*2 + R^6*z^3 then error("Red-blue trees: R") end_if; # Others examples: # if cs::diffeqtorec(y(z)-a*D(y)(z), y(z), v(n))<>v(n)-a*(n+1)*v(n+1) then error("diffeqtorec 1") end_if; if (deq:=cs::algeqtodiffeq(y - z - y^2,y(z)))<>4*z*D(y)(z)-2*y(z)-D(y)(z)+1 then error("algeqtodiffeq 1") end_if; if cs::diffeqtorec(deq, y(z), v(n))<>4*n*v(n)-2*v(n)-(n+1)*v(n+1) then error("diffeqtorec 2") end_if; if (deq:=cs::algeqtodiffeq(y - z - z*y - z*y^3,y(z)))<> y(z)*2 + z*y(z)*(-2) + z*D(y)(z)*(-2) + z^2*D(y)(z)*12 + z^3*D(y)(z)*(-18)\ + z^4*D(y)(z)*62 + z^2*D(D(y))(z)*(-4) + z^3*D(D(y))(z)*12 + z^4*D(D(y))(\ z)*(-12) + z^5*D(D(y))(z)*31 then error("algeqtodiffeq 2") end_if; if cs::diffeqtorec(deq, y(z), v(n))<> v(n)*2 + n*v(n)*(-2) + v(n + (-1))*(-2) + n*v(n)*(n + (-1))*(-4) + (n + (-\ 1))*v(n + (-1))*12 + (n + (-2))*v(n + (-2))*(-18) + (n + (-3))*v(n + (-3))\ *62 + (n + (-1))*(n + (-2))*v(n + (-1))*12 + (n + (-2))*(n + (-3))*v(n + (\ -2))*(-12) + (n + (-3))*(n + (-4))*v(n + (-3))*31 then error("diffeqtorec 3") end_if; #---------------------------------------------------------------------- use of speciftorec in compile for context-free specifications ----------------------------------------------------------------------# cs::HOLONOMIC:=TRUE: # Binary trees (2): # spec:={B=Union(Z,Prod(B,B))}: cs::compile(spec): if [cs::count([B,spec],size=i)$i=0..10]<> [0, 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862] then error("Binary trees (2)") end_if; # Motzkin trees (2): # spec:={M=Union(Z,Prod(Z,M),Prod(Z,M,M))}: if [cs::count([M,spec],size=i)$i=0..10]<> [0, 1, 1, 2, 4, 9, 21, 51, 127, 323, 835] then error("Motzkin trees (2)") end_if; # Schroeder trees (2): # spec:={S=Union(Z,Prod(S,U)), U=Union(Prod(Z,S),Prod(S,U))}: if [cs::count([S,spec],size=i)$i=0..10]<> [0, 1, 0, 1, 1, 3, 6, 15, 36, 91, 232] then error("Schroeder trees (2)") end_if; # Parallelogram polyominoes: # spec:={PP=Union(Prod(Z1,Z2),Prod(Z1,PP),Prod(Z2,PP),Prod(PP,PP)),Z1=Atom,Z2=Atom}: if [cs::count([PP,spec],size=i)$i=0..10]<> [0, 0, 1, 2, 5, 14, 42, 132, 429, 1430, 4862] then error("Parallelogram polyominoes") end_if; # General trees (2): # spec:={T=Prod(Z,Sequence(T))}: if [cs::count([T,spec],size=i)$i=0..10]<> [0, 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862] then error("General trees (2)") end_if; # (right) Schroeder trees (2): # spec:={S=Union(Z,Prod(Epsilon,Sequence(S,card>=2)))}: if [cs::count([S,spec],size=i)$i=0..10]<> [0, 1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049] then error("(right) Schroeder trees (2)") end_if; #---------------------------------------------------------------------- use of lazy product algorithm in compile ----------------------------------------------------------------------# cs::HOLONOMIC:=FALSE: cs::LAZY:=TRUE: # Binary trees (3): # spec:={B=Union(Z,Prod(B,B))}: cs::compile(spec): if [cs::count([B,spec],size=i)$i=0..10]<> [0, 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862] then error("Binary trees (3)") end_if; # Motzkin trees (3): # spec:={M=Union(Z,Prod(Z,M),Prod(Z,M,M))}: if [cs::count([M,spec],size=i)$i=0..10]<> [0, 1, 1, 2, 4, 9, 21, 51, 127, 323, 835] then error("Motzkin trees (3)") end_if; # Integer partitions (2): # spec:={P=Set(N),N=Sequence(Z,card>=1)}: if [cs::count([P,spec],size=i)$i=0..10]<> [1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42] then error("Integer partitions (2)") end_if; #---------------------------------------------------------------------- Generation of C code (DPE or GMP library) and C dynamic modules (DPE) ----------------------------------------------------------------------# cs::HOLONOMIC:=FALSE: cs::LAZY:=FALSE: spec:={T=Prod(Z,Sequence(T))}: # C - DPE by default # cs::compile(spec, target=C, file="PTrdpe.c", main=T): # C - GMP # cs::compile(spec, target=C, library=GMP, file="PTrgmp.c", main=T): # C dynamic module - DPE # cs::compile(spec, target=MODULE, file="PTrmoddpe.c"): quit