Ada for C/C++ Developers: Linked List

This installment in my Ada tutorial series is designed to show how to use records, pointers and exceptions.  Every C and C++ programmer probably remembers one of the first milestones in coming to grasp with pointers is the successful implementation of the linked list data structure.

First of all, after analyzing the source code of other Ada code on the Internet, it seems that the preferred method for naming variables and functions is The_Name and not TheName; use underscores instead of camel case.  Also make sure you use uppercase at the beginning of a word too.  This seems to be Ada style, so we might as well adopt it.

The program below should speak for itself, but I’ll just mention a few things.

  • Records like structures in C, and that is all there is to them.  In C++ structures are really just classes and the keyword is only there for C language compatibility.
  • Recursive data structures, such as lists and trees, require forward declaration of the types.  See the program below for details, but this should not be too much of a shock as C++ requires the same unless your working with templates, and even then…
  • Exceptions will be covered more in a later tutorial, but I thought I would add it to the linked list code just to demonstrate the concept.
  • The type keyword is also introduced, but we will cover it later.  For now just know that it declares a new data type.
  • Pointers in Ada are declared using the access keyword.  I particularly like this keyword, because if you read the code, it makes sense in English.  For example,  “type Link is access Node;” can be read “type Link is access to a Node.”
  • Pointers in Ada are implicitly dereferenced. If you want to explicitly dereference the pointer, use Ptr.all, but let’s not worry about it for now.
  • GNAT implements garbage collection, so we can create objects and let the run-time worry about cleaning up the memory.  Note that Ada implementations are not required to support garbage collection, and most have options for disabling the garbage collection.
  • Finally, not-equal is /=, but due to Ada’s readability, you can probably figure that out from the code

So, with no further delay, the source code is below.  I did test it with some simple scenarios, but I did not exhaustively test every possibility.  (possible unit testing topic in the future?)  Hopefully there are no bugs!

with Ada.Text_IO; use Ada.Text_IO;

