5 Think Euphoria

5.1 Fruitful functions

Eu) back next


5.2 Return values

Built-in functions we have used, such as the math functions, produce results. Calling the function generates a value, which we usually assign to a variable or use as part of an expression.

    include std/math.e
    e = exp( 1.0 )
    height = radius * sin( radians )
We have been writing procedures so far; they may print something or such, but they never return a value.

In this chapter, we are (finally) going to write "fruitful" functions. The "fruitful" description is just to remind you that a function always returns a value. The first example is area(), which returns the area of a circle with the given radius:

    include std/math.e

    function area( atom radius )
        atom temp = PI * radius * radius
        return temp
    end function
We have seen the return command before, but in a "fruitful" function the return command includes an expression. This command means: "Return immediately from this function and use the following expression as a return value." The expression can be arbitrarily complicated, so we could have written this function more concisely:

    include std/math.e
    function area( atom radius )
        return PI * radius * radius
    end function
On the other hand, temporary variables like temp often make debugging easier.

Sometimes it is useful to have multiple return commands, one in each branch of a conditional:

    function absolute_value( atom x )
        if x < 0 then
            return -x
        else
            return x
        end if
    end function
Since these return commands are in an alternative conditional, only one will be executed.

As soon as a return command executes, the function terminates without executing any subsequent commands. Code that appears after a return command, or any other place the flow of execution can never reach, is called dead code. In a "fruitful" function, it is a good idea to ensure that every possible path through the program hits a return command. For example:

    function absolute_value( atom x )
        if x < 0 then
            return -x
            end if
        if x > 0 then
            return x
            end if
    end function
This function is incorrect because if x happens to be 0, neither condition is true, and the function ends without hitting a return command. If the flow of execution gets to the end of a function, there is no return value--and an error message is produced:

    ? absolute_value( 0 )
        --attempt to exit a function without a return
By the way, Euphoria provides a built-in function called abs() that computes absolute values.

5.3 Incremental development

As you write larger functions, you might find yourself spending more time debugging. To deal with increasingly complex programs, you might want to try a process called incremental development . The goal of incremental development is to avoid long debugging sessions by adding and testing only a small amount of code at a time.

As an example, suppose you want to find the distance between two points, given by the coordinates (x1 , y1) and (x2 , y2). By the Pythagorean theorem, the distance is:

distance = sqrt( (x2 - x1)2 + (y2 - y1)2 )

The first step is to consider what a distance function should look like in Euphoria. In other words, what are the inputs (arguments) and what is the output (return value)?

In this case, the inputs are two points, which you can represent using four numbers. The return value is the distance, which is a atom value.

Already you can write an outline of the function:

    function distance( atom x1, atom y1, atom  x2, atom y2 )
        return 0
    end function
Obviously, this version doesn't compute distances; it always returns zero. But it is syntactically correct, and it runs, which means that you can test it before you make it more complicated.

To test the new function, call it with sample arguments:

    ? distance(1, 2, 4, 6)
    --  0
I chose these values so that the horizontal distance is 3 and the vertical distance is 4; that way, the result is 5 (the hypotenuse of a 3-4-5 triangle). When testing a function, it is useful to know the right answer.

At this point we have confirmed that the function is syntactically correct, and we can start adding code to the body. A reasonable next step is to find the differences x2 - x1 and y2 - y1. The next version stores those values in temporary variables and prints them.

    function distance(atom x1, atom y1, atom x2, atom y2)
        atom dx = x2 - x1
        atom dy = y2 - y1
        printf(1, "dx is %g \n", dx )
        printf(1, "dy is %g \n", dy )
        return 0
    end function
If the function is working, it should display dx is 3 and dy is 4. If so, we know that the function is getting the right arguments and performing the first computation correctly. If not, there are only a few lines to check.

Next we compute the sum of squares of dx and dy:

    function distance(atom x1, atom y1, atom x2, atom y2)
        atom dx = x2 - x1
        atom dy = y2 - y1
        atom dsquared = dx * dx + dy * dy
        printf(1, "dsquared is: %g ", dsquared )
        return 0
    end function
Again, you would run the program at this stage and check the output (which should be 25). Finally, you can use sqrt() to compute and return the result:

    function distance(atom x1, atom y1, atom x2, atom y2)
        atom dx = x2 - x1
        atom dy = y2 - y1
        atom dsquared = dx * dx + dy * dy
        atom result = sqrt( dsquared )        
        return result
    end function
If that works correctly, you are done. Otherwise, you might want to print the value of result before the return command.

The final version of the function doesn't display anything when it runs; it only returns a value. The output commands we wrote are useful for debugging, but once you get the function working, you should remove them. Code like that is called scaffolding because it is helpful for building the program but is not part of the final product.

When you start out, you should add only a line or two of code at a time. As you gain more experience, you might find yourself writing and debugging bigger chunks. Either way, incremental development can save you a lot of debugging time.

