Teaching FP to freshmen


This semester Dan Licata and I are co-teaching a new course on functional programming for first-year prospective CS majors.  This course is part of the new introductory CS curriculum at CMU, which includes a new course on imperative programming created by Frank Pfenning, and a planned new course on data structures and algorithms, which will be introduced by Guy Blelloch this fall.

The functional and imperative programming classes are independent of one another, and both are required for the new data structures class.  Both courses share an emphasis on verification techniques (principally, state invariants for imperative programming, and structural induction for functional programming).  The new data structures course emphasizes parallel algorithms as the general case, and places equal emphasis on persistent, as well as ephemeral, data structures.  This is achieved by using an expressive functional language (Standard ML) that includes both evaluation- and mutation-based computations, and that supports modularity and data abstraction.

Object-oriented programming is eliminated from the introductory curriculum, because it is both anti-modular and anti-parallel by its very nature, and hence unsuitable for our purposes.  A proposed new course on object-oriented design methodology will be offered at the sophomore level for those students who wish to study this topic.

Update: The revision of the undergraduate curriculum to which I allude here is described in the report “Introductory Computer Science Education at Carnegie Mellon: A Dean’s Perspective” by Randal E. Bryant, Klaus Sutner, and Mark J. Stehlik.  This report summarizes the recommendations of an ad hoc committee of faculty reporting to the faculty and dean of the School of Computer Science.

Update: Word-smithing.

About these ads

