Profile

Cover photo
Verified name
Dan Piponi
Worked at Google
Attended King's College London
2,368 followers|3,600,356 views
AboutPostsPhotosYouTube

Stream

Dan Piponi

Shared publicly  - 
 
In many programming languages, including Haskell, you can freely copy values. For example, in Haskell you can write

    let b = a in ...

Haskell is based on the internal language of Cartesian closed categories (CCCs). The feature of these that allows us to copy values is the fact that a CCC has a diagonal morphism

    Δ:A →A×A

You can imagine making the copy more explicit by thinking of the above notation as shorthand for

    let (a,b) = Δ(a) in ...

The shorthand makes clear that in some sense we're reusing the variable a to continue labelling one of the copies. But that doesn't matter here because a has the same value before and after.

If you're writing code for linear algebra it's natural to think in terms of operations in the category of vector spaces. They are equipped with a copy morphism too:

    Δ:V→V⊕V

and so a vector space language should have a let clause to allow this.

But vector spaces also come equipped with a duality operation so any linear map f:A→B gives rise to another f*:B*→A*, usually called the adjoint or transpose of f. So we'd like to have

    Δ*:V*⊕V*→V*

This map is more commonly known as addition.

As I mentioned on G+ recently [2], you can construct adjoints of computer programs by a process that involves writing your code backwards. It'd be nice to have your programming language reflect this. So what operation is dual to "let b = a"? In C it'd be written

    a += b

Because let is shorthand for reusing the variable name for one of the copies, the adjoint version also has a variable reuse. But this time a changes value so the corresponding operation is a mutation.

In CCCs you don't have a dual to Δ so it makes sense that Haskell outlaws these kinds of mutable updates. But in a language (or DSL) for linear algebra, += is as natural a statement as let.

The is a simpler formulation of something I mentioned many years ago. [3]

This also serves as a reply to Twan van Laarhoven [4]. Curiously, since then Laarhoven has played an important role in making a serviceable form of += available in Haskell [5].

[1] https://golem.ph.utexas.edu/category/2006/08/cartesian_closed_categories_an_1.html
[2] https://plus.google.com/+DanPiponi/posts/9uWDCeLPLpz
[3] http://blog.sigfpe.com/2007/01/monads-hidden-behind-every-zipper.html
[4] http://blog.sigfpe.com/2008/09/two-papers-and-presentation.html
[5] http://www.twanvl.nl/files/lenses-talk-2011-05-17.pdf
25
7
Rei Ayanami (年轻的大天才)'s profile photoFrank Yang's profile photoLin HU's profile photoIlya Yanok's profile photo

Dan Piponi

Shared publicly  - 
 
I enjoyed Jessica Augustsson's previous anthology so I bought this right away. Includes a story by +Lennart Augustsson so how could I refuse?
 
I'm happy and proud to announce my second anthology, Encounters, with a whole slew of new stories by talented authors. You can find it as a Kindle book or paperback from Amazon around the world! Please like and share! smile emoticon
http://www.amazon.co.uk/dp/B00ZJD1O26
View original post
5
1
JessEdit's profile photoLennart Augustsson's profile photo
2 comments
 
(Also, if you could perhaps consider doing a review, I'd be eternally grateful! No worries if not. Just thought I'd ask. :)
Add a comment...

Dan Piponi

Shared publicly  - 
 
With Satnam Singh, Simon Marlow and Phil Wadler on a beach in Kefalonia eating the best Greek food ever.
36
1
Lennart Kolmodin's profile photoRobert Harper's profile photoSatnam Singh's profile photo
2 comments
 
I think Wadler just travels for a living!
Add a comment...

Dan Piponi

Shared publicly  - 
 
I've been playing a little bit with the programming language Julia recently. I'm very conflicted about this language. For small numerical experiments this is my #1 language of choice now. But it contains many things I am not a fan of.

