Archive for the ‘The H++ Language’ Tag

Solved Problems to the Stanford Mathematics Problem Book using H++   Leave a comment

It’s been a while since i published my last post. This time, I’ll start with a little post, that will become the first of a sequel of solved problems in H++.

This time, I’ll show, two problems from the Stanford Mathematics Problem Book.  This is a little book, full of very interesting math problems. I highly recommend you to get this book, if you like to find solutions to problems like this and others very common in mathematics. This is my own copy of this book.

Stanford Mathematics Problem Book

Solving the Problems using H++


First Selected Problem: Problem 48.1

Because actually, my time is short, I selected two problems for this post. The first one, I’ll discuss here, is the problem on page 7, where you have to determine the mathematical formula in both sides of the equation; the left side, is a series; the other side, is a simple cubic equation:

Problem 48.1 on Page 7

The H++ Solution

First, I implemented the iterative power, just for the purpose of testing the H++ compiler:

Power code

Then, I implemented the actual solution, by a function who prints, the terms of the series:

Problem 48.1 Solution in H++

Then, I called this function, after instantiating the class where I coded this function; this is the entire code:

Invoking the Solutions Functions of the Problems in this Part

Second Selected Problem: Problem 54.1

And this is the other selected problem I decided to implement a solution from H++:

Problem 54.1 on Page 13 in the Standfords Problem Book

And this is my solution, using H++ (you can try it in other programming languages):

Solution for Problem 54.1 on Page 13

Other Algorithms implemented in H++

Other algorithm I decided to implement, to show in this post, is the Divide-And-Conquer version of the Fibonacci Algorithm:

Fibonacci Algorithm

The Output

This is the compilation process’s output:

The compilation processs output

The Results for n = 10

And this is the result/solution, for n = 10:

The output

In the next post, I’ll be working on more complex algorithms, to show the power of H++. See you next!

Advertisements

Floating Point and the support for IEEE 754 in H++   Leave a comment

As promised, the post that will reveal the details of the support of IEEE 754 in H++.

If after reading this post, you think you will need a more in depth discusion of IEEE 754 and its relation with the programming languages, please read Michael L. Overton’s excellent book called: Numerical Computing with IEEE Floating Point Arithmetic. A revision of the current IEEE standard can be located in IEEE 754: Revision of 2008.

Numerical Computing with IEEE Floating Point Arithmetic

Numerical Computing with IEEE Floating Point Arithmetic

As Overton explains in his book, the support for IEEE 754 and floating point in general has been inconsistent in both the hardware (the cpus), and finally the software (the programming languages). Programming Languages like C/C++ and Fortran are among others the ones with full support for the IEEE 754 specification. But that was not this way from the beginning.

The Floating Point support in H++ is very simple: I just have float and double types both with the same size and precision: 64 bits (1 bit for sign, 11 bits for the exponent, 52 bits for the significant or the mantissa). This was made this way just for simplicity when implementing the H++ Code Generator for x86 32-bits Assembly.

So, you can declare local or static variables with the keywords float and double, and will have the same double precision known from the double data type. In the future, that will change to reflect the standard: float will have 32-bits and double 64-bits of size.

Some of the floating point support tests I was writing in sample H++ programs, are provided as C programs in the Michael L. Overton’s book; if you want to do the same testing for C/C++ programs, please visit the links : Programs in this book.

Another lack of feature in H++ is in the print format; H++ supports only Fixed Format, which is very restrictive, but it works. The Exponential Format is the missing feature actually in my implementation. Here are examples of what I’m saying:

Fixed Format:            0.000542368921   (the only print format supported in H++ actually)

Exponential Format:    5.42368921E-4     (a more easy to handle print format, also known as Scientific Notation)

I’m thinking in dedicating a couple of days to implement  that format, but I really don’t know when I’ll start to make it.

Testing the H++ Compiler

One of the tests you can find in this book, is the reciprocal power of 2, like in this H++ program:

Calculus of Reciprocal Power Of 2

Calculus of Reciprocal Power Of 2

This little program outputs the reciprocal powers of 2; so one detail I have to explain that shows the differences of this implementation with the original found in Overton, is that the condition was made against this tiny number: 0.00000000000000001 and not against 0.0 as the original one; the reason is simple: because I just implemented the Fixed Format for output, all the number below this 1.0E-17 are all printed as 0.0 until x really underflows.

The output:

Resuls of Reciprocal Power of 2

Resuls of Reciprocal Power of 2

The final results are:

The problem with Fixed Format in H++

The problem with Fixed Format in H++

