-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathPCM20210818_SICP_1.3.2_ConstructingProceduresUsingLambda.jl
1822 lines (1483 loc) · 56.7 KB
/
PCM20210818_SICP_1.3.2_ConstructingProceduresUsingLambda.jl
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
### A Pluto.jl notebook ###
# v0.19.12
using Markdown
using InteractiveUtils
# ╔═╡ a46a671b-a813-4ab6-872f-0bbc29b1ee39
using Plots
# ╔═╡ 0bdc1f22-be80-11ed-1491-69cfe2382d1b
md"
=====================================================================================
#### SICP: 1.3.2 Constructing Procedures Using Lambda
##### file: PCM20210818\_SICP\_1.3.2\_ConstructingProceduresUsingLambda.jl
##### Julia/Pluto.jl-code (1.8.5/19.11) by PCM *** 2023/03/10 ***
=====================================================================================
"
# ╔═╡ 84db3c33-49f2-4045-a407-f21361b2cb37
md"
---
#### 1.3.2.1 SICP-SCHEME-like functional Julia ...
###### ... with anonomous $\lambda$-function $\mapsto$
"
# ╔═╡ f2c97a28-f1b7-43d7-a91f-272bcd886a12
md"
---
$\lambda: x \mapsto x+4$
"
# ╔═╡ 60e849eb-c960-4ad2-86d9-1d8065e26e69
function(x) +(x, 4) end # definition with 'function ... end'
# ╔═╡ a3e85937-1fd7-411b-b620-16ceb8d051af
(function(x) +(x, 4) end)(2) # application to argument '2'
# ╔═╡ 313274ed-fb9b-48c5-8bee-a3db4df8d297
x -> +(x, 4) # definition with '->'
# ╔═╡ cb99f6fd-bb69-4e98-b379-48069e778f70
(x -> +(x, 4))(2) # application
# ╔═╡ bb7e8e2f-94cf-4713-b36c-92e7816b6a34
md"
---
$\lambda: x \mapsto \frac{1}{x\cdot(x+2)}$
"
# ╔═╡ 704e5679-36d6-43cf-9d5b-253d93aa29e2
function(x) /(1.0, *(x, +(x, 2))) end # definition with 'function ... end'
# ╔═╡ e883c51e-1c3f-4d40-a13f-9af39d5e08e9
(function(x) /(1.0, *(x, +(x, 2))) end)(2) # application with '2'
# ╔═╡ 1ae10bc5-b8eb-41d0-89c7-d80c9cc598e8
x -> /(1.0, *(x, +(x, 2))) # definition with '->'
# ╔═╡ dd2922e7-ea2c-4457-bedd-6ae3885a42ac
(x -> /(1.0, *(x, +(x, 2))))(2) # application with '2'
# ╔═╡ 9c27049a-3c48-4d69-b181-be7acc4772e4
function sum1(term, a, next, b)
>(a, b) ?
0 :
+(term(a), sum1(term, next(a), next, b))
end # function sum1
# ╔═╡ 433ed93c-2c05-4bed-826e-eca8153bd30b
function pi_sum1(a, b)
sum1(function(x) /(1.0, *(x, +(x, 2))) end, a, x -> +(x, 4), b)
end
# ╔═╡ 962ca66e-ffe4-4625-b5ed-a2dc29072c15
function integral1(f, a, b, dx)
*(sum1(f, +(a, /(dx, 2.0)), x -> +(x, dx), b), dx)
end # function pi_sum1
# ╔═╡ 9754ae8a-180d-4da6-90ef-13e660f05dd1
8 * pi_sum1(1, 1E5)
# ╔═╡ 617b5094-bd33-455b-b1e4-87c214f21d60
md"
---
$\int_0^1 x^3 dx = \left[\frac{x^4}{4}\right]_0^1=\frac{1^4}{4}-\frac{1^0}{4}=\frac{1}{4}$
"
# ╔═╡ 4d3d47f5-f6ec-40d8-9907-6b75cfa55547
integral1(x->^(x, 3), 0, 1, 0.001) # ==> 0.25 --> :)
# ╔═╡ 6132d02f-7bd8-4e1d-aea5-212fefc2d355
plot(x->^(x, 3), 0, 1, size=(700, 300), xlim=(0.0, 1.1), ylim=(0.0, 1.2), line=:darkblue, fill=(0, :lightblue), aspect_ratio=1, framestyle=:semi, title="f: x->x^3", xguide="x", yguide="f: x^3")
# ╔═╡ 23e0515e-8023-41e0-b6d7-dd416d9db9a7
md"
---
$\int_0^1 (6 - 6x^5) dx = \int_0^1 6\;dx - 6\int_0^1 x^5 dx= \left[6x - \frac{6x^6}{6}\right]_0^1 = \left[6-\frac{6}{6}\right]-\left[0-\frac{0}{6}\right]=5.$
"
# ╔═╡ 3514b2a0-5dfa-4c0c-926c-7dcce3e12a2c
integral1(x->-(6, *(6, ^(x, 5))), 0.0, 1.0, 1.0E-4) # ==> 5.0 --> :)
# ╔═╡ a0f823ca-0a55-482a-9675-3c82fc86bd56
plot(x->-(6, *(6, ^(x, 5))), 0, 1, size=(500, 400), xlim=(0.0, 1.2), ylim=(0.0, 6.2), line=:darkblue, fill=(0, :lightblue), framestyle=:semi, title="f: x->(6-6x^5)", xguide="x", yguide="f: x->(6-6x^5)")
# ╔═╡ f062cf19-6507-4382-b450-57cf91c9d3a4
md"
---
###### Using $let$ to create local variables
$f(x,y)=x(1+xy)^2+y(1-y)+(1+xy)(1-y)$
"
# ╔═╡ 0c7b960d-35cf-4391-9496-7088b5a54326
f1(x, y) = # präfix operators
+(*(x,(+(1, *(x, y))^2)), # x(1+xy)^2
*(y, -(1, y)), # y(1-y)
*(+(1, *(x, y)), -(1, y))) # (1+xy)(1-y)
# ╔═╡ 42c074af-0452-458b-aae6-0eb22507883b
f1(1, 2)
# ╔═╡ 371c282e-4fc2-4939-8d7f-46ebb66a24a5
f2(x, y) = # infix operators
x*(1+x*y)^2 + y*(1-y) + (1+x*y)*(1-y)
# ╔═╡ 28e864e5-8fdd-4bd0-bc62-97cdc79e0c7e
f2(1, 2)
# ╔═╡ 14369a73-db5d-417e-a605-e31894b53a9c
md"
---
###### Using $let$ to create local variables
$f(x,y)=x(1+xy)^2+y(1-y)+(1+xy)(1-y) \equiv f(x,y)=xa^2+yb+ab$
with *local* variables
$a=(1+xy)$
and
$b=(1-y).$
"
# ╔═╡ b90a1a90-2e74-48cd-a34c-268d7bf4805f
function f3(x, y)
function f_helper(a, b)
square(x) = *(x, x)
+( *(x, square(a)),
*(y, b),
*(a, b))
end # function f_helper
f_helper(+(1, *(x, y)), -(1, y))
end # function f3
# ╔═╡ 2c0b827b-6c7b-4f12-9ab3-3ada545d7287
f3(1, 2)
# ╔═╡ 900bc14e-f097-46cd-9c6b-5784a5b37347
function f4(x, y)
((a, b) ->
+(*(x,a^2),*(y,b),*(a,b)))(+(1,*(x,y)),-(1,y)) # λ, arg must be inline !
end # function f4
# ╔═╡ bc5e9381-8162-481f-80bb-12324c692cea
f4(1, 2)
# ╔═╡ 1aab0c44-8270-4a34-963c-11855b3d030b
function f5(x, y)
(function (a, b)
+(*(x,a^2),*(y,b),*(a,b))
end)(+(1, *(x,y)), -(1, y)) # args must be close to '...end) !
end # function f5
# ╔═╡ 0b218a78-c5fc-4bf1-8fca-ab76f410bc0f
f5(1, 2)
# ╔═╡ fbda6639-bb4c-4aad-9880-8f87c6b0c3de
function f6(x, y)
let a = +(1, *(x, y)), b = -(1, y)
+(*(x,a^2),*(y,b),*(a,b)) # body of let
end # let
end # function f6
# ╔═╡ 8d03375c-77a5-4b92-9ec7-16ba347d5dc7
f6(1, 2)
# ╔═╡ 9f1a394d-2cca-42d1-bb03-5e9be765261e
let x = 5
let x = 3
+(x, *(x, 10))
end + x # to add the value of inner let '+ x' must be inline with 'end' !
end
# ╔═╡ 9102f937-b02d-4d5d-9fd6-f83643e27cdd
let x = 2 # semantics of Julia 'let' is different from Scheme's 'let' semantics !
let x = 3, y = +(x, 2)
*(x, y)
end
end
# ╔═╡ 634d23d2-df73-404c-9e19-145ca6b47305
function f7(x, y)
a = +(1, *(x, y))
b = -(1, y)
+(*(x,a^2),*(y,b),*(a,b))
end # function f7
# ╔═╡ 8a59bf14-0dc5-471c-bc0e-ec7c53e6ded6
f7(1, 2)
# ╔═╡ c2228ed7-7062-4810-aef2-b269845c26b0
md"
---
###### Nonterminating Lambda-Expression
in Scheme with tail-call optimization is
$((lambda (x) (x\;x))(lambda(x)(x\;x)))$
"
# ╔═╡ 9642417f-981c-4346-8a6f-3b1c69b862c8
try
(x -> x(x))(x -> x(x))
catch
@warn "lambda-expression is not terminating, so stack overflow"
end
# ╔═╡ 0013515a-fc8a-45df-8c08-3c7b7de17cb8
md"
---
##### CPS (= [Continuation Passing Style](https://en.wikipedia.org/wiki/Continuation-passing_style))
"
# ╔═╡ e230ec99-56b8-416a-9f47-9feaf46dab1b
md"
###### Basic CPS-Operators
"
# ╔═╡ 857a21e8-dc2f-415c-9669-aff2e1b30343
cpsAdd(x, y, k) = k(+(x, y))
# ╔═╡ cb84a330-6c45-4da2-8ac3-a9e843129573
cpsMult(x, y, k) = k(*(x, y))
# ╔═╡ dcd3061b-b54b-41a0-a218-1304c2559b1b
cpsExp(x, y, k) = k(^(x, y))
# ╔═╡ 697d7b63-cba6-4569-950e-10d3f7bbdff1
cpsEq(x, y, k) = k(==(x, y))
# ╔═╡ 70cec50e-6c07-460c-99a0-e3e9c582b155
cpsSub(x, y, k) = k(-(x, y))
# ╔═╡ 8cfe5793-265b-4e5c-8ae4-6b49f7c9c7b4
cpsIfThenElse(trueValue, FalseValue, condition, kTrue, kFalse) =
condition ?
kTrue(trueValue) : # application of true-Continuation
kFalse(FalseValue) # application of false-Continuation
# ╔═╡ 22c29e5f-9512-4460-9678-22f3d3efb4df
md"
---
###### Tests of Basic CPS-Operators
"
# ╔═╡ 4b6f4f18-d867-463b-80d7-51a9dddfcc51
cpsAdd(3, 4, xAddY -> print("x + y is $xAddY"))
# ╔═╡ 9fd6c383-c3b8-4b8b-957f-b8e458054a3d
cpsSub(1, 2, xSubY -> print("x == y is $xSubY"))
# ╔═╡ 12a0195e-3038-4f1d-968a-9631b59c41f4
cpsMult(3, 4, xMultY -> print("x * y is $xMultY"))
# ╔═╡ 8353921c-ec1c-4896-9ffa-91e06009a725
cpsExp(3, 4, xExpY -> print("x^y is $xExpY"))
# ╔═╡ a09663da-e08d-4866-9927-4fea1c9ac11c
cpsEq(1, 1, xEqY -> print("x == y is $xEqY"))
# ╔═╡ 28ecdc1f-291f-4dca-a0fa-22d66fef2fc2
cpsEq(1, 2, xEqY -> print("x == y is $xEqY"))
# ╔═╡ dbfffd66-2ecb-4e8c-89ff-cf6e635f2ac9
cpsIfThenElse( 0, 0, ==(0, 0),
value -> print("true case: value = $value "), # true-Continuation
value -> print("false case: value = $value ")) # false-Continuation
# ╔═╡ c1637306-5454-4e24-ac87-4555abebd7c7
cpsIfThenElse( 0, 5, ==(5, 0),
value -> print("true case: value = $value "), # true-Continuation
value -> print("false case: value = $value ")) # false-Continuation
# ╔═╡ 3a9b96f5-abe3-4140-807e-f05c0adc53f7
md"
---
##### Application of CPS-Style Functions
"
# ╔═╡ 2c4031b1-b1f2-47fc-ba72-7a3390445c79
md"
###### Nonrecursive Example: *Pythagoras*
$c=\sqrt{a^2+b^2}= (a^2+b^2)^{1/2}$
"
# ╔═╡ 973f5f48-040b-4552-9528-1e3dee12b49c
md"
---
###### DST (=*Direct* STyle)
"
# ╔═╡ e0f8d9f6-62a2-47d4-9fac-10672738b90b
function pythagorasDST(a, b) # DSt = Direct Style
^( +( *( a, a), *( b, b)), 1/2)
end # function pythagorasDSt
# ╔═╡ b850208d-49d7-489c-9867-2acbd366041d
let a = 3
b = 4
c = pythagorasDST(a, b)
end # let
# ╔═╡ eaad7fad-c313-482f-920d-5d2885876ee7
md"
---
###### ISS (= Imperative Sequential Style)
"
# ╔═╡ 8ebef2b8-3c45-4257-abae-6f7e4916a5c5
function pythagorasISS(a, b) # ISS = Imperative Sequential Style
let bSquare = *(b, b)
let aSquare = *(a, a)
let cSquare = +(bSquare, aSquare)
let c = ^(cSquare, 1/2)
print("c = sqrt(a^2 + b^2) = $c")
end # let
end # let
end # let
end # let
end # function pythagorasDSt
# ╔═╡ d9b274db-37d3-47cb-be5e-07f487fe13aa
pythagorasISS(3, 4)
# ╔═╡ e01734b4-c51e-4c9c-b3cb-c87f556e97cc
md"
---
###### NLS (= Nested Lambdas Style)
"
# ╔═╡ 81f36bde-b59a-4066-b5eb-21a6741a2b86
function pythagorasNLS(a, b) # NLS = Nested Lambdas Style
(bSquare ->
(aSquare ->
(cSquare ->
(c ->
print("c = sqrt(a^2 + b^2) = $c"))(^(cSquare, 1/2)))(+(bSquare, aSquare)))(*(a, a)))(*(b, b))
end # function pythagorasNLS
# ╔═╡ 2860e077-f4cb-441b-af25-6c11f3613e35
pythagorasNLS(3, 4)
# ╔═╡ 02dc74fa-d530-490e-ae86-b63da5466392
md"
---
##### CPS (= Continuation Passing Style)
"
# ╔═╡ c8c956c6-0b86-4d97-9840-4252ae571523
function pythagorasCPS(a, b, k) # CPS = Continuation Passing Style
cpsMult(b, b, bSquare ->
cpsMult(a, a, aSquare ->
cpsAdd(bSquare, aSquare, cSquare ->
cpsExp(cSquare, 1/2, k))))
end # function pythagorasCPS
# ╔═╡ 9c8df1cb-5e0e-4120-b6c9-a50e4ad305e6
let a = 3
b = 4
k = c -> print("c = sqrt(a^2 + b^2) = $c")
c = pythagorasCPS(a, b, k)
end # let
# ╔═╡ e03464fb-cfbe-402a-a6fc-1fa764fd20a3
md"
---
##### Linear Recursive Example: Factorial
"
# ╔═╡ 3e7759d5-bbb1-473d-a775-5fcd406ad9b6
md"
$n!=
\begin{cases}
1, & \text{ if } n = 0 \\
n \cdot(n-1)!, & \text{ if } n \gt 0 \\
\end{cases}$
"
# ╔═╡ 6c7029d1-d512-410e-953c-497601fc0ea6
md"
---
###### DST (=*Direct* STyle)
"
# ╔═╡ 03084fc1-4bb5-4fc2-8cd2-fa73b923b923
function factorialDST(n)
if ==(n, 0)
1
else
*(n, factorialDST(-(n, 1)))
end # if
end # function factorialDST
# ╔═╡ a4396645-8990-425f-94df-32e0ccfa7425
factorialDST(5)
# ╔═╡ 67cd2551-e8c9-4c0b-938e-5618d4b94339
md"
---
###### ISS (= Imperative Sequential Style)
"
# ╔═╡ def785ce-6ad1-4cf2-a3f2-cabd7cb0c33b
function factorialISS(n)
let isZero = ==(n, 0)
let result =
if isZero
1
else
let nSub1 = -(n, 1)
let facValNSub1 = factorialISS(nSub1)
*(n, facValNSub1)
end # let facValNSub1
end # let nSub1
end # if boolean
result
end # let result
end # let boolean
end # function factorialISS
# ╔═╡ 37e84a60-fe11-4687-b7be-7e1cfa39081c
factorialISS(5)
# ╔═╡ ebbcabe4-3ca7-456e-82e5-f93f816ecba2
md"
---
###### CPS-(= Continuation Passing)-Style
###### $factorialCPS1$ is a mixture of *DST* and *CPS*-Style:
The condition $if...then...else$ in $factorialCPS1$ is a relict of direct-style coding. This relict has to be removed to get a pure CPS-styled . This has been achieved in $factorialCPS2$.
"
# ╔═╡ e7e1a162-7450-4329-9cbb-2457a813076c
function factorialCPS1(n, k)
cpsEq(n, 0, isZero ->
if isZero
k(1)
else
cpsSub(n, 1, nSub1 ->
factorialCPS1(nSub1,
facValNSub1 ->
cpsMult(n, facValNSub1, k)))
end # if
) # end cpsEq
end # function factorialCPS1
# ╔═╡ d73f1ae9-f0d0-4c02-b6c2-6a9a19fdc238
factorialCPS1(0, result -> result)
# ╔═╡ d284b83d-ee52-4285-b005-16a2f9098e0b
factorialCPS1(0, result -> result)
# ╔═╡ a9958ad9-2092-4893-bdae-e31584b1fed8
factorialCPS1(5, result -> result)
# ╔═╡ 6c90570d-4a73-4cb6-8137-a8512d2b6736
factorialCPS1(6, result -> result)
# ╔═╡ a867dff9-f922-4214-88e2-cde3037ae9d6
md"
---
###### NLS (Nested Lambda Style)): $factorialCPS2$
"
# ╔═╡ 2d7e5950-a472-4ff8-80d6-317a8cec04be
function factorialNLS2(n)
let isNEqZero = n == 0
let
isNEqZero ? 1 :
let
nSub1 = n - 1
let facValNSub1 = factorialNLS2(nSub1)
n * facValNSub1
end # let
end # let
end # let
end # let
end # function factorialNLS2
# ╔═╡ fa36ac19-b792-455d-8667-e4b22013a493
factorialNLS2(0)
# ╔═╡ 75793fe4-9d5e-4ff9-b32e-a589e9722937
factorialNLS2(1)
# ╔═╡ 85e61913-b8a1-4a80-9bb5-d7b756a209cb
factorialNLS2(5)
# ╔═╡ 744f1453-d321-46f0-ba5d-cef4ea8b08c1
factorialNLS2(6)
# ╔═╡ 7293c431-85eb-40e0-ab74-0b3db732066d
md"
---
###### $factorialCPS2$ is a *pure* CPS-styled Recursive Factorial
The condition $if...then...else$ has been replaced by the function $cpsIfThenElse$ with Two Continuations
$trueContinuation$
and
$falseContinuation.$
"
# ╔═╡ e370bc78-e2ce-4db7-aefb-5678c9080977
function factorialCPS2(n, k)
cpsEq(n, 0, isNEqZero ->
cpsIfThenElse(1, n, isNEqZero,
stopValue -> k(stopValue), # true continuation
n -> cpsSub(n, 1, nSub1 -> # false continuation
factorialCPS2(nSub1,
facValNSub1 ->
cpsMult(n, facValNSub1, k)))))
end # function factorialCPS2
# ╔═╡ a028b140-6b8f-4303-8d45-9989e0d9163c
factorialCPS2(0, result -> result)
# ╔═╡ 4a912f72-0bd3-4678-819e-0ca3f34e7e59
factorialCPS2(1, result -> result)
# ╔═╡ 83e548b4-7f37-46bc-9ab4-e935ce201e16
factorialCPS2(5, result -> result)
# ╔═╡ a1910a28-207f-49dc-925e-9c61c1939304
factorialCPS2(6, result -> result)
# ╔═╡ c2c2b482-64ac-4306-94e2-1e79c82d9ac9
md"
---
##### Linear Iterative Example: Tail-Recursive Factorial
"
# ╔═╡ 6e2d6f64-b00b-4c4b-8408-215c5d58628c
md"
$n!=
\begin{cases}
product, & \text{ if } n \lt counter \\
iter(product, counter) ;= iter(counter * product, counter + 1), & \text{ if } n \ge counter \\
\end{cases}$
"
# ╔═╡ 42da07de-5508-4757-8ced-39cb8e67950a
md"
---
###### DST (=*Direct* STyle)
"
# ╔═╡ 48799cb6-d61c-4eda-aa29-c1e93c8a0302
function factorial2DST(n)
function iter(product, counter)
if counter == 0
product
else
iter( product * counter, counter - 1)
end # if
end # function iter
iter(1, n)
end # function factorial2DST
# ╔═╡ 2113e9c5-c003-4980-a8bd-6af6b5ee37ed
factorial2DST(0)
# ╔═╡ 7c87a7c4-7451-4bdd-a73e-6cf7c0184a9d
factorial2DST(1)
# ╔═╡ e93267e3-da0b-4794-9d28-3f56d0524a57
factorial2DST(5)
# ╔═╡ 78353412-675f-424d-a476-85fd38ad4cf8
factorial2DST(6)
# ╔═╡ 7e622eec-37ac-43e9-9483-fc114fed1d9b
md"
---
###### CPS-(= Continuation Passing)-Style
###### $factorial2CPS1$ is a mixture of *DST* and *CPS*-Style:
The condition $if...then...else$ in $factorial2CPS1$ is a relict of direct-style coding. This relict has to be removed to get a pure CPS-styled . This has been achieved in $factorial2CPS2$.
"
# ╔═╡ 97eeed7e-34c2-40a4-bfae-bbb3c4f53638
function factorial2CPS1(n, k)
function iter(product, counter, k)
cpsEq(counter, 0, isCounterZero ->
if isCounterZero
k(product) # unmodified continuation
else
cpsSub(counter, 1, counterSub1 ->
cpsMult(counter, product, countMultProd -> iter(countMultProd, counterSub1, k)))
end # if
)
end # function iter
iter(1, n, k)
end # function factorial2CPS1
# ╔═╡ 964dcb14-0373-4a15-a677-0e7cc683bf12
factorial2CPS1(0, result -> result)
# ╔═╡ 8ec93546-22c3-4cfa-933c-ffebec8917b4
factorial2CPS1(1, result -> result)
# ╔═╡ 319a46c2-f17b-4cb9-a581-48d33008e0d2
factorial2CPS1(5, result -> result)
# ╔═╡ 8ab5f711-7610-4d81-bb7a-fa218c0d9922
factorial2CPS1(6, result -> result)
# ╔═╡ c8a0352a-21b0-49e2-a0c6-857b06bcdf81
md"
---
###### $factorial2CPS2$ is a *pure* CPS-styled Recursive Factorial
The condition $if...then...else$ has been replaced by the function $cpsIfThenElse$ with Two Continuations
$trueContinuation$
and
$falseContinuation.$
"
# ╔═╡ ae12f10b-623d-49f2-bfeb-c7e646db832f
function factorial2CPS2(n, k)
function iter(product, counter, k)
cpsEq(counter, 0, isCounterZero ->
cpsIfThenElse(product, counter, isCounterZero,
product -> # true continuation
k(product),
counter -> # false continuation
cpsSub(counter, 1, counterSub1 ->
cpsMult(counter, product, countMultProd -> iter(countMultProd, counterSub1, k)))))
end # function iter
iter(1, n, k)
end # function factorial2CPS2
# ╔═╡ dd3a3675-b32c-4f1c-ae82-16109218f6c1
factorial2CPS2(0, result -> result)
# ╔═╡ 80653648-c27a-455e-b736-3f1e5bd80b15
factorial2CPS2(1, result -> result)
# ╔═╡ c8cc03ec-ce99-479f-bc1c-0eaecccf1a8a
factorial2CPS2(5, result -> result)
# ╔═╡ 972d5841-5c9f-4f82-b921-0061411eb8d0
factorial2CPS2(6, result -> result)
# ╔═╡ 5f25a438-fadf-4e9c-8234-7d668e797298
md"
---
#### 1.3.2.2 idiomatic imperative Julia ...
###### ... with while, Function, self-defined FloatOrSigned
"
# ╔═╡ f179f2cd-bb71-49ca-a3a4-c3ee48ef28c3
FloatOrSigned = Union{AbstractFloat, Signed}
# ╔═╡ 13138a8d-f944-4941-9372-57c7cb5ae76d
# idiomatic Julia-code with '::Function', '::Real', 'while', '+='
function sum2(term::Function, a::FloatOrSigned, next::Function, b::FloatOrSigned)::FloatOrSigned
sum = 0
while !(a > b)
sum += term(a)
a = next(a)
end # while
sum
end # function sum2
# ╔═╡ 066538f0-0a85-4763-97aa-85caaaf9fd6e
function pi_sum2(a::FloatOrSigned, b::FloatOrSigned)::FloatOrSigned
sum2(function(x) 1.0 / (x * (x + 2)) end , a, function(x) x+4 end, b)
end
# ╔═╡ 1b92beeb-8d34-45cd-807d-8b3aef90526c
8 * pi_sum2(1, 1E5)
# ╔═╡ 00b2e013-5134-4181-8e0e-e07babc4bf46
deviation = abs(8 * pi_sum2(1, 1E5) - pi)
# ╔═╡ 986c3531-565a-48eb-8ffe-20411ac119dc
function integral2(f::Function, a::FloatOrSigned, b::FloatOrSigned, dx::FloatOrSigned)::FloatOrSigned
sum2(f, a+dx/2.0, function(x) x+dx end, b) * dx
end # function integral2
# ╔═╡ 96e52bd7-bda8-41e6-8560-1e85dbd275b1
integral2(x->x^3, 0, 1, 0.001)
# ╔═╡ 94a7ffea-8915-4880-9e31-b6b01c6d27b8
integral2(x->-6x^5+6, 0.0, 1.0, 1.0E-4) # should be 5.0
# ╔═╡ 45c4441e-3a4f-4813-92ad-1b9744181661
md"
---
##### References
- **Abelson, H., Sussman, G.J. & Sussman, J.**; *Structure and Interpretation of Computer Programs*; Cambridge, Mass.: MIT Press, (2/e), 1996, [https://sarabander.github.io/sicp/](https://sarabander.github.io/sicp/); last visit 2022/08/25
- **Stark, P.A.**; *Introduction to Numerical Methods*, NY: Macmillan Company, 1970
- **Wikipedia**; *Continuation Passing Style*; [https://en.wikipedia.org/wiki/Continuation-passing_style](https://en.wikipedia.org/wiki/Continuation-passing_style) - last visit 2023/03/07 -
"
# ╔═╡ cc754c67-4e7c-4b34-abf3-4919ebf99386
md"
---
##### end of ch. 1.3.2
"
# ╔═╡ 965d0b6b-90cb-49d5-a482-d5982be4e264
md"
---
====================================================================================
This is a **draft** under the Attribution-NonCommercial-ShareAlike 4.0 International **(CC BY-NC-SA 4.0)** license. Comments, suggestions for improvement and bug reports are welcome: **claus.moebus(@)uol.de**
====================================================================================
"
# ╔═╡ 00000000-0000-0000-0000-000000000001
PLUTO_PROJECT_TOML_CONTENTS = """
[deps]
Plots = "91a5bcdd-55d7-5caf-9e0b-520d859cae80"
[compat]
Plots = "~1.38.7"
"""
# ╔═╡ 00000000-0000-0000-0000-000000000002
PLUTO_MANIFEST_TOML_CONTENTS = """
# This file is machine-generated - editing it directly is not advised
julia_version = "1.8.5"
manifest_format = "2.0"
project_hash = "d11d4fb0fd731734dc1c2ca399347ea5b41edbd7"
[[deps.ArgTools]]
uuid = "0dad84c5-d112-42e6-8d28-ef12dabb789f"
version = "1.1.1"
[[deps.Artifacts]]
uuid = "56f22d72-fd6d-98f1-02f0-08ddc0907c33"
[[deps.Base64]]
uuid = "2a0f44e3-6c83-55bd-87e4-b1978d98bd5f"
[[deps.BitFlags]]
git-tree-sha1 = "43b1a4a8f797c1cddadf60499a8a077d4af2cd2d"
uuid = "d1d4a3ce-64b1-5f1a-9ba4-7e7e69966f35"
version = "0.1.7"
[[deps.Bzip2_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "19a35467a82e236ff51bc17a3a44b69ef35185a2"
uuid = "6e34b625-4abd-537c-b88f-471c36dfa7a0"
version = "1.0.8+0"
[[deps.Cairo_jll]]
deps = ["Artifacts", "Bzip2_jll", "CompilerSupportLibraries_jll", "Fontconfig_jll", "FreeType2_jll", "Glib_jll", "JLLWrappers", "LZO_jll", "Libdl", "Pixman_jll", "Pkg", "Xorg_libXext_jll", "Xorg_libXrender_jll", "Zlib_jll", "libpng_jll"]
git-tree-sha1 = "4b859a208b2397a7a623a03449e4636bdb17bcf2"
uuid = "83423d85-b0ee-5818-9007-b63ccbeb887a"
version = "1.16.1+1"
[[deps.ChainRulesCore]]
deps = ["Compat", "LinearAlgebra", "SparseArrays"]
git-tree-sha1 = "c6d890a52d2c4d55d326439580c3b8d0875a77d9"
uuid = "d360d2e6-b24c-11e9-a2a3-2a2ae2dbcce4"
version = "1.15.7"
[[deps.ChangesOfVariables]]
deps = ["ChainRulesCore", "LinearAlgebra", "Test"]
git-tree-sha1 = "485193efd2176b88e6622a39a246f8c5b600e74e"
uuid = "9e997f8a-9a97-42d5-a9f1-ce6bfc15e2c0"
version = "0.1.6"
[[deps.CodecZlib]]
deps = ["TranscodingStreams", "Zlib_jll"]
git-tree-sha1 = "9c209fb7536406834aa938fb149964b985de6c83"
uuid = "944b1d66-785c-5afd-91f1-9de20f533193"
version = "0.7.1"
[[deps.ColorSchemes]]
deps = ["ColorTypes", "ColorVectorSpace", "Colors", "FixedPointNumbers", "Random", "SnoopPrecompile"]
git-tree-sha1 = "aa3edc8f8dea6cbfa176ee12f7c2fc82f0608ed3"
uuid = "35d6a980-a343-548e-a6ea-1d62b119f2f4"
version = "3.20.0"
[[deps.ColorTypes]]
deps = ["FixedPointNumbers", "Random"]
git-tree-sha1 = "eb7f0f8307f71fac7c606984ea5fb2817275d6e4"
uuid = "3da002f7-5984-5a60-b8a6-cbb66c0b333f"
version = "0.11.4"
[[deps.ColorVectorSpace]]
deps = ["ColorTypes", "FixedPointNumbers", "LinearAlgebra", "SpecialFunctions", "Statistics", "TensorCore"]
git-tree-sha1 = "600cc5508d66b78aae350f7accdb58763ac18589"
uuid = "c3611d14-8923-5661-9e6a-0046d554d3a4"
version = "0.9.10"
[[deps.Colors]]
deps = ["ColorTypes", "FixedPointNumbers", "Reexport"]
git-tree-sha1 = "fc08e5930ee9a4e03f84bfb5211cb54e7769758a"
uuid = "5ae59095-9a9b-59fe-a467-6f913c188581"
version = "0.12.10"
[[deps.Compat]]
deps = ["Dates", "LinearAlgebra", "UUIDs"]
git-tree-sha1 = "7a60c856b9fa189eb34f5f8a6f6b5529b7942957"
uuid = "34da2185-b29b-5c13-b0c7-acf172513d20"
version = "4.6.1"
[[deps.CompilerSupportLibraries_jll]]
deps = ["Artifacts", "Libdl"]
uuid = "e66e0078-7015-5450-92f7-15fbd957f2ae"
version = "1.0.1+0"
[[deps.Contour]]
git-tree-sha1 = "d05d9e7b7aedff4e5b51a029dced05cfb6125781"
uuid = "d38c429a-6771-53c6-b99e-75d170b6e991"
version = "0.6.2"
[[deps.DataAPI]]
git-tree-sha1 = "e8119c1a33d267e16108be441a287a6981ba1630"
uuid = "9a962f9c-6df0-11e9-0e5d-c546b8b5ee8a"
version = "1.14.0"
[[deps.DataStructures]]
deps = ["Compat", "InteractiveUtils", "OrderedCollections"]
git-tree-sha1 = "d1fff3a548102f48987a52a2e0d114fa97d730f0"
uuid = "864edb3b-99cc-5e75-8d2d-829cb0a9cfe8"
version = "0.18.13"
[[deps.Dates]]
deps = ["Printf"]
uuid = "ade2ca70-3891-5945-98fb-dc099432e06a"
[[deps.DelimitedFiles]]
deps = ["Mmap"]
uuid = "8bb1440f-4735-579b-a4ab-409b98df4dab"
[[deps.DocStringExtensions]]
deps = ["LibGit2"]
git-tree-sha1 = "2fb1e02f2b635d0845df5d7c167fec4dd739b00d"
uuid = "ffbed154-4ef7-542d-bbb7-c09d3a79fcae"
version = "0.9.3"
[[deps.Downloads]]
deps = ["ArgTools", "FileWatching", "LibCURL", "NetworkOptions"]
uuid = "f43a241f-c20a-4ad4-852c-f6b1247861c6"
version = "1.6.0"
[[deps.Expat_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "bad72f730e9e91c08d9427d5e8db95478a3c323d"
uuid = "2e619515-83b5-522b-bb60-26c02a35a201"
version = "2.4.8+0"
[[deps.FFMPEG]]
deps = ["FFMPEG_jll"]
git-tree-sha1 = "b57e3acbe22f8484b4b5ff66a7499717fe1a9cc8"
uuid = "c87230d0-a227-11e9-1b43-d7ebe4e7570a"
version = "0.4.1"
[[deps.FFMPEG_jll]]
deps = ["Artifacts", "Bzip2_jll", "FreeType2_jll", "FriBidi_jll", "JLLWrappers", "LAME_jll", "Libdl", "Ogg_jll", "OpenSSL_jll", "Opus_jll", "PCRE2_jll", "Pkg", "Zlib_jll", "libaom_jll", "libass_jll", "libfdk_aac_jll", "libvorbis_jll", "x264_jll", "x265_jll"]
git-tree-sha1 = "74faea50c1d007c85837327f6775bea60b5492dd"
uuid = "b22a6f82-2f65-5046-a5b2-351ab43fb4e5"
version = "4.4.2+2"
[[deps.FileWatching]]
uuid = "7b1f6079-737a-58dc-b8bc-7a2ca5c1b5ee"
[[deps.FixedPointNumbers]]
deps = ["Statistics"]
git-tree-sha1 = "335bfdceacc84c5cdf16aadc768aa5ddfc5383cc"
uuid = "53c48c17-4a7d-5ca2-90c5-79b7896eea93"
version = "0.8.4"
[[deps.Fontconfig_jll]]
deps = ["Artifacts", "Bzip2_jll", "Expat_jll", "FreeType2_jll", "JLLWrappers", "Libdl", "Libuuid_jll", "Pkg", "Zlib_jll"]
git-tree-sha1 = "21efd19106a55620a188615da6d3d06cd7f6ee03"
uuid = "a3f928ae-7b40-5064-980b-68af3947d34b"
version = "2.13.93+0"
[[deps.Formatting]]
deps = ["Printf"]
git-tree-sha1 = "8339d61043228fdd3eb658d86c926cb282ae72a8"
uuid = "59287772-0a20-5a39-b81b-1366585eb4c0"
version = "0.4.2"
[[deps.FreeType2_jll]]
deps = ["Artifacts", "Bzip2_jll", "JLLWrappers", "Libdl", "Pkg", "Zlib_jll"]
git-tree-sha1 = "87eb71354d8ec1a96d4a7636bd57a7347dde3ef9"
uuid = "d7e528f0-a631-5988-bf34-fe36492bcfd7"
version = "2.10.4+0"
[[deps.FriBidi_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "aa31987c2ba8704e23c6c8ba8a4f769d5d7e4f91"
uuid = "559328eb-81f9-559d-9380-de523a88c83c"
version = "1.0.10+0"
[[deps.GLFW_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Libglvnd_jll", "Pkg", "Xorg_libXcursor_jll", "Xorg_libXi_jll", "Xorg_libXinerama_jll", "Xorg_libXrandr_jll"]
git-tree-sha1 = "d972031d28c8c8d9d7b41a536ad7bb0c2579caca"
uuid = "0656b61e-2033-5cc2-a64a-77c0f6c09b89"
version = "3.3.8+0"
[[deps.GR]]
deps = ["Artifacts", "Base64", "DelimitedFiles", "Downloads", "GR_jll", "HTTP", "JSON", "Libdl", "LinearAlgebra", "Pkg", "Preferences", "Printf", "Random", "Serialization", "Sockets", "TOML", "Tar", "Test", "UUIDs", "p7zip_jll"]
git-tree-sha1 = "660b2ea2ec2b010bb02823c6d0ff6afd9bdc5c16"
uuid = "28b8d3ca-fb5f-59d9-8090-bfdbd6d07a71"
version = "0.71.7"
[[deps.GR_jll]]
deps = ["Artifacts", "Bzip2_jll", "Cairo_jll", "FFMPEG_jll", "Fontconfig_jll", "GLFW_jll", "JLLWrappers", "JpegTurbo_jll", "Libdl", "Libtiff_jll", "Pixman_jll", "Qt5Base_jll", "Zlib_jll", "libpng_jll"]
git-tree-sha1 = "d5e1fd17ac7f3aa4c5287a61ee28d4f8b8e98873"
uuid = "d2c73de3-f751-5644-a686-071e5b155ba9"
version = "0.71.7+0"
[[deps.Gettext_jll]]
deps = ["Artifacts", "CompilerSupportLibraries_jll", "JLLWrappers", "Libdl", "Libiconv_jll", "Pkg", "XML2_jll"]
git-tree-sha1 = "9b02998aba7bf074d14de89f9d37ca24a1a0b046"
uuid = "78b55507-aeef-58d4-861c-77aaff3498b1"
version = "0.21.0+0"
[[deps.Glib_jll]]
deps = ["Artifacts", "Gettext_jll", "JLLWrappers", "Libdl", "Libffi_jll", "Libiconv_jll", "Libmount_jll", "PCRE2_jll", "Pkg", "Zlib_jll"]
git-tree-sha1 = "d3b3624125c1474292d0d8ed0f65554ac37ddb23"
uuid = "7746bdde-850d-59dc-9ae8-88ece973131d"
version = "2.74.0+2"
[[deps.Graphite2_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "344bf40dcab1073aca04aa0df4fb092f920e4011"
uuid = "3b182d85-2403-5c21-9c21-1e1f0cc25472"
version = "1.3.14+0"
[[deps.Grisu]]
git-tree-sha1 = "53bb909d1151e57e2484c3d1b53e19552b887fb2"
uuid = "42e2da0e-8278-4e71-bc24-59509adca0fe"
version = "1.0.2"
[[deps.HTTP]]
deps = ["Base64", "CodecZlib", "Dates", "IniFile", "Logging", "LoggingExtras", "MbedTLS", "NetworkOptions", "OpenSSL", "Random", "SimpleBufferStream", "Sockets", "URIs", "UUIDs"]
git-tree-sha1 = "37e4657cd56b11abe3d10cd4a1ec5fbdb4180263"
uuid = "cd3eb016-35fb-5094-929b-558a96fad6f3"
version = "1.7.4"
[[deps.HarfBuzz_jll]]
deps = ["Artifacts", "Cairo_jll", "Fontconfig_jll", "FreeType2_jll", "Glib_jll", "Graphite2_jll", "JLLWrappers", "Libdl", "Libffi_jll", "Pkg"]
git-tree-sha1 = "129acf094d168394e80ee1dc4bc06ec835e510a3"
uuid = "2e76f6c2-a576-52d4-95c1-20adfe4de566"
version = "2.8.1+1"
[[deps.IniFile]]
git-tree-sha1 = "f550e6e32074c939295eb5ea6de31849ac2c9625"
uuid = "83e8ac13-25f8-5344-8a64-a9f2b223428f"
version = "0.5.1"
[[deps.InteractiveUtils]]
deps = ["Markdown"]
uuid = "b77e0a4c-d291-57a0-90e8-8db25a27a240"
[[deps.InverseFunctions]]
deps = ["Test"]
git-tree-sha1 = "49510dfcb407e572524ba94aeae2fced1f3feb0f"