Discussion. Which is more efficient on a parallel computer? Are they the same algorithm? What is a semantic-preserving rewrite?

Returning to the Engineer's code for triangle numbers, and comparing it with the Computer Scientist's code, are these the same algorithms?

This was the Computer Scientists code:

  let rec sum_m n = if n=1 then 1 else n + sum_m(n-1);;

Suppose we rewrite it such that it takes an auxiliary argument, c, like this:

  let rec sum_mc c n = if n=1 then 1+c else sum_mc (n+c) (n-1);;

This rewrite of the code can be automated (2nd-year Compiler Construction course continuation passing materials) and, moreover, a typical ML compiler will convert this program into the Engineer's form for internal execution (no stack will be needed). Hence, if all of the transformations required to convert one to the other are mechanised, can we consider the two programs to implement the same algorithm?

Of course the Mathematician used maths to obtain his formula. Whether he used an automated program to do his maths is a question for religion and philosophy --- was he predestined to do that bit of maths?

4: Records and Objects

record person_record;
  name : char [];
  year_of_birth:  int;
  month_of_birth: int;
  day_of_birth:   int;
  mothers_age_at_birth: int;
end

Object:

object person_object;
  name : char [];
  year_of_birth:  int;
  month_of_birth: int;
  day_of_birth:   int;
  mothers_age_at_birth: int;


  bool is_ripe()  { return current_year - year_of_birth > mothers_age_at_birth; }
end

5: Logic Programming and Databases

a) In mathematics, what does 'finding the root(s) of an equation' mean? Give a formal definition if you can (i.e. use a clear sentence).

With logic programming we do not write the program ourselves. We write a declarative formula that we want the system to satisfy.

The most famous logic programming language is PROLOG. But also SQL, structured query language, used for realtional databases, is a good example.

Do you have a database program installed on your machine? On my machine the command 'sqlite3' is installed so I will use that.

create table parts(part_no, part_name, supplier, cost INTEGER);
insert into parts values('101',  "front-fork", "ACME Ltd", 20);
insert into parts values('102',  "crank-arm", "ACME Ltd", 10);
insert into parts values('202',  "chain", "Manchester Bike Parts Ltd", 3);
insert into parts values('103',  "pedal", "ACME Ltd", 5);
insert into parts values('103',  "wheel", "ACME Ltd", 15);
insert into parts values('103',  "bell", "Birmingham Steel Solutions", 2);
insert into parts values('1103', "large frame", "Birmingham Steel Solutions", 41);
insert into parts values('1104', "small frame", "Birmingham Steel Solutions", 31);
insert into parts values('403',  "saddle", "Bognor Leather Goods Ltd", 4);
insert into parts values('203',  "saddlebag", "Bognor Leather Goods Ltd", 5);

# Here is the data for just one product, but typically there will be a number of products based on the same catalogue of parts.

create table product(product_name,   part_instance_name, bike_part_name);
insert into product values("Slicer", "front wheel",        "wheel");
insert into product values("Slicer", "back wheel",         "wheel");
insert into product values("Slicer", "frame",              "large frame");
insert into product values("Slicer", "left pedal",         "pedal");
insert into product values("Slicer", "right pedal",        "pedal");
insert into product values("Slicer", "left crank arm",     "crank-arm");
insert into product values("Slicer", "right crank arm",    "crank-arm");
insert into product values("Slicer", "fork",               "front-fork");

We'll do a demo in this session. If you are unfamiliar with databases, everything will be properly explained in the first term of the Tripos.
b) What is the SQL query to get the cost of goods for a Slicer bike?
c) What is a relational database?
d) What is a key and what is the key for the parts database?
Try running each of these queries in turn and see if you can understand the output.

1    select * from product, parts;
2    select * from product, parts where bike_part_name = part_name;    
3    select cost from product, parts where bike_part_name = part_name;
4    select SUM(cost) from product, parts where bike_part_name = part_name;
5    select SUM(cost) from product, parts where bike_part_name = part_name && cost < 33;										    

Some harder or more philosophical questions:
e) Is the data normalised? This means could the tables be reorganised so that the data stored in every table is 'functionally dependent' on the key of each table.
f) Suppose we want to store all of the components involved with pedals just once so they can be conveniently used over multiple products? Can we reorganised the tables to help with that?
g) How could we be sure that every product has a chain?
h)Is the relational style ideal for lists of components?