The key aspects of the process are:

  1. Start with a working program and make small incremental changes. At any point, if there is an error, you should have a good idea where it is.
  2. Use temporary variables to hold intermediate values so you can display and check them.
  3. Once the program is working, you might want to remove some of the scaffolding or consolidate multiple commands into compound expressions, but only if it does not make the program difficult to read.

5.4 Composition

As you should expect by now, you can call one function from within another. This ability is called composition . As an example, we'll write a function that takes two points, the center of the circle and a point on the perimeter, and computes the area of the circle.

Assume that the center point is stored in the variables xc and yc, and the perimeter point is in xp and yp. The first step is to find the radius of the circle, which is the distance between the two points. We just wrote a function, distance, that does that:

    radius = distance(xc, yc, xp, yp)
The next step is to find the area of a circle with that radius; we just wrote that, too:

    result = area(radius)
Encapsulating these steps in a function, we get:

    function circle_area( atom xc, atom yc, atom xp, atom yp )
        atom radius = distance( xc, yc, xp, yp )
        atom result = area( radius )
        return result
    end function
The temporary variables radius and result are useful for development and debugging, but once the program is working, we can make it more concise by composing the function calls:

    function_area( atom xc, atom yc, atom xp, atom yp )
        return area( distance( xc, yc, xp, yp ) )
    end function

5.5 Boolean functions

Functions can return boolean values (i.e. false or true), which is often convenient for hiding complicated tests inside functions. For example:

    function is_divisible( atom x, atom y )
        if remainder( x, y ) = 0 then
            return 1
        else
            return 0
        end if
    end function
It is common to give boolean functions names that sound like yes/no questions; is_divisible() returns either ( 0 ) for false or ( 1 ) for true to indicate whether x is divisible by y.

Here is an example:

    ? is_divisible( 6, 4 )
        -- 0
    ? is_divisible( 6, 3 )
        -- 1
The result of the remainder() is a atom, so we can write the function more concisely by returning it directly:

    function is_divisible( atom x, atom y )
        return remainder(  x, y )
    end function
You could use the fact that a value other than zero will also be interpreted as true.

Boolean functions are often used in conditional commands:

    if is_divisible( x, y ) then
        puts(1, "x is divisible by y" )
    end if
It might be tempting to write something like:

    if is_divible(x,y) = 0 then
        puts(1, "x is divisible by y" )
    end if
But the extra comparison is unnecessary.

5.6 More recursion