After the power 2^-55 and down, the number printed is zero;  if the number would be 0.0 in the while condition expression, the results are all zero from here until it really underflows to 0.0; the reason is the precision I’m using: 64-bits of precision.

A test that passed Ok, was the one involving 1.0 added to the reciprocal powers of 2:

Calc One Plus Reciprocal Power Of 2

Calc One Plus Reciprocal Power Of 2

The results were as expected:

Results passed Ok for 1.0 + 2^x

Results passed Ok for 1.0 + 2^x

This phenomena is very interesting because when you have isolated the reciprocal power in H++, it does not behave very well; but when you add it to 1.0, the results are as expected.

One interesting test, is the one related to the approximations as explained in Overton; here is the test H++ program:

Find One From Quotient

Find One From Quotient

As you can see from the formula, 1/ (1/x), the result should be X in all cases:

One Div Reciprocal X Results

One Div Reciprocal X Results

This test was successfull in H++. Here is why this test is very important: The binary representation for 1.0 and 0.99999999 are totally different besides they are the same value; let’s see these numbers as 32-bits float values in their binary format:

Short Real    sign exponent mantissa                                                  hex-value

1.000           =  0        01111111    00000000000000000000000   0x3F800000  <—- 1.0
1.000           =  0        01111110   11111111111111111111110   0x3F7FFFFE   <—- 0.9999999

As you could see, the number and its approximation have different binary representations; but if you continue adding more digits to the approximation, the process of rounding will take place here, and the number finally will change from .9999999…. to 1.0; you just have to add another digit 9, to convert the 0.99999999 in 1.0:

Short Real    sign exponent mantissa                                                  hex-value

1.000           =  0        01111111    00000000000000000000000   0x3F800000  <—- 1.0
1.000           =  0        01111111    00000000000000000000000   0x3F800000  <—- was once 0.99999999

If you want to have an in depth explanation of this phenomena, please read Overton’s book: Numerical Computing with IEEE Floating Point Arithmetic.

Fractions with Expressions of Zero Result, as the Divisor

Another interesting subject, is the one that relates to fractions with zero as divisor, one operation which is invalid in mathematics.

It’s well known that in an expression with fractions or divisions, where the denominator expression would result in zero, cannot be resolved inmediatelly; so, from Calculus, you know that some limits must be approximated, when they cannot be solved by simple substitution of x in the polynomiuns.

They are a lot of tools in calculus to solve that problem, and one is approximation; if you cannot use 3 as value of x, you could use values from the left like these: 2.4, 2.5, 2.7, 2.9, 2.95, 2.98, 2.995, 2.9995; also you can use values from the right, like these: 3.0000099, 3.00009, 3.0001, 3.001, 3.01, 3.1. Also, tools like L’Hopital’s rule, is well known to be applied in this cases, to avoid the approximation or numerical analysis.

But, one of the features of the IEEE 754 is that you can have two different approaches: allow this result to become infinite, or throw an exception, following the rules of Division by Zero.

In the following example, what you can have as result, is zero; that will help you understand the problem in your formula, or in your program:

y = 1/x;  //this will result in y = +oo|-oo (plus|minus infinite)

Based on the first approach, that expression would result in +oo (plus infinite) or -oo (minus infinite); so, if you continue operating with this value, the result could be infinite. If you then do this to the previous result:

z = 1/y;  //this will result in z == 0.0

The new result would be zero.

The second approach, is to throw an IEEE 754 Floating Point exception called: Division by Zero; so you’ll need to catch the exception to understand the problem, and avoid the program to terminate unexpectedly:

try{

y = 1/x;  //this expression causes the exception when x == 0.0;

z = 1/y;

}catch()
{
printf(“Division by Zero has ocurred!”);

}

Here is an H++ program that shows the results of the Total Resistance, for different values of R1 and R2 (the two resistances in the circuit):

Total Resistance in H++

Total Resistance in H++

To get the programs in C, please visit Michael L. Overton’s site.

The output of this little program is:

Results of Total Resistance in H++

Results of Total Resistance in H++

As you can see, when R2 == 0.0, the total resistance in the circuit is 0.0. That means that:

Total Resistance Formula

Total Resistance Formula

More advanced tests like Approximating a Derivative by a Difference Quotient, can be found in the Overton’s book. Also, a phenomena called Cancellation is well explained in that book, so I recommend you to read it to have a better understanding of the issues involved with Compilers and the expected results.

Here is the output:

Approximating a Derivative from A Diff Quotient

Approximating a Derivative from A Diff Quotient

This is the H++ program that generates that output:

