Working document



Download 120.99 Kb.
Date conversion05.08.2017
Size120.99 Kb.
Haggis

Working document

Greg Michaelson & Quintin Cutts

G.Michaelson@hw.ac.uk

Q.Cutts@glasgow.ac.uk


Contents


Evolution 2

Introduction 4

Types 4

System entities 5



Identifiers 6

Variable introduction 6

Commands 6

Assignment 6

Command sequences 7

Blocks 7


Parallelism 7

Condition 7

Repetition 7

Iteration 7

Operations 8

Coercions 9

Selection 9

Comment 9

Elision 9

I/O 9


Sub-programs 11

Object Orientation 13

Graphics 15

GUI 15


Grid GUI 16

Choices 16

GUI Example 1 18

GUI Example 2 19

Derek Middleton SQA Exam Examples 22

Quintin Cutts Assessment at SQA Examples 24

Jeremy Scott Smartphone Student Examples 26



Evolution


  • to do

    • explicit type signatures?

    • side effects?

  • 14/1/14

    • ARRAY size clarified

    • unknown size ARRAY variable definition

    • corrected floating point definition

    • “-“ no longer permitted in identifiers

    • commands in condition/repetition bodies

    • added draft OO

  • 20/12/13

    • OPEN, CLOSE, CREATE

    • end of file

    • reordered so GUI at end

  • 9/9/13

  • 24/6/13

    • SEQUENCE indices start at 0

    • removed PROCEDURE/FUNCTION BEGIN

    • added RETURN as last to be executed in PROC/FUNC

  • 21/6/13

    • added ^ exponent

    • changed && to AND, || to OR, == to =, != to ≠

    • changed examples at end to reflect previous changes



  • 13/6/13

    • added REF & VAL options for parameters



  • 22/5/13

    • added procedures & functions



  • 18/3/13

    • integer divide now explicitly rounds down

    • mixed type arithmetic has explicit coercions

    • introduced STRING append &



  • 11/12/12

    • rewritten to reflect National 5 document: SET/SEND/RECEIVE/END X

    • revised GUI notation to reflect above changes

    • added GUI example

    • revised Derek/Quentin/Jeremy examples accordingly





Introduction


Haggis is a joint venture by Greg Michaelson and Quintin Cutts to produce a notation suitable for posing programming assessments for all levels of the Scottish Qualifications Agency, Curriculum for Excellence, Computing Science curricula, as well as courses elsewhere.

The design philosophy is that Haggis should:



  • not be based on any one extant programming language;

  • be easily translatable into and out of most programming languages used in Scottish schools;

  • be suitable for qualifications up to Advanced Higher/University first year, while also being amenable to sub-setting as appropriate for earlier year qualifications;

  • be intuitive (whatever that means...);

  • be succinct but relaxed about there being different ways of expressing the same thing;

  • be orthogonal, that is unitary constructs should have meanings in different contexts;

  • not expose conceptual details if they are not germane.

We would like to thank David Bethune (SQA), Paul Cockshott (Glasgow) and Richard Connor (Strathclyde) for ongoing discussion about the Haggis specification and evolution.

Types


Haggis is typed but types are not exposed if obvious from context. Haggis is mostly monomorphic and mostly indifferent to issues of implicit/explicit, weak/strong and static/dynamic typing.

The base types and their values are:



  • INTEGER: -big ... + big – where big is arbitrary

  • REAL: -big.small ... + big.small – where big and small are arbitrary

    • floating point notation is also fine: +/- big1.smallEbig2 == big1.small times 10 to the power big2

  • BOOLEAN: true & false

  • CHARACTER: ‘character

The structured type is:

  • SEQUENCE: arbitrary length sequence of values of arbitrary type

SEQUENCEs are addressed from index 0.

This encompasses:



  • ARRAY: finite length sequence of same type

  • STRING: ARRAY of CHARACTER

  • TUPLE : finite length sequence of different type

  • RECORD: finite length sequence of different type with named fiields

  • STREAM: SEQUENCE of CHARACTER

    • this encompasses FILE & URL

Finite length structured type values may be denoted explicitly as:

  • ARRAY: [value,...]

  • TUPLE: (value,...)

  • RECORD: (name=value,...)

  • STRING: “character character...” == [‘character’,’character’,...]

