Java程序辅导

How many distinct values can be
stored in 7 bits?
A. 7
B. 8
C. 128
D. 127
E. –42
Welcome to
COMP1100 and COMP1130
Semester 1, 2018
Programming
Computing a mean
Memory Address Machine Code (hex) Assembler Instructions (Poorly coded) C program
0x100000e9b
0x100000ea2
0x100000eb9
0x100000ebc
0x100000ebf
0x100000ec5
0x100000ec9
0x100000ecd
0x100000ed0
0x100000ed3
0x100000ed6
0x100000ed9
0x100000ede
0x100000ee1
0x100000ee6
0x100000ee9
0x100000eea
c7 45 f0 00 00 00 00
c7 45 ec 00 00 00 00
8b 45 ec
3b 45 f4
0f 8d 21 00 00 00
48 63 45 ec
48 8b 4d f8
8b 14 81
03 55 f0
89 55 f0
8b 45 ec
05 01 00 00 00
89 45 ec
e9 d3 ff ff ff
8b 45 f0
99
f7 7d f4
movl $0x0, -0x10(%rbp)
movl $0x0, -0x14(%rbp)
movl -0x14(%rbp), %eax
cmpl -0xc(%rbp), %eax
jge 0x100000ee6
movslq -0x14(%rbp), %rax
movq -0x8(%rbp), %rcx
movl (%rcx,%rax,4), %edx
addl -0x10(%rbp), %edx
movl %edx, -0x10(%rbp)
movl -0x14(%rbp), %eax
addl $0x1, %eax
movl %eax, -0x14(%rbp)
jmp 0x100000eb9
movl -0x10(%rbp), %eax
cltd
idivl -0xc(%rbp)
int sum = 0;
int i = 0;
loop:
if (i >= length(values))
goto done;
sum += values[i];
i = i + 1;
goto loop;
done:
mean = sum / i;
Machine level programming
Not portable: depends on specific CPU model 
Error prone
Hard to handle complex problems 
Machine dictates the language in which the programmer thinks
Full control
Need more problem-oriented languages.
Need more abstract and safer languages.
Abstraction versus control is a tradeoff!
A brief history of programming languages
Inspired by machine code (imperative, macro assemblers)
Fortran (‘57), Cobol (‘59), Basic (‘64), C(‘71)
Based on formal model of computation (lambda calculus, functional)
Lisp (‘58), ML (‘73)
Structured and strongly typed (imperative)
Algol (58), Algol 60, Algol 68, Pascal (‘70)
Based on message-passing simulation models (object-oriented)
Simula (‘67), Smalltalk (‘69)
Based on first-order logic (declarative)
Prolog (‘72)
Programming paradigms
Control flow: imperative/declarative
Declarative: functional/logic/finite state machines
Allocations and bindings: static/dynamic
Time: event-driven/discrete/synchronous/continuous
Focus: control flow/data flow
Concurrency: sequential/concurrent/distributed
Structure: modular/generics/templates/objects/aspects/agents
Determinism: deterministic/non-deterministic
You don’t need to understand all of these; just many ways to program
Influential languages (≠popularity!)
Conceptual foundations
λ-calculus/Lisp, Simula/Smalltalk, Algol, Prolog
Also influential
ML/Haskell, Pascal, Eiffel, Ada, Modula-3, C, Java
Check out http://exploringdata.github.io/vis/programming-languages-
influence-network/
e.g., PHP widely used, but not particularly influential…

How is software written and executed
Source high-level program
Write in text editor or IDE (Integrated Development Environment)
Translation and interpretation
• Compiler: program that translates source program into machine instructions
• Interpreter: program that interprets (executes) a source program
IDEs allow editing, compiling, executing, and debugging from one 
environment ⇒ rapid development cycle
Program in high level
language, such as C
Compiler
Equivalent program in 
machine language
(a) (b) (c)
#include 
int main()
{
  println(”Hello!”);
  return 0;
}
C
0101010101010010
1010101101011001
1010101110101010
1010101010101111
x86
Program in high level
language, such as Python
Interpreter
Executes program 
directly on CPU
print “Hello!”
Python
AMD
Intel
Program in high level
language, such as Java
Compiler
Equivalent program in 
machine language
public class Hello {
  public static 
  void main
  (String[] args){
    System.out.
    println
    (”Hello!”);
  }}
