// you’re reading...

Education

Computer Science at Waterloo: the new Scheme of things

Programming with Scheme at the University of Waterloo

First-year computer science courses at the University of Waterloo will undergo a major revision in fall 2008. CS at UW is part of the Faculty of Mathematics, and all Math students (including not only CS and traditional Math students, but accountants, actuaries, statisticians, and many others) take two courses in CS as part of their core requirements, but they have typically had a choice of courses depending on interest and experience. For the first time in fall 2008, all of the first-term courses will use the programming language Scheme.

The course aimed at CS majors, CS 135, has been running as an alternative for four years now, attracting both CS students and other Math students. Scheme is a functional programming language with simple syntax, which permits the course to focus on ideas instead of language details, and gives the students a simple model of the meaning of a program. The PLT Scheme software (DrScheme), specifically designed for education, permits students to start in a simple teaching language with targetted error messages and move upward through language levels of increasing complexity.

CS 135 is followed by CS 136 which introduces C and covers notions of efficiency, scalability, and what actually happens at the machine level in both languages. The goal of CS 136 is to provide a firm foundation for subsequent study in computer science.

Making its debut in fall 2008 will be CS 115, aimed at non-CS majors. This covers about two-thirds of CS 135, with more examples and less formality. It is followed by CS 116, which covers selected topics from the rest of CS 135 and CS 136, but using Python. Students who find this material to their taste can follow up with CS 136 and other CS major courses.

Waterloo has had advanced math courses taken by the top 10% of students for decades, but never an advanced CS course. CS 145 will also debut in fall 2008. It will feature a highly conceptual approach to topics from CS 135 and CS 136, also using Scheme and C; students will proceed to second-year CS courses in the winter term of first year. The use of Scheme means that the prerequisites for the course are aptitude and an open mind, rather than prior experience.

The choice of three related entry points offer students flexibility (all courses are open to all students, and they can move up or down easily in the first few weeks) as well as a distinctive approach with proven effectiveness. The skills involved in expressing computation using Scheme as well as C or Python translate well to the many languages students may find themselves using in the workplace, and students in all of these courses get a representative look at important themes of computer science which they may choose to explore in followup courses.

Read more

