Gregory D. Weber

July 5, 2012

Sifflet Version 2.0

Just as water flows through rivers, and as rivers flow into other rivers and join their waters, so data flows through channels and mingles with other flows of data. Just as factories, sewage processing plants, dams, or power plants on a river may alter its water (unfortunately, often for the worse), so information processing units transform the data that flow through them (but for the better, we hope). We call these processing units functions.

Lesson 1: Simple Algebraic Functions

A company sells two products, A and B, and makes a gross profit¹ of $0.12 per unit of product A and $0.25 per unit of product B.

Start Sifflet by typing this command into a terminal in an X Window session:

sifflet

or, if you want to be able to continue using your terminal before Sifflet finishes:

sifflet &

Sifflet will open two windows: the Function Pad window and the Workspace window. Click on the grossProfit button in the Examples section of the Function Pad window (Figure 1):

Figure 1. The grossProfit button is selected in the Function Pad window.

Figure 1. The grossProfit button is selected in the Function Pad window.

Then move the mouse to the Workspace window and click to deposit a diagram of the gross profit function (Figure 2):

Figure 2. The "grossProfit" function diagram is displayed in the Workspace window.

Figure 2. The grossProfit diagram is displayed in the Workspace window.

This diagram shows a function named grossProfit. A function usually has one or more inputs, called parameters (or arguments); it always produces an output, called the return value (or just value).

The diagram is in a box with three panels.

• The light yellow header panel shows the function name, grossProfit, and the names of its parameters, salesA and salesB. These represent the number of units of products A and B that are sold.

• The light yellow footer panel repeats the names of the parameters.

• In between, the green panel shows how data flow through the function.

The box with these three parts—header, diagram, and footer panels—is called a frame.

When we call a function, we give it specific values for its parameters, run the function, and receive its return value. Since we can call the function again with different values for the parameters, the parameters of a function are variables.

To call the grossProfit function, click on its footer panel, enter two numbers in the input dialog box which opens up (Figure 3), and then click on the OK button:

Figure 3. The input dialog for the "grossProfit" function.

Figure 3. The input dialog for the grossProfit function.

Notice that the frame changes (Figure 4):

Figure 4. The grossProfit frame with inputs.

Figure 4. The grossProfit function, called with parameter values salesA = 320 and salesB = 175.

What's going on? The function is computing its output. Let's look in detail at the diagram and see how this happens.

The smaller boxes within the diagram are called nodes. Each node is a kind of computational unit, but there are different kinds.

• On the bottom of the diagram, we see two nodes that represent the numbers 0.12 and 0.25. These are constants—their values do not change—and they are called literal values or just literals.

• These nodes have small circles on top, called output ports, through which their values may flow out to other nodes.

• Also on the bottom row are two nodes labeled with the names of the parameters. Above each parameter's name, its current value is displayed in pink. (The value cannot change during the current call to the function. But it can change if we call the function again, with different values for the parameters. In this sense, the parameters are variables.)

• At the next level up, there are two nodes labeled with the asterisk (*) symbol, which means multiply.
  These nodes have small circles on the bottom, called input ports, through which data (arguments) flow into them. They multiply their inputs—the two nodes connected to them from below—and produce an output value, which is shown in pink near the top of the node. For example, the * node on the left multiplies 0.12 times the value of salesA, which is 320, and produces the output 38.4. The * nodes are function nodes because * is a function.²

• At the top is a node labeled +. The outputs from the * nodes flow into the + node, which adds them: 38.4 + 43.75 = 82.15. There is a little circle on the top which we could use, if we wanted to process this result further before leaving the function, but we don't, so the output from this node is the final result or value of the function. We say the function returns this value.

Thus, the parameter values in this function call are salesA = 320 and salesB = 175, and the function returns the value 82.15.

You can click on the footer again and enter different parameter values, and the function will (usually) return a different value. But whenever you give it the same parameter values (inputs), it always returns the same value (output). That is the characteristic of a pure function.³

We've used two of the arithmetic functions (also called operators): + and *. Here are four more:

• - (minus) subtracts its second argument from its first (i.e., first − second).
• / divides the first argument by the second (first / second); this always produces a number with a decimal point, called a floating point number, for example 10 / 5 = 2.0, and the result can be inexact due to the limitations of computer arithmetic (we have only a finite number of digits).
• div and mod calculate the integer quotient and remainder of the first argument divided by the second: 25 div 7 = 3, and 25 mod 7 = 4. The results of div and mod are always numbers without decimal points, called integers; they are exact (no round-off error), and their arguments must be (exact) integers: 25.0 div 7.0 is not allowed, and will produce an error.

