Can something like a Donkey Sentence exist in a programming language?

Question

I am interested, whether, in some programming language, there can be something like a 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, 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, 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.

Answer 1

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.

Answer 2

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.

Answer 3

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 4

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.