Transcript 3.5 Programming paradigms

3.5 Programming paradigms
Part 3
Declarative Languages
In declarative languages, the
programmer can simply state what is
wanted, having declared a set of facts
and rules.
 In the following example coded in prolog,
the query male (x) searches and returns
all those that are male.

VCN CIE COMPUTING 9691/3 :::
Compiled by Benjamin Muganzi
2
Example:

We have the following facts.












female(jane).
female(anne).
female(sandip).
male(charnjit).
male(jaz).
male(tom).
parent(jane,mary).
parent(jane, rajinder).
parent(charnjit, mary).
parent(charnjit, rajinder).
parent(sandip, atif).
parent(jaz, atif).

The output of male(x) will be
X = charnjit
X = jaz
X = tom
No

“No” means that there are no
more results.
VCN CIE COMPUTING 9691/3 :::
Compiled by Benjamin Muganzi
3
Goals

Looking in the database for male(X) is known as looking for a
GOAL

A goal is a statement that we are trying to prove whether or not it
is True or False.

If we add the rule
father(X, Y) :- parent(X, Y), male(X)

This rule states that X is father of Y if (the :- symbol) X is a parent

This means that father is a predicate, and X & Y are arguments
of Y AND (the comma) X is male.
VCN CIE COMPUTING 9691/3 :::
Compiled by Benjamin Muganzi
4
Instantiation

Instantiation means assigning a value to
a variable.

Example:

The query male(X) instantiates X to charnjit.
VCN CIE COMPUTING 9691/3 :::
Compiled by Benjamin Muganzi
5
Backtracking

Backtracking is the going back to a
previously found successful match in
order to continue a search.

If the goal (search) fails on the last part
of a rule the language will backtrack to
where the failed variable was first found
and it will move the variable onto the
next record.
VCN CIE COMPUTING 9691/3 :::
Compiled by Benjamin Muganzi
6
Example:


Consider
female(jane).
female(anne).
female(sandip).
male(charnjit).
male(jaz).
male(tom).
parent(jane,mary).
parent(jane, rajinder).
parent(charnjit, mary).
parent(charnjit, rajinder).
parent(sandip, atif).
parent(jaz, atif).
father(X, Y) :- parent(X, Y), male(X).

To find the father of rajinder (goal)
we use the rule father(X, rajinder)




X is instantiated to jane, and the
rule male(jane) is applied, which
gives a False.
Prolog backtracks to find a match
for the rule male(x) until it
becomes True at Charnijt.
Now prolog applies again the
whole rule which returns a TRUE
so it outputs Charnjit.
Then the program continies
looking for any other matches, and
finds none, so it returns No
The last rule states that X is father of
Y if (the :- symbol) X is a parent of Y
AND (the comma) X is male.
VCN CIE COMPUTING 9691/3 :::
Compiled by Benjamin Muganzi
7
Low level languages

Low level languages represent binary
with mnemonics, such as…
ADD = 001 (a command)
 NUM1 = 00101 (an address)


An Assembler translates the mnemonics
(using a table) to produce machine code
VCN CIE COMPUTING 9691/3 :::
Compiled by Benjamin Muganzi
8
Memory addressing techniques

An instruction in memory consists of an
opcode and an operand. The operand is the
data on which the operation should be applied.
The method used to locate said data is known
as memory addressing.
 There are 5 major techniques of memory
addressing





Immediate addressing
Direct addressing
Indirect addressing
Indexed addressing
Relative addressing
Immediate addressing



Immediate addressing is so-named because the value to be
stored in memory immediately follows the operation code in
memory.
For example, if you wanted to add 3 to the contents of the
accumulator, this would simply be: ADD 0011
The opcode is ADD and the actual data is 0011 (binary 3)
Advantage

It is very fast since the value to be loaded is included in the
instruction.
Disadvantage

The data cannot be used by other instructions


In our example, the value 3 would have to be repeated in every
instruction that needs it
It is difficult to change the value.
Direct Addressing


Direct addressing points to a location in memory that
holds the data.
E.g. ADD 0101 means that “go and find whatever is in
memory address 5 and add it to the accumulator.”
Advantage:

It is simple to use because you don’t need to know the data in
the memory location
Disadvantage

