Best way to contact prof is by email.

Office hours 4-6, or by appointment.

Recitation will be working through examples, going more deeply into some material, and going over practical info like setting up dev environments.

No required textbooks. But plenty of online resources.

But primary reference is lectures. Write down everything that’s on the board.

4 programming assignments in 4 (5?) different programming languages. Count for 40% of grade. Exam is other 40%, midterm is 20%.

Not allowed to work together on the assignments. Programs are run through plagiarism detectors.

Syllabus is on NYU classes. It gives topics, not readings.

Prof encourages interactivity in the class.

On to course material

What is a programming language?

Scratch that, what is a language in general?

• A set of strings (sequences of symbols).

  • English, for example, is the set of all strings of characters that are considered legal English (i.e. grammatically correct).

• These strings have meaning.

What makes a language a programming language?

• These strings must be unambiguous, and have exactly one meaning.

• Must be implementable on a computer.

  • There are things that you can say in human language that isn’t implementable in a programming language. For example, “Prove Fermat’s last theorem.”

• The language must be Turing complete.

  • Not every computer language is a programming language. For example, the DOS shell is a computer language. But you couldn’t write an arbitrarily powerful program in DOS shell language. (Is he right? Is DOS shell not Turing complete?)

Turing completeness

Any computable function can be expressed in the language.

Any function that is computable can be computed by any Turing-complete language.

Who discovered it?

There were three logicians working on problems related to this issue. They were looking at it from the perspective of human beings computing functions with pen and paper.

Gödel came up with the idea of general recursive functions. Any computable function is part of this set.

Alan Turing came up with a formal model of computation called the Turing machine.

Alonzo Church came up with a different model called the Lambda Calculus, based on the manipulation of symbols.

These were later proven to be all equivalent in expressiveness. There was nothing you could express in one of these models that you couldn’t express in any other.

The Church-Turing thesis

Any computable function (computable by paper and pen given an arbitrary amount of time) can be computed by any Turing machine.

Turing machines

Suppose you have a machine with an infinitely long tape (magnetic or paper). This tape is broken up into cells, which can each contain a symbol. The tape has an initial state, which is a finite number of symbols stored in the tape. The machine has a tape head that can read or write to a cell on the tape.

 -----------------------------------
| | | | | | |a|b|c|4|?| | | | | | | ...
 -----------------------------------
                 ^
               _|_|_
              |S1…Sn|

Then you have a set of states \(S_n\) in the machine itself. One of these states is the terminating or stop state.

The machine also has a transition function that:

1. Reads the current cell and current state,
2. Writes a symbol to the cell,
3. Moves the head left or right by one cell, and
4. Changes the machine to a new state.

Transition(current_cell, current_state) -> (new_cell_contents, next_movement, next_state)

This machine is equivalent to any one of these other formalisms.

In this class, we’re going to be using the Lambda Calculus mainly, because it’s much more programming-language-like.

A language is Turing Complete if it is equivalent in expressiveness to a Universal Turing Machine.

A Universal Turing Machine is a Turing Machine that, given any other Turing Machine \(M\) and input \(I\), can produce the same output as \(M\) operating on \(I\).

• I.e. a Universal TM can “emulate” any other TM.

Back to programming languages

All programming languages are equivalent in their computational power, because they’re all Turing-complete. So what makes one PL more desirable than another?

Readability

How easy is it to read programs that have already been written? This is very important for debugging and understanding other people’s code.

Think of APL (with its crazy greek letters). It’s a very powerful programming language, but unless you’re using very well-known idioms, it’s extremely difficult to read.

Access to the hardware

Is this a good thing or bad thing? It depends what you need and what you’re using it for, whether you need that low-level access.

Conciseness

It’s good to write powerful programs in a relatively small amount of code.

Mathematical foundation

In other words, being able to prove things about your program, like that it won’t have memory leaks or that it will terminate. If you don’t have a solid mathematical foundation, you can’t prove anything about your program. More important in the academic world.

High-level vs. low-level programming languages

What’s the difference? Low-level languages reflect the underlying machine (i.e. the hardware). High-level languages abstract away those details.

For example, in a low-level language:

• Variables are memory locations. Ex. x = x+1 means, “Load the value at the memory location for x, add 1 to it, then save it back into the memory location for x.”

• Your flow of control may be loops or jumps.

• And so on.

High-level languages don’t reflect the underlying hardware, but have some other computing model. For example, it could mean variables don’t represent memory locations. Think languages like Prolog, where variables mean something different.

Let’s look at two pieces of code that do the same thing, one in C and one in ML:

C

p = 1
for (i=1; i <= n; i++)
	p = p*i;

This forces you to think like the machine does and tell it exactly what steps to follow. It takes a while to understand it’s computing the factorial.

ML

ML is based on mathematics, so you can’t write something like x = x+1 or p = p*i. So how would you write it in math? Probably like this:

So in ML:

fun fac 0 = 1
  | fac n = n*fac(n-1)

Implementing programming languages

There are generally two ways of doing this.

Interpreters

Understand the source language (in which your program is written) itself and can execute the source code directly.

Compilers

Translates the source language into another language, which is then executed. Often machine code or assembly, but doesn’t have to be. (Think of Java, which translates into JVM bytecode, or the myriad languages that compile to bytecode.)

You can have an interpreter without a compiler, it just runs the code. But can you have a compiler without an interpreter? Probably not, at very least it has to be “interpreted” by the hardware.

How do you specify a programming languages?

This is going to come up in recitation.

What do you need?

Syntax

The rules that govern the organization of symbols in a program. Such as:

• The rules that govern a sequence of symbols to form a word, and
• The rules that govern a sequence of words that can form valid phrases.

In short, a set of rules that defines the valid strings.

Semantics

A set of rules that tell what these sequences of symbols should do. They give meaning to the valid sequences of symbols.

That’s it.

That’s all you need to define. You can give more stuff to clarify, but the syntax and semantics are sufficient to define a language.

Let’s look at syntax right now and in the recitation.

Syntax in detail

How do you specify which strings are valid in a programming language? You can’t enumerate all strings (because in any Turing-complete language they’re going to be infinite), so you need a shorthand. This shorthand will be the grammar of the language.

For defining words, that is, keywords, names, and numbers, you can use regular expressions.

For defining phrases, that is, expressions, statements, procedures, loops, etc. you need a context-free grammar.

Regular expressions

Given an alphabet, a regular expression defines a set of strings from that alphabet.

Suppose the alphabet is \({a, b}\).

Context-free grammars next week and in recitation.