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:
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.
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.
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:
Why is it desireable? The fact that f(x) - f(x) is not always zero in imperative programs is a source of error for humans, and it limits what can be done automatically with programs. Ex: Optimizing compilers, automatic parallelization
Lack of referential tranparency does interesting things.
For example, suppose S is a stack of numbers with 3 on the
top and 5 second from the top, and suppose you
evaluate the expression "
S.pop() - S.pop()".
What do you think you get? Hard to say! Depends which
pop gets executed first. In C++, for example, this is not
specified, so different compilers could give you different
things. It's not just a question of the ambiguity - after
all C++ could change the rules to fix that the
leftmost operand, for example, gets evaluated first and
there wouldn't be any ambiguity. The point is that
determining the value of a very simple expression becomes
a very subtle exercise.
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.