Compiling I D Hill's New Zealand Meek STV implementation: OpenTally dev log
In [1], I D Hill describes an implementation of Meek STV written in Pascal, which had been privately circulated since as early as 1999 [2]. The implementation is similar to the earlier ‘Algorithm 123’ Pascal implementation of Meek STV by Hill, Wichmann and Woodall [3], but introduces a number of refinements, such as the deferred transfer of small surpluses.
Hill's Meek STV implementation was available to those working on the rules for Meek STV for elections in New Zealand, and those rules – to date the only large scale implementation of Meek STV – retain the refinements made by Hill.
It would therefore be helpful to be able to use Hill's Meek STV implementation as a reference to validate implementations of the New Zealand electoral rules. When implementing OpenTally, open-source software for election counting, the only publicly available implementation of New Zealand Meek STV was from OpenSTV 1.7. As the New Zealand election counting software is not itself publicly available, the OpenSTV implementation had ‘not been verified’.
Recently, extracts from Hill's election counting software comprising the Pascal code relevant to New Zealand-style Meek STV, which appear to have been provided by Hill to those developing New Zealand's electoral rules, have been published as an ebook (Archive.org, Amazon) by Richard Lung, along with notes on the code by Hill.
The code
The code from Lung's ebook totals 1802 nonblank lines of Pascal. The first line is:
program nzmeek(datafile,outt,tmpp,rslt,confile,oei,ramm,rann);
The final 4 lines are:
shutdown(rslt);erase(tmpp);
anykey(25);
cursoron;initscreen{note 37}
end.
The software in [2] is labelled version 6.4.1, whereas the published code identifies itself as version 6.7.7.
Dealing with nonstandard features
Unlike the Algorithm 123 implementation, Hill's code relies on a number of nonstandard Pascal features, and so some work is required to compile the code on a modern system.
Hill's nzmeek code depends, in Hill's words, on certain ‘compiler-supplied’ types and routines. Some of these appear to be from Turbo Pascal, whereas others are of unknown provenance.
Lines 19 and 20 of the code read:
{$i paspc} {Although in the form of a comment, this is an instruction
to include extra compiler-supplied features}
In modern Pascal, this is a directive to include code from the file paspc.pas. Therefore, we should create a file paspc.pas and implement the relevant ‘compiler-supplied’ functionality. We will target the Free Pascal compiler.
We begin with each ‘compiler-supplied subtype of integer’:
{"Compiler-supplied" types for nzmeek}
type integer = int32;
type integer1 = int8;
type integer2 = int16;
Various ‘compiler-supplied routine’ implementations are already found within the Free Pascal CRT unit. We then need only implement those other CRT-related routines which are not standard in Free Pascal:
uses Crt;
{...}
{"Compiler-supplied" CRT routines}
var ColPaper, ColInk: byte;
const lightgrey = LightGray;
procedure clrvideo;
begin
ClrScr
end;
procedure getkeyboard(var a: char; var b: byte);
begin
a := ReadKey
end;
procedure initscreen;
begin
TextBackground(Black);
TextColor(LightGray);
ClrScr
end;
procedure ink(a: byte);
begin
ColInk := a;
TextColor(a)
end;
procedure paper(a: byte);
begin
ColPaper := a;
TextBackground(a)
end;
procedure putchattr(a: char; b, c, d: byte);
var x, y: byte;
begin
x := WhereX();
y := WhereY();
TextBackground(b);
TextColor(c);
Write(a);
GotoXY(x, y);
TextBackground(ColPaper);
TextColor(ColInk)
end;
procedure soundoff;
begin
NoSound
end;
Next, we implement each remaining ‘compiler-supplied routine’:
uses Crt, Sysutils;
{...}
{Other "Compiler-supplied" routines}
procedure close(var a: text; b: boolean);
begin
System.Close(a)
end;
procedure exitprog(a: longint);
begin
Halt(a)
end;
function get(var a: text): char;
var c: char;
begin
Read(a, c);
get := c
end;
function memavail: integer;
begin
memavail := 999999
end;
procedure ramfile(var a: text);
begin
Assign(a, GetTempFileName)
end;
{FIXME: Stub implementation not necessary for nzmeek to run}
function fstat(a:string): boolean; begin fstat:=false; end;
procedure time(var a,b,c,d:integer); begin end;
This implements all of the necessary ‘compiler-supplied’ types and routines used by nzmeek; however, nzmeek also appears to use the pointer dereference operator to ‘peek’ into opened files. This is not supported in Free Pascal (and, indeed, I struggled to identify any Pascal variant where this is supported). Pointer dereference is one of only 2 operators in Free Pascal which cannot be overloaded, and so we must modify the code to remove this use.
For example, line 991 of the nzmeek code reads:
else if ramm^='0' then ended:=true;
To make this compliant with Free Pascal syntax, we must replace this with:
else if peek(ramm)='0' then ended:=true;
There are a total of 16 such modifications which need to be made.
Finally, we add a definition of peek into paspc.pas:
{Peek function instead of dereference}
function peek(var a: text): char;
var c: char;
begin
Read(a, c);
Dec(TextRec(a).bufpos);
peek := c
end;
Other patches
Lines 1380 to 1391 of the nzmeek code read:
command('dir votes.dat >votes.tep',nn);{note 32}
assign(tmpp,'votes.tep');reset(tmpp);
repeat
readln(tmpp,str1)
until(pos('VOTES',str1)>0)and(pos('DAT',str1)>0);
filesize:=0;nn:=1;
while(str1[nn]<'0')or(str1[nn]>'9')do nn:=nn+1;
repeat
filesize:=10*filesize+ord(str1[nn])-48;
nn:=nn+1
until str1[nn]=' ';
erase(tmpp);
In the notes accompanying the code, it is noted that an external command (MS-DOS dir) is used to determine the filesize of the input file, which is stored in filesize. Clearly, MS-DOS commands are not portable across different operating systems. Additionally, the value of filesize is used only to determine whether to store temporary data on disk or in memory. Memory is not as scarce as it was circa 1999, and so this check is unimportant.
Therefore, we can simply replace these lines with:
filesize:=0;
No other changes are required to allow nzmeek to compile and run; however, there is a minor bug due to the cleaning up of temporary data. In the original code, it appears that temporary data was stored purely in RAM, but in our paspc.pas we have implemented this using temporary files, so those files must be closed and deleted in order to avoid a resource leak.
We can fix this by changing the line originally numbered 1799 (now 1788) from:
shutdown(rslt);erase(tmpp);
to
shutdown(rslt);close(tmpp,true);erase(tmpp);close(ramm,true);erase(ramm);
The final product
We can now compile the software as usual:
$ fpc nzmeek.pas
Free Pascal Compiler version 3.2.2 [2021/05/31] for x86_64
Copyright (c) 1993-2021 by Florian Klaempfl and others
Target OS: Linux for x86-64
Compiling nzmeek.pas
nzmeek.pas(975,5) Note: Local variable "j" not used
nzmeek.pas(977,1) Note: Local variable "str1" not used
nzmeek.pas(1030,10) Note: Local variable "mm" not used
nzmeek.pas(1030,13) Note: Local variable "marker" not used
nzmeek.pas(1032,21) Note: Local variable "tot1" not used
nzmeek.pas(1032,26) Note: Local variable "tot2" not used
nzmeek.pas(1264,5) Note: Local variable "arg1" not used
nzmeek.pas(1264,10) Note: Local variable "arg2" not used
nzmeek.pas(1305,1) Note: Local variable "answered" not used
nzmeek.pas(32,39) Note: Local variable "nn" not used
nzmeek.pas(35,1) Note: Local variable "constrained" is assigned but never used
nzmeek.pas(39,7) Note: Local variable "conmarker" is assigned but never used
nzmeek.pas(42,7) Note: Local variable "str1" not used
Linking nzmeek
1896 lines compiled, 0.2 sec
13 note(s) issued
As documented in the notes accompanying the software, nzmeek takes a BLT file (same format as described in [3]) named votes.dat and outputs the results to votes.res (result summary), votes.oei (detailed results data) and votes.rlt (computer-readable results).
For example, the results when counting my ballot papers for the ERS97 model election are:
New Zealand demonstration
Version 6.7.7 - NZ rules
Number of candidates = 11
Number of seats = 6
ERS97 Model Election
Table: 1 Count: 1 Quota: 107.57
Candidate Keep Transfer Votes
Smith 100.0% 0.0% 134.00 >>> Elected
Carpenter 100.0% 0.0% 81.00
Wright 100.0% 0.0% 27.00
Glazier 100.0% 0.0% 24.00
Duke 100.0% 0.0% 105.00
Prince 100.0% 0.0% 91.00
Baron 100.0% 0.0% 64.00
Abbot 100.0% 0.0% 59.00
Vicar 100.0% 0.0% 55.00
Monk 100.0% 0.0% 23.00
Freeman 100.0% 0.0% 90.00
Non-transferable 0.00
Total 753.00
>>>>> Smith elected <<<<<
ERS97 Model Election
Table: 2 Count: 2 Quota: 107.26
Candidate Keep Transfer Votes
Smith 80.3% 19.7% 107.57 >>> Elected
Carpenter 100.0% 0.0% 87.90
Wright 100.0% 0.0% 31.93
Glazier 100.0% 0.0% 30.11
Duke 100.0% 0.0% 106.58
Prince 100.0% 0.0% 91.00
Baron 100.0% 0.0% 64.00
Abbot 100.0% 0.0% 59.79
Vicar 100.0% 0.0% 55.00
Monk 100.0% 0.0% 23.39
Freeman 100.0% 0.0% 93.55
Non-transferable 2.17
Total 753.00
Lowest candidate cannot overtake, so can safely be excluded.
>>>>> Monk excluded <<<<<
ERS97 Model Election
Table: 3 Count: 3 Quota: 107.26
Candidate Keep Transfer Votes
Smith 80.0% 20.0% 108.86 >>> Elected
Carpenter 100.0% 0.0% 87.98
Wright 100.0% 0.0% 31.99
Glazier 100.0% 0.0% 30.19
Duke 100.0% 0.0% 108.80 >>> Elected
Prince 100.0% 0.0% 91.00
Baron 100.0% 0.0% 64.00
Abbot 100.0% 0.0% 64.80
Vicar 100.0% 0.0% 69.20
Monk 0.0% 100.0% 0.00 Excluded
Freeman 100.0% 0.0% 93.99
Non-transferable 2.19
Total 753.00
>>>>> Duke elected <<<<<
ERS97 Model Election
Table: 4 Count: 4 Quota: 107.02
Candidate Keep Transfer Votes
Smith 78.9% 21.1% 107.26 >>> Elected
Carpenter 100.0% 0.0% 88.40
Wright 100.0% 0.0% 32.28
Glazier 100.0% 0.0% 30.55
Duke 98.6% 1.4% 107.36 >>> Elected
Prince 100.0% 0.0% 91.00
Baron 100.0% 0.0% 64.00
Abbot 100.0% 0.0% 64.85
Vicar 100.0% 0.0% 69.21
Freeman 100.0% 0.0% 94.23
Non-transferable 3.86
Total 753.00
Lowest candidate cannot overtake, so can safely be excluded.
>>>>> Glazier excluded <<<<<
ERS97 Model Election
Table: 5 Count: 5 Quota: 106.36
Candidate Keep Transfer Votes
Smith 78.7% 21.3% 109.38 >>> Elected
Carpenter 100.0% 0.0% 96.46
Wright 100.0% 0.0% 33.97
Glazier 0.0% 100.0% 0.00 Excluded
Duke 98.3% 1.7% 117.85 >>> Elected
Prince 100.0% 0.0% 91.19
Baron 100.0% 0.0% 64.00
Abbot 100.0% 0.0% 65.85
Vicar 100.0% 0.0% 70.70
Freeman 100.0% 0.0% 95.11
Non-transferable 8.48
Total 753.00
Lowest candidate cannot overtake, so can safely be excluded.
>>>>> Wright excluded <<<<<
ERS97 Model Election
Table: 6 Count: 7 Quota: 103.71
Candidate Keep Transfer Votes
Smith 63.0% 37.0% 104.60 >>> Elected
Carpenter 100.0% 0.0% 111.56 >>> Elected
Wright 0.0% 100.0% 0.00 Excluded
Duke 87.1% 12.9% 105.66 >>> Elected
Prince 100.0% 0.0% 96.49
Baron 100.0% 0.0% 67.01
Abbot 100.0% 0.0% 68.70
Vicar 100.0% 0.0% 73.07
Freeman 100.0% 0.0% 98.88
Non-transferable 27.04
Total 753.00
>>>>> Carpenter elected <<<<<
ERS97 Model Election
Table: 7 Count: 10 Quota: 101.72
Candidate Keep Transfer Votes
Smith 61.4% 38.6% 101.92 >>> Elected
Carpenter 90.7% 9.3% 102.07 >>> Elected
Duke 83.9% 16.1% 101.94 >>> Elected
Prince 100.0% 0.0% 97.01
Baron 100.0% 0.0% 67.22
Abbot 100.0% 0.0% 68.90
Vicar 100.0% 0.0% 73.25
Freeman 100.0% 0.0% 99.73
Non-transferable 40.96
Total 753.00
Lowest candidate cannot overtake, so can safely be excluded.
>>>>> Baron excluded <<<<<
ERS97 Model Election
Table: 8 Count: 11 Quota: 92.03
Candidate Keep Transfer Votes
Smith 61.3% 38.7% 101.72 >>> Elected
Carpenter 90.4% 9.6% 101.79 >>> Elected
Duke 83.7% 16.3% 101.73 >>> Elected
Prince 100.0% 0.0% 97.05 >>> Elected
Baron 0.0% 100.0% 0.00 Excluded
Abbot 100.0% 0.0% 68.91
Vicar 100.0% 0.0% 73.26
Freeman 100.0% 0.0% 99.77 >>> Elected
Non-transferable 108.77
Total 753.00
>>>>> Freeman elected <<<<<
>>>>> Prince elected <<<<<
ERS97 Model Election
Table: 9 Count: 19 Quota: 74.49
Candidate Keep Transfer Votes
Smith 45.2% 54.8% 75.06 >>> Elected
Carpenter 61.5% 38.5% 75.24 >>> Elected
Duke 61.1% 38.9% 75.08 >>> Elected
Prince 74.2% 25.8% 75.15 >>> Elected
Abbot 100.0% 0.0% 70.69
Vicar 100.0% 0.0% 75.03 >>> Elected
Freeman 71.5% 28.5% 75.17 >>> Elected
Non-transferable 231.59
Total 753.00
>>>>> Vicar elected <<<<<
>>>>> Abbot excluded <<<<<
because all seats are now filled.
Election complete
With this test case, the OpenTally, OpenSTV 1.7 and nzmeek implementations of New Zealand Meek STV have been validated against each other.
References
[1] Hill ID. Implementing STV by Meek's method. Voting Matters. 2006 Jul; (22): 7–10. http://www.votingmatters.org.uk/ISSUE22/I22P2.pdf
[2] Wichmann BA. Validation of implementation of the Meek algorithm for STV. London: McDougall Trust; 2000 Apr 28. http://www.votingmatters.org.uk/RES/MKVAL.pdf
[3] Hill ID, Wichmann BA, Woodall DR. Algorithm 123: single transferable vote by Meek's method. The Computer Journal. 1987 Jun; 30: 277–81. doi: 10.1093/comjnl/30.3.277. In corrected form at: https://www.dia.govt.nz/diawebsite.NSF/Files/meekm/%24file/meekm.pdf