The number of memory addresses that can be accessed is
limited by the number of bits available for the operand.

If the operand was a 16 bit number, 216 memory locations can be addressed
giving us 64KB of memory which isn’t a lot.
Indirect addressing

Indirect addressing points to a memory
location that holds another memory location
that holds the data to be used.
 E.g, ADD 1011 means “go to memory location 11
where you’ll find another memory location; go to this
other address and use the value found there”
Advantage

It allows access to larger memory addresses as
the full size of register is used for an address.
Indexed Addressing

Indexed Addressing uses a special register
called the index register
 The value of the index register is incremented
each time it is referred to
 The memory address given in the instruction is
then adjusted according to the value of the
register.
Advantage

The same instruction can be repeated but applied to a
different memory location each time.

This is useful for processing an array, which would be stored in a
contiguous block of memory.
Indexed addressing: example

suppose we wanted to add up every number in
an array. Normally, we would execute:
ADD0001
ADD0010
ADD0011
etc.

However, the operator is the same (“ADD”),
only the operand changes. This means we
could repeat the same instruction and use the
index register to increment the memory
address.
Relative addressing



When we write a program, we don’t know where in
memory it will be held during execution, but we do
know that it will go into memory as a single block.
In relative addressing, all memory addresses are
relative to the first one.
Example: ****


If the first instruction in a program is ADD 100, all
subsequent addresses will be relative to 0100.
This means that if the next instruction is ADD 010, the
memory address that is accessed is 100+010=110.
Methods of defining syntax
 Each
language uses a different set
of rules to define its syntax.
 E.g.
a Visual Basic compiler would not
understand C++ syntax and vice
versa.
 The RULES of a language are specified
using Backus Naur Form (BNF) or
syntax diagrams.
Backus – Naur Form (BNF)

It is an internationally accepted notation language to define
the syntax of a system or programming language. Note that
It is necessary to unambiguously define the syntax of a
computer language.
 Suppose we wanted to define a digit using BNF.
 we say <digit> ::= 0|1|2|3|4|5|6|7|8|9
Brackets < > mean ‘can be defined further’
 ::= means ‘is defined to be’
 | means ‘or’


We could then define an integer as follows.
<integer> ::= <digit> | <digit><integer>
 This allows an integer to be a single digit or a digit followed
by an integer. This part of the definition is recursive. It
allows any number of digits.
VCN CIE COMPUTING 9691/3 :::
Compiled by Benjamin Muganzi
17
BNF Example.

Defining of a staff code being entered into a database.
<DIGIT> ::= 0|1|2|3|4|5|6|7|8|9
<LETTER> ::= A|B|C|D|E
<STAFF_CODE> ::= <LETTER><DIGIT> | <STAFF_CODE><DIGIT>
This means “a staff code can be a letter and then any number of digits.”
SO
 D4, E644678, A564 would all be valid staff codes.
 The following examples would be invalid staff codes:




Hf – because H is not defined to be a letter
d4 – because a lowercase ‘d’ is not defined to be a letter
A56E – because you can only have a letter at the beginning of a staff
code
AD574 – because the definition only allows a single letter at the
beginning of a staff code.
VCN CIE COMPUTING 9691/3 :::
Compiled by Benjamin Muganzi
18
BNF Example 2

Defining a variable (which is which is a
sequence of one or more characters
starting with a letter)
<variable> ::= <letter>|<variable><character>
<character> ::= <letter>|<digit>|<under-score>
<letter> ::= <uppercase>|<lowercase>
<uppercase> ::= A|B|C|D|E|F|G|H|I|J|K|ZL|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z
<lowercase> ::= a|b|c|d|e|f|g|h|i|j|k|zl|m|n|o|p|q|r|s|t|u|v|w|x|y|z
<digit> ::= 0|1|2|3|4|5|6|7|8|9
<under-score> ::= _
VCN CIE COMPUTING 9691/3 :::
Compiled by Benjamin Muganzi
19
Syntax diagrams


