CO1603  Computer Programming

 

Assessment: coursework 30% exam 70%

Textbook

Papert, S. Mindstorms: children , computers and powerful ideas.  Basic Books 1993.  Available from TA Morgen.

Introduction

Do you remember learning your times table (2 times 2 is 4, etc)?  Seymour Papert explains how we can use programming concepts to teach children how to solve problems (like how to juggle) by examining the structure of the problem.  On page 113, he says:

"People are capable of learning like rats in mazes.  But the process is slow and primitive.  We can learn more, and more quickly, by taking conscious control of the learning process, articulating and analyzing our behaviour"

To take control of our learning processes means we absorb and integrate ideas rather than merely remember what our teacher told us to remember.  

Did you know that Bazilian street children can do complex arithmetic much quicker and more accurately than most educated adults?  The street children teach themselves because they have had to assume financial responsibility for their own survival.  Did you know that Australian aboriginal children are better at remembering things and their locations than school-taught children?  In the Australian bush, you have to learn to navigate by creating mental maps of your surroundings so you won't get lost and die because there are no water taps or cellphone towers in the desert.

In this course, we are not learning to become computer programmers, but we are using the idea of constructing a computer program as a metaphor for problem structure discovery.  The key idea is that finding the answer to a problem involves finding the inherent structure of the problem and using that structure to find the answer.

You will get to learn how to do this by doing the three programming projects described in the next section.  I will introduce you the the basic principles by looking at three simple problems:

"how can I tie my shoelaces so they will stay tied but can be easily untied?"
"how can I cross the road without getting run over?"
"what makes robots think and do the things they do?"

Then we will move on to more complex problems such as:

"how many children will I be able to support without falling into debt?"
and "how can I instruct a robot how to walk?"

When you tie your shoelaces or cross the road, most people follow a method they have been taught.  Who invented the method?  I don't know, but someone did, a long time ago.   How are methods invented?  And have you ever found one of your shoelaces coming undone by itself?  Is it possible that you tied them incorrectly because you don't know the structure of the shoelace knot and why it cannot come undone if tied correctly?  If we follow instructions blindly without thinking about how they relate to the structure of the problem the instructions are intended to solve, we are behaving even less intelligently than rats in a maze, for recent experiments with rats have shown that they are capable of creating for themselves a "gestalt" (big picture) of the maze and working out for themselves a quick way to get out.

When you were taught to tie your shoes, probably by your parents, they used the language of your mother tongue.  However, natural languages are not very precise and it is easy to get the wrong idea.   Have you ever said to someone: "I didn't realise that was what you wanted!"  

A computer programming language is a precise language.  When you tell a computer what to do, it does precisely what you say, even if that is not what you meant !

There are many kinds of computer programming languages.  Languages like C++ and Java are designed for general use (ie creating any kind of software).  They are tricky to learn and it takes a long time to learn how to do anything interesting with them.  Others, like the ones we will use, are designed for special use and are more easy to learn.  It doesn't take a long time to learn how to do something interesting and fun with them.

These sites give tutorials on all kinds of computer stuff, including computer programming.  Read them at your own risk!
http://www.lausd.k12.ca.us/Jefferson_HS/lscomp.htm
http://www.free-ed.net/

Exam

You will not need to study or revise for the exam!  Simply doing the projects will teach you all you need to know to pass the exam.

There will be 4 questions of which you answer 3.  

2006 exam

2005 exam

Projects

There are 3 projects: Dollysoft, Logo and Excel.  Each project is worth one third of the coursework marks (ie 10% of overall marks). 

In CO1601, your project work was additional to studying from the book and videos.  But in CO1603, you learn mostly by doing the projects.  So, you should spend roughly

(((2 points * 2 hours per week per point) - 1) * 12 weeks ) / 3 projects
= about 12 hours altogether for each project, over the semester. 

The projects can be done by one or two people (not three) working together.  Teams can be changed without asking me.  You can be on a different team for each project. 

Begin with the Dollysoft project and start the other two as soon as you can.

Each person makes their own website and uploads their three projects to it.   Each project should be a single file.  The website must be a single webpage containing your name, student number, your photo (optional) and hyperlinks to your project files.

In the week before revision week, each team hands in one paper copy of each of its projects.  Write the names of the team members and the URLs of their websites on the first page of the paper copy of each project.  If the same team did all three projects together, you can put them together in a folder.

Dollysoft Project

Dollysoft  http://www.dollysoft.com is a language for making animated 2-D cartoons. The word "dolly" refers to the cinematographer's camera dolly, a device for moving the camera around a scene.

