Chapter 4, Metalinguistic Abstraction

Exercise 4.24


I tested using fib in both versions. I have also printed the time taken.

Note that while testing do not context switch between programs in computer else it will add context switching time too. So I first only checked analyzed version without any context switch and then I checked original version.

As can be seen in the output, the second call seems to reduce the time in analyzed version. However, the difference can be seen significantly only at 1000+ fibonacci number!

Analyzed version:

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
;;; M-Eval input:
(fib 5)

(Time Taken:  4)

;;; M-Eval value:
5

;;; M-Eval input:
(fib 5)

(Time Taken:  3)

;;; M-Eval value:
5

;;; M-Eval input:
(fib 30)

(Time Taken:  6)

;;; M-Eval value:
832040

;;; M-Eval input:
(fib 30)

(Time Taken:  3)

;;; M-Eval value:
832040

;;; M-Eval input:
(fib 100)

(Time Taken:  3)

;;; M-Eval value:
354224848179261915075

;;; M-Eval input:
(fib 100)

(Time Taken:  3)

;;; M-Eval value:
354224848179261915075

;;; M-Eval input:
(fib 500)

(Time Taken:  4)

;;; M-Eval value:
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125

;;; M-Eval input:
(fib 500)

(Time Taken:  4)

;;; M-Eval value:
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125

;;; M-Eval input:
(fib 1000)

(Time Taken:  5)

;;; M-Eval value:
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

;;; M-Eval input:
(fib 1000)

(Time Taken:  4)

;;; M-Eval value:
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

;;; M-Eval input:
(fib 5000)

(Time Taken:  6)

;;; M-Eval value:
3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125

;;; M-Eval input:
(fib 5000)

(Time Taken:  4)

;;; M-Eval value:
3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125

;;; M-Eval input:

Now, let’s see the same in old version:

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
;;; M-Eval value:
5

;;; M-Eval input:
(fib 5)

(Time Taken:  5)

;;; M-Eval value:
5

;;; M-Eval input:
(fib 10)

(Time Taken:  4)

;;; M-Eval value:
55

;;; M-Eval input:
(fib 10)

(Time Taken:  3)

;;; M-Eval value:
55

;;; M-Eval input:
(fib 30)

(Time Taken:  9)

;;; M-Eval value:
832040

;;; M-Eval input:
(fib 30)

(Time Taken:  4)

;;; M-Eval value:
832040

;;; M-Eval input:
(fib 100)

(Time Taken:  4)

;;; M-Eval value:
354224848179261915075

;;; M-Eval input:
(fib 100)

(Time Taken:  5)

;;; M-Eval value:
354224848179261915075

;;; M-Eval input:
(fib 500)

(Time Taken:  4)

;;; M-Eval value:
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125

;;; M-Eval input:
(fib 500)

(Time Taken:  10)

;;; M-Eval value:
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125

;;; M-Eval input:
(fib 1000)

(Time Taken:  14)

;;; M-Eval value:
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

;;; M-Eval input:
(fib 1000)

(Time Taken:  4)

;;; M-Eval value:
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

;;; M-Eval input:
(fib 5000)

(Time Taken:  15)

;;; M-Eval value:
3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125

;;; M-Eval input:
(fib 5000)

(Time Taken:  12)

;;; M-Eval value:
3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125

;;; M-Eval input:

Code changes to print time:

1
2
3
4
5
6
7
8
9
10
11
12
;;only in this procedure
(define (driver-loop)
  (prompt-for-input input-prompt)
  (let ((input (read)))
	(define stime (get-universal-time))
    (let ((output (eval input the-global-environment)))
	  (newline)
	  (display (list "Time Taken: " (- (get-universal-time) stime)))
	  (newline)
	  (announce-output output-prompt)
      (user-print output)))
  (driver-loop))