<p>I am interested, whether, in some programming language, there can be something like a <a href="https://en.wikipedia.org/wiki/Donkey_sentence" rel="nofollow noreferrer">Donkey Sentence</a>, a sentence that defies straightforward attempts to translate it into a formal language, but is nevertheless meaningful?</p>
<p>An example of a Donkey Sentence is &quot;<em>Every farmer who owns a donkey beats it.</em>&quot;, a straightforward attempt to translate it into a formal language would be:<br/>
<span class="math-container">$$\forall x. (\mathrm{FARMER}(x) \land \exists y. (\mathrm{DONKEY}(y) \land \mathrm{OWNS}(x, y)) \to \mathrm{BEAT}(x, y))$$</span></p>
<p>But that's not a valid sentence (&quot;y&quot; at the end is out of scope).</p>
<p>A correct translation seems to be:</p>
<p><span class="math-container">$$\forall x. \forall y. ((\mathrm{FARMER}(x) \land \mathrm{DONKEY}(y) \land \mathrm{OWNS}(x, y)) \to \mathrm{BEAT}(x, y))$$</span></p>
<p>But it's not obvious how it follows from the syntax of the sentence (notice that the translation says &quot;all donkeys&quot;, whereas the original sentence says &quot;a donkey&quot;).</p>
<p>In my <a href="https://flatassembler.github.io/PicoBlaze/PicoBlaze.rtf" rel="nofollow noreferrer">Bachelor Thesis</a>, on page 13, I claim that there isn't. However, given how diverse programming languages are, I am not really sure. Can there be such a sentence in some declarative (rather than imperative) language?</p>
<p>Sentences such as &quot;<em>More people have been to Russia than I have.</em>&quot; (that seem acceptable at first although they are ungrammatical) obviously can exist in programming languages: ungrammatical expression <code>5**</code>, in the first versions of <a href="https://flatassembler.github.io/compiler" rel="nofollow noreferrer">my AEC-to-x86 compiler</a>, passed through the parser (producing the AST <code>(* 5 *)</code>) and crashed the compiler. Sentences such as &quot;<em>Time flies like an arrow.</em>&quot; (where without context it is unclear which word is of which type and so can be parsed in different ways because of that) can also exist in some programming languages, that's what's the <em>typedef problem</em> is about. So I am wondering whether Donkey Sentences can exist in some programming language.</p>

<parsing><semantics>
Can something like a Donkey Sentence exist in a programming language?
CC BY-SA 4.0
2023-06-09T16:57:51.750Z
You can certainly create statements that don't do anything useful but but the example you give seems more like a bug
mousetail 'he-him'
CC BY-SA 4.0
2023-06-09T16:59:06.933Z
I don't see two different ways of parsing "time flies like an arrow", but "fruit flies like a banana" definitely has two possible meanings.
kaya3
CC BY-SA 4.0
2023-06-09T17:00:50.153Z
Could you add an example of a donkey sentence to the question? The linked Wikipedia article is helpful, but it would be better if people don't have to read an external source to understand the question.
DLosc
CC BY-SA 4.0
2023-06-10T00:31:23.747Z
My favourite one is "I saw the man on the hill with the telescope".
Bruce Adams
<p>These sentences remind me of an odd infelicity with existential types in Haskell. The <span class="math-container">$\texttt{length}$</span> function has the type <span class="math-container">$\forall α.[α]\to \text{Int}$</span>, but it could also be given the type <span class="math-container">$(\exists α.[α])\to \text{Int}$</span>. One way of looking at this is that <span class="math-container">$\forall α$</span> is like a function parameter (literally true in System F), while <span class="math-container">$\exists α.T(α)$</span> is like a pair <span class="math-container">$(α,T(α))$</span>, and so the translation from the <span class="math-container">$\forall$</span> to the <span class="math-container">$\exists$</span> form is like uncurrying.</p>
<p>But if you try this with <span class="math-container">$\texttt{head} :: \forall α.[α]\to α$</span>, you get <span class="math-container">$$* \; \texttt{head} :: (\exists α.[α])\to α$$</span> which has a dangling type variable. And yet... it makes sense, doesn't it? The caller gets an <span class="math-container">$α$</span> back, and it knows what <span class="math-container">$α$</span> is because it passed it to <span class="math-container">$\texttt{head}$</span> in the first place.</p>
<p>This is not legal Haskell, so it may not count as an example. But arguably it should be legal, somehow.</p>
<p>If you write the type in continuation-passing style, <span class="math-container">$\forall α.[α]\to (α\to r)\to r$</span>, then it can become <span class="math-container">$(\exists α.[α]\mathbin{\&amp;}(α\to r))\to r$</span>, avoiding the problem.</p>

