Programming Languages - Fall 2011

Homework 2 Solution

The biggest design decision that had to be made for this homework was which type of string you would use to represent your numbers. I chose to use Ada.String.Unbounded.Unbounded_String, which I imported into the main namespace so I wouldn't have to type that repeatedly. A good alternative is to use bounded strings whose lengths are dynamically computed at the top of each function. The least desirable solution is to hardcode a single maximum length for all strings. What happens if a user supplies you an input longer than your string type? Any code which used fixed-length strings should at least check for this error condition.

-- use unbounded strings as the representation of arbitrary length/base numbers  
with Ada.Strings.Unbounded;
use Ada.Strings.Unbounded;
with Ada.Strings.Unbounded.Text_IO;
with Ada.Text_IO; 
with Ada.Command_line; 
with Ada.Assertions; 

procedure hw2 is
  -- need this package to read unbounded strings from a file 
  package UIO renames Ada.Strings.Unbounded.Text_IO; 
  -- use Text_IO both for file reading and printing regular strings 
  package IO renames Ada.Text_IO; 
  -- need command_line to get filename 
  package CL renames Ada.Command_line; 

Some of the submissions had very long case statements mapping to/from every character and its numerical value. It's way tidier to use Character'Pos and Character'Val to convert between characters and their ASCII values.

  -- takes a number, returns an equivalent character
  -- Character'Val maps ascii codes to character
  -- Character'Pos maps characters to their ascii codes
  function Nat_to_Char(N : Natural) return Character is 
  begin 
    if N <= 9 then return Character'Val(N + Character'Pos('0'));
    else return Character'Val(N - 10 + Character'Pos('A')); 
    end if; 
  end Nat_to_Char; 

I created an exception 'Invalid_Character' which gets raised whenever a character of an input string is something other than '0'-'9' | 'a'-'f' | 'A' - 'F'. However you handle this sort of error, somewhere in your code you should be validating that all characters fall within the valid range. Further down there is additional verification that the value of each character doesn't exceed the base.

  -- exception that gets raised on characters outside the '0'.. 'F' range
  Invalid_Character : exception;
  -- takes a character representing a number in base 16, returns its value
  function Char_to_Nat(C : Character) return Natural is 
    Ascii_Code : Natural := Character'Pos(C);
  begin 
    case C is
      when 'A' .. 'F' => return 10 + Ascii_Code - Character'Pos('A');
      when 'a' .. 'f' => return 10 + Ascii_Code - Character'Pos('a');
      when '0' .. '9' => return Ascii_Code - Character'Pos('0');
      when others => raise Invalid_Character; 
    end case; 
  end Char_to_Nat;

My implementation of addition might differ slightly from your but the underlying logic should be similar. Traverse the two number strings from least to most significant digits, adding each digit pair and carrying any value greater than the base to the next position.

  
  -- indexes into strings from right to left
  -- returning 0 if you go past the leftmost boundary 
  function Elem_to_Nat(S : Unbounded_String; Index : Positive) return Natural is 
    RevIndex : Integer := Length(S) - Index + 1; 
  begin 
    if RevIndex > 0  then return Char_to_Nat(Element(S, RevIndex));
    else return 0; 
    end if;
  end Elem_to_Nat;
      
  function Reverse_String(S : Unbounded_String) return Unbounded_String is
    N : Natural := Length(S); 
    Rev : Unbounded_String := S; 
  begin 
    for I in Positive Range 1 .. N loop 
      Replace_Element(Rev, I, Element(S, N - I + 1)); 
    end loop; 
    return Rev; 
  end Reverse_String; 
  
  -- to add two arbitrary length integers, loop through the elements of
  -- of strings, adding each pair of elements and carrying result/Base
  -- to the next position
  function Add(X, Y : Unbounded_String; Base : Positive) return Unbounded_String is 
    -- Elem_Sum is where we stick the result of adding two single-digit numbers
    -- may exceed the base so it will get split into one digit of the result and a carry
    Elem_Sum : Natural := 0;
    Carry : Natural := 0;
    Sum : Unbounded_String := Null_Unbounded_String;
  begin 
    -- adds from least to most significant positions, 
    -- appending to a result string in reverse
    for I in Positive range 1 .. Natural'Max(Length(X), Length(Y)) loop
      Elem_Sum := Elem_To_Nat(X, I) + Elem_To_Nat(Y, I) + Carry;
      Append(Sum, Nat_To_Char(Elem_Sum mod Base)); 
      Carry := Elem_Sum / Base; 
    end loop; 
    -- don't forget the last carry
    if Carry > 0 then Append(Sum, Nat_to_Char(Carry)); end if; 
    -- since we've been accumulating from right to left, 
    -- now we reverse the Sum string to get our result 
    return Reverse_String(Sum); 
  end Add; 

