CPT204 lecture note

lecture的简单笔记记录

Lecture 1

Basic Java Review, Checking 1, Testing 1

Types

A type is a set of values, along with operations that can be performed on those values 类型是一组值，以及可以对这些值执行的操作
Java has 8 primitive types 8种原始类型
boolean, byte, char, long, short, int, float, double
Java has 2 object types 2种对象类型
String, BigInteger

Operations

Operations are functions that take input values and produce output values 操作符是接受输入值并产生输出值的函数
There’re three different synataxes for an operation in Java:

• as an infix, prefix, or postfix operator 作为中缀、前缀或后缀操作符 (a + b)
• as a method of an object 作为对象的方法 (bigint1.add(bigint2))
• as a function 作为函数 (Math.sin(x))

Some operations are overloaded, same operation name is used for different types 有些操作是重载的，不同类型使用相同的操作名
e.g., arithmetic operators +, -, *, / are overloaded for numeric primitive types

Static Typing

Java is a statically-typed language. The types of all variables have to be known at compile time (before the program runs), and the compiler can therefore deduce the types of all expressions as well. For example, if a and b are declared as ints, then the compiler concludes that a+b is also an int. In fact, you will shortly see in our lab, IntelliJ environment does this while you’re still typing your code! Java是一种静态类型的语言。所有变量的类型必须在编译时(在程序运行之前)就知道，因此编译器也可以推断出所有表达式的类型。例如，如果a和b被声明为int型，那么编译器就会得出a+b也是int型。事实上，你很快就会在我们的实验室里看到，IntelliJ环境在你输入代码的时候就能做到这一点!
In dynamically-typed languages like Python or Javascript, this kind of checking is deferred until runtime (while the program is running) 在动态类型语言如Python或Javascript中，这种检查被推迟到运行时(即程序运行时)

Static Checking

Static typing is a particular kind of static checking, which means checking for bugs at compile time. 静态类型是一种特殊类型的静态检查，这意味着在编译时检查bug
例如输入"5" * "6"，静态输入会在你coding的时候就捕捉到错误，而不是到这一行被运行的时候再捕捉错误。

Lecture 2

Checking 2, Testing 2, Immutability, List, Map

Checking

Three kinds of automatic checking that a language can provide:

1. static checking: the bug is found automatically before the program even runs 静态：程序开始前就被捕捉
2. dynamic checking: the bug is found automatically when the code is executed 动态：程序开始运行才被捕捉
3. no checking: the language doesn’t help you find the error at all. U have to watch for it yourself, or end up with wrong answers. no checking：程序不会帮忙捕捉，需要自己检查出来，但是不捕捉会产生错误结果。

不用说，静态地捕获bug比动态地捕获要好，而动态地捕获总比根本不捕获要好!

Static Checking

static checking can catch:

• syntax errors, like extra punctuation or spurious words 语法错误，比如多余的标点符号或虚假的单词
• wrong names, Math.sine(2) (the right name is sin) 名字错了
• wrong number of arguments, Math.sin(30,20) 参数的数量错了
• wrong argument types, Math.sin(“30”) 参数的数据类型错了
• wrong return types, return “30”; from a function that’s declared to return an int 返回量的数据类型错了，应该返回int却返回了str

Dynamic Checking

dynamic checking can catch:

• illegal argument values, for example, the integer expression x/y is only erroneous when y is actually zero 非法的实参值，例如，整数表达式x/y只有在y实际为零时才会出错;否则工作!所以在这个表达式中，被零除不是一个静态错误，而是一个动态错误
• unpresentable return values, when the specific return value can’t be represented in the type 不可表示的返回值，当特定的返回值不能在类型中表示时
• out-of-range index, using a negative or too-large index on a string 超出范围的索引，在字符串上使用负或过大的索引
• calling a method on a null object reference 调用空对象的方法

No Checking

One trap in Java — and many other programming languages — is that its primitive numeric types have corner cases that do not behave like the integers and real numbers we’re used to.
As a result, some errors that really should be dynamically checked are not checked at all!
Java(以及许多其他编程语言)中的一个陷阱是，其原始数字类型有一些不像我们所习惯的整数和实数那样的情况。
因此，一些真正应该动态检查的错误根本没有被检查!

1. Integer division, for example, 5/2 should equals 2.5 however the result is 2.
2. Integer overflow, for example, 就是整数太大了或者太小了超过int的范围。
3. special values in floating-point types: Floating-point types like double types have several special values that aren’t real numbers: NaN (which stands for “Not a Number”), POSITIVE_INFINITY, and NEGATIVE_INFINITY. When you apply certain operations to a double that you’d expect to produce dynamic errors, like dividing by zero or taking the square root of a negative number, you will get one of these special values instead. 以下代码块的结果应该是no checking

   double a = 7;
   double b = 0;
   double div = a/b; 

Two goals

1. communicating with the computer
2. communicating with other people

Snapshot Diagrams

