L3 - WHILE Language

Question 1

Why do we prefer a high level language in order to write effective procedures?

Answer 1

Turing machines are tedious in terms of establishing computability and complexity. Thus, a higher level language is preferred.

Question 2

Why is the WHILE language a good choice for establishing computability and complexity?

Answer 2

The language is high level and has a good mix of expressive power and simplicity.

Question 3

How many data types does WHILE have? What is this data type?

Answer 3

WHILE can be considered untyped. The type system contains only Binary Trees. These trees are used to encode all other types needed.

Question 4

What other Programming Languages did WHILE take inspiration from ? What were some reasons for this?

Answer 4

JSON, XML, S-Expressions

These are document notation languages. They are:
- expressive
- human readable
- efficiently read by machines
- Are nested lists, which can be encoded as Binary Trees.

Question 5

In what form is WHILE data represented?

Answer 5

Binary Trees.

Question 6

What letter do we use to denote a set of Binary Trees?

Answer 6

D

Question 7

What are the only 2 states that the while binary tree can be? How are these denoted?

Answer 7

Empty : Nil
Constructed : <l,r>

Question 8

Think of a simple binary tree where all leaf atoms are nil. Represent this tree in linear form…

Answer 8

…

Question 9

In WHILE syntax, how do we encode Booleans?

Answer 9

False = nil
True = <nil.nil></nil.nil>

Question 10

In WHILE syntax, how do we encode Natural Numbers?

Answer 10

3 = <nil . <nil . <nil.nil> > ></nil.nil>

Question 11

In WHILE syntax, how do we encode Lists?

Encode : [a1,a2,a3]
Encode : [[],[]]
Encode : [nil,nil,[],[]]

Answer 11

[] = nil
[a1] = <a1.nil>
[a1,a2] = < a1 . <a2.nil> >
[a1,a2,a3] = < a1 . < a2 < a3.nil > > ></a2.nil></a1.nil>

Question 12

In WHILE syntax, how do we encode Pairs?

Answer 12

(p,q) = [p,q] = < p . < q . nil > >

Question 13

What are the 2 data that Expressions can represent in WHILE?

Answer 13

• An empty tree
• A constructed tree

Question 14

What is a Destructor in WHILE? Give the main 2.

Answer 14

• Disassemble a Binary Tree into left and right subtrees.
• Head : Disassembles to left subtree.
• Tail : Disassembles to right subtree.

Question 15

What are the 4 types of Commands in WHILE?

Answer 15

Assignment
Conditional
While Loop
Statement Block

Question 16

Name and define the components of a WHILE program…

Answer 16

Name
Input Read
Statement Block
Output Write

Question 17

How many variables can a WHILE program read and write?

Answer 17

1