Class 1: Introduction to Programming Languages

Chapter 1 of Programming Language Pragmatics. The homework is all from Section 1.6, An Overview of Compilation. A lot of that stuff should look pretty familiar from Theory of Computing! The other sections are informal and and very easy to read.


The course
Whether you like it or not, computer science is all about programs! The study of networks only exists because we want programs that communicate over networks; the study of artificial intelligence only exists because we want programs that exhibit intelligent behaviour; and so on. So ultimately, the writing of programs and the languages in which programs are written is a key concern for any computer scientist. Section 1.3 of your textbook, Programming Lanugage Pragmatics, addresses the question: "Why Study Programming Languages?" I encourage you to read it, but in the end I think what I wrote above is pretty compelling. Then again, I wrote it.

Fundamentally, we are going to study how programming languages "work", i.e. how it is that a programmer writes code using high-level constructs far removed from the load and store and logic/arithmetic instructions of assembly languages, and magically this is translated (unambiguously, we hope!) into machine instructions. We rely on this kind of thing every time we write a program, and the theoretical principles behind how this is done shape the structure of all the languages we use.

It's worth taking a look at Wikipedia's list of programming languages. One thing should pop out at you: there are lots of programming languages! (A fun site is 99 Bottles of Beer, a website holds a collection of the Song 99 Bottles of Beer programmed in hundreds of different programming languages.) It's not just Java and C++ out there. Why? What kinds of different ideas are floating around? How do you even talk about differences in languages?

Here are our Course Goals:

Programming paradigms
A programming paradigm is a style of programming, a way of thinking about what a program is. Languages may support or not support various pardigms ... and support them to various degrees. Scheme, for example, strongly supports functional programming, but does not force functional programming, you can "do" object-oriented programming in Scheme, for example, even though it's inherently un-functional. However, most languages have a primary paradigm that they focus on.

The primary (best known) programming paradigms are structured/procedural programming, object-oriented programming, and functional programming. You should understand these three and be able program in some language(s) using all three paradigms. Your into course was all about structured/procedural programming in C++, and you studied object-oriented programming in Java, so in this class you need to study functional programming, and Scheme is the language we'll use for that study.

A vocabulary for programming languages
Here's an excerpt from the first page of the Scheme(5) language definition:
Excerpted from the page 1 summary of "Revised5 Report on the Algorithmic Language Scheme"
The report gives a defining description of the programming language Scheme. Scheme is a statically scoped and properly tail-recursive dialect of the Lisp programming language invented by Guy Lewis Steele Jr. and Gerald Jay Sussman. It was designed to have an exceptionally clear and simple semantics and few different ways to form expressions. A wide variety of programming paradigms, including imperative, functional, and message passing styles, find convenient expression in Scheme.

The introduction offers a brief history of the language and of the report.

The first three chapters present the fundamental ideas of the language and describe the notational conventions used for describing the language and for writing programs in the language.

Chapters 4 and 5 describe the syntax and semantics of expressions, programs, and definitions.

Chapter 6 describes Scheme's built-in procedures, which include all of the language's data manipulation and input/output primitives.

Chapter 7 provides a formal syntax for Scheme written in extended BNF, along with a formal denotational semantics. An example of the use of the language follows the formal syntax and semantics.

I've highlighted nine terms in this short excerpt that you presumably don't know, or don't understand very deeply. If this is the simple summary of a programming language, as a Computer Scientist, you should be able to read it and actually walk away understanding a bit about the language and what it is like. With all those zillions of programming languages out there, you're not going to try even a small fraction of them, so somehow you need to be able to read such summaries and squeeze some appreciation of the language from them. You need this vocabulary to talk about different languages and make decisions about what does or doesn't warrant further investigation. One of our goals is to understand terms like this deeply, so we can read summaries like the above and talk meaningfully about languages.

Properties that define functional languages
The big difference between the functional programming paradigm and the the other pradigms we've seen - structured/procedural and object oriented - is that functional programming seeks to take references to time out of the program. That probably sounds wierd. Time permeates our programs, because any idea of execution order automatically brings time into the picture. When you write
int x = 0;
x = 3;
x = x + 1;
you are stating that "int x = 0" should be performed before "x = 3" which should come before "x = x + 1". Programs like this proceed by evaluating each statement in turn, and each evaluation may have side effects, meaning that the state of the program (roughly the values of its variables) changes. Functional programming tries to remove this dependency on side effects, and to remove these explicit references to time (i.e. ordering of statements). After we get a bit more comfortable with functional programming in a specific language - Scheme is the language we'll use - we'll try to talk about what benefits there are in the functional approach.

Here are the basic properties that define a language as being functional:

Additionally, there are several properties that functional languages traditionally have, mostly because realizing the above properties would be difficult without them.

We often call functional programs "declarative" instead of "imperative". In declarative programming we describe the object to be computed. In imperative we give a sequence of commands - the actions that accomplish the computation. In other words, declarative programming describes the result of the computation, while imperative describes the computation itself.

Christopher W Brown
Last modified: Mon Aug 24 14:27:52 EDT 2009