Java
0101010101010010
1010101101011001
1010101110101010
1010101010101111
x86
1010101101011001
0101010101011100
1010100000101010
1110101010101100
Bytecode
JIT
Compiler
Program in platform
independent
bytecode
Lots of programs work reliably
Most flight computers
Car braking controllers
Banking systems
High speed trains, subway systems
Internet search engines
Professional A/V equiment
…
Programming delivers trusted systems that even our lives depend on
What makes a professional programmer?
“Fluent” in all essential programming constructs and paradigms
Can choose and use the right tools for the job
Considers capabilities of available hardware
Understands translation into executable machine code and how to 
control that translation
Understands testing and verification and uses them adequately
Finds best suited abstractions and modularisations (experience!)
Knows how to analyse unexpected problems (debugging)
Functional Programming
Computing a mean
Haskell
A lazy, functional programming language (based on the λ-calculus).
Statically typed with polymorphism and operator overloading.
Uses monads to provide side-effects and imperative sequencing.
Pragmatically
• Compiler + interactive interpreter
• Concise, compact syntax
• Compiler detects many (most) errors (but error messages may be confusing)
• Performs well (though not as “fast” as C, C++, or even Java)
• Commonly used for verifiable systems, high-integrity systems
• Not directly useful for real-time or high-performance computation
Functional
Functions are first-class: functions are values that can be used in 
exactly the same ways as any other sort of value.
The meaning of Haskell programs is centred around evaluating 
expressions rather than executing instructions.
The result is a different way of thinking about programming.
What is a function?
A recipe for generating outputs from inputs
• ‟multiply a number by itself”
A set of (input, output) pairs:
• (1,1) (2,4) (3,9) (4,16) (5,25)
An equation:
f x = x2
A graph relating inputs to output (for numbers only)
-2 -1 0 1 2
1
2
Functions and states
y = f(x1,x2,…,xn) ?
x1
x2
xn
Input
Output
A repeatable (deterministic) function: fully described by its input-output relation.
This function is in exactly the same “state” every time it is called.
Functions and states
y = f(x1,x2,…,xn) ?
x1
x2
xn
Input
Output
Limiting observability:
• After the function receives its inputs it is oblivious to the outside world.
Functions and states
y = f(x1,x2,…,xn) ?
x1
x2
xn
Input
Output
Limiting observability:
• When the function produces its output it reveals nothing else.
Functions and states
Limiting observability:
• There can be no other communication with the outside world.
y = f(x1,x2,…,xn) ?
x1
x2
xn
Input
Output
❌
❌
Functions and states
Limiting observability:
• The function cannot hold values internally after the function has completed
y = f(x1,x2,…,xn) ?
x1
x2
xn
Input
Output❌
❌
Functions and states
Limiting observability:
• The function cannot write to its input values
y = f(x1,x2,…,xn) ?
x1
x2
xn
Input
Output
❌
❌
❌
Functions and states
y = f(x1,x2,…,xn) ?
x1
x2
xn
Input
Output
The result is a side-effect free function!
Easy to understand and verify.
Can be designed in isolation, supporting modularity.
Pure
Haskell expressions are always referentially transparent:
• no mutations; everything is immutable
• expressions are side-effect free
• calling the same function with the same arguments results in the same 
output; programs are deterministic
Benefits:
• equational reasoning and refactoring: “replace equals by equals” (algebra)
• parallelism: evaluating in parallel is easy when no side effects
• fewer headaches: easier to debug, maintain, and reason about programs

