-
Notifications
You must be signed in to change notification settings - Fork 6
/
Fruitful_func.tex
1266 lines (1046 loc) · 38.1 KB
/
Fruitful_func.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
\chapter{Fruitful Subroutines}
\label{fruitchap}
Most of the Raku functions we have used, such as the math
functions, produce return values. But most of the subroutines
we've written so far are void: they have an effect, like
printing a value, but they don't have a return value. In
this chapter you will learn to write fruitful functions.
\section{Return Values}
\index{return!value}
Calling a fruitful function generates a return value,
which we usually assign to a variable or use as part
of an expression:
\begin{verbatim}
my $pi = 4 * atan 1;
my $height = $radius * sin $radians;
\end{verbatim}
%
Many of the subroutines we have written so far are void.
Speaking casually, they have no usable return value; more
precisely, their return value may be {\tt Any}, {\tt Nil},
{\tt ()}, or {\tt True}.
In this chapter, we are (finally) going to write fruitful subroutines.
The first example is {\tt area}, which returns the area of a circle
with the given radius:
\begin{verbatim}
sub area($radius) {
my $circular_area = pi * $radius**2;
return $circular_area;
}
\end{verbatim}
%
We have seen the {\tt return} statement before, but in a fruitful
function the {\tt return} statement includes
an expression. This statement 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:
\index{return!statement}
\index{statement!return}
\begin{verbatim}
sub area($radius) {
return pi * $radius**2;
}
\end{verbatim}
%
On the other hand, {\bf temporary variables} like
\verb'$circular_area' can make debugging easier. They
may also help document what is going on.
\index{temporary variable}
\index{variable!temporary}
Sometimes it is useful to have multiple return statements, for
example one in each branch of a conditional:
\begin{verbatim}
sub absolute_value($num){
if $num < 0 {
return -$num;
} else {
return $num;
}
}
\end{verbatim}
%
Since these {\tt return} statements are in an alternative
conditional, only one runs.
This could also be written more concisely using the statement
modifier syntax:
\begin{verbatim}
sub absolute_value($num){
return -$num if $num < 0;
return $num;
}
\end{verbatim}
%
Here again, only one of the return statements runs: if the
number is negative, the first return statement is executed and
the subroutine execution stops there; if the number is
positive or zero, then only the second return statement is
executed.
As soon as a return statement runs, the function
terminates without executing any subsequent statements.
Code that appears after an unconditional {\tt return} statement,
or any other place the flow of execution can never reach,
is called {\bf dead code}.
\index{dead code}
In a fruitful function, it is a good idea to ensure
that every possible path through the program hits a
{\tt return} statement. For example:
\begin{verbatim}
# WARNING: faulty code
sub absolute_value($num){
if $num < 0 {
return -$num;
}
if $num > 0 {
return $num;
}
}
\end{verbatim}
%
This subroutine is incorrect because if {\tt \$num} happens to be 0,
neither condition is true, and the subroutine ends without hitting a
{\tt return} statement. If the flow of execution gets to the end
of a function, the return value is {\tt ()}, which basically
means ``not defined'' and is clearly not the absolute value of 0:
\index{undefined value}
\begin{verbatim}
> absolute_value(0)
()
\end{verbatim}
%
By the way, Raku provides a built-in function called
{\tt abs} that computes absolute values.
\index{abs function or method}
\index{function!abs}
\label{compare}
As an exercise, write a {\tt compare} subroutine that
takes two numbers, {\tt \$x} and {\tt \$y}, and returns {\tt 1}
if {\tt \$x > \$y}, {\tt 0} if {\tt \$x == \$y}, and
{\tt -1} if {\tt \$x < \$y}.
Solution: \ref{sol_compare}
\index{compare function}
\index{function!compare}
\section{Incremental Development}
\label{incremental.development}
\index{development plan!incremental}
\index{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
{\bf 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.
\index{testing!incremental development}
\index{Pythagorean theorem}
As an example, suppose you want to find the distance between
two points, given by the Cartesian or rectangular coordinates
$(x_1, y_1)$ and $(x_2, y_2)$. By the Pythagorean theorem,
the distance is:
\index{Pythagorean theorem}
\index{Cartesian coordinates}
\index{coordinates!Cartesian}
\index{rectangular!coordinates}
\index{coordinates!rectangular}
\begin{displaymath}
\mathrm{distance} = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}
\end{displaymath}
%
The first step is to consider what a {\tt distance} function should
look like in Raku. In other words, what are the inputs (parameters)
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 represented by
a numeric value.
Immediately you can write an outline of the function:
\begin{verbatim}
sub distance($x1, $y1, $x2, $y2) {
return 0.0;
}
\end{verbatim}
%
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:
\begin{verbatim}
> distance(1, 2, 4, 6);
0.0
\end{verbatim}
%
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.
\index{testing!knowing the 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
$x_2 - x_1$ and $y_2 - y_1$. The next version stores those values in
temporary variables and prints them:
\begin{verbatim}
sub distance($x1, $y1, $x2, $y2) {
my $dx = $x2 - $x1;
my $dy = $y2 - $y1;
say '$dx is', $dx;
say '$dy is', $dy;
return 0.0;
}
\end{verbatim}
%
If the function is working, it should display \verb"$dx is 3" and
\verb"$dy is 4" (and still return 0.0). 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 {\tt \$dx} and {\tt \$dy}:
\begin{verbatim}
sub distance($x1, $y1, $x2, $y2) {
my $dx = $x2 - $x1;
my $dy = $y2 - $y1;
my $dsquared = $dx**2 + $dy**2;
say '$dsquared is: ', $dsquared;
return 0.0;
}
\end{verbatim}
%
Again, you would run the program at this stage and check the output
(which should be 25).
Finally, you can use the {\tt sqrt} built-in function to compute
and return the result:
\index{sqrt function}
\index{function!sqrt}
\begin{verbatim}
sub distance($x1, $y1, $x2, $y2) {
my $dx = $x2 - $x1;
my $dy = $y2 - $y1;
my $dsquared = $dx**2 + $dy**2;
my $result = sqrt $dsquared;
return $result;
}
\end{verbatim}
%
If that works correctly, you are done. Otherwise, you might
want to print the value of {\tt \$result} before the return
statement.
The final version of the subroutine doesn't display anything when it
runs; it only returns a value. The {\tt print} statements we wrote
are useful for debugging, but once you get the function working, you
should remove them. Code like that is sometimes called
{\bf scaffolding} because it is helpful for building the program
but is not part of the final product.
\index{scaffolding}
When you start programming, 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:
\begin{enumerate}
\item 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.
\item Use variables to hold intermediate values so you can
display and check them.
\item Once the program is working, you might want to remove some of
the scaffolding or consolidate multiple statements into compound
expressions, but only if doing so does not make the program
difficult to read.
\end{enumerate}
Note that, at least for relatively simple cases, you can also
use the REPL to test expressions and even multiline statements
or subroutines in interactive mode before you commit them to your
program code. This is usually fast and can save you some time.
\index{REPL}
\index{interactive mode}
\label{hypotenuse}
As an exercise, use incremental development to write a function
called {\tt hypotenuse} that returns the length of the hypotenuse of a
right triangle given the lengths of the other two legs as arguments.
Record each stage of the development process as you go.
Solution: \ref{sol_hypotenuse}.
\index{hypotenuse}
\section{Composition}
\index{composition}
\index{function composition}
As you should expect by now, you can call one function from within
another. 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 {\tt \$x-c} and
{\tt \$y-c}, and the perimeter point is in {\tt \$x-p} and {\tt \$y-p}. The
first step is to find the radius of the circle, which is the distance
between the two points. We just wrote a function, {\tt
distance}, that does that:
\begin{verbatim}
my $radius = distance($x-c, $y-c, $x-p, $y-p);
\end{verbatim}
%
The next step is to find the area of a circle with that radius;
we just wrote that, too:
\begin{verbatim}
my $result = area($radius);
\end{verbatim}
%
Encapsulating these steps in a function, we get:
\index{encapsulation}
\begin{verbatim}
sub circle-area($x-c, $y-c, $x-p, $y-p) {
my $radius = distance($x-c, $y-c, $x-p, $y-p);
my $result = area($radius);
return $result;
}
\end{verbatim}
%
The temporary variables {\tt \$radius} and {\tt \$result} are useful for
development and debugging, but once the program is working, we can
make it more concise by composing the function calls:
\begin{verbatim}
sub circle-area($x-c, $y-c, $x-p, $y-p) {
return area distance($x-c, $y-c, $x-p, $y-p);
}
\end{verbatim}
%
The last line of the previous example now works like a data
pipeline from right to left: the \verb'distance' function
takes the four arguments and returns a distance (the radius)
which is fed as an argument to the \verb'area'; with this
argument, \verb'area' is now able to return the area, which
is then returned by \verb'circle-area' to the caller code.
We'll come back later to this very expressive data pipeline
model.
\index{pipe-line programming}
\section{Boolean Functions}
\label{boolean}
Functions can return Boolean values, which is often convenient for hiding
complicated tests inside functions. For example:
\index{Boolean function}
\begin{verbatim}
sub is-divisible(Int $x, Int $y) {
if $x % $y == 0 {
return True;
} else {
return False;
}
}
\end{verbatim}
%
It is common to give Boolean functions names that sound like yes/no
questions; \verb"is-divisible", for instance, returns either
{\tt True} or {\tt False} to indicate whether {\tt x} is
divisible by {\tt y}.
Here is an example:
\begin{verbatim}
> is-divisible(6, 4);
False
> is-divisible(6, 3);
True
\end{verbatim}
%
The result of the {\tt ==} operator is a Boolean value, so we
can write the subroutine more concisely by returning it directly:
\begin{verbatim}
sub is-divisible(Int $x, Int $y) {
return $x % $y == 0
}
\end{verbatim}
%
If there is no return statement, a Raku subroutine returns the
value of expression on the last code line of the subroutine
(provided the last code line is an expression that gets evaluated), so that the
{\tt return} statement is not required here. In addition,
since 0 is a false value and any other integer a true value,
this could be further rewritten as follows:
\begin{verbatim}
sub is-divisible(Int $x, Int $y) {
not $x % $y
}
\end{verbatim}
The {\tt Int} type declarations in the subroutine signatures above
are not necessary. The subroutine would work without them, but
they can provide some form of protection against using this
subroutine with faulty arguments.
Boolean functions are often used in statement modifiers:
\index{statement modifier}
\index{modifier!statement}
\begin{verbatim}
say "$x is divisible by $y" if is-divisible($x, $y);
\end{verbatim}
%
It might be tempting to write something like:
\begin{verbatim}
say "$x is divisible by $y" if is-divisible($x, $y) == True;
\end{verbatim}
%
But the extra comparison is unnecessary: {\tt is-divisible}
returns a Boolean value that can be interpreted directly by
the {\tt if} conditional.
\label{isbetween}
As an exercise, write a function \verb"is-between(x, y, z)" that
returns {\tt True} if $x \le y \le z$ or {\tt False} otherwise.
Solution: \ref{sol_isbetween}.
\section{A Complete Programming Language}
We've seen in the section above several ways of writing a
subroutine to check the divisibility of two integers.
\index{divisibility}
In fact, as briefly mentioned earlier, Raku has a
``is divisible'' operator, \verb'%%', which returns
{\tt True} if the number on the left is divisible by
the one on the right:
%\index{%%!is divisible operator}
\index{is divisible operator}
\begin{verbatim}
> 9 %% 3
True
> 9 %% 4
False
\end{verbatim}
So there was no need to write the {\tt is-divisible} subroutine.
But don't worry, that's all right if you did not remember that.
Speakers of natural languages are allowed to have different
skill levels, to learn as they go and to put the language
to good use before they know the whole language. The same
is true with Raku. You (and I) don't know all about Raku
yet, just as we don't know all of English. But it is in fact
``Officially Okay in the Perl and Raku Culture'' to use the subset of
the language that you know. You are in fact
encouraged to use what is sometimes called ``baby Perl'' or ``baby Raku''
to write programs, even if they are somewhat clumsy at the
beginning. That's the best way of learning Raku, just as using
``baby talk'' is the right way for a child to learn English.
\index{baby Perl}
\index{Perl culture}
\index{baby Raku}
\index{Raku culture}
The number of different ways of accomplishing a given task,
such as checking whether one number is divisible
by another, is an example of one of Perl's and Raku's mottos:
\emph{there is more than
one way to do it}, oft abbreviated TIMTOWTDI. Some ways may be
more concise or more efficient than others, but, in the Perl and Raku
philosophy, you are perfectly entitled to do it your way,
especially if you're a beginner, provided you find the correct
result.
\index{there is more than one way to do it}
\index{TIMTOWTDI}
\index{Turing!complete language}
\index{language!Turing complete}
\index{Turing, Alan}
\index{Turing!thesis}
We have only covered a small subset of Raku so far, but you
might be interested to know that this subset is a {\em complete}
programming language, which means that essentially 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 mouse,
disks, networks, 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 {\em Introduction to the
Theory of Computation}.
\section{More Recursion}
\label{more.recursion}
\index{recursion}
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:
\begin{description}
\item[Vorpal] An adjective used to describe something that is vorpal.
\index{vorpal}
\index{circular definition}
\index{definition!circular}
\end{description}
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:
%
\begin{eqnarray*}
&& 0! = 1 \\
&& n! = n (n-1)!
\end{eqnarray*}
%
This definition says that the factorial of 0 is 1, and the
factorial of any other (positive integer) 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.
\index{factorial!function}
\index{function!factorial}
\index{recursive definition}
If you can write a recursive definition of something, you can
write a Raku program to evaluate it. The first step is to decide
what the parameters should be. In this case it should be clear
that {\tt factorial} takes a number\footnote{It should really be an
integer, but we'll get back to that later in this chapter.}:
\begin{verbatim}
sub factorial($n){
}
\end{verbatim}
%
If the argument happens to be 0, all we have to do is return 1:
\begin{verbatim}
sub factorial($n){
if $n == 0 {
return 1;
}
}
\end{verbatim}
%
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$:
\index{factorial!using recursion}
\begin{verbatim}
sub factorial($n){
if $n == 0 {
return 1;
} else {
my $recurse = factorial($n-1);
my $result = $n * $recurse;
return $result;
}
}
\end{verbatim}
%
The flow of execution for this program is similar to the flow of {\tt
countdown} in Section~\ref{recursion}. If we call {\tt factorial}
with the value 3:
Since 3 is not 0, we take the second branch and calculate the factorial
of {\tt \$n-1}...
\begin{quote}
Since 2 is not 0, we take the second branch and calculate the factorial of
{\tt \$n-1}...
\begin{quote}
Since 1 is not 0, we take the second branch and calculate the factorial
of {\tt \$n-1}...
\begin{quote}
Since 0 equals 0, we take the first branch and return 1
without making any more recursive calls.
\end{quote}
The return value, 1, is multiplied by \verb'$n', which is 1, and the
result is returned.
\end{quote}
The return value, 1, is multiplied by \verb'$n', which is 2, and the
result is returned.
\end{quote}
The return value, 2, is multiplied by \verb'$n', which is 3, and
the result, 6, becomes the return value of the subroutine call
that started the whole process.
\index{stack diagram}
Figure~\ref{fig.stack3} shows what the stack diagram looks like for
this sequence of function calls.
\begin{figure}
\centerline
{\includegraphics[scale=0.8]{figs/stack3.pdf}}
\caption{Stack diagram.}
\label{fig.stack3}
\end{figure}
The return values are shown being passed back up the stack. In each
frame, the return value is the value of {\tt result}, which is the
product of {\tt n} and {\tt recurse}.
\index{function!frame}
\index{frame}
In the last frame, the local
variables {\tt recurse} and {\tt result} do not exist, because
the branch that creates them does not run.
A seasoned Raku programmer might write a more concise or
more idiomatic subroutine\footnote{We will see later even
more idiomatic ways of computing the factorial of a number.}:
\index{idiomatic}
\begin{verbatim}
sub factorial($n){
return 1 if $n == 0;
return $n * factorial $n-1;
}
\end{verbatim}
%
This is not better than our initial version, and will probably
not run significantly faster, but this is arguably clearer,
at least once you get used to this type of syntax.
\section{Leap of Faith}
\index{recursion}
\index{leap of faith}
Following the flow of execution is one way to read programs, but
it can quickly become overwhelming. An alternative is what may
be called the ``leap of faith.'' When you come to a
subroutine call, instead of following the flow of execution, you {\em
assume} that the subroutine 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 math functions such as {\tt cos} or {\tt sqrt},
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 likely to be good programmers (and because you
can safely assume that they have been thoroughly tested).
The same is true when you call one of your own subroutines. For
example, in Section~\ref{boolean}, we wrote a subroutine called
\verb"is-divisible" that determines whether one number is divisible by
another. Once we have convinced ourselves that this subroutine is
correct---by examining the code and testing---we can use the subroutine without looking at the body again.
\index{testing!leap of faith}
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 (returns the correct result) and then ask
yourself, ``Assuming that I can find the factorial of \verb"$n-1", can I
compute the factorial of \verb"$n"?'' It is clear that you
can, by multiplying by \verb"$n".
Of course, it's a bit strange to assume that the subroutine works
correctly when you haven't finished writing it, but that's why
it's called a leap of faith!
\section{One More Example}
\label{one.more.example}
\index{Fibonacci!function}
\index{function!Fibonacci}
After {\tt factorial}, the most common example of a recursively
defined mathematical function is {\tt fibonacci}, which has the
following definition (see
\url{http://en.wikipedia.org/wiki/Fibonacci_number}):
%
\begin{eqnarray*}
&& \mathrm{fibonacci}(0) = 1 \\
&& \mathrm{fibonacci}(1) = 1 \\
&& \mathrm{fibonacci}(n) = \mathrm{fibonacci}(n-1) + \mathrm{fibonacci}(n-2)
\end{eqnarray*}
%
In plain English, a Fibonacci sequence is a sequence of numbers
such as:
\begin{verbatim}
1, 1, 2, 3, 5, 8, 13, 21, ...
\end{verbatim}
where the two first terms are equal to 1 and any other term is the
sum of the two preceding ones.
We briefly covered the Fibonacci sequence in Exercise~\ref{fibonacci}
of the previous chapter and implemented it with a {\tt for} loop.
Let's now translate the recursive definition into Raku. It looks like this:
\begin{verbatim}
sub fibonacci ($n) {
return 1 if $n == 0 or $n == 1;
return fibonacci($n-1) + fibonacci($n-2)
}
\end{verbatim}
%
If you try to follow the flow of execution here, even for fairly
small values of \verb'$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.
\index{flow of execution}
\section{Checking Types}
\label{guardian}
What happens if we call {\tt factorial} and give it 1.5 as an argument?
\index{type!checking}
\index{error checking}
\index{factorial!function}
It seems that we get an infinite recursion. How can that be?
The subroutine has a base case---when {\tt \$n == 0}. But if {\tt \$n}
is not an integer, we can {\em miss} the base case and recurse forever.
\index{infinite recursion}
\index{recursion!infinite}
\index{base case}
In the first recursive call, the value of {\tt \$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 {\tt factorial}
function to work with noninteger numbers, or we can make
{\tt factorial} check 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.
\index{function!gamma}
\index{gamma function}
We have already seen examples of subroutines using the signature
to verify the type of the argument. So we can add the {\tt Int}
type to the parameter in the signature. While we're at it,
we can also make sure the argument is positive or zero:
\begin{verbatim}
sub factorial(Int $n where $n >= 0){
return 1 if $n == 0;
return $n * factorial $n-1;
}
\end{verbatim}
%
\index{constraint}
\index{trait}
The {\tt Int} type checking in the signature handles
nonintegers, this is not new. The {\tt where \$n >= 0}
part is a parameter constraint: if the parameter is negative,
the subroutine should fail. Technically, the constraint is
implemented here within the signature using a syntax feature
called a \emph{trait}, that is a property imposed on the
parameter at compile time. If the argument passed to the
function is not an integer or if it is negative, the program prints
an error message to indicate that something went wrong:
\begin{verbatim}
> say factorial 1.5
Type check failed in binding $n; expected Int but got Rat
in sub factorial at <unknown file> line 1
in block <unit> at <unknown file> line 1
> say factorial -3
Constraint type check failed for parameter '$n'
> say factorial "Fred"
Type check failed in binding $n; expected Int but got Str
in sub factorial at <unknown file> line 1
in block <unit> at <unknown file> line 1
\end{verbatim}
%
If we get past both checks, we know that \verb'$n' is an
integer and that it is positive or zero, so we can prove
that the recursion terminates.
\index{subset!type}
\index{type subset}
Another way to achieve a similar result is to define your own
subset of the built-in types. For example, you can create an
{\tt Even-int} subset of integers and then use it more or less
as if it were a new type for declaring your variables or
typing your subroutine parameters:
\begin{verbatim}
subset Even-int of Int where { $_ %% 2 } # or : … where { $_ % 2 == 0 }
# Even-int can now be used as a type
my Even-int $x = 2; # OK
my Even-int $y = 3; # Type mismatch error
\end{verbatim}
Similarly, in the case of the {\tt factorial} subroutine, we
can create a \emph{nonnegative integer} subset and use it
for checking the parameter passed to the subroutine:
\begin{verbatim}
subset Non-neg-int of Int where { $_ >= 0}
# ...
sub factorial(Non-neg-int $n){
return 1 if $n == 0;
return $n * factorial $n-1;
}
\end{verbatim}
%
If we pass a negative integer to the subroutine, we get
a similar error as before:
\begin{verbatim}
Constraint type check failed for parameter '$n'...
\end{verbatim}
\index{guardian pattern}
\index{pattern!guardian}
This program demonstrates a pattern sometimes called a {\bf guardian}.
The signature acts as a guardian, protecting the code that
follows from values that might cause an error. The guardians make it
possible to prove the correctness of the code.
\section{Multi Subroutines}
\label{multisubs}
\index{multi!subroutine}
It is possible to write multiple versions of a subroutine
with the same name but with different signatures, for example
a different \emph{arity} (a fancy word for the number of
arguments) or different argument types, using the
{\tt multi} keyword. In this case, the interpreter will
pick the version of the subroutine whose signature
matches (or best matches) the argument list. This process
is called \emph{dispatch}. Dispatch happens depending on
the number (arity), type and name of arguments.
\index{arity}
\index{dispatch (multi subroutines)}
\index{multi!dispatch}
For example, we could rewrite the factorial function
as follows:
\index{factorial!using multi subroutines}
\begin{verbatim}
multi sub fact(0) { 1 };
multi sub fact(Int $n where $n > 0) {
$n * fact $n - 1;
}
say fact 0; # -> 1
say fact 10; # -> 3628800
\end{verbatim}
Here, we don't enter into infinite recursion because, when
the parameter passed to {\tt fact} is 0, it is the first
version of the multi subroutine that is called and it returns
an integer value (1), and this ends the recursion.
Similarly, the Fibonacci function can be rewritten with
multi subroutines:
\index{Fibonacci!function with multi subroutines}
\begin{verbatim}
multi fibonacci(0) { 1 }
multi fibonacci(1) { 1 }
multi fibonacci(Int $n where $n > 1) {
fibonacci($n - 2) + fibonacci($n - 1)
}
say fibonacci 10; # -> 89
\end{verbatim}
Note that in the {\tt fibonacci} example just above, we have
omitted the {\tt sub} keyword, since it isn't necessary after
the {\tt multi} declarator.
Many built-in functions and most operators of Raku are
written as multi subroutines.
In the two examples above, only one of the {\tt multi}
subroutine signature could match the input parameters.
For example, if the argument passed to the {\tt fact}
subroutine is 0, then the first version is called;
if the argument is greater than 0, then the second version
is called.
What if more that one signature matches the passed
arguments? Then, the dispatch process becomes a little
bit more complicated. As said at the beginning of this section,
the runtime environment will select the \emph{candidate}
subroutine that \emph{best} matches the signature.
In such cases, the run time environment first looks
at the arity (number of arguments) of the signature.
If only one signature matches the number of parameters
passed to the subroutine, then it is this candidate subroutine
that is selected. If, on the other hand, several signatures
match the number of arguments, then the type of the arguments
drives the dispatch. \footnote{We will see later
(see section \ref{named_parameters}) that there can
be other types of signatures, with \emph{named parameters}.
Let's just say here that, when there are named arguments,
they drive the dispatch even when their type is the same as
another candidate. \index{named parameter}
}
\index{arity}
\index{dispatch (multi subroutines)}
\index{multi!dispatch}
\index{candidate (multi subroutines)}
\index{multi!subroutine}
\section{Debugging}
\label{factdebug}
Breaking a large program into smaller functions or subroutines
creates natural checkpoints for debugging. If a subroutine
is not working, there are three possibilities to consider:
\index{debugging}
\begin{itemize}
\item There is something wrong with the arguments the subroutine
is getting; a precondition is violated.
\item There is something wrong with the subroutine; a postcondition
is violated.
\item There is something wrong with the return value or the
way it is being used.
\end{itemize}
To rule out the first possibility, you can add a print statement
at the beginning of the function and display the values of the
parameters (and maybe their types). Or you can write code
that checks the preconditions explicitly.
\index{precondition}
\index{postcondition}
For the purpose of debugging, it is often useful to print
the content of a variable or of a parameter within a string
with surrounding characters, so that you may visualize
characters that are otherwise invisible, such as spaces or
newlines. For example, you think that the \verb'$var' should
contain ``two,'' and run the following test:
\begin{verbatim}
if $var eq "two" {
do-something()
}