62 Responses to Teaching FP to freshmen

  1. […] 巨星一般都不说话,它们只是默默的释放着自己的能量。以至于人们看着夜空,以为它们只是被卡在深蓝色琥珀中的萤火虫。而这个世界上充满了太多业余级别的程序语言设计者。他们每一个都卖力的推广自己的语言,煽动群众,然后被他们崇拜为神。由于没有系统的学习过程序语言理论,他们经常做出糊涂的设计,重复前人犯过的错误。但是普通的程序员都不知道真正的程序语言专家是什么,所以这些人可以利用自己懂得的那点东西来糊弄他们,以至于真正的专家说话都没有人信。 我经常发现自己没法跟人讨论关于程序语言的设计,就是这个原因。比如当我提到 Python 的缺点使得它不适合作为入门语言,就会有人拿 Linus Torvalds,Guido van Rossum 甚至 Eric Raymond 的话来“镇压”。说这些高人都喜欢 Python,甚至把 Python 作为他子女的第一门程序语言。对于这种盲从“权威”,只相信名气的人,理性的探讨是没有用的,因为真正的科学家们的名气,显然不如他们心目中的偶像们名气大。因为他们从未见过真正的程序语言专家,所以我没法告诉他们,其实他们心目中的某些“偶像”,不过是半壶水响叮当的传教士。而真正卓越的程序语言专家和研究者,他们其实一个也不认识。 举个例子,有谁认识 C.A.R. Hoare 和 Robin Milner?几乎每个程序员都知道 Donald Knuth 和 Dennis Ritchie,却很少有人知道 Hoare 和 Milner 的名字。而其实 Hoare 和 Milner 对于程序语言本质的理解,比起 Knuth 和 Ritchie 还要深入不知道多少,以至于这后两者基本不算是程序语言专家。然而由于 Knuth 和 Ritchie 经常发表言论,再加上崇拜者们对他们的宣传,他们对于广大程序员的种种误导,真是让人解不开的结。 程序语言专家们有一个特点,他们喜欢让编程变得更加简单,更加优美,更加安全,表达力更强,同时却不损失效率。而很多知名的计算机科学家其实并不真的明白什么是“简单”。比如 Dennis Ritchie,他说:“Unix is simple. It just takes a genius to understand its simplicity.”可是你如果学过程序语言的理论,就会发现 Unix 的设计其实是非常繁琐的。那为什么人们都“同意”Unix 是简单的呢?因为他们都想让别人觉得自己是 genius!请比较一下 Ritchie 的话跟这句《皇帝的新装》里的织布工的话吧:“The clothes made of this material are invisible to any man who is unfit for his office or unpardonably stupid.”看出来两者的逻辑关系了吗? 如果你看不见Unix的简单,那么你就不是一个天才。 如果你看不见皇帝的衣服,那么你就  是一个白痴。 把一个东西的存在跟人的自尊和虚荣关联起来,就是为什么那两个织布工能够控制所有人的嘴。我想让人觉得我是天才,所以我得说我懂得“Unix 的简单”;我不想让人知道我是白痴,所以我得说我看见了“皇帝的衣服”。 Knuth 也曾有类似的说法:“要是看不懂 TAOCP,就别当程序员。”他总是被誉为“计算机科学的神”,在他的演讲里大谈文学,艺术,上帝和宗教,给人陡增神秘感。他总是说程序员应该学习机器语言,而不是高级语言,机器才是不变的真理。但是 Knuth 却不是从科学的角度来看这个问题,而只是他个人的偏见。当他看到 Fortran, Lisp, ALGOL, Pascal, C, C++, Java 这些语言的发展仿佛没有尽头的时候,他并没有理解其中不变的原理。在程序语言的设计上,他不是一个强者。他很有可能根本不理解 lambda calculus 和类型理论,否则他不会设计出像 TeX 那样毫无章法的语言。TeX 排版的质量无可厚非,但是到了1978年还仍然采用程序语言专家们早已深恶痛绝的 dynamic scoping,再加上其它一些蹩脚的设计,说明他对程序语言理论缺乏理解。实际上 TeX 含有一个图灵完备的扩展语言,是因为 Knuth 采纳了 Guy Steele(Scheme 的发明者)的建议,然而 Knuth 却没有把它设计好。 Knuth 觉得机器是不变的真理,所以他坚持用机器语言来写作 TAOCP。但是由于机器语言缺乏抽象,程序员没法专注于真正的问题。使用机器语言来描述算法,会把本来很简单的问题都显得高深难懂,仿佛这书永远也看不完。有多少人真正的看过 TAOCP 呢?恐怕大部分人把这套书买回去,只是把它们摆在书架上做面子。只要有人说机器语言太难懂,这些人就会说你自己不够聪明,不配做程序员。而其实呢,他们自己都没看过。 机器不是计算的本质这个事实,很多人包括 Dijkstra,早就看到了。他说:“计算机科学是个错误的名字,因为它不是计算机的科学,这就像外科手术不是刀子的科学。”而这是几乎每一个程序语言专家都明白的道理。在他们的眼里,这不再是道听途说或者个人观点,而是可以用逻辑来证明的事实。真正明白计算本质的人,可以设计出全新的硬件来来满足语义的需要,而不是受控于处理器的设计。他们甚至可以超越集成电路,而使用另外的技术来制造机器。这些都说明,计算其实是独立于机器的。 有不好的想法不要紧,但是如果把不好的想法硬说成是好的,那就会阻碍历史发展了。我并不否认 Knuth 和 Ritchie 对算法,排版和操作系统的重要贡献,但是由于他们以及他们崇拜者经常在有关语言的事情上误导群众,所以觉得有必要指出他们的一些局限性。Linus Torvalds, Guido van Rossum, Eric Raymond, Paul Graham 也经常发表对语言的评论,被很多人奉为圣旨,但其实他们言论里面很少有真知灼见。 其实我要说的不过是,通常程序员们膜拜的偶像,大部分都不是真正的程序语言专家。希望你不要觉得这是危言耸听,实际上这些是大部分世界级的计算机科学家们很多年前就知道的事情。他们不把这些向大众公开,是因为他们都是聪明人。 真正的程序语言专家在哪里 那么真正的程序语言专家在哪里呢?其实真正的程序语言专家,大部分都在大学和研究所里面。就这个专业而言,学术界要比工业界强很多。很多专家待在大学里面,是因为大学里常常有志同道合的人,而公司一般不明白程序语言专家的价值,甚至不知道他们是做什么的。 程序语言专家常常是独当一面的强人,所以程序语言方向的强弱,经常不取决于学校的名气和排名,而几乎都是取决于少数的个人。比如,曾经 Cornell 有着一颗巨星:Greg Morrisett。当时的 Cornell 是程序语言研究最强的一个地方,培养了一批最好的研究者,产生了一批像 Typed Assembly Language(一种带类型的汇编语言)那样优秀的成果。可是后来 Greg Morrisett 离开 Cornell 去了哈佛,其他人也陆续离开,Cornell 的程序语言方向也就衰落了。哈佛的计算机系曾经不咋的,可是后来由于 Greg Morrisett 出任他们的院长而实力大增,开始吸引优秀的程序语言研究者。至于 MIT,Stanford 和 Berkeley?让你吃惊的是,我看过这么多世界上最重要的论文之后发现,它们近年来似乎没有拥有过最好的程序语言专家。老一辈的专家们,有的退休,有的去世了。所以如果 MIT 把编程的入门课改成用 Python 的传言是真的,一点也不奇怪,只是觉得非常遗憾。可是跟它们名气相当的 CMU,却汇聚了一批最好的研究者,包括 Robert Harper,John Reynolds, Frank Pfenning 等等。Robert Harper 看透了面向对象语言的毛病,所以在 CMU 本科生的入门编程课中完全取消了面向对象语言的內容[参考]。很多顶级的程序语言专家不在美国,他们分布在英国,法国,丹麦,瑞典,荷兰,日本…… 这些大学和机构包括 Cambridge, Oxford, Edinburgh, INRIA, Paris 7, DIKU, Chalmers, … 当然由于他们的迁移,你无法预测一个学校未来在这方面的兴衰,也许在不久的将来 MIT, Stanford 和 Berkeley 会变成世界上最强的也说不定。我想说的其实只是,这一切都取决于那少数的个人。在程序语言的世界里,个人思想的重要性,远远大于学校的名气。 不过程序语言专家也不是完全排斥工业界的。只要有公司慧眼识英雄,给他们足够的尊敬和优待,他们也会在工业界发挥出非常大的威力。有些金融行业的公司比如 Jane Street Capital, Standard Chartered Bank 等,已经开始意识到这一点,请了一些程序语言专家来领导金融软件系统的开发。也有一些专家成立了自己的公司,从事高精尖的项目。比如 GrammaTech 就是由一个前 Cornell 程序语言教授创办的。这个二三十人的小公司,客户却包括 NASA,Boeing,Airbus, Lockheed Martin, GE,SONY 这样的巨头。再比如 IU 的教授 R. Kent Dybvig,他的公司 Cadence Research Systems 只有他一个人(有时候两个人),客户却包括 Motorola,Cisco 这样的大公司。另外的由程序语言专家创立的公司还有 Galois, BlueSpec 等等。 学术传承 由于不喜欢 Cornell 的学校气氛以及程序语言方向的衰落,我离开了 Cornell。但是我并不后悔,因为我找到了这一生中给予我最大帮助的人,他教会了我独立的思想。回过头来我也意识到,其实当时的 Cornell 仍然存在一颗超级巨星,他的名字叫 Robert Constable。不过他是如此的“厚德载物”,以至于我在 Cornell 的时候,居然没有听说过他的名字。因为我当时对程序语言粗浅的认识,让我完全不能明白他的伟大。以至于当我跟他谈话之后,我仍然决定了离开!可他却是多个最重要的研究者的“学术祖先”,包括在这个领域最受瞩目的 CMU 的教授 Robert Harper,哈佛的 Greg Morrisett,和 UPenn 的 Benjamin Pierce,…… 看过他的 Naive Computational Type Theory 之后我发现,Robert Constable 对类型理论的理解,恐怕这个世界上也少有几个人能比。 后来我才发现,Robert Constable 原来是 Stephen Kleene 的学生,而 Stephen Kleene 是 Alonzo Church 的学生。Alonzo Church 有另一个学生,他非常的出名,几乎无人不知无人不晓,他的名字叫图灵(Alan Turing)。名师出高徒,这确实是不可不信的。每个人都知道图灵,可是有多少人听说过 Stephen Kleene?其实每个程序员几乎每天都不知不觉使用他的成果。正则表达式里的 * 号(比如 “a*b*”)其实叫做 “Kleene star“,因为是 Kleene 发明了这个东西。Kleene 还有其它一些非常重要的成果,它们超前于时代,以至于直到今天人们还没能完全理解它们的潜力。举一个例子就是 Kleene 的“SMN定理”,由这个定理衍生出来的一种方法叫 Partial Evaluation,它涵盖了编译器内部大部分的“优化”,你甚至可以用这种方法来自动生成编译器。世界上最先进的 Scheme 编译器 Chez Scheme,内部就实现了这样一个优化,它能一步到位的完成别的编译器需要多步的优化,却比这多个步骤累加起来的效果还要好。 每当说到这些的时候我就默默的感叹,这个世界是怎么了。人们都说“长江后浪推前浪”,事实却不是这样的。前几天我看了一篇 Kleene 写于 1945 年的论文,几乎涵盖了现在某领域最新,最热门,最尖端的思想。而现代逻辑学鼻祖 Gottlob Frege 写于 1879 年的论文 “Begriffsschrift“,居然比后来大部分的逻辑学著作更加深刻,更加直观。为什么我们总是没法超越“古人”?因为人们都喜欢忘记历史,喜欢把简单的问题搞复杂,喜欢听能说会道的人瞎掰,却连这些有真知的科学家的名字都没听说过,更不要说去看他们的论文。 星光灿烂 鉴于广大程序员对程序语言这个专业的不了解,我这里给出一个“真正的程序语言专家名单”,让大家对他们有所了解。这里面几乎每一个人都可以被称为巨星。当然由于他们人数众多,我不可能全都列举出来,这里的列表基本上出自我看过的最好的论文。虽然其中有好些人得过图灵奖,他们一般不会以“图灵奖得主”自居。他们对计算本质的认识,有些甚至超过图灵本人。 这个列表是:C.A.R. Hoare, Dana Scott, Robin Milner, John McCarthy, Dale Miller, Christopher Strachey, Peter Landin, Robert Constable, R.M. Burstall, Valentin Turchin, Patrick Cousot, Neil D. Jones, Gordon Plotkin, J Strother Moore, Tobias Nipkow, Robert Harper, John Reynolds, Frank Pfenning, Olivier Danvy, Yoshihiko Futamura, Philip Wadler, Luca Cardeli, Greg Morrisett, Benjamin Pierce, Daniel Friedman, Matthias Felleisen, Amr Sabry, R. Kent Dybvig, … 列出这个列表,并不是说我们应该转而膜拜他们,而只是开拓一下大家的眼界,说明到底哪些人是真正的在潜心研究程序语言,不要把眼光局限于大众崇拜的“英雄”。其实不管膜拜什么人,最后你都会发现是个错误。比如我就发现上述某些人提出的概念过于复杂,却因为是(领域内的)名人而被盲目的推崇。如果你不加批判就接受的话,就永远解不开那个结。我也并不是想把我的领域捧上天。这个领域里也存在很多喜欢吹牛皮的人,偷换概念,写没有意义的论文。这些我都看得很清楚。 另外有一些人算是“半个”程序语言专家。为什么叫“半个”呢?因为他们更加接近于逻辑学家或者哲学家。在一方面,他们的思想更加深邃,经常出其不意的给出程序语言专家们梦寐以求的答案;然而在另一方面,他们的思想往往过于“符号化”,以至于他们对问题的表达方式过于复杂。由于他们的贡献对程序语言的巨大作用,也一并列在这里: Alonzo Church, Stephen Kleene, N.G. de Bruijn, Haskell Curry, W.A. Howard, Per Martin-Löf, Gerard Huet, Henk Barendregt,Thierry Coquand, Jean-Yves Girard, … 这些人之间存在着有趣的师承关系,你可以到 Mathematics Genealogy Project 查“学术家谱图”。如果一个人发明了某个概念,他的学生们也会有类似的想法。所以我经常通过这个家谱图发现具有近似思想的人,或者顺藤摸瓜找到他们思想的源头。这也可以作为一个寻找志同道合的导师的窍门。 […]

  2. […] Similarly, Robert Harper, a professor at Carnegie Mellon University, put it this way:  […]

  3. […] On Eliminating OO from Introductory Curiculum, by Robert Harper […]

  4. […] and anti-parallel by its very nature, and hence unsuitable for a modern CS curriculum.” http://existentialtype.wordpress.com/2011/03/15/teaching-fp-to-freshmen/ There will be a lot of people defending OOP but the trends/benefits in favor of Functional […]

  5. emil2000 says:

    Your own website uses WordPress, which is largely written in object-oriented PHP (yes, it actually uses the OO features of PHP). If functional languages are so great, why is your own website not written in one?

    This is just totally ridiculous. Have you ever even read Code Complete?

  6. jonathanaldrich says:

    Like others in this forum, I’d like to hear why Bob claims objects are anti-modular.

    Some past arguments I’ve heard in this vein point to problems with particular designs or languages that are not inherent to the paradigm. For example, inheritance can be misused, and some languages make it too easy to do that, but there are good methodologies for modular reasoning in the presence of inheritance (see some of Gary Leavens’ work for example; my group’s work on typestate also includes a modular treatment of inheritance).

    Other arguments rely on outdated notions of modularity, such as expecting to reason based on tracing a call to an implementation. This approach to reasoning is inherently procedural in nature and is unsuited to reasoning about any kind of higher-order design, either OO or FP.

    So in the past it has been hard to make an argument that OO is anti-modular, which stands up to scrutiny–but I would be interested to hear Bob’s take on the subject.

    • lindydonna says:

      I too would like to hear this argument, particularly why the “very nature” of OO is anti-modular. All the mainstream programming languages do OO poorly, and yes, they are anti-modular. And many–perhaps even most–instances of OO programs are non-modular. But I hope there is more to this argument than just a straw man.

      The anti-parallel argument is particularly intriguing, since I have seen several examples of OO handling parallelism quite well. For instance, Chafi et al describe how to compile DSLs written in an object-oriented host language to heterogeneous architectures (e.g., GPUs and FPGAs).

  7. arunvr says:

    Congratulations for taking such a bold yet welcome change in your curriculum. I am sure this is a step in the right direction for several reasons. The OOP paradigm is not essential for modelling every scenario. The cognitive load of learning OOP as well as programming might be distracting for the students. I have shared my own experiences on why I think teaching OOP for introductory courses is unnecessary. Hope it further illustrates why this might be better for your students.

  8. [...] how MIT folks caught the wind of it (must be those damn Paparazzis :)), but they have completely removed Object Oriented Programming from the introductory MIT curriculum. I am sure some of the best minds in Computer Science are at work here and I am glad that they have [...]

  9. [...] Robert Harper, a Professor of Computer Science at Carnegie Mellon University (CMU) posted about the new introductory CS curriculum at [...]

  10. Alex says:

    I have been very interested in the conversations happening here in the comments about Functional languages’ value over OOP languages. I don’t come at it from a professorial standpoint but rather as a recent graduate from a Big-Box 10 university.

    Functional languages were not formally introduced until my last year where they were all thrown together in a jumbled mess of a class entitled “Programming Language Concepts.” Even then the approach to teaching the class was less than ideal and left myself, as well as many others that I talked to in the class, feeling like the class lacked a purpose other than to force us to write two small programs in each of 5 different functional (and imperative) languages.

    In just a few short paragraphs the conversations here have presented a much more compelling argument for functional languages than the entire 15 week course I took. I’ll have to go back and take a look at them again as I am especially interested in the growing parallelism needed to properly utilize modern hardware.

    Thank you very much! I hope the new curriculum is a great success!

  11. bheron says:

    OO is *by definition* both modular and parallel, if I’m understanding your use of these terms correctly.

    It is modular because, when doing your OO analysis you are required to analyze the problem domain and determine what objects you have and produce classes to represent them which encapsulate and hide the implementation details of each of these classes. Outside code does not need to know how things are accomplished within an object, it just has to know what a given call does.

    It is parallel in the sense that you can, when your objects are properly written use such objects in parallel, see this: http://en.wikipedia.org/wiki/Actor_model. The Actor model is a mathematical model of concurrent computation that treats “actors” as the universal primitives of concurrent digital computation.

    So, you’ll excuse me if I’m confused as to why such a prestigious university is not teaching an essential technique to it’s students unless they “want to study it.”

    Please do not follow in the footsteps of Stepanov who believes that OO has “no merit” as this is certainly not true. Having grown up with FP, OO has made my efforts in programming much more productive and useful and, above all, reusable.

    Gregory Casamento

    • johnzabroski says:

      True, objects are inherently parallel insofar as the problem is decomposed correctly, because OO is about simulating the real world and the real world is inherently parallel. However, in practice, objects force programmers to embed procedural knowledge. These embedding tend to contain implicit assumptions about the hardware architecture or even the sequence in which objects interact.

      Please do not follow in the footsteps of Stepanov who believes that OO has “no merit” as this is certainly not true.

      Stepanov doesn’t know the canonical programming language design terminology, and so he isn’t saying what you think he is saying. This is unfortunate, because he has miseducated tons of already brain damaged C++ programmers. Rather than learn the canonical terminology, he has chosen to invent his own. If you’ve read his book, you’ll see what I mean.

  12. robnagler says:

    I applaud CMU for integrating dynamic languages into its curriculum. I imagine the political process was quite difficult so I applaud the people who are trying to change the entrenched, structured-programming viewpoint.

    I do wonder, however, if you really believe your statement “Our goal at Carnegie is provide students with an education, not training.” Python is simply a popular replacement for Java. It’s acceptable to imperative programmers and lets graduates go on to Facebook, but it is a poor choice if your goal is “education, not training”.

    It seems to me that the reasoning in the CMU-CS-10-140 report is out of date, because it fails to integrate many the changes to software development, which are in use, even large shops like Facebook. I will address one issue here, but there are others I’d be happy to address if you contact me directly.

    The report states, “Now we want students to be able to argue both formally and informally that their programs will run under all possible conditions.” This attitude was prevalent during my undergraduate days, 30 years ago. It’s a tragedy that it persists, but it’s an all-too-common position taken by programmers and academics. It’s impossible to meet the constraint “under all possible conditions.”

    Perfection is a trap for programmers for too many reasons to explain here. I’m a programmer, not an writer, but I occasionally attempt to clarify my ideas in prose. The following article touches on why perfection is not an option, and, more importantly, covers automated testing, which is notably missing from your report:

    http://www.viarob.com/my/page/The_Psychology_of_Software_Testing

    • omerzach says:

      Very few computer science majors take the new Python course; it’s meant as a crash-course to programming principles for the ~20% of incoming CS majors who have never written a line of code before and as a class for non-majors who want to learn to program but will only take one CS course at Carnegie Mellon. It’s been a while since I read that report, but I’m pretty sure that was very explicitly explained there.

      C and Standard ML are the primary languages used in the new CS curriculum; Python is not meant as a replacement for Java.

      I’d also like to add that I don’t feel like you need a Carnegie Mellon education to learn how to write good unit tests. Test-driven development is great, but I think a big point in the new curriculum is that they’re teaching things that are a) difficult and b) we can actually learn better from being in a CMU setting (professor, TAs, guided curriculum, etc.), not things a textbook or practice can teach just as well.

  13. Graham Murray says:

    Interesting. I’m not sure if this is the best solution though. One thing that I felt like my course work at CMU inadequately prepared me for was how to do OOP properly. There was plenty of technical info about OOP, but not much about patterns and practices. I truly value the FP experience that I got at CMU and I think it truly helps even thinking about/doing OOP. But so much of the professional world revolves around OOP that I’d rather CMU focused a bit more on how to do OOP well (Gang of Four should be required reading), rather than try to pretend students wont have to use it when they hit the professional world.

  14. socalsammy says:

    Interesting. Historically the argument has been going back and forth.

    Functional Programming languages such as FORTRAN used to be one of the introduction to programming classes. And FORTRAN is still around, with many simulations of large engineering projects certified using FORTRAN. Then one day FORTRAN was declared dead. Unfortunately, there is still a large body of libraries that use FORTRAN.

    LISP, one of the first object oriented programming languages. Still around, declared dead from time to time.

    COBOL, whatever that language is, bleh. Declared dead, rose from the dead in the year 2000. Then lives on at insurance companies.

    The reason that non-Computer science groups view the output of CS is that it is difficult to use. An electrical engineer needs to do simulations and doesn’t like for variables to change. Game Programmers need to use objects.

    Hey, it’s a big world out here. Engineering and Physical Science Students will thrive if functional programming is taught as an intro class.

    • abstract type says:

      This is the first time I’ve ever heard of Fortran being called a “functional language”. My objection so oopl’s is that they force a single paradigm on you, namely objects, which is often the wrong tool for the job, which is not to say that they are never the right tool.

    • beaneg says:

      Fortran is not functional. Haskel, F#, and Caml are example of functional languages. You are confusing imperative and functional.

  15. [...] a few blows. First it was the chapter on “the art of Unix programming (TAOUP),” then I just read that CMU is dropping OO programming from its introductory curriculum, and only planning to offer it [...]

  16. RalfW says:

    I the decision very much. And my experience is the same with OO. I´d argue like this:

    1. OO at it´s heart is about state. It´s state everywhere (at least if you follow mainstream OOAD thinking). And state is shared liberally. That´s a fundamental anti-pattern for concurrent programming. But since it´s so ingrained in the OO paradigm and in the minds of millions of programmers, it´s nearly impossible to fight it with additional principles.

    Some OO languages might offer help for async/concurrent programming – but still they are OO languages and people will use them in suboptimal ways. We´ve seen that before with remote communication. At least 10 years and millions of dollars were lost to the vain idea of remote objects (aka CORBA, COM+, EJB).

    2. OO at it´s heart is about dependencies. Without additional principles OO code will quickly grow into a dependency mess: static, dynamic, functional dependencies everywhere. The recent rise of “clean code” thinking is only an expression of this fundamental drawback of OO. The SOLID principle and a host of others are trying to compensate what OO itself is lacking. To not much avail. It´s hart to teach Joe Developer to be careful to constantly heed all those principles.

    Dependencies are anti-modular. State is anti-concurrent. So OO unfortunately stands in the way of more modular and more async/concurrent programs.

    However, while FP might help with the second, I doubt it will help with the first. FP itself has no notion of larger functional blocks than functions (or maybe classes in hybrid languages). So it does not guide much the thinking of developers in terms of abstraction and work allocation within a team.

    Developers/students are very textual source code focused (be that OO or FP languages). Source code however is a bad tool to help teams to jointly design software.

    My experience is, if you give developers a tool/method to 1. help them think in non-OO ways during design at least, 2. help them with easy diagramming (no, not UML ;-), and 3. help them with ways to organize code so that all team members can work in parallel on the same (!) feature… then team performance as well as personal satisfaction improves much.

    -Ralf

    • techtonywp says:

      OO is not “at its heart, about dependencies”. This is naivete or misinformation. To pick out one aspect of OO (i.e., inheritance or class hierarchies) is to “miss the boat”. Being or becoming a good software designer (and some are more suited to this than others) applies to any given software design paradigm. As is the case with most things, people tend to grasp at “the low-hanging fruit” and extreme scenarios and miss everything in-between. This is, of course, “shallow thinking”. To eliminate a ubiquitous design paradigm from a curriculum is inappropriate. Granted that a single paradigm should probably not be a stand-alone class — rather, there should be a class on software design which covers the most important paradigms in detail and surveys past, present and potential future design paradigms.

    • RalfW says:

      I have seen this reaction before, techtonywp. But let me ask you: Have you seen any OO program not struggling with dependencies? Why has there been so much fuzz about IoC? Why are DI containers the basic tool for any OO programmer today? What about principles like Law of Demeter or Interface Segregation?

      All this is just because static/dynamic dependencies are everywhere in OO programs. (Let alone logical/functional dependencies which we cannot avoid.)

      So millions and millions of programmers are just dumb, because the “grasp at ‘the low-hanging fruit’”? I doubt it. Or if so, then I´d say not the dumb programmers have to be educated but the paradigm has to shift.

    • johnzabroski says:

      Why are DI containers the basic tool for any OO programmer today?

      DI containers are a basic tool because scattering object initialization across client classes breaks encapsulation. DI containers “contain” all the object initialization logic, and provide an object to inject into the application. Beyond that, ultimately, it is worth noting that most OO languages today have their weaknesses highlighted by the presence of DI containers. Why, though? Because they let you create pseudo-modules called “packages” (or some other buzzword) that contain concrete external dependencies. But a module with concrete external depenendencies isn’t a module, since it depends on a very specific behavior somewhere else, and if it doesn’t get that exact behavior, who knows what could go wrong? What’s the solution? Well, we start by not allowing programmers to build modules with concrete external dependencies. From there, we build progressively more advanced module systems e.g. parameterized by equations.

      Have you seen any OO program not struggling with dependencies?

      Functional programs written in functional programming languages have dependency challenges, such as one library using one string implementation and another library using a different string implementation. There is no free lunch, you have to pay for your soup no matter what techniques you use. Due to the fact that most functional programming languages lack robust libraries shipped with the compiler proper, practitioners have avoided them since it is much easier to deal with the OO dependency problem vs. a package management dependency problem. OO programs also have package management dependency problems, but inertia has taken care of this problem in practice – there are tons and tons of .NET and Java libraries. More recent functional programming languages, attempting to interest the mainstream and also ease programming multicore systems, are built on top of the CLR and JVM. However, their performance is bottlenecked by the intrinsics supported by these VMs. These are sociological concerns, not theoretical ones.

      What about principles like Law of Demeter or Interface Segregation?

      These are rules for any language, and as with rules, you are taught them first as a guideline, and you have to know when (and how) to break them. For example, for the Law of Demeter, it is helpful to not address every detail of a data structure when writing an operation over that data structure – we want to “Scrap Your Boilerplate” and make the compiler infer the code for you. Even better than “Scrapping Your Boilerplate” is to have first-class patterns, and make variables used for reduction purposes separate from binding variables used to control scope.

      All this is just because static/dynamic dependencies are everywhere in OO programs.

      My best guess is that you failed to understand what these principles were stated for. The goal is structured design. In other words, to solve the problem structurally, and then let the details almost implement themselves. For example, a Factory pattern addresses hiding from the problem domain details of object construction, since any two objects collaborating with one another should not care at all about how they came to be, only that they are mutual peers and have to collaborate. Similarly, Behavioral patterns are really just a way to convert dynamic run-time behavior into structure. Viewed this way, we can solve many canonical OO behavioral pattern implementation issues simply by adding an additional layer of indirection (introducing another object) into the solution. For example, we can interject a Registrar between an Observer and Subject, and that Registrar can manage potentially adverserial or non-cooperative observers, giving each Observer a fair, deterministic opportunity to respond to announcements from a Subject. Now, I don’t have to use Objects to describe this, I could use something like contextual nets instead, but my experience is I can explain what I just said above to any programmer I’ve ever met, and they will understand my design goal instantly, whereas with contextual nets they might need some heavy formalism to decipher how things will actually work (e.g., conditional term rewriting, etc.)

      Finally, note that in my example, Subject, Observer and Registrar do not share a class hierarchy and do not derive from one another; there is no inheritance. Yet we are still managing dependencies. Except, the dependencies are the values produced by Subjects and consumed by Observers, with the special case that Observers can perturb the Subject in response. Without a Registrar (or equivalent), you would have a nondeterministic system, since some Observers would be acting on stale information.

      Obviously, paraphrasing Bob’s remarks in his post “The dog that didn’t bark”, structural induction is one of many tricks software developers can use to manage the structure of applications. But structural induction doesn’t cover everything, including concurrent and demand-driven computation.

    • RalfW says:

      @johnzabroski: You´re saying:

      My best guess is that you failed to understand what these principles [like LoD] were stated for. The goal is structured design. In other words, to solve the problem structurally, and then let the details almost implement themselves.

      To use you´re ton of voice let me answer like this: I guess you´re failing to understand the cause-effect relationship here.

      It is because of the complexity of OO that all these patterns and principles had to be “invented”. Without a host of patterns and principles there is no way that a non-trivial OO program can easily evolve.

      Now you might be proud because you understand all these principles and patterns – but unfortunately millions of programmers don´t. So millions of programmers are stuck with a tool (OO) that is so complicated it´s hardly of much use.

      This is not to say that the notion of objects is bad. I like polymorphism and even inheritance (once in a while). But trying to
      design (!) software systems using “just” object thinking unfortunately hardly ever leads to long term easily evolvable systems.

      I know plenty of companies struggling with messes of OO code. And I know hardly any company being content with their OO code after 5 oder 10 years. To be honest, I don´t know a single such company.

      So is this situation the fault of dumb programmers and dumb teachers all not grasping the essence of OO? Maybe. But, well, I guess then have to live with all such dumbness and better adapt out approaches to programming to it.

      I at least do no longer design software along OOAD or using design patterns. That has not proven helpful. I use OO languages, of course. But OO is bridled by a functional or flow-oriented design. At least this suites my obvious OO-dumbness.

    • jonathanaldrich says:

      OO is neither about state, nor about dependencies. William Cook’s excellent essay argues that the essence of OO is procedural data abstraction (i.e. dynamic dispatch): each object (conceptually) carries with it the procedures necessary to use it; different objects with the same interface can be implemented differently. Cook’s examples in the paper are all functional; state is not essential to objects.

      Why does this matter? As johnzabroski pointed out above, domain decomposition is important to OO design, and dynamic dispatch supports that. But the most critical thing is capturing the points of variation in a domain: where are there different kinds of things, and where are things likely to change? This principle of design goes back to Parnas; in the OO context it underlines most design patterns (as is well covered by Shalloway and Trott’s Design Patterns Explained text).

      The reason OO “works” is that for many programs, software evolvability is the most important design criterion, and OO makes creating these structured points of variation easy (e.g. using an interface with multiple implementations that are chosen dynamically via dispatch). Software frameworks, which are some of the most successful reusable libraries today, rely inherently on this kind of variability support.

    • abstract type says:

      We don’t need William Cook to state the obvious; see my book for a discussion of classes and methods from a functional point of view.

      I am well aware of the numerous epicycles introduced into an oop framework to reduce it to what we had in the first place, namely a rich module system.

    • jonathanaldrich says:

      Yes, I cited Cook’s paper as a response to RalfW’s statement, to argue that state is not an essential feature of objects. Design advice from people like Joshua Bloch also emphasizes the value of purely functional objects in situations where state is not needed.

      Few if any interesting OOP frameworks, however, can be expressed in rich module systems like that of ML. The key reason is that the structure of nearly all important frameworks is highly dynamic. This is not because of OO; it is driven by domain requirements to add or reconfigure new functionality as the program is running. Thus plugins to frameworks are commonly created, connected, and reconnected dynamically. Most rich module systems in current languages (such as ML) do not support this dynamism at the module level.

      Of course there are module systems in the research literature/research languages in which modules are first-class, and in which they can be instantiated and connected dynamically as required by modern frameworks. In Cook’s definition, as in my own (and I think consistent with yours), these module systems incorporate the most essential and valuable feature of OOP. They are object-oriented.

    • abstract type says:

      As I say in my book, the term “object-oriented” is mainly used to express approval; it doesn’t mean very much, except that it’s never what it actually is in practice.

    • lindydonna says:

      I’m confused; if OO doesn’t mean much (which is often true in mainstream programming practice), then how can it have any property, let alone those claimed in this post?

      It seems that it would be more productive to use a definition of OO that is used in programming languages research–for instance, the idea of procedural abstraction as discussed above. In such a case, we should call a spade a spade and note that some higher-order module systems are in fact object-oriented, as distasteful as this term might be. Does something become automatically “bad” and “anti-modular” as soon as it is termed “object-oriented”?

    • abstract type says:

      I should say “by proponents”. The point is that many of the supposed innovations of the OO world are just awkward and ugly reformulations of ideas that were present at the start in type theory. There’s no need for epicycles that make a bad idea slightly less bad; we had the right idea in the first place.

  17. [...] Harper and Dan Licata, Professors of Computer Science at Carnegie Mellon University, announced last week that they have decided to “eliminate entirely” OOP from the CS introductory curriculum. [...]

  18. [...] on : Robert Harper’s post. Referenced in the post is the report Introductory Computer Science Education at Carnegie Mellon [...]

  19. samuelryan says:

    Even if functional programming is considered better as being more module and inherently parallel, the vast majority of professional development is object oriented. You’re doing a great disservice to your graduates by primarily and sometimes only teaching techniques that are not used in the workplace. It’s true that there is some pressure towards functional programming in professional development, but it’s still minor and is likely to continue to be a minor proportion for another decade or two.

    • abstract type says:

      Our goal at Carnegie is provide students with an education, not training. There are plenty of opportunities for them to learn the old ways, and to pick up industry practices on the fly. My department head recently had a meeting with the (very many) Carnegie alums working as developers at Facebook, and they overwhelmingly said that one of the three most important courses for them was my course on functional programming. The reason? Because they learned there how to think abstractly, and learned what the code “should be”, and then used this as a model for working with the code “as it is”. They cited their ability as giving them an overwhelming advantage over the other developers with whom they work. So, no, I have no regrets, and I firmly believe we are doing the right thing by our students.

    • samuelryan says:

      I agree with the importance of learning functional programming and the value it brings to programmers, but cannot agree with the fundamental shift in priorities. Of course universities are not purely practical training and do not teach developers the many many technologies they’ll need to learn once they graduate, but they also need a good foundation to build upon. We interview dozens of candidates each for each internship period from several universities, including CMU, and we never expect them to have specific knowledge in the technologies we use, but we certainly require a basic fundamental understanding and educational experience in OOP.

    • johnzabroski says:

      Why do you require it, then?

      I don’t necessarily care if CMU teaches functional programming or OO, but I would like to see computer science professors teach design. However, very few have any clue what that word means.

      (I am guessing that what you are really testing for is the ability of a student to do design, not OOP. Marian Petre’s Ph.D. thesis from the 80s showed that the single biggest factor influencing a design expert’s problem solving expertise was there fluency in multiple paradigms.)

    • Scott Kilpatrick says:

      What’s wrong with offering an optional course on OOP?

    • abstract type says:

      Nothing; that’s exactly what we do. We’ve just stopped using OOP to teach introductory programming; it’s counterproductive. If students want to learn that stuff later, they certainly can, both here and on the job.

    • Scott Kilpatrick says:

      Right. My question was posed to samuelryan. (When you described the curriculum above you mentioned the optional OOP course.)

      In my mind this mediates the two approaches to PL education quite reasonably. Others, however, would fault the curriculum for not churning out industry-ready, OO programmers for their first summer. (I believe this was a common complaint about MIT’s former Scheme-based curriculum.) Arguably these people would rather produce cheap interns than computer scientists.

    • samuelryan says:

      IMO, what’s wrong is that it’s optional. OOP is a fundamental requirements for the majority of professional software development.

    • climatecode says:

      CMU is teaching Computer Science. Not “How to be a programmer”.

  20. [...] the trainer himself, the only one who could have gotten into the stables unnoticed.  As I’ve mentioned, this semester Dan Licata and I are co-teaching a new course in functional programming for [...]

  21. mcandre says:

    That’s great news!

  22. pauldoo says:

    I too would like to hear the argument to why OO is anti-modular.

  23. philipschwarz1 says:

    Why do you say that OO is anti-modular?

    In Object Oriented Software Construction (http://www.amazon.com/Object-Oriented-Software-Construction-Book-CD-ROM/dp/0136291554), Bertrand Meyer showed that OO decomposition meets all of the following:

    5 criteria:
    Modular Decomposability
    Modular Composability
    Modular Continuity
    Modular Protection
    Modular Understandability

    5 rules:
    Direct Mapping
    Few Interfaces
    Explicit Interfaces
    Information Hiding
    Small Interfaces (weak coupling)

    5 principles:
    Linguistic Modular Units principle
    Self-Documentation principle
    Uniform Access principle
    Open-Closed principle
    Single Choice principle

    • abstract type says:

      You’re joking, right?

    • serg5z says:

      could you please be more verbose.
      I also do not understand why OO is labeled as anti-modular.
      I think there is nothing wrong with OO per se. There may be wrong applications though.

    • johnzabroski says:

      serg5z,

      You may find Neelk’s explanation at Lambda the Ultimate very helpful:

      http://lambda-the-ultimate.org/node/4235#comment-64975

      By the way, bonus points if you can tell me how you would write an OO ATM software. This is the modern Glenford Myers’ Art of Testing “Test this triangle” for OO, IMHO. Mainly because so many purported “design” textbooks about OO Analysis & Design used ATMs as a pedagogical example (most of them got it wrong, IMHO, too).

    • serg5z says:

      John,
      This sounds like:
      “Do your utmost and get me
      Something That Cannot Be!
      Write it down for it might
      Somehow get out of your mind”

      There is no way to produce a satisfactory implementation to an undefined problem. Any attempt to provide implementation for “X software” is doomed regardless what paradigm is used.

      A problem in order to be solvable has to have well defined bounds. Otherwise it is possible to dismiss any solution with “oh, by the way, how about Y, your solution does not address this at all…”.

      I’m sure that there is no ultimate FP solution to “ATM software”.

      Regards.

    • johnzabroski says:

      serg5z,

      As I see it, the increased network bandwidth one solution uses might be considered neglible in some contexts. So some might say “There’s nothing to learn here!”

      Likewise, we may never wish to worry about ever upgrading an ATM, and keep currencies constant, and keep receipt formats constant, and keep the display screen and menu options and input methods constant, and keep the accounting bookkeeping methods constant. But then these constants add up to very monolithic design. (We’re talking about modularity, aren’t we?) One of the selling points of OO was that the real world provides all the details on how to design objects, but what I am saying is that most people are actually very poor at selecting the right objects.

      You’ve piqued my interest: How would you give the assignment to a student, or present it for pedagogy purposes? (Most people don’t push back when I give this example, so it is cool when I get resisteance from people who say, “B.S. I don’t get it.”) (You can answer via e-mail if you wish, I don’t want to tie up Bob’s blog with a digression: username @ yahoo dot com).

    • johnzabroski says:

      OO is essentially modular only insofar as the domain decomposition is correct, due to the fact that properly designed objects encapsulate their responsibilities.

      I have seen too many examples of OO gone wrong. My favorite is the textbook example of an ATM where the ATM has knowledge of bank accounts, implying that Account classes have to be serializable and shared by the client and server. You’ve immediately complicated your whole system by requiring an object broker. And you still haven’t built an ATM. And why is an object broker essential to building an ATM?

      Orthogonal to that problem is the question of how you persistent account objects. In other words, how does an (ATM) Account interact with an accounting subsystem that manages transactions? Who is responsible for managing the details of how to post transactions correctly and ensure the integrity of Account objects? This is one example of why enterprise software today advocates “persistence ignorance” as an OO best practice.

      But now for the really interesting fun! This same logic applies to non-OO software! Because, guess what, domain decomposition is really important no matter what! (In fact, the parametric programming available in functional programming languages can in some cases be a better way to decompose a problem – yet we should never do this at the expense of foolish design mistakes).

      Sorry, no free lunch. You still have to learn how to use abstraction properly. Maybe Bob will teach us on this blog.

  24. gknauth says:

    Your new course sounds great. I wish I could go back 30 years and take it.

  25. aivarannamaa says:

    I would also like to know why OO is anti-modular.

  26. Geoff says:

    Could you talk a bit in a future post about why objected-oriented programming is “anti-modular and anti-parallel by its very nature,” moreso than even imperative programming? I tend to agree, but I have a hard time arguing it. I would be curious to hear some specific reasons why this is so. Thanks!

    • johnzabroski says:

      Object-oriented programming requires correct domain decomposition, and so its primary source of parallelism is going to be the parallelism in the problem domain, rather than sequences of operations performed on objects. (However, I think “anti-parallel” is a bit sensationalistic.)

      If you want an example of open recursion and object-oriented programming being difficult, google for papers on The Inheritance Anomaly. For a good solution, read Jose Meseguer’s paper “Solving the Inheritance Anomaly in Concurrent Object-Oriented Programming”. Jose’s trick, which is obvious once you think about it, is to Solve The Problem By Avoiding It(TM). He simply argues solving the problem at the wrong level of abstraction is the root cause, and that if people would just do that, there would be no talk of this “anomaly”, which is really a modularity problem.

    • johnzabroski says:

      Oops. Should’ve said “an example of open recursion and *concurrent* object-oriented programming being difficult”.

    • aqd0 says:

      I read it but…

      The root problem seems to be about imperative programming, so why not use OO in a purely-functional way?

    • johnzabroski says:

      The root problem is not imperative programming. The root problem is reusing synchronization code in ad-hoc ways e.g. through open recursion.

  27. [...] an earlier post I mentioned that one goal of the new introductory curriculum at Carnegie Mellon is to teach [...]

  28. [...] mentioned in a previous post that I am developing a new course on functional programming for first-year students.  The [...]

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,428 other followers

%d bloggers like this: