**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: *

**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_{1}, i_{2},
i_{3}, i_{4},
… i_{n})à
( u_{1}, u_{2},
u_{3}, … 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*_{1}*, e*_{1}*,
e*_{1}*,… e*_{n}*)* where *name* is
the operator related to the function; *e*_{1}*,
e*_{1}*, e*_{1}*,… 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:

result: 5

? SQRT 16

result: 4

? REMAINDER 21 6

result: 3

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_{0}

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.

SUM |
PRODUCT |

**Figure 3-4**

DIFFERENCE |
QUOTIENT |

REMAINDER |
POWER |

NEXT |
PREVIOUS |

**(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}=0; N_{1}=NEXT(N_{0})… 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]

ENDTO 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

ENDTO 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

ENDTO SQU.AREA :SIDE

OUTPUT PRODUCT :SIDE :SIDE

ENDTO RET.PERIM :BASE :HEIGHT

OUTPUT PRODUCT 2 SUM :BASE :HEIGHT

ENDTO RET.AREA :BASE :HEIGHT

OUTPUT PRODUCT :BASE :HEIGHT

ENDTO TRI.PERIM :SIDE

OUTPUT PRODUCT 3 :SIDE

ENDTO 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

ENDTO THIRD.PROP :A :B :D

OUTPUT QUOTIENT (PRODUCT :A :D) :B

ENDTO 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

ENDTO ODD? :N

OUTPUT EQUAL? 1 REMAINDER :N 2

(or OUTPUT NOT EVEN? :N)

ENDThe 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_{1}, E_{2}, 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_{1}+E_{2}-E_{3}In which E

_{1}=3 E_{2}=5*(17-2)/3 E_{3}=(18+12)/6

At this point E_{1}, can not be simplified anymore, E_{2}
and E_{3} can be simplified into other simpler
expressions:

E

_{2}=E_{21}*E_{22}/E_{33}E_{3}=E_{31}/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

ENDTO EXPRES2 :A :B

OUTPUT SUM PRODUCT 3 :A PRODUCT 2 :B

ENDTO EXPRES3 :A :B

OUTPUT SUM PRODUCT :A :A PRODUCT :B :B

ENDTO 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]

ENDTO 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

ENDTO NUM :FRA

OUTPUT FIRST :FRA

ENDTO DEN :FRA

OUTPUT LAST :FRA

ENDTO GCDF :FRA

OUTPUT GCD NUM :FRA DEN :FRA

ENDTO LCMF :F1 :F2

OUTPUT LCM DEN :F1 DEN :F2

ENDTO INV :N

OUTPUT QUOTIENT 1 :N

ENDTO INV.FRA :F

OUTPUT FRACTION DEN :F NUM :F

ENDTO 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

ENDTO PROD.FRA :F1 :F2

OUTPUT RID.FRA FRACTION PRODUCT NUM :F1 NUM :F2 PRODUCT DEN :F1 DEN :F2

ENDTO QUO.FRA :F1 :F2

OUTPUT PROD.FRA :F1 INV.FRA :F2

ENDTO 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**

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