Re:Why functional programming matters (1990) [pdf]
by tel on Thursday May 07, 2015 @01:36PM
(#9506815)
You can take this work much further in an "FP" kind of way by noting that the pi calculus is a good proof system for linear logic. Frank Pfenning has some lectures on this.
Re:Why functional programming matters (1990) [pdf]
by mafribe on Thursday May 07, 2015 @09:17PM
(#9509482)
I don't fully agree with Pfenning here. The pi-calculus is not that good a proof system for linear logic: pi-calculus imposes sequentiality constraints on proofs that impede parallelism. Take for example the term
x!<a> | y!<b> | x?(c).y?(d).P
You have to sequentialise the two possible reductions on x and y.
The culprit is the pi-calculus's input prefix, which
combines two operations: blocking input and scoping of
the bound variables (here c and d). This sequentialisation is not true to the spirit of linear logic proofs (think e.g. proof nets).Conversely, I don't think linear logic is a good typing system for pi-calculus for a variety of reasons: among them that linear logic does not track causality well, and because it doesn't take care of affine (at most once) interactions well.
Re:Why functional programming matters (1990) [pdf]
by tel on Friday May 08, 2015 @09:36AM
(#9511612)
These are good points and I'll have to consider them. I was planning on going back through Pfenning's notes again in a bit and I'll keep a more critical eye this next time. Thanks!
(Also, to be clear and with reference to other threads we've conversed on here, I think of linear logic and pi calculus, even if they aren't well-corresponding, as fantastic, unavoidable examples of non-function-application style programming.)
Re:Why functional programming matters (1990) [pdf]
by discreteevent on Thursday May 07, 2015 @01:50PM
(#9506912)
Thanks very much for that. I'll read them all. (I did a bit of reading around actors before including some Hewitt but didn't pick up on the message passing equivalence. Will read closely. The Milner paper looks very interesting)
I don't remember off the top of who first showed that parallel computation has no 'good' encoding into functional computation (lambda-calculus). I'll try to dig out a reference and post it here if I find it.
But the upshot of all this is that message-passing is more fundamental than functions / function application.
[1] C. Hewitt, H. Baker, Actors and Continuous Functionals.
[2] C. Hewitt, Viewing Control Structures as Patterns of Passing Messages.
[3] R. Milner, Functions as Processes.