Lazy
Expressions are not evaluated until their results are needed.
• It is easy to define a new control structure just by defining a function.
• It is possible to define and work with infinite data structures.
• It enables a more compositional programming.
• BUT it makes reasoning about time and space usage more difficult!
Kinds of data
Integers: 42, -69
Floats: 3.14
Characters: ‘h’
Strings: “hello”
Booleans: True, False
Pictures: ♞
Applying a function
invert :: Picture -> Picture
knight :: Picture
invert knight
♞ ♘invert
Composing functions
beside :: Picture -> Picture -> Picture
flipV :: Picture –> Picture
invert :: Picture -> Picture
knight :: Picture
beside (invert knight) (flipV knight)
♞ ♘invert
flipV
beside

 


double
Defining a new function
double :: Picture -> Picture
double p = beside (invert p) (flipV p)
♞ ♘invert
flipV
beside

 


Defining a new function
double :: Picture -> Picture
double p = beside (invert p) (flipV p)
♞ double 


Terminology
Type signature
double :: Picture -> Picture
Function declaration
double p = beside (invert p) (flipV p)
function name function body
Terminology
double p = beside (invert p) (flipV p)
formal parameter
function definition
double knight
actual parameter
expression
Types
The meaning of a program will depend on the types of the values it 
manipulates:
• Even though values are just represented as bits, the operations on 
those bits will  interpret them in some way
For example, consider the addition operator +:
It takes two number values and combines them to give a new number.
To add two integers it must interpret the bits of those values as integers 
and use integer addition to produce the result.
Integer addition applied to non-integers would make no sense.
Applying a function
scale:: Picture -> Integer -> Picture
knight :: Picture
scale knight 2♞ ♞scale2
Applying a function
scale:: Picture -> Integer -> Picture
knight :: Picture
scale knight knight♞
scale♞
Types
A type is a collection of values that are the same sort of thing:
e.g., numbers or pictures (and even functions!)
In a strongly-typed programming language you cannot use values and 
the functions that manipulate them inconsistently.
Makes programs type-safe.
This can be enforced statically (compile time) or dynamically (run time).
Static typing helps clarify thinking and express program structure, 
serves as documentation, and turns run-time errors into compile-time 
errors.
Static typing
Helps clarify thinking and express program structure.
Serves as a form of documentation.
Turns run-time errors into compile-time errors.
Examples
Int
• Set of values, subset of the integers, fixed precision
• Stored in some fixed number of bits
• [Live coding experiments to find out range using minBound/maxBound]
Integer
• Set of values, all the integers, arbitrary precision
(up to some number of bits available in memory)
• [Live coding experiment to see behaviour]
Programming: craft and correctness
A human activity (“the art of programming”)
• A program can be well-crafted and aesthetically pleasing
• A program can be unmaintainable or unreadable
Programs are formal artefacts
• An expression in (temporal) logic
• Can be correct/incorrect (against a specification)
Obfuscated code
The International Obfuscated C Code Contest
http://www.ioccc.org/2014/endoh2/prog.c
#include      
#define TA    q=/*XYXY*/
#define/*X    YXY*/CG r=
void p(int n,int c){;
for(;n--;)    putchar(c)
#define Y(    z)d;d=c++\
%2<1?x=x*4    +z,c%8>5?\
x=x?p(1,x),   0:x:0:0;d=
#define/*X    YX*/C Y(1)
#define/*X    YX*/G Y(2)
;}int(*f)(  void),d,c,
#define/*X  YX*/A Y(0)
#define/*XY*/AT int\
m(void/**/){d=
#define/*XYX*/T Y(3)
#define GC  d; return\
0;}int(*f)  (void )=m;
x,q,r; int main(){if(
f)f();else    {for(puts(
"#include"    "\40\"pro\
g.c\"\n\n     \101T"+0);
d=!d?x=(x=    getchar())
<0?0:x,8*8    :d,TA++c%8
,TA(1+7*q- q*q)/3,r=c
*15-c*c-36    ,p(r<0?!q+
4:r/6+!q+4    ,32),q||x;
c%=16)q?p(    1,"ACGT"[x
/d&3]),p(q    ,126),p(1,
"TGCA"[x/d    &3]),d/=4,
p(001,10):    puts(c%8?\
"CG":"TA")    ;puts("GC"
);}return     0;}/**/
Programming myths
It’s easy, everybody can do it with just a few tutorials
Especially sales people for the latest trendy language
It’s intrinsically hard
What old programmers say to keep their jobs
A weird way to spend your day
Hollyword nerd stereotypes
In reality
A specialized, historically recent, technological, professional activity, which 
requires care and focus (just like any advanced profession)
Programming truths
Some things will never work …
• Decision problems
is a program syntactically correct? 
Is x a prime number? 
Will a program stop for a given input? 
The last one is the halting problem, which is representative of a class of 
inherently undecideable problems
Undecideable problems
Kurt Gödel (31): loosely, “any consistent theory can 
express true statements which cannot be proven in this 
theory”
Alan Turing (’37): “no program can decide whether 
another arbitrary program will terminate on a given input”
Henry Gordon Rice (’53): “for any non-trivial property of 
partial functions, no general and effective method can 
decide whether an algorithm computes a partial function 
with that property”
Function composition operator
flipV :: Picture –> Picture
flipH :: Picture -> Picture
rotate :: Picture -> Picture
rotate = flipH . flipV
knight :: Picture
Rotate knight
♞ flipV 
 flipV 

