G22.2110 Spring 1998
Project - Part III
Due Date: 07/30/98
This project comes in 2 parts, the first part focuses on Object-Oriented programming in Ada 95, while the second part illustrates functional programming in ML.
I. Object-Oriented Programming in Ada 95
The goal of this first part is to get familiar with the data type support in Ada 95. In particular, it illustrates Ada 95's fundamental support for composite data types, and its support for abstract data types using private types and generics.
Write an Ada program to encode a message using a simple substitution cipher, where each letter of the message is replaced by a different letter using a lookup table. The lookup table is generated using a keyword; the letters of the keyword are used for the first few positions in the table (ignoring any repeated letters) and the remaining letters of the alphabet are used to complete the table in alphabetical order. The output should be displayed in groups of five letters, all in upper case, with the last group padded out with Xs. For example, if the keyword is JABBERWOCKY, the lookup table will be as follows:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Encoded as: J A B E R W O C K Y D F G H I L M N P Q S T U V X Z
Note that B occurs twice in the keyword so the keyword actually appears as JABERWOCKY in the table, and the remaining letters of the alphabet (D, F, G, etc.) are then used to fill up the rest of the table. The message "Cabbages and kings" would be encoded as BJAAJ ORPJH EDKHO PXXXX using this table.
One of the remaining shortcomings in the Ada type system is that if a numeric type is declared to represent physical values such as lengths in metres, the inherited multiplication operator will multiply two lengths to produce another length. In reality, multiplying metres by metres gives square metres.
Produce a package to represent the dimensioned physical quantities by recording the dimensions of mass (in kilogram), length (in metres) and time (in seconds) involved together with the magnitude of the quantity. For example, acceleration is measured in metres per second squared (m s-2), so the dimensions are 0 for mass, 1 for length and -2 for time.
Provide a set of arithmetic operators for dimensioned quantities. They can only be added or subtracted if the dimensions match (so you can't add density and acceleration); they can be multiplied or divided by multiplying or dividing the magnitudes and adding or subtracting the corresponding dimensions.
Modify the dimensioned units package from part b so that the dimensions are specified by a discrete type supplied as a generic parameter. The dimensions can be represented as an array of integers whose index subtype is the supplied discrete type. For example, the original package used dimensions of mass, length and time; this could be handled by instantiating the new package with an enumeration type consisting of the three values (Mass, Length, Time).
II. Functional Programming in ML
ML is a relatively new language that provides a combination of features offering users a great deal of programming ease. ML is primarily a functional language, meaning that the basic mode of computation is the definition and application of functions. ML expressions are free of side-effects, and ML supports higher-order functions (i.e., functions that take functions as arguments), polymorphism, abstract data types, recursion, rule-based programming, and strong typing.
For the second part of this project, we focus on the mechanics of using a particular implementation of ML, called Standard ML of New Jersey (SML/NJ). Software and documentation for ML may be downloaded from http://cm.bell-labs.com/cm/cs/what/smlnj. The software is already installed on the department sun network, and a version of SML/NJ is also available for PCs running Microsoft Windows. The most recent version of SML/NJ has been implemented to conform to the recent ML97 standard. To run SML/NJ in interactive mode, in response to the UNIX prompt type "sml". To terminate an SML/NJ session, type "<CTRL>d".
1. The goal of this first question is to provide you with a rudimentary view of what ML programs look like. Using the SML/NJ in interactive mode and the web documentation, familiarize yourself with the simplest form of programming in ML, where one types expressions to the ML system and receives back values for these expressions. You should learn how to construct expressions using atomic types such as integers, reals, booleans, strings, and characters. In the process, you should experiment with various ML operators (arithmetic, string, comparison, logical values combination), and if-then-else expressions. You will find that ML assigns a unique type to every expression, and that operators have particular types that they require their operands to have. You should also study expressions involving lists and ML's simple form or record structure called "tuples". When you are done experimenting, answer the following simple questions.
a. What is wrong with the following ML expression "8/4", "if 0 then 1 else 2"? What are the errors, and how might one fix them?
b. Are (1,2) and (1,2,3) the same type? Are [1,2] and [1,2,3] the same type? Please explain.
c. Using ML operators, is it possible to convert a string of length one into the character of that string? Please show how to accomplish this transformation.
2. After the first question, you should know everything there is to know about ML, except how to program! The goal of the second question is to help you learn about defining and using functions. Essentially, all programming in ML is conducted by the definition of functions and the application of these functions to arguments. In particular, ML uses functions in places where more traditional languages use iteration. To experiment with ML functions, you will write a "Pig Latin" translator using ML.
The simple rule for translating into Pig Latin is to take a word that begins with a vowel and add "yay", while taking any word that begins with one or more consonants and transferring them to the back before appending "ay". For example, "able" becomes "ableyay" and "stripe" becomes "ipestray". Write a function that converts a string of letters into its Pig-Latin translation. You should use "explode" and the ML function that tests for vowels suggested in the hints below.
Hint1: Write a ML function that takes a list of characters and returns true if the first element is a vowel and false if not. Use the wildcard symbol "_" to represent anonymous or wildcard variables whenever possible in the patterns.
Hint2: ML provides several ways to support the conversion from strings to characters. The conversion is not so straightforward for strings that are not of length one. In particular, ML provides the "explode" operator, which converts a string to a list of characters.