AproxADerivByDiffQuot Program in H++

ApproxADerivByDiffQuot Program in H++

Approximating the Euler’s e Constant

Let’s do another test: let’s find Euler’s e constant in an H++ program:

Approximating Euler e Constant

Approximating Euler e Constant

As you observe, the result depends on the size of n; when n–>oo, e will have a more accurate value; here is the result:

Approximating Euler e Results

Approximating Euler e Results

You can see that, when I applied the Natural Logarithm to the value of e I found with n = 10E+8, the result was close to 1.0; the approximation was very good for that value of n.

Now, let’s do the same thing, but this time, using the Taylor series formula:

Approximating e using Taylor Series

Approximating e using Taylor Series

Now, making a few changes to return the e value from each function, and compare the cancellation digits, to determine how many digits are correct in the two aproximations, we get these results:

Approximating e Methods

Approximating e Methods

Now you can notice that the two aproximations are valid for the first 6 digits after the decimal point. In this example, the more accurate was the Taylor Series formula.

H++ Floating Point Math Library

As a explained in older posts, the Math library supports almost all the fundamental functions, primitives and intrinsic functions; most of them were implemented at the x86 assembly level, to leaverage the existing implementation in the Floating Point Unit (FPU) in the x86 microprocessors.

Fundamental Math Functions

Here are some of the implemented functions:

Hpp Math Lib - Part I

Hpp Math Lib - Part I

Most of these functions are already implemented in the FPU.

Hpp Math Lib - Part II

Hpp Math Lib - Part II

You can also note the constants that are already computed in the FPU, and the most common Trigonometric Functions.

I also implemented the y^x function, and e^x:

Hpp Math Lib - Part III

Hpp Math Lib - Part III

Inverse Functions

Hpp Math Lib - Part IV

Hpp Math Lib - Part IV

Here you can see, how I implemented the Inverse ArcSin in x86 Assembly Language, for the H++ Library:

Implementation of Inverse ArcSin Function

Implementation of Inverse ArcSin Function

Hyperbolic Functions

Finally, the other more advanced functions, I decided to implement them directly in H++ because of matter of time:

Hyperbolic Functions

Hyperbolic Functions

This code is compiled and is available in the H++ library for any math operations that require them.

Inverse Hyperbolic Functions

Hyperbolic Inverse Functions

Some aliases you can use, without referring to the full name of a static function for these hyperbolic and inverse hyperbolic functions, was defined:

Hyperbolic and Inverse Hyperbolic Function Shortcuts

Having implemented these later functions in H++ saved me a lot time, which I dedicated to finish some important issues including bug fixes.

Conclusion

The full support of IEEE 754 is still very distant in H++, but as you could see, there is a lot of work already done in the H++ compiler, and fewer things are missing. I highly recommend you to read Overton‘s book: Numerical Computing with IEEE Floating Point Arithmetic, if you are serious about Floating Point and the IEEE 754 Standard.

I hope this post can help you understand the basics of Floating Point, and the support in H++.

Bye, bye.

H++ Sample Sorting Library: Part II   Leave a comment

In this new post, I’ll be describing the process of implementing an OO library in the H++ language; first, I’ll detail the classes that interact in the problem of sorting. The subject will be : sorting automobiles by year and cost, with priority in cost in Ascending mode. The Sorting algorithms can be implemented in Descending mode, by just changing the implementation for the ProxyObject::Compare member function.


The SorterEx class

 This new abstract class, is the base class for all the OO Sorting algorithms that will be presented here in this post.

SorterEx abstract class

SorterEx abstract class

As you noted, this class rely on a new abstract type called Array; this class only implements the Swap member, and the behavior can be changed in new concrete sorting classes.

The H++ Array base class

Here is the definition of the base class Array:

H++ Array abstract class

H++ Array abstract class

This class contains a pointer member to the ProxyObject type; the idea is to create an dynamically allocated array of objects, and have an internal pointer refer to the address of the first object in memory. 

The properties are : 

  • length, a read only property to let to users to know the items count  in the array.
  • item_size, this can be used to know the size of each object contained in the array.

The other member functions are self descriptive, and will be implemented in a concrete class called ArrayOfAutomobile in the same H++ unit.  

Now, let’s set our attention to the Automobile class, the real top character in this post, the Automobile class:

The Automobile class

The Automobile class

 This class has the following properties:

  • Model, to represent the name of the brand of the vehicule.
  • Cost, to represent the price to acquire on auto of this model (these data are demo, and does not reflect the actual prices of these brands mentioned in this post).
  • Year, this is the year of emition of the vehicule.

