On the operator overloading in Delphi

4

The operator overloading in Delphi records is straightforward if a record type does not contain fields which reference heap objects. To illustrate the problem which heap references arise let us consider the following (incorrect) example:

program DelphiDemo;

{$APPTYPE CONSOLE}

uses
  SysUtils;

type
  Adder = record
  private
    FRef: PInteger;
    function GetMemory: Integer;
    procedure SetMemory(AValue: Integer);
  public
    procedure Init(AValue: Integer = 0);
    procedure Done;
    class operator Add(const A, B: Adder): Adder;
    property Memory: Integer read GetMemory write SetMemory;
  end;

{ Adder }

class operator Adder.Add(const A, B: Adder): Adder;
begin
// !!! Memory leak
  New(Result.FRef);
  Result.Memory:= A.Memory + B.Memory;
end;

procedure Adder.Done;
begin
  Dispose(FRef);
end;

function Adder.GetMemory: Integer;
begin
  Result:= FRef^;
end;

procedure Adder.Init(AValue: Integer);
begin
  New(FRef);
  FRef^:= AValue;
end;

procedure Adder.SetMemory(AValue: Integer);
begin
  FRef^:= AValue;
end;

procedure Test;
var
  A, B, C: Adder;

begin
  A.Init(1);
  B.Init(2);
  C.Init();
  C:= A + B;
  Writeln(C.Memory);
  C.Done;
  B.Done;
  A.Done;
end;

begin
  ReportMemoryLeaksOnShutdown:= True;
  try
    Test;
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
  ReadLn;
end.

The line #59 (C:= A + B) in the above program works as follows:

  • A temporary Result record is pushed on stack
  • The temporary record receives the sum A + B
  • The temporary record is assigned (by shallow copying) to the C variable
  • The temporary record is popped from stack

It would work fine if Adder did not reference a heap data; the FRef of the Adder record field makes things complicated. You should always initialize FRef field for every Adder instance but you can’t finalize it for a temporary record that is created on line #59. The only way to solve the memory leak issue in the above code is to comment out the line #58, but it will not work for more complicated right-hand side expressions and it is not a solid approach anyway.

The correct solution involves using a type with automatic memory management instead of a simple pointer. Here is a solution that uses interface:

program DelphiDemo2;

{$APPTYPE CONSOLE}

uses
  SysUtils, Classes;

type
  IAdder = interface
    function GetMemory: Integer;
    procedure SetMemory(AValue: Integer);
  end;

  TAdderRef = class(TInterfacedObject, IAdder)
  private
    FMemory: Integer;
    function GetMemory: Integer;
    procedure SetMemory(AValue: Integer);
  end;

  Adder = record
  private
    FRef: IAdder;
    function GetMemory: Integer;
    procedure SetMemory(AValue: Integer);
  public
    procedure Init(AValue: Integer = 0);
    procedure Done;
    class operator Add(const A, B: Adder): Adder;
    property Memory: Integer read GetMemory write SetMemory;
  end;

{ TAdderRef }

function TAdderRef.GetMemory: Integer;
begin
  Result:= FMemory;
end;

procedure TAdderRef.SetMemory(AValue: Integer);
begin
  FMemory:= AValue;
end;

{ Adder }

class operator Adder.Add(const A, B: Adder): Adder;
begin
  Result.FRef:= TAdderRef.Create;
  Result.Memory:= A.Memory + B.Memory;
end;

procedure Adder.Init(AValue: Integer);
begin
  FRef:= TAdderRef.Create;
  FRef.SetMemory(AValue);
end;

procedure Adder.Done;
begin
  FRef:= nil;
end;

function Adder.GetMemory: Integer;
begin
  Result:= FRef.GetMemory;
end;

procedure Adder.SetMemory(AValue: Integer);
begin
  FRef.SetMemory(AValue);
end;

procedure Test;
var
  A, B, C: Adder;

begin
  A.Init(1);
  B.Init(2);
//  C.Init();
  C:= A + B;
  Writeln(C.Memory);
