©J.Tiberghien - ULB-VUB Version 2007 Première partie, chap. 4, page 1 Chapitre 1.4 Langages et outils de programmation

©J.Tiberghien - ULB-VUBVersion 2007 1Première partie, chap. 4, page

Chapitre 1.4

Langages et outils

de programmation


Summary• Programming languages

– Low level languages and assemblers– High level languages

• Imperative and non-imperative languages • Tools for executing high level languages

• System and Program design– Specifications– Design– Tools for design and documentation

• Essential constructs in imperative languages


Machine Language Assembler

P1: 10 0 101 COPY #0 NDP2: 10 0 102 COPY #0 SCP3: 40 200 0 3 EQ? KFL #0 P3P4: 24 102 10 102 MUL SC #10 SCP5: 21 102 201 102 ADD SC KDA SCP6: 10 0 200 COPY #0 KFLP7: 20 101 1 101 ADD ND #1 NDP8: 42 101 3 3 NE? ND #3 P3P9: 42 102 321 1 NE? SC #321 P1P10: 10 1 202 COPY #1 DDAP11: 47 1 JMP P1

Machine Language vs. Assembler


Machine vs. Assembly language

• Data memory addresses receive symbolic names.• Program memory addresses receive symbolic names.• IO interfaces receive symbolic names.• Operation codes receive a name that evokes the

performed action.• each machine instruction corresponds to one

assembly language instruction• An assembly language program can have pseudo

instructions which are commands for the assembler


Source Code (LLL)

ASSEMBLER

Object Code

HARDWARE

The ASSEMBLER


Assembling and Executing1. Loading the Assembler

Assembler

(in machine language)

ABL


Assembling and Executing2. Assembling the program

AssemblerSo

urc

e C

od

e

Ob

ject

Co

de


Assembling and Executing3. Loading the user’s program

ABL

User’s Program



Assembling and Executing4. Executing the user’s program

User’s ProgramUs

er’

s D

ata

Us

er’

s re

su

lts


Assembly LanguageSource Code Format

Label Opc Operands Comments

BGN: COPY #0,ND Initialise number of entered digits

COPY #0,SC Initialise secret code

TFL: EQ? KFL,#0,TFL Test continuously for key stroke

MUL SC,#10,SC Shift SC one digit to the left

ADD SC,KDA,SC Add newly entered digit to SC

COPY #0,KFL Reset Keyboard flag

ADD ND,#1,ND Increase number of entered digits

NE? ND,#3,TFL Any more digits needed ?

NE? SC,#321,BGN Is the entered secret code correct ?

COPY #1,DDA Open the door

JMP BGN Restart everything


Assembly LanguagePseudo Instructions

Label Opc Operands Comments

ORG 100 First address of data memory

ND: DAT 2 Number of entered digits, 2 bytes

SC: DAT 2 Secret Code as entered, 2 bytes

KFL: EQU 200 Keyboard flag, hardwired at address 200

KDA: EQU KFL+1 Keyboard data

DDA: EQU 202 Door data

ORG 0 First address of program memory

…

END


WHAT IS A PROGRAM ?

PROGRAM

=

Description of data

+

Actions to perform upon these data


ORG 100 Begin of data memoryND: DAT 2 Number of digits,2 bytesSC: DAT 2 Secret code,2 bytesKFL: EQU 200 Keyboard FlagKDA: EQU 201 Keyboard DataDDA: EQU 202 Door Data

ORG 0 Begin of program memoryBGN: COPY #0 ND Init. number of digits

COPY #0 SC Init. secret codeTFL: EQ? KFL #0 TFL Test for key stroke

MUL SC #10 SC Shift SC one digit leftADD SC KDA SC Add new digit to SCCOPY #0 KFL Reset keyflagADD ND #1 ND Increase entered digitsNE? ND #3 TFL More digits needed ?NE? SC #321 BGN Correct secret code ?COPY #1 DDA Open the doorJMP BGN Restart everythingEND

Assembler Example