Syntax diagrams are diagrammatic way of representing a BNF
definition.
The staff code example from slide no. 18 would be represented
as follows
LETTER
DIGIT
STAFF_CODE
VCN CIE COMPUTING 9691/3 :::
Compiled by Benjamin Muganzi
20
Example 3: Signed integer
BNF for Integer (signed or unsigned)
VCN CIE COMPUTING 9691/3 :::
Compiled by Benjamin Muganzi

<integer> ::= <unsigned integer>|<signed integer>
<signed integer> ::= + <unsigned integer>| - <unsigned integer>
<unsigned integer> ::= <digit>|<digit><unsigned integer>
<digit> ::= 0|1|2|3|4|5|6|7|8|9

To add a sign to the integer you just add signs !
Syntax diagram for signed integer
Digit
Digit
+
21
Reverse Polish notation

Reverse Polish Notation is an unambiguous method of writing
mathematical expressions without brackets.




Adding two numbers is written as A + B
This is called infix notation as the operator is in between the operands
To multiply the result by two, we’d write 2 * (A + B)
We need brackets to make sure it’s done in the right order.

Polish notation avoids brackets by putting each operator before its
operands. A + B would become +AB and 2 * (A + B) becomes *2+AB
 Reverse polish notation is simply polish notation written the other
way around.
 So those examples would be AB+ and AB+2*. This can be read
as ‘take the numbers A and B and add them together, then take the result and
the number 2 and multiply them together.’
 Reverse polish notation puts each operator after its operands.
VCN CIE COMPUTING 9691/3 :::
Compiled by Benjamin Muganzi
22



Binary tree diagrams can be used to convert between
normal infix notation and reverse polish notation.
A binary tree is a tree data structure in which each
node has at most two child nodes, usually
distinguished as "left" and "right".
Nodes with children are parent nodes, and child nodes
may contain references to their parents.
23
VCN CIE COMPUTING 9691/3 :::
Compiled by Benjamin Muganzi
Converting between
Reverse polish and Infix notations
Traversing a binary tree

Traversing a tree: IN-ORDER (infix)
Using this method, we must visit the tree in this order:





Visit the left sub-tree.
Visit the root node.
Visit the right sub-tree.
So we would have DBEAC
Traversing a tree: POST-ORDER
Using this method, need to:




Visit the left sub-tree.
Visit the right sub-tree.
Visit the root node.
Using our binary tree, the order that we would be: D E B C A
Converting…

Consider the: 3 * (6 + 2) - 4 / (3 + 7)

If we wanted to get the infix notation from a binary
tree, we would follow this algorithm, which is known as
'in-order':




1) Traverse the left sub-tree
2) Visit the root
3) Traverse the right sub-tree
This would give us:
3 * (6 + 2) - 4 / (3 + 7)
Converting

If we wanted to get the reverse polish notation,
we would follow this algorithm, which is known
as ‘post-order':




1) Traverse the left sub-tree
2) Traverse the right sub-tree
3) Visit the root
This would give us:
362+*4-37+/
Using stacks

Stacks are also associated with reverse
polish notation.
 They can be used to evaluate expressions
using the following algorithm
1. Read expression from left to right
2. If a number is encountered, PUSH it onto stack
3. If an operator is encountered, POP two number
from stack and carry out operation
a) PUSH result onto stack
4. End if last item in expression has been dealt with.
Example: using stacks
1

We have the expression 6 4 5 + * 25 2 3 + / 1. The numbers 6, 4 and 5 are encountered so they are
PUSHED to the stack one by one.
2. Then an operator is encountered: + The top two numbers are
POPPED (4 and 5) and the operation carried out on them, the
result is PUSHED to the stack (9)
3. Another operator is encountered: * This is applied to the two
items POPPED from the stack (9 and 6). The result is
PUSHED onto the stack
4. The numbers 25, 2 and 3 are PUSHED onto the stack as they
are encountered
5. The ‘+’ is encountered so the 3 and 2 are POPPED, added
together and the result is PUSHED (5)
6. The 5 and 25 are POPPED and divided (notice the order of
the operands) and the result, 5, is PUSHED.
7.
Finally, the 5 and 54 and POPPED and subtracted and
the result is PUSHED back onto the stack. This is our
final answer. Again, notice that the first operand to be
POPPED is placed to the right of the operator i.e. 54-5.
2
3
4
5
6
7