//  C.Done;
//  B.Done;
//  A.Done;
end;

begin
  ReportMemoryLeaksOnShutdown:= True;
  try
    Test;
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
  ReadLn;
end.

A nice side effect of the above approach is that you need not initialize or finalize the FRef fields manually anymore (though you can still do it). Some lines in the Test procedure above were commented out because they are not needed, but they can be uncommented and the code will remain correct – automatic memory management of interfaces takes care of it.

It is very interesting to know how the problem discussed above is solved in C++. The standard C++ approach is totally different – it involves overloading the assignment operator (a feature which Delphi does not support; Delphi allows to overload only conversionImplicit, Explicit operators) and writing a copy constructor (another concept absent in Delphi object model). I am planning to discuss it later.

On the Pointers and References

6

A Reference is a distinct concept in C/C++ languages. The next code sample (MinGW GCC compiler was used)

#include <iostream>

int main()
  {
    int Value;
    int &ValueRef = Value;

    Value = 2;
    std::cout << "Value: " << Value << "\n";
    std::cout << "ValueRef: " << ValueRef << "\n";

    ValueRef = 3;
    std::cout << "Value: " << Value << "\n";
    std::cout << "ValueRef: " << ValueRef << "\n";
    return 0;
  }

declares ValueRef as a reference to Value variable. The output is
_ref1
Though ValueRef variable is a pointer to Value internally the indirection operator is never used, and the syntax for accessing Value directly or indirectly via ValueRef is the same. ValueRef is also called an alias to Value; the point that ValueRef variable is a pointer internally is just an implementation detail.

Another important thing about C/C++ references is that they are always initialized. The language syntax enforces that you cannot declare a wild reference.

Pascal does not have the same reference concept. The closest concept is a procedure parameter passed by reference:

program ref;

{$APPTYPE CONSOLE}

var
  Value: Integer;

procedure Test(var ValueRef: Integer);
begin
  Writeln('ValueRef: ', ValueRef);
  ValueRef:= 3;
end;

begin
  Value:= 2;
  Writeln('Value: ', Value);
  Test(Value);

  Writeln('Value: ', Value);
  Test(Value);
end.

we can see that

  • ValueRef does not use indirection operator to access a referenced variable;
  • the language syntax enforces that ValueRef is always initialized.

Delphi does not elaborate the reference concept, though there are many built-in types in the language that are ‘transparent pointers’ – objects, interfaces, dynamic arrays, strings. The term reference can be used for example for object variables because the language syntax makes these variables indistinguishable from referenced instances. Instead the term object is usually used, that can mean object reference or object instance, so sometimes you think twice to understand what a particular object does mean.

Bitwise operations on big integers

0

Standard fixed-sized negative integers are stored in two’s complement format; for arbitrary-precision big integers the two’s complement format means infinite size, so internally it is not used. Still bitwise operation on big integers are implemented as if negative big integer values are stored in two’s complement format.

As a result bitwise boolean operations (and, or, xor) applied to big integers produce the same results as with standard fixed-sized integers:

procedure Test1(I, J: Integer);
var
  BigI, BigJ: BigInteger;

begin
  BigI:= I;
  BigJ:= J;
  Assert(BigI and BigJ = I and J);
  Assert(BigI or BigJ = I or J);
  Assert(BigI xor BigJ = I xor J);
end;

There is a difference between standard Delphi integer types and big integers in shift operations. Shift operations on big integers preserve sign. That means any shift applied to negative big integer results in negative big integer (the same is for non-negative values):

procedure Test2(I: BigInteger; N: Cardinal);
begin
  Assert(((I shl N) < 0) = (I < 0));
  Assert(((I shr N) < 0) = (I < 0));
end;

That is a natural consequence of the infinite-sized two’s complement negative values. Shift operations on big integers are arithmetic shifts rather than logical shifts. On the other hand ‘shl’ and ‘shr’ operations on the standard Delphi integer types are implemented as logical shifts and does not preserve sign:

procedure Test3;
var
  I: Integer;