Also, includes a default constructor, required by the new operator when it’s creating a new instance of this type of objects in the heap.

The most important member is Compare, which is virtual, and is overriden here to show a specific behavior (Polymorphism).

Finally, a destructor to show when the object is being destroyed.

The Array concrete class

 Next, is the concrete array class, ArrayofAutomobile, created to hold and manage the array of Autombile objects:

ArrayofAutomobile concrete class

ArrayofAutomobile concrete class

This class possesses a constructor which expects the number of items to construct in itself. Here you can also see the getAt member, which returns an instance of ProxyObject as an upcast, from the array of automobiles. As you can see, all it takes to create an array of any object, that can be sorted with the H++ OO Sorting classes, is just to inherit from Array class, and implement the virtual abstract members.

Now, let’s take a look at the sorting algorithms.

Simple Sorting Algorithms

Here is the implementation of the Insertion Sort algorithm:

Insertion Sort for Array objects

Insertion Sort for Array objects

 

In languages like C++ or C#, you can overload the operators [], >, <, ==, and also !=; but in H++, you can’t, obviously, because I have not implemented that language facility yet; that will be part of version 2.0 of the H++ Compiler, I promise that; because I know the importance of having overloaded these operators I mention here.

For now, we have the Array::getAt() member, to access the objects in the internal array, and the ProxyObject::Compare(), to compare against other objects.

The ProxyObject::Compare(), return the following int values, based on the results of the tests that perform this virtual function:

  • -1, when the current object is less than the object compared with
  • 1, when the current object is greater than the object compared with
  • 0, when both objects are equals

When I implemented these sorting classes I show here, I had a conflict with the  class names, because besides they belong to different namespaces, they cannot live in the same place when they are instanced in the program; so the H++ Compiler reacted yelling the following ambiguity errors:

>TestSorting.hpp:
TestSorting.hpp{153} : error: Identifier is ambiguous in the current scope ; which do you want to use: ‘Algorithms::Sorting::InsertionSort’ or ‘Algorithms::Sorting::Proxy::InsertionSort’ ?
TestSorting.hpp{154} : error: Incompatible types : cannot convert from ‘Algorithms::Sorting::Proxy::InsertionSort’ to ‘Algorithms::Sorting::Sorter’  for parameter: sorter
TestSorting.hpp{183} : error: Identifier is ambiguous in the current scope ; which do you want to use: ‘Algorithms::Sorting::BinaryInsertionSort’ or ‘Algorithms::Sorting::Proxy::BinaryInsertionSort’ ?
TestSorting.hpp{184} : error: Incompatible types : cannot convert from ‘Algorithms::Sorting::Proxy::BinaryInsertionSort’ to ‘Algorithms::Sorting::Sorter’  for parameter: sorter
TestSorting.hpp{191} : error: Identifier is ambiguous in the current scope ; which do you want to use: ‘Algorithms::Sorting::InsertionSort’ or ‘Algorithms::Sorting::Proxy::InsertionSort’ ?
TestSorting.hpp{209} : error: Identifier is ambiguous in the current scope ; which do you want to use: ‘Algorithms::Sorting::BinaryInsertionSort’ or ‘Algorithms::Sorting::Proxy::BinaryInsertionSort’ ?
                 729 source lines.
                   x syntax errors.

Here is the compiler errors live:

H++ Ambiguity Errors

H++ Ambiguity Errors

This is something similar that happens with the C++ compiler; the problem came to light because I included both namespaces to the same unit; like this:

OO TestUnit including the Sorting namespaces

OO TestUnit including the Sorting namespaces

 

To solve the problem, I just changed the OO classes ‘ names, so that no collision would occur; another way to solve the problem, is to explicitly specify the namespace Proxy prefixed to the OO sorting classes like:

Proxy::InsertionSort sorter;
TestSortingEx(sorter, “\nTesting INSERTION SORT Algorithm: O(n^2) – faster”);

Another error you can receive when compiling would be from trying to pass as a parameter, an Array’s concrete object, to one of the previous algorithms from the Part I of this post; here is what you get:

>TestSorting.hpp:
importing: algorithms.sorting.hpp
c:\testsource\algorithms.sorting.hpp{597} : error: Incompatible types : cannot convert from ‘Algorithms::Sorting::Proxy::Array’ to ‘double[]’  for parameter: array
c:\testsource\algorithms.sorting.hpp{597} : error: Wrong number of arguments
c:\testsource\algorithms.sorting.hpp{597} : error: Function does not take 1 parameters. Unknown function signature.
                 729 source lines.
                   x syntax errors.

