Transcript Slides - University of Virginia, Department of Computer Science

Lecture 15:
Using
Low-Level
Languages
CS201j: Engineering Software
University of Virginia
Computer Science
David Evans
http://www.cs.virginia.edu/~evans
Menu
•
•
•
•
Subtyping and Arrays
Survey Results
C
Data Abstraction in C
29 October 2002
CS 201J Fall 2002
2
Subtyping and Arrays
If B <= A, should B[] <= A []?
29 October 2002
CS 201J Fall 2002
3
Array Subtyping
static public Object getFirst (Object [] els) throws NoSuchElementException {
if (els == null || els.length == 0) {
throw new NoSuchElementException ();
} else {
return els[0];
}
}
static public void main (String args[]) {
try {
Object o = getFirst (args);
System.err.println ("The first parameter is: " + o);
} catch (NoSuchElementException e) {
System.err.println ("There are no parameters!");
}
}
29 October 2002
CS 201J Fall 2002
4
Array Store
static public void setFirst (Object [] els) throws NoSuchElementException {
if (els == null || els.length == 0) {
throw new NoSuchElementException ();
} else {
els[0] = new Object ();
}
> javac TestArrays.java
}
> java TestArrays test
The first parameter is: test
Exception in thread "main" java.lang.ArrayStoreException
at TestArrays.setFirst(TestArrays.java:16)
at TestArrays.main(TestArrays.java:25)
static public void main (String args[]) {
try {
Object o = getFirst (args);
System.err.println ("The first parameter is: " + o);
setFirst (args);
} catch (NoSuchElementException e) {
System.err.println ("There are no parameters!");
}
}29 October 2002
CS 201J Fall 2002
5
ESC/Java and Array Stores
> escjava TestArrays.java
ESC/Java version 1.2.4, 27 September 2001
TestArrays ...
TestArrays: getFirst(java.lang.Object[]) ...
[0.199 s] passed
TestArrays: setFirst(java.lang.Object[]) ...
-----------------------------------------------------------------------TestArrays.java:16: Warning: Type of right-hand side possibly not a subtype of
array element type (ArrayStore)
els[0] = new Object ();
29 October 2002
CS 201J Fall 2002
6
Java
• Type checking: B <= A  B[] <= A[]
• Need a run-time check for every array
store (to an array where the actual
element type is not known)
• Better rule: no inference of array subtypes
29 October 2002
CS 201J Fall 2002
7
Survey Results
• Responses: 23 (27 students)
• Speed
– way too fast: 2; too fast: 11; just about right: 10
– too slow, way too slow: 0
• Collaboration
– assigned groups: 6
– groups you form yourselves: 9
– groups you form yourselves different from PS4/5: 1
– alone: 5
29 October 2002
CS 201J Fall 2002
8
Final Problem Set
• Final Problem Set:
– Open ended: 9
– Well-defined problem: 3
– Something in-between: 10
– No more problem sets: 0
29 October 2002
CS 201J Fall 2002
9
Reading Comments
• Read comments on PS4
– yes: 8
– skimmed: 11
– a few: 2
– no, but will before exam: 2
• Read comments on Exam 1:
– yes: 9
– skimmed: 9
– a few: 2
– no, but will before exam: 3
29 October 2002
CS 201J Fall 2002
10
Using ESC/Java
• Use ESC/Java if not required:
– Check all and use annotations: 3
– Check some, no annotations: 5
– Hardly ever: 8 (“but I know I should”)
– Never: 7
29 October 2002
CS 201J Fall 2002
11
Using ESC/Java
• Hard to get much benefit without using
annotations
• Cost/benefit depends on:
– Importance of correctness
– Complexity of software
– Longevity of software
– Size, dynamism of team
• What if your final exam was to write one
program, and get an A or F if it passes one
secret test case?
29 October 2002
CS 201J Fall 2002
12
Classes
• Classes:
– More work in groups: 8
– Fewer groups, more lectures: 2
– Same: 13
• First Flight:
– Only ESC/Java: 5
– Only Testing: 14
– Take the train: 3
29 October 2002
CS 201J Fall 2002
13
Final Exam
•
•
•
•
•
•
Programming: 4
Design: 7
Essay: 5
Multiple choice: 2
Optional: 17
No final: 4
29 October 2002
CS 201J Fall 2002
14
Exam 2
similar to exam 1: 16
like exam 1, real programming: 3
in class: 0
no exam 2: 2
• Exam 2 will be similar in format to Exam 1
• Out: Nov 14, Due: Nov 19
• Topics: subtyping (substitution, inheritance),
concurrency, low-level programming,
anything from first part of course also
29 October 2002
CS 201J Fall 2002
15
New Languages and Tools
• Problem Set 6 with new language/tool:
– Grossly unfair: 1
– A little bit bizarre: 8
– Better then doing more Java and ESC/Java: 4
– Good opportunity: 11
29 October 2002
CS 201J Fall 2002
16
C
29 October 2002
CS 201J Fall 2002
17
Programming Languages Phylogeny
Fortran (1954)
Algol (1958)
LISP (1957)
Scheme (1975)
CPL (1963), U Cambridge
Combined Programming Language
BCPL (1967), U Cambridge
Basic Combined Programming Language
B (1969), Bell Labs
C (1970), Bell Labs
C++ (1983), Bell Labs
Java (1995), Sun
29 October 2002
CS 201J Fall 2002
18
C Programming Language
• Developed to build Unix operating system
• Main design considerations:
– Compiler size: needed to run on PDP-11 with
24KB of memory (Algol60 was too big to fit)
– Code size: needed to implement the whole
OS and applications with little memory
– Performance
– Portability
• Little (if any consideration):
– Security, robustness, maintainability
29 October 2002
CS 201J Fall 2002
19
C Language
• No support for:
– Array bounds checking
– Null dereferences checking
– Data abstraction
– Exceptions
– Automatic memory management (next lecture)
– Subtyping, inheritance
• Program crashes (or worse) when something
bad happens
• Lots of syntactically legal programs have
undefined behavior
29 October 2002
CS 201J Fall 2002
20
Example C Program
void test (int x) {
while (x = 1) {
printf (“I’m an imbecile!”);
x = x + 1;
}
}
Weak type checking:
In C, there is no boolean type.
Any value can be the test expression.
x = 1 assigns 1 to x, and has the value 1.
29 October 2002
CS 201J Fall 2002
In Java:
void test (int x) {
while (x = 1) {
printf (“I’m an imbecile!”);
x = x + 1;
}
}
> javac Test.java
Test.java:21: incompatible types
found : int
required: boolean
while (x = 1) {
^
1 error
21
C/C++ Bounds NonChecking
# include <iostream.h>
int main (void) {
int x = 9;
char s[4];
}
cin >> s;
cout << "s is: " << s << endl;
cout << "x is: " << x << endl;
29 October 2002
> g++ -o bounds bounds.cc
> bounds
cs
(User input)
s is: cs
x is: 9
> bounds
cs201
s is: cs201
x is: 49
> bounds
cs201j
s is: cs201j
x is: 27185
> bounds
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
s is: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
x is: 1633771873
Segmentation fault (core dumped)
CS 201J Fall 2002
22
So, why would anyone use
C today?
29 October 2002
CS 201J Fall 2002
23
Reasons to Use C
• Legacy Code
– Linux, most open source applications are in C
• Simple to write compiler
– Programming embedded systems, often only
have a C compiler
• Performance
– Typically 50x faster than interpreted Java
• Smaller, better defined language, lots of
experience
29 October 2002
CS 201J Fall 2002
24
Secure, Dependable,
Maintainable Programming in C
• How can we write secure, dependable,
maintainable programs in C?
Program in a disciplined way:
Just because a language doesn’t have support for
data abstraction, doesn’t mean we can’t use it!
Use static analysis to enforce program properties:
Our abstract types are really abstract
Array fetches are in bounds
Memory management is correct
We don’t use undefined behaviors of C
29 October 2002
CS 201J Fall 2002
25
User-Defined Types in C
• typedef defines a new type
• Types are checked by structure, not name
typedef int color;
typedef int weight;
int f (color c, weight w) {
return c + w;
}
29 October 2002
CS 201J Fall 2002
26
User-Defined Structure Types
• Use struct to group data
• Dot (.) operator to access fields of a struct
• Fields are accessible everywhere (no way
to make them private)
typedef struct {
char name[10];
char genome[10];
} Species;
29 October 2002
CS 201J Fall 2002
27
Pointers
T *x;
Declares x as a reference to a T
*x
Evaluates to the object x references.
int *x;
*x = 3;
x
Crashes (undefined
behavior). In C, we need
to explicitly allocate
space to store the object.
29 October 2002
CS 201J Fall 2002
int
28
Pointers
T *x;
Declares x as a reference to a T
*x
Evaluates to the object x references.
int *x;
x
x = malloc (sizeof (int));
*x = 3;
29 October 2002
CS 201J Fall 2002
int
3
29
Data Types in C
• Most useful data types are pointers to
structs
typedef struct {
char *name;
char *genome;
} *Species;
Species Species_new (char *p_name, char *p_genome) {
Species res = malloc (sizeof (*res));
res->name = p_name;
res->name is short for
res->genome = p_genome;
(*res).name
return res;
}
29 October 2002
CS 201J Fall 2002
30
Abstract Types in C
• How can we get most of the benefits of
data abstraction in C?
Distinguish between client code and implementation code
In client code:
Check types by name instead of by structure
Don’t allow client code to depend on the
representation of a type:
Make struct fields inaccessible
Don’t allow use of C operators
29 October 2002
CS 201J Fall 2002
31
Splint
• Lightweight analysis tool for C
• Uses annotations (like ESC/Java)
– Simpler and more limited than ESC/Java
annotations
• Allows us to program in C but get:
– Abstract data types
– Checked null dereferences
– Checked memory management
– etc.
29 October 2002
CS 201J Fall 2002
32
Abstract Types
color.h:
typedef /*@abstract@*/ int color;
typedef /*@abstract@*/ int weight;
client.c:
# include "color.h"
int f (color c, weight w) {
return c + w;
}
> splint client.c
Splint 3.0.1.7 --- 08 Aug 2002
client.c: (in function f)
client.c:4:10: Operands of + are abstract types (color, weight): c + w
An abstraction barrier is broken. If necessary, use /*@access <type>@*/ to
allow access to an abstract type. (Use -abstract to inhibit warning)
Finished checking --- 1 code warning
29 October 2002
CS 201J Fall 2002
33
Implementing a Type
• Header File (<Type>.h)
– Define representation
– Declare functions
• Implementation File (<Type>.c)
– Implement the operations associated with a
type
– Use a naming convention
<Type>_<operation> has access to the abstract
type <Type>
29 October 2002
CS 201J Fall 2002
34
Species.h
/*
** OVERVIEW: Species is an immutable record type.
*/
typedef /*@abstract@*/ struct {
/*@only@*/ char *name;
/*@only@*/ char *genome;
} *Species;
extern /*@only@*/ Species Species_new (/*@only@*/ char *p_name,
/*@only@*/ char *p_genome)
/* EFFECTS: Returns a new Species with name p_name and genome p_genome. */ ;
extern /*@observer@*/ char *Species_getName (Species s) ;
extern /*@observer@*/ char *Species_getGenome (Species s) ;
extern /*@only@*/ char *Species_toString (Species s)
/* EFFECTS: Returns a string representation of s. */ ;
29 October 2002
CS 201J Fall 2002
/*@only@*/ and
/*@observer@*/ annotations
35
explained next class
Species.c
#
#
#
#
include
include
include
include
<stdio.h>
<stdlib.h>
<string.h>
"Species.h"
Species Species_new (char *p_name, char *p_genome) {
Species res = malloc (sizeof (*res));
res->name = p_name;
res->genome = p_genome;
return res;
}
char *Species_getName (Species s) {
return s->name;
}
29 October 2002
CS 201J Fall 2002
36
Enforcing Abstract Types
• Implementation Code
– Where datatype is defined (also naming
conventions to allow access)
– Rep and abstract type are interchangable
• Client Code
– Everywhere else
– ADT is type name only: cannot access fields,
use C operators, treat as rep
– Only manipulate by passing to procedures
29 October 2002
CS 201J Fall 2002
37
Phylogeny.c
# include <stdio.h>
# include "Species.h"
int main (void) {
Species s = Species_new ("Duck", "ACTGACA");
printf ("Species name: %s\n", s->name);
return 0;
}
> splint Phylogeny.c
…
Phylogeny.c:6:34: Arrow access of non-pointer (Species): s->name
Types are incompatible. (Use -type to inhibit warning)
…
Finished checking --- 4 code warnings
29 October 2002
CS 201J Fall 2002
38
# include "Species.h"
Species Species_new (char *p_name, char *p_genome) {
7
Species res = malloc (sizeof (*res));
8
res->name = p_name;
res->genome = p_genome;
return res;
}
> splint Species.c
Splint 3.0.1.7 --- 08 Aug 2002
Species.c: (in function Species_new)
Species.c:8:6: Arrow access from possibly null pointer res: res->name
A possibly null pointer is dereferenced. Value is either the result of a
function which may return null (in which case, code should check it is not
null), or a global, parameter or structure field declared with the null
qualifier. (Use -nullderef to inhibit warning)
Species.c:7:17: Storage res may become null
Finished checking --- 1 code warning
29 October 2002
CS 201J Fall 2002
39
Charge
• You can write secure and dependable
programs in any language
– Different languages and tools make it easier or
harder, but most important is the programmer
• Splint detects some other problems with our
examples today (more on that Thursday)
• PS5: Due Halloween (Thursday)
Happy simulating!
• PS6: Use C and Splint (Phylogeny Revisited)
29 October 2002
CS 201J Fall 2002
40