begin
  I:= -1;
  Writeln(I shr 2);   // 1073741823, because 'shr' is logical shift
  I:= 1000000000;
  Writeln(I shl 2);   // -294967296, because of 32-bit overflow
end;

PS: right now TForge does not support bitwise operations on BigInteger type, they will be implemented soon.

Be careful with Ord function in Unicode Delphi versions

17

Here is a simple test:

program OrdTest;

{$APPTYPE CONSOLE}

uses
  SysUtils;

begin
  try
    Writeln(Ord('Я'), '  ', Ord(Char('Я')));   // 223,  1071
    Assert(Ord('Я') = Ord(Char('Я')));         // Fails
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
  Readln;
end.

While evaluating the Ord function with hardcoded character parameter the compiler treats the parameter as ANSI character. In the above example Ord(‘Я’) returns 223 (Cyrillic codepage 1251) instead of 1071 (UTF16) as one could expect. As a result the assertion fails (tested on Delphi XE):
assertion failed

After reading the comments I tried another test with both Cyrillic ‘Я’ (=223 on 1251 codepage) and German ‘ß’ (=223 on 1252 codepage):

program OrdTest2;

{$APPTYPE CONSOLE}

uses
  SysUtils;

begin
  try
    Writeln(Ord('Я'), '  ', Ord(Char('Я')));
    Writeln(Ord('ß'), '  ', Ord(Char('ß')));
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
  Readln;
end.

if I set the compiler’s codepage to 1251 I get

if I set the compiler’s codepage to 1252 I get

because German ‘ß’ has the same code (223) both in ANSI 1252 codepage and UTF16 encoding.

Benchmarking BigInteger

0

Last TForge commits contain PiBench console application that calculates decimal digits of Pi using Machin’s formula; the execution takes about 30 seconds on my laptop. The code was written to compare the execution time of subsequent TForge revisions, but it can also be used to compare TForge BigCardinal and BigInteger types with .NET 4.0 BigInteger type.

Here is Delphi PiBench code:

program PiBench;

{$APPTYPE CONSOLE}

uses
  SysUtils, Diagnostics, tfNumerics;

var
  StopWatch: TStopWatch;
  PiDigits: BigCardinal;

procedure BenchMark;
var
  Factor, Num, Den: BigCardinal;
  Term: BigCardinal;
  N, M: Cardinal;

begin
  PiDigits:= 0;
  Factor:= BigCardinal.Pow(10, 10000);
  Num:= 16 * Factor;
  Den:= 5;
  N:= 1;
  repeat
    Term:= Num div (Den * (2 * N - 1));
    if Term = 0 then Break;
    if Odd(N)
      then PiDigits:= PiDigits + Term
      else PiDigits:= PiDigits - Term;
    Den:= Den * 25;
    Inc(N);
  until N = 0;
  M:= N;
  Num:= 4 * Factor;
  Den:= 239;
  N:= 1;
  repeat
    Term:= Num div (Den * (2 * N - 1));
    if Term = 0 then Break;
    if Odd(N)
      then PiDigits:= PiDigits - Term
      else PiDigits:= PiDigits + Term;
    Den:= Den * 239 * 239;
    Inc(N);
  until N = 0;
  M:= (M + N) div 2;
// M last digits may be wrong
  PiDigits:= PiDigits div BigCardinal.Pow(10, M);
end;

begin
  ReportMemoryLeaksOnShutdown:= True;
  try
    Writeln('Benchmark test started ...');
    StopWatch:= TStopWatch.StartNew;
    BenchMark;
    StopWatch.Stop;
    Writeln(PiDigits.AsString);
    PiDigits.Free;
    Writeln;
    Writeln('Elapsed ms: ', StopWatch.ElapsedMilliseconds);
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
  Readln;
end.

And here is equivalent C# application:

using System;
using System.Numerics;
using System.Diagnostics;

