\section{The Positional Regime: Polish Notation}
%
%
%
It has been observed by {\L}ukasiewcicz in the 20ies that it is 
possible to write down unambiguously any formula without the use 
of brackets. All that needs to be done is to put the function symbol 
always first (alternatively: always last). So, rather than writing 
{\tt (x + y) + (z - 3)} one must write {\tt ++xy-z3}. This way of 
writing down formulae is known as Polish Notation. It has hardly 
gained much popularity except in some logical literature and in 
some pocket calculators, where the so--called Reverse Polish 
Notation was used, which differs from the Polish Notation in that 
the function symbol is put last rather than first. You first enter 
the arguments (say, first 7 and then 14) and then you press the 
function key (say, $\times$), rather than pressing first 7 then 
$\times$ and then 14. 

A note on our notation. We shall use typewriter font to denote true 
characters in print for a formal language. This helps to distinguish 
between a metavariable and a variable. For example, $x$ is a 
metavariable, but {\tt x} is a variable, used by the language itself. 
Moreover, concatenation is sometimes denoted by using the symbol 
$^{\smallfrown}$, especially when dealing with symbols that merely 
denote strings. Between true characters in print, however, 
$^{\smallfrown}$ is superfluous and omitted. 

An abstract definition of terms runs as follows. Let 
$F$ be a set of symbols, and $\Omega : F \pf \BN$ a function. 
The pair $\auf F, \Omega\zu$ is called a {\it signature}. 
We shall often write $\Omega$ in place of $\auf F, \Omega\zu$. 
$\Omega(f)$ is called the {\it arity\/} of $f$. 
%%
\begin{defn}
Let $\Omega$ be a signature. A {\bmi term} over $\Omega$ is 
defined inductively as follows. 
%%
\begin{enumerate}
\item
If $\Omega(f) = 0$, then $f$ is a term.
\item
If $\Omega(f) > 0$ and $t_i$, $i < \Omega(f)$, are terms, so 
is $f(t_0, \ldots, t_{\Omega(f)-1})$.
\end{enumerate}
\end{defn}
%%
Terms are represented in Polish Notation by strings over $F$. 
The set of terms is denoted by $T$. Define a mapping $^p$ 
from terms to strings over $F$ in the following way. 
%%
\begin{enumerate}
\item $t^p := t$, if $t \in F$ and $\Omega(t) = 0$. 
\item $(f(t_0, \ldots, t_{n-1}))^p := 
	f^{\smallfrown}t_0^p{^{\smallfrown}\ldots^{\smallfrown}%
		t_{n-1}^p}$, 
	if $n = \Omega(f) > 0$.
\end{enumerate}
%%%
We say that $\vec{x}$ {\it represents\/} $t$ if $t^p = \vec{x}$.
Furthermore, we shall write $\mbox{\it PN}_{\Omega}$ for the set of 
strings representing some $\auf F, \Omega\zu$--term. 
$\mbox{\it PN}_{\Omega}$ is context--free. Here is a grammar that 
generates it: 
%%
$$\begin{array}{l@{\quad \pf \quad}l}
\mbox{\tt S} & \mbox{\tt F}_0  \\
\mbox{\tt S} & \mbox{\tt SF}_1 \\
\mbox{\tt S} & \mbox{\tt SSF}_2 \\
\multicolumn{2}{c}{\ldots} \\
\mbox{\tt F}_0 & \mbox{\tt f}_0^1 \mid \mbox{\tt f}_0^2 \mid 
	\ldots \\
\mbox{\tt F}_1 & \mbox{\tt f}_1^1 \mid \mbox{\tt f}_1^2 \mid 
	\ldots \\
\mbox{\tt F}_2 & \mbox{\tt f}_2^1 \mid \mbox{\tt f}_2^2 \mid 
	\ldots \\
\multicolumn{2}{c}{\ldots} 
\end{array}$$
%%
(Here, $\mbox{\tt f}_i^j$ is a symbol for the $j$th function 
of arity $i$.)
Call this grammar $G_{\Omega}$.  We shall note some properties of 
this grammar. Before we can do so, we have to define a few notions 
from the theory of context--free languages. Given a grammar $G$, 
it assigns to a string $\vec{x}$ a set of derivations. In turn, 
each derivation defines a parse tree in the usual way (see 
\cite{harrison:formal}). $G$ is called {\it ambiguous\/} if 
there is a string that it assigned more than one parse tree. 
A language $L$ is context--free iff it is recognized by some 
nondeterministic pushdown automaton. $L$ is called {\it deterministic\/} 
iff it is recognized by some deterministic pushdown automaton.