rotate
Expressions and evaluation (reduction)
Evaluating any Haskell expression works much like a calculator:
42.0 → 42.0
3 + 4 / (1234 – 1)
→ 3 + 1 / 1233
→ 3 + 3.2441200324412004e-3
→ 3.0032441200324413
Expressions and evaluation (reduction)
(3 + 4) * (5 – 2)
→ 7 * (5 – 2)
→ 7 * 3
→ 21
Or alternatively:
(3 + 4) * (5 – 2)
→ (3 + 4) * 3
→ 7 * 3
→ 21
Can even compute 3+4 and 5-2 concurrently (in parallel)!
Expressions and evaluation (reduction)
double :: Integer –> Integer
double n = 2 * n
double (3 + 1) → double 4
→ 2 * 4
→ 8
Types
All expressions have types:
:type 42.0
42.0 :: Fractional a => a
Types can be from a class of types, here a type derived from the class 
of Fractional types (i.e., real numbers or fractions).
:type (3 + 4) / (5 - 2)
(3 + 4) * (5 - 2) :: Num a => a
Here Num is a class of numeric types (i.e., numbers).
The essence of functional programming
Types model objects in the problem domain.
Programming means writing functions over types.
Computing with functions means evaluation (reduction).
Haskell variables name values and cannot vary.
Functions have no side-effects.
The essence of Haskell programming
Programs are higher level: define relationship between input and 
output (the what) rather than how to compute a result.
First class functions: can be passed around like any other data.
Functions have no side-effects: monads embed side-effects inside 
Haskell and its type system.
Haskell programs are easy to parallelize: there is no shared state!
Definitions are equations: easy to validate properties, allowing proofs.
Haskell programs are easy to refactor.
A domain specific language for pictures
horse :: Picture
flipH :: Picture -> Picture
flipV :: Picture -> Picture
invertColour :: Picture -> Picture
above :: Picture -> Picture -> Picture
beside :: Picture -> Picture -> Picture
scale :: Picture -> Integer -> Picture
Forming complex pictures
Infix use of above:
horse `above` (flipH horse)
Naming pictures:
bigPic = scale (horse `above` (flipH horse)) 42
Defining new functions:
mirror pic = pic `beside` (flipV pic)

ASCII-art model of pictures
[Live coding look at ASCII-art representation as lists.]
flipH = reverse -- reverse list of lines
flipV = map reverse -- reverse each line of list
above = (++) -- join two lists
beside = zipWith (++) -- join corresponding lines
The Prelude
The function reverse and the basic types come from the Haskell 
Prelude.
[Live programming, browse Prelude.]
Changing models
Abstraction means we can use a different representation for pictures.
Display pictures using SVG graphics instead of ASCII-art.
[Demonstration]
[Live Coding from Chapters 1 and 2 of text]
See files Chapter1.hs and Pictures.hs