VAR (* data *) ND,SC : INTEGER; KFL[200] : (idle,ready); (* Keyboard flag *) KDA[201] : [0..9]; (* Keyboard data *) DDA[202] : (closed,open); (* Door data *)BEGIN (* actions *) LOOP SC := 0; FOR ND := 1 TO 3 DO REPEAT UNTIL KFL = ready; SC := SC * 10 + KDA; KFL := idle; END (* Key reading FOR *); IF SC = 321 THEN DDA := open END (* Key test IF *) END (* ever running LOOP *)END

High-level Language Example


Programming Languages

• Low Level Languages (Assembler)– One statement corresponds to one instruction– Machine specific– Error prone, low programmers productivity

• High Level Languages– One statement corresponds to many instructions– Machine independent– User friendly, high programmers productivity.


Imperative vs. Non-imperative

• Imperative– Program states how things should be done– Traditional programming style– Efficient execution.

• Non imperative (Declarative or Functional)– Program states what should be done– Innovative programming style for specific fields– Often rather slow.


Imperative vs. Non-imperative

READ (archi);

READ (algo);

final := (archi+algo)/2;

WRITE (final)

• Declarations:archi can be read

algo can be read

final = (archi+algo)/2

• Commands:Write(final)


Spreadsheet example


Translates and executes Statement after

Statement

HARDWARE

INTERPRETER

Source Code (HLL)

COMPILER

Object Code

Translates the entire program at once

Compilers vs. Interpreters


Compiling and Executing1. Loading the Compiler

Compiler


ABL


Compiling and Executing2. Compiling the program

CompilerSo

urc

e C

od

e

Ob

ject

Co

de


Compiling and Executing3. Loading the user’s program

ABL

User’s Program



Compiling and Executing4. Executing the user’s program

User’s ProgramUs

er’

s D

ata

Us

er’

s re

su

lts


Interpretation1. Loading the Interpreter

Interpreter


ABL


Interpretation2. Interpreting the user’s program

Interpreter

Us

er’

s re

su

lts

So

urc

e C

od

e+

Us

er’

s D

ata


Compilers vs. Interpreters

• Compilers– Translate the entire program at once– Program execution very fast– Poor run-time error messages

• Interpreters– Translate and execute statement after statement– Very slow execution– Good run-time error messages


HARDWARE

INTERPRETER

Source Code (HLL)

COMPILER

Object Code

ASSEMBLER

Assembler Source


HARDWARE 1

INTERPRETER 1

Source Code (Java)

COMPILER

CommonAssembler Source

HARDWARE 2

INTERPRETER 2

Java byte code


Source B Source C Source DSource A

Reloc. DReloc. A Reloc. B Reloc. C

Compiler X Compiler Y Assembler

LINKER

Object Code A+B+C+D

Role of a Linker


Relocatable Code

• Relocatable object code = three tables:– CODE

• Program to be loaded from address 0

• List of all location dependant addresses

– EXTERNALS• Symbolic names to be imported

• Addresses where these externals are referenced

– ENTRY POINTS• Symbolic names that can be referenced elsewhere

• Address corresponding to the symbolic name


LinkersUsing intermediate code

Reloc.A

Object

LINKER

Reloc.B

Reloc.C

Reloc.D

Main module Libraries


HARDWARE

INTERPRETER

Source Code (LLL or HLL)

Translator

Object Code

LINKER

Reloc.Code

Static linking


Dynamic Linking

• Fact : – Many procedures are not activated at each

program execution

• Solution :– Link at run-time !

• Initial procedure calls replaced by call to linker

• Procedure name passed as parameter to linker

– Example : .dll files in MS/DOS & Windows


The Cost of Softwarefor successful large systems

Design (18%)

Coding (7%)

Debugging(25%)

Maintenance(50%)

During design and coding, efforts should be madeto reduce the cost of debugging and maintenance








Design Methods

• Top-down design: From global to detail– Decompose the problem in simpler subproblems– Further decompose subproblems– UNTIL all subproblems have trivial solutions

• Bottom-up design: From detail to global– Solve some small problems that might be useful

for solving the big problem– Use the partial solutions for assembling a global

solution


Example : Repairing a flat tire

• Specifications : – Given : A car with a flat tire– Wanted : Instructions for fixing it

• Strategy choice :– Wait with a smile until somebody fixes it …– Call a repair service> Try to repair yourself


