Exploring NLP in Oz/Mozart

Torbjörn Lager, 2001

Introduction

This is a first course in programming for computational linguistics. We use the programming language Oz and its implementation Mozart to learn about relational and functional programming. No previous programming experience is required, but some background in mathematical methods in linguistics is necessary. In fact, examples and exercises are often carefully selected to illustrate such methods. Furthermore, we take a problem-solving approach to programming, based on Simon Thompson's adaptations of George Pólya's ideas for "How To Solve It".

Course Plan

Lectures

• Lecture 1: Procedures in Oz. Relations and functions. Lists, numbers, strings. Conditionals (if-then-else). Library procedures. Using higher order functions for mapping, filtering and accumulating. The Oz development environment.
• Lecture 2: A problem-solving approach to program development. Pattern matching. Recursive list processing. The Oz debugger.
• Lecture 3: Choice and Search. Indeterministic programming. Relation to logic. Examples from parsing and knowledge representation. Search trees. The Oz Explorer. A quick look at Prolog.
• Lecture 4: Simple higher order functions. More about anonymous procedures (lambda expressions etc.). Examples from compositional semantics.
• Lecture 5: Records. More about unification. Examples from unification-based grammars.

Relation to other courses

Exercises and Projects

Exercises

• Introductory exercises
• Mapping, sorting and filtering: Working with strings and higher order functions
• Elementary recursive list processing
• Trees, tuples and recursion
• Records and recursion
• Working with procedures
• Working with dictionaries
• Reading and writing from/to files and URLs
• Building command line applications in Oz

More Exercises

• Warmup exercises (Constructed by Per Brand, Nils Franzén, Dragan Havelka, Erik Klintskog and Anna Neiderud at SICS).

Projects

• Project I: Building a Palindrome Recognizer
• Project II: Building a Frequency Listing Tool
• Knowledge representation and reasoning in Oz NB: This project is actually part of the course in Mathematical Methods in Linguistics.
• A grammar for a fragment of English (complete with compositional semantics). NB: This project is actually part of the course in Mathematical Methods in Linguistics.
• Unification and unification-based grammars. NB: This project is actually part of the course in Mathematical Methods in Linguistics.

Relevant Reading

Course Notes and Papers

• How To Solve It. George Pólya, 1957
• How To Program It. Simon Thompson
• How To Program It in Oz
• Notes on Computing the Length of a List
• Notes on Reversing a List
• Notes on Reading and Writing to Files
• Beskow, Björn and Nivre, Joakim (1994) Kompositionell Logisk Semantik. Institutionen för lingvistik, Göteborgs universitet.
• Lager, Torbjörn (2001) Kompositionell Logisk Semantik i Oz. Institutionen för lingvistik, Stockholms universitet.
• Top Ten Things To Take With You From This Course

Tutorials and text books

• Tutorial of Oz (chapter 1-6). Read this and wamp up with the warmup exercises.
• Oz text book: Peter van Roy and Seif Haridi "Concepts, Techniques and Models of Computer Programming" (most of it too advanced for this course). The most recent draft is always available at: http://www.info.ucl.ac.be/~pvr/book.pdf
• Oz NLP text book: Denys Duchier, Claire Gardent and Joachim Niehren "Concurrent Constraint Programming in Oz for Natural Language Processing" (most of it too advanced for this course.)
• Note that the course book by Partee et al. is relevant for this course too!

Documentation (a selection)

• The Oz Base Environment
  • Lists
  • Strings
  • Characters
  • Records
  • Dictionaries
• System Modules
  • Files
  • Basic Search
• The Oz Programming Interface

Relevant Links

• MOGUL: the MOzart Global User Library, the NLP section