CC BY-SA 4.0
2024-05-21T18:11:47.950Z
2024-05-21T18:11:47.950Z
benrg
<p>In programming languages, it's possible for a program to match multiple productions in the grammar, which would seem to make it ambiguous. The more complex the language grammar, the more likely it is to have conflicting productions like this.</p>
<p>For instance, in C++ there's the notion of a <a href="https://en.wikipedia.org/wiki/Most_vexing_parse" rel="nofollow noreferrer">most vexing parse</a>, because similar syntax is used for declaring a variable with an initial value and declaring a function:</p>
<pre><code>int i(int(my_dbl));
</code></pre>
<p>This could be equivalent to either of</p>
<pre><code>int i = (int)my_dbl; // variable whose initial value is my_dbl converted to int
int i(int my_dbl);   // function with integer parameter named my_dbl
</code></pre>
<p>In natural languages we generally resolve ambiguities using common sense -- semantics feeds back into the parser, and we reject nonsensical parses. E.g. in &quot;fruit flies like a banana&quot;, it doesn't make sense for &quot;flies&quot; to be a verb, because neither fruit nor bananas fly.</p>
<p>In language design, a simple solution is to prioritize the productions, so the first match in the priority list takes precedence. The grammar designer can make an arbitrary decision. Notice that in the above example, there are alternate, unambiguous syntaxes that produce the same result, so nothing is lost by picking one as the interpretation.</p>
<p>So nothing is truly ambiguous, it's clear from the grammar which interpretation will be used. This contrasts with natural language ambiguities, since &quot;common sense&quot; depends on the experience of the speaker and audience -- misunderstandings may occur if there's a disconnect (imagine someone who doesn't know that there's an insect called &quot;fruit fly&quot; -- &quot;fruit flies like a banana&quot; will be meaningless to them).</p>
<p>Since the programmer may not intuitively realize that they're using ambiguous syntax (there have been many Stack Overflow questions due to this), a helpful compiler can recognize this condition and produce a warning message.</p>

CC BY-SA 4.0
2024-05-21T20:49:06.720Z
2024-05-21T20:49:06.720Z
Barmar
<p>Per <a href="https://en.wikipedia.org/wiki/Donkey_sentence" rel="noreferrer">Wikipedia</a>:</p>
<blockquote>
<p>Barker and Shan define a donkey pronoun as &quot;a pronoun that lies outside the restrictor of a quantifier or the if-clause of a conditional, yet covaries with some quantificational element inside it, usually an indefinite.&quot;[3]</p>
</blockquote>
<p>The sentence <em>&quot;Every farmer who owns a donkey beats it&quot;</em> seems to be a prototypical example. Here the pronoun &quot;it&quot; refers to the donkey that the farmer owns, but this pronoun occurs outside of the clause <em>&quot;farmer who owns a donkey&quot;</em> in the parse tree of the sentence where its referent exists.</p>
<p>So, can programming languages have sentences like this? In a trivial sense, the answer is no ─ a &quot;donkey sentence&quot; is defined by the use of a variable outside of its scope, and that is definitively an error. But this is tautological; the scope of a name <em>means</em> the places that name can be used.</p>
<p>A more interesting way of looking at it is whether the scope of some names can be expanded so that they can be used in more places, allowing the language to express things like donkey sentences can in natural language. Put another way, in a donkey sentence the pronoun refers to something outside of the clause where that pronoun's referent is declared, but the pronoun still has meaning outside of that clause because its scope <em>is</em> broader than the parse tree would suggest.</p>
<p>Consider pattern matching:</p>
<pre class="lang-rust prettyprint-override"><code>match donkey {
    Some(d) if farmer.owns(d) =&gt; assert!(farmer.beats(d)),
    _ =&gt; {},
}
</code></pre>
<p>Here the name <code>d</code> is declared in the pattern <code>Some(d) if farmer.owns(d)</code>, and used in the expression <code>farmer.beats(d)</code> which is not a sub-expression of that pattern. That is, the pattern declaring <code>d</code> and the expression using <code>d</code> are separate, non-overlapping nodes in the parse tree. But nonetheless the language defines that the scope of a variable bound in a pattern includes the right-hand-side of the <code>match</code> arm where that pattern occurs, and hence <code>d</code> is in scope where it is used.</p>
<p>So it seems to be subject to interpretation whether this is really analogous to a donkey sentence, but also I'm not sure there is much value for programming language designers in figuring that out. Maybe it's a more interesting question for linguists or philosophers interested in correspondences between natural and artificial languages.</p>

