Cambridge University Computing and Technology Society
event / 69
Tue 07 Nov 2017, 7:45pm  |  MR3, Centre for Mathematical Sciences, Wilberforce Road, Cambridge
Dr Conor McBride (University of Strathclyde) speaks on
This is our first talk of the year, presented by Dr Conor McBride! The talk title is ‘Newton’s Finger’ and will explore the relationship between Newton and Leibniz derivatives and computer data types, it should be a very interesting talk regardless of background knowledge! As always, we will be heading to the pub after for free drinks, so don’t miss out :) Newton's notion of "divided difference", D(F)(X,Y) = (F(Y) - F(X))/(Y-X) makes perfect sense for container-like data structures, F(-), even in the absence of "subtraction" or "division". We may rather consider solutions to the equation (or type isomorphism) F(Y) + D(F)(X,Y)*X = Y*D(F)(X,Y) + F(X) which witnesses how to travel "left-to-right" through an F(-)-structure, gradually turning Ys into Xs. D(F)(X,Y) represents a snapshot in the process, where there is a finger over a place where a Y has been removed but an X has yet to be inserted, but there are Xs "left of the finger", and Ys "right of the finger". Just as various limits of the divided differnce play a useful role in mathematics, so the same limits have computational meaning. Leibniz's derivative F'(X) = D(F)(X,X) gives the type of "one-hole contexts" for an X in an F(X). Meanwhile, D(F)(0,Y) (i.e., nothing left of the finger) gives a formal notion of "division by Y with remainder F(0)", but also plays a vital role in Brzozowski's differential analysis of regular expressions. Lastly, D(F)(X,1), also known as "Fox's free deriviative", captures F(-) structures under construction, with stubs right of the finger, in place of values not yet computed. In any functional programming language that treats datatype descriptions as first-class notions, we can just do the mathematics and extract the functionality in general, once for all.


If you are reading this, no additional material has been uploaded for this event.

Powered by HERDING CATS v1.0+b6ae1e4 (2018-06-13 15:31:13 +0100 nitrous) ©2011-2013 CUCaTS
"Share" font family by Ralph Oliver du Carrois
Hoodies and stash provided to CUCaTS by Ideasbynet.com.