This project shows how to code permutation function in Chicken Scheme. Basically, Chicken is a compiler for Scheme Programming Language. It is very easy to learn if you know Haskell or other functional programming languages.

• Install Chicken Scheme (https://www.call-cc.org/)
• Chicken can be used as an interpreter

> csi
> (load "a1.scm")
; loading a1.scm ...

• Or as a compiler

> csc -o a1 a1.scm

Implement a Scheme function permute to print all permutations of a given list of any length.

For example:

\> (permute '(a e d))
(a e d)
(a d e)
(e a d)
(e d a)
(d a e)
(d e a)
#f

\> (permute '())
#f

\> (permute '(a))
(a)
#f

Implement a Scheme function to compute path lengths (distances) in weighted directed graphs.

Scheme/Lisp lists, or s-expressions, give us a very easy way to represent a directed graphs. We'll use the association list convention here (but in general, you could also use other simple conventions).

We'll do the following to represent a weighted graph using incidence lists. A graph is an association list of (nodename . out-edges) pairs. Each nodename is just any unique symbol that identifies a node. Each out-edge is another association list of incident outgoing-edges, each of which is represented by a (destination-nodename . weight) pair. Each destination-nodename is a symbol that identifies the destination node. Each weight is a number.

For example:

(define g
  '((a . ((b . 5) (c . 8) (d . 3)))
   (b . ((a . 4) (c . 7)))
   (c . ((a . 2) (b . 6) (c . 2) (d . 9)))
   (d . ((b . 1) (c . 4)))))

We'll use weights that are positive integers representing the length or distance between any two points.

Write a function path-length that calculates the total sum of weights along any given path represented as a list of nodenames. Also write a convenient variation distance that lets you pass paths as a variable number of nodename arguments.

For example:

\> (path-length g '(a c d b c))
25

\> (distance g 'a 'c 'd 'b 'c)
25

\> (distance g 'c 'c)
2

\> (distance g 'd 'a)
#f

Notice that cycles are allowed, and distance must return #f if the path does not exist in the graph.

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).

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.

COMP 4221 - Natural Language Processing in HKUST