Repairing a flat tire

“Data” and Actions

• “Data”– Car, Defective wheel, Spare wheel, Tools.

• Actions– All that need to be done with the Car, the

Defective wheel, the Spare wheel and the Tools in order to solve the problem.



Top level design of actions

• inspect the spare wheel

• if available & in good condition,

– repair yourself

– else, you will need to call help


Repairing a flat tireRefinement of “repair

yourself”

• fetch the tools

• fetch the spare wheel

• exchange defective and spare wheels

• store defective wheel

• store tools



Refinement of “tools”

• Tools :– jack : device to lift a car– wrench : device to loose or fasten bolts


Repairing a flat tireRefinement of “Exchange defective and spare

wheels”• do loose one bolt with wrench while fastened bolts left;• lift car with jack;• do remove one bolt while bolts left;• remove defective wheel;• put spare wheel in place;• do replace one bolt while bolts missing;• lower car with jack;• do fasten one bolt with wrench while bolts loose;


Object oriented Design

• Problem : – If a data item is slightly changed, the entire

program needs to be checked.

• Solution :– Group data with description of all actions

that can be performed upon such data– Access data exclusively through the actions

predefined for these data

• Object = data + actions to access it.



Object-oriented style

• Instance of the object :• YourJack

• Possible actions :• Fetch = …

• Inspect = …

• Store = …

• Lift a car = …

• Lower a car = …

Object Jack =

Repairing your flat tire…Fetch YourJackInspect YourJackif (ok)… with YourJack Lift YourCar… with YourJack Lower YourCar…Store YourJack…



Decision TableSpare Wheel

Tools

Available & OK

No good tools available

OK Not OK

repairyourself

get help

get help

try toborrowtools



Top-level Controlflowchart

spare wheelOK ?

get help repairyourself

No Yes


Repairing a flat tireRefinement of “repair

yourself”

spare wheelOK ?


No Yes get tools

get spare wheel

change wheel

store bad wheel

store tools


Repairing a flat tireRefinement of “get tools”

tools present & OK ?


pick up the tools

try borrowing tools

NoYes

got tools or tired ?

Yes

Yes

No

No

Help Needed !!!


Repairing a flat tireAdapted refinement of “get tools”


pick up the tools

try borrowing tools

NoYes

got tools or tired ?

Yes

No



Improved top-level designspare wheel

OK ?

No Yes

tools OK ?

fetch tools

Yes

No


Risk :

Spaghetti

Programming !


State Diagrams

Flat tire problemDriving

Flat tire

Need help Goodspare wheel

Repairing

Try borrowtools

Puncture

No goodSpare wheel

Successfulhelp

Nosuccess

Spare wheelOK

Done

Notools Tools

OK

Success


State Diagrams

Electronic lockFirst digitentered

Waiting1st digit

Testing key

Waiting2nd digit

Waiting3rd digit

Second digitentered

Third digitentered

Wrong Key Opening door

Good Key

Closing thedoor by

hand








Assignment Statement

• Assignment operator: in C = (in other languages :=)

– The = used for assignment is fundamentally different from the = used in mathematics.

– In math, the = sign denotes a timeless relation– In C, the = operator describes a particular action:

• The right side expression is evaluated• Its value is stored in the left side variable

– Illustrative example : a = a + 1;

area = pi * radius * radius;


Selection Statement

No

selector = a ? Tasks to be doneif selector = A

Yes

No

selector = b ? Tasks to be doneif selector = B

Yes

No

selector = c ? Tasks to be doneif selector = C

Yes

Tasks to be doneif no criteria OK


if (B) S1 else S2;

B

S2 S1

FALSE TRUE


Iteration Statement

Termination Test

Initialization

Loopbody, part 1

Loopbody, part 2

Continue

Finish


while (B) S ;

B

S

TRUE

FALSES

BTRUE

FALSE

do S while (B)


Function Call Statement

CCC

CCC

CCC

doCCC

doCCC

function DoCCC

end DoCCC

Documents

©J.Tiberghien - ULB-VUB Version 2007 Première partie, chap. 4, page 1 Chapitre 1.4 Langages et outils de programmation