CM10135 / Programming II:   Lecture 1

Reinventing the Wheel
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.
        1. Let us know after the first coursework if you really are going to need remedial help.
      2. Some people think computer scientists don't program.
  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 second six are by Derek Paddon
  5. Details of first 6 weeks of Programming II content:

Week Starting
 Lecture Topics
Lab Topics

10 February
Intro to programming, data structures, algorithms and sorting.
Lists in different languages.
17 February
Algorithms and complexity. Sorting (Java practice).
24 February
Searching and exceptions.
Coursework 1
2 March
Concurrency & threading.
Coursework 1
9 March
Coursework 2
16 March
Internet Programming.
Coursework 2
23 March -
21 May
Part B
Data structures. Abstract data types and classes (lists, stacks, queues, etc.) Inheritance vs composition. Abstract vs concrete classes. Self-referential classes.
Part B
This is taken from the course web page:
If that's too hard to remember, just write down:  (which you can find from the department pages or Google)
-> teaching -> Programming I

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
        2. C
        3. Lisp, C++
      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 598 different languages
      1. Check out the Common Lisp version using the format command.  (A more normal lisp version is just afterwards.) 
      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. Someone pointed out after lecture that it's 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. How would you write a list in Java?
    1. with the libraries?
    2. from scratch?

page author: Joanna Bryson
10 Feb 2004