Let $\vec{x}$ be string. A {\it substring occurrence\/} of 
$\vec{y}$ in $\vec{x}$ is a pair $\auf \vec{u}, \vec{v}\zu$ such that 
$\vec{x} = \vec{u} \vec{y}\vec{v}$. Given a parse tree (or analysis) 
$\CP$ of $\vec{x}$, we can associate with each node of the tree a 
substring occurrence of some substring of $\vec{y}$. Given 
$\CP$, such a substring occurrence is called a {\it constituent} of 
$\vec{x}$ under the analysis $\CP$. A constituent of $\vec{x}$ 
under the analyis $\CP$ which is not a constituent of $\vec{x}$ 
under $\CP$ is called an {\it accidental\/} constituent of $\vec{x}$ 
in $\CP$. Now, a context--free language is called {\it transparent\/}
if no constituent occurrence in a given string and analysis is 
accidental. 
%%
\footnote{This terminology as well as the results are due to Kit 
Fine (\cite{fine:transparency}).}
%%
From this a deterministic parser is easily constructed, 
for example using a shift--reduce parser. Just note that whenever it 
finds the right hand side of a rule on its stack, it can assume that 
this rule has been applied and it can reduce the stack using that rule. 
This shows that a transparent language is also deterministic. 
%%
\begin{thm}
\label{poltrans}
Let $\Omega$ be a signature. Then $G_{\Omega}$ is a context--free 
transparent grammar generating $\mbox{\it PN}_{\Omega}$. Consequently, 
$\mbox{\it PN}_{\Omega}$ is deterministic. 
\end{thm}
%%
One can show that each string represents at most one term. 
%%
\begin{prop}
Suppose that $\vec{x}$ represents $t$ and $s$. Then $t = s$. 
\end{prop}
%%
This follows from the transparency of the grammar and the fact 
that the parse trees are in one--to--one conrrespondence with 
the $\Omega$--terms. Now we shall establish the following terminology. 
%%
\begin{defn}
Let $\vec{x}$ be a string. $\vec{x}$ is called a {\bmi constituent} 
if it represents a term. If $\vec{x} = f\vec{y}_0\ldots \vec{y}_{n-1}$, 
we shall call $f$ the {\bmi head} of $\vec{x}$, and 
$\vec{y}_i$ the $i$th {\bmi argument} of $\vec{x}$.
\end{defn}
%%
The main advantage of Polish Notation is that it does not use any 
syncategorematic symbols, ie brackets. Its disadvantage is among 
other the complete regimentation of word order, and the fact that 
all arguments must be present. If we allow certain arguments to be 
dropped, ambiguity arises. Furthermore, a symbol has exactly 
one arity. If that is not the case, again ambiguities 
may arise. For example, let {\tt f} have arity 0 or 1 
and {\tt g} arity 2. Then the following string is 
ambiguous: {\tt gfff}. It may either represent $\mbox{\tt g}
((\mbox{\tt f}(\mbox{\tt f}), \mbox{\tt f})$ or 
$\mbox{\tt g}(\mbox{\tt f}, \mbox{\tt f}(\mbox{\tt f}))$. 
%%%
\footnote{In what is to follow we shall exclude that a symbol 
has more than one translation, in particular that it has more 
than one arity. Of course, there are examples in natural 
languages where this is not so, but if we disregard argument 
omission, this is actually a negligeable phenomenon for the 
purpose at hand.}

The semantics of such a language is also straightforward to 
define. 
%%
\footnote{Throughout this paper we shall ignore the question of 
typing. This will simplify the discussion considerably.}
%%
An $\Omega$--algebra is a pair $\auf A, I\zu$, where $A$ is a 
non--empty set and $I$ and function sending each $f \in F$ 
to a $\Omega(f)$--ary function on $A$. So, the symbol {\tt +} 
will denote a binary function on the set of numbers, while 
{\tt 0} denotes a 0--ary function on $A$ (ie a constant). 
A complete expression is a term without variables. 
The value of a complete expression is then simply an 
element of $A$. For example, the term $\times(\mbox{\tt +}(\mbox{\tt 3}, %
\mbox{\tt 5}),\mbox{\tt 7})$ is evaluated in the natural numbers 
(with the usual interpretation of {\tt +} and $\times$) to the 
number 56. Notice that terms such as $\times(\mbox{\tt +}(\mbox{\tt x}, %
\mbox{\tt 5}),\mbox{\tt 7})$ have no meaning since {\tt x} is a 
variable. 

Montague deviates from this picture in the following way. 
He starts with typed first--order logic and defines $\lambda$--terms 
on top of it. He assumes that there are only unary functions, 
whose values can also be functions rather than objects (Currying). 
In this way he gets full binary branching, but uses typing in an 
essential way. So, if $f$ is an $n$--ary symbol, the term 
$ft_0 \ldots t_{n-1}$ is computed by applying $f$ to $t_0$, the 
result to $t_1$ etc. So we are effectively computing the value 
of $(\ldots ((ft_0)t_1) \ldots )t_{n-1}$. In order to make this 
work for natural language, Montague deviates from linguistical 
practice and makes the object the functor in the VP and the 
subject the functor of the entire sentence. Even though the 
verb is the head (and therefore intuitively plays the role of 
$f$ here), it is an argument of the associated function of the 
object. This is necessitated by the need to give a compositional 
analysis of quantifiers. The noun {\sf eg} is translated into 
two distinct formulae, depending on whether it constitutes an 
object NP or a subject NP: 
%%
$$\lambda \CP. \exists x. \mbox{\sf cat}'(x) \und \CP(x), 
\qquad 
\lambda \CQ. \lambda y. \exists x. \mbox{\sf cat}'(x) \und 
\CQ(y)(x)$$
%%
The verb {\sf um} is translated by 
%%
$$\lambda x.\lambda y.\mbox{\sf chase}'(y,x)$$
%%
where --- finally --- $\mbox{\sf chase}'(y,x)$ means that 
$y$ is chasing $x$. 

If we assume the canonical regime with the functor last, only 
SOV languages are generated. So, only the sentences (\thesection.1) 
and (\thesection.2) are grammatical and they mean (\thesection.1a) 
and (\thesection.2a), respectively.
%%
\\[2mm]
\begin{tabular}{ll}
(\thesection.1) & {\sf eg ag um} \\
(\thesection.1a) & $\exists y.\exists x.\mbox{\sf cat}'(y) \und 
	\mbox{\sf dog}'(x) \und \mbox{\sf chase}'(y,x)$ \\
(\thesection.2) & {\sf ag eg um} \\
(\thesection.2a) & $\exists y.\exists x.\mbox{\sf dog}'(y) \und 
	\mbox{\sf cat}'(x) \und \mbox{\sf chase}'(y,x)$ \\
\end{tabular}
\\[2mm]
%%
In fact, Montague Semantics allows for more choices in the positional 
regime, but we shall be concerned here only with this case. 

If one wants to insist that the verb is the head of the construction, 
there is an easy fix. We raise the verb over its object and its 
subject and assume that it has the following meaning: 
%%
$$\lambda \CO. \lambda \CS. \CS (\CO(\lambda x. \lambda y. %
\mbox{\sf chase}'(y,x)))$$
%%
Here, $\CS$ is a variable over subject NPs and $\CO$ a variable 
ranging over object NPs. It is still the case that only SOV 
and VOS languages are generated, but now the semantics is in 
line with the syntactic analysis.  

We shall derive the translation of the sentence 
%%
\\[2mm]
\begin{tabular}{ll}
(\thesection.4) & {\sf A woman sees every man.}
\end{tabular}
\\[2mm]
%%
We start with {\sf sees every man}.
%%
$$\begin{array}{l}
(\lambda \CO. \lambda \CS. \CS (\CO(\lambda x. \lambda y. %
\mbox{\sf see}'(y,x))))(\lambda \CQ.\lambda y. \forall x. 
\mbox{\sf man}'(x) \pf \CQ(x)(y)) \\ 
\quad = \quad 
	\lambda \CS. \CS((\lambda \CQ.\lambda y.\forall x.\mbox{\sf man}'(x) 
	\pf \CQ(x)(y))(\lambda x.\lambda y.\mbox{\sf see}'(y,x))) \\
\quad = \quad  
	\lambda \CS. \CS(\lambda y.\forall x.\mbox{\sf man}'(x) \pf 
	\mbox{\sf see}'(y,x))) \\
\end{array}$$
%%
Next we apply this to {\sf some woman}.
%%
$$\begin{array}{l}
\lambda \CS. \CS(\lambda y.\forall x.\mbox{\sf man}'(x) \pf 
\mbox{\sf see}'(y,x)))(\lambda \CP.\exists x. 
\mbox{\sf woman}'(x) \und \CP(x)) \\
\quad = \quad 
(\lambda \CP.\exists x. \mbox{\sf woman}'(x) \und \CP(x)) 
(\lambda y.\forall x.\mbox{\sf man}'(x) \pf \mbox{\sf see}'(y,x)) \\
\quad = \quad 
\exists x.\mbox{\sf woman}'(x) \und 
\forall x'.\mbox{\sf man}'(x') \pf \mbox{\sf see}'(x,x') 
\end{array}$$
%%
So, this generates the desired result. 