File names are STRINGs.

The GUI types are:



  • WINDOW: SEQUENCE of GUI types with implicit IMAGE

  • LABEL: displays STRING

  • BUTTON: causes EVENT

  • TEXTBOX: returns STRING

  • MENU: SEQUENCE of BUTTON or MENU

  • IMAGE: with means of extracting/changing sub-images and drawing graphics

System entities


System entities include:

  • DISPLAY: in effect the default WINDOW

  • KEYBOARD: in effect the default TEXTBOX

  • MOUSE: with means of determining movement & button clicks

  • TIME: with means of extracting date/time information from year to milli-second

Identifiers


Identifiers are the usual sequences of letters and digits and “.” and “_”.

Variable introduction


Variables may be introduced explicitly by declaration:

  • VAR idunknown type

  • VAR id [size] – ARRAY of unknown type & known size

  • type idid can only be associated with type values

  • type id [size] – ARRAY of known type & size

  • VAR [] id – ARRAY of unknown type & size

  • size type id [] – ARRAY of known type & unknown size

size is a sequence of size type values

Variables may be introduced implicitly by first use on the left of an assignment:



  • SET id TO value – introduces id of same type as, and initialised to, value

    • includes initialisation of structured types

Commands


Commands include:

  • assignment

  • command sequences

  • blocks

  • parallelism

  • conditions

  • repetitions

  • iterations

  • sub-program calls

Assignment


SET id TO expression

  • assignment i.e. change value associated with id to that of expression

    • see above for type implications

Command sequences


Commands one line after another are implicitly in top to bottom sequence, subject to block rules below.

Command sequences may be made explicit on one line with “;” as a separator, not a terminator.


Blocks


Contiguous blocks of sequential commands may be identified in the context of an parent command and terminated with command specific end markers.

Blocks determine the scope and extent of any variables they introduce.


Parallelism


PARALLEL commands1 AND commands2 AND... END PARALLEL

Condition


IF expression THEN commands END IF

IF expression THEN commands ELSE command END IF

WHEN expression DO commands END WHEN


  • expression evaluates to an EVENT

  • in PARALLEL, END WHEN may be omitted before AND and END PARALLEL

Repetition


REPEAT commands END REPEAT

  • never terminates

REPEAT expression TIMES commands END REPEAT

WHILE/UNTIL expression DO commands END WHILE



REPEAT command sUNTIL/WHILE expression END REPEAT

Iteration


FOR id FROM expression1 TO expression2 DO commands END FOR

FOR id FROM expression1 TO expression2 STEP expression3 DO command END FOR

FOR EACH id FROM expression DO commands END FOR EACH


  • expression returns a structured value

  • the order of value extraction form the value is probably first to last

DO may be omitted if commands is indented

Operations


Haggis provides the usual infix and prefix operations on INTEGER and REAL:

  • minus: - unary

  • add: +

  • subtract: -

  • multiply: *

  • divide: /

  • exponent: ^

INTEGER divide rounds down.

In addition, INTEGER has:



  • modulo: mod

Arithmetic may be mixed mode and is coerced:




INTEGER

REAL

INTEGER

I

R

REAL

R

R

The binary comparison operators are:

  • equality: =

  • inequality: ≠ (or !=)

  • less than: <

  • less than or equal: <=

  • greater than: >

  • greater than or equal: >=

Comparisons apply to all finite types, where equality is defined to be element by element.

Order comparisons on structured types imply alphabetic order or equivalent.

The logical operators are:


  • conjunction: AND

  • disjunction: OR

  • negation: NOT

Expressions are bracketed by (...).

All structured types have the operator:

append: &

STRING append with mixed types coerces non-STRINGs to STRING representation.


Coercions


(type) preceding an expression will coerce the value of that expression to the type, if such coercion makes sense

(INTEGER) coercing a real value will round that value down to the nearest integer.


Selection


All SEQUENCE types may be accessed by: id[index]

Fields of RECORD types may be accessed by: id.name


Comment


A comment of the form #text may appear on a line on its own or at the end of a line.

Elision


<text> (i.e. text bracketed by <...>) may be used instead of any command or expression.

I/O


RECEIVE id FROM source

  • input next value from source to id

  • source may be:

    • KEYBOARD

    • id associated with TEXTBOX

    • file path

  • first access to file source opens file

  • source may be preceded by a coercion (type)