Array and double[] are incompatibles

Array and double|| are incompatibles


The Bubble Sort Algorithm 

 

The Bubble Sort Algorithm

The Bubble Sort Algorithm

The Selection Sort Algorithm

The Selection Sort Algorithm

The Selection Sort Algorithm

 

Advanced Sorting Algorithms in H++

The next algorithm, is the Binary Insertion sort, now acting on ProxyObjects subclass’s instances:

The Binary Insertion Sort Algorithm

The Binary Insertion Sort Algorithm

You can note, that most of the implementations require that before doing anything, that the _array member be assigned before doing anything; this is needed because the SorterEx::Swap member function rely on this field to have access to the array object.

The Heap Sort Algorithm

This algorithm is pretty similar to the version over an array of scalar types:

The OO Heap Sort Part I

The OO Heap Sort Part I

The final part in implementation of the Heap Sort is this below:

The OO Heap Sort Part II

The OO Heap Sort Part II

The H++ implementation of the QuickSort Algorithm

The Quick Sort algorithm is one of the most popular sorting algorithms, and because of that, it has multiple different implementations; the one that we are using now, is the called Median of Three Quick Sort, and you can find it in the Bruno Preiss book of Data Structures and Algorithms with C++:

The OO Quick Sort Part I

The OO Quick Sort Part I

I chose this implementation because is beautyful and very powerful; you can note, that this class is also abstract; you may wonder how can this class be instantiated then? The problem is that this class is abstract, and requires a concrete class to finish the implementation of the QuickSortEx::selectPivot() abstract member function, like in the class below:

The Median Of Three Implementation of the Quick Sort

The Median Of Three Implementation of the Quick Sort

Now, the QuickSort algorithm is fully implemented thanks to the concrete class above; another QuickSort implementations can be found on the internet, and implemented in H++ the same way as you can see here.

The most difficult to implement in H++: the Merge Sort

As the subject suggest, this algorithm is very complex to implement; but that does not means that cannot be implemented in H++:

The OO Merge Sort Algorithm Part I

The OO Merge Sort Algorithm Part I

The problem with this implementation, is noted in the next image:

The OO Merge Sort Algorithm Part II

The OO Merge Sort Algorithm Part II

Because this algorithm requires to have a temp array to hold the sorted list, the problem arrives in that H++ at that moment did not supported the H++ pointer_cast operator, so that you can call the malloc function alias to allocate memory from the heap, and make the algorithm completely generic; that will be solved in the next build of H++.

The CopyTo and CopyFrom members, for the Array concrete classes, should look something like this for the ArrayOfAutomobile class:

CopyTo and CopyFrom members

CopyTo and CopyFrom members

These members are required to make the Merge Sort implementation possible in H++.

The H++ Test Program

Here is how the new implementation would look:

OO Test Unit

OO Test Unit

This fragment shows how the array of objects are iterated in the two loops: Before Sorting, and After Sorting.

The OO TestUnit - II

The OO TestUnit - II

As you can see, the new algorithm classes are named with the postfix Ex, to avoid the name collisions between the two imported namespaces in this test program. Here is the new implementation of the Program::main() static member function:

The Program::main() member

The Program::main() member

The Compilation of TestSorting.hpp source

 

Compiling TestSorting.hpp

Compiling TestSorting.hpp

The runs of each H++ Unit Testing

OO Insertion Sort

OO Insertion Sort

 As you can see, the autos are sorted by year, but with the priority by Cost, as you can see from the rectangle above, that highlights the Costs before and after sorting.

OO Bubble Sort

OO Bubble Sort

OO Heap Sort

OO Heap Sort

 

OO Selection Sort

OO Selection Sort

OO Quick Sort

OO Quick Sort

OO Merge Sort

OO Merge Sort

As you also have noted, the objects are destroyed every time the function goes out of scope, but this time because of the H++ destroy operator.

What’s Next?

In the next post, I’ll be presenting part of the Intel x86 32-bits Assembly generated by the H++ Compiler, for the TestSorting.hpp and Algorithms.Sorting.hpp files.

See you all in the next post!

H++ Sample Sorting Library: Part I   Leave a comment

In this demo library’s post, I’ll present a H++ Sample Sorting Library for Scalar types like the double type. The next post in the serie will treat the H++ Sorting Algorithms for H++ Objects.

For more information about sorting algorithms, their time, efficiency and recomendations, please visit a link from the list of links below:

Dictionary of Algorithms and Data Structures
Sorting Algorithms by Michael Lamont
Sorting algorithms by Wikipedia

 