Matlab is a kind of de facto standard in the scientific world for numerical computing. From a language theoretical perspective it is (IMO) a very poorly thought out language with frequently poor performance and a high degree of non-orthogonality. But as long as you stick with vectorised operations Matlab can perform tolerably well. And not every aspect of the language is poorly designed. It has a very compact notation for dealing with arrays and their slices. And it's easy to call C code when needed.

Julia is an attempt to fix many of the problems with Matlab. This means it does slavishly copy many features of Matlab. But it uses LLVM on the back end to generate high performance code. What's appealing is that you can use a mixture of imperative style loops with array updates alongside vector operations like those in Matlab and know you'll likely get good performance. This makes it very appealing to me.

Most programming languages I have learnt have given me a new perspective on the world inside a computer. This includes languages from Forth, and assembly language to Python and Haskell. Just learning them expands your mind in some way. Julia is the first non-mind-expanding language I've learnt. If I hadn't used APL, numpy and Matlab before I might have found its vectorised operations revolutionary. But I had, and Julia doesn't seem to offer anything new. So in that respect it's a bit boring.

But it's not completely without some interesting aspects. Like Lisp it's homoiconic. That's slightly surprising for a language that looks superficially a lot like Fortran.

And although it's described as dynamically typed, in actuality it makes clear that the distinction between static and dynamic typing isn't so straightforward. Just like with a dynamically typed language like Python, just about every function you write is polymorphic in the sense that it's not an error to pass in arguments of just about any type. But Julia's one truly interesting feature is that once it knows the type of the arguments it attempts to monomorphise the function (ie. specialise it to the required types) and compile it just-in-time. This gives the best of both the dynamic and static worlds. Except sometimes it gives the worst of both worlds too.

For example some type related errors get uncovered during compilation before the code is run. This is cool for a dynamic language. But sometimes you still get the disadvantage of having to wait for code to run before a type error is discovered as well as the disadvantage of having to wait for your code to compile every time. Worst of both worlds!

Because it's a JIT compiler Julia can be painfully slow to import libraries. This is why I like it only for small tasks. I hope this is eventually fixed as I don't think it's an inherent problem with the language.

Julia has many annoying niggles. For example arrays start at 1. And within matrices spaces are used as a separator. So, for example, let's say f is a function mapping ints to ints. "f(x)" is a valid expression. Outside of an array expression, "f (x)" is a perfectly good way to write the same thing. You can write a two element matrix of ints as "[1 2]" where there is a space separator between 1 and 2. But "[f (2)]" is not the matrix of integers containing f(2). It is in fact a two element inhomogeneous matrix whose first element is a function and whose second element is an integer. Yikes!

But for doing things like testing the divide and concur circle packing I mentioned recently, it's hard to beat how fast I got that working in Julia.

And one more thing: functions are first class objects in Julia and forming closures is fairly easy.

http://en.wikipedia.org/wiki/Julia_%28programming_language%29
37
7
Bagus Tris Atmaja's profile photoLuca Luve's profile photoConor Lawless's profile photoVít Tuček's profile photo
13 comments
 
Hiiiiii
Add a comment...

Dan Piponi

Shared publicly  - 
 
I recently mentioned the alternating projection algorithm for finding a point in the intersection of two convex spaces. Today I thought I'd mention some variations.

(1) Sometimes you want to work with non-convex spaces. There's an easy method you can apply: just use the same method blithely ignoring the non-convexity. That's a method that's long been used by people working in X-ray crystallography and other fields where you want to recover a phase of a complex-valued field but you can only measure the absolute value: http://en.wikipedia.org/wiki/Phase_retrieval There's also a more complex variation called the difference map: http://en.wikipedia.org/wiki/Phase_retrieval

(2) Sometimes you want to find a point in the intersection of N convex spaces. You could try cycling through N projections, but by time you've reached the Nth your iterate will likely have "forgotten" much of what was learnt on the first iteration. Instead there's a trick: move to a "superspace" that's the N-fold cartesian (and hence tensor) product of the original space. Now define two "superprojections": (a) each of the N projections is simultaneously applied to one of the copies of the original problem in the "superspace", and (b) each of the N copies is made equal to the average of all N copies. The first "superprojection" is called 'divide' and the second is called 'concur'. Now use your favourite variation on alternating projections.