Snapshot diagrams represent the internal state of a program at runtime – its stack (methods in progress and their local variables) and its heap (objects that currently exist) 快照图表示程序在运行时的内部状态——它的堆栈(正在进行的方法及其局部变量)和它的堆(当前存在的对象)

Primitive Values

原始值代表了bare constants，例如n = 5，这种情况直接用一个单箭头来表示赋值，就是字母n箭头指向5（n –> 5）

Object Values

An object value is a circle labeled by its type. 对象就是箭头指向圈。

Reassigning Variables vs Mutating Values

1. When you assign to a variable, you’re changing where the variable’s arrow points – you can point it to a different value 当你给一个变量赋值时，你改变了变量的箭头指向——你可以给它指向一个不同的值
   
2. When you change the contents of a mutable value – such as an array or list – you’re changing references inside that value, this is called mutating the value 当你改变一个可变值的内容时——比如一个数组或列表——你改变了那个值内部的引用，这叫做改变值
   

string is an example of an immutable value

这种不可变的type，在画图时使用两个圈表示，注意看上图的string。

Mutable Values

StringBuilder is a mutable value that represents a string of characters StringBuilder是可以修改的

Immutable References

final int n = 5; 有final的说明是Immutable，这里的箭头用双线箭头表示

Pay attention not to confuse reference versus value, when we talk about mutability versus immutability 注意区别

• Notice that we can have an immutable reference to a mutable value (for example: final StringBuilder sb) whose value can change even though we’re always pointing to the same object
• We can also have a mutable reference to an immutable value (for example: String s), where the value of the variable can change because it can be re-pointed to a different object

Lecture 3

Coding Rules, Testing 3, Recursion
There are sensible coding rules that help us to write good code: making it safe from bugs, easy to understand, and ready for change:

• Don’t Repeat Yourself (DRY)
• Comments where needed
• Fail fast
• Avoid magic numbers
• One purpose for each variable
• Use good names
• Don’t use global variables
• Return results, don’t print them
• Use whitespace for readability

Testing

Divide the input space into subdomains, each consisting of a set of inputs
其中每个subdomains包含相似的输入，这些输入在函数内会有相似的输出
然后对不同参数的subdomains进行排列组合

Lecture 4

Testing 4, Linked List 1

Testing

• Black-box vs White-box Testing
• Unit vs Integration Testing
• Automated Regression Testing
• Testing Documents and Coverage

Blackbox&Whitebox

Black box testing means choosing test cases only from the specification, not the implementation of the method 黑盒测试意味着只从规范中选择测试用例，而不是方法的实现
就是我不需要知道功能是怎么实现的，只需要测试功能能不能正常使用，假如不能正常使用就告诉开发，约等于功能测试。
white box testing 白盒测试就是从代码层面去分析代码是否可以正常运行

Coverage

Coverage: how thoroughly it exercises the program 覆盖范围:它执行程序的彻底程度
There are three common kinds of coverage:

• Statement coverage: is every statement run by some test case? 测试是否让每行代码都运行过
• Branch coverage: for every if or while statement in the program, are both the true and the false direction taken by some test case? 每个分支是否都运行过一遍
• Path coverage: is every possible combination of branches — every path through the program — taken by some test case?

Path > Branch > Statement

Lecture 5

Specification

A specification is like a contract for part of your program 一个规范就像是你程序的一部分的契约

• saying what it can count on from the rest of the program 说什么它可以指望从其余的程序
• and what it’s expected to do in return 以及期望它做什么作为回报

Why Specification?

• many of the nastiest bugs in program arise because of misunderstandings about behavior at the interface between two pieces of code 程序中许多最糟糕的错误都是由于对两段代码之间的接口行为的误解而产生的
• Specifications are good for the client of a method because they spare the task of reading code 规范对方法的客户端是有益的，因为它们省去了阅读代码的任务

Spec and implementer

Specifications are good for the implementer of a method because they give the implementer freedom to change the implementation without telling clients 规范对方法的实现者是有益的，因为它们给了实现者在不通知客户的情况下更改实现的自由

Spec and Client

• The contract acts as a firewall between the client and the implementer 合同充当了客户端和实现者之间的防火墙
• This firewall results in decoupling, allowing the code of the unit and the code of a client to be changed independently, so long as the changes respect the specification — each obeying its obligation 这种防火墙导致了解耦，允许单元代码和客户端代码独立地进行更改，只要这些更改遵守规范——每个都遵守自己的义务

Specification Structure

A specification of a method consists of two clauses:

• a precondition, indicated by the keyword requires 是调用者的责任
• a postcondition, indicated by the keyword effects 是实现者的责任

Java has a convention for documentation comments, in which parameters are described by @param clauses and results are described by @return and @throws clauses

• Put the preconditions into @param where possible precondition是放参数
• Put postconditions into @return and @throws postcondition是放return值和抛出的异常

@后面都不需要数据类型，只需要变量名

Lecture 6

Exception

Null References