CS603 Organization of Programming Languages
Due 23 January 2004

University of Alabama
Department of Computer Science
Spring 2004


The purpose of this assignment is to provide an opportunity for you to become acquainted with the basic use of our interpreters and to do some programming in the Impcore language. In particular, this exercise should be a refresher in the use of recusion for solving number theoretic problems.

Problem Description

Do Exercises 1-4 on pages 47-48 of the textbook, as given below. Use recursion; it will be good practice for when we cover Scheme.
  1. (sigma $m$ $n$) $= m + (m + 1) + \cdots + n$. When $m>n$, the behavior of sigma is unspecified; your implementation may do anything you like.
  2. (exp $m$ $n$) $= m^{n} (m,n, \ge 0)$. (log $m$ $n$) is the least integer $l$ such that $m^{l+1} > n (m > 1, n> 0)$.
  3. choose $n$ $k$k is the number of ways of selecting $k$ items from a collection of $n$ items, without repetitions, $n$ and $k$ non-negative integers. This quantity is called a binomial coefficient and is notated $\left( \begin{array}{cc} n \\ k \end{array}\right)$. It can be defined as $\frac{n!}{k!(n-k)!}$, but the following identities are more helpful computationally: $\left( \begin{array}{cc} n \\ 0 \end{array}\right) = 1 (n \ge 0)$, $\left( \begin{array}{cc} n \\ n \end{array}\right) = 1 (n \ge 0)$, and $\left( \begin{array}{cc} n \\ k \end{array}\right) = \left( \begin{array}{cc} n...
...rray}\right) + \left( \begin{array}{cc} n-1 \\ k-1 \end{array}\right) (n,k > 0)$.
  4. (fib $m$) is the $m$th Fibonacci number. The Fibonacci numbers are defined by the identities:
    (fib $0$)$= 0$, (fib $1$)$=1$, and for $m>1$, (fib $m$)$=$(fib $m-1$)$+$ (fib $m-2$).

How to Run the Interpreter

As a graduate student, you have access to the lab in EE121. You can also use your Bama account or any other machine if you desire, but you are responsible for compiling the interpreters. From a DOS prompt, you can either invoke the Impcore program to run an interactive session:
    -> (+ 2 3)
or you can create a file mp1.txt with the text:
    (+ 2 3)
and use IO redirection:
    C:\MSC_EXE>chap1 < mp1.txt
    -> 5

How to Turn In the Program

Your program will be extracted and executed programatically. Therefore, it is critical that the following instructions be followed exactly. Email the source code to me as a single attachment, named MP1.imp. In your email, set the subject line to ``CS603MP1''. The attachment should contain your name, set out as a comment. For example:
; Joel Jones
(define add1 (x) (+ x 1))

About this document ...

CS603 Organization of Programming Languages
Due 23 January 2004

This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.61)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -nonav MP1.tex

The translation was initiated by on 2004-01-16