Translating mathematics into code
matt.might.net
matt.might.net
I'm convinced, from long experience, from long experience, that functional collections are stylistically superior to imperative collections, even in otherwise imperative code.
In fact I'd go so far as to say that the worst mistake van Rossum made in designing Python was not to use functional collections. Then we wouldn't need to discuss how to copy them: http://news.ycombinator.com/item?id=3201033 There also wouldn't be this bug where using an empty list as the default value of an optional parameter would do the wrong thing (the same list object is reused on subsequent calls, when it is no longer empty).
(Yes, I understand, Python does have functional sets, but not AFAICT functional sequences or maps.)
It's great to see that Rich Hickey has designed Clojure around functional collections. I'm sure he'll do more for the cause than my own FSet library for Common Lisp, but I'll plug the latter anyway: http://common-lisp.net/project/fset/
That's not a consequences of not using "functional collections" - lisp has non-functional collections, yet the empty list doesn't have that behavior.
Note the difference between "an empty list" (correct for python) and "the empty list" (correct for lisp). That reflects a design decision that has consequences. Neither is superior in all circumstances.
In some sense, this is an instance of an overloading error. Python's lists aren't lisp's lists and there are many other definitions.
Re functional sequences, there's tuples.
I think the difference here is, and I don't think this is a subject that has been thought about quite enough, is that mathematics typically describe calculation, while code describes a superset of calculation, computation.
When we spend all our time working with the more expansive set, computation, we sometimes forget that calculation is in many ways less expressive and has fewer ways to express a thing. Many of the ideas in the article seem to be about getting over things we take for granted in computation, and understanding how to operate in the more limited framework offered by calculation, and/or understanding that even if things look kind of alike (what's a good word for this concept? a homoscript?) in computation vs. calculation they can be subtly different with a range of pitfalls.
Here are two examples:
1. Consider the set of Turing machines that halt on a certain string. This set is logically sound, but it's impossible, in general, to create a computer program that can decide membership on the set.
2. Non-constructive "there exists" style proofs. For example, take Peano's existence theorem. This helps characterize an important class of ODEs that clearly have solutions but lends no help towards actually constructing solution(s).
Interesting but recent thread on it http://news.ycombinator.com/item?id=3227620
This statement is correct, but probably not for the reason you think it is.
The set of math proofs is isomorphic to the set of programs that terminate [1].
There are useful non-terminating programs (operating systems, for example), but all of the useful CS theory lies in the common subset. Data structures can completely described in math, including mutable ones.
[1] See the Curry-Howard isomorphism.
An aside: I was trying to brush up on Python and looked at Learn Python the Hard Way, and found exercise 25 absolutely appalling. I hope that's not idiomatic Python.