Expression Trees

The structure in our diagram is called a tree—more specifically, an expression tree, because it represents an expression, which is a computation that has a value.

The top node (+) is called the root of the tree.⁴ The nodes directly connected to it (the two * nodes) are its children, and it is their parent. In general, the nodes directly connected to any node from below are its children, and the node directly connected to it from above is its parent. Thus, the children of the * node on the right are 0.25 and salesB. In a tree, a node can have zero, one, or many children, but it can have only one parent. — The root node, of course, has no parent, and that's what makes it the root. A tree can have only one root; all the other nodes must have parents. The nodes with no children are called leaves.

We started the tutorial with a river metaphor: data flows through processing units (functions) as water through a river, and rivers join together, ultimately joining into one big river which empties into the sea.

But is data also like something that flows through a tree? Of course, sap flows through a tree, but in the trees that are living things, sap flows from the root through the branches to the leaves. In expression trees, data flows in the opposite direction: we start at the leaves and proceed to the root. So it's more like reverse sap. However, at least the sap is moving upwards, since the root is at the top!

And now I shall unveil the mystery of the name: Sifflet stands for Simple vIsual Friendly Functional Language of Expression Trees. Sifflet is as simple as possible in order to be friendly to people aspiring to understand and create programs. The visual aspect should be self-explanatory. It is functional because it deals with pure functions. And the functions are diagrammed using expression trees.⁵

Lesson 2: Editing a Function

The sales price per unit of product, as well as the costs of producing it, can change. Suppose that after some time, the gross profit per unit changes from $0.12 to $0.14 for product A, and from $0.25 to $0.22 for product B. We need to edit (revise) our grossProfit function to bring it up to date.

In the grossProfit frame on the Workspace window, right-click to bring up the context menu and select Edit (Figure 5).

Figure 5. Selecting "edit" from the context menu.

Figure 5. Selecting Edit from the context menu of the grossProfit frame.

An editor window will appear with the title "Edit grossProfit." It shows the same function diagram that we've seen on the Workspace, but with a panel of buttons in place of the footer (Figure 6). Our task is to replace the literal nodes 0.12 and 0.25 with new literal nodes 0.14 and 0.22.

Figure 6. Editing grossProfit.

Figure 6. The "Edit grossProfit" window.

The first step is to delete the literal nodes. In the yellow header or the dark green canvas of the editor window, right-click to bring up its context menu and select the "DELETE" tool (Figure 7).

Figure 7. Selecting DELETE.

Figure 7. Selecting the DELETE tool from the context menu of the "Edit grossProfit" window.

The "Edit grossProfit" window will display "Tool: DELETE" at the bottom, showing that DELETE is the currently selected tool. The DELETE tool acts like an eraser in a graphics program. Click on the two literal nodes to make them disappear (Figure 8).

Figure 8. After deletion.

Figure 8. After deleting the two literal nodes in the "Edit grossProfit" window.

The second step is to make the new literal nodes. Using the context menu, choose the LITERAL tool. The LITERAL tool will open an input box for you to enter the value of the literal (Figure 9). Type in 0.14 and press the ENTER or RETURN key. You can backspace to make corrections, but if you want to cancel the data input altogether, press the Esc key.

Figure 9. Entering a literal value.

Figure 9. Entering a literal value for the LITERAL tool.

Then, click on the canvas to deposit a literal node with the value 0.14. In the same way, select the LITERAL tool, enter the value 0.22, and place a literal 0.22 node on the canvas (Figure 10).

Figure 10. After placing two new literal nodes.

Figure 10. After placing two new literal nodes on the canvas.

