Unit 6 - Trees, Graphs, Recursive Types

Question 1

In most cases, in custom types that allow values of arbitrary size, these values are some
kind of

Answer 1

trees or graphs

Question 2

A tree is a

Answer 2

hierarchical structure with one root

Question 3

A graph is a (in this context)

Answer 3

a collection of arbitrary links among a set of nodes.

Question 4

In most PLs, graphs are more difficult to

Answer 4

represent and manipulate than trees

Question 5

Imperative languages let us treat recursive structures as

Answer 5

nodes with explicit links between
them

Question 6

Abstract languages present the recursive structures as

Answer 6

symbolic expressions.

Question 7

Imperative PLs are characterised by

Answer 7

• more flexibility in organising the structures, in particular they support structures
  with aliasing and cycles;
• the danger of making hard-to-discover mistakes due to aliasing;
• the ability to modify and evolve structures that had been built earlier;
• the need to write much more code when creating and traversing trees;
• less PL support for checking the correctness of the code.

Question 8

The main ways in which Java differs from C in treating recursive structures are:

Answer 8

• In Java there is no need to distinguish pointers to records (ie objects) from the re-
  cords themselves because all Java records (ie objects) are on the heap and can be
  referred to only by pointers.
• There is no easy way to duplicate a whole record (ie object) in Java, whereas in C a
  whole record can be copied by an ordinary assignment to a variable of the record
  type.
• In Java, new heap memory space is allocated and initialised with a correct record
  value in a single statement (ie a constructor call), whereas in C, space of the right
  size has to be first allocated by a special malloc call and then other statements
  initialise the value stored in that space.

Question 9

The main differences between Lisp and Haskell in treating symbolic expressions are:

Answer 9

• Constructors in Lisp symbolic expressions do not have to be declared and have
  no interesting intrinsic types, whereas in Haskell it is the opposite: Each record
  constructor symbol has to be explicitly declared and associated with a unique type.
• Lisp trees can be modified using setf, but it has to be used with care to avoid
  dangerous effects, such as modifying the program code. Haskell symbolic trees
  cannot be modified, only re-created with some changes.