procedure ListMech is
   --
   -- Define the list data structures
   --   Note: recursive data structs require forward declaration
   type Node;			-- forward declare
   type Link is access Node;	-- read literally: a "Link" accesses a "Node"

   type Node is			-- now declare the Node type
      record
         Node_Id: Integer;	-- prefer underbar to camel-case
         Next:    Link;
      end record;

   type List is
      record
         Head:   Link;		-- first node in list
         Tail:   Link;		-- last node in list
         Length: Integer := 0;	-- number of nodes in the list
      end record;

   Empty_Exception: exception;

   --
   -- Inserts an ID into the linked list
   --
   procedure Insert( Id: in Integer; Linked_List: in out List) is
   begin
      if Linked_List.Head = null then
         Linked_List.Head := new Node'(Id, null);
         Linked_List.Tail := Linked_List.Head;
         Linked_List.Length := 1;
         Put_Line("List empty => creating head node: " & Integer'Image(Id));
      else
         Put_Line("Creating node: "  & Integer'Image(Id));
         Linked_List.Tail.Next := new Node'(Id, null);
         Linked_List.Length := Linked_List.Length + 1;
         Linked_List.Tail := Linked_List.Tail.Next;
      end if;
   end Insert;

   --
   -- Removes and ID from the linked list (if available)
   --
   procedure Remove( Id: in Integer; Linked_List: in out List ) is
      Curr_Link: Link := Linked_List.Head;
      Prev_Link: Link := null;
      Found_Flag: Boolean := False;
   begin
      -- make sure list is not empty
      if Linked_List.Head = null then
         raise Empty_Exception;
      end if;

      while Curr_Link /= null loop
         if Curr_Link.Node_Id = Id then
            Put_Line("Removing node: "  & Integer'Image(Curr_Link.Node_Id));
            if Curr_Link = Linked_List.Head then
               Linked_List.Head := Curr_Link.Next;
            else
               Prev_Link.Next := Curr_Link.Next;
            end if;
            Found_Flag := true;
            Linked_List.Length := Linked_List.Length - 1;
            exit;
         else
            Prev_Link := Curr_Link;
            Curr_Link := Curr_Link.Next;
         end if;
      end loop;

      if Found_Flag /= true then
         Put_Line("Node not in list: "  & Integer'Image(Id));
      end if;
   end Remove;

   --
   -- Traverses the linked list and prints out the IDs at each node
   --
   procedure Walk( Linked_List: in List ) is
      Link_Index: Link := Linked_List.Head;
   begin
      Put_Line("Walking the list(" & Integer'Image(Linked_List.Length)& "): ");
      loop
         exit when Link_Index = null;
         Put_Line("--> " & Integer'Image(Link_Index.Node_Id));
         Link_Index := Link_Index.Next;
      end loop;
   end Walk;

   -- local variables
   Id_List: List;
   TestVector: array(Positive range <>) of Integer := (1, 2, 3, 4, 5);

begin

   for Index in TestVector'Range loop
      Insert( TestVector(Index), Id_List );
   end loop;
   New_Line;
   Walk( Id_List );
   New_Line;
   Remove( 1, Id_List );
   New_Line;
   Walk( Id_list );
   New_Line;
   for Index in TestVector'Range loop
      Remove( TestVector(Index), Id_List );
   end loop;

   -- list should be empty now
   New_Line;
   Remove( 9, Id_List );

exception
      when Empty_Exception => Put_Line("*** List is empty ***");
end ListMech;

The code is significantly longer this time, but I think we’re ready to move away from trivial programs.  After all, we’re programmers, right?  We fear nothing!

C:\work\ada\listmech>listmech.exe
List empty => creating head node:  1
Creating node:  2
Creating node:  3
Creating node:  4
Creating node:  5

Walking the list( 5):
-->  1
-->  2
-->  3
-->  4
-->  5

Removing node:  1

Walking the list( 4):
-->  2
-->  3
-->  4
-->  5

Node not in list:  1
Removing node:  2
Removing node:  3
Removing node:  4
Removing node:  5

*** List is empty ***

Copy the source code into an editor and try it out for yourself.  I am a better programmer than I was when I started with C++ years ago, but it felt very easy to develop this linked list code.  I’m starting to appreciate the verbosity of the syntax, the rigidity of the compiler, and the elegance of the language.  I hope you’re enjoying our endeavor too.

Ada for C/C++ Developers: Development Environments

Lessons Learned: Get them fresh off the boat

(Skip this anecdote if you want to get straight to work the info)

When I first started learning C/C++, it was just out of curiosity and I didn’t want to spend any money on expensive compilers.  Visual C++ and Borland C++ Builder were not cheap for a secondary school student; after all, I had just spent $30 a C++ book.  Luckily the book came with a floppy disk containg the example code and a copy of Borland Turbo C++ 4.5, an older MS-DOS C++ compiler.  It was perfect for someone like myself just getting started, and with that tool I was able to explore the world of programming: console apps, pointers, linked lists and all of that good stuff.

Back then Borland was a really popular compiler vendor, but at some point Microsoft tipped the scale and stole the developer tools market.  One reason that Microsoft took over is that Visual Basic proved to be easier than Delphi (“Visual Pascal”) for new programmers in the corporate world.  Another very important reason, however, is that Microsoft went after the future developers through outreach programs in academia.  When I entered the university, Microsoft sold a bundled package of Microsoft Office Professional and Microsoft Visual Studio 6.0 to incoming students for $99. All the software that we would need during our four years was available at low cost.  In my final year in school, Microsoft was giving away Visual Studio .NET for free to each student in computer science and computer engineering programs.  I can only assume they were trying to quash Java with .NET.

When I first looked into Ada back in 1999, there didn’t seem to be much to choose from for someone just getting started.  It seems though that the commerical Ada vendors have come to their senses and made their tools available for open-source use.  It is a matter of survival perhaps?

Ada Development Environments

Mostly likely you’ll be using GNAT unless your company is asking you to learn Ada on a specific vendor’s platform.  I’m not going to argue the merits of integrated development environments versus command-line development.  My personal method is to use a text editor and the command-line for small programs, and for large projects I’ll normally fall back on an IDE due to the object browsing capabilities.  When I frst started with Ada, I used the command-line and a text editor only because I felt overwhelmed by the options in the IDE.  Now that I have a better feeling for the jargon used in Ada, the IDEs make more sense and are quite usable.  If you don’t like development environments, then stop reading here and just install GNAT if you’re on UNIX or Cygwin + GNAT if you’re on Windows.


GNAT Programming Studio (GPS)

GPS comes from AdaCore, the company that developers the GNAT tool chain.  If you create a free account on their Libre web page, you can then generate a custom download package that bundles not only GPS and GNAT, it also GTK+ binding, libraries for XML and CORBA, and more.  Compared to Visual Studio or Eclipse, GPS is very light-weight, and if you are comfortable with the Ada language you will become proficcient with this tool very quickly.  The only downside I see with it is that there is no auto-completion nor a “intellisense” system that displays possible choices.

Platforms: Windows .NET, Windows x86, Linux x86, Linux86 64-bit

Cost: (registration required) Free for open-source developers, but for commercial users a yearly subscription is required

Opinion: the best IDE available to non-commercial users

gps


AdaGIDE

AdaGIDE was the popular IDE before GPS was made available to open-source developers. While it resembles Emacs visually, it is a regular editor and you don’t have to memorize a bunch of Ctrl or Alt key combinations.  AdaGIDE supports integration with GNAT, syntax highlighting, and all of the features needed for developing small Ada software projects.

Platforms: Windows

Cost: free

Opinion:  a light-weight IDE that should suit the needs for any hobbyists running on older hardware


GNATBench

Also AdaCore, GNATBench is simply a plug-in for the popular Eclipse IDE.  It uses an exisiting install of GNAT on your machine, and then utilizes Eclipse to manage, edit and build your software.  I had high-hopes for this plug-in because unlike GPS, GNATBench has an “intellisense” like-feature.  Though it was easy to install this plug-in in my existing Eclipse setup, Eclipse reported errors and Java run-time exceptions after I started editing some Ada source files.  I don’t know where the fault is, but I never get such errors when I edit Erlang files in ErlIDE.  I want to write code and solve problems, not debug Eclipse, so I am not using this tool anymore.

Platforms: any platform that supports both Eclipse and GNAT

Cost: free

Opinion: a lot of potential, but still too unstable for my liking

eclipse


Hibachi ADT – unavailable

As far as I can tell, this is a project that was suposed to take off and fill a gap in the market, but it appears dead in the water since 1997.  Perhaps Aonix’s and AdaCore’s plug-ins have caused the developers of this project to hang up their shoes?

Opinion: Noting really to say, it seems like a dead project


Cygwin – not really and development envirnoment…but an option

I don’t think the Cygwin project needs any introduction.  If you want a UNIX-like environment to develop Ada programs in, simply select the GNAT binaries during installation and you should be set to go.  Edit Ada files with your favorite text editor, debug with GDB — it should all be familiar.

Platforms: Windows

Cost: free

Opinion:  If you know UNIX, this is a great way to get started with Ada and learn the build process


AonixADT

Aonix has their own Ada compiler called ObjectAda, and AonixADT is a plug-in for Eclipse that can be used with ObjectAda or GNAT. I have downloaded the plug-in, but I have not installed it or evaluated it yet.  The build data is 2007, and here we are in 2009?  I’m a bit skeptical of Eclipse plug-ins that don’t keep up with the times.  I blame Mentor and their Nucleus RTOS development environment for this skepticism.

Platforms: any that support Eclipse and ObjectAda or GNAT

Cost: (registration required) free

Opinion: none yet, I haven’t tried this one


SPARKAda

SPARK is a subset of the Ada language as well as a platform that is quite popular in the commercial Ada development community.  A lot of PR about Ada in the news these days revolves around SPARK, such as the NSA Tokeneer [DrDobbs, AdaCore] project. From the vendor’s web page:

SPARK gives confidence in the correctness of code – it is verifiable. Early detection and prevention of defects reduces the cost of verification and validation. SPARK is a very portable language and has minimal runtime system requirements.

SPARK is a commercial tool aimed at real systems and embedded platforms, so there is no free version for developing application software.  A demo version for training and education is available, however.

Platforms: Demo version is available for Windows, Linux, Mac OS X 10.4

Cost: (registration required) free demo version; contact sales for the commercial package

Opinion:  none yet, though I should take a look at the demo version sooner or later


There are probably other development environments available, especially in the commercial realm, but the above were the ones that turned up at the top of Google searches when I was researching the Ada development environment terrain.  While all are not quite as polished as Visual Studio or NetBeans, it is definately a good start!

Ada for C/C++ Developers: Wide Characters

Originally, the Ada language only supported the ISO-8859-1 encoding, which is capable of handling most of the characters in Western European languages. I suppose that was acceptable in the 80s, and even in the late 90s perhaps as most of the users of Ada seem to come from the USA, UK, Germany and France.  But in the 21st century?  No way, completely unacceptable!

Ada 2005 added support for wide characters so that your application can support languages such as Chinese, Russian and Arabic.  It also also added support for UTF-8 file encoding. As a C++ developer who has struggled with internationalization issues, particularly reading UTF-8 text files, I truly welcome this support in Ada. I may not have the latest information, but I don’t believe C++ supports UTF-8 without the help of third party libraries.  Perhaps that will change in C++0x?

Working with wide characters in Ada is no more difficult than it is in C++.  Separate I/O libraries are provided for regular and wide text, just like in C++ (wcout/wcin, wsprintf, etc).  For example, Ada.Wide_Text_IO is the wide character equivalent of Ada.Text_IO.  I should also mention that unlike C++, Ada 2005 allows a developer to define variables  and types using languages like Chinese or Hebrew.  Though I doubt (perhaps naively) that this is utilized very often, it is interesting nonetheless.  Please note that:

  • Ada.Strings.Unbounded and Ada.Strings.Bounded are similar to the std::string and char [] arrays in C++
  • Ada.Strings.Wide_Unbounded and Ada.Strings.Wide_Bounded and are similar to the std::wstring and wchar_t [] arrays in C++.

Here is an extremely simple program to demonstrate the use of wide characters with Russian and Chinese.  If you are copying and pasting this to an editor, make sure to save the file in UTF-8 format or you might loose the Chinese and Russian text.

with Ada.Wide_Text_IO;
use Ada.Wide_Text_IO;

procedure WideText is
	Msg1: Wide_String := "Россия";
	Msg2: Wide_String := "中国";
begin
	Put_Line(Msg1);
	Put_Line(Msg2);
end WideText;

The Msg1 variable holds the Cyrillic for “Russia”, and the Msg2 variable holds the Chinese for “China”.  My test environment is Cygwin on Windows, and unfortunately, I have not figured out how to get unicode to display properly in the terminal.  Perhaps someone on a Linux box with a UTF-8 terminal could very this?  If you’re in the same boat as me, then just dump the output to a file and open it up in a unicode-friendly editor.

./widetext.exe > output.txt

You should be able to see both strings on a separate line in the file:

Россия
中国

If someone ever figures out unicode in the cygwin terminal or Windows cmd.exe terminal, please let me know!

Ada for C/C++ Developers: A first program

After feeling a bit overwhelmed with Ada for Software Engineers, I decided to take a break and try to write some simple programs so that I can get more familiar with the core Ada language.  Hopefully these entries will help any one else interested in Ada.

The following is a sample program I created to become accustomed with the some basics of Ada: console I/O, arrays, and most importantly,  strings.

with Ada.Text_IO;
with Ada.Strings;
with Ada.Characters.Latin_1;
use  Ada.Text_IO;

procedure Reverser is

	procedure ReverseIt
		( Text: in String;
                  Len:  in Integer  )
	is
	begin
		for Index in reverse Text'First .. Len loop
			Put(Text(Index));
		end loop;
		Put(Ada.Characters.Latin_1.CR);
		Put(Ada.Characters.Latin_1.LF);
	end ReverseIt;

	Input:    String(1..255);
	Last:     Integer;
begin
	loop
		Put(">> ");
		Get_Line(Input, Last);
		exit when Input(1) = Ada.Characters.Latin_1.ESC;
		ReverseIt(Input, Last);
	end loop;
end Reverser;

First of all, Ada is case insensitive, but good Ada style dictates that we name variables and functions with upper-case letters. I have yet to find out whether camel case (ReverseIt) or underbars (Reverse_It) are preferred for nameing variables and functions that have mulitple words.  Before I forget, I should also mention that array indeces start from one is Ada, not zero like in C++.

Ada is quite verbose and easy to read even if you don’t know the syntax.  Without know the details of the syntax, a developer familiar with basic procedural programming should have no trouble understanding what this simple program does.  It simply reads a string from the user and prints it out reversed on the string.

For a C++ programmer, the syntax is quiet different though.  In the definition of the ReverseIt procedure, each parameter in the parameter list is labed as in before the type is listed.  “Len: in Integer” is equivalent to “const int Len” in C++.  For ouputs we can use out, which would be similar to “int &Len” and for parameters that function as both inputs and outputs, we can use inout.

The with clauses are like #include statements in C++ in that they allow our program to call functions from external libraries.  Ada.Text_IO and Ada.String libraries are  similar to cstdio and cstring respectively.  Ada.String is for fixed length strings like C-style character arrays.  The use clause is similar to the C++ namespace statement as it brings the library into scope and allows us to leave off the library name when calling a function from the library.  Instead of using Ada.Text_IO.Get_Line in the program we can simply use Get_Line. It might also be a good idea to take a look at the Ada.Text_IO library to better understand how to use the I/O functions.

The final thing to be wary of is semicolons in the parameter list for the ReverseIt procedure.  The last parameter for the procedure does NOT have a semicolon. If you place a semicolon at the end of the statement, GNAT will become angry with you.  My advice is to always complete the parenthesis first and then go back and fill in the parameters as necessary.

Other oddities for the C++ programmer might be that both local variables and procedures/functions are declared before the main program body is defined.  Also, the Ada.Characters.Latin_1 library is withed so that we use control characters like carriage return (CR), line-feed (LF) and escape (ESC).  These are the equivalent of escape characters such as  “\n” or “\r” in C++.  If you look at the .ads file for the Latin_1 library, you can see it simply defines a bunch of character constansts with the proper ASCII values.

Finally, note that there is no main function defined in the code.  Unlike the C++ run-time, the Ada run-time does not require the entry point of the program to be named “main”.  However, the entry point procedure should be the same as the file name.  In this case, the entry point is the Reverser procedure, which is why the file is named reverser.adb.

To build this program, first copy the program code into your favorite editor and save it as reverser.adb.  GNAT expects program bodies to end in the suffix .adb.  It expects specifications–like C++ header files–to end in the .ads suffix.  For now lets not worry about specifications as our programs will be simple in the beginning.  We can either run the single-step build process, or we can build it separate steps.  Execute “gnatmake reverser.adb” on the command line to runt he single-step process.  If there are no errors, the reverser binary is created in your working directory.

For learning purposes though, lets build the program step-by-step.  To start, execute the following on the command line:

gnatmake -c reverser.adb

If you look in your working directory, reverser.o and reverser.ali have been created.  On the screen you probably noticed that the above command actually invoked “gcc -c reverser.adb”.  The GNU compiler supports not only C/C++, but also languages like Objective-C and Ada.  Just as in C++, after compiling the program, an object file, reverser.o, is created. The GNAT manual explains the Ada Library Info (ALI) file in more depth, but it essentially holds information about required libraries and version information.

The next step is to bind the program.  The binding process uses information from ALI and object files to make sure that package (modules) versions match and that there are no inconsistencies.  There is no equivalent in C++, and binding is touted by Ada developers as yet another way that Ada is inherently safer than C/C++ programs.  To bind the application, execute the following:

gnatbind reverser

We do not need to specify the ALI file with its suffix because the binder figures it out. The bind process produces two files, b~reverser.ads and b~reverser.adb.  Take a look at the contents of the files–quite a bit of information in there!  Refer to the GNAT manual if you want to know more, but lets move on and worry about the details later.

The final step is to link the program with required libraries to produce an executable (just like we do in C++).

gnatlink reverser

Take a look at the working directory.  Notice that the gnatbind output is now removed and that there is also an executable for our program.

So that is it for our first program.  If the program doesn’t make any sense, spend some time looking at the library specifications.  For further enrichment, try changing things in the program such as outputing past the length of the input string or passing bad arguments.

Reflections on the Ada Language

I go through periods where I have a crave to learn new programming technology.  I’ve tried Java in the past, but in the end I fell back on C++.  Same thing for Python and Haskell–the syntax (sorry, freedom with white-space is just a personal preference!) and lack of familiarity with the libraries led me back to C++.  But sometimes I want to try something new and feel that “wow” moment when you really appreciate a new way of doing something.  So far only Erlang has managed to cause that reaction.  I still need to have a go at Eiffel one of these days.  The software engineering aspect of Eiffel looks really interesting.

Speaking of software engineering, I have always been interested in evaluating Ada and understanding the how and why it is known for safety and reliability.  I have been trying to make myself more comfortable with Ada since my days in the university.  After all, unlike Java, C# or many modern languages, Ada is not managed and I can use the GNU tool chain for development and debugging.  Yet somehow Ada never sticks to me–I don’t know why.  Ada is used in some of the most interesting software in the world: avionics, rail transport control in the EU, satellites, and more.  Even with such an impressive track record, I still find it difficult to buckle down and really go at Ada!  Those applications are so much more interesting that what I currently work on.

Whenever someone in the Ada community publishes and article about the strength of Ada in software engineering and the lack of developers who know the language, I get the urge to try and pick it up again.  I really want to understand what makes it so well suited for mission critical applications, yet when I start reading a book on Ada, I loose interest in a few days.

One major factor may be that I cannot really use it in my job. I could, but my boss would probably throw a telephone book at me if he wanted to update my software and found it was not C, C++ or C#.

I just cannot put my finger on it though.  I don’t mind that Ada is a verbose language–it helps to keep my C/C++ style of thinking out of any Ada code.  Reflecting on my FPGA designs, when I write Verilog (required at work) I sometimes catch myself writing it like a C program.  I never had that issue with VHDL (from my school days)  because the syntax is just so different from C–in fact, VHDL is based on Ada.

So why the personal trouble with Ada?   Am I just not motivated enough?  Perhaps.  Honestly, I think the biggest hurdle for me with Ada is the constant reference to the ARM, the Ada Reference Manual, in Ada learning materials.  I understand that the ARM is a “contract” and Ada programmers should refer to it when it doubt.  However, it has to be the driest reading I’ve ever attempted–even my undergraduate electromagnetics textbook was more interesting! In “Ada for Software Engineers”, I can feel myself nodding off whenever a reference/quote is made to the ARM.

Perhaps the reverence for the ARM is the difference between Ada and other languages.  When I first learned C++, I learned little-by-little, and as I gained more experience and felt more confident in my ability to write C++, I could then attempt to read Stroustrup’s C++ book and Lippman’s C++ Object Model book.  I was at the level where I really could understand C++ and I could understand how it worked under the hood.  Perhaps I should try some other Ada books, I don’t know.

Nonetheless, I still toy around with the language during downtime.  I often wonder if there are there any interesting open-source Ada projects out there?  It always helps to see how a language is applied.