The Mathematical Hacker
evanmiller.org
evanmiller.org
Computer science researchers are doing actual mathematics, and they are clearly more in what the article calls "Lisp school" than the "Fortran school". Research in functional programming is mostly mathematics. Lambda calculi (which was originally not developed to be a programming language at all), types, logic, category theory… Most of the tools used in programming languages research are mathematical tools, and they always have been.
The article is great and I mostly agree with its conclusion, but it seems to miss a lot about what is actually going on in computer science. I understand that it mainly talks about programmers and not computer scientists, but it's less and less true that programmers are not interested in what is happening in computer science research. Lisp invented a lot of the stuff that are now in almost every languages (conditionals, garbage collector, first class function, everything is an expression, recursion…) and it took many years to arrive here. But nowadays I see a lot of interests from the programmer community for what is happening in the programming languages research around Haskell, Scala, OCaml, and even stuff like Coq, Isabelle… ! In order to understand even a little what is actually going on with these research project one have to study (even if indirectly) mathematics.
Now that I have written this comment, I'm thinking that may be I have a skewed/distorded vision and that I'm not really talking about the same people as the article does. I don't know.
I'm reaching out to CS researchers interested in language design for my company. Would you like to talk about building languages for saving healthcare? If so, shoot me an email!
So I'm pleased if such research is going on, because back then I went deliberately looking for it and couldn't find it.
I don't understand why schools do that. There is so much to know and learn in computer science course, yet somehow learning j2ee takes precedence above everything else.
Everytime I read this kind of article, I can't prevent myself from thinking it's mostly a UK/US problem.
You can make a case for using Java to teach about data structures, and if your alternative is C++, that case is pretty solid. If your alternative is C or Python, both sides can be argued.
Teaching J2EE at uni isn't CS education, it's poorly-aimed vocational education.
Many packages have successfully used FP as a layer over those calculations, but that doesn't invalidate the original point you're replying to. Calling functions to add numbers is in fact that worst possible paradigm for performing the actual numerics.
Types, logic, and category theory are the sort of things the author thinks that functional programming people concern themselves with, and he is raising the point that these mathematical concepts only help people create better languages and write safer code, not do "useful" things like weather/weapon simulations, solve optimization problems, or image/video processing.
For me code is just a tool for modeling/solving problems in the outside world. It is the outside world that is interesting. I think the emphasis in the article is the right one. If more people focused on applied mathematics rather than category theory then we probably would get more innovation. Eric Evans said something similar in Domain Driven Design "Instead, the technical talent goes to work on elaborate frame-works, trying to solve domain problems with technology. Learning about and modeling the domain is left to others. Complexity in the heart of software has to be tackled head-on. To do otherwise is to risk irrelevance."
One problem though is that I do like lisp and its lineage (smalltalk etc). Had to take fortran years ago. Never really liked it.
Here is my attempt at a summary that captures all the detail:
Programmer math is not only restricted to type theory and formal logic. Applied Math is also a very important aspect. Eric S Raymond is wrong for trying to make it look like the 'Except for X' is negligible. Plus, machine learning, bio, geo and so on are increasing in importance and growing rapidly as fields. Even in the past, applied Math Programs had a massive impact on the economy by enabling engineers with specialized software. Learn Math. It is important for you as a programmer going forward.
---------
I am not sure why he restricts functional programming to recursion with lisp. There is no need to denigrate functional programming, it fits extremely well with these applied math problems and helps a lot with reducing complexity of implementation, in my opinion. They also tend to be at least as fast as Java with OCaml posting incredible single core speeds.
Another point is math algorithms is distinct from mathematical programming. Math helps one calculate and choose faster algorithms or find better bounds. But except for some portions of the haskell compiler there are few uses of direct calculation to derive programs mathematically. In engineering, math allows you to precisely calculate behaviour and properties but in programming you have to debug. The key reason for this divide is that other engineers have lots of components with well defined properties to work with.
This is another reason why functional programming is more mathematical. Although the idea of composition is not inherent to FP, in FP it is the default paradigm. The ideas of combinators with well defined properties, and theorems proven on them, that only go together in a certain way and that you can sit down and have a pretty good idea of how your program would behave theoretically, this idea is what makes FP so close to doing applied math. And Haskellers really shine at that. Haskellers like to talk about monoids and categories but really most of haskell programming is closer to what a reguler engineer does with the category theoriests serving the same function as physicists.
Mathematical depth is the irreducible core of a computer scientist's value. Fundamentally, what computers provide is the mechanization of knowledge. In the same way that robotics came along and mechanized all of the entry-level manufacturing jobs (the root of the current "skills gap" in manufacturing, more so than outsourcing in my opinion), over the coming few decades I expect that computers will mechanize most entry-level knowledge workers' jobs, if they haven't already.
And the wacky thing about comp. sci. is that our entry level positions are in fact basic knowledge-work. As the field matures, the fields that are the bread-and-butter of basic vocational computer science are increasingly swallowed by more sophisticated technical solutions that are more mechanized and productized. Comp. Sci. is an ouroboros, eating its own tail of unskilled positions.
The most obvious example currently is sysadmins: computing infrastructure is being productized and sold under the umbrella of "cloud computing," and its main value proposition is that you can cut your sysadmin budget by a huge margin. Similarly, QA and software testing departments are having their lunch eaten by better testing practices and automated solutions such as CI: the jobs aren't disappearing entirely, they are just being consolidated into a tiny department (maybe even one dev, part time) that can maintain an automated infrastructure. At a more basic level, data entry positions started drying up years ago with the advent of OCR, and now most of the big easy targets are entirely mechanical (ex. the post office/shipping).
In short, the best way to provide enduring value is to provide mathematical insight that can't be mechanized. If you can recognize optimizations and opportunities that take advantage of the unique structure of your domain, you are unlikely to be swallowed by someone with a productized version of your livelihood. If all you can manage is CRUD apps for enterprise, then when someone comes along with a general product that reduces your department from many guys writing software to one guy managing the product, you aren't gonna convince anyone of your value. At that point your only defense is the behemoth of bureaucracy, but the competitive nature of business suggests that it won't be a great defense for long.
If we're going to talk about real world, practical applications, then it might be more relevant to bring up a problem for which there isn't a trivial O(1) solution. A dynamic programming problem, perhaps? It's glossed over with a terse dismissal:
> “Advanced” discussions might consider engineering considerations such as tail-call behavior, or the possibility of memoizing results.
... But this is exactly why a functional programming language might be better than an imperative for certain applied mathematics problems. Note, I'm not saying that it is better, just that it's not such a simple argument. With a different set of examples, this article could have been written in favor of Lisp just as easily. I still think it's a good article overall, just that the point it tries to sneak in about Lisp and functional programming is a little shaky.
A good network programmer should have at least passing knowledge about graph theory (the network is a graph), queueing theory (how else are you going to size your buffers?), and also some statistics (given these numbers, how much bandwidth will be taken by resends? How much data can we send per hour? How many 9s do we get for 'probability that a messages is handled within 10 seconds'?)
Good systems programmers should have some knowledge of all of these for essentially the same reasons. They also will need some knowledge of Petri nets (for deadlock avoidance), formal languages (how else are you going to spec a language or some complex protocol?)
Also, an article on this subject that mentions neither Knuth nor Dijkstra? Weird. Is that because they do not have a blog (yes, Dijkstra does not live anymore, but I doubt he would have a blog if he did)?
Partial differential equations can also be useful there. From Danny Hillis' TEDxCaltech talk about Feynman's work on the Connection Machine, where Feynman was figuring out how many buffers they needed in the routers:
---------------------------
By the end of that summer of 1983, Richard had completed his analysis of the behavior of the router, and much to our surprise and amusement, he presented his answer in the form of a set of partial differential equations. To a physicist this may seem natural, but to a computer designer, treating a set of boolean circuits as a continuous, differentiable system is a bit strange. Feynman's router equations were in terms of variables representing continuous quantities such as "the average number of 1 bits in a message address." I was much more accustomed to seeing analysis in terms of inductive proof and case analysis than taking the derivative of "the number of 1's" with respect to time. Our discrete analysis said we needed seven buffers per chip; Feynman's equations suggested that we only needed five. We decided to play it safe and ignore Feynman.
The decision to ignore Feynman's analysis was made in September, but by next spring we were up against a wall. The chips that we had designed were slightly too big to manufacture and the only way to solve the problem was to cut the number of buffers per chip back to five. Since Feynman's equations claimed we could do this safely, his unconventional methods of analysis started looking better and better to us. We decided to go ahead and make the chips with the smaller number of buffers.
Fortunately, he was right. When we put together the chips the machine worked. The first program run on the machine in April of 1985 was Conway's game of Life.
---------------------------
Source: http://longnow.org/essays/richard-feynman-connection-machine...
"One way to read the history of business in the twentieth century is a series of transformations whereby industries that 'didn't need math' suddenly found themselves critically depending on it." This is a significant understatement. It also summarizes the history of business in the 19th century and even earlier. See, for example: steam power, metallurgy, bridge building, chemical industries, and electricity.
Not all hackers miss Miller's point. One of Zed Shaw's older rants "Programmers Need To Learn Statistics Or I Will Kill Them All" comes to mind[1].
Perhaps I'm missing some intended irony, but Miller's polemics on Lisp and his reverence for Fortran feel overdone & unnecessarily narrow. Coders who buy into Miller's notions can join the "Fortran School" by learning something along the lines of R programming (lots of fun, functional, array-based, and adept at statistics) or J (compression and austere beauty that only a mathematician could love) or any number of other languages that have not shunned math. Of course, calculus, statistics, and linear algebra also required. For the university trained, brush up (or curse your university for not requiring you to learn these subjects). For the autodidacts among us, the likes of Coursera and Sal Khan are indispensable.
Although willful ignorance of math is clearly a problem among certain segments of industry, it's just plainly not true in general and certainly doesn't correlate with lisp.
If there is a divide between fortran and LISP hackers, I'd have to say that Python is going to be the adopted parent/mentor, and it's the only programming language truly situated to bring them together. This is why projects like PyPy get me excited. Other projects like Julia are really interesting as well.
I have to agree with the premise of the article though. There is a divide between mathematical hackers and non-mathematical hackers. I don't think it's anti-intellectualism per se, it's possibly more of a result of the increasing stratification of backgrounds in an industry which has increasingly focused on products, services, and most importantly consumers and "social".
I went to a talk yesterday by an veteran applied mathematician who does research at HP labs. He mentioned something that really resonated with this notion: The days of academic style research, of Bell Labs and the like, has disappeared. This isn't to say that research and math has disappeared from the industries, but as a researcher you have to justify the research by explaining how it can contribute to a bottom line for the company. There's a few companies with looser restrictions on this (Microsoft, Google), but typically this kind of research is best done at companies that are monopolies with high profit margins. In that case, a company like Apple would be best situated to conduct research on the level of the Bell Labs of the past, but it's evident that they don't. The mathematical hacker started falling out of vogue sometime in the 70s. If the mathematical hacker ever becomes vogue again, it won't be because of Apple. It will be because of big data, autonomous cars, medicine and bioinformatics.
Writing programs now, that's not mathematical in nature at all. There are an infinite number of programs that compute the same result. A program is good because it meets a number of criteria, among which efficiency and math soundness are not always the most important. Many of the criteria have to do with how the human mind works and how it intuits.
Why would the Lisp hacker ask that? That makes no sense. There is no reason to combine those two functions.
Isn't this wrong? I don't think pow is computed in constant time.
This usually gives enough accuracy for the purposes of floating point.
However, I'm not sure if "pow" can be usefully implemented this way. I am guessing no, because pow grows faster than any polynomial eventually...
edit: Hmm, pow at least looks linear here: http://www.netlib.org/fdlibm/e_pow.c
Sounds great! What's the factorial of 40? Let's use some python:
>>> int(math.exp(math.lgamma(41)))
815915283247882431423526575245034982027017846784L
Huh, weird. I would've thought the factorial of 40 would be divisible by ten. Let's try it another way:
Prelude> let fac n = foldr1 (*) [1..n]
Prelude> fac 40
815915283247897734345611269596115894272000000000
The author's disdain for the lambda calculus, as if it is somehow not real math (because it doesn't involve numbers in the familiar sense?), is bizarre.
lround(exp(lgamma(...)))
On top of that the article is missing the point that some elements functional programming (map, lambda) are actually making a numerical implementation neater.
It is not an accident that the original authors of R were themselves lispers and admitted having been inspired by lisp when creating R.
I think among others, those links will illustrate the previous point: http://cran.r-project.org/doc/html/interface98-paper/paper.h... http://www.stat.auckland.ac.nz/~ihaka/downloads/Compstat-200...
It also represents potentially really good news, because it means that we are probably at the beginning of a huge wave of wealth creation as we figure out how to apply mathematical knowledge to the massive growing mountains of data generated by everyone and everything everywhere.
Think about the historical impact that statistical-quality-control software has had in manufacturing, or the impact that economic-forecasting-and-optimization software has had in farming, or the impact that 'linear programming' software has had in supply-chain management and logistics; and then extrapolate these past achievements to get a sense of the potential impact that applications of mathematical knowledge could have in an everyone-connected, everything-networked, everything-measured world.
Exciting times.
No, seriously.
We're taught in mainstream programming languages to temper our desire for abstraction with mechanical sympathy; being careful not to build too high a tower of abstraction lest our CPU god grows angry and knocks us down to earth with miserable runspeeds. Even if your algorithm is right, failing to fit in cache or having too many memory fetches can increase your code runtime by multiple orders of magnitude from where an optimal, machine-aware piece of code should be.
And the languages that do try to bring more abstraction to the table are ironically dismissed as "too academic" or "too strange" or "not practical" by most people in the industry.
The only time I had to delve into deep mathematics was implementing CORDIC algorithm for microcontroller powered floating point ops (sin/cos/ln) on a 68HC11 because we couldn't buy an implementation in that had source code so we could verify it. Even then it wasn't all that hard. Took about a week to wrap my head round the maths involved.
I do find that mathematical literature is all theory and no application, even with my engineering background. If we had some applications, people would use it more and take it seriously as well and therefore there would be more mathematical programmers.
I have a mathematics background and I see immediately thousands of not-implemented applications when I read mathematical literature (especially the highly abstract one). Thus applications are there. But getting the abilities to see these applications takes time and dedication. I try to hint lots of colleagues to these connections and applications and get ignored (I could talk to a wall instead - it wouldn't make a difference). The colleagues only want to get their job done somehow and nothing more...
If you look at the very early days of computing, you tended to find three types of degree/backgrounds: Electrical Engineering, Mathematics, and Philosophy. The double E is obvious: building the kit. The other two, the potentially Left Brained or Right Brained approach to programming. All three of them have one thing in common: A structured, _logical_ approach to solving problems.
If there is anything to lament, it is that we still have the tug of war between left and right brain approaches. The reality is that one size, indeed, does not fit all. We should accept that and move on to getting the work appropriately done.
Creativity requires comfort with risk and can therefore be costly, which goes against the contemporary programmer's drive toward efficiency and optimization. Creativity requires bring a fresh perspective to each problem encountered, and can therefore be exhausting, which eschews the programmer's drive toward re-use and generalization. Creativity requires leaning on other disciplines for inspiration, which runs counter to the demands of being a language or technology expert.
With time, the grip of these convictions can be loosened and contextualized, allowing room to explore curiosities and creative impulses, many of which may be mathematical (or psychological, or involve re-framing), that arise naturally during the course of a project.
Let's say you graduated HS and slept through your algebra classes. Now a few years later you're a programmer with pretty much no math skills other than what you've learned in elementary school.
Math seems to teach you one of the most fundamental and useful things about programming. The ability to reduce a problem from something that is complex into something that is not complex.
I've only gotten a taste of some basic algebra after taking some online CS courses and really, coming into it with a background of "embarrassingly poor math skills" I can really say that it has changed my life for the better.
I'm still clueless when it comes to some algebra but I find myself looking at problems and being able to solve them much easier now and this is only after a few weeks of programming related courses that happen to use algebra on some occasions.
The math isn't what made it easier. It's applying the same things to solve math problems to programming.
EDIT: Adding some background on dynamic programming
For dynamic programming, the problem should be breakable in terms of overlapping smaller problems, and the base case should be recognized. If the problems don't overlap, they fall within broader divide and conquer category(mergesort, quicksort etc are famous examples).
fib(n) is defined as fib(n-1) + fib(n-2) (overlapping smaller subproblems) and fib(0) = 1 and fib(1) = 1 (base cases)
fib(n) = fib(n-1) + fib(n-2)
fib(0) = 0
fib(1) = 1
Recurrence relations form the basis of dynamic programming and they can be solved either top down or bottom up.
The top down approach is the traditional recursive solution.
def fib(n):
if n == 0 or n == 1: return n
return fib(n-1) + fib(n-2)
def fib(n):
cache = {0: 0, 1: 1}
def _fib(n):
if cache.has_key(n): return cache[n]
cache[n] = _fib(n-1) + _fib(n-2)
return cache[n]
return _fib(n)
EDIT: Adding table based bottom up fibonacci.
Now once the student understands top down dynamic programming, as in he can find the recurrence relations and base cases, it's time for bottom up. As the name suggests, bottom up starts from the bottom and calculates n compared to top down which starts from n and boils down to base cases.
def fib(n):
vals = {0: 0, 1: 1}
for i in range(2, n+1):
vals[i] = vals[i-1] + vals[i-2]
return vals[n]
Top down is recursive and might trigger the recursion limit. Bottom up doesn't have the recursion problem. Sometimes in case of bottom up, table can be eliminated depending on the overlap. But the important thing is, once the recurrence and base cases are known, it can be implemented quite easily.
In fibonacci's case, nth number depends only on n-1 and n-2 and maintaining the whole table is wasteful. The bottom up approach will be better.
def fib(n):
f0, f1 = 0, 1
for i in range(n-1):
f2 = f0 + f1
f0, f1 = f1, f2
return f2
The article picks one recurrence which has a closed form expression. The dynamic programming problems which I have encountered aren't that easily reduced to closed form expressions.
Also, I don't know about Graham or Raymonds, but Yegge advocates maths for programmers.
http://steve-yegge.blogspot.in/2006/03/math-for-programmers....
(I don't count lgamma as obvious...)
There are a lot more closed forms of recurrence relations in the math than the two we talked about above, and a good deal of us (me included) are ignorant/negligent of them (by negligent I mean lazy :P). However, this sort of knowledge is exactly the kind that, in large enough occurrences, leads to game changers and serious disruption in industries.
It's also worth pointing out that someone who's taught about recursion, dynamic programming, and memoization using the Fibonacci sequence likely knows a lot more about those topics by the end than the person who's told "use lgamma and exp to calculate the nth Fibonacci number" knows about gamma functions. Unless, of course, you think that programmers should all take the necessary mathematics to know how to derive the relevant results themselves---maybe you do---but the author certainly doesn't present a case for that.
It doesn't matter. The purpose of fibonacci is to understand recursion and dynamic programming. I have never ever encountered a practical problem where I need the value of nth fib. How does it matter it has a closed form and it takes less clock cycles when I almost never need it?
> While there are a lot of dynamic programming problems that do not easily reduce to closed form expressions, there are a lot that do.
The practical dynamic programming problems which have closed form and we need the value and not workout the whole series are rare. Fibonacci is a learning tool, so is factorial. The practical dynamic programming problems viz. longest common subsystem, interleaving, alignment, travelling salesman, matrix multiplication etc either don't have a closed form, or the closed form isn't useful.
"How many ways to change 100 using 1, 5, 10, 20, 50" does have a closed form, but more often than not, if I encounter a practical variant, the closed form is useless as the "how many ways" is not interesting, but the actual combinations are.
> Maybe there are better examples for students to learn that of similar difficultly, but lack closed form solutions. The Fibonacci one still seems useful since you might be on a system that doesn't provide the lgamma function.
The existence of closed form is immaterial. Closed form exists for Fibonacci doesn't affect learning recursion and dynamic programming.
Also, Fibonacci's closed form isn't defined in terms of lgamma.
> However, this sort of knowledge is exactly the kind that, in large enough occurrences, leads to game changers and serious disruption in industries.
I don't have to know the closed form beforehand to find one when I need it.
I started programming fairly young, about 12, so the "constructive" mathematical approach was the most natural to me. By my third year at university it had worn off and I was much more comfortable with things like existence proofs and thinking in terms of relations rather than constructions (a very vague description, but it will suffice for now), but programming always felt like it emphasized the constructive part of mathematical thinking. It was like I went to a math class and thought one way, then a C.S. class and emphasized a large subset of that thinking.
We know that math is a universal language that, as far as we know, is capable of describing every phenomenon in the universe. And while Computer Science (if you can even call it a science) has had a storied history with mathematics it's not unusual to me to see maths used as a tool rather than the foundation of study. It's the same in many other fields such as physics, engineering, chemistry and so on -- mathematics is a useful tool and nothing more. In Computer Science mathematics is a useful language for discovering and discussing the properties and consequences of algorithms and their computation.
It stands to reason then that if one increases ones knowledge of mathematics then one will have a larger vocabulary to work with in their area of study. If you're studying physics then the more math you know the more complex phenomenon you will be able to model and discuss. In Computer Science you will be able to find efficient applications and optimizations of various algorithms and model physical and ephemeral phenomenon with more rigour and precision.
However there is a maximum lower bound on the amount of mathematical knowledge required in order to effectively practice programming. That is where I think the meme, "you don't need to know math," comes from in our field. More often than not the primary concern of a software developer is to balance two primary concerns: "does it work as it is expected to?" and "can another human being understand and maintain this?" Having a broader understanding of mathematics will certainly open your horizons but there's only so much you need to know to get by. Most of your "work-a-day" programming won't involve much math at all and is primarily concerned with APIs and implementation issues.
I personally believe that Computer Science certainly needs more rigour and mathematics should be stressed a little harder in our curriculum. However in a "hacker" culture rigour is the least of your concerns. The hacker is a pragmatic creature and heavily leans towards asking the question, "Does it work?" more often than, "is this the right way to do it?" See the "New Jersey" school of development (or "Worse is Better" philosophy). As a field I think we'd benefit from a stronger approach to rigour. We are currently mired in a populist culture that constantly re-invents the wheel every decade or so. It'd be nice if we had a common literature and history from which to draw upon as part of our standard curriculum.
Interesting article... but I don't think the treatment of lispers is quite fair. :p
My CS degree was quite theoretical (completed in 1999) so it wasn't just being taught the language of the day (we did x86 assembly, Modula-2, Prolog, Lisp, C++ and Occam).
The Mathematics degree has definitely been useful for programming; specifically set theory, matrix manipulation and linear algebra, number theory, and graphs/networks/design, but a lot of it is stuff I'm unlikely to use for usual programming areas. Number theory (and implications within assymetric encryption) is where I'll probably look to continue learning (as part of a Masters degree) if I find the time.
Doing programming all day will not make you a mathematician.
If you read the link that's not what it says.
Doing programming all day will not make you a mathematician.
Sad truth. For now!
So a systems programmer would never use a tree, a heap or any not trivial data structure? Since when graph theory is not part of math? I am with the author on this, those statements are fairly simplistic. In my experience, a strong math background is the difference between an A and a B/C programmer.
I think it's also easy to stare oneself blind on low-level stuff. We need people that have higher skills in the domain that the code should solve that can code. Having coders in one camp and then the "product owners" in another camp leads to solutions that doesn't work for either group.
And then you wonder why an average person hates/is scared of math.
I would love it if someone had resources on how mathematics could actually be used as a tool by programmers.
What kind of problems would mathematics as a tool help me solve better/faster/more efficiently than the other tools in my programmer toolbox?
^---So true.
No.
Ha! Made me laugh.
If you're doing simple things over and over, with the objective function being minimal rejection/loss rate, the anti-intellectual/industrial get-your-boss-off-your-back-oriented development works. Complex work is different. You need to invest a lot of additional energy into elegance and quality that most companies won't pay for.
However, what we do is so intensely collaborative if it's done right that we are teachers more than anything else. Not engineers or programmers. Our job doesn't end when we build the thing: we have to teach people how to use it, so that it's not mindless complexity being inflicted upon them (as is true of many enterprise products) but something that actually makes their lives better (most software doesn't, because bosses have a tendency to force people to use bad software and this makes engineers' lives, and thus products, worse). It's sad to me that this is an extreme minority viewpoint, and that almost no software manager on earth will actually pay for things to be this way.
I think that "industrial get-your-boss-off-your-back-oriented development works" and "Complex work" is a false dichotomy.
It's because of these abstractions that we can predict the motions of planets or build computers.
This also explains the "why" of functional programming. Referentially transparent functions are just simpler than methods that are constantly changing. Of course, in the real world, it's neither desirable nor possible to eliminate mutable state: you sequester and manage it.
The opposite of mathematical rigor (defined semantics, reproducible behavior) is the sloppy, ad-hoc, corporate FactoryVisitor stuff that is tolerated under the assumption that programming has nothing to do with math.
Less sarcastically, the mere existence of the builder pattern in Java, which undermines referential transparency to its core, is proof that the design of Java as both a language and community is strongly biased against a functional, referentially transparent, mathematical approach to programming, even if such a style were theoretically possible[1].
[1] eg. com.sun.java.swing.plaf.nimbus.InternalFrameInternalFrameTitlePaneInternalFrameTitlePaneMaximizeButtonWindowNotFocusedState
[2] Scala and Clojure being proof that it is still possible (though only to a lesser extent - tail call elimination and corecursion being an example where it fails completely).
In clojure, loop..recur and trampoline does the job. Tail recursion is not automatic, but still, it's there and quite straight forward to use with the added benefit of recur cribbing if your call isn't a tail call.
You may know this already, but my understanding is that Clojure opts to not automatically eliminate tail calls in order to use Java calling conventions, which I imagine simplifies or eases interop. I'm not defending this decision, as I don't have much of an opinion on it, but to call it a design flaw or a bug seems a bit disingenuous as there is definitely a tradeoff to be made.
Now, while Clojure just not implementing automatic TCO would not be a bug or a design flaw per se -- clisp does fairly well without it, because the developers just didn't bother -- if implementing such an AST transformation in the Clojure compiler is impossible, then the compiler's design is faulty. It's like programming FizzBuzz so that you can't later modify it to add a case for multiples of 7. OK, yeah, TCO without goto is not such a piece of cake, but you get the idea.
And I don't think it's a trade-off in the least. If so, what are Clojure programmers winning now? The glorious overhead of thousands of function calls? Those tasty "stack overflow" back-traces, with thousands of calls to the same function?
Rich Hickey wrote:
"No language that uses the JVM stack and calling convention (e.g. Clojure and Scala) can do TCO since it would require either stack manipulation capabilities not offered in the bytecode spec or direct support in the JVM. The latter is the best hope for functional languages on the JVM, but I'm not sure is a priority for Sun as tail-calls are not idiomatic for JRuby/Jython/ Groovy." [0]
I thought that there are implementations of Scheme and other languages on the JVM that do tail call optimization, but I assumed they utilised some kind of virtual stack. Jörg W Mittag on StackOverflow confirmed this:
"Nah, TCO [on the JVM] is easy. Seph does it, Erjang does it, Kawa and all the other Scheme implementations on the JVM do it. The JVM has Exceptions, which are basically the same as GOTO, which can be used to implement TCO. Or you use trampolines. Or you don't use the JVM call stack at all and just implement your own. The reason why Clojure and Scala only provide limited TCO (basically, only tail recursion is optimized) is because they want to use the JVM call stack for interoperability and performance reasons. As Rich Hickey, Clojure's designer said: Interop, speed, TCO -- Pick two." [1]
James Iry wrote the following on LtU, which explains why even though "Real instruction sets (or C) don't 'support' proper tail recursion either", the fact that the JVM doesn't is an issue for Clojure (and Scala):
"Native instruction sets often let you do whatever you want with the stack. C doesn't in the ANSI standard, but you can do it with a bit of assembly. .NET IL has an explicit instruction for tail calls. The JVM, on the other hand, is very strict about how you use its stack and has no tail call instruction." [2]
During my Googling, I also found this[3], which is pretty interesting!
"CTCO works by applying a first-order one-pass CPS algorithm (via Danvy 2007), then transforming the code to return thunks, and finally creating a custom trampoline to be used when the code is executed. Thanks to the properties of the CPS transformation, CTCO will make all function calls into tail calls, thereby even making non-tail code compiled by CTCO use constant space."
This actually sounds not far from what you suggested! Although it does seem to be a bit more than "just an AST transformation". I haven't read through it, or read the referenced paper [4] it's a bit over my head. You should check it out and report back! I've bookmarked it for now.
Finally, you wrote:
"And I don't think it's a trade-off in the least. If so, what are Clojure programmers winning now? The glorious overhead of thousands of function calls? Those tasty 'stack overflow' back-traces, with thousands of calls to the same function?"
Do you still think it's not a trade-off? Unless that last link I found is a magic bullet that makes TCO fast without interfering with Java interop (or the performance of Java interop) then I really don't think it's fair to say that it's not a design trade-off. Rich Hickey (and Martin Odersky) obviously made a conscious decision about this, and you're welcome to disagree with them, but it's not clear cut.
What Clojure programmers are winning now (by being hosted on the JVM) is a lot, I think. Easy interop is one of the pillars of Clojure that has contributed heavily to it picking up steam. I think the same applies to Scala. I said earlier that I don't have an opinion, and I guess it's only true that I don't have a strong opinion. If I had to pick, I think I'd pick interop.
Sorry for the long comment but I'd already done the research, I figured I might as well share it, although there really already has been a great deal said about this.
[0] https://groups.google.com/forum/?fromgroups=#!msg/clojure/Oi...
[1] http://stackoverflow.com/questions/7261039/haskell-on-jvm
[2] http://lambda-the-ultimate.org/node/3106
[3] https://github.com/cjfrisz/clojure-tco
[4] http://www.brics.dk/RS/07/Abs/BRICS-RS-07-Abs/BRICS-RS-07-Ab...
If you were writing a virtual guestbook for a company which has many factories, you would have an excellent reason for having objects with names like FactoryVisitor.
Philosophers of mathematics spent the 20th century what mathematics is all about and they did not settled on any potential definition.
Ok, I have to disagree with you here. What Godel established is that there's no complete axiom system. Every mathematical formalism will have statements P for which neither P nor ~P can be proven. This was not an unexpected result. What makes Godel's Incompleteness Theorem awesome is that it proved incompleteness, which few people thought possible.
Same with Turing and the Halting Problem. Almost no one actually believed that such a program (that could determine, algorithmically, if a program halted) existed. If one did, it would blow open all of mathematics. Turing proved, in a very elegant way, that it didn't.
What 20th-century mathematicians agree upon is that mathematical statements aren't "true" or "false" in an absolute, platonic sense, but that they are products of the axiom systems that generate them.
Whether the Axiom of Choice or Continuum Hypothesis are "true" is meaningless. These aren't mathematical "controversies" that have people yelling at each other saying that the other is wrong. They're axioms about infinity (specifically, uncountable infinity) that, although they have no physical correlates (you can't actually Banach-Tarski an orange) are logically independent of the "obvious" axioms. What logically independent means is that neither L nor ~L will generate a contradiction, and therefore neither has any absolute high ground.
Most mathematicians use AoC and CH for typical mathematics, but there are alternative mathematical worlds in which they don't hold, and those are interesting in their own right.
AoC is used indirectly in almost every place of pure mathematics, but I researched numerical methods for PDEs and Stochastic PDEs which is not pure mathematics, maybe someone who is much more intelligent than me will say where you will use AoC directly in this area outside of some theorems of Analysis that are used but well, I've never ever touched this same axiom again in my life and if I chose to spend my life as a researcher I doubt I will ever need it again to work and publish, and yet I was able to get a Ph.d in Applied Mathematics. The theorem that I know uses the AoC that I cited once but not exactly used is Banach–Alaoglu theorem.
As sbi put if you go to a department of mathematics that includes mathematicians, statisticians and applied mathematicians chances are that almost no one will know too much of set theory excluding some pure mathematicians, this was true on almost every department that I saw in my entire life. So there are mathematicians whose life are not spent trying to use abstractions everywhere. That was the point.
Programming is not necessarily a job for intellectuals, any more than painting or automotive repair is reserved for intellectuals. Have you heard of the balmer peak? This stuff we call code ain't that hard.
I don't like your complexity argument. If you are a gear in a watch you do not deal with complexity. You are well insulated, dealing with your 1 or 2 immediate neighbors. Most programmers are gears, they are attempting to deal with the complexity inherent in your company is a great way to procrastinate, waste time remaking the build system, and get fired. I am sure we have all see this happen.
On what basis do you make that assertion? "Lots of people program who didn't bother to learn maths" doesn't mean they aren't able to learn maths.
>This stuff we call code ain't that hard.
Then why do we so consistently fuck it up horribly?
This is the crux of it. Coding these days "ain't that hard" because the current generation of programmers sneer at formal methods. They believe providing even semi-rigorous proofs that their code works is not worth their effort.
The result? Testing code with arbitrary input is the best practice; even semi-rigorous proofs are a "luxury". Would your high school geometry teacher accept "well, here's three triangles whose angles sum to 180 degrees. QED."? Then why are we so content as professionals to provide similar "proofs" of correctness?
Unfortunately, there's a strong feedback method here. Formal methods receive little treatment because there is little enthusiasm for their application. There is little enthusiasm for their application because the tools aren't advanced enough. The core problem is still the same though: programmers don't take math seriously.
There is more than one "correct". Cheap fast prototypes can and generally should skimp on "correct" scaling things because that extra work isn't necessary unless the idea takes off, otherwise you're saving a ton of labor skipping things that a final product might need but a failed idea won't.
> You don't blame the business when someone builds a bridge that collapses
Be serious; lives aren't generally on the line for most business apps and that kind of engineering is time consuming and expensive and totally unnecessary most of the time for application developers.
> do it wrong, and doing it right doesn't take significantly longer
I completely disagree.
>Programmers just need to be educated and learn how to write code.
Sounds like you need to spend some time running a business and paying for those programmers; you'll change your mind fast.
Prototypes don't go into production, so it is moot. No, first versions should not skimp on correctness. It saves virtually no time at all. For example, I've done absolutely nothing special to make our web apps scalable, we just use scalable tech to build it in the first place instead of garbage.
>Be serious; lives aren't generally on the line
How is that relevant?
>I completely disagree.
Maybe you should try it sometime then.
>Sounds like you need to spend some time running a business and paying for those programmers
Almost 6 years so far, how much more time do I need to spend before reality will suddenly flip on its head and doing things wrong will suddenly become awesome?
Yes they do.
> No, first versions should not skimp on correctness.
Yes they should.
> It saves virtually no time at all.
It saves plenty of time.
> we just use scalable tech to build it in the first place instead of garbage.
We aren't talking about tech, but technique. There are plenty of times you can do things in a less than optimal fashion that is much quicker to code than the optimal version which isn't worth doing unless the idea gets some traction.
So it seems we just fundamentally disagree.
That's not what prototype means to me. A prototype is a first cut that's enough to try an idea out with real users, but is built by optimizing developer time only, not performance or scalability. If an idea is validated, you can come back and optimize things, add caches, optimize db queries to pull minimal required fields or add paging or all of the dozens of little things you can skip to save time that don't add functionality but do add scalability to either traffic or a full database. This has nothing at all to do with mathematical knowledge.
It's not about correct code vs wrong code, it's about the right code for the situation. Bad ideas don't need scalable code and scalable performant code is not as fast to write as quick and dirty code. Quick and dirty doesn't mean wrong, it means working but not optimal.
Sometimes you write these quick and dirty things to let the business guy try his idea out and if it fails, as it often does, then you've not wasted time or money making something scalable and performant that doesn't need to be.
Production code is code that has had the optimization pass after you've decided an idea is worth the effort.
It is what it means in English.
>Bad ideas don't need scalable code and scalable performant code is not as fast to write as quick and dirty code.
Scalable and performant are two entirely orthogonal concepts. Neither of which are really relevant to the topic, correctness.
Oh, you want to be a jerk; OK, discussion over, grow up.
> Scalable and performant are two entirely orthogonal concepts.
Obviously, that's why they were mentioned separately. Get a clue.
> Neither of which are really relevant to the topic, correctness.
Well aren't you full of yourself, bugger off now.
The next difficulty is defining correct code. It's going to be difficult to find consensus beyond anything basic.
Is that not what you are paid to do to some degree? To use software to model business process etc?
But even if it were scientifically accurate, alcohol doesn't make you dumber (at least not at first) - it makes you less inhibited and slower-thinking, two traits that may actually be desirable in problem-solving.
QED!
This, of course, holds in a setting where multiple people work together to build a sizeable codebase. There are many other settings where adopting this mantra would be counter-productive.
From here http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-7.html , second paragraph. The second part also responds to the original topic.
I just curious to find out, what downfall are you talking about ? Isn't software eating the world and Silicon Valley making billions ?
For the kind of human scalability our industry is currently demanding, there is no other choice but to see this as a inevitable consequence.
At the same time, programming itself, like mathematics, is not a world of numbers or any of this, and is in fact the expression of complexity: the complexity of the sign as written or drafted by the mathematician, itself expressed in a non-denumerable set. Programming itself depends on the conventional expressions and idioms of programmers who write actual code.
As Wittgenstein might say “Mathematics consists of calculations, not of propositions.”
Like so: "Programming consists of executions, not of functions."