Bugs (doesn't handle base case of recursion correctly?)

(%i2) call_expr_tree(1);
last: empty argument.
#0: finalize_list(tt=[])(tree.mac line 14)

OK:

(%i3) call_expr_tree(a+b);
(%o3) ["+",b,a]

(%i4) x[1] : 5;
(%o4) 5

Not OK (fix this with a local, I think)

(%i5) call_expr_tree(a+b);
first: argument must be a non-atomic expression; found 5

both curr_exp and final are global variables--I think you could greatly simplify your code and eliminate these

globals too.

From: Pankaj Sejwal <pankajsejwal@gmail.com>
Sent: Monday, August 11, 2014 05:35
To: maxima-discuss@lists.sourceforge.net; Stavros Macrakis; Barton Willis; Richard Fateman
Subject: Assigning positions to an expression's parts

Hi,
Recently there was discussion regarding assigning position to list elements but that method wasn't for expressions.

I have written some new methods that shall address this problem,
_______________________________
/*------------*/
call_expr_tree(lis):=block([final:[],temp:[],count:0,curr_exp],expr_tree(lis),
final:map(lambda([x],[cons(first(x[1]),last(x[1])),last(x)]),final),finalize_list(final))\$
/*------------*/
expr_tree(lis):=block([oper],if(atom(lis)=false) then (oper:op(lis),push([[oper,args(lis)],curr_exp],final),(for i:1 thru length(args(lis))
do (curr_exp:args(lis)[i],
expr_tree(args(lis)[i]))))else lis)\$
/*------------*/
finalize_list(tt):=block(for item:1 thru length(tt) do ( for i:1 thru length(tt) do
(for j:1 thru length(first(tt[i])) do
(if(last(tt[item])=first(tt[i])[j]) then
first(tt[i])[j]:tt[item][1]))),
first(last(tt)))\$
/*------------*/
%in:      call_expr_tree(a^2+b^3+c^4);
%out:    ["+",["^",c,4],["^",b,3],["^",a,2]]
/*------------*/
%in: tt:call_expr_tree((z+y+k+ll)^4+a^2+b^3+c^4+sin(s+f));
%out: ["+",["^",["+",z,y,ll,k],4],[sin,["+",s,f]],["^",c,4],["^",b,3],["^",a,2]]
________________________________
This shall give a expression tree sort of output. I tried searching a lot but there is no example I could find that could tell how trees are represented in functional languages, though there are plenty of examples for c/java etc. So, I tried this approach.
In case someone knows how trees are implemented in functional languages, please share some link/details.
__________________________________
/*These methods were discussed earlier but I am keeping it here to prevent the effort of re-search(in case one tries). It also has a subtle difference than earlier usage */
/*------------*/
assign_positions(lis):=block([ltemp2:[],count:-1],for item in lis do
if(listp(item)) then
(push([assign_positions(item),
[count:count+1]],ltemp2))
else (push([item,[count:count+1]],ltemp2))
,reverse(ltemp2))\$
/*------------*/
call_from_inside(lis):=block([olast:[],temp:0,final:[]],olast:from_inside(lis),reverse(final))\$
/*------------*/
from_inside(lis):=block([count:0],for item in lis do
(if(atom(first(item))) then
(if(olast=[]) then (push(item,final))
else (push([first(item),
flatten(endcons(last(item),reverse(olast)))
],final))) else (push(last(item),olast),
from_inside(first(item)),pop(olast))))\$
/*------------*/
​%in:  call_from_inside(assign_positions(tt));
%out: [["+",[0]],["^",[1,0]],["+",[1,1,0]],[z,[1,1,1]],[y,[1,1,2]],[ll,[1,1,3]],[k,[1,1,4]],[4,[1,2]],[sin,[2,0]],["+",[2,1,0]
],[s,[2,1,1]],[f,[2,1,2]],["^",[3,0]],[c,[3,1]],[4,[3,2]],["^",[4,0]],[b,[4,1]],[3,[4,2]],["^",[5,0]],[a,[5,1]],[2,[5,2]]]​

/* To see if it rhymes with "part" addressing,
expr:(z+y+k+ll)^4+a^2+b^3+c^4+sin(s+f);
part(expr,2,1,2); => f
part(expr,2,1,0); => +
___________________________________
Which shows that results are consistent. Here addressing it upto leaf level, so a user can easily make out what's maximum address available to be used. The output is "depth-first" and it shouldn't be difficult to read it "breadth-first" too based on positions. It can also help find other stats on tree say depth,size etc.

Here count for assignment is from "0" because of operators enlisted in lists while in case of simple lists discussed earlier it is from 1 as "[" need not be enlisted separately.
_____________________________________
/* Collecting subtrees from main tree */

call_collect_subtrees(lis):=block([temp:[]],collect_subtrees(lis),push(lis,temp))\$
/*------------*/
collect_subtrees(lis):=block(for item in lis do if(listp(item)) then (push(item,temp),collect_subtrees(item)) else push(item,temp))\$
/*------------*/
%in:: call_collect_subtrees(tt);
%out:: [["+",["^",["+",z,y,ll,k],4],[sin,["+",s,f]],["^",c,4],["^",b,3],["^",a,2]],2,a,"^",["^",a,2],3,b,"^",["^",b,3],4,c,"^",["^",c,4],f,s,"+",["+",
s,f],sin,[sin,["+",s,f]],4,k,ll,y,z,"+",["+",z,y,ll,k],"^",["^",["+",z,y,ll,k],4],"+"]

/* This will help in checking tree membership and specially if someone implements pattern sort of functionality no need to recurse through tree every time.
______________________________________
/*After someone has made some changes to the list, there is need to regenerate the expression */

call_create_exp(lis):=block([count:0,prev:[],tt1:lis,n_tt1],prev:tt1,
create_expr_outwards(tt1),
while(prev#tt1) do (prev:tt1,create_expr_outwards(tt1)),tt1)\$
/*---------*/
create_expr_outwards(lis):=block([],
if(listp(lis) and sublist(lis,listp)=[])
then
tt1:subst(apply(first(lis),rest(lis)),lis,tt1) else
(for item in lis do
if(listp(item))then
(create_expr_outwards(item))))\$
/*---------*/
%in :: f1:call_expr_tree(sin(x+y)*'integrate(x,x))
%out:: ["*",[integrate,x,x],[sin,["+",y,x]]]

%in:: subst(call_expr_tree(cos(w+d+diff(tan(x),x))),call_expr_tree(y+x),f1);
%out:: ["*",[integrate,x,x],[sin,[cos,["+",["^",[sec,x],2],w,d]]]]

%in:: call_create_exp(%);
%out:: integrate(x,x)*sin(cos(sec(x)^2+w+d))
___________________________________________
I have been suggested at times to write in lisp but I find it problematic to add appropriate headers at places in lisp code to make it compatible to Maxima though I am trying.

Please try these once and suggest improvements. I find these useful, can we use them in share with more modifications/additions needed? There could be an experimental code in share that users can contribute to and others can use at their own risk :P and suggest modifications !.

--
​-----​

Regards,
Pankaj Sejwal
________________________________________
"The more I read, the more I acquire, the more certain I am that I know nothing.” -
Voltaire