SEND expression TO target

  • append value of expression in standard form to target

  • target may be:

    • DISPLAY

    • id associated withLABEL or BUTTON

    • file path

  • first access to file target creates new file

empty(path)

  • returns true if file associated with path is empty

The following optional commands may be used to explicitly open, create and close files:

OPEN path



  • opens extant file associated with path for input or output by context of use

CREATE path

  • creates new file associated with path

  • new file replaces any extant file

  • does not open file

CLOSE path

  • closes file associated with path

A typical sequence for an extant file would be:

OPEN path

process using path

CLOSE path

A typical sequence for a new file would be:

CREATE path

OPEN path

process using path

CLOSE path

Note that the string for a path may be associated with a variable and that variable used in I/O i.e.

SET id TO path

RECEIVE ... FROM id/SEND ... TO id

OPEN/CREATE/CLOSE id

...empty(id)...


Sub-programs


We explicitly distinguish:

  • procedure: control abstraction

  • function: expression abstraction

At simplest, parameter-less procedure definitions have the form:

PROCEDURE id()



...

END PROCEDURE

and parameter-less function definitions have the form:

FUNCTION id()

...

END FUNCTION



The last command to be executed in a FUNTION must always be:

RETURN expression

Parameter-less procedures and functions are called by:

id()

in control and expression contexts respectively.

For a function call, it is implicit that the return expression should have a type which is consistent with the calling context.

For functions, the definition may be optionally preceded by the return type:



type FUNCTION id()

...


END FUNCTION

so the return expression must have that type.

For procedures and functions with parameters, the identifier is followed by a sequence of comma separated formal parameter identifiers:

PROCEDURE id(id1,id2,...idN)

...

FUNCTION id(id1,id2,...idN)



...

It is a Haggis convention that occurrences of formal parameters in procedure and function bodies should be in italics, or underlined in non-digital media.

Procedures and functions with parameters are called by:

id(exp1,exp2,...expN)

It is implicit that the actual parameter expi has the same type as the formal parameter idi.

Formal parameters may be optionally preceded by their types:

PROCEDURE id(type1 id1,type2 id2,...typeN idN)

...

FUNCTION id(type1 id1,type2 id2,...typeN idN)



...

No assumptions are made about the mode of parameter passing. However, formal parameters may also be optionally preceded by:



  • REF – call by reference

  • VAL – call by value

Object Orientation


Classes are defined by:

CLASS id [INHERITS id]

...

END CLASS



Haggis has single inheritance.

Classes may contain:



  • variable introduction –fields

  • procedure/function definitions –methods

  • constructor definitions:

CONSTRUCTOR id(id1,id2,...idN)

...


END CONSTRUCTOR

A class id may appear anywhere that type may appear.

New instances of objects are constructed by:

CONSTRUCT id(exp1,exp2,...expN)

There are implicit constructors for SEQUENCE types:

e.g. INT x[];

SET x TO CONSTRUCT INT[23];

Fields of objects are selected by:



exp.id

Methods of objects are invoked by:



exp.id(id1,id2,...idN)

For example:

CLASS stack

INT sp;


INT MAX;

INT s[];


CONSTRUCTOR stack(INT n)

SET SP TO 0;

SET MAx to n;

SET s TO CONSTRUCT INT[n];

END CONSTRUCTOR

PROCEDURE push(INT v)

IF sp=MAX THEN

SEND “stack overflow” TO DISPLAY

ELSE

SET s[sp] TO v;



SET sp TO sp+1;

END PROCEDURE

INT FUNCTION pop()

IF sp=0 THEN

SEND “stack underflow” TO DISPLAY

RETURN 0;

ELSE

SET sp TO sp-1;



RETURN s[sp];

END FUNCTION

END CLASS

The object oriented form:



exp.id(parameters)

has the procedural equivalent:



id(exp,parameters)


Graphics


Graphics may be in pen or co-ordinate mode.

Generic commands include:



  • clear() – clear drawing area

  • lineWidth(integer)

Pen commands:

  • penUp()

  • penDown()

  • penHome() – sets pen facing north

  • penRotate(+/-degrees)

  • penMove(distance)

  • penColour(colour)

  • etc

