Turtlematic:
a functional approach to aritmetics.

Paolo Passaro
Scuola Media Statale "G. Marconi"
Via Addis Abeba 38, 13051 Biella, Italy
tel: +39 15 401713
fax: +39 15 401704
email: paspal@bielnet.it

Abstract

The author introduces a functional style approach in exploring aritmetics using Logo language. This methodology is the result of a work made inside a project of "Didactics by computer", carried out during the last 8 years. The author thinks that the formalization of knowledge, mainly the mathematics ones, three years goal of italian "scuola media", can be well reached by more and more complex and formal actual calculation "tiny machines". The so said "machinette" can be simulated both phisically and by a Logo procedure.

Keywords

Aritmetics, function, recursion, programming style, designing.

Introduction

Ten years ago we had the idea of using the computer with our classes as an aid to teaching and learning. Apart from problems about hardware buying, then didactics software ready to be used, effective and fascinating, which could give valid help in understanding aritmeticsl and algebraic concepts, were difficult to be found. We tried to build something with the languages at our disposal, tipically Basic or Pascal. The use of such languages showed ( but after two years) ineffective, both for teachers and learners. Moreover these, after the first enthusiasm for the great novelty in studying (in "playing" for a lot of them), lost every interest in solving them. They were not wrong. Before getting something to satisfy them, they had to learn vague and not immediate knowledge. The use of Pascal in Italian "scuola media" is prohibitive, as we consider the absence of any interactivity. The Basic one could be acceptable in many cases, but as soon as we tried to probe the arguments, before getting to something useful, the practicability was lost.

Later, the revision of the project suggested the adoption of Logo enviroment, not like a new discovery, but as a checking of its natural didactic efficiency and educational philosophy ( constructionist, constructivist or else) which the teacher can choose.

1 Functional programming.

The Functional Programming (FP hereafter) unlike other types of programming, is distinguished by its formal elegance, its precision and its clarity.

The first functional language created was LISP, even though historically, Church had presented the l -calculus in the ‘30. The LOGO is closely related to the LISP (from which it has inherited some of its functions and list type).

The FP is based on mathematical function concept or the application among sets:

(i₁, i₂, i₃, i₄, … i_n)à ( u₁, u₂, u₃, … u_m)

in which to a set I of inputs we associate another set U by using the transforming rule F to get results.

In practice the result is simpler being only one, one unmistakable result. The multiple results can be represented by twos, threes, n-th (represented by a vector or a list).

A function is put into operation by a syntax like name(e₁, e₁, e₁,… e_n) where name is the operator related to the function; e₁, e₁, e₁,… e_n are expression said arguments (actual). At the runtime the arguments are substituted or attached to function’s parameters (formal arguments). It’s possible to rappresent any functions by a virtual machine (machinette) in order to do calculations, like the one represented with a symbol as in figure 1.

Figure 1

A fundamental feature of the FP is referencial transparence, which stabilises that a given variable has always the same value in its visual field. This is not true in an imperative program, in which it is normal for a variable to change value in different parts of the program. In the original FP therefore there’s no assignment instructions nor any instructions for an iterative cycle or a jump. The cycle concept can be substituted by the most efficient concept of recursion.

The typical functional environment is the one where the user can interact with the machine by inputing certain expressions and receiving the consequential result from a Functional executor. The form is identical to that used in operating with a numeric calculator:

There are other essential aspects of the FP: a) the derivation from the primitive, b) the composition of the functions and c) the Super order functions..

a) The function scripting is based on a set of a basic functions which in LOGO language are called primitives; it also gives the possibility to use the user functions immediately in other user functions, making the complex program planning easy and elegant.

b) In the function’s composition the result of a calculation goes into the next function and continues in this way until the final result (fig.2).

Figure 2

c) The super order functions are those where the inputs are functions and the ouput is a result or another function.

The trace of a functional calculation is similar in many respects to the one used in arithmetic expression (and algebraic) for successive simplification:

E_nà E_n-1à … E_2à E_1à E₀

Of which Eo is the final expression that cannot be further reduced obtained by means of successive rewriting where the principal rule of mathematics named principle of substitution is applied.