Your task is to make a short cartoon.  Don't ask me how long short is.  There are no notes on Dollysoft here but plenty on its website.  Dollysoft has not been installed in the labs but you can download and install it yourself.  NB.  Submit only the .tal script file of your cartoon (not the huge .avi runfile dollysoft creates from it).  If you are feeling adventurous, you can create your own cartoon character - you could even use a picture of yourself for this purpose and be in your own cartoon....

We can make cartoon scripts that embody some of the essentials of computer program structure: the sequence, the hierarchy, and the repetition.  If you have an enquiring mind you could ask yourself how Dollysoft produces a cartoon from your script.  

Logo Project

Tutorial:  http://www.ecu.edu.au/pa/ecawa/sig/logo/paul_dench/turtle

LOGO was invented for children of all ages.  But it's not just for kids.  Papert's book contains a wonderfully written explanation of how developing and debugging program structures enables you to teach yourself about problem solving by what he calls  "mathetics" = learning by doing (the original, Greek, meaning of "math" is "learning"). 

With Dollysoft, you just tell things where to go.  Dollysoft draws the animation for you.  But with LOGO, you have to tell it (the turtle) how to produce a series of still images that give the viewer a sense of objects moving around.  To do this, you have to figure out the geometry of movement and learn to use program structures, the ones you have already met with Dollysoft, plus two new ones: the conditional instruction and the recursion mechanism. 

Your task is to make a short animated picture.  Use MSLogo (the version on ICTC lab machines) or include a Zip file or the URL of the Logo software you used so i can run your program. 

Excel Project

Tutorial:  http://homepage.cs.uri.edu/tutorials/csc101/pc/excel97/excel.html

Excel's ancestor, called VisiCalc, was the software that made small computers popular with people running small businesses, long before video games and then internet came along and made PCs playthings as well as business tools.  It was designed to be used for business planning, but is also pretty handy for calculating statistics and doing other things with numbers.

Your task is to design a customer survey and create an Excel workbook (ie program) to analyse your data and make an objective assessment of the quality of the campus restaurants (in terms of what you think is important).   There are four restaurants on campus (to which anyone, of either gender) can go: one near the bookshop, one in each of the hostels and one at the sports field.    Get at least 20 people to fill in your survey for each restaurant. 

Make up your own questions and make your own decisions about how Excel should calculate and present its analysis.  

Your Excel workbook should fit on A4 paper (one page per worksheet) when printed and enable visual comparison between all 4 restaurants at a single glance of one page (a picture is worth a thousand words). 

Write a one-page summary report of your recommendations - giving your reasons for them - to each of the restaurant managers.  Include this as the first worksheet in your Excel workbook (not as a separate document).

----------------------------------------------------------------

Finding the structure

An abstract model of a thing is a useful first step in building any kind of complex physical system like a building (architectural plans), aeroplane (engineering drawings) or movie (script).  We use abstraction in the process of writing a program by first sketching out the main ideas and then filling in the details.

But, usually, it's not so simple.   We often have to look at some of the details to work out what the overall picture is.

