| 1 | #!/usr/bin/env perl | ||||||||||
| 2 | |||||||||||
| 3 | # Copyright (c) 2015-2019 Christian Jaeger, copying@christianjaeger.ch | ||||||||||
| 4 | # This is free software. See the file COPYING.md that came bundled | ||||||||||
| 5 | # with this file. | ||||||||||
| 6 | |||||||||||
| 7 | # NOTE: there is now a more extensive intro in docs/intro.md; this | ||||||||||
| 8 | # file was written before that intro existed. This file still has | ||||||||||
| 9 | # useful info above that intro; you can probably choose one or the | ||||||||||
| 10 | # other (and then check the other for completeness) without much | ||||||||||
| 11 | # difference (to get a perfect didactic material, someone could work | ||||||||||
| 12 | # on eliminating this duplication). | ||||||||||
| 13 | |||||||||||
| 14 | # This file contains an intro to functions and the very basic parts of | ||||||||||
| 15 | # functional programming, and to how to use FunctionalPerl: | ||||||||||
| 16 | # | ||||||||||
| 17 | # 1. what is a "repl"? | ||||||||||
| 18 | # 2. what are closures? | ||||||||||
| 19 | # 3. what is recursion? | ||||||||||
| 20 | # 4. what is iteration, in imperative and functional ways? | ||||||||||
| 21 | # 5. what are linked lists, and why are they the list data structure | ||||||||||
| 22 | # of choice for functional programs? | ||||||||||
| 23 | # | ||||||||||
| 24 | # 2-3 won't use any of the FunctionalPerl code; it's really just | ||||||||||
| 25 | # using standard Perl. 5 will use the List module from | ||||||||||
| 26 | # FunctionalPerl. | ||||||||||
| 27 | |||||||||||
| 28 | # ------------------------------------------------------------------ | ||||||||||
| 29 | # (0) boilerplate (this will be familiar to Perlers) | ||||||||||
| 30 | |||||||||||
| 31 | # This (together with the -w flag in the #! line at the top) is how to | ||||||||||
| 32 | # set up Perl to treat undefined or ambiguous language use as errors, | ||||||||||
| 33 | # which is a good idea to always do, since it leads to earlier | ||||||||||
| 34 | # reporting of errors in the program flow, before invalid results are | ||||||||||
| 35 | # used for real, and while still close to the context the issue is | ||||||||||
| 36 | # originating from, making the problem easier to find. | ||||||||||
| 37 | 1 | ▶ | use strict; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 38 | 1 | ▶ | use warnings; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 39 | 1 | ▶ | use warnings FATAL => 'uninitialized'; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 40 | |||||||||||
| 41 | # Some setup that's required to have this script work well as part of | ||||||||||
| 42 | # the project, you wouldn't need this in your own scripts. | ||||||||||
| 43 | |||||||||||
| 44 | # Find modules from the functional-perl working directory (if not | ||||||||||
| 45 | # installed, but checked out from Github) | ||||||||||
| 46 | 1 | ▶ | use Cwd 'abs_path'; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 47 | our ($mydir, $myname); | ||||||||||
| 48 | |||||||||||
| 49 | 1 | ▶ | BEGIN { | ||||||||
|
Subroutine
BEGIN: called CC=3 SCAR=11.7
| |||||||||||
| 50 | 1 | ▶ | my $location = (-l $0) ? abs_path($0) : $0; | ||||||||
|
Branch: 1 branch
| |||||||||||
| 51 | 1 | ▶ | $location =~ /(.*?)([^\/]+?)_?\z/s or die "?"; | ||||||||
|
Branch: 1 branch
| |||||||||||
| 52 | 1 | ($mydir, $myname) = ($1, $2); | |||||||||
| 53 | } | ||||||||||
| 54 | 1 | ▶ | use lib "$mydir/../lib"; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 55 | |||||||||||
| 56 | # Specify FP::Repl's dependencies as a dependency when this file is | ||||||||||
| 57 | # run through test suite (so that testing of this file will be skipped | ||||||||||
| 58 | # instead of reported as a failure) | ||||||||||
| 59 | 0 | ▶ | use Chj::TEST use => 'FP::Repl::Dependencies'; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.4
Subroutine
BEGIN: called CC=1 SCAR=0.4
| |||||||||||
| 60 | |||||||||||
| 61 | # end of "Some setup". | ||||||||||
| 62 | |||||||||||
| 63 | # For development/debugging | ||||||||||
| 64 | |||||||||||
| 65 | #use Chj::ruse; # get the 'ruse' procedure which will reload modules; | ||||||||||
| 66 | # since we're putting the meat of the program into the | ||||||||||
| 67 | # main file here, this wouldn't help us in this case. | ||||||||||
| 68 | |||||||||||
| 69 | use Chj::Backtrace; # show a backtrace when an error happens | ||||||||||
| 70 | |||||||||||
| 71 | use FP::Repl; # get the 'repl' procedure, so we can call it at the | ||||||||||
| 72 | # end, but you can also put it anywhere in the code when | ||||||||||
| 73 | # you want to examine the state of the program at that | ||||||||||
| 74 | # point. | ||||||||||
| 75 | |||||||||||
| 76 | use FP::Repl::AutoTrap; # set up an error handler (via $SIG{__DIE__}) | ||||||||||
| 77 | # that opens a repl whenever there's an | ||||||||||
| 78 | # uncaught exception in your program (and the | ||||||||||
| 79 | # program is running on a tty). This is useful | ||||||||||
| 80 | # if you're the programmer; it wouldn't be | ||||||||||
| 81 | # useful if you hand your script to an end | ||||||||||
| 82 | # user who is not a programmer, thus comment | ||||||||||
| 83 | # out (or otherwise disable) this import when | ||||||||||
| 84 | # you pass the script on. NOTE: this overrides | ||||||||||
| 85 | # the handler from Chj::Backtrace above, thus | ||||||||||
| 86 | # you could comment out that line above; or, | ||||||||||
| 87 | # just leave it as is, and if you comment out | ||||||||||
| 88 | # FP::Repl::AutoTrap, Chj::Backtrace will | ||||||||||
| 89 | # automatically be active instead. | ||||||||||
| 90 | |||||||||||
| 91 | # ------------------------------------------------------------------ | ||||||||||
| 92 | # (1) Demonstrating the repl, which stands for read-eval-print loop: | ||||||||||
| 93 | |||||||||||
| 94 | # The repl allows to evaluate expressions without restarting the | ||||||||||
| 95 | # program. It shows a prompt, reads a line of input, evaluates it, and | ||||||||||
| 96 | # prints the result, and does this in an endless loop until you enter | ||||||||||
| 97 | # <ctrl>-d at the prompt, at which point the repl procedure | ||||||||||
| 98 | # returns. It has line editing, history and <tab> completion. Example: | ||||||||||
| 99 | |||||||||||
| 100 | #main> 1+1 | ||||||||||
| 101 | #$VAR1 = 2; | ||||||||||
| 102 | |||||||||||
| 103 | # The 'main' at the prompt indicates the namespace, which is main:: | ||||||||||
| 104 | # here. | ||||||||||
| 105 | |||||||||||
| 106 | # Run this script now, `intro/basics`, and you will get a repl prompt | ||||||||||
| 107 | # (you can see the call to it at the bottom of this file), where you | ||||||||||
| 108 | # can play with these examples. | ||||||||||
| 109 | |||||||||||
| 110 | # Multiple values: | ||||||||||
| 111 | |||||||||||
| 112 | #main> (1+1,2*2) | ||||||||||
| 113 | #$VAR1 = 2; | ||||||||||
| 114 | #$VAR2 = 4; | ||||||||||
| 115 | #main> () | ||||||||||
| 116 | #main> | ||||||||||
| 117 | |||||||||||
| 118 | # An array: | ||||||||||
| 119 | |||||||||||
| 120 | #main> [1+1,2*2] | ||||||||||
| 121 | #$VAR1 = [ | ||||||||||
| 122 | # 2, | ||||||||||
| 123 | # 4 | ||||||||||
| 124 | # ]; | ||||||||||
| 125 | |||||||||||
| 126 | # Variables: | ||||||||||
| 127 | |||||||||||
| 128 | # Strict mode is not active in the repl, so you can leave out the | ||||||||||
| 129 | # otherwise obligatory "our " keyword and it will be understood as a | ||||||||||
| 130 | # package variable and hence survive across entries. | ||||||||||
| 131 | |||||||||||
| 132 | # main> $x = 10 | ||||||||||
| 133 | # $VAR1 = 10; | ||||||||||
| 134 | # main> $x++ | ||||||||||
| 135 | # $VAR1 = 10; | ||||||||||
| 136 | # main> $x | ||||||||||
| 137 | # $VAR1 = 11; | ||||||||||
| 138 | |||||||||||
| 139 | # If you used "my ", it would be restricted to just the line you enter: | ||||||||||
| 140 | |||||||||||
| 141 | # main> my $x = 100 | ||||||||||
| 142 | # $VAR1 = 100; | ||||||||||
| 143 | # main> $x | ||||||||||
| 144 | # $VAR1 = 11; | ||||||||||
| 145 | |||||||||||
| 146 | # You can define new code: | ||||||||||
| 147 | |||||||||||
| 148 | # main> sub hi { my (@names) = @_; "Hello ".join(" and ", @names) } | ||||||||||
| 149 | # main> hi "Paul" | ||||||||||
| 150 | # $VAR1 = 'Hello Paul'; | ||||||||||
| 151 | |||||||||||
| 152 | # main> hi "Stefan", undef | ||||||||||
| 153 | # Exception: 'Use of uninitialized value $names[1] in join or string at (eval 146) line 1. | ||||||||||
| 154 | # ' | ||||||||||
| 155 | # main 1> | ||||||||||
| 156 | |||||||||||
| 157 | # An exception has happened because of the "use warnings FATAL" | ||||||||||
| 158 | # above. The "1" in the new prompt indicates that you're in a nested | ||||||||||
| 159 | # repl: this is because FP::Repl::AutoTrap was loaded above (see | ||||||||||
| 160 | # comments there). Whatever you enter in this nested repl is evaluated | ||||||||||
| 161 | # in the context where the die happened. There are some meta commands | ||||||||||
| 162 | # in the repl; enter ":?" or ",?" for help: | ||||||||||
| 163 | |||||||||||
| 164 | # main 1> :? | ||||||||||
| 165 | # Repl help: | ||||||||||
| 166 | # If a command line starts with a ':' or ',', then the remainder of the | ||||||||||
| 167 | # line is interpreted as follows: | ||||||||||
| 168 | # ... | ||||||||||
| 169 | # ... | ||||||||||
| 170 | |||||||||||
| 171 | # Get a backtrace: | ||||||||||
| 172 | |||||||||||
| 173 | # main 1> ,b | ||||||||||
| 174 | # 0 FP::Repl::WithRepl::__ANON__('Use of uninitialized value $names[1] in join or string at (ev...') called at (eval 146) line 1 | ||||||||||
| 175 | # 1 main::hi('Stefan', undef) called at (eval 148) line 1 | ||||||||||
| 176 | # 2 main::__ANON__() called at intro//../lib/FP/Repl/Repl.pm line 556 | ||||||||||
| 177 | # 3 FP::Repl::Repl::__ANON__() called at intro//../lib/FP/Repl/Repl.pm line 107 | ||||||||||
| 178 | # ... | ||||||||||
| 179 | |||||||||||
| 180 | # Look at the environment (variables): | ||||||||||
| 181 | |||||||||||
| 182 | # main 1> ,e | ||||||||||
| 183 | # \@names = ['Stefan', undef]; | ||||||||||
| 184 | |||||||||||
| 185 | # Run code within that environment: | ||||||||||
| 186 | |||||||||||
| 187 | # main 1> $names[0] | ||||||||||
| 188 | # $VAR1 = 'Stefan'; | ||||||||||
| 189 | |||||||||||
| 190 | # main 1> hi "there", undef, "again" | ||||||||||
| 191 | # Exception: 'Use of uninitialized value $names[1] in join or string at (eval 146) line 1. | ||||||||||
| 192 | # ' | ||||||||||
| 193 | # main 2> | ||||||||||
| 194 | |||||||||||
| 195 | # The "2" signifies that you've got 2 nested repls now. | ||||||||||
| 196 | |||||||||||
| 197 | # main 2> ,e | ||||||||||
| 198 | # \@names = ['there', undef, 'again']; | ||||||||||
| 199 | # main 2> ,b | ||||||||||
| 200 | # 0 FP::Repl::WithRepl::__ANON__('Use of uninitialized value $names[1] in join or string at (ev...') called at (eval 146) line 1 | ||||||||||
| 201 | # 1 main::hi('there', undef, 'again') called at (eval 160) line 1 | ||||||||||
| 202 | # ... | ||||||||||
| 203 | # 11 FP::Repl::WithRepl::__ANON__('Use of uninitialized value $names[1] in join or string at (ev...') called at (eval 146) line 1 | ||||||||||
| 204 | # 12 main::hi('Stefan', undef) called at (eval 148) line 1 | ||||||||||
| 205 | # 13 main::__ANON__() called at intro//../lib/FP/Repl/Repl.pm line 556 | ||||||||||
| 206 | |||||||||||
| 207 | # main 2/12> ,10 | ||||||||||
| 208 | # .. | ||||||||||
| 209 | # FP::Repl::WithRepl 2/10> ,e | ||||||||||
| 210 | # \@names = ['Stefan', undef]; | ||||||||||
| 211 | # FP::Repl::WithRepl 2/10> $names[0] | ||||||||||
| 212 | # $VAR1 = 'Stefan'; | ||||||||||
| 213 | |||||||||||
| 214 | #XXX buggy 1 off TODO fix. | ||||||||||
| 215 | |||||||||||
| 216 | # You can exit one level of repls by entering ctl-d. You'll be back at: | ||||||||||
| 217 | |||||||||||
| 218 | # main 1> ,e | ||||||||||
| 219 | # \@names = ['Stefan', undef]; | ||||||||||
| 220 | |||||||||||
| 221 | # And again ctl-d: | ||||||||||
| 222 | |||||||||||
| 223 | # main> | ||||||||||
| 224 | |||||||||||
| 225 | # ------------------------------------------------------------------ | ||||||||||
| 226 | # (2) Demonstrating closures: | ||||||||||
| 227 | |||||||||||
| 228 | # 'sub' stands for 'subroutine', also called procedures, or | ||||||||||
| 229 | # functions. "Function" implies that a value is returned. If we say | ||||||||||
| 230 | # "pure function", then its *only* effect is to return a value. | ||||||||||
| 231 | |||||||||||
| 232 | sub f { | ||||||||||
| 233 | |||||||||||
| 234 | # this is just how functions receive their arguments in Perl | ||||||||||
| 235 | # (ugly, yes; we'll see a nicer way in the file | ||||||||||
| 236 | # `more_tailcalls`): | ||||||||||
| 237 | my ($x, $y) = @_; | ||||||||||
| 238 | |||||||||||
| 239 | # $x and $y are fresh variables here ('my' means fresh and local | ||||||||||
| 240 | # to the scope), set to the arguments that were passed to 'f' | ||||||||||
| 241 | |||||||||||
| 242 | # The value of the last expression in a scope is also the value | ||||||||||
| 243 | # being returned by the scope (and in this case, the 'f' | ||||||||||
| 244 | # function). This is an anonymous function here (note that no name | ||||||||||
| 245 | # is given); it is called a "closure" as it "closes over" | ||||||||||
| 246 | # variables in its enclosing scope, i.e. $x and $y here. | ||||||||||
| 247 | sub { | ||||||||||
| 248 | my ($z) = @_; | ||||||||||
| 249 | $x * $y - $z | ||||||||||
| 250 | } | ||||||||||
| 251 | } | ||||||||||
| 252 | |||||||||||
| 253 | # See how f returns a subroutine as the result (its body is shown as | ||||||||||
| 254 | # "DUMMY" for simplicity): | ||||||||||
| 255 | |||||||||||
| 256 | # main> f(2,3) | ||||||||||
| 257 | # $VAR1 = sub { 'DUMMY: main::__ANON__ at "intro/basics" line 247' }; | ||||||||||
| 258 | |||||||||||
| 259 | # If we want to call that: | ||||||||||
| 260 | |||||||||||
| 261 | #main> $VAR1->(4) | ||||||||||
| 262 | #$VAR1 = 2; | ||||||||||
| 263 | |||||||||||
| 264 | # 2 * 3 - 4, correct. | ||||||||||
| 265 | |||||||||||
| 266 | # Capture the anonymous subroutines in variables (thus giving them | ||||||||||
| 267 | # names, although those names are prefixed with '$' (they are 'SCALAR' | ||||||||||
| 268 | # variables instead of the 'CODE' variables that 'sub name' sets)): | ||||||||||
| 269 | |||||||||||
| 270 | #main> $g = f(2,3); $h = f(4,5); () | ||||||||||
| 271 | #main> $g->(4) | ||||||||||
| 272 | #$VAR1 = 2; | ||||||||||
| 273 | #main> $h->(4) | ||||||||||
| 274 | #$VAR1 = 16; | ||||||||||
| 275 | |||||||||||
| 276 | # Note how $g and $h remember the values that were passed to 'f' for | ||||||||||
| 277 | # their creation. | ||||||||||
| 278 | |||||||||||
| 279 | # ------------------------------------------------------------------ | ||||||||||
| 280 | # 3-4: we're defining the factorial function: | ||||||||||
| 281 | # f(n) = 1 * 2 * 3 * ... * n | ||||||||||
| 282 | |||||||||||
| 283 | # (3) factorial using recursion: | ||||||||||
| 284 | |||||||||||
| 285 | sub fact { | ||||||||||
| 286 | my ($n) = @_; | ||||||||||
| 287 | warn "n=$n"; | ||||||||||
| 288 | if ($n < 2) { | ||||||||||
| 289 | 1 | ||||||||||
| 290 | } else { | ||||||||||
| 291 | $n * fact($n - 1) | ||||||||||
| 292 | } | ||||||||||
| 293 | } | ||||||||||
| 294 | |||||||||||
| 295 | # The above definition is purely functional (except for the warn | ||||||||||
| 296 | # statement): not only is the only effect of calling fact its return | ||||||||||
| 297 | # value (again except for the warning, please consider that a | ||||||||||
| 298 | # debugging feature, outside of the scope of program behaviour), but | ||||||||||
| 299 | # it's also not using anything else than pure functions (the operators | ||||||||||
| 300 | # like '*', '-', '<' can be understood as functions in the | ||||||||||
| 301 | # mathematical sense, even though they are not accessible as functions | ||||||||||
| 302 | # in Perl) and variable bindings inside. | ||||||||||
| 303 | |||||||||||
| 304 | # With the 'variable binding', my $n = ... is meant. In pure | ||||||||||
| 305 | # functional languages, variables are only ever assigned once (and | ||||||||||
| 306 | # immediately upon their instantiation); they are usually called | ||||||||||
| 307 | # 'bindings' in those languages, not variables. They bind a value to a | ||||||||||
| 308 | # name in a context; the same name in the same context is guaranteed | ||||||||||
| 309 | # to always be the same value in those languages, thus, a binding | ||||||||||
| 310 | # doesn't vary (the same binding isn't variable). Note that this | ||||||||||
| 311 | # doesn't mean that $n is constant: every invocation of 'fact' will | ||||||||||
| 312 | # bind its own instance of $n to whatever argument was passed; but | ||||||||||
| 313 | # that same instance of $n can never be modified in a purely | ||||||||||
| 314 | # functional language, and in this implementation of the factorial we | ||||||||||
| 315 | # don't do that either (voluntarily). | ||||||||||
| 316 | |||||||||||
| 317 | # Try it out: | ||||||||||
| 318 | |||||||||||
| 319 | # main> fact 10 | ||||||||||
| 320 | # ... | ||||||||||
| 321 | |||||||||||
| 322 | # ------------------------------------------------------------------ | ||||||||||
| 323 | # (4) factorial using iteration: | ||||||||||
| 324 | |||||||||||
| 325 | # If you already know about the difference between iterative and | ||||||||||
| 326 | # recursive algorithms, you could skip down to (4a). | ||||||||||
| 327 | |||||||||||
| 328 | # The recursive algorithm above delays the multiplication until the | ||||||||||
| 329 | # recursive call returns. fact(3) will calculate 3 * fact(2), which | ||||||||||
| 330 | # has to evaluate fact(2) before the multiplication can be executed; | ||||||||||
| 331 | # fact(2) will calculate 2 * fact(1), and fact(1) will return 1, after | ||||||||||
| 332 | # which point the multiplication 2 * 1 => 2 can be executed, which | ||||||||||
| 333 | # will be returned, at which point the multiplication 3 * 2 will be | ||||||||||
| 334 | # executed. The steps that are not done yet, like "3 *", are called | ||||||||||
| 335 | # continuations ("3 *" is the continuation of the evaluation of | ||||||||||
| 336 | # "fact(2)", etc.), and are remembered implicitely by the Perl | ||||||||||
| 337 | # interpreter on a stack (the Perl language-level stack, which is | ||||||||||
| 338 | # implemented independently of the C stack). This means that | ||||||||||
| 339 | # calculating fact for n will need n slots of space on the stack. This | ||||||||||
| 340 | # is unlikely to be a problem here since fact for big values of n is | ||||||||||
| 341 | # going to overflow Perl's number range anyway, but it's something to | ||||||||||
| 342 | # be aware of since you *will* run out of stack space for some other | ||||||||||
| 343 | # tasks when implementing them by way of recursion. | ||||||||||
| 344 | |||||||||||
| 345 | # But the factorial can also be calculated in another way: instead of | ||||||||||
| 346 | # carrying out the multiplication after getting the factorial for the | ||||||||||
| 347 | # next smaller n, we can multiply by the next smaller n and then use | ||||||||||
| 348 | # this for the next iteration. Effectively, instead of calculating | ||||||||||
| 349 | |||||||||||
| 350 | # 4 * (3 * (2 * 1)) | ||||||||||
| 351 | |||||||||||
| 352 | # we can calculate | ||||||||||
| 353 | |||||||||||
| 354 | # ((4 * 3) * 2) * 1 | ||||||||||
| 355 | |||||||||||
| 356 | # which of course (thanks to the associativity of multiplication) will | ||||||||||
| 357 | # give the same result (at least for exact numbers). If we evaluate | ||||||||||
| 358 | # the multiplications in the same direction as the decrement of n | ||||||||||
| 359 | # (i.e. towards the end condition), then the work continues only | ||||||||||
| 360 | # towarts the end condition, and no pending work is piling up (no | ||||||||||
| 361 | # continuations are to be remembered on the stack). Such an algorithm | ||||||||||
| 362 | # is called *iterative*. This distinction is independent of the fact | ||||||||||
| 363 | # whether we're implementing the algorithm with a programming language | ||||||||||
| 364 | # that continues to the next evaluation step by way of calling a | ||||||||||
| 365 | # function, or by way of using loop syntax. These two styles are shown | ||||||||||
| 366 | # below: | ||||||||||
| 367 | |||||||||||
| 368 | # (4a) iteration with a loop and variable mutation. This means, that | ||||||||||
| 369 | # only one instance of $n and $res respectively is created when | ||||||||||
| 370 | # calling 'imperative_fact', and subsequently assigned new values; | ||||||||||
| 371 | # this is *not* functional, but imperative programming. | ||||||||||
| 372 | |||||||||||
| 373 | # To peek inside what's going on, we're going to save a closure from | ||||||||||
| 374 | # every iteration step, so that we can call those later to show us the | ||||||||||
| 375 | # values of the variables that were in their context at the time of | ||||||||||
| 376 | # their creation. | ||||||||||
| 377 | |||||||||||
| 378 | our @imperative_inspect; # array to hold the closures; 'our' means a | ||||||||||
| 379 | # global variable, as opposed to 'my' which | ||||||||||
| 380 | # is lexically accessible only. For a | ||||||||||
| 381 | # variable to be accessible from 'repl', it | ||||||||||
| 382 | # needs to be global (sadly) | ||||||||||
| 383 | |||||||||||
| 384 | sub imperative_fact { | ||||||||||
| 385 | my ($n) = @_; | ||||||||||
| 386 | my $res = 1; | ||||||||||
| 387 | while (1) { | ||||||||||
| 388 | |||||||||||
| 389 | # save closure for later inspection of $n and $res | ||||||||||
| 390 | push @imperative_inspect, sub { ($n, $res) }; | ||||||||||
| 391 | |||||||||||
| 392 | if ($n < 2) { | ||||||||||
| 393 | return $res; | ||||||||||
| 394 | } else { | ||||||||||
| 395 | |||||||||||
| 396 | # treat $res and $n not as immutable binding of a name to | ||||||||||
| 397 | # a value, but as mutable memory location | ||||||||||
| 398 | $res = $n * $res; | ||||||||||
| 399 | $n = $n - 1; | ||||||||||
| 400 | } | ||||||||||
| 401 | } | ||||||||||
| 402 | } | ||||||||||
| 403 | |||||||||||
| 404 | #main> imperative_fact 4 | ||||||||||
| 405 | #$VAR1 = 24; | ||||||||||
| 406 | #main> @imperative_inspect | ||||||||||
| 407 | # $VAR1 = sub { 'DUMMY: main::__ANON__ at "intro/basics" line 391' }; | ||||||||||
| 408 | # $VAR2 = sub { 'DUMMY: main::__ANON__ at "intro/basics" line 391' }; | ||||||||||
| 409 | # $VAR3 = sub { 'DUMMY: main::__ANON__ at "intro/basics" line 391' }; | ||||||||||
| 410 | # $VAR4 = sub { 'DUMMY: main::__ANON__ at "intro/basics" line 391' }; | ||||||||||
| 411 | #main> $imperative_inspect[0]->() | ||||||||||
| 412 | #$VAR1 = 1; | ||||||||||
| 413 | #$VAR2 = 24; | ||||||||||
| 414 | #main> $imperative_inspect[3]->() | ||||||||||
| 415 | #$VAR1 = 1; | ||||||||||
| 416 | #$VAR2 = 24; | ||||||||||
| 417 | |||||||||||
| 418 | # Note how our captured closures all show the same values, namely the | ||||||||||
| 419 | # last ones. Even though the closure that was captured in the first | ||||||||||
| 420 | # loop iteration was created when the variables held different values, | ||||||||||
| 421 | # by the time we call it, the variables were mutated and don't bind to | ||||||||||
| 422 | # the same values anymore. All of the closures in @imperative_inspect | ||||||||||
| 423 | # refer to the same variable instances. | ||||||||||
| 424 | |||||||||||
| 425 | # Ponder how this could be a dangerous feature in bigger programs (and | ||||||||||
| 426 | # hence why functional programming avoids it.) | ||||||||||
| 427 | |||||||||||
| 428 | # As an aside: note that as seen by the world *outside*, | ||||||||||
| 429 | # imperative_fact is still purely functional (when ignoring the | ||||||||||
| 430 | # mutation of @imperative_inspect, which again we do for | ||||||||||
| 431 | # debugging/inspection purposes only). Iff mutations are kept | ||||||||||
| 432 | # localized, their danger is correspondingly low (they will only | ||||||||||
| 433 | # matter when working on the code within the scope that they are kept | ||||||||||
| 434 | # to, i.e. when imperative_fact is modified later on). | ||||||||||
| 435 | |||||||||||
| 436 | # (4b) factorial still using iteration, but instead of using mutation, | ||||||||||
| 437 | # again using pure functions internally. Note how this implements the | ||||||||||
| 438 | # same algorithm as imperative_fact, but the looping happens by way of | ||||||||||
| 439 | # calling the containing function instead of a while loop within | ||||||||||
| 440 | # it. This way, $n and $res are new instances for every iteration; | ||||||||||
| 441 | # they are not mutated and maintain the same value throughout their | ||||||||||
| 442 | # lifetime. | ||||||||||
| 443 | |||||||||||
| 444 | sub functional_fact { | ||||||||||
| 445 | my ($n) = @_; | ||||||||||
| 446 | functional_fact_iter($n, 1) | ||||||||||
| 447 | } | ||||||||||
| 448 | |||||||||||
| 449 | our @functional_inspect; | ||||||||||
| 450 | |||||||||||
| 451 | sub functional_fact_iter { | ||||||||||
| 452 | my ($n, $res) = @_; | ||||||||||
| 453 | push @functional_inspect, sub { ($n, $res) }; | ||||||||||
| 454 | if ($n < 2) { | ||||||||||
| 455 | return $res; | ||||||||||
| 456 | } else { | ||||||||||
| 457 | |||||||||||
| 458 | # This is a tail call: it happens in tail position, | ||||||||||
| 459 | # i.e. there's nothing happening *after* this call within this | ||||||||||
| 460 | # function. | ||||||||||
| 461 | functional_fact_iter($n - 1, $n * $res) | ||||||||||
| 462 | |||||||||||
| 463 | # In different words: when this sub-call returns a value, it | ||||||||||
| 464 | # will be immediately returned by the current call, too, | ||||||||||
| 465 | # without doing any further computation with it. Because of | ||||||||||
| 466 | # this, there's no need to keep space allocated (on the call | ||||||||||
| 467 | # stack) for the current context--it won't be used | ||||||||||
| 468 | # anymore. Dropping the current context at the same time as | ||||||||||
| 469 | # executing the tail call is what one calls "tail-call | ||||||||||
| 470 | # optimization". | ||||||||||
| 471 | |||||||||||
| 472 | # But: Perl does *not* carry out this optimization | ||||||||||
| 473 | # automatically, thus this code will still use stack space | ||||||||||
| 474 | # (not a real problem for factorial since it will not be a | ||||||||||
| 475 | # huge amount; cases where a loop can be repeated millions of | ||||||||||
| 476 | # times it would be a problem as Perl would run out of stack | ||||||||||
| 477 | # space). It can be specified explicitely, though. See the | ||||||||||
| 478 | # file `tailcalls` for a version that won't use stack space. | ||||||||||
| 479 | } | ||||||||||
| 480 | } | ||||||||||
| 481 | |||||||||||
| 482 | #main> functional_fact 4 | ||||||||||
| 483 | #$VAR1 = 24; | ||||||||||
| 484 | #main> @functional_inspect | ||||||||||
| 485 | # $VAR1 = sub { 'DUMMY: main::__ANON__ at "intro/basics" line 458' }; | ||||||||||
| 486 | # $VAR2 = sub { 'DUMMY: main::__ANON__ at "intro/basics" line 458' }; | ||||||||||
| 487 | # $VAR3 = sub { 'DUMMY: main::__ANON__ at "intro/basics" line 458' }; | ||||||||||
| 488 | # $VAR4 = sub { 'DUMMY: main::__ANON__ at "intro/basics" line 458' }; | ||||||||||
| 489 | #main> $functional_inspect[0]->() | ||||||||||
| 490 | #$VAR1 = 4; | ||||||||||
| 491 | #$VAR2 = 1; | ||||||||||
| 492 | #main> $functional_inspect[3]->() | ||||||||||
| 493 | #$VAR1 = 1; | ||||||||||
| 494 | #$VAR2 = 24; | ||||||||||
| 495 | |||||||||||
| 496 | # Note how the closures really remember the values that were in their | ||||||||||
| 497 | # context when they were created. | ||||||||||
| 498 | |||||||||||
| 499 | # ------------------------------------------------------------------ | ||||||||||
| 500 | # (5) Linked lists | ||||||||||
| 501 | |||||||||||
| 502 | # If lists of values are implemented as arrays (slots in adjacent | ||||||||||
| 503 | # memory locations), then the only way to initialize an array is to | ||||||||||
| 504 | # write to it using mutation. If we want to stay purely functional, a | ||||||||||
| 505 | # different data structure has to be used; singly linked lists are | ||||||||||
| 506 | # commonly used for this purpose. (Trees are an alternative.) | ||||||||||
| 507 | |||||||||||
| 508 | # Those are built from pairs of (val, rest), where rest is again a | ||||||||||
| 509 | # pair, or the list end marker. Lisp calls the function to create a | ||||||||||
| 510 | # pair 'cons', and the accessors to get val 'car' and rest 'cdr' | ||||||||||
| 511 | # (sometimes aliased to 'first' and 'rest'; the reason to use 'car' | ||||||||||
| 512 | # and 'cdr' is that pairs can be used as building blocks for other | ||||||||||
| 513 | # things than lists, too, and because combinations of those names can | ||||||||||
| 514 | # be shortened, e.g. car(car($x)) can be written as caar($x), or | ||||||||||
| 515 | # car(cdr($x)) to cadr($x).) Also, pairs can be used for other data | ||||||||||
| 516 | # structures than lists. But there are also aliases for car and cdr | ||||||||||
| 517 | # named 'first' and 'rest', for more descriptive names in the context | ||||||||||
| 518 | # of lists. Those are also the names used by Clojure, Mathematica, and | ||||||||||
| 519 | # perhaps some other languages, whereas Haskell and Scala use the | ||||||||||
| 520 | # names 'head' and 'tail'. Since 'tail' is already taken by the | ||||||||||
| 521 | # `Sub::Call::Tail` module, we're staying with 'first' and 'rest'. | ||||||||||
| 522 | |||||||||||
| 523 | # For best fit with functional programming, the bare chains are passed | ||||||||||
| 524 | # around, without any object wrapper. | ||||||||||
| 525 | |||||||||||
| 526 | use FP::List ":all"; # cons, car, cdr, first, rest | ||||||||||
| 527 | use FP::Array ":all"; # list_to_array | ||||||||||
| 528 | |||||||||||
| 529 | # main> cons(1,2) | ||||||||||
| 530 | # $VAR1 = bless( [ | ||||||||||
| 531 | # 1, | ||||||||||
| 532 | # 2 | ||||||||||
| 533 | # ], 'FP::List::Pair' ); | ||||||||||
| 534 | |||||||||||
| 535 | # As you can see, cons returns a Pair object simply containing the two arguments. | ||||||||||
| 536 | |||||||||||
| 537 | # Let's introduce Chj::TEST, it is useful to make sure the results we | ||||||||||
| 538 | # show here actually are what the current functional-perl version | ||||||||||
| 539 | # returns. TEST takes a block of code, and a value that the block of | ||||||||||
| 540 | # code is expected to return. | ||||||||||
| 541 | |||||||||||
| 542 | use Chj::TEST; | ||||||||||
| 543 | |||||||||||
| 544 | TEST { cons(1, 2) } | ||||||||||
| 545 | bless([1, 2], 'FP::List::Pair'); | ||||||||||
| 546 | |||||||||||
| 547 | # Let's build a list containing 3 elements; null is returning the list | ||||||||||
| 548 | # end marker. | ||||||||||
| 549 | |||||||||||
| 550 | TEST { cons(1, cons(2, cons(5, null))) } | ||||||||||
| 551 | bless( | ||||||||||
| 552 | [ | ||||||||||
| 553 | 1, | ||||||||||
| 554 | bless( | ||||||||||
| 555 | [2, bless([5, bless([], 'FP::List::Null')], 'FP::List::Pair')], | ||||||||||
| 556 | 'FP::List::Pair' | ||||||||||
| 557 | ) | ||||||||||
| 558 | ], | ||||||||||
| 559 | 'FP::List::Pair' | ||||||||||
| 560 | ); | ||||||||||
| 561 | |||||||||||
| 562 | # This becomes ugly fast, so, turn it back into an array that Perl | ||||||||||
| 563 | # will show nicely: | ||||||||||
| 564 | |||||||||||
| 565 | # main> cons(1, cons(2, cons(5, null)))->array | ||||||||||
| 566 | # $VAR1 = [1, 2, 5]; | ||||||||||
| 567 | |||||||||||
| 568 | # But, there's also a meta command in the repl that can show such | ||||||||||
| 569 | # values nicely: | ||||||||||
| 570 | |||||||||||
| 571 | # main> ,s | ||||||||||
| 572 | # main> :s # same | ||||||||||
| 573 | # main> cons(1, cons(2, cons(5, null))) | ||||||||||
| 574 | # $VAR1 = list(1, 2, 5); | ||||||||||
| 575 | |||||||||||
| 576 | # :s formats things in a single line; if you'd like it to be | ||||||||||
| 577 | # pretty-printed into multiple lines, use :S, but that (currently) | ||||||||||
| 578 | # requires Perl::Tidy to be installed, and can be a bit slow for large | ||||||||||
| 579 | # data structures. | ||||||||||
| 580 | |||||||||||
| 581 | # `list` is a function from `FP::List` that turns the arguments given | ||||||||||
| 582 | # to it into a linked list. The code shown by the repl in "s" mode is | ||||||||||
| 583 | # actually Perl code that, when run, yields the value that the command | ||||||||||
| 584 | # evaluated to. | ||||||||||
| 585 | |||||||||||
| 586 | # main> list(1, 1+1, 2*2) | ||||||||||
| 587 | # $VAR1 = list(1, 2, 4); | ||||||||||
| 588 | |||||||||||
| 589 | # Let's build a list functionally, using recursion: | ||||||||||
| 590 | |||||||||||
| 591 | sub iota { | ||||||||||
| 592 | my ($from, $to) = @_; | ||||||||||
| 593 | if ($from >= $to) { | ||||||||||
| 594 | null | ||||||||||
| 595 | } else { | ||||||||||
| 596 | cons $from, iota($from + 1, $to) | ||||||||||
| 597 | } | ||||||||||
| 598 | } | ||||||||||
| 599 | |||||||||||
| 600 | # main> iota (3, 8) | ||||||||||
| 601 | # $VAR1 = list(3, 4, 5, 6, 7); | ||||||||||
| 602 | |||||||||||
| 603 | # you could use write_sexpr to get Scheme-compatible formatting | ||||||||||
| 604 | # instead (this needs the print to force a newline and hence flush the | ||||||||||
| 605 | # buffer; you're first seeing the written output, then the return | ||||||||||
| 606 | # value): | ||||||||||
| 607 | |||||||||||
| 608 | # main> write_sexpr iota (3, 8); print "\n" | ||||||||||
| 609 | # ("3" "4" "5" "6" "7") | ||||||||||
| 610 | # $VAR1 = 1; | ||||||||||
| 611 | |||||||||||
| 612 | # A preview on lazy lists, AKA functional streams: | ||||||||||
| 613 | # those are linked lists, but computed on demand. | ||||||||||
| 614 | |||||||||||
| 615 | use FP::Stream ":all"; | ||||||||||
| 616 | use FP::Lazy ":all"; | ||||||||||
| 617 | |||||||||||
| 618 | # main> stream_iota (4, 3) | ||||||||||
| 619 | # $VAR1 = lazy { "DUMMY" }; | ||||||||||
| 620 | |||||||||||
| 621 | # or, back in Data::Dumper mode: | ||||||||||
| 622 | |||||||||||
| 623 | # main> :d stream_iota (4, 3) | ||||||||||
| 624 | # $VAR1 = bless( [ | ||||||||||
| 625 | # sub { "DUMMY" }, | ||||||||||
| 626 | # undef | ||||||||||
| 627 | # ], 'FP::Lazy::Promise' ); | ||||||||||
| 628 | |||||||||||
| 629 | # Instead of calculating the nested list data structure right away, | ||||||||||
| 630 | # this just returns a "promise". (Details to be shown in another | ||||||||||
| 631 | # intro, some time.) | ||||||||||
| 632 | |||||||||||
| 633 | # stream_iota treats the arguments a bit different (second argument is | ||||||||||
| 634 | # length, not last value; XX should this be changed?) | ||||||||||
| 635 | |||||||||||
| 636 | # main> write_sexpr stream_iota (3, 5); print "\n" | ||||||||||
| 637 | # ("3" "4" "5" "6" "7") | ||||||||||
| 638 | # $VAR1 = 1; | ||||||||||
| 639 | |||||||||||
| 640 | # `write_sexpr stream_iota (3)` would print an endless list: | ||||||||||
| 641 | # stream_iota never ends it without the second argument. | ||||||||||
| 642 | |||||||||||
| 643 | sub square { | ||||||||||
| 644 | my ($x) = @_; | ||||||||||
| 645 | $x * $x | ||||||||||
| 646 | } | ||||||||||
| 647 | |||||||||||
| 648 | # A function from a 'CODE' variable can be passed by prefixing it with | ||||||||||
| 649 | # \& (yes, a bit ugly, too). | ||||||||||
| 650 | |||||||||||
| 651 | # This creates an infinite stream of integers, maps it to its squares, | ||||||||||
| 652 | # takes the first 10 values from it and prints those: | ||||||||||
| 653 | |||||||||||
| 654 | # main> write_sexpr stream_take (stream_map (\&square, stream_iota 0), 10); print "\n" | ||||||||||
| 655 | # ("0" "1" "4" "9" "16" "25" "36" "49" "64" "81") | ||||||||||
| 656 | |||||||||||
| 657 | # It's usually nicer to use method calls, though: the same in "object | ||||||||||
| 658 | # orientation" (still purely functional!): | ||||||||||
| 659 | |||||||||||
| 660 | # main> stream_iota(0)->map(\&square)->take(10)->write_sexpr ; print "\n" | ||||||||||
| 661 | # ("0" "1" "4" "9" "16" "25" "36" "49" "64" "81") | ||||||||||
| 662 | # $VAR1 = 1; | ||||||||||
| 663 | |||||||||||
| 664 | # But you can also just get a FunctionalPerl list: | ||||||||||
| 665 | |||||||||||
| 666 | # main> :s stream_iota(0)->map(\&square)->take(10)->list | ||||||||||
| 667 | # $VAR1 = list(0, 1, 4, 9, 16, 25, 36, 49, 64, 81); | ||||||||||
| 668 | |||||||||||
| 669 | # Or, remember, a plain old array: | ||||||||||
| 670 | |||||||||||
| 671 | # main> stream_iota(0)->map(\&square)->take(10)->array | ||||||||||
| 672 | # $VAR1 = [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]; | ||||||||||
| 673 | |||||||||||
| 674 | # Or, a purearray, which is an array that's immutable and that is an | ||||||||||
| 675 | # object, so, the same methods for sequences can called on it as on | ||||||||||
| 676 | # list: | ||||||||||
| 677 | |||||||||||
| 678 | # main> stream_iota(0)->map(\&square)->take(10)->purearray | ||||||||||
| 679 | # $VAR1 = purearray(0, 1, 4, 9, 16, 25, 36, 49, 64, 81); | ||||||||||
| 680 | # main> $VAR1->map(\&square) | ||||||||||
| 681 | # $VAR1 = purearray(0, 1, 16, 81, 256, 625, 1296, 2401, 4096, 6561); | ||||||||||
| 682 | # main> $VAR1->list | ||||||||||
| 683 | # $VAR1 = list(0, 1, 16, 81, 256, 625, 1296, 2401, 4096, 6561); | ||||||||||
| 684 | |||||||||||
| 685 | # In addition to sequence methods (those which are declared by | ||||||||||
| 686 | # FP::Abstract::Sequence), purearray has efficient (constant time) | ||||||||||
| 687 | # random position element access, whereas list has an efficient | ||||||||||
| 688 | # (constant time) `rest` method, so which one to choose depends on the | ||||||||||
| 689 | # task at hands. | ||||||||||
| 690 | |||||||||||
| 691 | # ------------------------------------------------------------------ | ||||||||||
| 692 | |||||||||||
| 693 | # run TEST forms if called as part of test suite, otherwise enter the | ||||||||||
| 694 | # repl for your experiments: | ||||||||||
| 695 | |||||||||||
| 696 | perhaps_run_tests "main" or repl; | ||||||||||
| 697 | |||||||||||