2 Functions with LOGO.

In Logo arithmetic you can use the arithmetic symbols (+, x, -, /) and the relational symbols (<, = , >) in the classical infixed (that is between operand) notation. The most interesting thing is that these symbols can also be used in prefixed (that is before both operand) notation, like a function (I’m referring to the LCSI’s PC Logo, I have not verified it in other version).

In the prefixed functional style LOGO language there exist the primitive functions SUM, PRODUCT, DIFFERENCE and QUOTIENT, besides others that do not have an infixed corresponding symbol like POWER, SQRT, REMAINDER, INTEGER, etc.

Figure 3-4

(Figure 5-10)

However for logical functions AND, OR, NOT there does not exist the related symbols.

Ones approach can be either purist or not, that is strictly respecting the FP canons or deviate from such impositions and write definite functions with a non functional style. In some cases it is quicker to teach students an algorithm by scripting them using a function, but with the imperative style.

The natural functional style however is an exceptional field of study for higher class students.

Scripting new functions is an activity which will arise spontaneously when the students have understood the process and it will become a normality both for primitive and derivative functions to define new ones.

The project plan can be visualized by using coloured card for the primitive function and assembling them to form the machine similar to the new function.

3 Activity and Examples

In this section we present some examples of the use of the functional style in aritmetics. In our project we discuss also about algegra and geometry.

3.1 "Machinette"

The following are elementary examples of machinette that can be realised even by children; their peculiarity is in not holding more than one row of codes and in not using any assignment instructions.

By the counting process ( forward and backwards ) can be defined the tiny-machines NEXT and PREVious:

TO NEXT :N
OUTPUT :N+1
END
TO PREV :N
OUTPUT :N-1
END

With them you can give a simplified version of the arithmetic axioms inside the set N of Natural numbers:

N: [ N₀=0; N₁=NEXT(N₀)… N_n+1=NEXT(N_n)]

So that

n = NEXT(NEXT(NEXT… NEXT(0)…))

The operations of addition (Add) and subtraction (Sub) can be therefore defined in terms of NEXT and PREV with the following recurrent definitions:

Add(a, 0)=a; Add(a, b)=Add(Next(a), Prev(b))
Sub(a, 0)=a; Sub(a, b)=Sub(Prev(a),Prev(b))

TO ADD :A :B
OUTPUT IF EQUAL? :B 0 [:A][ADD NEXT :A PREV :B]
END

TO SUB :A :B
OUTPUT IF EQUAL? :B 0 [:A][SUB PREV :A PREV :B]
END

The understanding of these recurrent definitions and recursion itself is easy to explain and to understand: - ‘To sum two numbers that represent two groups of sweets: while there are sweets in second group two you take from it one at a time and add it to first group…’.

The set N contains all even numbers (2*n) and all odd numbers (2*n+1) (with n=0, 1,2):

TO EVEN :N
OUTPUT 2*:N
END

TO ODD :N
OUTPUT 2*:N+1
END

Putting together Even, Odd, Next and Prev we notice:

Next(Even) is Odd Next(Odd) is Even Prev(Even) is Odd Prev(Odd) is Even

So the definition of Odd numbers can be deducted from the even ones by:

TO ODD :N
OUTPUT NEXT EVEN :N
END

With the construction of the related card machines, the youth discover spontaneously the possible and impossible calculations, variant and invariant properties, commutativity of the operands and of the operators. For example:

Even(Prev) or Even(Next) are always Even

Odd(Prev) or Odd(Next) are always Odd

The interchanging of the operands for SUM and PRODUCT will be verified immediately by the related machines whilst being built will be painted on both sides with the same color. The non-interchanging operands for Difference and Quotient, will be visualised by the non-capsizing machines because they have different colours on two sides.

In the graphic rapresentation of the non-commutative machines we distinguish the first operand with a spot (see DIFFERENCE and QUOTIENT).

Another simple application of the machines is related to the measurement of flat figures like the triangle, the square and the rectangle:

TO SQU.PERIM :SIDE
OUTPUT PRODUCT :SIDE 4
END

TO SQU.AREA :SIDE
OUTPUT PRODUCT :SIDE :SIDE
END

TO RET.PERIM :BASE :HEIGHT
OUTPUT PRODUCT 2 SUM :BASE :HEIGHT
END

TO RET.AREA :BASE :HEIGHT
OUTPUT PRODUCT :BASE :HEIGHT
END

TO TRI.PERIM :SIDE
OUTPUT PRODUCT 3 :SIDE
END

TO POLI.PERIM :SIDE :N
OUTPUT PRODUCT :SIDE :N
END

With these machines the youth can resolve arithmetic problems applied to Geometry drawing the figure with the Turtle and asking in an colloquial style the results of the calculation of a measurement relative to the figure.

Other simple machines are those used for proportions:

TO FOURTH.PROP :A :B :C
OUTPUT QUOTIENT (PRODUCT :B :C) :A
END

TO THIRD.PROP :A :B :D
OUTPUT QUOTIENT (PRODUCT :A :D) :B
END

TO MEDIUM.PROP :A :D
OUTPUT SQRT PRODUCT :A :D
END

Some machines do not output a number but a logical value:

TO PROPORTIONAL? :A :B :C :D
OUTPUT EQUAL? PRODUCT :A :D PRODUCT :B :C
END

3.2 Remainder

LOGO has already the primitive Remainder, but it very useful to build a machine that shows what it is about. Here it is defined by recursion as a repetitive substraction ( until yu cannot take away no-more):

TO MYREMAIN :A :B
OUTPUT IF LESS? :A :B [:A] [MYREMAIN DIFFERENCE :A :B :B]
END

Note the use of IF in the function style form. Remainder is an equivalent of Mod function Pascal’s or Basic’s language and can be used to explain different Algorithm or to construct other useful and important functions e.g. the Greatest Common Divisor (see further).

The following logical machinette can calculate parity:

TO EVEN? :N
OUTPUT EQUAL? 0 REMAINDER :N 2
END

TO ODD? :N
OUTPUT EQUAL? 1 REMAINDER :N 2
(or OUTPUT NOT EVEN? :N)
END

The parity test is extensible to divisibility test in general:
TO DIVISIBLE? :A :B
OUTPUT EQUAL? 0 REMAINDER :A :B
END

This machine invites students to reflect when A and B takes-on particular values and these observations come forth naturally during test.

The youth discover that B=0 it is not good that if A=0 or if B=1 or again A=B the result is always true. From this they deduce spontaneously a lot of divisible criteria and they discover the prime numbers property.

3.3 Expressions as project training.

For a complex expression with many operations you can project a machine that calculate results as in a manual way with pen and paper.

Given E_n as a stating expression it can be substituted by some expressions E₁, E₂, E_m - which composed give the same result and continuing to substitute them until we arrive to a simpler expression that can be calculated using the primitive function or it is a simple value

This, for example starting from...

E_n: 3+5*(17-2)/3 - (18+12)/6à E₁+E₂-E₃

In which E₁=3 E₂=5*(17-2)/3 E₃=(18+12)/6

At this point E₁, can not be simplified anymore, E₂ and E₃ can be simplified into other simpler expressions:

E₂=E₂₁*E₂₂/E₃₃ E₃=E₃₁/E_32.

In Figure11 is shown as example the calculation of expression (a+b)*(c+d).

Figure 11

The process continues until there’s an expression with a value or an operation that can be calculated by the primitive function or the known function.

The following examples are machinettes designed and built by students:

TO EXPRES1 :A :B
OUTPUT PRODUCT 2 SUM :A :B
END

TO EXPRES2 :A :B
OUTPUT SUM PRODUCT 3 :A PRODUCT 2 :B
END

TO EXPRES3 :A :B
OUTPUT SUM PRODUCT :A :A PRODUCT :B :B
END

TO EXPRES4 :A :B :C
OUTPUT SUM PRODUCT :A :A PRODUCT 3 :B :C
END

3.4 Greatest Common Divisor and Least Common Multiple