Prolog Example

Prolog is another logic programming language. Here is a fragment where we define relations between atoms and then a rule for inferring further relationships.

  father(Charles, Harry);
  father(Charles, William);
  father(Philip, Charles);

  grandfather(X, Z) :- father(X, Y), father(Y, Z);

  

As well as simple atoms, Prolog allows you to define relationships between 'algebraic structures' such as lists and trees, so for instance, you can define a list of N elements to be the concatenation of any two appropriate sub-lists that when appended become the initial list:

    append( [], X, X).                                   
    append( [X | Y], Z, [X | W]) :- append( Y, Z, W).    

    This defines a relationship between the three arguments, let's say A, B and C.
    The first line says, " C is the result of appending A and B if A and C are non-empty lists, they both have the same head (i.e. first element), 
    and the tail of C is the result of appending the tail of A with the same 2nd argument, B".
(From   https://stackoverflow.com/questions/11539203/how-do-i-append-lists-in-prolog/11551001)

For reasoning about stable chemical formulae, you can use facts like 'divalent(Oxygen)' and 'monovalent(Hydrogen)' along with suitable valency rules to allow the molecule H2O but not HO.

Boolean Satisfiability (SAT)

Many logic programs can be converted to a Boolean Satisfiability problem (SAT). SAT solver tools are then able to find solutions of hundreds of bits, despite that a brute-force search would require more than a universe lifetime on the fastest possible computer.

The satisfiability problem is: given a Boolean expression over some number of variables, find a setting for those variables that makes the expression true.

For simple problems, such as ABC + BE~A, two obvious solutions are "A=1, B=1, C=1" and "A=0, B=1, E=1", but for tens or hundreds of variables, the problem becomes much harder. (Indeed it is one of the problems called exponentially hard in Complexity Theory). But given a suggested solution, that can be rapidly checked, so this is an example of a problem where the search can usefully be run on an unreliable computer.

There may be a huge role for unreliable computers in the future. A computer run on a very low supply voltage will be unreliable yet not use much electricity. Hence it might be beneficial. Likewise, a computer made of components a few atoms across can suffer from a lot of fabrication mistakes and might fall apart (electromigration) fairly rapidly. But owing to its small size, it too will use very little electricity and hence still play a useful part.

Logic programming example from cryptography: We have the encrypted message O0 that encodes x and a sufficient number of known input/output (plain/cyphertext) pairs under a given key. The satisfiability problem is then find x such that I1 ~ O1 && I2 ~ O2 && ... && x ~ O0.

Methods of making stable chemicals can also be discovered using logic programming. Knowing what a new chemical might be useful for is another matter. But drugs companies can use logic programming to discover a cheap process for synthesising new chemicals and then medical experiments can be run to see if the resulting compounds are useful for anything. For instance, the logic program might generate a list of all stable chemicals that can be cheaply generated from the available source compounds and with the available processing equipment. Or it might find a (new) way (recipe) for synthesising a given target compound of interest, such as methotrexate. The possibilities are endless.

The final word?

Here's a paper.

'When are two algorithms the same?' by ANDREAS BLASS, NACHUM DERSHOWITZ, AND YURI GUREVICH. Abstract.People usually regard algorithms as more abstract than the programs that implement them. The natural way to for- malize this idea is that algorithms are equivalence classes of pro- grams with respect to a suitable equivalence relation. We argue that no such equivalence relation exists. PDF.

Does it agree with my notion that two algorithms are the same if there exists a holy set of automated rewrites that can make the transform there are back? Afterall, how can one rewrite procedure produce two outputs? This would perhaps imply that all versions of an algorithm exist in a ring and the procedure always set shunts us to the next one? Perhaps a reduction to normal form approach could work better: any version of an algorithm is equivalent if the normal form transformations are textually equivalent? Can we prove that a program cannot have a normal form?

Adverts:

August 2021: Read my book Modern SoC Design on Arm Free PDF Download

August 2021: Stream my single Let Me Love You Anneli UK: YouTube     Anneli UK:Apple Music.