The third step is to connect the new literal nodes with the multiply (*) nodes. Again, open the context menu; choose the CONNECT tool. To connect two nodes, you must click on the upper (output) circle of the literal node, and click on the lower left (first input) circle of the multiply (*) node. (It doesn't matter whether you click on the output first or the input first.)

After connecting both pairs of nodes, click on the Apply button (Figure 11) to activate the new definition of grossProfit.

Figure 11. Connected, apply.

Figure 11. After connecting the two pairs of nodes, Apply the new definition.

Look back at the Workspace window. The frame for grossProfit has updated to show the new diagram, and any input and output values it had have disappeared. Again, click on its footer and enter the values for salesA and salesB; the function will now compute gross profit according to the revised definition (Figure 12).

Figure 12. Connected, apply.

Figure 12. Recomputing gross profit with the revised definition.

But why are node output values shown as 44.800000000000004 and 83.30000000000001, instead of exactly 44.8 and 83.3? There is a rounding error resulting from the use of the decimal point in the literal 0.14. Numbers with a decimal point are called floating-point numbers; they are the computer's approximation of real numbers. In Sifflet, a numerical computation is always exact as long as it uses only integer values, but the introduction of a floating-point number causes it to become inexact.

Lesson 3: Conditional Functions

We turn next to a function that takes two numbers as parameters, and returns whichever of them is the larger. Click on the max button in the Examples section of the Function Pad Window (Figure 13):

Figure 13. Function Pad: max

Figure 13. Selecting max from the Function Pad.

Move the mouse to the Workspace window. Click to deposit a frame of the max function on the workspace. Click on its footer to initiate the input dialog, enter 3 as the value of x, enter 2 as the value of y, and click on OK. You should see the function find the maximum of 3 and 2 as in Figure 14:

Figure 14. max 3 2

Figure 14. The max function with x = 3, y = 2.

The top (root) node in this diagram is the if function, which takes three inputs. The first (leftmost) input is a condition (or test) which is either True or False: is x > y? If the condition is True, the if function will select its second input and ignore the third. If the condition is False, it will select the third input and ignore the second. In this case, since x = 3 and y = 2, and 3 > 2, the condition is True, so the if function evaluates its second (middle) input and leaves the third unevaluated. The middle input's value then becomes the value of the if function, and so also the value of the max function. Notice that the frame displays no value at all for y in the rightmost input to if: it is completely ignored.

Now again start the input dialog and this time enter 3 as the value of x, and 4 as the value of y. The max function displays its computation as in Figure 15:

Figure 15. max 3 4

Figure 15. The max function with x = 3, y = 4.

This time, the condition x > y is False, so the if function will ignore its second (middle) input, but it will evaluate its third (rightmost) input, and the value of that will become the value of the if function, and so also the value of the max function. Here again, the other input, in this case the x in the middle, is unevaluated.

Thus, the if function behaves as a switch, which selects its second input if its first input is True, or its third input if its first input is False. The unselected input is never evaluated, because it is not needed.

We've just used the > function, which asks if its first argument is less than its second. This function is one of the six relational operators which are for comparing numbers. Let's look at the rest:

• < asks if its first argument is less than its second.
• <= asks if the first argument is less than or equal to (≤) the second.
• >= asks if the first argument is greater than or equal to (≥) the second.
• == asks if the arguments are equal.
• /= asks if the arguments are unequal (≠).

Exercise 1: Speeding Fines

From the Functions menu, select New ... to begin defining a new function. Let the function name be speedingFine; name its two arguments speed and limit. The argument speed is the driver's actual speed, and limit is the speed limit. The function should compute a driver's fine, if any, for speeding, according to these rules:

1. If the driver's speed is less than or equal to the speed limit, then there is no speeding and therefore no fine, i.e., the fine is 0.
2. Otherwise, the fine is $50, plus an additional $10 for each mile per hour in excess of the speed limit (50 + 10 * (speed − limit)).

Lesson 4: Using a Combination of Functions

A company's president has decreed that if the firm earns a gross profit in excess of $100,000 for the year, then each employee will get a bonus of $1,000 plus $0.0012 for each dollar of gross profit.

From the Function Pad's Examples, select the function bonus1 and place it on the workspace (Figure 16). Study the function and understand how it computes the bonus. The notation 1.2e-3 means 0.0012, i.e., 1.2 × 10⁻³.

Figure 16. The bonus1 function.

Figure 16. The bonus1 function.

Study the diagram and use Sifflet to answer:

• What is the bonus if the gross profit is $99,999.99, and how does the function compute it?
• What is the bonus if the gross profit is $200,000, and how is it computed?
• Now, what is the bonus if the company sells 200,000 units of product A and 750,000 units of product B? You have to use the grossProfit function to determine the value of the profit argument of bonus1 (Figure 17).

Figure 17. Using grossProfit and bonus1 functions together

Figure 17. Using the grossProfit and bonus1 functions together.

Since it's awkward to have to call two functions to answer one question, let's make life easier by combining the two. From the Examples in the Function Pad, select bonus2 and place its frame on the workspace. Note that bonus2 has, instead of one argument, profit, two arguments, salesA and salesB. Call the function with arguments salesA = 200000 and salesB = 750000 to find the answer directly (Figure 18).

Figure 18. Calling bonus2

Figure 18. Evaluating a call to bonus2.

So, how does this work? Well, notice that bonus2 feeds the arguments salesA and salesB into the function grossProfit, then sends the result of grossProfit into the function bonus1. In other words, it's using a combination of two functions that were already defined. Each of the two functions, grossProfit and bonus1, solves a piece of the problem, and by putting them together, we have a solution to the whole problem. The ability to combine and re-use functions in this way is a powerful technique.

But how do we know that grossProfit, when called by bonus2, is doing its calculation correctly? Or what if we just want to see how it's doing its calculation? Sifflet makes it easy to see this: simply left-click on the grossProfit node, and it will expand into a new frame connected to the old node by what might be rays of light (Figure 19).

Figure 19. Calling bonus2

Figure 19. Evaluating a call to bonus2 and inspecting its call to grossProfit.

Similarly, you can click on the bonus1 node to expand it and see how it's getting its result. You may have to drag the frame around to see both the bonus1 and grossProfit frames together.

You can close any of the frames by right-clicking in the frame header and choosing Close from the context menu.

Lesson 5: Recursive Functions

From the Examples in the Function Pad, select fact and click on the Workspace to make its function diagram appear (Figure 20).

Figure 20. factorial function

Figure 20. The factorial function, n!.

This is the factorial function, usually written as n! = 1 × 2 × ... × n. For example, 4! = 1 × 2 × 3 × 4 = 24. But although intelligent human beings understand the "..." as referring to certain missing numbers and multiplication operators, there is no direct way to express "..." in Sifflet, or almost any programming language, and so we have to take a different approach. We can do this by splitting the product: 4! = 1 × 2 × 3 × 4 = (1 × 2 × 3) × 4 = (3!) × 4 = 4 * (3!). Since n = 4 here, this suggests the general formula n! = n * (n − 1)!. This is what we see in the rightmost subtree, the one connected to the third input port of the if node. The sub1 node subtracts 1 from its argument.

Unfortunately, this formula won't quite work, because according to it:

• 4! = 4 × 3!
• 3! = 3 × 2!
• 2! = 2 × 1!
• 1! = 1 × 0!
• 0! = 0 × (−1)!

Since 0 times anything is 0, we must have 0! = 0, and consequently also 1! = 2! = 3! = 4! = 0. There's another problem, of course: we'd have to find the value of (−1)! before we could multiply it by 0, and there doesn't seem to be any end to this process:

• −1! = −1 × (−2)!
• −2! = −2 × (−3)!
• etc.

So in fact we must put an end to it, and the time to make it end is when n = 0. Mathematicians recognize 0! as a special case: 0! = 1. And 1 is the only value that would work here, because it is the multiplicative identity: for any number m, 1 × m = m. In particular, when computing 4!, 1 × (1 × 2 × 3 × 4) = (1 × 2 × 3 × 4) = 24, as expected.

Making the computation stop like this requires the if node and its first two inputs: their meaning is "if n = 0, then the answer is 1." (The zero? node asks if its argument is equal to 0.)

So, putting this all together, we have the two-part formula:

• n! = 1 if n = 0
• n! = n × (n−1)! otherwise.

This is called a recursive function because the function being defined (fact, or !) occurs again (recurs) in the definition. The part in which it recurs is the recursive step, and the other part is the base case.

So, if we evaluate the base case, 0!, the result is pretty straightforward (Figure 21):

Figure 21. 0!.

Figure 21. Computation of 0!.

If we evaluate 4!, we can see the result (Figure 22):

Figure 22. 4! begun

Figure 22. Computation of 4!.

We see that the evaluation of 4! includes the evaluation of 3!, but how is 3! evaluated? Click on the fact node to expand it (Figure 23).

Figure 23. 4! continued

Figure 23. Expanded computation of 4!.

But it doesn't stop there, because evaluating 3! requires evaluating 2!. So, just click to expand all the rest of the fact nodes (Figure 24).

Figure 24. 4! the rest

Figure 24. Expanding 4! the rest of the way.

Now we have uncovered the whole process of evaluating 4!.

Our definition of the factorial function assumes that n ≥ 0. If we violate that assumption, by trying to evaluate (−1)!, we run into a problem (Figure 25).

Figure 25. Stack overflow.

Figure 25. Stack overflow in the attempted evaluation of (−1)!.

You can expand this computation (as before, by clicking on the fact nodes), but you cannot expand it all the way because it never ends! Sifflet provides a limited amount of space for recursive computations, called the stack, and when it runs out of room, we have a stack overflow error.

This is a tutorial on using Sifflet, not a tutorial on recursive functions. Most people who are meeting recursive functions for the first time will need more explanation than this. The Function Pad Examples provide a few more recursive functions, including a few faulty ones: buggySumFromZero, sumFromZero, rmul, fib1, gcd, even?, odd?, rabbitBabies, rabbitAdults, rabbitTotal. If you are taking a university course in computer programming, your professor will be able to explain these examples and may provide additional examples and explanation.

Most programming textbooks cover the topic of recursive functions, but unfortunately the explanations are given using textual rather than visual languages for programming. So, there would seem to be a need for a textbook on recursive programming using Sifflet, but it is not written yet.

Lesson 6: List Functions

A list is a sequence of objects. For example, [1, 3, 5] is a list of numbers. The objects contained in a list are called its elements; in this example, 1, 3, and 5 are the elements of the list. So a list is a kind of "container." A list, being a sequence, stores its elements in a particular order. For example, in the list [1, 3, 5] we see the first element, 1, followed by the second, 3, followed by the third, 5, and that's the last. It is not the same as the list [1, 5, 3], which contains the same elements, but in a different order. So, as a container, a list is more like a conveyer belt than a grocery sack, because the items in a list are in a certain order.

So, most lists contain elements. But just as a sack or a conveyor belt can be empty, so can a list. The empty list, which we write as [], has no elements. The empty list is an important list, just as zero is an important number. One reason is that when building lists, we always start with [].

If a list is not empty, then it has a first element, called the head of the list; and all the remaining elements form a sublist, called the tail of the list. For example, the head of the list [1, 3, 5] is 1, and its tail is [3, 5]. The tail of [3, 5] is [5], and the tail of [5] is []. Of course, [], being empty, has neither tail nor head.

To summarize: a list is either empty, or it consists of a head (the first element) and a tail (the list of all elements after the head).

Exercise 2

1. Create a new function with the name second, with one argument, xs, and with the expression tree shown in Figure 26:

Figure 26. Function second.

Figure 26. The function second.

This function expects a list as the value of xs and will return the second element of xs. How? It applies tail to xs, producing the list of all but the first element of xs (that is, the second, third, and so on). It applies head to the result of tail, producing the first element of that. Now, of course, the first element of the tail of a list, is the second element of the whole list, because the tail begins with the second element of the whole.

2. Evaluate the function with xs = [10, 9, 7] (Figure 27) and observe how it computes the result.

Figure 27. Input dialog for function second.

Figure 27. Calling second with xs = [10, 9, 7].

3. Evaluate the function with xs = [10]. Explain why there is an error.

4. Evaluate the function with xs = []. Explain the error. Note that the error originates in the tail node but is propagated through the head node.

Exercise 2 (continued)

To avoid the errors encountered with second, we need to be able to recognize when a list is empty. The function null in the Function Pad is True when its argument (which must be a list) is empty; False otherwise.

5. Use null (Function Pad) and if (Function Editor context menu) to create a new function named secondOr with two arguments, xs and y, as shown in Figure 28:

Figure 28. Function secondOr.

Figure 28. The function secondOr.

The function returns the second element of xs, if xs has a second element; otherwise it returns y as a "default" value.

6. Evaluate the function secondOr with xs = [] and y = 27, and explain the result.

7. Similarly, evaluate secondOr with xs = [10] and y = 27, and explain the result.

8. Similarly, evaluate secondOr with xs = [10, 9, 7] and y = 27, and explain the result.

Lesson 7: Building Lists

To construct a list we use the function : (Function Pad), pronounced "cons" (as in "construct"), with two arguments: the first argument becomes the head of the new list, and the second argument becomes the tail.

Exercise 3

1. Create the new function buildList with arguments x and y as shown in Figure 29:

Figure 29. The function buildList.

Figure 29. The function buildList.

2. Evaluate the function with x = 21 and y = 37. Explain the result.

3. List elements can be any type of value; they do not have to be numbers. A string is a sequence of characters (letters, digits, punctuation, etc.). String literals are written in double quotation marks: for example, "cat" is the string of three letters c, a, t. Evaluate the function buildList with arguments x = "cat", y = "dog". Be sure to type the quotation marks around the strings, as shown in Figure 30.

Figure 30. String arguments for buildList.

Figure 30. Entering string arguments for buildList.

4. We can also have lists of lists! Evaluate the function buildList with arguments x = ["mouse"], y = []. Be sure to type the brackets, [], and quotation marks, "", as shown in Figure 31.

Figure 31. List arguments for buildList.

Figure 31. Entering list arguments for buildList.

Lesson 8: Recursive List Functions

Remember: a list is either empty, or it consists of a head (the first element) and a tail (the list of all elements after the head). This statement can be understood as a recursive definition of list, and we will often find it useful as a way of structuring recursive functions that process lists.

Examples

Experiment with four functions found in the Examples section of the Function Pad.

1. The length function. "What is the length of a list?" means "How many elements does it have?" A list is either empty or not empty. If it's empty, then, of course, it contains zero elements (base case). If it's non-empty, then its head is one element, and there are as many more as there are elements in the tail, so we apply length to the tail and add 1 (recursive step).

   Evaluate the length function with xs = [10, 9, 7]. Remember, you can open up a recursive node to unveil its details.

2. The buggyLength function is almost just like length. Evaluate buggyLength with the same value of xs, and explain why it gives the wrong result.

3. The sum function expects its argument, xs, to be a list of numbers. It returns the total of all the numbers in xs. Try it with xs = [10, 9, 7] and explain how it computes the result.

4. The buggySum function is almost just like sum. Try it with the same value of xs, and explain why it terminates with an error.

Lesson 9: Menus and Shortcuts

Function Shortcuts

In the Function Pad, note the functions add1 and sub1, which add one to and subract one from their argument, respectively. Also the comparison functions: zero? asks if its argument is equal to zero, positive?, greater than zero; negative?, less than zero. All of these are "shortcuts" for common patterns; we could use +, -, ==, >, and < if we didn't have them. Experiment with them to be sure you understand what they do.

File and Functions Menu Commands

The File Menu contains the commands Save, Save as, and Open, so you can save your functions and work with them again later. Function definitions are saved in an XML document format. Sifflet does not require that you use any particular file extension for saving your work, but you might want to use ".sfl".

Most File Menu commands have keyboard shortcuts, shown in parentheses. C-key means hold down the Control key and press key; for example, C-o means Control + O.

The Functions Menu has commands to create a new function and to show the Function Pad (if it is hidden). Note that the keyboard shortcut for new function is just n, without the Control key. Just press n to start creating a new function.

Function Editor Operations

We've used the function editor a few times, but now I'll point out a few other operations:

• DISCONNECT (d) is used to disconnect nodes. It's the opposite of CONNECT (c), of course. Select the DISCONNECT tool, click on each of the two connected ports, and the connection vanishes.
• MOVE (m) is used to move nodes.
  • Using the MOVE tool, you can drag a node. If there are too many crossed lines, this can clear up your workspace. The effects of moving nodes last only until you Apply the function definition; Apply will automatically re-arrange the tree to look good.
  • Using the MOVE tool with the Shift key held down, if you drag a node, you will also drag everything in the subtree which begins at that node. Try it!
• FUNCTION (f) and LITERAL (l) allow you to type in the name of a function or a literal value. Sifflet will show a list of completions for function names. Press ENTER to use the value typed in, or, to cancel the function or literal input, press the escape (Esc) key.

All of the function editor operations have keyboard shortcuts, as shown in parentheses in the context menu. For example, just press i to start using the IF tool. The keystroke shortcut for the DELETE tool is the Del key in the numeric keypad. — Did I say "shortcut"? It's really a "longcut." It's deliberately placed a long way from everything else so that you don't accidentally delete things.

Lesson 10: Higher Order Functions

Version 2.0 of Sifflet introduces partial (and still somewhat buggy) support for higher order functions.

Okay, what are those?

Suppose we've got a list of numbers, like [5, 10, 20, 7], and we want to do the same thing to each number in the list: add one to it. This would give us [6, 11, 21, 8]. This, by the way, is called mapping the function add1 over a list. Here's a Sifflet function named add1List which does the trick:

Figure 32. add1List in action

Figure 32. The function add1List, in action.

Exercise 4

1. Define the function add1List, as shown in the figure 32, and test it. Be sure you understand how it works. Remember that you can click on the recursive calls to expand them.

2. Define sub1List, which is like add1List except that it subtracts one, instead of adding one, for every element in a list of numbers. (Use sub1.)

3. Similarly, define squareList, which takes a list of numbers and returns a list of their squares. You'll also need to define square to square a single number.

Now, we could keep doing this with all sorts of other functions on numbers, but this is getting tedious, isn't it? The functions are all alike, except that where the original function used add1, the later functions use some other function that applies to a single number. There should be an easier way.

And there is.

Defining the map Function

These functions all have the same structure, and in fact they're exactly alike except for two details: their names are different, and they each call a different function: see Figure 33.

Figure 33. Three similar mapping functions

Figure 33. Three similar mapping functions.

There's a pattern here, which we can and should generalize. To generalize, we need a parameter, f, which will stand for add1, sub1, square, or whatever function we want to apply to the elements in the list. And we'll call the generalized function itself map (remember, we are mapping the function f over the list).

To generalize from Figure 32, then, we'll just replace add1 with f, and replace add1List with something like map f. The result will look like this:

Figure 34. The map function

Figure 34. The map function.

The map function is called a higher-order function because it takes another function, f, as a parameter.

Okay, that's the idea. Now let's get going and actually define map in Sifflet. Start with the "New Function" dialog, as usual. Name the function "map", and give the parameters names as "f" and "xs":

Figure 35. New Function "map"

Figure 35. The New Function dialog for the map function.

Create the nodes and link them up, as shown above in Figure 34. You'll find that you get stuck because the f nodes have no input ports; one of them needs to receive input from the head node, but there is no place to let it in:

Figure 36. A problem connecting head to f

Figure 36. The f nodes have no input ports, so how can one of them get input from head?

We need to tell Sifflet that f needs an input port, because it is a function. To do this, click on the "Parameters" button to open the "Edit Parameters" dialog:

Figure 37. Edit Parameters

Figure 37. Edit Parameters dialog.

In the "Inlets" (input ports) column, change the "0" for parameter f to a "1" and click on "OK":

Figure 38. Edit Parameters, continued

Figure 38. Edit Parameters, continued.

We see now that the f nodes have sprouted input ports:

Figure 39. New input ports.

Figure 39. The f nodes with their new input ports.

We only need one of them, so connect to it from head, and leave the other unused:

Figure 40. f now has input

Figure 40. f with input from head.

Then click on "Apply," to finish the map function definition and make it usable:

Figure 41. Apply map definition.

Figure 41. The map function definition after "Apply."

Using the map Function

Now what? Remember we started with three similar functions, add1List, sub1List, and squareList, and defined map as a generalization of all three, with the function parameter f? If we use map with f = add1, we get a function which is equivalent to add1List. Or we can just edit and simplify our definition of add1List to use map:

Figure 42. Redefining add1List

Figure 42. Redefining the add1List function, using map.

It now looks ridiculously simple, right? Let's see how it works when we apply it:

Figure 43. Applying the revised add1List

Figure 43. Applying the simplified add1List function.

We have the same result as before, [6, 11, 21, 8]! Hooray!

Notice that the value of the symbol add1 is displayed as <primfunc add1>. This means "the primitive function named add1". Primitive functions are the most basic functions that are built into Sifflet. They are binary code, so they cannot be displayed in any more meaningful way than this.

But how does the new add1List work? Remember, you can click on map to expand the call, and you can keep expanding the recursive calls until all mysteries are explained:

Figure 44. Expanding the calls to map

Figure 44. Expanding the calls to map.

Exercise 5

1. Redefine sub1List using the map function.

2. Redefine squareList using the map function.

Now weren't those awfully easy?

Exercise 6

This should be more challenging.

1. Define the function filter, which takes two parameters. The first parameter, f, is a function which is applied to each element of the list; it returns True or False. The second parameter, xs, is a list. The value returned by filter is a list of all the elements in xs for which f returns True. For example, if filter is applied with f = positive? and xs = [5, −7, 0, 12, −3], it should return [5, 12].

2. Using filter, define a function which takes a list of numbers as an argument, and returns the list of those numbers that are positive.

Higher Order Functions: Conclusions

1. A function, such as map, which takes another function as a parameter, is called a higher order function. That is, these functions take functions as inputs. Functions like map and filter provide tremendous power where otherwise we would have to define a bunch of other complicated functions that had the same structure and only trivial differences, like add1List, sub1List, and squareList.

2. If we are going to use functions as parameters to other functions, it would be nice to have a convenient way of creating little functions on the fly, to be the values of those parameters. For example, map lets us easily define add1List, because we have the add1 function. But what if we wanted to add 2 to every element in a list of numbers? We don't have an add2 function, so we'd have to define it. And what about add3? There's a whole class of functions like this, that simply add a constant (a different constant for each function) to their arguments. Wouldn't it be great to have a function to create these functions, for example, an adder function which, applied to 2, produces a function that adds 2 to its argument? In other words, a function that gives a function as its output. This would be another kind of higher order function. Sifflet does not yet support this second kind of higher order function; we will have to wait for a future release for that.

A higher order function, then, is a function which takes a function as input (a function parameter) or gives a function as output (a function return value). In Sifflet, you can create and use the first kind, but not yet the second kind.

Lesson 11: Exporting Sifflet Functions to Other Languages

Sifflet can "export" the functions you've defined into Scheme, Python 3, and Haskell programming languages. All three exporters are located in the File menu.

Exporting to Scheme

From the File menu, choose Export to Scheme ..., and then select an output file, typically with the file extension .scm.

The Scheme Export Options dialog will ask, "Use lambda in function definitions?" Answer "Yes" if you want your Scheme function definitions to use lambda (IU style), like this:

(define foo (lambda (x) ...))

Answer "No" if you want them to omit lambda (MIT style), like this:

(define (foo x) ...)

In the generated Scheme source file, the definitions of your functions will be near the top. Below your definitions will be some additional functions that may be needed for exported Scheme functions; this begins with the comment line,

;;; Sifflet function library for Scheme

If your implementation of Scheme supports an import or load function, you can put this library into a separate file and import or load it from your main file.

Exporting to Python 3

From the File menu, choose Export to Python3 ... and then select an output file, probably with the extension .py. The exporter will write two files: a file containing your exported functions, with the name you selected; and a file named sifflet.py, which is the Sifflet library for Python 3. The file sifflet.py should normally be in the same directory with your other Python file.

Note that if your functions use lists, the generated Python code does not use native Python lists (array-based lists), but a kind of list (a linked list) which is more natural for Sifflet and for functional programming in general. In sifflet.py, the supporting types and functions for linked lists are provided. This module allows you to use functions like head and tail and the other list functions used in Sifflet. You can create a linked list with the function li, and convert them to and from Python's native lists using ll_to_al and al_to_ll:

>>> li(5, 7, 9)
li(5, 7, 9)
>>> ll_to_al(li(5, 7, 9))
[5, 7, 9]
>>> al_to_ll([5, 7, 9])
li(5, 7, 9)

Exporting to Haskell

From the File menu, choose Export to Haskell ... and then select an output file, obeying normal Haskell source file name rules such as capitalization and the extension .hs.

The exporter will write a statement in the Haskell file like this:

import Data.Number.Sifflet

This statement directs Haskell to read the definitions of Sifflet's number type and related functions, which are different from normal Haskell numbers in that they may be exact or inexact. These definitions are found in the Data.Number.Sifflet module of the library sifflet-lib, which is part of Sifflet. So if Sifflet is installed on the computer, then Haskell will know where to find this module. The module is needed for some, but not all, Sifflet functions. If Haskell complains that your code does not use Data.Number.Sifflet, then you can safely remove the import statement.

The Sifflet version 2.0 Haskell exporter is in the early stages of development. Known limitations are:

• Sifflet does not generate Haskell type declarations. The code should still work, because Haskell can infer the types.
• Importing Data.Number.Sifflet actually loads the entire sifflet-lib package, much more code than what is really needed to run the exported functions.

The Future of Sifflet

Sifflet is far from finished. Here's what to expect in future releases.

New Features to Be Expected

These are some of the features I plan to add to Sifflet:

• Improved support for higher-order functions
  • Fix those bugs!
  • Allow functions that create and return functions.
• Tree data types, and/or a facility for users to define new data types.
• Improvements to exporters:
  • Add explicit type declarations (for Haskell).
  • Additional exporters (probably for Java and JavaScript)

Features Not to Be Expected

Here's something that I do not plan on ever adding to Sifflet:

• Import from various programming languages. Sifflet's export will use only a small subset of the languages it exports to, so it is not reasonable to expect Sifflet to be able to import an arbitrary program in any of these languages.