Composing Programs – Python 3 in the tradition of SICP
composingprograms.com
composingprograms.com
Previous Hacker News Discussions:
https://news.ycombinator.com/item?id=3491142
https://news.ycombinator.com/item?id=3141996
Full disclosure: I'm a TA for the course right now.
Teaching SICP in Python is just a further development of that trend.
Software engineering is a very trend-following, path of least resistance, bandwagon-jumping profession. If "everyone" is using language X, that's where most engineers (and managers) want to be. Universities are just satisfying that need.
It's a wonder that Scheme lasted in universities as long as it did. It'll be interesting to see how long Python lasts.
http://www.joelonsoftware.com/articles/ThePerilsofJavaSchool...
Python is 25 years old.
Remember, all of those "old" languages, when they became notable or influential, were younger than Python is now.
Scheme, when SICP was written, was only 15 years old. It was young and trendy at the time.
C was less than 20 years old when I learned is as part of a required course for my CS degree. I've no doubt that part of the reason was that it was widely used in industry.
C++ was the trendy thing by the time I left school. It was less than 10 years old.
Perl was 10-15 years old when it was used as the "Swiss Army chainsaw" for a lot of the first era of web development.
While this appears to solidify your observation that software engineering is very trend-following, I listed them to point out that Python seems to be the oldest language when it made the jump. It's surely older than most of the students and even TAs for the course.
You won't see a CS course taught in Go or Rust anytime soon.
def make_adder(n):
def f(a):
return n + a
return f
"About 12 years ago, Python aquired lambda, reduce(), filter() and map(), courtesy of (I believe) a Lisp hacker who missed them and submitted working patches. But, despite of the PR value, I think these features should be cut from Python 3000."
If my understanding is flawed, I'd like it to be corrected, though.
You can't have anonymous lambdas that aren't first class (how would you reference them?) but you can have first class functions that are not technically anonymous.
I suppose I wasn't aware that that wasn't a universal requirement, but count me in with that group. I think it's useful to make a distinction between "higher-order" and "first-class" for this very reason (i.e., we can talk about languages that do make a distinction without resorting to overloaded terms).
I mean, consider a language where this is the case:
> "hello," .. " world"
==> "hello, world"
> 2 + 2
==> SYNTAX ERROR
> def a = 2
==> #<number "a">
> a + a
==> 4
Sort of on a tangent, but while I'm reminded of it: as far as Python's "lambdas" go, they're brutally gimped compared to Python's notion of a function, since what is allowed (and even required) of a function body in Python is much different than what is allowed of a "lambda" body.
Yes, I still would, because integers can be bound to variables, passed to and returned from functions, and stored in fields of objects.
I would think that the language had a silly syntactic restriction -- which is the same thing I think about Python -- but it wouldn't materially change how I would write programs. It's just that, before any expression using an integer literal, I would have to name the literal.
Well, same here. If you want to use a function too complicated to fit in Python's restricted lambda expression syntax, you have to use a named local function. I agree that it's silly, and I'd never design a language like that myself, but again it wouldn't materially change how I write programs -- it just means that what would have fit in one expression would now, in some cases, require multiple statements.
Trying to draw a fine distinction between "higher-order" and "supporting first-class functions" doesn't appeal to me; I think of the latter as the definition of the former. (I'm sure I would have trouble remembering which was supposed to be which.)
But again, I have no problem with criticizing the design decision -- just not using these terms :-)
I could see saying something like, Python functions are semantically first-class but syntactically second-class. Or maybe we should just call them "business-class" :-)
(BTW your comment downthread about referential transparency is spot-on.)
And I also see (now) where you're coming from. But it's hard for me to accept the "once the value has been created" exception, because in my mind the construction of a value is as important as any other operation on that value.
Anyway, I'm not going to argue this any further -- I think we understand each other's perspective and we can pretty much resolve to chalk this one up to the (rather unfortunate, imo) lack of precision that's so common to terminology in computation science (see also: any debate whatsoever about types ;) ).
I'm a seasoned programmer, who after years in the industry really enjoyed SICP once I discovered it. I found it very nicely put together in the sense that it managed to teach a simple LISP and handle programming in a deeper and more academical/sciency way, and not just the regular "here's how you make a blog with whateverDB".
I'm currently looking into expanding my very basic Python knowledge, and are looking for books/courses on the subject.
Would you say this course here is good for learning Python, or would you rather recommend something else to experienced programmers?
Archive.org Mirror: http://web.archive.org/web/20160402152716/http://www.composi...
The exercises and demonstrations in each section quickly build from an elementary introduction up to powerful examples accompanied by clear explanations. I especially like the explanatory diagrams.
Thank you to the authors for your craftsmanship and for making it available on-line.
Yes. The autograder is provided with each assignment.
- Dijkstra, 1972
My opinion isn’t pie-in-the-sky theorizing: I know plenty of intelligent people whose first exposure to programming was Scheme, which scared them off into thinking that “they’re not smart enough for programming” or some bullshit like that. When they later tried a language like Python, they weren’t scared off—they were hooked.
The whole argument in favor of using Scheme as an introduction to programming seems highly ideological, and not at all informed by how people actually learn how to program. The fact that so many online resources successfully (Codecademy, Coursera, etc.) introduce people to programming using high-level languages is evidence that it works.
[1]: I know that all abstractions are leaky, but in the context of an introductory class, they’re not leaky enough.
Completely agreed
> anyone can understand all in one sitting
Goodness gracious, no. At least it sure wasn't as of the last time I TA'd a class that was taught using it (admittedly during the previous millennium). In a typical group, approaching half the students - smart students, this was a fairly selective school - dropped or failed. A huge chunk foundered on figuring out how to do useful things with lists (cons/car/cdr and friends are elegant, but they are also weird). Another huge chunk struggled with let/let*/letrec. And closures weren't very fun for many students, either.
The one neat thing I've noticed about Scheme is that, if you get Scheme, then you will have a very solid grasp of how to compose abstractions. I wouldn't be too quick to infer a causal link there, though. It might be that Scheme makes people better at CS. It could just as easily (given those failure rates, possibly more easily) be that Scheme is a filter for identifying people who have a pre-existing knack for the academic side of CS.
Of course, once side-effects are introduced, that substitution model breaks down, and a new one must be picked up. But by then, the students ought to have become reasonably comfortable with the ideas of programming.
I often hear smug Lisp weenies bragging about how simple the syntax is , which allows instructors to spend little time on syntactic rules and get at the meat of programming. But I'd argue that the simplicity of the semantics in the absence of side-effects is even more important. Any student with an eighth-grade[1] understanding of elementary algebra will be able to understand program evaluation quickly and easily.
As to why Lisp specifically when any referentially transparent language or sublanguage thereof could provide the benefits of the substitution model just as well: try implementing a complete and fully-functional metacircular interpreter in something other than Lisp, as a literate program, in under 40 pages. Now do it again for a lazy version, a nondeterministic version, and a relational (a.k.a. logical, as in logic programming, e.g. Prolog) version. Some argue that a metacircular evaluator really has no business being part of an introductory course, but in my experience it's actually a good way to finally formalize the actual model of evaluation, while at the same time demonstrating that interpreters, compilers, etc. aren't magic black boxes, but actually relatively simple programs (though when I teach the material I like to point out that they can get pretty complex, depending on source/object languages and optimization... let that be a lesson to them!).
[1]: This is the name for the educational status of typical twelve-to-thirteen-year-old students in the US.
Granted, it would be unusual to see all, or even most, of those in one place, but they see use enough that calling python bad a functional programming is a little odd. I'd say it's pretty good at functional work in the small while somewhat ill suited in the large.
There's a much better discussion over here
http://stackoverflow.com/questions/1017621/why-isnt-python-v...
If you define "functional style" as writing Lisp or Haskell programs using Python syntax, I agree they look horrendous.
Here's my favored source (in the Standard Library) https://docs.python.org/2/library/collections.html#collectio...
> and what do you do when every third party library you interact with uses mutable ones?
That's situational; which library are you having a problem with? I haven't really had that problem (okay, sometimes the tooling around web frameworks do stupid things, but that's not common).
Note that just because something is mutable doesn't mean you have to mutate it. Yes, Python doesn't as widely enforce non-mutation as Haskell, OCaml, etc., but that doesn't mean that suddenly all the Python programmers lost their minds and started mutating all the things. We're not savages.
I agree, and I don't mutate it, but my third party libraries and my collegues functions will. Not all of them, but enough to introduce annoying bugs.
You've claimed that third party libraries and your colleague's functions will mutate the data structures you pass them, but this has very rarely been my experience.
[EDIT: I shouldn't impugn my coworkers: I had trouble resisting the siren call of side effecting functions!]
Sadly I've seen functional operations like map/filter/reduce etc discouraged in (commercial) projects I've worked on, though I guess there's a bit of an argument there for debugability (make it a word?) since hunting down side effects may be more onerous?
[fn(a) for a in seq]
[a for a in seq if pred(a)]
map(fn, seq)
filter(pred, seq)
Comprehensions don't help at all with reduce, of course, which has been tidied out of __builtins__ now.
Are map and filter more concise? Yeah but only in this case. If you would need to do some processing, they would get messy fast because of a lambda.
On the second point. I agree. Python's lambdas are a code-smell, for me. Which I don't say lightly, I'm a Scheme/Lisp guy deep down. But they fundamentally work against the aesthetics of the Python language, imho. A local function declaration is much less fragile.
But I would say that as code complexity increases, in my experience, comprehensions don't last long either. They've a narrow range of applicability before you get a big block of spaghetti code. Then it is much better to define a local function and, essentially, 'map' it (even if that 'map' is done as comprehension). Of course, YMMV.
>> x = 5
>> [x for x in range(10)]
>> x # => 9 Python 2.7.10 ...
>>> a = 3
>>> [a for a in range(10)]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> a
9
>>> a = 3
>>> list(a for a in range(10))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> a
3
(defmacro dict-comp
[bindings & body]
`(into {} (for ~bindings (do ~@body))))[0]: http://python-history.blogspot.hu/2009/04/origins-of-pythons...
[1]: https://docs.python.org/3.2/library/functools.html#functools...
I've written tens of thousands of lines of code in a functional style in Python, and while it's different from Scheme and takes a little getting used to, Python is a very capable programming language for functional programming.
It does lack tail call optimization, but I think you'd find that even in Scheme, most times where you would write a recursive function, you should be writing something with one of the higher-order functions. 99.9% of recursive functions contain a buggy hand-rolled implementation of map, reduce, or filter. Scheme is a more academic language, so it makes sense for them to include this feature, which gives language users the same power as the language creators. But Python is intended for professional development and as such, it makes sense to force users into a better style.
[1] http://learnyousomeerlang.com/recursion [2] http://www.fastcompany.com/3026758/inside-erlang-the-rare-pr...
From your sarcastic tone it seems like you take issue with something you think I've said, but since your post is unrelated to anything I actually said, I can only guess that you've inferred some meaning that isn't there.
Sometimes, it's just the clearer way to get the job done. I realize it is these days considered "un-Pythonic" to consider there to be more than one way to do something, but that is in fact one of the reasons why I no longer use Python. The attitude of its creator and its community have shifted against creative solutions and I have no use for that attitude in a technology field.
> The point is, the idea that it's somehow "unprofessional" to write a recursive function is an absurd assertion.
...which is why I didn't say that. What I said was, "[E]ven in Scheme, most times where you would write a recursive function, you should be writing something with one of the higher-order functions. 99.9% of recursive functions contain a buggy hand-rolled implementation of map, reduce, or filter."
There are certainly cases where writing a recursive function is cleaner, and I would never say it's "unprofessional" to write a recursive function. However, I've debugged enough Scheme to know that if you're writing a recursive function you're probably reimplementing one of the core higher-order functions, and in doing so you're increasing your chance of bugs. You're also making your code less composable. If you're not experience enough with Scheme to have recognized this fact yet, you're probably not experienced enough to recognize exceptions to the rule.
> Many, many functional languages beyond just "academic" ones use recursion as a standard idiom, and using that to dismiss Scheme is itself an inflammatory statement especially on a site that is literally running on top of a Scheme derivative.
Scheme is my favored language for personal projects. I write more Python because there's more work available for Python, but when it has been my choice I've chosen Scheme. The reason I've written so much Python in a functional style was because I learned that style from Scheme. So if you think I'm dismissing Scheme, you're hilariously wrong. My statement isn't inflammatory; you became inflamed all on your own.
> I realize it is these days considered "un-Pythonic" to consider there to be more than one way to do something, but that is in fact one of the reasons why I no longer use Python. The attitude of its creator and its community have shifted against creative solutions and I have no use for that attitude in a technology field.
Cool. I thought I was the one being inflammatory.
It seems that you saw me say, "Scheme is a more academic language" and decided to take offense to that. Well, news flash, Scheme was designed at the MIT AI Lab. It's an academic language. That doesn't mean it's a "toy language" or that it's only an academic language; I didn't say either of those things. It's also ridiculous that you needed to bring Erlang into the conversation to defend Scheme: Scheme has plenty of history of professional use at both HP and Sun and is perfectly well respected in its own right.
Please try to learn something from this experience.
reduce = 0
Nevertheless I still maintain that the classic CS61a by Prof. Brian Harvey is a gold standard. It teaches the most important big ideas, such that code is data and hence the whole OO paradigm is mere a DSL over structured data with named slots, with a protocol to follow (inheritance).
It teaches the superiority of declarative over imperative approach - one defines what shall be done, not how it can be done.
It also teaches lazy evaluation, so one doesn't parrot nonsense about monads and Haskell.
It teaches what genetics are, and that everything could be defined as an ADT with corresponding predicates (which represents mental categories we learn from environment).
Mr. Harvey is a gentle intellectual with charm and that characteristic lack of arrogance and tendencies to show off modern narcissistic personages exhibit nowadays.
I can't stand guys like Hickey or Tellman or whoever it is.
Watch him, at least first 3 or 4 lectures.
This is correct one - CS61A 2008.
https://www.youtube.com/watch?v=zmYqShvVDh4&list=PL6879A8466...
Too much garbage on youtube. I am so sorry.