Co-ordinate commands:

  • line(x1,y1,x2,y2)

  • drawColour(colour)

  • fillColour(colour)

  • drawRectangle(x,y,height,length)

  • drawCircle(x,y,radius)

  • etc

GUI


A basic WINDOW is implicitly a column of rows.

Constructs are implicitly resized sensibly as they are added to a WINDOW.

ADD id1 TO id2


ADD [...] TO id

  • [...] specifies a column of GUI constructs

  • so each construct in [...] added on next row of WINDOW associated with id

ADD[ ...[...]...] TO id

  • nested [..] specifies a row of GUI constructs

  • so each constructs in nested [...] added along same row

ADD [...[...[...]...]...]

  • inner [...] specifies a sub-column on a row

Use id1.id2 to disambiguate elements in different windows with same name where id1 is window and id2 is element

NB DISPLAY is default WINDOW so after adding elements to DISPLAY don’t need to use nominate “DISPLAY.” explicitly

NB KEYBOARD is an implicit TEXTBOX shared by all WINDOWs.

Grid GUI


Each element is same size.

WINDOW id[r]



  • id has integer r rows of same size

WINDOW id [r][c]

  • id has integer r rows of integer c columns

access using indices

Choices


To set text on GUI construct:

a)

BUTTON stop



SET stop to “STOP”

b)

BUTTON stop(“STOP”)



c)

BUTTON stop

stop.setText(“STOP”)

Not mutually exclusive...

Generalised problem is notation for changing arbitrary GUI construct properties:


  • size

  • colour

  • font

  • visibility

  • enabled

GUI Example 1



w



COUNTER



title



counter

27



+

RESET



plus

reset

WINDOW w


LABEL title

SET title to “COUNTER”

LABEL counter

SET counter TO 0

BUTTON plus

SET plus to “+”

BUTTON reset

SET reset TO “RESET”

ADD [title,counter,[plus,reset]] TO w

PARALLEL


WHEN plus.clicked() DO

SET counter TO counter+1

AND

WHEN reset.clicked() DO



SET counter TO 0

END PARALLEL


GUI Example 2



c



0



keys

1

3



2

4

6



5

7

9



8

CLEAR


ENTER

0


enter



zero

clear
WINDOW c

LABEL padDisplay

BUTTON keys[3][3]

BUTTON clear, zero, enter

SET padDisplay TO 0

FOR i FROM 0 TO 2

FOR j FROM 0 TO 2

SET keys[i][j] TO 3*i+j+1

END FOR

END FOR


SET clear TO “CLEAR”

SET zero TO 0

SET enter TO “ENTER”

SET c TO [padDisplay,keys,[clear,zero,enter]]

PARALLEL

WHEN keys[i][j] DO

SET padDisplay TO 10*padDisplay+2* i+j+1

AND


WHEN zero DO

SET padDisplay TO 10*padDisplay

AND

WHEN clear DO



SET padDisplay TO 0

AND


WHEN enter DO

SEND padDisplay TO DISPLAY

END PARALLEL

Derek Middleton SQA Exam Examples


AH 2011

lower TO

higher TO

FOR counter FROM lower TO upper DO

SET temp TO distance[counter]

SET distance[counter] TO distance[upper-counter]

SET distance[upper-counter] TO temp

END FOR


AH 2011

SET lower TO

SET upper TO

REPEAT


SET middle TO (lower+upper)/2

IF search_value>list[middle] THEN

SET lower TO middle+1

ELSE


SET upper TO middle-1

END IF


UNTIL list[middle]=search_value OR lower>upper

END REPEAT

IF search_value=list[middle] THEN

SEND [“Search item was found at”,middle] TO DISPLAY

ELSE

SEND “Search item is not in list” TO DISPLAY



END IF

AH 2009


FOR counter FROM 1 T0 DO

IF array[counter]>array[counter+1] THEN

SET temp TO array[counter]

SET array[counter] TO array[counter+1]

SET array[counter+1] TO temp

SET swap TO true

H 2010

FOR EACH current IN list DO



IF current.gender = “M” OR current.gender = “F” THEN

SET current.valid TO true

ELSE

SET current.valid TO false



END IF

END FOR


H Comp 2010

FOR floor_no FROM 1 TO 38 DO