namespace PiBench
{
    class Program
    {
        static void Main(string[] args)
        {
            int N, M;
            BigInteger Term;
            Console.WriteLine("Benchmark test started ...");
            Stopwatch Watch = new Stopwatch();
            Watch.Start();
            BigInteger PiDigits = 0;
            BigInteger Factor = BigInteger.Pow(10, 10000);
            BigInteger Num = 16 * Factor;
            BigInteger Den = 5;
            for(N = 1; N != 0; N++){
              Term = Num / (Den * (2 * N - 1));
              if (Term == 0) break;
              if ((N & 1) != 0) PiDigits = PiDigits + Term;
              else PiDigits = PiDigits - Term;
              Den = Den * 25;
            }
            M = N;
            Num = 4 * Factor;
            Den = 239;
            for(N = 1; N != 0; N++){
              Term = Num / (Den * (2 * N - 1));
              if (Term == 0) break;
              if ((N & 1) != 0) PiDigits = PiDigits - Term;
              else PiDigits = PiDigits + Term;
              Den = Den * 239 * 239;
            }
            M = (M + N) / 2;
       // M last digits may be wrong
            PiDigits = PiDigits / BigInteger.Pow(10, M);
            Watch.Stop();
            Console.WriteLine(PiDigits);
            Console.WriteLine();
            Console.WriteLine("Elapsed ms: " + Watch.ElapsedMilliseconds.ToString());
            Console.ReadLine();
        }
    }
}

You can run both and compare; my tests show nearly the same execution time.

TForge

0

My interface-based arbitrary precision integer arithmetic implementation for Delphi and Free Pascal now is a project on BitBucket.
Currently TForge is a single runtime package (tforge.dpk; future releases will also include a language agnostic dll); you can download the project, build the package and start hacking with BigCardinal and BigInteger types by adding tfNumerics unit to uses clause.
The code is not fully tested yet and not optimized at all, so use it carefully.

Here are some implementation details:

1. BigInteger and BigCardinal variables are initialized by assignment:

var A: BigCardinal;
    B: BigInteger;

begin
   A:= 1;
   B:= 2;
   Writeln(A.AsString, ', ', B.AsString);
   ..

2. No need to finalize BigInteger and BigCardinal variables, the compiler does cleanup when a variable goes out of scope; still you can finalize explicitly by Free method. You can also reuse a ‘Freed’ variable:

var A: BigCardinal;

   A:= 1;
   A.Free;
   A:= 10;
   Writeln(A.AsString);

3. Strings can be explicitly casted to BigInteger and BigCardinal types; you can also use TryFromString method to assign a string value to a BigInteger or BigCardinal variable:

var A: BigCardinal;
    B: BigInteger;

begin
  try
   A:= 1;
   B:= BigInteger('1234567890987654321');
   if not A.TryFromString('Wrong string')
     then Writeln('Bad value');
   Writeln(A.AsString, ', ', B.AsString);

4. BigInteger accommodates BigCardinal, so BigCardinal is implicitly casted to BigInteger, and BigInteger is explicitly casted to BigCardinal:

var A: BigCardinal;
    B: BigInteger;

begin
  A:= 1;
  B:= A; // never raises exception
  A:= BigCardinal(B); // no exception here
  B:= -1;
  A:= BigCardinal(B); // exception – negative value
  ..

5. BigInteger and BigCardinal variables can be mixed in Boolean expressions, with BigCardinal casted to BigInteger:

var A: BigCardinal;
    B: BigInteger;

begin
    A:= 1;
    B:= -2;
    if (A > B) then B:= 0;
    ..

6. BigInteger and BigCardinal variables can be mixed in arithmetic expressions, with BigCardinal casted to BigInteger:

var A: BigCardinal;
    B: BigInteger;

begin
    A:= 10;
    B:= -42;
    Writeln( (A * B).AsString);

The project has a public bug tracker, bug reports are welcome!

A word about ‘out’ parameters in Delphi

5

