COMP 4221 Assignment 2 - Fall 2015

Fall 2015, COMP 4221 Introduction to Natural Language Processing
Lecture 1, MW 10:30-11:50, LTF
Prof. Dekai WU, Rm 3539, 2358-6989, dekai@cs.ust.hk

Due: 2015.11.30 at 23:00 by CASS

Assignment page: http://www.cs.ust.hk/~dekai/4221/assignments/a2.html

Part 1

Extend your Scheme function permute from A1, to implement a new function anagram that takes an additional argument consisting of a list of symbols representing legal words. Your new function will print all permutations of a given list of any length, such that appending the symbols in the permuted list gives a legal word.

For example:

> (define dictionary '(a act ale at ate cat eat etc tea))
> (anagram dictionary '(a e t))
(a t e)
(e a t)
(t e a)
#f
> (anagram dictionary '(a t c))
(a c t)
(c a t)
#f
> (anagram dictionary '(a))
(a)
#f
> (anagram '() '(a e t))
#f
>

(Hint: You may wish to recall some potentially useful standard functions like symbol->string, string->symbol, string-append, etc.)

Notice that anagram always returns #f. The legal permutations must be displayed to standard output, not returned. This is to avoid building enormous lists in memory (consider how many permutations there are of a list of length 10).

Part 2

Consider the following my-or macro:

(define-macro my-or
  (lambda (x y)
    `(if ,x ,x ,y)))

For simple cases, this works fine:

> (my-or 1 2)
1
> (my-or #f 2)
2
>

But what happens here?

> (define i 0)
> (my-or
  (begin
    (set! i (+ i 1))
    #t)
  2)
> i

We can try to solve the problem thus:

(define-macro my-or
  (lambda (x y)
    `(let ([temp ,x])
       (if temp temp ,y))))

But now what happens?

> (define temp 3)
> (my-or #f temp)

Re-implement the my-or macro, in a way that avoids this variable capture problem from using define-macro, by instead using define-syntax to invoke Scheme's built-in `hygienic' and `referentially transparent' macro system.

Important reminders

Your final submitted version must run on the version of Chicken Scheme in Lab 2. You may only use any SRFIs that were taught in lecture.

Place your entire assignment in one well-organized and documented file named a2.scm.

Your proper software engineering skills are being graded. Your programming style (how clearly and how well you speak Scheme) is what will be graded. Correct functioning of your program is necessary but not sufficient!

You must write the final version of the program on your own. Sophisticated plagiarism detection systems are in operation, and they are pretty good at catching copying! If you worked in study groups, you must also acknowledge your collaborators in the write-up for each problem, whether or not they are classmates. Other cases will be dealt with as plagiarism. Re-read the policy on the course home page, and note the University's tougher policy this year regarding cheating.

---

dekai@cs.ust.hk
Last updated: 2015.11.17