CC BY-SA 4.0
2023-06-09T18:08:23.783Z
2023-06-10T01:12:24.940Z
2023-06-10T01:12:24.940Z
kaya3
CC BY-SA 4.0
2023-06-10T12:21:46.323Z
The value would lie in the fact that most beginner programmers try to use a local variable after it has left its scope. Donkey sentences make sense in real life. Learning that they don't in programming can be difficult.
shawnhcorey
CC BY-SA 4.0
2023-06-10T14:35:14.933Z
@shawnhcorey Sure, there is value in widening the scope of variables so they can be used in more places, so long as widening the scope makes sense to do so. What I don't see much value in is figuring out whether code which makes use of such wider scopes is really "like a donkey sentence" or not; that's a philosophical point.
kaya3
CC BY-SA 4.0
2023-06-10T18:33:26.577Z
You missed the part about beginner programmers. Humans can easily parse Donkey Sentences. That is why beginners programmers often make this mistake. If a compiler can figure out how to do the same thing, it would be easier to learn programming.
shawnhcorey
CC BY-SA 4.0
2023-06-10T19:25:21.477Z
@shawnhcorey I didn't miss that part. Beginner programmers won't benefit from a debate over whether a particular scoping rule is "like a donkey sentence", any more than they would benefit from a debate over how many angels can dance on the head of a pin.
kaya3
CC BY-SA 4.0
2023-08-12T06:42:32.357Z
@shawnhcorey Beginner programmers make lots of mistakes, like `if a == "foo" or "bar":` when it should be `if a == "foo" or a == "bar":`, because they expect the programming language to be parsed like English. So unless your objective is to design a language that's more English-like (e.g. COBOL) so that beginners are less likely to make mistakes like this, it's not clear how interesting this is.
Barmar
<p>I'm not sure this is answering your question but...</p>
<h2>Programming languages are generally designed to be unambiguous</h2>
<p>With the exception of some <a href="https://esolangs.org/wiki/Main_Page" rel="nofollow noreferrer">esoteric languages</a> programming language are generally designed to have one unique interpretation* <sup>(at least per compiler)</sup></p>
<p>Programming languages are to give instructions to a computer.
Unlike human languages they do not normally contain any intentional ambiguity.</p>
<h4>C++</h4>
<p>C++ has a <a href="https://en.wikipedia.org/wiki/Most_vexing_parse" rel="nofollow noreferrer">Most_vexing_parse</a> which is ambiguous at the pure syntax level.
You can't tell if a symbol is a variable or function in certian forms but this only lasts until you can place it in the symbol table.
C++ compilers often feed information back into the lexical and syntactic stages to do with this.
C++ has a context sensitive grammar but its interpretion is still unambiguous
(caveat deliberately undefined behaviour).</p>
<h4>Prolog</h4>
<p>Prolog is a logic language whose operation is to search through a space of predicates. For instance if you construct a predicate to solve the <code>https://en.wikipedia.org/wiki/Eight_queens_puzzle</code>. Say:</p>
<pre><code>queens(a,b,c,d,e,f,g,h): 
   ...
</code></pre>
<p>It has 92 solutions so it seems ambiguous. But this predicate will typically give you each one in turn in a deterministic order so it doesn't really qualify.</p>

