CM10135 / Programming II:   Lecture 1

Reinventing the Wheel
or
Looking under the Hood
[Brit. Bonnet]

I.  What is this unit about?

1. CM10135 is Programming II, not Java II.
   
2. Programming I was about how ordinary programmers program.
3. Those of you in Programming II are not just ordinary programmers.  You are Computer Scientists.
1. Someone needs to know how things really work so they can be fixed.
2. Someone needs to invent the new big ideas!
3. Some of you may think you aren't good enough programmers to be computer scientists.
1. Don't panic.
1. Keep trying.  Practice!!  It takes time to learn new ways to think.
   
2. Let us know after the first coursework if you really are going to need remedial help.
3. Friday tutorials
4. newbies forum
   
2. Some people think computer scientists don't program.
4. Some of you are bored --- don't worry, it gets more interesting.
1. hackers forum
   
4. Broad categories for Programming II content:
1. Most lecture topics are about Computer Science --- understanding how the programs really work.
2. The coursework will help you learn these concepts, but more importantly will give you more practice programming.
3. There are several weeks of topics which are also more commercial skills, as well as CS concepts.
1. GUIs
2. Applets
3. Internet Programming
4. First 6 weeks are lectured by me (Dr. Joanna Bryson), the last four are by Derek Paddon
   
5. Details of first 6 weeks of Programming II content:

II.  What is the difference between Programming and Java?

1. There are many different programming languages, but there are some common principles that underly all of them, and others that are shared by most of them.
1. All languages:
   
1. Run on physical computers.
2. Take time.
3. Take space in memory.
4. Run algorithms.
   
2. Understanding how much time & space a program takes, and how to make it take less time & space, is known as understanding the complexity of a program. 
   
1. Determines what is computable.
2. Primary topic of the Theory of Computation.
3. Example:  The Church-Turing Thesis
1. Church-Turing thesis says any algorithm can be run on a Turing Machine.
2. Every computer you've met is Turing equivalent.
3. Every language you will learn is Turing complete.
   
4. But this is all less exciting than it seems when you realize an algorithm is now defined as anything that can run on a Turing machine.
1. Is there any other kind of computation?
2. Is the human brain a Turing machine?
3. These are open questions!  (See this page for a description of the evidence for Church-Turing.)
   
4. But not the topic of this course.
5. An open question is one still being actively researched.  Intelligent, well educated experts in a field hold opposing views with each other.
   
3. Differences between languages (just a few!):
1. Compiled vs. interpreted.
1. Java, C, C++
2. Lisp, smalltalk, prolog
   
3. NB: Can write Java, C interpreters if you want to.
   
2. Strictly typed or not.
1. Java, C, C++
2. Lisp, python, perl
   
3. Object oriented or not or sort of.
1. Java, smalltalk, python
2. C
3. Lisp, C++, perl
   
4. High-level vs. low vs. in between
   
1. Python, PHP, SQL.
2. C, assembler
3. Java
   
5. Dynamic or not or maybe -- can write & evaluate new code on the fly (while running).
   
1. Lisp, python, perl, smalltalk.
2. C, C++
3. Java? (Introspection, Reflection)
   
4. The fact Java comes sort of in between on a couple of these lists is part of what makes it obscure / not the best teaching language.
1. So don't feel bad when things seem confusing.
   
2. Also what makes it an excellent (& dominant) programming language for real work.
   
3. In tutorial this week you'll be able to play with Lisp, which may make Java seem clearer.
5. Why have different languages?
1. Because they make different tasks easier to program.
2. Usually a tradeoff between run-time speed & programming speed.
3. Help you think in different ways. 
   
1. I enjoy translating my best programs/ideas between languages to understand them better.
6. Here is the page I mentioned in lecture, 99 Bottles of Beer, currently in 1057 different languages
1. Check out the Common Lisp version using the format command.  (That's from the page, but they've currently messed up the formatting there. There is also a more normal lisp version available on the page.) 
2.  It works in lispworks, but not euscheme (see this week's lab for an explanation of the difference.)

III.  Thinking About Memory

1. Arrays of basic types are chunks of adjacent memory.
2. Arrays of objects are adjacent references, which point to memory allocated elsewhere.
3. A list is a bunch of simple elements arranged in a chain.
1. Each element has a reference to its contents, and a reference to the next element.
2. The last element sets its "next" reference to null.
4. In the old days, you used an array when you knew how much memory you needed, because they were faster, and lists when you didn't, because you could easily make them longer.
1. Arrays also let you index any element quickly (via arithmetic) instead of by reading lots of memory cells.
1. Arithmetic:  address you want = address of first element + (index * size-of-element).
   
2. But lists let you do more elaborate things, like for example making the last element point at the first & make a loop.
   
5. Now that computers are faster, languages like Java let you change the length of arrays
   
1. extending an array is still a slowish operation, but you might not care...
   
2. or you might extend the array much less often than you index into its memory, so it's still faster over all than a list.
6. It is also easier to insert new things in the middle of lists.
1. All the same arguments apply as in the previous point.
2. Copying arrays sections (to move them back & make space for the new stuff) is usually a fairly fast operation, not much worse than reallocating the new memory in the first place.  Still slow enough that you don't want to do it as often as you reference the memory.
   
7. Quick intro to lists in lisp
1. cons pairs:
   
1. the first reference is called "first" (or sometimes "car"), points to a value
   
2. the second part is called "rest" (or sometimes "cdr"), points at the rest of the list.
3. You construct a list by consing something onto the front of an existing list
1. you start with the empty list.
2. Null (called nil in lisp) is a basic type / object and is exactly equivalent to the empty list.
2. See this week's tutorial for more details.
8. Exercises for later: how would you write a list in Java?
   
1. with the libraries?
2. from scratch?