Abstract data types vs Data structures

C++ data structures is another course am learning this semester. This course is a pre-requisite for all non-Computer Science students. I have already learnt and implemented all the C++ data structures in a private course during my undergraduate studies, but not with the same understanding am learning them these days. Frankly I dont know much about data structures during my work experience. So I consider this course as an opportunity to get my hands on C++ again and implement various datastructures.

First thing I got to know is.. the difference between the abstract data types (ADT) and datastructures. Earlier I thought they are same.

Before starting that, we need to be clear about the logical and implementation level of data. Let us take an example of a simple built-in data type integer. At the logic level, we application programmers know only about what are the operations an integer data type can perform, ie., addition, subtraction etc., But we are no way aware of how the data type is actually implemented. At the implementation level, it is about how the data type integer is implemented in the machine level, ie., it could either of binary-coded decimal, unsigned binary, sign-and-magnitude binary, One's complement and Two's complement notation.

Now.. for the understanding the ADT and data structure, we need to assume a higher level abstraction where we have the built-in types at the implementation level.

To put it simple, ADT is a logical description and data structure is concrete. ADT is the logical picture of the data and the operations to manipulate the component elements of the data. Data structure is the actual representation of the data during the implementation and the algorithms to manipulate the data elements. ADT is in the logical level and data structure is in the implementation level.

As you can see, ADT is implementation independent. For example, it only describes what a data type List consists (data) and what are the operations it can perform, but it has no information about how the List is actually implemented.

Whereas data structure is implementation dependent, as in the same example, it is about how the List implemented ie., using array or linked list. Ultimately, data structure is how we implement the data in an abstract data type.

This is something new of what I have learnt.

got to know.. 'Leda'

I just came across a new programming language called Leda when I was reading the book 'Thinking in C++' by Bruce Eckel. What is so unique about Leda is, it is a multiparadigm programming language. Multiparadigm, I mean, has all the paradigms of programming languages implemented in it ie., imperative, object-oriented, functional and logic!

As we all know that these abtraction of programming languages were basically to address the problem needs to be solved by the computer. As in imperative languages the problem space and solution space were different, so it became tedious for a programmer to map the spaces with each other. And then came the better abstraction, object-oriented programming. Here the problem space and solution space looked similar! like.. all were treated as objects ie., the abstraction was catered in a way that it fits the real world. Later we had functional and logic paradigms which had their own conceptualization of the real world ie., as 'lists' in LISP and 'algorithms' in Prolog. So there came a point that every paradigm best suits only for the particular kind of problem that it was catered for.

So Leda was designed to have all the paradigms in one language and the programmer can chose the paradigm based on which will best suit his problem to be solved. It was founded by Timothy Budd. There is a book named 'Multiparadigm Programming in Leda' authored by the founder himself. I tried finding a free soft copy of this book to learn more but in vain. But I got a research paper on this topic from my univ's 'Adaptive Systems and Languages group'. Will post more when I get time to read that paper.

Paradigms of languages

In the first lecture, I learnt about the different paradigms of prg. languages. This is not new to us but generally we classify them as low-level, structural and object oriented languages, and what I learnt is a way forward. Have a look at it.

The taxonomy is provided based on the nature of program and data in these paradigms. The taxonomy is based on my instructor, Dr. Mattox A. Beckman's views.

1. Low level languages
Program : series of control signals for a CPU.
Data : integers, memory address, IEEE floating point.
eg: Assembly languages and microcode

2. Imperative languages
Program : list of commands to be executed.
Data : low level types (integers) and composite types (records and arrays)
eg: C, BASIC, Fortran, Forth and Pascal.

Fortran is still the best language to do intensive mathematic calculations. It has advantages over Matlab.

3. Data encapsulation languages
Program : list of commands to be executed.
Data : low level types (integers), composite types and we can hide details from the user.
eg: Clu, Modula 2, Ada

4. Object oriented languages
Program : message between objects
Data : object (functions with state)
eg: Smalltalk, Java, C++

C++ and Java were actually inspired by Smalltalk which should have been the web language, - what Java has become. But they didn't see the opportunity at the right time.

5. Functional languages
Program : an expression to evaluate.
Data : low level types and higher order types (the functions)
eg: LISP, Scheme, ML

6. Logic programming languages
Program : a logical predicate to satisfy.
Data : set of assertions about what we know to be true.
eg: Prolog

So from this taxonomy am already introduced to four of the paradigms. I learnt BASIC during my schooling days and have done few coding in assembly level language during my undergraduate studies. I have also learnt C and C++ in a private course. Then I learnt and worked in Java during my work experience.

Still there are two more paradigms unexplored and I'll learn them in this course (functional and logic programming languages). Hope that should provide me with the well-rounded understanding of the different paradigms, I strive for.

Programming languages and translators

One of my major reasons to opt for graduate studies is to learn the science behind programming languages. This thought blossomed 4 the first time when I was attending a training class in Java in my prev. organization. My tutor was Mr. Sanjay Kumar Mitra, a very nice gentle man with sound knowledge in Java. When he was talking about objects and primitive datatypes like 'int', the similarity in their implementation in Java and the fact that you can't do everything with an 'int' that you do with an object, added more mystery.. I wondered how the designer of the language would have designed it and whatz the science behind it?

With my experience as a software engineer, I felt that every software developer should have a good understanding of the different paradigms of progamming languages. Because this is an ever-growing field and it becomes compelling for us to be updated with the technical advancements thoughout our career. The understanding of the paradigms and the root of their conceptualization, is the key to adapt to any new programming language down the line.

Now.. I hope this course 'Programming languages and translators' will address that. In this blog I'll give an introduction abt what I'll learn through this course.

Yep.. so this is what I'll learn from this course.

1. The major classes of programming languages.
2. How to specify formally the meaning of a language - to people and to the computer. (type derivation etc.,)
   
3. How to design and implement a language?
4. Three powerful concepts - Abstraction, Recursion and Transformation.

Yeah! I am going to learn how to design and implement a language.. now doesn't that sound cool?

and basically there are three major themes in this course.

1. How do we describe a language to ourselves?
2. How do we describe a language to the computer? - how the computer understands what we typed in? (parsing)
3. Once the computer has understood, how it does what we said? (interpreting and compiling)

and I am gonna learn all these through a new language called 'OCaml' - Objective Caml. Itz a functional language .

so.. now comes the question, why a functional language? and why not an object oriented programming language which is predominant in the market?

Because functional languages are step ahead and have all the features of procedural and OOP languages. So learning through this language, we can conceptualize all other paradigms.

Ground zero..

This is my first blog and the purpose is to share whatever I learn in the field of computer science.. or might add even more in the career perspective.

Why blogging? It will help me to express myself better and also logging my step-by-step learning curve will help me in the long run to evaluate myself. Apart from that my intention is to share the knowledge I gain and keep this blog as an informative resource to the reader.

and with this short note am starting off..