CC BY-SA 4.0
2023-06-10T00:28:21.403Z
2023-06-13T01:13:05.187Z
2023-06-13T01:13:05.187Z
Bruce Adams
CC BY-SA 4.0
2024-06-23T01:48:29.173Z
A more extreme version of C++'s most vexing parse is Perl 5's bareword arity heuristic BEGIN dependency. As explained in http://modernperlbooks.com/mt/2009/08/on-parsing-perl-5.html, begin blocks can define functions which then change the parsing arity of later code. Since Perl allows dynamically defining functions, this makes it possible to define programs where the resulting parse tree is dependent on the results of Turing complete runtime code execution.
user1937198
# Can something like a Donkey Sentence exist in a programming language?
Posted by: username_0 on 2023-06-09
I am interested, whether, in some programming language, there can be something like a [Donkey Sentence](https://en.wikipedia.org/wiki/Donkey_sentence), a sentence that defies straightforward attempts to translate it into a formal language, but is nevertheless meaningful?

An example of a Donkey Sentence is "*Every farmer who owns a donkey beats it.*", a straightforward attempt to translate it into a formal language would be:  
$$\forall x. (\mathrm{FARMER}(x) \land \exists y. (\mathrm{DONKEY}(y) \land \mathrm{OWNS}(x, y)) \to \mathrm{BEAT}(x, y))$$

But that's not a valid sentence ("y" at the end is out of scope).

A correct translation seems to be:

$$\forall x. \forall y. ((\mathrm{FARMER}(x) \land \mathrm{DONKEY}(y) \land \mathrm{OWNS}(x, y)) \to \mathrm{BEAT}(x, y))$$

But it's not obvious how it follows from the syntax of the sentence (notice that the translation says "all donkeys", whereas the original sentence says "a donkey").

In my [Bachelor Thesis](https://flatassembler.github.io/PicoBlaze/PicoBlaze.rtf), on page 13, I claim that there isn't. However, given how diverse programming languages are, I am not really sure. Can there be such a sentence in some declarative (rather than imperative) language?

Sentences such as "*More people have been to Russia than I have.*" (that seem acceptable at first although they are ungrammatical) obviously can exist in programming languages: ungrammatical expression `5**`, in the first versions of [my AEC-to-x86 compiler](https://flatassembler.github.io/compiler), passed through the parser (producing the AST `(* 5 *)`) and crashed the compiler. Sentences such as "*Time flies like an arrow.*" (where without context it is unclear which word is of which type and so can be parsed in different ways because of that) can also exist in some programming languages, that's what's the *typedef problem* is about. So I am wondering whether Donkey Sentences can exist in some programming language.
**Tags:** parsing semantics
> **Comments:**
> **username_1**: You can certainly create statements that don't do anything useful but but the example you give seems more like a bug  
> **username_2**: I don't see two different ways of parsing "time flies like an arrow", but "fruit flies like a banana" definitely has two possible meanings.  
> **username_3**: Could you add an example of a donkey sentence to the question? The linked Wikipedia article is helpful, but it would be better if people don't have to read an external source to understand the question.  
> **username_4**: My favourite one is "I saw the man on the hill with the telescope".  
---
## 4 answers
### Answer by username_2 on 2023-06-09. Score: 9 | Accepted answer
Per Wikipedia:

Barker and Shan define a donkey pronoun as "a pronoun that lies outside the restrictor of a quantifier or the if-clause of a conditional, yet covaries with some quantificational element inside it, usually an indefinite."[3]

The sentence "Every farmer who owns a donkey beats it" seems to be a prototypical example. Here the pronoun "it" refers to the donkey that the farmer owns, but this pronoun occurs outside of the clause "farmer who owns a donkey" in the parse tree of the sentence where its referent exists.
So, can programming languages have sentences like this? In a trivial sense, the answer is no ─ a "donkey sentence" is defined by the use of a variable outside of its scope, and that is definitively an error. But this is tautological; the scope of a name means the places that name can be used.
A more interesting way of looking at it is whether the scope of some names can be expanded so that they can be used in more places, allowing the language to express things like donkey sentences can in natural language. Put another way, in a donkey sentence the pronoun refers to something outside of the clause where that pronoun's referent is declared, but the pronoun still has meaning outside of that clause because its scope is broader than the parse tree would suggest.
Consider pattern matching:
match donkey {
    Some(d) if farmer.owns(d) => assert!(farmer.beats(d)),
    _ => {},
}

Here the name d is declared in the pattern Some(d) if farmer.owns(d), and used in the expression farmer.beats(d) which is not a sub-expression of that pattern. That is, the pattern declaring d and the expression using d are separate, non-overlapping nodes in the parse tree. But nonetheless the language defines that the scope of a variable bound in a pattern includes the right-hand-side of the match arm where that pattern occurs, and hence d is in scope where it is used.
So it seems to be subject to interpretation whether this is really analogous to a donkey sentence, but also I'm not sure there is much value for programming language designers in figuring that out. Maybe it's a more interesting question for linguists or philosophers interested in correspondences between natural and artificial languages.
> **Comments:**
> **username_7** (2023-06-10): The value would lie in the fact that most beginner programmers try to use a local variable after it has left its scope. Donkey sentences make sense in real life. Learning that they don't in programming can be difficult.  
> **username_2** (2023-06-10): @shawnhcorey Sure, there is value in widening the scope of variables so they can be used in more places, so long as widening the scope makes sense to do so. What I don't see much value in is figuring out whether code which makes use of such wider scopes is really "like a donkey sentence" or not; that's a philosophical point.  
> **username_7** (2023-06-10): You missed the part about beginner programmers. Humans can easily parse Donkey Sentences. That is why beginners programmers often make this mistake. If a compiler can figure out how to do the same thing, it would be easier to learn programming.  
> **username_2** (2023-06-10): @shawnhcorey I didn't miss that part. Beginner programmers won't benefit from a debate over whether a particular scoping rule is "like a donkey sentence", any more than they would benefit from a debate over how many angels can dance on the head of a pin.  
> **username_6** (2023-08-12): @shawnhcorey Beginner programmers make lots of mistakes, like `if a == "foo" or "bar":` when it should be `if a == "foo" or a == "bar":`, because they expect the programming language to be parsed like English. So unless your objective is to design a language that's more English-like (e.g. COBOL) so that beginners are less likely to make mistakes like this, it's not clear how interesting this is.  
---
### Answer by username_4 on 2023-06-10. Score: 7
I'm not sure this is answering your question but...
Programming languages are generally designed to be unambiguous
With the exception of some esoteric languages programming language are generally designed to have one unique interpretation* (at least per compiler)
Programming languages are to give instructions to a computer.
Unlike human languages they do not normally contain any intentional ambiguity.
C++
C++ has a Most_vexing_parse which is ambiguous at the pure syntax level.
You can't tell if a symbol is a variable or function in certian forms but this only lasts until you can place it in the symbol table.
C++ compilers often feed information back into the lexical and syntactic stages to do with this.
C++ has a context sensitive grammar but its interpretion is still unambiguous
(caveat deliberately undefined behaviour).
Prolog
Prolog is a logic language whose operation is to search through a space of predicates. For instance if you construct a predicate to solve the https://en.wikipedia.org/wiki/Eight_queens_puzzle. Say:
queens(a,b,c,d,e,f,g,h): 
   ...

It has 92 solutions so it seems ambiguous. But this predicate will typically give you each one in turn in a deterministic order so it doesn't really qualify.
> **Comments:**
> **username_8** (2024-06-23): A more extreme version of C++'s most vexing parse is Perl 5's bareword arity heuristic BEGIN dependency. As explained in http://modernperlbooks.com/mt/2009/08/on-parsing-perl-5.html, begin blocks can define functions which then change the parsing arity of later code. Since Perl allows dynamically defining functions, this makes it possible to define programs where the resulting parse tree is dependent on the results of Turing complete runtime code execution.  
---
### Answer by username_5 on 2024-05-21. Score: 1
These sentences remind me of an odd infelicity with existential types in Haskell. The $\texttt{length}$ function has the type $\forall α.[α]\to \text{Int}$, but it could also be given the type $(\exists α.[α])\to \text{Int}$. One way of looking at this is that $\forall α$ is like a function parameter (literally true in System F), while $\exists α.T(α)$ is like a pair $(α,T(α))$, and so the translation from the $\forall$ to the $\exists$ form is like uncurrying.

But if you try this with $\texttt{head} :: \forall α.[α]\to α$, you get $$\* \; \texttt{head} :: (\exists α.[α])\to α$$ which has a dangling type variable. And yet... it makes sense, doesn't it? The caller gets an $α$ back, and it knows what $α$ is because it passed it to $\texttt{head}$ in the first place.

This is not legal Haskell, so it may not count as an example. But arguably it should be legal, somehow.

If you write the type in continuation-passing style, $\forall α.[α]\to (α\to r)\to r$, then it can become $(\exists α.[α]\mathbin{\&}(α\to r))\to r$, avoiding the problem.
---
### Answer by username_6 on 2024-05-21. Score: 0
In programming languages, it's possible for a program to match multiple productions in the grammar, which would seem to make it ambiguous. The more complex the language grammar, the more likely it is to have conflicting productions like this.
For instance, in C++ there's the notion of a most vexing parse, because similar syntax is used for declaring a variable with an initial value and declaring a function:
int i(int(my_dbl));

This could be equivalent to either of
int i = (int)my_dbl; // variable whose initial value is my_dbl converted to int
int i(int my_dbl);   // function with integer parameter named my_dbl

In natural languages we generally resolve ambiguities using common sense -- semantics feeds back into the parser, and we reject nonsensical parses. E.g. in "fruit flies like a banana", it doesn't make sense for "flies" to be a verb, because neither fruit nor bananas fly.
In language design, a simple solution is to prioritize the productions, so the first match in the priority list takes precedence. The grammar designer can make an arbitrary decision. Notice that in the above example, there are alternate, unambiguous syntaxes that produce the same result, so nothing is lost by picking one as the interpretation.
So nothing is truly ambiguous, it's clear from the grammar which interpretation will be used. This contrasts with natural language ambiguities, since "common sense" depends on the experience of the speaker and audience -- misunderstandings may occur if there's a disconnect (imagine someone who doesn't know that there's an insect called "fruit fly" -- "fruit flies like a banana" will be meaningless to them).
Since the programmer may not intuitively realize that they're using ambiguous syntax (there have been many Stack Overflow questions due to this), a helpful compiler can recognize this condition and produce a warning message.
---
