it-ebooks - Programming and Programming Languages (Brown Univ)

Version: Saturday, December 31st, 2016 11:25:27pm

Author: Shriram Krishnamurthi, Benjamin S. Lerner, Joe Gibbs Politz

From: Programming and Programming Languages

Many people would regard this as being two books in one. One book isan introduction to programming , teaching you basic concepts oforganizing data and the programs that operate over them, ending in theinvestigation of universally useful algorithms. The other book isan introduction to programming languages : a study, from onelevel up, of the media by which we structure these data and programs.

Obviously, these are not unrelated topics. We learn programmingthrough one or more languages, and the programs we write then becomenatural subjects of study to understand languages atlarge. Nevertheless, these are considered sufficiently differenttopics that they are approached separately. This is how we approachedthem, too. The one noble exception to this separation isthe best computer science book ever written, The Structure andInterpretation of Computer Programs .

We have come to realize that this separation is neither meaningful norhelpful. The topics are deeply intertwined and, by accepting thatinterleaving, the result is likely to be a much better book. This ismy experiment with that format.

There are many ways to organize the study of programming andprogramming languages. My central theme is the concept of predictability .

Programs are typically static: they live on the moral equivalent of apaper, unmoving and unchanging. But when we run a program, it producesa complex, dynamic behavior that yields utility, pleasure, and(sometimes) frustration. Everyone who writes programs ultimatelycareswhether they realize it or notin predicting thelatter from the former. Sometimes we even write programs to help uswith this task (as well see in , and elsewhere).

Predictability has a bad rap. Under the guise of programreasoning, it came to be viewed simultaneously as both noble andmind-numbingly boring. It is certainly noble, but we will try topresent it a way that will hopefully seem utterly natural, indeedentirely obvious (because we believe it is). Hopefully youll come awayfrom this study reasonably convinced about the central place ofpredictability in your own work, and as a metric for programminglanguage design.

Unlike some other textbooks, this one does not follow a top-downnarrative. Rather it has the flow of a conversation, withbacktracking. We will often build up programs incrementally, just asa pair of programmers would. We will include mistakes, not because wedont know better, but because this is the best way for youto learn . Including mistakes makes it impossible for you to readpassively: you must instead engage with the material, because you cannever be sure of the veracity of what youre reading.

At the end, youll always get to the right answer. However, thisnon-linear path is more frustrating in the short term (you will oftenbe tempted to say, Just tell me the answer, already!), and itmakes the book a poor reference guide (you cant open up to a randompage and be sure what it says is correct). However, that feeling offrustration is the sensation of learning. We dont know of a wayaround it.

At various points you will encounter this:

Exercise

This is an exercise. Do try it.

This is a traditional textbook exercise. Its something you need todo on your own. If youre using this book as part of a course, thismay very well have been assigned as homework. In contrast, you willalso find exercise-like questions that look like this:

Do Now!

Theres an activity here! Do you see it?

When you get to one of these, stop . Read, think, and formulatean answer before you proceed. You must do this because this isactually an exercise , but the answer is already in thebookmost often in the text immediately following (i.e., in the partyoure reading right now)or is something you can determine foryourself by running a program. If you just read on, youll see theanswer without having thought about it (or not see it at all, if theinstructions are to run a program), so you will get to neither (a)test your knowledge, nor (b) improve your intuitions. In other words,these are additional, explicit attempts to encourage active learning.Ultimately, however, we can only encourage it; its up to you topractice it.

This book uses a new programming language calledPyret.Pyret is the outgrowth of our deep experience programming in anddesigning functional, object-oriented, and scripting languages, aswell as their type systems, program analyses, and developmentenvironments.

The languages syntax is inspired by Python. UnlikePython, Pyret will enforce indentation rather than interpret it: thatis, indentation will simply become another syntax well-formednesscriterion. But that hasnt been implemented yet. It fits the niche missing in computer science education of a simple language that sheds both the strange corner-cases (of which there are many) of Python while adding important features that Python lacks for learning programming (such as algebraic datatypes, optional annotations on variables, design decisions that better enable the construction of development environments, and strong support for testing). Beginning programmers can rest in the knowledge they are being cared for, while programmers with past acquaintance of the language menagerie, from serpents to dromedaries, should find Pyret familiar and comfortable.

Lets think about some of the programs we use. We might use Google, asearch engine: it consumes a search query and produces asearch results. We may use Facebook, a social network: it consumes information about our friendships and produces updates from our friends. We could use Amazon, a store: it consumes descriptions of things were interested in and produces lists of products that match our descriptions. Wesometimes use Weather.com, a weather site: it consumes ourlocation and produces a weather forecast for that location. Infact these systems consume and produce even more: they consume ourhistory of past preferences, and produce ads, recommendations forrelated products [REF collaborative filtering], and so on. In short, programs consume andproduce information .

Therefore, to write programs, we have to understand their data. Wewill begin by understand the most basic kinds of data, and writingsome simple programs with them. As our programs get moresophisticated, we will need to represent more interesting kinds ofinformation. Much of our presentation is directly derivedfrom the book How to Design Programs , which you can findat http://htdp.org/ .