Is there a concise/existing way to denote the expressive power of "lambda calc without using parentheses/tree-of-expressions/application-order-restructuring anywhere"?

Can you do without them/reinvent them? Does it break completely (i.e, even with a naive no-more-parentheses, you're using them implicitly, like when naming things)? Does it become completely trivial/boring?

I haven't tried very hard, but I feel like I couldn't express something like

$\lambda x y z . x y (x z)$

without using parentheses somewhere.

  • $\begingroup$ Are we allowed to write $\lambda xyz.xyz$ even if $xyz$ is $((xy)z)$ ? what about $(\lambda x. x(\lambda y. y))$ ? I can't understand exactly what would you allow. $\endgroup$ – chi Mar 28 '17 at 16:54
  • $\begingroup$ Yes, you couldn't. What would you replace parenthesis with? The lack of parenthesis in some lambda expressions are based on some conventions (like precedence or associativity). Strictly speaking -i.e. if you forget about conventions-, every lambda expression has parenthesis. $\endgroup$ – Euge Mar 28 '17 at 17:49

Answer 1

The best answer to this question is: This is the wrong question to ask! Let me explain.

The fact that we write down expressions (in $\lambda$-calculus or anywhere else) as sequences of symbols is a convenience and tradition established by humans. From a theoretical point of view the strings of symbols are not the optimal way of representing expressions. Instead, abstract syntax trees are.

Abstract syntax trees do not require any parentheses. Parentheses are there only because we use a particular way of writing things. There is nothing deep in having or not having parenthesis. Your question then boils down to the following: "Suppose we use a notation which requires parentheses, but then we remove parenthesis, what happens?" This is not a mathematically interesting question. It can be answered, but it's irrelevant for $\lambda$-calculus. The answer might be interesting, but it will not reveal anything about parentheses. Instead, it will reveal something about abstract syntax trees of a certain shape.

Were you born in a slightly different universe, where everyone used reverse Polish notation then you would not have known that there is such a thing as parentheses.

Let me put it another way. It is a convention that in $\lambda$-calculus we write $a\,b\,c$ to mean $(a\,b)\,c$. Without such a convention we would always have to write parentheses everywhere, all the time. The first person to establish the convention could have picked the other one, so that $a\,b\,c$ would mean $a\,(b\,c)$. Then your question would have a different answer because of some person who picked a convention a long time ago.

Answer 2

It is not entirely clear where you think parentheses are needed, but let's suppose that

  1. application is left-associative, so that $x y z = (x y) z$, and
  2. $\lambda$-abstraction has lower precedence than application, and it binds as much as it can, so that $\lambda x . x y z$ and $(\lambda x . x y) z$ are different expressions.
  3. You think that $x \lambda y . y$ is not a valid expression because it should be written as $x (\lambda y . y)$. That is, a $\lambda$-abstraction in an aplication must always be parenthesized.

Under these conditions, we cannot ever write any $\beta$-redeces (because we would have to apply a $\lambda$-abstraction). So any expression must be of the form $\lambda x_1 . \lambda x_2 . \ldots \lambda x_n . M$, possibly with $n = 0$, where $M$ is of the form $y_1 y_2 \ldots y_m$ for some variables $y_1, \ldots, y_m$ (which may be equal to the $x_i$'s).

If anyone can say anything interesting about this fragment of $\lambda$-calculus, I'd be interested to hear.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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