(3) Now combine (2) and the difference map in (1) to get a general purpose algorithm to find intersections between N non-convex sets in a Euclidean space. This is the...wait for it..."Divide and Concur" algorithm as described here: http://arxiv.org/pdf/0801.0222v1.pdf

Astonishingly, the approach described in (3) can be used to solve many problems (possibly approximately) including Sudoku, 3SAT and packing problems, with a minimal amount of code. In some cases it performs as well as other state of the art methods.

The picture is the result of me implementing a circle packer using divide and concur in just a few lines of code.

Looks like a good tool to add to the utility belt.
17
7
Mirko Bulaja's profile photoWalter Di Carlo's profile photoAlok Tiwari's profile photoDaniel Canelhas's profile photo
6 comments
 
Thanks!
Add a comment...

Dan Piponi

Shared publicly  - 
 
Hauntology is a peculiarly British artistic movement, largely in the medium of popular music, that draws on a mythology constructed from public information films, village horror movies and children's TV, all from Britain of the 60s, 70s and 80s. Musically there are influences ranging from the BBC Radiophonic Workshop and Tangerine Dream, to folk songs and jingles, employing a mixture of digital and analogue production methods. The aesthetic extends to record sleeves, web sites and various kinds of literature published by the main purveyor of hauntological recordings, Ghost Box.

Anyway, I like the stuff, so maybe you will too. Some links to get you started:
https://www.youtube.com/results?search_query=belbury+poly
https://www.youtube.com/results?search_query=advisory+circle

I think I'll add a link to Scarfolk too: http://scarfolk.blogspot.com
Toward the end of last year, I was clearing out some old boxes under the stairs when I happened across a huge pile of old record label mail outs and flyers. As I sifted through the sheaves of gloss...
7
3
Stefan Scherer's profile photoKatherine Prevost's profile photo
Add a comment...
In his circles
185 people
Have him in circles
2,368 people
Edward Kmett's profile photo
Carmilo Vannucci's profile photo
Damián Silvani's profile photo
Edvin Gjuti's profile photo
Benjamin Jones's profile photo
Daniel Piker's profile photo
Syed Hamza's profile photo
Sandy Hilson's profile photo
Anatoly Karp's profile photo

Dan Piponi

Shared publicly  - 
 
One of the pillars of quantum mechanics is the photoelectric effect. Light below a certain frequency is unable to dislodge electrons from a material even when provided by a high power beam. The argument in almost every textbook, due to Einstein, says that the energy must be arriving in discrete packets, photons, and that you need a single packet on its own to have enough energy to kick out an electron.

If it's an advanced enough textbook then there will be a later chapter on time-dependent perturbation theory where it is shown how to calculate the rate at which electrons are kicked from one energy level to another as a function of the incoming electromagnetic wave. In almost every single textbook the argument treats the incoming wave as a classical field, demonstrating how you can in fact explain the photoelectric effect without recourse to photons.

Disappointingly these books don't simply self-annihilate in a cloud of contradiction.

(Of course the photoelectric effect is still good  evidence for QM. Just not in the way textbooks claim.)
90
31
San T's profile photoDanuta Sinclair's profile photoJaythan Donell's profile photoHernan Murua's profile photo
9 comments
 
hmm interesting.  Your thoughts on mutual resonance increasing vibration... 
Add a comment...

Dan Piponi

Shared publicly  - 
 
A few years ago I read a pop science article about "rogue planets", planets floating free of any star that might retain enough heat to support a habitat suitable for life. I thought it'd make a great scenario for a science fiction story so I was pleased when Chris Beckett's Eden stories (Dark Eden, then Mother of Eden) were published.