The greatest common divisor and the least common multiple are machines that are difficult to explain, but once the youth have built them, they will never stop playing with them.

The algorithms for the GCD and LCM calculation normally use the sets of divisors and multiples; they are difficult methods to explain in simple ways to the youth.

The successive-subtraction and the successive-division methods for the GCD calculation are due to Euclide.

In these examples we are using once again the Remainder machine which takes us back to algorithm’s repetitive division.

TO GCD :A :B
OUTPUT IF EQUAL? 0 REMAINDER :A :B [:A][GCD :B REMAINDER :A :B]
END

TO LCM :A :B
OUTPUT QUOTIENT PRODUCT :A :B GCD :A :B
END

The interesting thing about the recursive machines is the visualising of the link between input and Output. This facilitates the feedback concept.

The logical test of end’s condition of cycle can be shown by a flow plan.

3.5 Results with two numbers.

The following examples are an introduction to the use of the list implementing the fractional calculation. A fraction rapresented by a list with two members: first the numerator and last the denominator:

TO FRACTION :A :B
OUTPUT LIST :A :B
END

TO FRACTION? :FRA
OUTPUT IF AND LIST? :FRA EQUAL? 2 COUNT :FRA
END

TO NUM :FRA
OUTPUT FIRST :FRA
END

TO DEN :FRA
OUTPUT LAST :FRA
END

TO GCDF :FRA
OUTPUT GCD NUM :FRA DEN :FRA
END

TO LCMF :F1 :F2
OUTPUT LCM DEN :F1 DEN :F2
END

TO INV :N
OUTPUT QUOTIENT 1 :N
END

TO INV.FRA :F
OUTPUT FRACTION DEN :F NUM :F
END

TO APPLY :FUN :LIS
OUTPUT IF EMPTY? :LIS [[]] [SETFIRST RUN SENTENCE :FUN FIRST :LIS APPLY :FUN BUTFIRST :LIS ]
END

TO RID.FRA :FRA
OUTPUT APPLY SENTENCE [INV QUOTIENT ] (GCDF :FRA) :FRA
END

TO PROD.FRA :F1 :F2
OUTPUT RID.FRA FRACTION PRODUCT NUM :F1 NUM :F2 PRODUCT DEN :F1 DEN :F2
END

TO QUO.FRA :F1 :F2
OUTPUT PROD.FRA :F1 INV.FRA :F2
END

TO SUM.FRA :F1 :F2
OUTPUT RID.FRA FRACTION SUM PRODUCT NUM :F1 DEN :F2 PRODUCT_ NUM :F2 DEN :F1 PRODUCT DEN :F1 DEN :F2
END

Conclusion

The handled theme reenters between the first two subject of discussion of EUROLOGO conference.

–Methology in curriculum content area. What kind of learning does the specific environment invoke? –Learning by developing special features of languange.

The methodology used in the activity promotes different learning aspects:

a) learn by doing, that’s try immediately what being building;

b) build by project, that is know how to analyze a problem, divide it in simpler problems and adopt the fitter models;

c) learn to use the built models, generalizing them for more complex situations up to the formalization.

The immediate results and the small discoveries act on the affective sphere bettering:

a) the respect of oneself and the recognition of the own ability;

b) the relationship with the friends and the teacher and above all with the matter;

c) the curiosity and the pleasure of the discovery.

Probably all this is not new. Nevertheless the big satisfaction that every day we, teacher and learners get, also pushes us to the pleasure of make it known to who believes in LOGO.

References

1. AA.VV., Manuale di Informatica, Calderini, Bologna, Italy 1991
2. Abelson, Hal, and DiSessa, Andrea, Turtle Geometry, MITPress, Cambridge, MA 1981
3. Callegarin, G., L3P - Linguaggio a tre paradigmi, Cedam, Padova, Italy 1993
4. Garavaglia and Petracchi and Graffer, Sistemi, Masson, Milano, Italy 1994
5. Papert, Seymour, Mindstorms, Basic Books, New York, NY 1981
6. Papert, Seymour, The Children’s Machine, Basic Books, New York, NY 1993