For example, the bow you use to tie your shoelaces looks like this (with acknowledgements to http://www.fieggen.com/shoelace/standardknot.htm):

Figuring out how to tie it is a knotty problem!  Look carefully.  Can you see any structure in it?  Can you abstract its  form?  

You were probably taught "left over right and then right over left". 

But there's more to it than that!

........................

Let's step back from the problem a bit and think about knots.  

Here is a right-handed "overhand knot":

make left blue
make right mauve
rho (left, right)

where the procedure (function) rho is defined as:

to rho (x, y)
  crossover (y, x)
  holdTheCrossWithYourRightThumbAndForefinger
  tuckBackUnder (y, x)
  foldover (y, x)
  swap (x, y)
end rho

Before rho is put into operation (in computerspeak, we say it is "executed"), left = blue and right = mauve. But afterwards, it is the other way around.  The swap function exchanges the values of the parameters x and y to reflect this.

Now look at the shoelace knot again and compare it with the overhand knot. 

The bottom of the shoelace knot looks a bit like a right-handed overhand knot, but it's the other way around - it's a left-handed overhand knot!

to loh (left,right)
  roh (right, left)
end loh

The procedure loh uses the procedure roh, just as a boss uses a subordinate to do something for her.  This is a hierarchical structure.

Now, what about the rest of it?  To understand how it works and where the idea came from, we have to step back in time to the days of the old sailing ships...........  On a sailboat, when the wind becomes strong, we reduce the sail area by "reefing the sail".   In the old days, this was done by partly lowering the sail, bundling up the excess at the bottom and tying up the bundle under the boom with special reefing lines (like big shoelaces) reeved through the sail's reef points.  Your shoes have two grommets, one on the left and one on the right.  A sail has only one for each reef point but it has a left and right side if you look at it sideways. 

The sail is lowered until the line of reef points is just at the bottom, the clew and tack secured.  The sail is then tightened up, with the tension being taken by the reef clew and tack.  The loose sail left at the bottom is bundled up and the bundle tied (to stop it flapping around) by passing light lines through the reef points and tying them underneath.

picture from http://www.fsanmiguel.com/boat/reefing/reefing.html                 

A Reef knot  is quick to tie and easy to untie.  A reef knot will hold together provided the two long ends are constantly pulling against each other.  But if you let them become loose, and grab one of the short ends and give it a good shake, the knot will unwind and the ropes will fall apart.  For this reason sailors and mountaineers use a different knot (called a sheet bend) to tie two ropes together when they must stay tied tigether under any circumstances. 

picture from http://www.geocities.com/roo_two/reefknot.html

Look at the reef knot on the left.  The bottom part is a left-handed overhand knot.

And the top part is a right-handed overhand knot.

to reef (x,y)
  loh (x,y)
  roh (x,y)
end reef

Can you see that the reef knot looks like two loops pulling each other tight?  Look at the right hand side - both ends go under the loop.  On the left, both ends go over the loop.  So the two loops are pulling each other together, keeping the knot tied.  The two loops pulling against each other is the structure of the reef knot.

The classic error when trying to tie a reef knot is the so-called granny knot because olden time sailormen thought that grannies (grandmothers) can't tie reef knots properly! 

Compare the reef and granny knots.   The granny knot is also made of two overhand knots, but it doesn't have the structure of two loops pulling against each other.  This means the friction between the laces can be lost more easily and the knot can come undone.

Now let's look at the shoelace bow again.  Can you see that the shoelace bow is a kind of reef knot?  If your shoelaces have ever come untied by themselves, it is probably because you tied a granny knot by mistake. 

In the shoelace bow, the second overhand knot (the one on top) is made with looped ends (made by folding the end of the lace back on itself).  Pulling on one of the free ends reduces the structure of the shoelace bow from a looped end reef knot to an overhand knot, which can be easily slid apart. 

to bow (left, right)
  loh (left, right)
  roh (loop (left), loop(right))
end bow

The instruction roh (loop (left), loop(right)) is an example of functional composition.  The value of the variables passed to the parameters of the procedure roh and themselves computed by another procedure called loop.

Notice we can't extend the technique of hierarchical structure all the way to say:

to bow (left, right)
   reef (loop (left), loop (right))
end bow

because only the top (the second) overhand knot uses loops.

Now we have met three kinds of programming construct:

the sequence
the hierarchy
the functional composition (which is a kind of hierarchy)

The two other basic constructs are the repetition and conditional instruction.  And recursion, which is a hierarchy of repetitions.

Let's look at all the constructs together in the context of an important procedure that we as programmers have to perform - correcting our mistakes. 

We make programming mistakes because we have not got the right overall "gestalt" - big picture structure - because we have not properly understood the inherent structure of the task we are trying to tell the computer to do.   The behaviour of the computer gives us feedback we can use to figure out what the actual structure is.

So don't say "stupid computer!".  Say "stupid programmer"!!

Here is where Papert had his great insight.  He realised the relationship between problem structure and program structure and that learning is the process of debugging the structure.  This applies to our own learning of how to do things, how we see the world, how we solve problems. 

Papert first published his ideas over 30 years ago, but most teachers - even many teachers who teach LOGO - still don't understand the point he is making.  But you can.  You will need to read his book as well as practising his ideas by building and debugging your own program structures.

Debugging

In any non-trivial task, we can expect to make mistakes.  The term used for programming mistakes is "bugs".  The term comes from a long time ago when one of the early computers was found to be malfunctioning because a moth had short-circuited some of its wires, getting itself fried by an electric cooker and causing the information the wires were carrying to go the wrong way.

If bugs are found, we must modify the program to remove the bugs. This process is called debugging.  Let's look at how the process works in the context of designing a procedure to perform a process.  Tying a shoelace bow is also a process - to figure out how to do it we looked at the structure of the end result and worked backwards from the answer, using abstraction and decomposition principles.  In the next problem, it is not so easy to see the answer until we have got it.

Let's imagine we are telling a robot how to cross the road safely.   Here is the procedure  I was taught at school; my teacher called it the "Green Cross Code".

look left
look right
look left again
if it is safe, then
walk

Given the density of traffic on most roads, it is unreasonable to insist that there be no vehicle in view, so you must calculate whether you can walk across before any vehicle coming reaches you. This involves estimating the nearest vehicle's distance and speed and taking into account the width of the road and your walking speed. 

In England and Brunei, cars drive on the left hand side of the road. When you look left, you are looking far into the distance to ascertain that no car from that direction could reach you before you make it across the far lane to the other side of the road. The second look left is a double-check, because it takes time to look right and calculate whether it is safe to cross, just in case a car appears from the left during the time you are looking right.  The double-check is a safeguard in case a child doesn't take into account the fact that it takes twice as long to cross both lanes as it does to cross the near lane.

But the Green Cross Code procedure is not efficient - If it's not safe on the left, there's not much point looking on the right!

But what happens if it's not safe?? The robot will simply stay where it is for ever, because it has not been told to look again after the danger has passed!

So what should our program tell it to do?? Well, it has to keep looking until it's safe, that is, it has to look, ask itself "do I see danger?" and if so, wait a bit and then look again in the same direction.:

But in steps 2 and 3 the robot will think to itself that it is safe before it looks.....(because "safe" is the value of the variable called "it" which ended up with the value "yes" at the end of step 1. It should assume it is not safe before looking:

However, there's still a problem: suppose whilst its doing step 3 a few cars come along. The robot will stand there waiting until they pass.  That's good.

But suppose that while it is looking left, a car appears from the right??  Oh dear, what should we do??

The answer is simple: it should only look left once in step 3 so that there is not enough time for a car to appear from the right in time to reach the robot while it's walking across:

But what if it is not safe in step 4?

It has to repeat the whole thing again!

How can we tell it to do that?

Let's restructure our program:

check is another program, called a procedure or subroutine or method by different programming languages. It looks like this:

Gosh! It looks so easy! Why didn't you say so in the first place??!! Well, that's the whole point about programming...once you get it right, it looks straightforward - but it takes a lot of thought to get it right. As Albert Einstein said, "if a thing can be said, it can be said simply" - however, it takes a lot of effort to work out how to say things simply.......we can all understand E=MC² ....it's simple.....so why didn't anyone say it before Albert?.....

.....but is his formula as simple as it looks? What does the square of a speed mean??? Ask your physics teacher... it doesn't mean anything to me, but I do know it took Sisyphus effort to roll that stone up the hill. So he needed energy to be able to exert that effort. The energy needed is the force he needed to move it a unit distance times how far he had to roll it E=FD.   Now Newton believed F=M₀A.  But Einstein says Newton was wrong, F=MA where
M=M₀/sqrt(1-V²/C²) where M₀ is the rest mass and M the mass at speed V and C is the speed of light. 

So E= MAD which is what having to do endless strenuous pointless things makes Sisyphus and us :)  

Logic Programming

Another way of programming is to use logic.  This is more natural for some computational processes. 

For example, imagine a robot computer that has 3 processors: a conscious brain (C), a mammalian brain (M) and a reptilian brain (R). 

The mammalian brain - the limbic system - takes care of emotional processes, the reptilian brain - the brain stem - is concerned with with basic survival body regulatory processes such as heartrate, blood pressure etc and the conscious brain - the cortex - is where the robot thinks it thinks because it doesn't know what is going on in its two (subconscious) brains, although it sends / receives messages to / from them. 

Exactly what consciousness is is still a research question, but there is general agreement among neurophysiologists that the human brain's overall anatomy is pretty much like our robot's. 

Our robot is female.  Her conscious brain has learned from magazines that:

rule C1. "if he looks at another girl, he doesn't love me"

and from ethical instructors that:

rule C2 "it is wrong to use violence"

which we might express in logic as:

C1. looksat (him, anothergirl) -> not (loves (him, me))
C2. (hit (someone1, someone2) -> (bad (someone1) and hurt (someone2))

From television advertisements and personal experiments, she has learned that:

C3. eatchocolate (me) -> feelgood (me)

Her conscious brain is unaware that she also has two subconscious brains.  The mammalian brain contains the following instinctual causal relations concerning emotions, fears, self-esteem and body image:

M1. not (loves (him, me) -> (insecure (me) and mad (me, him))
M2. insecure (me) -> feelbad (me) 
M3. bad (me) -> feelbad (me)
M4. teethfallout (me) -> feelbad (me)

Her reptilian brain, located in her brain stem at the top of her spinal column, contains just one survival rule (crocodiles and us have many more):

R1. mad (me, someone) -> hit (me, someone)

Rule R1 was Napoleon's and Sun Tzu's (and George Bush's?) motto: "attack is the best form of defence".  That's why I called it a survival rule.  In my opinion, Jerry Seinfeld invented a more effective survival rule: "the best revenge is to enjoy life".

The arrow symbol -> denotes "logical implication".  If the statement on its left is true, then we can infer (deduce) the statement on its right is also true.  The principle by which we can do this is called Modus Ponens.  It is an axiom of formal logic systems of mathematics.  An axiom is something that is believed as a basic truth without justification (proof).   Axioms underly all of human reasoning, including but not exclusively our thoughts about things we cannot touch or see.  All commonsense is predicated upon (culturally) common axioms.  These vary from one culture to another.

M2 is a rule that all animals concerned with their survival have.  M3 is a rule that only animals that live in groups or packs have.  Lone hunters don't care what they do to others, but pack animals have built-in instinctive mechanisms that protect the safety of the group from harm by its own members.  We are unaware we have these rules in us, but they have been articulated by people who advocate group safety, who call them ethical rules.

Let's see how our robot reacts to a situation.  If the information looksat (him, anothergirl) is input, rule C1 is triggered which infers not (loves (him, me)) which is passed to the mammalian brain which triggers rule M1 which infers insecure (me) and mad (me, him).  The first part triggers M2 and the second part is passed to the reptilian brain which in turn triggers rule R1 and the action hit (me, him) is carried out.  By the way, crocodiles don't actually get mad (it's a mammalian emotion) - they just get even!

Realisation of having done hit (me, him) is input to the conscious brain and rule C2 is triggered, causing the message bad (me) to be added to her set of feelings.  This causes rule M3 to be triggered again, with the result that feelbad (me) is sent back to the conscious brain which now has to work out a way to deal with a difficult situation created by the robot's reaction to her own action.

The robot has learned rule C3 from television advertisements.   It's a quick fix, as chocolate contains (or mimics) a chemical compound called dopamine or oxytocin or something which is a neurotransmitter which helps signals pass across certain synapses that make you feel good when they are flowing. 

Unfortunately, chocolate also contains a lot of sugar, which saliva converts to acid, which eats away tooth enamel.  Some years later. the robot's body provides the input

 teethfallout (me) 

When the robot discovers this happening, rule M4 is activated, making the robot feelbad again.  No problem!  Rule C3 has the solution: eat more chocolate!

Our robot is self-destructive.  It needs to learn another rule..... the program does not work properly.... it has a bug.   Can you fix it?

Excel Programming

A spreadsheet consists of a grid of cells.  Each cell can contain data (a text string or  a number) or a formula.

Formulas calculates a value based on the values in other cells.   For example, the formula 

=PMT(rate, nper, pv, fv, type)

uses a standard function called PMT which calculates the periodic payment for a loan based on the values of parameters you supply:

rate = interest rate per period
nper = number of payments until repaid
pv = present value of the loan (amount we are borrowing)
fv = future value (just set it to 0)
type = when payments are due: 0= at start of period, 1= at end of period

Conditional Formula

This allows you to calculate a value depending on the value in another cell.

=IF (condition, value-if-true, value-if-false)

Examples:

=IF (A2>1,"Yes","No")

=IF (A6>10000, .08, .05)

(Aside: In order to survive in a varying environment, an organism or robot needs lots of conditional functions to cope with the different things that can happen.  When the different things it does produce behaviours that improve its situation (or at least don't make it worse), we call the organism intelligent.  Appropriateness of response is the essence of intelligent behaviour.  When the world around us changes in a way we had not anticipated (for example, it's starting to get hotter) we need to change our program's conditional instructions so they are appropriate to the new situation.  This is called adaptability.  Adaptability is regarded as the key to evolutionary success.  If a computer program is to survive a change of its environment, it must be adaptable.  Since programs are themselves data, a program-changing program can be written that will produce adaptive behaviour.  Writing self-modifying programs is for advanced programmers, but I thought you might like to know that it is possible)

Copying Formulas

To copy a formula, we can use the copy and paste commands. The cell locations in the formula are pasted relative to the position we copy them from.

Sometimes we want to keep a certain reference absolute - ie not relative.  This is possible by inserting a $ before the Column letter or a $ before the Row number (or both) in the reference.

Formatting Cells

We often want to make our numbers look a certain way (format), such as have a certain number of decimal places, or prefix them with a dollar sign, show them as a percentage, show negative numbers in red, etc.

To format cells,  select a cell (or group of cells) and from the FORMAT menu -- go down to format -- click on number.

Charts

A picture is worth a thousand words (or numbers). Excel's  Chart Wizard  will step you through questions that will draw a chart of your data.  There are many types of charts. The two most widely used are the bar chart and the pie chart.

The BAR Chart is convenient for displaying how something changes over time.

The PIE Chart is usually used to look at how something is divided up.  If you had a pie chart of where you spent your money you could look at the proportions spent on different things.

Here is a simple family planning tool.  I will explain to you how it works in class.
 

LOGO programming

http://pages.intnet.mu/jhbpage/program/logo.htm   

http://el.media.mit.edu/logo-foundation  

http://www.ringsurf.com/netring?ring=logoring;action=list

MswLogo

There are two windows, the MswLogo Screen and the Commander.  The Screen is where your picture will be drawn and the bottom pane of the Commander is where you type in your commands to Logo.

The File menu includes commands that enable you to operate on logo procedure files.  

The Set menu allows you to SET some of the characteristics of how LOGO behaves when drawing.  Don't use it!  Instead, put any Set commands you want inside your program (see later).

A semicolon begins a comment in an instruction line.  Logo ignores characters from the semicolon to the end of the line.  A tilde (~) as the last character still indicates a continuation line, but not a continuation of the comment.

How to write and test a MswLogo program

The following will seem a little weird at first, but it's the easiest way to develop and de-bug your program:

1. start MswLogo

2. Start Notepad

3. in MswLogo Screen,

File...Save A:/myLogoFile

this creates a new file called myLogoFile.lgo

4. in Notepad,

File...Open A:/myLogoFile.lgo

write your program in the file. To make a LOGO procedure called mine, type in:

to mine
put some commands in here
end mine
 
File...Save

5 in MswLogo Screen,

 File...Load A:/myLogoFile.lgo

6. in Commander,

type the name of the TO procedure you want to run (eg mine), press Execute button (or hit Enter key)

7. work out what changes you want to make.  Repeat steps 4 to 7 until it does what you want or until you need a break - your program will be saved in your file ready for the next time you work on it. 

Basic Commands

FD 100  Move the turtle forward 100 steps. 
RT 90  Turn the turtle to the right 90º. 
LT 90  Turn the turtle to the left 90º. 
BK 100  Move the turtle backwards 100 steps. 
PU  Pick the turtle's pen up off the paper. 
PD  Put the turtles pen back down on the paper. 
CS  Clear the screen and start over. 
HT  Hide the turtle (triangle). 
ST  Show the turtle (triangle). 
REPEAT 3 [...]  Repeat the commands 3 times. 


Draw a square using the turtle

FORWARD 100
RIGHT 90
FORWARD 100
RIGHT 90
FORWARD 100
RIGHT 90
FORWARD 100
RIGHT 90

That was easy but too much typing, lets try again.

REPEAT 4 [FD 100 RT 90]

That's it? Yes, that's the same square.  We did two things. We noticed too much redundant code in our first example, so we asked logo to repeat the sequence 4 times.  We also used abbreviated forms of the same commands.  But we can still do better.  A square is a popular item wouldn't you say?  Wouldn't it be more useful just to say square when you wanted a square.

TO SQUARE   
REPEAT 4 [FD 100 RT 90]
END

This only draws squares of 100 by 100.  Wouldn't it be better to draw any size square?  It sure would and it's easy.

TO SQUARE :length
REPEAT 4 [FD :length RT 90]
END

SQUARE 100
SQUARE 200

Note all we did is replace 100 with a variable name called :length.  Now when we call square we must specify how big we want.  Above we asked logo to draw one square at 100x100 and another at 200x200.  Note the ":" in front of the word length tells logo that length is a variable.  However, we can still even do better.  What's wrong now, you ask.  Well wouldn't it be better if we could draw something other than a square like a triangle?

TO TRIANGLE :length
REPEAT 3 [FD :length RT 120]
END

TO SQUARE :length
REPEAT 4 [FD :length RT 90]
END

TO PENTAGON :length
REPEAT 5 [FD :length RT 72]
END

Do you see the general pattern?

TO POLYGON :length :sides
REPEAT :sides [FD :length RT 360.0/:sides]
END

What would a polygon with a huge number of short sides look like?

Building a 'house'

We can build complex structures by putting simpler structures together.  This is hierarchical composition.

For example, we can design a house by first thinking about what parts (procedures) we want and how we would put them together.  Then we fill in the details of each procedure. 

To build a 2-D HOUSE  you could place a TRIANGLE roof on top of a SQUARE wall.

Arrange your procedure so that it is easy to read - like this:

to house
    wall
    roof
end

to wall
  POLYGON 60 4
end

to roof
    rt 60 ; to get the turtle pointing the right way
    POLYGON 60 3
    lt 60 ; so the turtle is pointing up in case we want to add some more things after
end

Now teach your turtle to VILLAGE using your HOUSE procedure. You could teach your turtle to SPACE: a procedure containing the commands it needs to move from HOUSE to HOUSE without drawing a line.  You will need the standard functions pu (= lift pen up) and pd (= put pen down).

Try drawing these compound shapes:

If that was too easy, try drawing these pictures!:

The two bars are actually the same size but B looks bigger.  Why is that?

The "Devil's Triangle" is devilishly tricky - follow the path around starting from one corner and you will see that although at first glance it looks like a 2-D image of a 3-D object, such a 3-D object cannot possibly exist.

Are your eyes watering?  Is your head spinning?  How do they do that?!

....................

Polygonal Flowers

to pol :sides :size
; draws a regular polygon with sides of length size
if :sides>0 ~
  [repeat :sides ~
     [fd :size ~
      rt 360/:sides]]
end pol


to flo :sides :size 
; draws a "flower" of evenly spaced regular polygons
repeat :sides ~
   [pol :sides :size ~
    rt 360/:sides]
end flo

here's what flo 5 60 draws:

here's what flo 30 10 draws:

here's what flo 500 3 draws:

Recursion

"Big fleas have little fleas
To bite 'em
And so on, ad infinitum"

A recursive process has a regular hierarchical structure that can be defined by a single pattern.  The pattern repeats itself within itself. 

Recursive Trees

The following procedure draws trees with branches, one going left and the other going right.  Each branch is the start of a smaller subtree.  The difference in size is a ratio of 0.7.

to tree :size
  if :size < 5 [stop]
  fd :size
  lt 30 tree :size*0.7
  rt 60 tree :size*0.7
  lt 30 bk :size
end
 

here's what tree 60 draws:

0.7 is a very rough approximation to the "Golden Number" discovered by Fibonacci a few hundred years ago which has a mystically magical property:

G = 1 + 1/G

A better approximation would be 0.618.  This ratio turns up all over the place in nature.  Take a look at the book "Fascinating Fibonacci" by Trudi Garland.  It's in the library.

Of course, real trees are not exactly symmetric.  Thery are not always two-branched and sub-branches aren't always at exactly 30 degrees to their predecessor branch.  We could start to simulate nature by introducing a random change to the downsizing ratio of subbranch length, making it somewhere around 0.618 (in the range 0.5 to 1).

to rtree :size
  if :size < 5 [stop]
  fd :size
  lt 30 rtree :size*(((random 5)+5)/10)
  rt 60 rtree :size*(((random 5)+5)/10)
  lt 30 bk :size
end

"random" is a LOGO standard function that produces a pseudo-random number in the range 0 to 5.  By adding 5 to this and dividing by 10, we get a number in the range 0.5 to 1.0.  A different number each time.

here's what rtree 60 draws:

--------------------------------------------------------------------------------

More complex recursion - The "Towers of Hanoi" puzzle

The Towers of Hanoi puzzle is a game of 3 pegs and a number of disks. Each disk has a different size. The puzzle starts with all the disks on one peg, in order of size. The problem is to move the disks from the first peg to the last peg without ever placing a larger disk on top of a smaller one.

How can we solve the puzzle? 

There are three pegs.  To move 2 disks from one peg to another, keeping their order, we can use the third peg as a "temporary holding stage".

move top disk to holding stage
next, move second disk to new peg
next, move the disk in the holding stage on top of the other one on new peg

We can generalise this principle to cope with any number of disks.  Do you see the pattern?

to tower :disks :from :to :using
   if :disks = 1 [move :from :to stop]
   tower :disks-1 :from :using :to
   move :from :to
   tower :disks-1 :using :to :from
end

to move :from :to
   (print "Move "disk "on "peg :from "to "peg :to ".)
end

If you become intrigued by recursion, take a look at fractals!  Here's one, known as Sierpinski's triangle:

to sierp :size
  if :size < 1 [stop]
  repeat 3 [triangle :size]
end

to triangle :size
  repeat 3 [fd :size
            sierp :size/2
            rt 120]
end

Animation

Our eyes do not see things moving.  They see still pictures.   These pictures are sent to our brains, which calculate that something is moving based on how its position in the picture changes.

So we can send a series of pictures with things changing their positions and it will appear as if they are moving.  In cinematography jargon, each picture is called a frame and the rate at which they are shown is called the frame rate.  If the frame rate is too slow, the movements will look jerky.  If it is too fast, we might miss the movement altogether and think they are two different pictures.

Dollysoft creates the frames for you, but in LOGO we have to create them ourselves.  We could draw each frame by hand, but if we take into account the geometry of motion, we can provide formulas for the program to calculate for itself how the object positions should change from one frame to the next. 

A bouncing ball

to ball
   arc 360 20
end ball

to move :y
   pu
   back :y
   pd
end move

to frame
   clean; erases the previous frame
    ball
   wait 60 - :speed
end frame

to bounce :speed
   cs
   ht
   repeat 5 [until [ycor <-200]
                      [frame
                          move - 5]
                    until [ycor=0]
                       [frame
                         move 5]
end bounce

A waving arm (with a blobby hand on the end of it)

to wave
   repeat 10 ~
      [repeat 10 [clean arm wait 6 rt 6] ~
          repeat 10 [clean arm wait 6 lt 6]]
end

to arm
   fd 100 arc 360 5 fd -100
end

A walking man

; the action of walking is more complicated than you might think!
; this was my first attempt

to w1
cs
walker 60 100
end w1

to walker :w :h
repeat 200 ~
[step1 :h wait :w clean ~
pu rt 90 fd :h/4 lt 90 pd
step2 :h wait :w clean]
end walker

to step1 :h
bodyhead :h
leg 145 25 :h
leg 190 15 :h
end step1

to leg :thigh :calf :h
rt :thigh
fd :h/4
rt :calf
fd :h/4
lt 90 fd :h/12 fd -:h/12 rt 90 ;foot
fd -:h/4
lt :calf
fd -:h/4
lt :thigh
end leg

to step2 :h
bodyhead :h
leg 190 15 :h
leg 220 15 :h
end manstep2

to man :h
bodyhead :h
fd -:h/2
fd :h/2
end man

to bodyhead :h
fd :h/2 ;body
head :h
fd -:h/2 ;go back to pelvis
end bodyhead

to head :h
pu
fd :h/8
pd
arc 360 :h/8
pu
fd -:h/8
pd
end head

A smoother, more colourful walking man

;this program contains at least one bug.  it looks as if his legs keep swapping around
; because his bum keeps changing colour
;also, his body looks too long
; can you work out how to fix these bugs?
to w :w
   wrap
   setscreencolor [137 197 228] ;sky blue
   setpensize [3 3]
   cs ht rt 90 pu bk 200 pd lt 90
   pu setpos [-250 40] pd
   make "green [56 123 45]
   make "red [220 43 22]
   make "putih[250 233 231]
   repeat 888 ~
      [make "left :green make "right :red p
       make "left :red make "right :green p]
end w


to p ;pace
   l 0 0
   n :w
   l 0 10
   r 10 30
   n :w
   l -10 20
   r 20 20
   n :w
   l -20 10
   r 30 10
   n :w
   l -30 0
   r 20 20
   n :w
   l -20 10
   r 10 10
   n :w
   l -10 10
   r 0 0
end p

to n :w
   wait :w clean pu rt 90 fd 5 lt 90 pd
end n

to l :h :k ; hip, knee
   setpencolor :left
   s :h :k
   end l

to r :h :k
   setpencolor :right
   s :h :k
end r

to s :h :k ; partial step
   make "leg pencolor
   setpencolor :putih
   bodyhead
   setpencolor :leg
   lt :h
   pu fd 5 pd arc 115+:h 8 pu bk 5 pd ;bum
   bk 40 ;thigh
   rt :k bk 40 ;calf
   fd 4 arc -180 6 bk 4 ;foot
   fd 40 lt :k
   fd 40 rt :h
end s

to bodyhead
   setpensize [12 12]
   fd 40/0.618; 0.618 is the Fibonacci ratio
   setpensize [2 2]
   head 40/1.618/1.618
   setpensize [12 12]
   bk 40/0.618
   setpensize [3 3]
end bodyhead

to head :h
  pu
  fd :h
  pd
  arc 360 :h
  pu
  fd -:h
  pd
end head

When there are several objects moving in different directions, or you want to have a static background, each moving object has to remember where it is from one frame to the next.   I will explain in class how you can do this.