The main story starts with a growing community several generations after a small number of humans are stranded on a rogue planet heated by geothermal activity. They are equipped with the most basic technology, and memories about a distant home called Earth. There's some interesting world-building, though Beckett's main focus is on using the scenario as a fictional testbed for exploring various kinds of origin myth. Similarly to Delany's Tales of Neverÿon [1] we get characters explianing to us the origin of everything from money and patriarchy to social class and prohibitions against homosexuality. In fact, the books remind me a lot of a work of non-fiction, Graeber's analysis of debt [2].

The planet's ecosystem is interesting with plant-life providing a transport mechanism that pumps heat from the lower depths of the planet to the surface. There's also a novel (to me) variation on the idea of a deity, the notion of a Watcher who looks out from the same eyes as each individual and who can be perceived only fleetingly in moments of stillness. Humans have spent many thousands of years exploring the space of spiritual entities so it's surprising to find an author managing to find space for something new.

Although the world-building and analysis are interesting, the plot and characters are a little weak, feeling more like holes in a template that needed to be filled. Nonetheless I enjoyed both books a lot and look forward to the next book in the inevitable series.

BTW I think these would be great books for "young adults" to provoke classroom discussion about politics and power. An alternative to The Lord of the Flies.

[1] https://plus.google.com/+DanPiponi/posts/YDoTxpHgeEZ
[2] http://en.wikipedia.org/wiki/Debt:_The_First_5000_Years
12
1
Devan Stormont's profile photo
Add a comment...

Dan Piponi

Shared publicly  - 
 
 
Solar-powered Loon balloons provide Internet fast enough to stream YouTube videos #io15 
83 comments on original post
13
2
Greg Steuck's profile photoAndrei Lopatenko's profile photoWilliam Rutiser's profile photo
 
How many users worth of YouTube streaming per balloon?
Add a comment...

Dan Piponi

Shared publicly  - 
 
Years back I had a paper published showing how any algorithm to compute a linear function can be run "backwards" to compute the transpose operation in the same amount of time: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.159.4990

It seemed obvious but I hadn't seen it presented as a general purpose algorithm transformation. Today I came across a clear statement. It's known as Tellegen's Principle and it turns out to be quite old. Here's a presentation on the subject: http://www4.ncsu.edu/~kaltofen/bibliography/05/montagnac.pdf A web search will turn up lots of applications. For example: http://specfun.inria.fr/bostan/publications/exposeJNCF.pdf

There's a twist on this I haven't seen mentioned anywhere on the web. You don't have to do this in rings. It works in semirings too. In particular it works in the max-plus semiring (http://en.wikipedia.org/wiki/Max-plus_algebra) which is the natural home for many well-known algorithms.
31
9
Andres Rodriguez's profile photoDmitry Shintyakov's profile photoVít Tuček's profile photoTracy Morehead-Tobiasz's profile photo
2 comments
 
Yes. As far as I can see Tellegen showed x.Ay=0 if transpose(A)x=0. Trivial except it's not quite so obvious in original context. I think he said nothing about algorithms. But that's the name that's stuck.
Add a comment...

Dan Piponi

Shared publicly  - 
 
People keep comparing the number of votes cast with the number of seats won in Parliament and using this to illustrate a problem with the first-past-the-post system in the UK. I suspect this isn't the best comparison.

The number of votes cast throughout the UK is not a simple representation of the degree of support for each party. Assuming rationality, each voter voted in a way that maximised their gain on the assumption that they were voting in a first-past-the-post system. Arguing that the seat allocation would have been different with a different system is somewhat misguided because people voting under a different system would have cast different votes. In other words, I suspect these numbers are very heavily influenced by the observer effect.

I don't know how rationally people vote. (I personally think it's rational not to vote given the tiny expected gain.) Many people vote strategically but I don't know what proportion do. Some people deliberately vote for a larger party than the one they'd like to see in power believing their vote is more likely to have an effect that way. Some people vote for a smaller party believing it can send a message without risk of that party coming into power. I'm pretty sure this isn't exaggerating the sophistication of voters. I'm pretty sure real voters do reason this way.