H++ Sorter base class

H++ Sort base class

H++ Sort base class

 The H++ class Sorter is used to define an Abstract Data Type (ADT), so that all the Sorting Algorithms can be modeled and implemented using the same contract; that will help in creating more Object-Oriented programs and will allow more flexibility writing the code in applications that will rely on these sorting algorithms. At the end of this post, I’ll show a sample source program, and the results in action of compiling the H++ source.

 You can also observe that the H++ Sorter class has a Swap member function implemented; that will result in less code when compiling the sources; the function will be reused from almost all the Sorting Algorithms that rely on data exchange.

Simple Sorting Algorithms in H++

The following algorithms are relatively easy to implement from the H++ language; most of them rely on two loops (H++ for or while):

 H++ implementation of the Selection Sort Algorithm

I’m not a fan of this algorithm, because besides its simplicity, is not really good at all.

Selection Sort Algorithm

Selection Sort Algorithm

 
H++ implementation of the Bubble Sort Algorithm

This one is pretty slower; I just implemented it for illustration purposes:

Bubble Sort Algorithm

Bubble Sort Algorithm

 

 H++ implementation of the Insertion Sort Algorithm

This algorithm is highly used in computer science; there are implementations of other old and new algorithms that rely on the insertion sort; you’ll see the Shell Sort algorithm here, depends on the Insertion Sort, but this time I implemented it inlined:

Insertion Sort Algorithm

Insertion Sort Algorithm

 

The next list algorithms, are considered advanced, because most of them are very complex to implement, and have of burden of difficulty to understand them.

 

Advanced Sorting Algorithms in H++

 

 H++ implementation of the Shell Sort Algorithm

This algorithm is an hybrid using the Insertion Sort to solve part of the problem:

Shell Sort Algorithm

Shell Sort Algorithm

 

 H++ implementation of the Quick Sort Algorithm

Considered the fastest sorting algorithm of all; this is widely used because its time is very good ( best time: O(n lg n); worst time: O(n^2) ) :

Quick Sort Algorithm: Partition

Quick Sort Algorithm: Partition

Quick Sort Algorithm: Divide and Conquer

Quick Sort Algorithm: Divide and Conquer

 

 H++ implementation of the Merge Sort Algorithm

 I consider this algorithm, the very complex implementation algorithm of all; you can note, that this algorithms uses twice the memory of the others, and also, is heavily recursive:

Merge Sort Algorithm : Very Complex

Merge Sort Algorithm : Very Complex

 

Merge Sort Algorithm: Heavily Recusirve

Merge Sort Algorithm: Heavily Recusirve

 

 H++ implementation of the Heap Sort Algorithm

This sorting algorithm is very efficient, when it comes to the number of comparisons and data swaps that it executes:

Heap Sort Algorithm: Complex Algorithm

Heap Sort Algorithm: Complex Algorithm

Heap Sort Algorithm: Calling SiftDown member

Heap Sort Algorithm: Calling SiftDown member

 

 H++ implementation of the Binary Insertion Sort Algorithm

Finally, I present the Binary Insertion Sort, to demostrate another Divide and Conquer algorithm:

Binary Insertion Sort Algorithm

Binary Insertion Sort Algorithm

 

H++ Sample Program to test the Sorting Libray

This is a sample program to test the sample library:

 

TestSorting.hpp : Part I

TestSorting.hpp : Part I

 And. this is the main entry point function:

 

TestSorting.hpp : Part II

TestSorting.hpp : Part II


Compiling the H++ source TestSorting.hpp and the H++ Sample Sorting Library

This is what it takes to compile the sources:

Compiling with H++

Compiling with H++


Running the H++ TestSorting.exe program

 

Results for Insertion Sort

Results for Insertion Sort

 

Results for Shell Sort

Results for Shell Sort

 

Results for Quick Sort

Results for Quick Sort

 

Results for Merge Sort

Results for Merge Sort

 

Results for Heap Sort

Results for Heap Sort

 

Results for Binary Insertion Sort

Results for Binary Insertion Sort

What’s next?

The next post, will demostrate the same sorting algorithms, with different implementations, but with a more Object-Oriented approach.

See you in the next post!

 

The H++ Core Language Features – Part V   Leave a comment

OOP in H++

TH++PL support the declaration and definition of abstract types, and single inheritance; so you can create abstract classes declaring virtual abstract functions, like in the picture below:

Abstraction and Single Inheritance

Abstraction and Single & Inheritance