FOR room_no FROM 1 TO 25 DO

SEND [“Floor number:”,floor_no] TO DISPLAY

SEND [“Room number:”,room_no] TO DISPLAY

END FOR


SEND [“\n”,”\n”] TO DISPLAY

END FOR

Quintin Cutts Assessment at SQA Examples


Slide 7

alienOnWheels.neck01.turn(left,1)

alienOnWheels.neck01.turn(left,2)

spiderRobot.turn(left,2)

spiderRobot.neck.head.turn(left,2)

Slide 8 (noting that “eskimo” should be “inuit”...)

PARALLEL

eskimoGirl.say(“Hello”)

AND

eskimoGirl.move(up,0.5)



AND

eskimoGirl.move(down,0.5)

END PARALLEL

Slide 9


PARALLEL

eskimoGirl.say(“Hello”)

AND

eskimoGirl.move(down,0.5)



eskimoGirl.move(up,0.5)

PARALLEL


eskimoGirl.say(“Hello”)

END PARALLEL

eskimoGirl.move(down,0.5)

eskimoGirl.move(up,0.5)

eskimoGirl.say(“Hello”)

PARALLEL


eskimoGirl.move(down,0.5)

AND


eskimoGirl.move(up,0.5)

END PARALLEL


Jeremy Scott Smartphone Student Examples


p12

WHEN ButtonPet.Click() DO

Sound.Play()

Sound.Vibrate(500)

END WHEN

p13


WHEN AccelerometerSensor.Shaking() DO

Sound.Play()

Sound.Vibrate(500)

END WHEN


p14

PARALLEL


WHEN ButtonCat.Click() DO

CanvasAnimal.BackgroundImage <== “cat.png”

Sound.Play()

AND


WHEN ButtonDog.Click() DO

CanvasAnimal.BackgroundImage <== “dog.png”

Sound.Play()

AND


WHEN CanvasAnimal.Dragged(startX,startY,prevX,prevY,

current,currentY,draggedSprite) DO

Sound.Play()

END PARALLEL

p16

PARALLEL


WHEN ButtonBlue.Click() DO drawColour(Blue)

AND


WHEN ButtonGreen.Click() DO drawColour(Green)

AND


WHEN ButtonRed.Click() DO drawColour(Red)

AND


WHEN DrawingCanvas.Touched(x,y,touchedSprite) DO

drawCircle(x,y,10)

AND

WHEN ButtonWipe.Click() Do clear()



AND

WHEN ButtonSmall.Click() DO lineWidth(5)

AND

WHEN ButtonBig.Click() DO lineWidth(15)



AND

WHEN DrawingCanvas.Dragged(startX,startY,prevX,prevY,

current,currentY,draggedSprite) DO

line(prevX,prevY,current,currentY)

END PARALLEL

p19


SET brushSize TO 5

WHEN ButtonBigBrush.Click() DO

brushSize < brushSize+1

lineWidth (brushSize)

END WHEN

p20


WHEN ButtonSave.Click() DO

TinyDB1.StoreValue(“FingerPainting.png”,DrawingCanvas.Save())

END WHEN

p22


SET brushSize TO 0

WHEN ButtonBigBrush.Click() DO

lineWidth (brushSize)

SET brushSize TO brushSize+1

END WHEN

p27


WHEN ButtonReset.Click() DO

SET LabelHitsNumber.Text TO hits

SET LabelMissesNumber.Text TO misses

SET misses TO 0

SET hits TO 0

END WHEN


p31

make_text(counter,tableNumber,tableNumber*counter)

p35

WHEN ButtonCreateTable.Click() DO



IF is_text_empty(TextBoxTableNumber.Text)

NotifierErrorBox.ShowMesageDialog

(“You must enter a number”,”Error”,”OK”)

ELSE


SET tableNumber TO TextBoxNumber.Text

TableHeader()

END WHEN

p40


WHEN LocationSensor.LocationChanged(latitude,longitude,altitude) DO

SET LabelCurrentLocation.Text TO

make_text(“Current location:”, “\n”,LocationSensor.CurrentAddress)

END WHEN


p41

WHILE password ≠ ”sesame” DO

Notifier.ShowAlert(“Wrong password!”)

END WHILE





The database is protected by copyright ©ininet.org 2016
send message

    Main page