Discussion

  1. Posted by Tony | March 18, 2008, 8:01 am

    Announced back in May 2007, the changes have passed the approval and will take effect. Professor Prabhakar Ragde is the source on making sense of the new curriculum, and I thank him for offering to write up this guide to the new program.

    Personally I’m thrilled about the use of Scheme. Java is great for large corporate projects, but it was a poor choice for academic study, especially at an introductory level. Java is very verbose and requires a lot of, often unexplained, syntax just to run. Having worked with other students, I’ve noticed that a lot of time was devoted to simply figuring out the language itself.

    CompSci.ca Forums already cover at least a part of the functional programming paradigm, so you should know where to catch up on some Scheme ;)

    Reply to comment

  2. Posted by Noam | March 18, 2008, 11:07 am

    This is awesome news. Java makes me sad. :P

    I do have a couple of questions though.

    In CS 134, students learned about (among other things) abstract data types, data structures, and exact asymptotic analyses, which are built upon in second-year. Using Java, CS 134 taught these concepts in an object-oriented context.
    Scheme and C are not object-oriented, and some of the upper year courses (currently) do rely somewhat on student knowledge of OOP principles. Will students still have adequate preparation for courses like CS 240 (Data Structures), which expect a basic knowledge of abstract data types, data structures and code analysis? What about CS 246 (Software Design and Abstraction), which deals with OOP design patterns and principles that were discussed in CS 133/134? Will upper year CS courses be expected to change to accomodate the shift in first-year courses? Will they still use Java and C in assignments, for instance?

    I should mention that I am not asking these questions because I feel something is wrong here; I’m very excited about these changes and I’m certain that these questions have been considered already. I’ve only started hearing about these changes though, and I’m very curious about exactly how things will work. :)

    Reply to comment

  3. Posted by Prabhakar Ragde | March 18, 2008, 2:31 pm

    Noam: I am in the third-last week of the pilot version of the new CS 136, which will replace CS 134. In CS 136, we cover, among other things, abstract data types, data structures, and asymptotic analysis of algorithms, using both Scheme and C, in more depth than CS 134. (On last week’s assignment, students wrote code for a purely functional indexable deque with logarithmic-time operations; this week, they’re studying the tradeoffs between preprocessing and query time using C.)

    We cover the basics of objects by showing how to encapsulate state variables in Scheme. ADTs are covered by this technique and also by using PLT Scheme’s modules together with opaque structures (we also discuss typedef and separate compilation in C). This separation of the roles of classes and modules is harder to get across with Java in which the roles are conflated. The course ends with a discussion of type abstraction in C , Java, ML, and Haskell.

    They will certainly be prepared for CS 240 (Data Structures). CS 246 will be changing for other reasons as well, and I don’t know what form it will take, but I hope that it will include the use of both C and Java, and that we can return to the assumption we once made that upper-year students can rapidly learn languages and systems on their own (after perhaps a brief overview in lecture) in order to use them in learning concepts and techniques.

    Reply to comment

  4. Posted by Prabhakar Ragde | March 18, 2008, 2:56 pm

    I should also mention that while Tony has linked to Wikipedia for the phrase “programming language Scheme”, the link really should be to http://www.htdp.org/ , the online version of the textbook designed to work with DrScheme. The reason is that CS 135 and CS 115 don’t actually use Scheme as described by Wikipedia. They use a tiny subset of it augmented with some features that don’t appear in R5RS Scheme (structures, the “local” construct) and with some standard constructs renamed to be more intuitive (first and rest instead of car and cdr, empty instead of ‘()). Scheme is not a small language, but the HtDP teaching languages are small — and yet powerful enough to provide a challenging and stimulating first course in computation.

    Reply to comment

  5. Posted by Tony | March 18, 2008, 3:57 pm

    I’ve updated the link in the article.

    Reply to comment

  6. Posted by Scott | March 19, 2008, 1:04 pm

    According to Joel (Joel Spolsky: The Perils of JavaSchools). We’re all a little safer now.

    Reply to comment

  7. Posted by Gurukulam » Blog Archive » There is hope.. | March 19, 2008, 1:11 pm

    [...] of Waterloo chooses to use Scheme in Fall 08 for first year CS undergrads instead of Java. More US schools should [...]

  8. Posted by Kevin | March 19, 2008, 2:13 pm

    Northeastern University in Boston MA (where i went) did this around when i started, 6 or so years ago. I’m glad to see it’s catching on!

    Reply to comment

  9. Posted by Emmy | March 19, 2008, 2:18 pm

    A program like this is already in effect at Worcester Polytechnic Institute and has been for years. The intro cs classes, intro to programming design and accelerated intro to program design are taught with scheme so the students can focus on the ideas of good program design and functionality instead of complex syntax. It is followed my higher cs classes in java and c.

    Reply to comment

  10. Posted by Johnny | March 19, 2008, 2:21 pm

    Fantastic! It is just terrific to see that Prof. Ragde finally saw his idea through. Congratulations!

    Reply to comment

  11. Posted by Prabhakar Ragde | March 19, 2008, 2:34 pm

    The courses at Northeastern and WPI (plus ones at Chicago, Utah, Georgia Tech, and some other institutions) were a source of ideas for the original design of CS 135 at Waterloo in fall 2004, as these used the same textbook and software. CS 136 is more of a synthesis on my part, and CS 145 will also be unique. Another difference is the number of students involved — 400 CS majors a year, plus about 700 non-CS Math majors.

    Reply to comment

  12. Posted by John Nowak | March 19, 2008, 2:34 pm

    Congratulations! DrScheme is a fantastic way to introduce people to programming. Clean, understandable, and simple semantics are a must!

    Reply to comment

  13. Posted by Andrew | March 19, 2008, 2:57 pm

    Another Northeastern CS student here – starting with Scheme is definitely a good thing!

    Waiting until now to start using DrScheme for a course is also definitely a good thing. Back in 2003 when I started using it, DrScheme was frustratingly buggy.

    Reply to comment

  14. Posted by David Greiman | March 19, 2008, 3:16 pm

    I was ‘forced’ to learn Pascal when I started (another learning language, so to speak). I would have rather just bit the bullet and learned a real-world language to help improve my market skills. Employers have complained that CS graduates can solve CS problems but they can’t work handle .Net, J2EE, Oracle, etc. with out significant ramp-up. There has to be a good balance of academic and real-world, IMO.

    Reply to comment

  15. Posted by Brian Schneider | March 19, 2008, 3:42 pm

    when i was at syracuse as a freshman in 95/96, second semester we had scheme…my first comp. sci. class…since switched majors that semester.

    Reply to comment

  16. Posted by Prabhakar Ragde | March 19, 2008, 4:10 pm

    David: We had students learning a “real-world” language, Java, as their first language for ten years. They still couldn’t handle .Net, Oracle, etc. without significant ramp-up, and they couldn’t solve CS problems, either. My first university course was in a “real-world” language, too — COBOL. It gave me some temporary marketability (though I vowed never to take a job using it) and nothing in terms of transferable skills. First-year students need practice in problem solving, design, testing, and fundamental concepts of CS, not reams of detail regarding a particular “real-world” language that may be obsolete by the time they graduate.

    Reply to comment

  17. Posted by Henrik | March 19, 2008, 4:44 pm

    I started studying computer science in the Helsinki University of Technology in the end of 90s. There was a course which translates roughly to “The Extended Basic course for Programming”. The language used was Scheme. Taking the course made me realize that computer science and the whole university wasn’t really the thing for me, and I decided to jump ship straight in the beginning. It is a good motivation tester to have a course in a language which is 0% applicable to any practical and work situations.

    Reply to comment

  18. Posted by Martin | March 19, 2008, 4:46 pm

    David: Perhaps companies who want employees with .Net/j2ee/oracle skills might want to look into hiring graduates from vocational programs targeted at programming, rather than CS graduates, just as a CS degree perhaps isn’t the right thing for someone whose goal is being a java/c# programmer.

    Reply to comment

  19. Posted by Prabhakar Ragde | March 19, 2008, 5:21 pm

    Henrik: I’m guessing that your course used MIT’s approach and the textbook “Structure and Interpretation of Computer Programming”. The textbook and software we are using did not exist at that time. Our approach (and that of Northeastern and the other schools using this approach) is quite different — more gentle, more systematic, and applicability is stressed.

    Reply to comment

  20. Posted by Wat-Now? | March 19, 2008, 5:57 pm

    Back in my day at UW, we cut our teeth on Pascal mainly (Cobol & Fortran for some electives, and C in some later courses). I don’t remember there being any OO languages used, perhaps smalltalk or early C (this was the mid 80’s). Colleagues and I picked up C very easily in industry. In fact, anyone who uses Pascal and C et. al. for any significant amount of time (like throughout an undergrad curriculum) comes to an intuitive understanding of OO and expectation that it is needed. You end up writing OO-like code, to the extent possible by the procedural language you’re using: via C macros, structs, function pointers, and Pascal records and types. Being taught a so-called unmarketable language is not an issue if you are being taught highly marketable fundamental skills. (As it turns out, Pascal was highly marketable at the time, partially explaining the UW/BNR synergy).

    Reply to comment

  21. Posted by DaveMo | March 19, 2008, 6:39 pm

    I recently finished a “vocational program” here in Saskatchewan (CST ~ Computer Systems Technology) at SIAST Kelsey Campus. While I did have prior work and education that helped me breeze through much of the java programming first year I think utilizing a language like Scheme would have simplified things for a lot of the other students who had no background whatsoever. A lot of first time programming / cs students tend to get very confused by cryptic syntax irregularities and really strange error reporting messages.

    This sounds like a good thing, I hope more educational institutions take note of what uWaterloo is doing here :)

    Reply to comment

  22. Posted by Peter Michaux | March 19, 2008, 7:18 pm

    Luck, lucky students! What a great program you have for your beginning CS majors!

    Reply to comment

  23. Posted by Hypothetical Labs » The world becomes a little bit safer | March 19, 2008, 7:31 pm

    [...] Leading Canadian University drops Java in favour of Scheme for first year students [...]

  24. Posted by Robert | March 19, 2008, 7:52 pm

    As a student who took the Scheme first sequence in Fall 05, I would certainly say that my fundamentals are much better than I would have initially guessed. I’m able to easily break down a problem recursively and then segue to the iterative solution. It has actually helped me on my co-op interviews since for the skill questions I was often asked to come up with a recursive solution to a problem after finding the iterative one. Interviewers commented on seeing scheme on my resume, and they were pleased with the answers I gave.

    It let me to think of problem solving in a way that is removed from the language I’m working in, since everything else is just syntax and obscure details.

    What is the sound of one parenthesis opening….

    Reply to comment

  25. Posted by Steve | March 19, 2008, 8:28 pm

    Personally I think that is a step backwards. My university in the UK has just changed its first year courses from Scheme to Java. Scheme requires a type of thinking that is entirely different from that required by other languages (though admittedly this depends on how it is taught) and just adds another layer of complexity for students to understand. Although Java does have extra syntax to make it work, this can be brushed aside quite easily whilst still concentrating on the basics of procedural programming, a paradigm that I think is much easier to grasp.

    Reply to comment

  26. Posted by tom blalock | March 19, 2008, 9:01 pm

    The first goal in designing any computer language is minimizing parenthesis. Scheme fails miserably in this respect.

    Reply to comment

  27. Posted by Adam H | March 19, 2008, 10:23 pm

    When I started at Waterloo in ‘98 I was in the very first pilot group learning Java — the infamous M section 13. I count myself very lucky that I already knew how to program before that class. I don’t blame the teachers (yes two) for the poor performance of my classmates and instead blame the complexity and flexibility of Java. We were thrown into an OOP world without even knowing what a procedure or function was. I blame the Turtle class, a waste of time in any programming language except Logo. I blame the fact that we worked with Applets, why add all that complexity when we are supposed to be learning how to program? That of course is the short list but I think you see my point.

    Of course it is possible to shoe horn a much simpler programming course into void main, as Java schools have learned they must. But why allow all the issues of Java syntax to hinder a student from learning programming concepts? I’m not sold on Scheme either but I am certainly impressed by the showroom. The brackets are annoying agreed but DrScheme seems to do a good job of highlighting what bracket you are in and providing easy methods for debugging and visual parsing your code.

    I learned on Turing back in high school and its simplicity of syntax, I believe, has led directly to my success in school and subsequently in industry.

    Reply to comment

  28. Posted by PT | March 20, 2008, 2:04 am

    I’ve started my CS career in the University of Manchester (UK) with a functional language called SML. I think it was an excellent way to start even though SML is not used pretty much anywhere. Java might be used widely but it is not a good language for teachnig – you’ll get into SML in half the time. Make difference between learning to program and learning languages for they are very different things.

    For those who are afraid they’ll be left behind from the start if not learning a language used in the business: you can sleep your nights calmly. You’ll have plenty of time to learn Java, C, C , C#, Perl, Python, Ruby, Lisp, Prolog… the list goes on, trust me.

    Reply to comment

  29. Posted by University of Waterloo and introduction to programming « Occasionally sane | March 20, 2008, 8:26 am

    [...] Waterloo and introduction to programming It has been reported that the University of Waterloo dropped Java in favor of Scheme for first year students. A lot of discussion revolves around whether this is a good [...]

  30. Posted by Anon | March 20, 2008, 9:25 am

    I did my CS degree 95-98 at the University of Manchester, UK. First semester contained NO imperative languages. It was all functional programming and discrete maths. All labs we done in SML. This managed to help level the playing field for students who had little programming experience behind them, and really started to drill home a lot of concepts that the more experienced students were oblivious too.

    If you are going to teach commercial languages such as Java/.NET, do it in the later years. Get the real eduction out of the way first before polluting their minds with this.

    Reply to comment

  31. Posted by Grant Rettke | March 25, 2008, 7:21 pm

    PT brought up a critical question: is your goal to learn how to program, or to learn a particular language?

    If you want to learn how to program, it takes time, practice, good material, a good medium (programming language), and hopefully you’ve got a good teacher.

    If you want to learn a particular language, it takes one book.

    There is a big difference. Don’t confuse the two!

    Reply to comment

  32. Posted by Gary Baumgartner | March 28, 2008, 9:06 pm

    Addressing the statement above:

    “The first goal in designing any computer language is minimizing parenthesis.”
    “Scheme fails miserably in this respect.”

    I, in a sense agree with the first statement.

    However, the second statement is false, despite how incredibly obvious it seems at first glance! Scheme code does use more parentheses per line than code in more common languages, but (except for small programs) has fewer lines of code.

    A student of mine just wrote a program in Scheme, and it turned out another experienced Python programmer was writing a program for a similar task. We counted the number of parentheses in each, and the Python program had many more (not to mention all the other punctuation), because it required many more lines of more repetitive code. In fact the *comments* in the Python code looked more similar to the Scheme code.

    Reply to comment

  33. Posted by Brad Lucier | April 7, 2008, 11:51 pm

    The choices in teaching programming using Scheme are not limited to SICP or HTDP. I prefer the approach by Manis and Little at UBC as developed in “The Schematics of Computation”—I call it “SICP for mortals” because it has the big ideas of SICP but presented in a more manageable way.

    Reply to comment

  34. Posted by Fady Samuel | April 18, 2008, 2:16 am

    I’m a 4th year University of Waterloo Computer Science student but I have great interest in this new curriculum. My sister is planning to start computer science at UW in the Fall. My concern with teaching Scheme in first year without touching Java/C is that it may significantly hurt co-op employment rates. The hottest two languages used by the industry right now are Java and C/C (plus Python to a lesser degree). By completely disregarding the top languages, are you not effectively hurting students’ chances at good co-op positions? Will there still be a Java course in first year for those who prefer that?

    I have nothing against Scheme, I’m all for learning multiple language paradigms, but I’m greatly concerned about co-op employability.

    Reply to comment

  35. Posted by Prabhakar Ragde | April 18, 2008, 9:24 am

    Fady: By coincidence, notification of your post arrived as I was preparing a presentation to co-op coordinators about the changes. Co-op has representation on the curricular bodies at faculty and university levels and has no objections to the new curriculum. Here’s a good recent blog post addressing the general issue:

    http://www.amazon.com/gp/blog/post/PLNK1VEO3LPERI26L

    Note that stream-4 goes away as of this fall, so that all Math/CS students will have experience with C or Python before their first work term.

    Reply to comment

  36. Posted by Tony | April 18, 2008, 9:33 am

    @Fady — I personally doubt that having classes be taught in Scheme will impair students’ co-op employability. I think so because Computer Science classes are about concepts (algorithms, data structures, proofs, math (being a UW student yourself, you should know how much Math goes into the program)), Java was simply a tool used to express some of the ideas, but it was never taught as a language. Really, one should be looking at colleges if they are after a Java-shop.

    A frosh student, having taken no computer science in high school, but having done a term (or even two) of Java based CS classes, is will not be significantly more qualified for co-op jobs, than a student of similar background having spend as much instructional time with Scheme. By the 2nd year, having also seen C and Python, the “lack” of Java will be even less significant.

    To quote Robert, from above in the comments:

    [Scheme] has actually helped me on my co-op interviews … . Interviewers commented on seeing scheme on my resume, and they were pleased with the answers I gave.

    Reply to comment

  37. Posted by Fady Samuel | April 18, 2008, 6:13 pm

    @Prabhakar:

    Ohh I didn’t realize stream 4 no longer exists. That seems reasonable. Does Computer Science at Waterloo still introduce Java to the students at some point? Concepts are very important of course, but so is code. Is there an outline somewhere of all the changes in the first and second year curriculum? Thanks.

    Reply to comment

  38. Posted by Prabhakar Ragde | April 18, 2008, 6:21 pm

    I think this link:

    http://www.cs.uwaterloo.ca/prospect/placement.shtml

    plus the course descriptions linked at the bottom of that page is as close as it gets to a formal description of the changes. The Web pages for the new courses will come on stream at some point (135 and 136 already exist, 145 is under development).

    The natural place to discuss Java is in CS 246, but I don’t know how its instructors will deal with the changes. There is a subcommittee looking at changes to the second-year curriculum.

    Reply to comment

  39. Posted by Andrew Whaley | November 9, 2008, 4:28 pm

    I’m an experienced software engineer in industry and whilst I sympathize with the view that students should learn a ‘commercial’ language like Java, I disagree.

    I work with many Java developers who are reasonably competent in Java but can’t program to save their lives ! They may know the syntax and the API’s but they don’t know the basics like abstract data types and recursion.

    It’s far better that they learn the basics using any language (and Scheme is better than most) before they learn Java – it’s only syntax and API’s and doesn’t take long to learn.

    Besides, who’s to say that Java will still be widely used 5 years from now – I for one think that it’s had it’s day.

    Reply to comment

Post a comment

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>