It’s always good idea to also have a virtual destructor in each declaration of abstract types; that ensures that the destructors will be called in an array of objects referred by a variable of the abstract type. I’ll describe that later to make it more easy to understand.

Object instances

In H++ you can create local variables of custom types in the same way it’s done for scalar types. In the picture below, you can see two different objects of type Square and Triangle instantiated as local variables:

Local object variables

Local object variables

The constructors for these variables are called inmediatelly after the variable declaration before they are actually used in expressions.

Dynamic Object Instantiation

To create objects in the process’s heap, you must allocate the object memory through the new operator; to release the memory when it’s no needed anymore, just call the destroy operator (I just took the decision of calling to this operator destroy, instead of the C++’s delete, but the results are the same: call the destructor for the object, and finally release the memory to the operating system); let’s see this in the picture below:

Use of new and destroy operators

Use of new and destroy operators

Copy of objects

Because I have not implemented Copy constructors in H++, the only way to copy objects is by using memory operations that copies the data in obj1 to obj2; this approach is very dangerous when you have pointers involved, as I know from C++, but for now is the only way until I finish the implementation:

Copying objects

Copying objects

You can also copy objects from and to arrays of object, like in the next picture:

Object Copying - Part II

Object Copying - Part II

Because I know that’s very dangerous, and because I also know that every programming language needs to be evolved to improve it, that will be part of my goals in the near future, after I implement the function overloading first.

Dynamic array of objects

As we other programming languages, the memory that was acquired for the process, must be freed before doing anything else, and this is very important for an array of objects:

new and destroy operators

new and destroy operators

 

The dynamic_cast operator

The dynamic_cast operator allows you to cast a pointer variable whose type could be an abstract type, holding a pointer to a concreate object instance; the idea is the same as in other programming languages where you can do up-casting by copying the object instance of a Concreate Class, to a local variable whose type is of the Abstract Class. Then you can use the dynamic_cast operator to convert that pointer variable to a lower level in the class hierarchy, and call the members only available in the Concrete Class. Let’s see an example: 

dynamic_cast operator

dynamic_cast operator

Another example would be: receiving an object of any concreate class, which inherits from the parameter’s abstract type; you can then do a down-cast, to obtain the real object type by using the dynamic_cast operator:

dynamic_cast operator

dynamic_cast operator

Support for Pointers

Actually, the support for pointers in H++ is very limited still; but you can create link objects, and using the new and destroy operators go ahead implementing data structures. When I complete this support, you could create almost all types of data structures and algorithms as in C/C++ or C#; but to achieve that goal, I’ll have to prepare myself and finish my readings to do a better job! For now, let’s see what can be done when it comes to data structure declarations:

Constructs for link and tree types

Constructs for link and tree types

 And here is how it’s used in code:

Using the node object

Using the node object

I think that in the near future, I’ll have enough time to finish these features, and continue implementing important and critical features like function overloading; for now, I think I can finish the support for the & (address of operator), and start writing a library in H++ to demostrate the language capabilities. Now, let’s take a look at the following code:

 

Sorting objects and Scalar types

Sorting objects and Scalar types

 

After I finish the issues with the address of (&) operator, I think my nexts posts should be for demostrating what can be done in H++ with a sample library; that could be the realization of H++ as a programming language.

For the creation of the demo library, I’ll use the book: Data Structures and Algorithms with Object-Oriented Design Patterns by Bruno Preiss; is a good book, and the code could be implemented in H++ with minor changes. Other books I like for this demo library are: The Practice of Programming by Brian Kernighan and Rob Pike, and Programming Pearls by Jon Bentley.

I hope that these sequence of post that describes The H++ Core Language Features, could help you grasp the idea behind H++ as a new programming language, and as my research project.

In the next post, I’ll describe some of the books I was using during my initial development, and also the new books I’m currently reading to prepare me for the next level of in designing this language called H++, and writing its compiler.

See you in the next post!

Posted February 8, 2009 by hmarzan in Uncategorized

Tagged with , ,

The H++ Core Language Features – Part IV   Leave a comment

In this post, I’ll describe the support for arrays in H++.

Local arrays

TH++PL support local arrays up to two (2) dimensions, and dynamic arrays (using the new operator) of one dimension only. When you have the need for more dimensions, you just have to create classes with array data members, and then create arrays of these objects to solve the problem.

Local array of doubles

Local array of doubles

It’s equal to C/C++ when subscripting an array for an element or component:

array subscripting

array subscripting

Here is another example of a sorting algorithm, expecting an array of doubles; also note the Swap function expect references to doubles:

array subscripting

array subscripting