We have only covered a small subset of Euphoria, but you might be interested to know that this subset is a complete programming language, which means that anything that can be computed can be expressed in this language. Any program ever written could be rewritten using only the language features you have learned so far (actually, you would need a few commands to control devices like the keyboard, mouse, disks, etc., but that's all).

Proving that claim is a nontrivial exercise first accomplished by Alan Turing, one of the first computer scientists (some would argue that he was a mathematician, but a lot of early computer scientists started as mathematicians). Accordingly, it is known as the Turing Thesis. For a more complete (and accurate) discussion of the Turing Thesis, I recommend Michael Sipser's book Introduction to the Theory of Computation.

To give you an idea of what you can do with the tools you have learned so far, we'll evaluate a few recursively defined mathematical functions. A recursive definition is similar to a circular definition, in the sense that the definition contains a reference to the thing being defined. A truly circular definition is not very useful:

frabjuous:
An adjective used to describe something that is frabjuous.
If you saw that definition in the dictionary, you might be annoyed. On the other hand, if you looked up the definition of the factorial function, denoted with the symbol ( ! ), you might get something like this:

      0! = 1 
      n! = n(n-1)!

This definition says that the factorial of 0 is 1, and the factorial of any other value, n, is n multiplied by the factorial of n-1.

So 3! is 3 times 2!, which is 2 times 1!, which is 1 times 0!. Putting it all together, 3! equals 3 times 2 times 1 times 1, which is 6.

If you can write a recursive definition of something, you can usually write a Euphoria program to evaluate it. The first step is to decide what the arguments should be. In this case it should be clear that factorial takes an integer:

    function factorial( integer n )
If the argument happens to be 0, all we have to do is return 1:

    function factorial( integer n )
        if n=0 then
            return 1
        end if
    end function
Otherwise, and this is the interesting part, we have to make a recursive call to find the factorial of n-1 and then multiply it by n:

    function factorial( integer n )
        if n=0 then 
            return 1 
        else
            atom recurse = factorial( n - 1 )
            atom result = n * recurse
            return result
        end if
    end function
The flow of execution for this program is similar to the flow of countdown() shown previously. If we call factorial() with the value 3:

Here is what the stack diagram looks like for this sequence of function calls:

png/05_state2.png

The return values are shown being passed back up the stack. In each frame, the return value is the value of result, which is the product of n and recurse.

In the last frame, the local variables recurse and result do not exist, because the branch that creates them does not execute.

5.7 Leap of faith

Following the flow of execution is one way to read programs, but it can quickly become labyrinthine. An alternative is what I call the "leap of faith." When you come to a function call, instead of following the flow of execution, you assume that the function works correctly and returns the right result.

In fact, you are already practicing this leap of faith when you use built-in functions. When you call cos() or exp(), you don't examine the bodies of those functions. You just assume that they work because the people who wrote the built-in functions were good programmers.

The same is true when you call one of your own functions. For example, previously we wrote a function called is_divisible() that determines whether one number is divisible by another. Once we have convinced ourselves that this function is correct--by examining the code and testing--we can use the function without looking at the body again.

The same is true of recursive programs. When you get to the recursive call, instead of following the flow of execution, you should assume that the recursive call works (yields the correct result) and then ask yourself, "Assuming that I can find the factorial of n-1, can I compute the factorial of n?" In this case, it is clear that you can, by multiplying by n.

Of course, it's a bit strange to assume that the function works correctly when you haven't finished writing it, but that's why it's called a leap of faith!

5.8 One more example

After factorial, the most common example of a recursively defined mathematical function is fibonacci, which has the following definition:

      fibonacci(0) = 0 
      fibonacci(1) = 1 
      fibonacci(n) = fibonacci(n-1) + fibonacci(n-2);

Translated into Euphoria, it looks like this:

    function fibonacci( atom n )
        if n=0 then
            return 0
        elsif n = 1 then
            return 1
        else
            return fibonacci(n-1) + fibonacci( n-2 )
        end if
    end function
If you try to follow the flow of execution here, even for fairly small values of n, your head explodes. But according to the leap of faith, if you assume that the two recursive calls work correctly, then it is clear that you get the right result by adding them together.

png/05_fibonacci.png

5.9 Checking types

What happens if we call factorial and give it 1.5 as an argument?

    ? factorial( 1.5 )
        -- typecheck error
That is because we had, in advance, only allowed integers to be used as an argument to the factorial function.

But, what if we had defined it like:

    function factorial( atom n )
      ...
        end function
Why allow the atom-type at all? Well, the atom-type allows for larger integer values than the integer-type--just in this case it also allows fractional values to slip through.

What happens now is:

    ? factorial( 1.5 )
        -- Killed
It looks like an infinite recursion. But how can that be? There is a base case--when n = 0. But if n is not an integer, we can miss the base case and recurse forever.

In the first recursive call, the value of n is 0.5. In the next, it is -0.5. From there, it gets smaller (more negative), but it will never be 0.

We have two choices. We can try to generalize the factorial function to work with floating-point numbers, or we can make factorial check the type of its argument. The first option is called the gamma function and it's a little beyond the scope of this book. So we'll go for the second.

We can use the built-in function integer() to verify the type of the argument. While we're at it, we can also make sure the argument is positive:

    function factorial( atom n )
        if integer(n) then
            puts(1, "Factorial is only defined for integers." )
            return 0
        elsif n < 0 then
            puts(1, "Factorial is only defined for positive integers." )
            return 0
        elsif n = 0 then
            return 1
        else
            return n * factorial( n - 1 )
        end if
    end function
The first base case handles nonintegers; the second catches negative integers. In both cases, the program prints an error message and returns 0 to indicate that something went wrong:

    ? factorial( "fred" )
        -- error 
        -- atom expected
    ? factorial( -2 )
        -- Factorial is only defined for positive integers
        -- 0
If we get past both checks, then we know that n is a positive integer, and we can prove that the recursion terminates.

This program demonstrates a pattern sometimes called a guardian . The first two conditionals act as guardians, protecting the code that follows from values that might cause an error. The guardians make it possible to prove the correctness of the code.

TOM patch this code using object as input, and reject sequences

5.10 Debugging

Breaking a large program into smaller functions creates natural checkpoints for debugging. If a function is not working, there are three possibilities to consider:

To rule out the first possibility, you can add a output command at the beginning of the function and display the values of the arguments (and maybe their types). Or you can write code that checks the preconditions explicitly.

If the arguments look good, add a print command before each return command that displays the return value. If possible, check the result by hand. Consider calling the function with values that make it easy to check the result.

If the function seems to be working, look at the function call to make sure the return value is being used correctly (or used at all!).

Adding print commands at the beginning and end of a function can help make the flow of execution more visible. For example, here is a version of factorial with print commands:

    function factorial( atom n )
        sequence space = repeat( " ", n )
        printf(1, "%s  factorial %n", {space,n} )
        if n=0 then
            printf(1, "%s returning 1", {space} )
            return 1
        else
            atom recurse = factorial( n - 1 )
            atom result = n * recurse
            printf(1, "$s returning %g", {space, result} )
            return result
        end if
     end function
space is a string of space characters that controls the indentation of the output. Here is the result of factorial(5) :

                     factorial 5
                 factorial 4
             factorial 3
         factorial 2
     factorial 1
 factorial 0
 returning 1
     returning 1
         returning 2
             returning 6
                 returning 24
                     returning 120
If you are confused about the flow of execution, this kind of output can be helpful. It takes some time to develop effective scaffolding, but a little bit of scaffolding can save a lot of debugging.


back next


5.11 Glossary