Multi-Paradigm Programming in Oz for
Natural Language Processing

Torbjörn Lager

Recent Updates

• New exercises
  • Working with cells
  • Working with procedures has been expanded
• New project suggestions
  • A State Machine Toolkit for Dialogue Processing

   

Old Updates

• Deny's slides from his GBG talk
• Deny's slides about managing data in Oz 
• Constraint Programming For Natural Language Processing.

Introduction

In this course, we use the programming language Oz and its implementation Mozart to explore multi-paradigm programming for natural language processing. So, what's the point? See here for my view on this!

What You Could Do Before this Course Starts

1. Download and Install Oz/Mozart (or perhaps already installed on your ThinkPad?)
2. Start reading the van Roy & Haridi book
3. Browse the documentation
4. Start doing some of the simple exercises below

Schedule/Course Plan

[Details still subject to change]

Handouts etc.

• Torbjörn's slides
• Code samples
  

Exercises

Simple Exercises

Many of the following exercises were developed to suit complete programming novices. Depending on your background, you may therefore find many of them more or less trivial. However, getting acquainted with a new programming language through solving 'the usual stuff' in it is probably a good idea. Also, you are not expected to submit all of them for evaluation, only the ones that are marked as such, and they are usually a bit more challenging.

• 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 cells
• Working with dictionaries
• Reading and writing from/to files and URLs

For your convenience, here are some shortcuts to the documentation that should be sufficient for solving the above exercises:

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

More Difficult Exercises

• More Higher Order Programming
• Relational Programming
• ...

Practical Exercises

• Building CLI applications in Oz
• Building CGI applications in Oz
• Building GUI applications in Oz

Larger Exercises

• A Frequency Lister
• Knowledge representation and reasoning in raw Oz
• A raw Oz grammar for a fragment of English
• Unification and unification-based grammars

Even More Exercises

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

Book Exercises

Running out of exercises? Don't forget that the van Roy and Haridi book contains exercises as well! And so does the draft book by Duchier, Gardent and Niehren.

Roll Your Own Exercises

Your help in designing more interesting exercises would be greatly appreciated! Send the exercises, complete with your own ideas of good solutions, to lager@ling.gu.se

Deny's Exercises

Projects

As part of the examination of this course, you are required to hand in a project. The level of difficulty should match your current programming skill and experience. Ideally, you are able to implement something relevant to your master's thesis project. In case you're not sure what to do, you may want to consider the suggestions listed below.

Library/Toolkit Projects

• Viterbi Tagging Library
• N-Gram Statistics Package
• WordNet Library
• Common Sense Database
• Functional Morphology
• A PC-Kimmo interface
• Categorial Grammar Tools
• A State Machine Toolkit for Dialogue Processing
• Grammar Development Environment
• A GATE-like thingy...
• NL (Surface) Generator(s)
• Wirén Style Incremental Chart Parser
• Dialogue Grammar Toolkit
• A Transformation-Based Learner
• Lexicon Maintenance Tools
• Tools for building automata and transducers
• Named-Entity Recognizer
• Anaphora Resolution Module

Demo Projects

• Adventure in Oz
• Enhancing a Chat System
• Computational Semantics
• Godis in Oz

Existing Resources

A number of components that you may want to make use of in your own projects.

Components in the Mogul

• Transformation-Based Tagger (Mogul entry)
• Text Classifier (Mogul entry)
• Simple Sentence Splitter (Mogul entry)
• Simple Tokenizer (Mogul entry)
• Gump-Based Tokenizer (Mogul entry)
• Edit Distance Meter (Mogul entry)
• Porter Stemmer (Mogul entry)
• Dependency Grammar Parser (Mogul entry)
• Transformations on context free grammars (Mogul Entry)
• Parsing with unification grammars (Mogul Entry)
• Parsing with typed unification grammars (Mogul Entry)
• TkDag (Mogul Entry)

Other Components - not (yet) in the Mogul

• Chart Parsers
• Parse Trees

Relevant Readings

Text books

• Oz text book: Peter van Roy and Seif Haridi "Concepts, Techniques and Models of Computer Programming" 
• Oz NLP text book: Denys Duchier, Claire Gardent and Joachim Niehren "Concurrent Constraint Programming in Oz for Natural Language Processing".
• Denys Duchier. Constraint Programming For Natural Language Processing. Lecture Notes, ESSLLI 2000, August 2000.

Relevant Links

• MOGUL: the MOzart Global User Library, the NLP section
• ALICE: A new statically typed language interoperating with Oz.
• Lightweight Languages Workshop 2002. Look and listen at the webcasted talk "Concurrency Oriented Programming in Erlang" by Joe Armstrong (starts 1.30 minutes into the morning session). You'll need a Real player to view these streams. Slides (PDF)

Examination

The following is required:

• Solutions to selected exercises. However, when an exercise is too simple given your background, I would prefer that you send in something else instead. If an exercise is too difficult, you just have to work harder :-)
• One project per student, complete with documentation (manual, report etc.) One project may be replaced with a course paper, dealing with more theoretical aspects of multi-paradigm programming for NLP.