Dynamic arrays

Here is an example of dynamic arrays using the new operator, and a two dimensional local array:

arrays of integer types

arrays of integer types

You can also declare arrays as data members for your classes; to create dynamic arrays, is necessary to use the new operator. Let’s see the picture below:

data member arrays

data member arrays

Static arrays

The support for static arrays is weak, because I’ve not finished the implementation; you can create an static array of object, the constructors will be called as expected; but every time you enter the same function by calling it, the constructors for all these objects that belongs to the same array, will be called also. The correct behavior is to call the constructors once for all the static array objects. So I have to make it happen just once as expected. Let’s see:

static arrays

static arrays

Array of chars

Array of chars

Array of chars

Array of strings

 An array of strings is like an array of const char* in C/C++:
Array of strings

Array of strings

Constructor and Destructor call for Local Object Arrays

For local arrays of objects, and for dynamic arrays, the H++ compiler makes sure that the constructor member function is called for every object in the array in a sequencial order; when the function  terminates, the destructor member function is also called for every object in the same array in the same order.

In the next picture, there is an array of  TestIntegers objects, which also have array data members being accessed in expressions:

local arrays of objects

local arrays of objects

Object Properties

In H++, you can define properties to objects using the get: and put: declarations, like in the TestIntegers class:

Object Properties declarations

Object Properties declarations

 In the next post, I’ll describe the support for custom/user data types, so, see you in the next post!

Posted February 8, 2009 by hmarzan in Uncategorized

Tagged with , ,

The H++ Core Language Features – Part III   Leave a comment

 

In this post, I’ll describe the language statements supported by H++, but before I enter in details, I’ll describe a little bit the support for recursion.

Recursive functions

Recursive functions are very useful for implementing the most popular algorithms like n! and recursive power; but for very CPU intensive algorithms like determining the Fibonacci numbers, it’s not a good idea. Let’s see some popular algorithms implemented in H++ using recursion:

Recursive factorial

Recursive factorial

 Other function implemented with recursion, is the recursive power, a divide and conquer algorithm:

Recursive power

Recursive power

It’s important to note the use of the div operator in this algorithm, the quotient cannot be rounded, and that exactly what H++ does when the result is a floating point number: it round the result.

Another complex recursive function is the Ackermman algorithm:

Ackermman algorithm

Ackermman algorithm

 

H++ Statements

And now, I’ll show the statements supported in H++; I won’t make reference in particular for the if-else statements, because are very clear.

The For loop

Like in C/C++ and C#,  here are variations of the for statement:

Simple for loop

Simple for loop

The for loop with no expressions, is the infinite for loop.

Another loop

Another loop

In the example above, you can note an instance of the class TestFloatingPoint, which implements the recursive power; the loop shows all the powers of base 2, from 2^0 to 2^32; the other loop, does not have an increment expression in it but in the loop body.

You can observe other loops in the following picture:

For loops and static functions

For loops and static functions

This picture also demostrates static functions in H++.

While and do-While loops

These loops are very common in C/C++ and C#; when you have a bool true as the expression of a while statement, that means an infinite loop, so you must pay attention to where you terminate the loop using the break keyword. To avoid breaking, you can use the continue keyword to specify that:

while and do-while loops

while and do-while loops

You can also use the break and continue sub-statements in the for loop.

Goto statement

I know we all hate the goto statement, but this little friend sometimes comes in hand to help you until you re-design or refactor some piece of code to avoid it; H++ also supports the goto statement like in the picture below:

goto statement

goto statement

In the previous picture, I created a loop based on goto statements, for demo purposes only.

A sometimes useful statement is the with block:

with statement

with statement

Actually, I’m not done with the implementation of this statement, because H++ only support l-value expressions in the with block; when I’m done with it, it will also support r-value expressions.

try-catch blocks

TH++PL also supports exceptions actually in a very primitive way (don’t blame me, the subject is not to easy to grasp and understand), but it works! What’s under the generated code, is Structured Exception Handling (SEH); my implementation of SEH will be decribed in later posts that talks about the H++ Compiler and its Code Generator. For now, let’s see some examples of using the try-catch blocks:

try-catch block

try-catch block

Another try-catch block, where you can see a breakpoint that won’t be catched by any debugger, because the SEH exception is being handled by the H++ try-catch block:

try-catch block

try-catch block

I think for now, it’s a brief and quick introduction to the H++ for those who already program C/C++, C# or Java.

In the next post, I’ll describe the support for arrays and object properties

Posted February 8, 2009 by hmarzan in Uncategorized

Tagged with , ,