Delphi compiler has a contract – any interface variable should be either a valid reference or nil. The same also applies to other lifetime managed types – strings and dynamic arrays. An interesting consequence of the contract is how Delphi interprets ‘out’ function parameters.
As the name suggests, ‘out’ means that an input value of a parameter should be ignored inside a function; but Delphi compiler cannot ignore input value of a lifetime managed instance. It decrements the reference count of an instance when an instance is no longer needed if a reference to instance is not nil.
As a workaround Delphi compiler applies the following trick. Suppose we have a procedure

procedure Foo(out II: IInterface);
begin
  II:= TInterfacedObject.Create;
end;

a call of the procedure

  Foo(II);

compiles as:

II:= nil;
Bar(II);

where

procedure Bar(var II: IInterface);
begin
  II:= TInterfacedObject.Create;
end;

Bar procedure decrements the reference count of the input parameter instance; the meaning of ‘out‘ parameter forbids to do so. Since Delphi compiler cannot ignore input value of a lifetime manage instance the problem was solved by assigning nil value to a parameter before calling a procedure.

Big Integer redux

9

I started a project that will include Big Integer math implementation (common Delphi&FPC codebase) based on interfaces without objects. Right now the project reached the stage where I am able to compile (and run!) code like that:

{
  Usage example: BinomCoff 120 42
  Demonstrates how to use BigCardinal type
  see also:

http://rosettacode.org/wiki/Evaluate_binomial_coefficients#Delphi

}
program BinomCoff;

{$APPTYPE CONSOLE}

uses
  SysUtils, tfNumerics;

function BinomialCoff(N, K: Cardinal): BigCardinal;
var
  L: Cardinal;

begin
  if N < K then
    Result:= 0      // Error
  else begin
    if K > N - K then
      K:= N - K;    // Optimization
    Result:= 1;
    L:= 0;
    while L < K do begin
      Result:= Result * (N - L);
      Inc(L);
      Result:= Result div L;
    end;
  end;
end;

var
  A: BigCardinal;
  M, N: Cardinal;

begin
  ReportMemoryLeaksOnShutdown:= True;
  try
    if ParamCount <> 2 then begin
      Writeln('Usage example: BinomCoff 120 42');
      ReadLn;
      Exit;
    end;
    N:= StrToInt(ParamStr(1));
    M:= StrToInt(ParamStr(2));
    A:= BinomialCoff(N, M);
    Writeln('C(', N, ', ', M, ') = ', A.AsString);
    A:= BigCardinal(nil);   // A is global var and should be freed explicitely
                            //   to prevent memory leak on shutdown
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
  ReadLn;
end.

Output:

A lot still yet to be done, but it works! :)

Nice feature of Lazarus IDE

4

Lazarus treats include files (*.inc) as a part of a project. That means you should not bother where you store include files in a project – just

{$I Smth.inc}

is enough.

Not so in Delphi (Delphi XE to be exact). You can add *.inc file to a Delphi project, but it does not matter for Delphi, you still need to write paths to include files like that

{$I ..\..\Source\Common\Smth.inc}

and sure the paths are different for units in different project folders.

Introduction to unit testing with Lazarus

2

1. Lazarus 1.0 comes with built-in unit testing framework called FPCUnit. FPCUnit is another Pascal clone of Java JUnit framework, like DUnit framework supplied with Delphi, but different from DUnit in some details.
If you are absolutely new to unit testing (or to Lazarus, like me) create your first unit test project by running the wizard. Select File->New… from IDE menu, choose FPCUnit Test Application and click ‘OK’:

Check two checkboxes and click ‘OK’ in the next dialog:

The wizard is very primitive, but you need not anything more. You can save the generated unit test project as a template and never run the wizard again.

2. Now time add a unit under test to the project. Most usual unit under test is a class, but it also can be a record with methods, or a pascal unit with flat procedures in interface section. For demonstration purposes I have written TCalc class implementing a simple calculator to be a unit under test:

unit Calcs;

{$mode objfpc}{$H+}

interface

uses
  Classes, SysUtils;

type
  TCalc = class
  private
    FAccumulator: Integer;
  public
    procedure Clear;
    procedure Add(Value: Integer);
    procedure Sub(Value: Integer);
    property Accumulator: Integer read FAccumulator;
  end;

