Seminar on Computational Semantics with Haskell

In this seminar, I'm trying to teach my student some computational semantics using van Eijck and Unger's book.

Solution to Exercise 3

Solution to part 1. The following is a bottom-up version:

• BUStackParser.hs

More Problems on Parsing

Exercise 4

1. Improve the efficiency of transS in Section 9.8 (Adding Semantics) by eliminating calls to bInLF, as we did with lfSent from Section 6.2 (Predicate Logic as Representation Language).
2. Rewrite the code in Section 9.8 (Adding Semantics) using higher-order abstract syntax for LF.
3. Write semantic interpretation functions for the HOAS version of LF.

Parsing

Recursive Descent

The various parsers in this chapter are all deterministic simulations of a particular kind of non-deterministic pushdown automaton associated with context-free grammars. There are three well-known types of non-deterministic pushdown automata for CFGs that are used as bases of parsing: top-down, bottom-up, and left-corner (see here for more information). The one that's used here is the top-down variety, and the corresponding parsing method is also called "recursive descent". It is particularly natural in the context of functional programming. (Note that the term "stack-based" is often used to describe parsing based on NPDA.)

Read more …

Solution to Exercise 1

"Top-down" and "bottom-up" on LF do not completely correspond to "top-down" and "bottom-up" on syntactic trees of English. The direction of flow of information sometimes gets reversed in English trees. With the bottom-up approach, the DET needs to receive information both from the RCN and the VP, so the information from the VP has to first get passed to the NP, and then from the NP to the DET.

• Exercise1.hs

Extension and Intension

Montague's Typing in PTQ

The mapping \[ \alpha \mapsto \overline{\alpha}, \] which replaces each occurrence of \(e\) and \(t\) by \(s \rightarrow e\) and \(s \rightarrow t\), and the associated intensionalization and extensionalization operators (\({}^{\cap}\) and \({}^{\cup}\)) is not familiar to linguists. In linguistics, a common practice nowadays is to use the fewest instances of \( s \) as are necessary for adequate semantic analysis, rather than systematically replacing each occurrence of an atomic type by its intensional counterpart.

Read more …

Model Checking with Predicate Logic

Representation of Predicate Logic Variables

The book uses a combination of a string and an integer as a representation of a variable in first-order logic. An alternative is to use a Haskell variable. In this approach, a quantified formula consists of the constructor for the quantifier and a function from terms to formulas. In other words, we treat \[ \forall x\: \varphi \] as a shorthand for \[ \forall (\lambda x.\varphi), \] where the \(\lambda\)-abstract is a real function, not an expression. The local variable in the function definition plays the role of the bound variable.

Read more …

Errors

• Page 132, Section 6.2 (Predicate Logic as Representation Language): The result of executing lf2 is wrong.
• Page 171, Section 7.4 (Reducing Expressions of Typed Logic): "Alpha reduction" is usually called "alpha conversion". The formulation of eta reduction given here is incorrect. This is just a special instance of beta reduction. It should be corrected as follows:

  Eta reduction: \( (\lambda v \mapsto (E\: v)) \stackrel{\eta}{\longrightarrow} E \)
  Condition: \( v \) is not free in \( E \).

• Page 196, Section 8.4 (Intensionalization): The recursive clause for the definition of \( \overline{\alpha} \) should be corrected as follows: \[ \overline{\alpha} = \overline{\alpha_1 \rightarrow \alpha_2} = \overline{\alpha_1} \rightarrow \overline{\alpha_2}. \]
• Page 214, Exercise 9.7, Section 9.2 (Recognizing and Parsing Context-Free Languages):The recognizer and parser in this section does loop in the face of left recursion. For example, with a grammar for the Dyck language,

  module Ptest where
  
  import P
  
  recognizeDyck :: String -> Bool
  recognizeDyck = \xs ->
  	null xs || or [ recognizeDyck ys | ["a",ys,"b"] <- splitN 3 xs ] || or [ recognizeDyck ys && recognizeDyck zs | (ys,zs) <- split2 xs ]
  

  we get non-termination for "abab".

  *Ptest> recognizeDyck "ab"
  True
  *Ptest> recognizeDyck "abab"
    ^C ^CInterrupted.
  *Ptest>
  

• Section 9.7 (Handling Extraction): The implementation of the recursive-descent parser for sequentially indexed grammars given in this section is incorrect. See Parsing.

Last modified: 2018-04-05 16:49:54 JST