Left-justify with align on "=" in align environment

The alignat environment from amsmath can manage that.

\documentclass{article}
\usepackage{amsmath}

\begin{document}
  \begin{alignat}{2}
    & e(x)                &&= x\\
    & e(M N)              &&= e(M) e(N)\\
    & e(\lambda x:\tau.M) &&= \lambda x:\tau.e(M)\\
    & e(\lambda\_:\tau.M) &&= \lambda x:\tau .e(M)  (x \notin FV(M))
  \end{alignat}
\end{document}

You could use an array:

\documentclass{article}
\begin{document}
\[\begin{array}{ll}
e(x)      &= x\\
e(M N)    &= e(M) e(N)\\
e(\lambda x:\tau.M) &= \lambda x:\tau.e(M)\\
e(\lambda\_:\tau.M) &= \lambda x:\tau .e(M)  (x \notin FV(M))\\
\end{array}\]
\end{document}

If the spacing is too far apart, use @ separators for the column specifications, e.g., \begin{array}{l@{\,}l}

According to the manual, the lhsTeX poly environment uses the polytable package internally. So I maybe that package provides the table format you are looking for.