To multiply I add X to itself as many times as the value of Y. I implement this as recursion where each subsequent recursive call gets a Y string 1 less in value. I'm not totally happy with either this code or algorithm, email me if yours came out cleaner.

  Zero : Unbounded_String := To_Unbounded_String("0"); 
  One : Unbounded_String := To_Unbounded_String("1"); 

  -- subtract 1 from the arbitrary length natural encoded as a string 
  function Sub1(X : Unbounded_String; Base : Natural) return Unbounded_String is
    N : Natural := Length(X);
    Result : Unbounded_String := X; 
    CurrDigit : Natural; 
  begin
    if X = One then return Zero; end if; 
    -- scan from right to left until you find a non-zero position, 
    -- then decrement it 
    for I in reverse 1 .. N loop
       CurrDigit := Char_to_Nat(Element(X, I)); 
       -- if a digit is 0, we're going to borrow from further right 
       -- and replace it with last single digit number 
       if CurrDigit = 0 then Replace_Element(Result, I, Nat_to_Char(Base-1));
       elsif CurrDigit = 1 and I = 1 then Delete(Result, 1, 1); exit; 
       else
         -- replace current character with char representation 
         -- of the digit - 1
         Replace_Element(Result, I, Nat_to_Char(CurrDigit - 1)); 
         exit; 
       end if;
    end loop; 
    return result; 
  end Sub1; 

  -- multiply by recursively adding X 
  -- every recursive call takes a value of Y which is one smaller 
  function Mult(X, Y: Unbounded_String; Base : Positive) return Unbounded_String is
  begin 
    if Y = Zero or X = Zero then return Zero; 
    elsif Y = One then return X;
    else return Add(X, Mult(X, Sub1(Y, Base), Base), Base); 
    end if; 
  end Mult; 

No character's value in a string should exceed the base (for example, "023" is not a binary string). Something like this simple loop should happen after each string gets loaded.

  -- check every character of a string to ensure that it is within the appropriate range 
  procedure Validate_Base(X : Unbounded_String; Base : Positive) is
  begin 
    for I in 1 .. Length(X) loop 
      Ada.Assertions.Assert(Char_to_Nat(Element(X, I)) < Base, "character greater than base");       
    end loop; 
   end Validate_Base; 
  

The body of the main procedure should be easy to understand. The only exotic thing going is that I use the Command_line package to read in the input filename. Many of you hardcoded your the filename as something like "input.txt", which is fine.

  File : IO.File_Type;
  BaseStr : Unbounded_String := Null_Unbounded_String;
  Base : Natural; 
  X : Unbounded_String := Null_Unbounded_String; 
  Y : Unbounded_String := Null_Unbounded_String; 

begin
   -- make sure the filename has been given as a commandline arg
  Ada.Assertions.Assert(CL.Argument_Count /= 0, "file name not given"); 
   -- also assert that no additional args were given
  Ada.Assertions.Assert(CL.Argument_Count < 2, "too many arguments"); 
  IO.Put("Reading triplets from file: ");
  IO.Put_Line(CL.Argument(1));
  IO.Open (File => File, Mode => IO.In_File, Name => CL.Argument(1));
                     
   -- loop through all triplets in the file   
  loop 
    -- read base 
    BaseStr := UIO.Get_Line(File);  
    Base := Natural'Value(To_String(BaseStr));
    Ada.Assertions.Assert(Base <= 16, "invalid base"); 
    exit when Base = 0; 
     
    -- print "Base b"
    IO.Put("Base "); 
    UIO.Put_Line(BaseStr); 
	 
    -- read two numbers 
    X := UIO.Get_Line(File);
    Y := UIO.Get_Line(File);

     -- ensure inputs are well formed 
    Validate_Base(X, Base); 
    Validate_Base(Y, Base); 

    -- print "x + y = sum" 
    UIO.Put(X);
    IO.Put(" + "); 
    UIO.Put(Y); 
    IO.Put(" = "); 	 
    UIO.Put_Line(Add(X, Y, Base)); 

    -- print "x * y = product"
    UIO.Put(X);
    IO.Put(" * "); 
    UIO.Put(Y); 
    IO.Put(" = "); 	 
    UIO.Put_Line(Mult(X, Y, Base)); 

    exit when IO.End_Of_File(File); 
  end loop; 
  IO.Close(File => File);
end hw2;