"how did it all begin?"
Payroll was the very first program (well, the first business program) that Chris Hicks wrote, back in 1979 on a Commodore PET with tape drive (Incidentally, Chris sold this PET on eBay in 2006 for £50, still in working order.)
In the past 25 years the Payroll has been rewritten and modified and then rewritten again, usually several times a year. Various programmers have been involved in this work over the years, and I am sure they all feel enriched by the experience.........
As computers have got faster and more powerful, the Government has made the PAYE system bigger and more complicated, to slow things down again. One of the toughest programming jobs Chris has done was the utility to connect to the Government website and send Payroll End Of Year returns electronically. This took over 3 months solid work and involved learning XML, HTML, SOAP, etc - some very thick books were purchased.
2008 saw the launch of the ABC6 version of the Payroll -- a windows program. This took a lot of work but was relatively easy to do.