Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

1 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$.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.