-----BEGIN PGP SIGNED MESSAGE----- % Vote counting program, using the quota preferential (single % transferable vote) method of proportional representation. % See "Rules for conducting PR elections" by the % Proportional Representation Society of Australia % for the algorithm. % % This should probably be seen as a prototype system. However, with % today's hardware (and improvements I made in September 1997 for the % University of Queensland Student Union election) it can be used for % elections with several thousand ballots and over ten candidates. % Usage: count < ballot_file (main_stdin/1 as top level predicate) % or run from WWW via CGI (main/1 as top level predicate) % eg, http://www.cs.mu.oz.au/~lee/prsa/count/count_form.html % % The ballot file is a simple text file containing three Prolog terms: % The list of candidates (list(atom)) % The number of vacancies (integer) % The list of ballots, ecah ballot being a list of % candidates (list(list(atom))) % The text inside the /* */ comment below is valid input, for example /* % Note: everything from a '%' to the end of line is a comment and is ignored % Whitespace is also not significant % first the candidates - here we use single letters but any sequence of % letters, digits and underscores starting with a lower case letter is % acceptable. You can also use any sequence of characters enclosed in % single quotes '...'. The candidates must be in a comma separated list % enclosed in brackets [..] and terminated with a period then a white % space. (ok, the whitespace char after a period *is* significant) [a, b, c, d, e, f]. 3. % the number of vacancies - an integer terminated with a period+ws % now the list of ballots: same list syntax as before but here each % element of the list of ballots is a list of candidates. There is a % single period+ws terminating the whole list of lists [ [a, b, c, d], % the first ballot: first preference is for candidate 'a' % second preference is candidate 'b' % third preference is candidate 'c' % fourth preference is candidate 'd' % no further preferences [a, b, c, d], % another ballot, with the same preferences [a], % This one has only the first preference marked [d, a, b, c, f, e], % all preferences are given in this one [b, a, f, e], [b, a, f, e], [b, a, f, d], [c, a, f, d], [c, d, f, a], [d, a, b, c, f], [e, f, d, a, b] % the last one - note there is no comma ]. % end of the list of ballots */ % % Author: Lee Naish (lee@cs.mu.oz.au) % % Things to do % Add more comments & refer to sections of the counting manual. % Don't bother saving exhausted ballots explicitly? % Don't bother saving preferences which are not continuing? % Return "counting sheet" as well as elected candidates... % This has now bee done, though we could return more info, eg % remainders and (further) improve output (eg, html) % Do "count back" for excluding candidates with = votes. % Fix init_value. % Make dist_1a etc more efficient? % Check validity of ballots better initially. % Terminate count as soon as enough are elected. % Translate to Mercury -> C % Abbreviations used in code % % N Number of % ...s (postfix s) List of % NVac Number of vacancies % Q Quota % % Bal Ballot % Par Parcel (of ballots) % Stk Stack (of parcels) % Val Value (of ballot/parcel/stack) % % Can Candidate % S Successful (candidates may be successful) % E Excluded (candidates may be excluded) % Exh Exhausted (ballots may be exhausted) % % eg, % SStks = List of Successful (candidate) Stacks % NSCan = Number of Successful Candidates % ExhPars = List of Parcels of Exhausted ballots % Test interface to HTML forms for NU-Prolog % Adapted from C code from Andrew Davison (http://www.cs.mu.oz.au/~ad), % who got it from elsewhere no doubt. % top level main(_) :- html_form_interface. % Standalone interface - input contains % list of candidates; number of vacancies; list of ballots. % Each ballot is a list of candidates. main_stdin(_) :- read(Cans), read(NVac), read(Bals), count(Bals, NVac, Cans, SCans, Stages), write_stages(Stages, SCans). % PR count % Given list of ballots, number of vacancies and % list of candidates, return list of successful candidates % Assume all ballots are formal (should check?) :- pred count(ballots, posInt, candidates, candidates, stages). count(Bals, NVac, Cans, SCans, Stage1.Stages) :- length(Bals, NBal), init_value(NBal, NVac, Val), Q is (NBal * Val) // (NVac + 1) + 1, init_stacks(Cans, Stks), distribute(Bals, Val, Stks, Stks1, stack(exhausted, 0, []), ExhStk), check_success(Q, Stks1, Stks2, SStks, SCans1), Stage1 = stage(init(Cans, NBal, NVac, Q, SCans1), Stks2, ExhStk, SStks, []), length(SCans1, NSCan), NVac1 is NVac - NSCan, append(SCans1, SCans2, SCans), count1(NVac1, Q, Stks2, ExhStk, SStks, [], SCans2, Stages). % continue count % Given unfilled vacancies, quota, stacks for % continuing candidates + exhausted % + list of elected candidates' stacks not dealt with and, % parcels of eliminated candidate not yet dealt with, % return list of successful candidates; :- pred count1(nonNeg, posInt, stacks, stack, stacks, parcels, candidates, stages). % nothing pending -> exclude someone or elect everyone count1(NVac, Q, Stks, ExhStk, [], [], SCans, Stages) :- length(Stks, NCan), % (if NCan > NVac then (NCan > NVac -> % then exclude(Stks, stack(_, _, EPars), Stks1, ECan), reverse(EPars, EPars1), Stages = stage(exclusion(ECan), Stks1, ExhStk, [], []).Stages1, count1(NVac, Q, Stks1, ExhStk, [], EPars1, SCans, Stages1) ; % else Stages = [stage(elect_all, [], [], [], [])], elect_all(Stks, SCans) ). % no exclusions but possible surplus pending count1(NVac, Q, Stks, ExhStk, stack(SCan, Val, parcel(_PVal, NBal, Bals)._).SStks, [], SCans, Stage.Stages) :- % Note: transfer value does not take account % of (now) exhausted ballots (opinion is % divided on whether this should be done). Stage = stage(dist_surplus(SCan, SCans1), Stks2, ExhStk1, SStks2, []), TransVal is (Val - Q) // NBal, distribute(Bals, TransVal, Stks, Stks1, ExhStk, ExhStk1), check_success(Q, Stks1, Stks2, SStks1, SCans1), length(SCans1, NSCan), NVac1 is NVac - NSCan, append(SCans1, SCans2, SCans), append(SStks, SStks1, SStks2), count1(NVac1, Q, Stks2, ExhStk1, SStks2, [], SCans2, Stages). % exclusion pending count1(NVac, Q, Stks, ExhStk, SStks, parcel(PVal, _NBal, Bals).EPars, SCans, Stage.Stages) :- % same as prev clause -> combine Stage = stage(dist_excluded(SCans1), Stks2, ExhStk1, SStks2, EPars), distribute(Bals, PVal, Stks, Stks1, ExhStk, ExhStk1), check_success(Q, Stks1, Stks2, SStks1, SCans1), length(SCans1, NSCan), NVac1 is NVac - NSCan, append(SCans1, SCans2, SCans), append(SStks, SStks1, SStks2), count1(NVac1, Q, Stks2, ExhStk1, SStks2, EPars, SCans2, Stages). % distribute ballots over stacks for continuing candidates % (or exhausted) :- pred distribute(ballots, posInt, stacks, stacks, stack, stack). distribute(Bals, Val, Stks0, Stks, stack(exhausted, EVal0, ExhPars), stack(exhausted, EVal, parcel(Val, 0, EBals).ExhPars)) :- add_mt_parcels(Stks0, Val, Stks1), dist_all(Bals, Val, Stks1, Stks, 0, EVal1, EBals), % % findall wrapper used to reclaim memory wasted due to % inefficient dist_1a implementation - unfortunately this % also does some copying which wastes time and (other) space... % What we really want is a garbage collector... % % findall(foo(TmpStks, TmpEVal1, TmpEBals), ( % add_mt_parcels(Stks0, Val, Stks1), % dist_all(Bals, Val, Stks1, TmpStks, 0, TmpEVal1, TmpEBals)), % [foo(Stks, EVal1, EBals)]), EVal is EVal0 + EVal1. % add an empty parcel to top of each stack, % for distribution :- pred add_mt_parcels(stacks, posInt, stacks). add_mt_parcels([], _, []). add_mt_parcels(stack(Can, StkVal, Pars).Stks0, Val, stack(Can, StkVal, parcel(Val, 0, []).Pars).Stks) :- add_mt_parcels(Stks0, Val, Stks). % as above, exhausted stack unwrapped :- pred dist_all(ballots, posInt, stacks, stacks, nonNeg, nonNeg, ballots). dist_all([], _Val, Stks, Stks, EVal, EVal, []). dist_all(Bal.Bals, Val, Stks0, Stks, EVal0, EVal, EBals) :- % (if some Stks1 dist_1(Stks0, Bal, Val, Stks1) then (dist_1(Stks0, Bal, Val, Stks1) -> % then dist_all(Bals, Val, Stks1, Stks, EVal0, EVal, EBals) ; % else EVal1 is EVal0 + Val, EBals = Bal.EBals1, dist_all(Bals, Val, Stks0, Stks, EVal1, EVal, EBals1) ). % distribute a single ballot to a stack, if suitable stack exists :- pred dist_1(stacks, ballot, posInt, stacks). dist_1(Stks0, Bal, Val, Stks) :- dist_1a(Stks0, Bal, Bal, Val, Stks). % as above; keep copy of whole ballot % (currently this is very inefficient) % Comp = Complete :- pred dist_1a(stacks, ballot, ballot, posInt, stacks). dist_1a(Stks0, Can.Cans, CompBal, Val, Stks) :- % (if some [StkVal0, ParNum, ParVal, Bals0, Pars, Stks1] ( delete(stack(Can, StkVal0, parcel(ParVal, ParNum, Bals0).Pars), Stks0, Stks1) -> % then StkVal1 is StkVal0 + Val, ParNum1 is ParNum + 1, Stks = stack(Can, StkVal1, parcel(ParVal, ParNum1, CompBal.Bals0).Pars).Stks1 ; % else % check other preferences dist_1a(Stks0, Cans, CompBal, Val, Stks) ). % check for more than a quota of votes :- pred check_success(posInt, stacks, stacks, stacks, candidates). check_success(_Q, [], [], [], []). check_success(Q, stack(Can, Val, Bals).Stks0, Stks, SStks, SCans) :- % (if Val >= Q then (Val >= Q -> % then Stks1 = Stks, % writeln(electing(Can)), %% temporary output SStks = stack(Can, Val, Bals).SStks1, SCans = Can.SCans1 ; % else Stks = stack(Can, Val, Bals).Stks1, SStks = SStks1, SCans = SCans1 ), check_success(Q, Stks0, Stks1, SStks1, SCans1). % initial value = 1000 (change) :- pred init_value(posInt, posInt, posInt). init_value(_, _, 1000). % form list of empty stacks from list of candidates :- pred init_stacks(candidates, stacks). init_stacks([], []). init_stacks(Can.Cans, stack(Can, 0, []).Stks) :- init_stacks(Cans, Stks). % form list of candidates from list of stacks :- pred elect_all(stacks, candidates). elect_all([], []). elect_all(stack(Can, _, _).Stks, Can.Cans) :- elect_all(Stks, Cans). % exclude whoever has smallest number of votes % (if equal then "first" one is excluded, not one which % was behind most recently - this is a BUG) % Currently we don't have access to the "history" of the % count so we can't figure out the right one. % This rule for deciding who to exclude is arbitrary anyway. % The Church of England rules (which are very similar) exclude % the person was behind *earliest* in the count. % In any case, its % very unlikely to make any difference to the outcome. % (I guess we could return multiple solutions quite easily % since its Prolog, and see if the outcome *is* the same) :- pred exclude(stacks, stack, stacks, candidate). exclude(Stk0.Stks0, EStk, Stks, Can) :- Stk0 = stack(_, Val, _), min_stk(Stks0, Stk0, Val, EStk), % could use min/3 EStk = stack(Can, _EVal, _), % find candidate % writeln(excluding(Can, EVal)), %% temporary output delete(EStk, Stk0.Stks0, Stks). % find stack to exclude (with accumulator) :- pred min_stk(stacks, stack, nonNeg, stack). min_stk([], AStk, _, AStk). min_stk(Stk.Stks, AStk, AVal, EStk) :- Stk = stack(_, Val, _), % (if Val < AVal then (Val < AVal -> % then min_stk(Stks, Stk, Val, EStk) ; % else min_stk(Stks, AStk, AVal, EStk) ). % write out stages of election for reporting :- pred write_stages(stages, candidates). write_stages([], SCans) :- format( "Final result: the following candidates are elected:\n", []), format_all(" ~a\n", SCans). write_stages(S.Ss, SCans) :- write_stage(S), write_stages(Ss, SCans). % write out single stage :- pred write_stage(stage). write_stage(stage(init(Cans, NBal, NVac, Q, SCans), Stks, ExhStk, SStks, EPars)) :- format("List of candidates:\n", []), format_all(" ~a\n", Cans), length(Cans, NCans), format("\nNumber of candidates: ~d\n", [NCans]), format("Number of vacancies: ~d\n", [NVac]), format("Number of ballots: ~d\n", [NBal]), format("Quota: floor(~d*1000/(~d+1) + 1) = ~d\n", [NBal, NVac, Q]), format("\nDistribution of first preferences:\n\n", []), write_elected(SCans), write_totals(Stks, ExhStk, SStks, EPars). write_stage(stage(dist_surplus(SCan, SCans), Stks, ExhStk, SStks, EPars)) :- format("\nDistribution of surplus for ~w:\n\n", [SCan]), write_elected(SCans), write_totals(Stks, ExhStk, SStks, EPars). write_stage(stage(exclusion(ECan), Stks, ExhStk, SStks, EPars)) :- format("\nEXCLUDING ~w\n", [ECan]). write_stage(stage(dist_excluded(SCans), Stks, ExhStk, SStks, EPars)) :- ( SCans = [], EPars= _._ -> % no candaidates elected, still more parcels to % distribute -> don't bother writing totals true ; format("Distribution of parcel(s) of excluded candidate:\n", []), write_elected(SCans), write_totals(Stks, ExhStk, SStks, EPars) ). write_stage(stage(elect_all, Stks, ExhStk, SStks, EPars)) :- format("\nElecting remaining candidates.\n\n", []). % write out summary of the stacks etc write_totals(Stks, ExhStk, SStks, EPars) :- ( SStks = [] -> true ; format("\nSuccessful candidates with surpluses pending:\n", []), write_stacks(SStks) ), ( Stks = [] -> true ; format("\nContinuing candidates:\n", []), write_stacks(Stks) ), ExhStk = stack(_, ExhTot, _), printf("\nExhausted ballots: %7d\n", [ExhTot]), val_parcels(EPars, EVal), ( EVal = 0 -> true ; printf("\nExcluded ballots not yet distributed: %7d\n", [EVal]) ), printf("----------------------------------------------\n", []). % find value of list of parcels val_parcels([], 0). val_parcels(parcel(BVal, NBal, _).Pars, SVal) :- val_parcels(Pars, SVal1), SVal is SVal1 + BVal*NBal. % write out list of stacks (first sort them) write_stacks(Stks) :- sort(Stks, Stks1), write_stacks1(Stks1). % as above write_stacks1([]). write_stacks1(stack(Can, Tot, _).Stks) :- printf(" %-28s %7d\n", [Can, Tot]), write_stacks1(Stks). % output each member of Ts using format string S format_all(S, Ts) :- member(T, Ts), format(S, [T]), fail. format_all(_, _). % write list of elected candidates write_elected(SCans) :- format_all("ELECTING ~a\n", SCans). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % code for HTML interface to PR counting software % Given list of Name-Value pairs from form, % output new HTML page html_form(NVs) :- putl("\n"), putl("\n"), putl("Result of election\n"), putl("\n"), putl("\n"), putl("

Result of election

\n"), putl("
\n"),
	( html_read_data(NVs, NVac, Cans, Bals) ->
		true
	;
		writeln('ERROR: Data input/checking failed'),
		writeln(NVs),
		fail
	),
	count(Bals, NVac, Cans, SCans, Stages),
	write_stages(Stages, SCans),
	putl("
\n"), putl("\n"), putl("\n"). % take list of Name-Value pairs from interface to form, % extract data in right format then call counting code html_read_data(NVs, NVac, Cans, Bals) :- member('NVac'-NVacS, NVs), intToString(NVac, NVacS), member('NCan'-NCanS, NVs), intToString(NCan, NCanS), member('Cans'-CansS, NVs), lines(CansS, SCans), % could remove blank lines etc also map_atomToString(Cans, SCans), (length(Cans, NCan) -> % check for consistency true ; writeln('ERROR: Number of candidates inconsistent'), fail ), member('Bals'-BalsS, NVs), lines(BalsS, BalLs), cvt_balls(BalLs, Cans, Bals). % converts atoms to strings (used in reverse to % convert string version of candidates to atoms) :- map_atomToString(As, Ss) when As or Ss. map_atomToString([], []). map_atomToString(Can.Cans, SCan.SCans) :- atomToString(Can, SCan), map_atomToString(Cans, SCans). % convert from list of lines to list of ballots cvt_balls([], _, []) :- writeln('Error: END expected at end of ballots'), fail. cvt_balls(L.Ls, Cans, Bals) :- (if L = "END" then (Ls == [] -> true ; writeln('More data after END in ballots'), fail ), Bals = [] else expand_bal(L, Cans, Bal1), Bals = Bal1.Bals1, cvt_balls(Ls, Cans, Bals1) ). % transform shorthand for ballot to the real thing expand_bal(L, Cs, B) :- add_keys(L, Cs, KCs), sort(KCs, KCs1), check_keys(KCs1), rm_keys(KCs1, B). % for each marked position on ballot paper, % add candidate with that number as key add_keys([], [], []). add_keys(K.Ks, C.Cs, B) :- get_mark(K.Ks, Mark, Ks1), (if Mark = " " then % no mark on ballot add_keys(Ks1, Cs, B) else all_digits(Mark), intToString(Pref, Mark), B = (Pref-C).B1, add_keys(Ks1, Cs, B1) ). % read until next period, return what was read + rest of string % get_mark([], [], []). % shouldn't happen get_mark(C.Cs0, M, Cs) :- (C == 0'. -> M = [], Cs = Cs0 ; M = C.M1, get_mark(Cs0, M1, Cs) ). % check all chars are digits all_digits([]). all_digits(C.Cs) :- 0'0 =< C, C =< 0'9, all_digits(Cs). % check preferences start with 1 and increment by 1 check_keys((K-_).KCs) :- (if K ~= 1 then write(error) else check_keys_1(KCs, 2) ). % as above check_keys_1([], _). check_keys_1((K-_).KCs, N) :- (if K ~= N then write(error) else N1 is N + 1, check_keys_1(KCs, N1) ). % remove keys (should be in lib) rm_keys([], []). rm_keys((_-C).Ks, C.Cs) :- rm_keys(Ks, Cs). % fix (want number of vacancies also?) write_all(_NC, _Cs, Bs) :- % extra ',' (writeln('['), member(B, Bs), write(B), writeln((,)), fail ; writeln(']')), % write(Bs), % should pretty print writeln(.). % convert string with newlines into list of lines % (each without newlines). Tries to be portable! lines([], []). lines(C.Cs, L.Ls) :- line1(C.Cs, Cs1, L), lines(Cs1, Ls). % returns first line + rest of string % Looks for \n or \r\n or \r as line terminators % - possibly should look for other sequences? % Why the **** aren't the different systems compatible? line1([], [], []). line1(C.Cs0, Cs, LCs) :- (C == 0'\n -> LCs = [], Cs = Cs0 ; C == 0'\r -> LCs = [], (Cs0 = 0'\n.Cs1 -> Cs = Cs1 ; Cs = Cs0 ) ; LCs = C.LCs1, line1(Cs0, Cs, LCs1) ). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % generic HTML form - NU-Prolog interface % Outputs the required "Content-type:" line + blank line, % checks that the apropriate environment variables are set % correctly, reads chars from standard input, forms list of % name-value pairs, fixes escape sequences etc and passes list % to html_form/1, which is expected to write a HTML page to stdout. % % The argument to html_form/1 is a list of Name-Value pairs. % The Names are atoms which have *not* had escape sequences % processed. They are the names of the form fields, so you % had better not use any funny characters in the names! The % Values are strings which have had escape sequences processed. % I have no idea how non-ascii characters entered into a form % turn out. html_form_interface :- putl("Content-type: text/html\n\n"), (getenv('REQUEST_METHOD', "POST") -> true ; putl("This script should be referenced with a METHOD of POST.\n"), putl("If you don't understand this, read "), putl("forms overview.\n"), exit(1) ), (getenv('CONTENT_TYPE', "application/x-www-form-urlencoded") -> true ; putl("This script can only be used to decode form results.\n"), exit(1) ), getenv('CONTENT_LENGTH', CLS), intToString(CL, CLS), read_all(CL, Input), % read whole input inp_to_nvs(Input, NEVs), % convert to name-escaped_value pairs expand_esc_plus_nv(NEVs, NVs), html_form(NVs). % read N chars from input % (reading until EOF seems to just hang) % returns list of N+1 chars, including terminating "&" read_all(N, Cs) :- (N == 0 -> Cs = "&" ; get0(C), Cs = C.Cs1, N1 is N - 1, read_all(N1, Cs1) ). % Converts string "name1=val1&name2=val2&" into % list of pairs [name1-"val1", name2="val2"] etc % Funny chars, eg = and & never occur in vals (they % appear as escape sequences) inp_to_nvs(Cs, NVs) :- inp_to_nvs1(NVs, Cs, []). % as above using DCG inp_to_nvs1([]) --> "". inp_to_nvs1(N-V.NVs) --> non_eq(NS), {atomToString(N, NS)}, [0'=], non_amp(V), [0'&], inp_to_nvs1(NVs). % reads string not containing "=" non_eq([]) --> "". non_eq(C.Cs) --> [C], {C ~= 0'=}, non_eq(Cs). % reads string not containing "&" non_amp([]) --> "". non_amp(C.Cs) --> [C], {C ~= 0'&}, non_amp(Cs). % expands escape sequences and converts "+" back into " " % in value strings of name-value pairs % (NOTE its assumed that names don't have any funny chars!) expand_esc_plus_nv([], []). expand_esc_plus_nv(N-EV.NEVs, N-V.NVs) :- expand_esc_plus(EV, V), expand_esc_plus_nv(NEVs, NVs). % expand escape sequences and converts "+" back into " " % in a string expand_esc_plus([], []). expand_esc_plus(C0.Cs0, C.Cs) :- (C0 == 0'+ -> C = 0' , expand_esc_plus(Cs0, Cs) ; C0 == 0'% -> Cs0 = C1.C2.Cs1, expand_esc(C1, C2, C), expand_esc_plus(Cs1, Cs) ; C = C0, expand_esc_plus(Cs0, Cs) ). % expand escape sequence % translated from C code with no comments... % seems to work expand_esc(C1, C2, C) :- (C1 >= 0'A -> Digit1 is ((C1 /\ 16'df) - 0'A) + 10 ; Digit1 is C1 - 0'0 ), (C2 >= 0'A -> Digit2 is ((C2 /\ 16'df) - 0'A) + 10 ; Digit2 is C2 - 0'0 ), C is Digit1 * 16 + Digit2. -----BEGIN PGP SIGNATURE----- Version: 2.6.3i Charset: noconv iQBVAwUBNCDivhcUsayOlEqNAQFYkwH/RD493aNhqOCSr7bJG8UfxGQhXbXAykTS KSieNtJMpsoZr9VFn9Ps0H/2pcxoiXJnbpry0BAw1KYr969VvBl1fA== =Sv69 -----END PGP SIGNATURE-----