If I had to hazard a guess I'd propose that in a more proportional system the smaller parties would have received a significantly larger share of the vote, because voters would feel they weren't wasting votes. This means that looking at seats won in a first-past-the-post election is an even worse estimator of voter preferences that it seems.

BTW People often express surprise at election results compared to earlier polls. I suspect that this is because people aren't really motivated to reveal their true preferences or votes in a poll. Instead, a poll might be used strategically as a safe way to send a message.
17
Dan Piponi's profile photoNeil Mitchell's profile photoDavid “goo.gl/LuFkzX” Tweed's profile photoKenny Laidlaw's profile photo
13 comments
 
Scotland has a Proportional Representation style voting system for the Scottish Government. Despite this apparently making it virtually impossible to get a majority government, the SNP currently have a majority government at Holyrood, just. 

http://www.scottish.parliament.uk/visitandlearn/Education/16285.aspx

There is an election next year, 2016, and their majority could increase if they get a similar result to the UK election.
Add a comment...

Dan Piponi

Shared publicly  - 
 
There are lots of ingenious algorithms in the world, but one of my favorites is stupidly simple.

If C is a convex set then the projection of a point p onto C is, by definition, the closest point in C to p. If C and D are convex sets, then here's a way to find a point in a non-empty C∩D: pick some point p. Project it onto C, then D, then C and keep iterating. In a finite dimensional space the sequence converges to a point in the intersection. If C and D are affine then you get convergence in a finite number of steps to the projection of the starting point onto C∩D.

I wrote part of ILM's GPU based fluid solver Plume including the part that handles interactions with solid objects. You can see it at work in the video.

In the approach to computational fluid dynamics we used there's a step where you use the fluid velocity to move the fluid around, the advection step. At any time the fluid needs to satisfy two conditions: (1) incompressibility and (2) matching the velocity of the solid objects at their boundaries. After advection these conditions are no longer satisfied. So you project back onto the space of flows that satisfy both conditions. Each condition corresponds to an affine subspace.

There are nice algorithms to project back onto the space of incompressible flows when you have trivial boundary conditions. For example you can use multigrid or FFT based methods. There's an easy algorithm to make velocities match along the boundaries: set the velocities along the boundaries. Many years ago I spent some time puzzling over how to solve both of these problems simultaneously and failed to spot the stupidly simple solution we eventually borrowed from [1]: just alternate these two methods.

The surprise is how quickly it works. The convex sets it works with live in something like a hundred million dimensional space. But convergence was often good enough, to the eye, after around five iterations.

This alternating projection method is just the tip of an iceberg of widely applicable alternating projection algorithms. You can read more about them in [2] and generalise even further using [3].

[1] http://jcohen.name/papers/Molemaker_Low_2008.pdf
[2] http://web.stanford.edu/class/ee392o/alt_proj.pdf
[3] https://web.stanford.edu/~boyd/papers/pdf/prox_algs.pdf
39
10
garfield cat's profile photoEd S's profile photoNilay Engineer's profile photoAndrei Lopatenko's profile photo
4 comments
Ed S
 
Great post, +Dan Piponi - reshared to Computer Science, Seriously
https://plus.google.com/u/0/communities/111381551813675174408
Add a comment...
People
In his circles
185 people
Have him in circles
2,368 people
Edward Kmett's profile photo
Carmilo Vannucci's profile photo
Damián Silvani's profile photo
Edvin Gjuti's profile photo
Benjamin Jones's profile photo
Daniel Piker's profile photo
Syed Hamza's profile photo
Sandy Hilson's profile photo
Anatoly Karp's profile photo
Work
Employment
  • Google
Basic Information
Gender
Male
Story
Tagline
Homo Sapiens, Hominini, Hominidae, Primates, Mammalia, Chordata, Animalia
Introduction
Blog: A Neighborhood of Infinity
Code: Github
Twitter: sigfpe
Home page: www.sigfpe.com
Bragging rights
I have two Academy Awards.
Education
  • King's College London
    Mathematics
  • Trinity College, Cambridge
    Mathematics
Links
YouTube
Other profiles
Contributor to