Again, I'm trying to understand Martin Henson's "Elements of Functional Languages." He talks about "maximal free expression." For example,
M of EXP is a maximal free expression of N of EXP iff M is a free expression of N, and whenever M is a proper subexpression of M', M' is not a free expression of N.
And then comes the exercise:
Identify the free and maximal free expressions of λxy.xzy(zwx)(wwzyw)
I cannot envision what an expression is in this context. So if x + y +2z is an expression, would x + y be a subexpression thereof?
. . . and no, I'm not a student. This is all just independent research for someone who has coded but not truly understood. . . .
Best Answer
In general a subexpression is a part of an expression that corresponds to a subtree in the parse tree -- that is, some node in the parse tree plus all of its descendants. The subexpression is a proper subexpression if it is not the enitre expression.
One often works with abstract syntax trees that have no nodes for semantically empty constructs such as parentheses-for-grouping. So in "$(\lambda x.x y)$", the expression "$x y$" is a proper subexpression, and "$\lambda x.x y$" is a subexpression that may or may not be considered proper depending on the purpose at hand.
On the other hand, $\lambda x.x$ is not a subexpression of $\lambda x.x y$, because the only common ancestor of the two $x$s in the parse tree is the lambda-abstraction node, which also has $y$ as a descendant.
For your example $x+y+2z$, what this means in practice depends on the particular grammar of the expressions you're studying, since $x+y+2z$ can parse either as $(x+y)+2z$ or $x+(y+2z)$. Mathematics doesn't care which it is, since addition is associative, but computer science does. Programming languages in general tend to be defined such that it means $(x+y)+2z$ (because, among other things, this allows a smooth extension to expressions with subtractions like $a+b-c-d+e-f$, such that they end up meaning what they usually do in mathematics). In that case $x+y$ is indeed a subexpression of $x+y+2z$.