implementation

{ TCalc }

procedure TCalc.Clear;
begin
  FAccumulator:= 0;
end;

procedure TCalc.Add(Value: Integer);
begin
  FAccumulator:= FAccumulator + Value;
end;

procedure TCalc.Sub(Value: Integer);
begin
  FAccumulator:= FAccumulator - Value;
end;

end.

3. To implement a testing of a unit we create a test case. Our generated unit test project already contains one test case – that is TTestCase1 class. Our unit under test has 3 functions to be tested: the methods TCalc.Clear, TCalc.Add and TCalc.Sub. Edit testcase1.pas unit as follows:

unit TestCase1;

{$mode objfpc}{$H+}

interface

uses
  Classes, SysUtils, fpcunit, testutils, testregistry, Calcs;

type
  TTestCase1= class(TTestCase)
  private
    FCalc: TCalc;
  protected
    procedure SetUp; override;
    procedure TearDown; override;
  published
    procedure Clear;
    procedure Add;
    procedure Sub;
  end;

implementation

procedure TTestCase1.SetUp;
begin
  FCalc:= TCalc.Create;
end;

procedure TTestCase1.TearDown;
begin
  FCalc.Free;
end;

procedure TTestCase1.Clear;
begin
  FCalc.Clear;
  AssertEquals(FCalc.Accumulator, 0);
end;

procedure TTestCase1.Add;
begin
  FCalc.Add(42);
  AssertEquals(FCalc.Accumulator, 42);
end;

procedure TTestCase1.Sub;
begin
  FCalc.Sub(42);
  AssertEquals(FCalc.Accumulator, -42);
end;

initialization
  RegisterTest(TTestCase1);
end.

4. Our first unit test project is ready now. Run it and see the result:

5. We created a published method of a test case for every tested function of a unit under test. Unit testing framework includes published methods of test case class into a test runner application. Notice that Setup and TearDown methods of a test case are called every time a published method of a test case is called. When I started to use unit testing I thought that Setup (TearDown) is called when test case class is created (destroyed) – that is not true, they are called ‘per function’.

6. You can add more units under test to a unit test project. If you have several units under test (and correspondent test cases) in a project you can have a separate test register unit. Remove the initialization section from the test case unit, add a second unit testcase2.pas with TTestCase2 test case class (you can make a replica of the first) to the project, and create a new RegTests.pas unit in to register test cases:

unit RegTests;

{$mode objfpc}{$H+}

interface

uses
  Classes, SysUtils, testregistry, testcase1, testcase2;

implementation

initialization
  RegisterTest(TTestCase1);
  RegisterTest(TTestCase2);
end.

Now we have a unit test project with 2 test cases:

7. If your unit test project grows one day you will want to have a hierarchical structure of test cases instead of a flat one. You can create a test hierarchy using a different RegisterTest overload. Create an additional hierarchy levels by updating RegTests.pas unit as follows:

unit RegTests;

{$mode objfpc}{$H+}

interface

uses
  Classes, SysUtils, testregistry, testcase1, testcase2;

implementation

initialization
  RegisterTest('Level1.Level2', TTestCase1);
  RegisterTest('Level1.Level2', TTestCase2);
end.

8. Our oversimplified test case class contains all testing code inside the published methods. More realistic published methods are wrappers for other functions which perform actual testing. You may be tempted to add private methods and fields to test case classes; it is OK if your test case class is simple, otherwise you will soon find your test case class cluttered with a mess of methods corresponding to different tests (published methods). My own experience leaded me to creating (if needed) a separate helper class for every test. These helper classes inherit from a common base class which provides access to TTestCase functions:

type
  TTestHelper = class
  private
    FTestCase: TTestCase;
  public
    constructor Create(ATestCase: TTestCase);
    property TestCase: TTestCase read FTestCase;
  end;

implementation

constructor TTestHelper.Create(ATestCase: TTestCase);
begin
  FTestCase:= ATestCase;
end;

Happy unit testing with FPCUnit and Lazarus!