-
Notifications
You must be signed in to change notification settings - Fork 9
/
README.html
4469 lines (3951 loc) · 173 KB
/
README.html
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
<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">
<head>
<!-- 2023-03-09 Thu 17:11 -->
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>Extending a Language — Writing Powerful Macros in Scheme</title>
<meta name="author" content="Marc Nieper-Wißkirchen" />
<meta name="generator" content="Org Mode" />
<style>
#content { max-width: 60em; margin: auto; }
.title { text-align: center;
margin-bottom: .2em; }
.subtitle { text-align: center;
font-size: medium;
font-weight: bold;
margin-top:0; }
.todo { font-family: monospace; color: red; }
.done { font-family: monospace; color: green; }
.priority { font-family: monospace; color: orange; }
.tag { background-color: #eee; font-family: monospace;
padding: 2px; font-size: 80%; font-weight: normal; }
.timestamp { color: #bebebe; }
.timestamp-kwd { color: #5f9ea0; }
.org-right { margin-left: auto; margin-right: 0px; text-align: right; }
.org-left { margin-left: 0px; margin-right: auto; text-align: left; }
.org-center { margin-left: auto; margin-right: auto; text-align: center; }
.underline { text-decoration: underline; }
#postamble p, #preamble p { font-size: 90%; margin: .2em; }
p.verse { margin-left: 3%; }
pre {
border: 1px solid #e6e6e6;
border-radius: 3px;
background-color: #f2f2f2;
padding: 8pt;
font-family: monospace;
overflow: auto;
margin: 1.2em;
}
pre.src {
position: relative;
overflow: auto;
}
pre.src:before {
display: none;
position: absolute;
top: -8px;
right: 12px;
padding: 3px;
color: #555;
background-color: #f2f2f299;
}
pre.src:hover:before { display: inline; margin-top: 14px;}
/* Languages per Org manual */
pre.src-asymptote:before { content: 'Asymptote'; }
pre.src-awk:before { content: 'Awk'; }
pre.src-authinfo::before { content: 'Authinfo'; }
pre.src-C:before { content: 'C'; }
/* pre.src-C++ doesn't work in CSS */
pre.src-clojure:before { content: 'Clojure'; }
pre.src-css:before { content: 'CSS'; }
pre.src-D:before { content: 'D'; }
pre.src-ditaa:before { content: 'ditaa'; }
pre.src-dot:before { content: 'Graphviz'; }
pre.src-calc:before { content: 'Emacs Calc'; }
pre.src-emacs-lisp:before { content: 'Emacs Lisp'; }
pre.src-fortran:before { content: 'Fortran'; }
pre.src-gnuplot:before { content: 'gnuplot'; }
pre.src-haskell:before { content: 'Haskell'; }
pre.src-hledger:before { content: 'hledger'; }
pre.src-java:before { content: 'Java'; }
pre.src-js:before { content: 'Javascript'; }
pre.src-latex:before { content: 'LaTeX'; }
pre.src-ledger:before { content: 'Ledger'; }
pre.src-lisp:before { content: 'Lisp'; }
pre.src-lilypond:before { content: 'Lilypond'; }
pre.src-lua:before { content: 'Lua'; }
pre.src-matlab:before { content: 'MATLAB'; }
pre.src-mscgen:before { content: 'Mscgen'; }
pre.src-ocaml:before { content: 'Objective Caml'; }
pre.src-octave:before { content: 'Octave'; }
pre.src-org:before { content: 'Org mode'; }
pre.src-oz:before { content: 'OZ'; }
pre.src-plantuml:before { content: 'Plantuml'; }
pre.src-processing:before { content: 'Processing.js'; }
pre.src-python:before { content: 'Python'; }
pre.src-R:before { content: 'R'; }
pre.src-ruby:before { content: 'Ruby'; }
pre.src-sass:before { content: 'Sass'; }
pre.src-scheme:before { content: 'Scheme'; }
pre.src-screen:before { content: 'Gnu Screen'; }
pre.src-sed:before { content: 'Sed'; }
pre.src-sh:before { content: 'shell'; }
pre.src-sql:before { content: 'SQL'; }
pre.src-sqlite:before { content: 'SQLite'; }
/* additional languages in org.el's org-babel-load-languages alist */
pre.src-forth:before { content: 'Forth'; }
pre.src-io:before { content: 'IO'; }
pre.src-J:before { content: 'J'; }
pre.src-makefile:before { content: 'Makefile'; }
pre.src-maxima:before { content: 'Maxima'; }
pre.src-perl:before { content: 'Perl'; }
pre.src-picolisp:before { content: 'Pico Lisp'; }
pre.src-scala:before { content: 'Scala'; }
pre.src-shell:before { content: 'Shell Script'; }
pre.src-ebnf2ps:before { content: 'ebfn2ps'; }
/* additional language identifiers per "defun org-babel-execute"
in ob-*.el */
pre.src-cpp:before { content: 'C++'; }
pre.src-abc:before { content: 'ABC'; }
pre.src-coq:before { content: 'Coq'; }
pre.src-groovy:before { content: 'Groovy'; }
/* additional language identifiers from org-babel-shell-names in
ob-shell.el: ob-shell is the only babel language using a lambda to put
the execution function name together. */
pre.src-bash:before { content: 'bash'; }
pre.src-csh:before { content: 'csh'; }
pre.src-ash:before { content: 'ash'; }
pre.src-dash:before { content: 'dash'; }
pre.src-ksh:before { content: 'ksh'; }
pre.src-mksh:before { content: 'mksh'; }
pre.src-posh:before { content: 'posh'; }
/* Additional Emacs modes also supported by the LaTeX listings package */
pre.src-ada:before { content: 'Ada'; }
pre.src-asm:before { content: 'Assembler'; }
pre.src-caml:before { content: 'Caml'; }
pre.src-delphi:before { content: 'Delphi'; }
pre.src-html:before { content: 'HTML'; }
pre.src-idl:before { content: 'IDL'; }
pre.src-mercury:before { content: 'Mercury'; }
pre.src-metapost:before { content: 'MetaPost'; }
pre.src-modula-2:before { content: 'Modula-2'; }
pre.src-pascal:before { content: 'Pascal'; }
pre.src-ps:before { content: 'PostScript'; }
pre.src-prolog:before { content: 'Prolog'; }
pre.src-simula:before { content: 'Simula'; }
pre.src-tcl:before { content: 'tcl'; }
pre.src-tex:before { content: 'TeX'; }
pre.src-plain-tex:before { content: 'Plain TeX'; }
pre.src-verilog:before { content: 'Verilog'; }
pre.src-vhdl:before { content: 'VHDL'; }
pre.src-xml:before { content: 'XML'; }
pre.src-nxml:before { content: 'XML'; }
/* add a generic configuration mode; LaTeX export needs an additional
(add-to-list 'org-latex-listings-langs '(conf " ")) in .emacs */
pre.src-conf:before { content: 'Configuration File'; }
table { border-collapse:collapse; }
caption.t-above { caption-side: top; }
caption.t-bottom { caption-side: bottom; }
td, th { vertical-align:top; }
th.org-right { text-align: center; }
th.org-left { text-align: center; }
th.org-center { text-align: center; }
td.org-right { text-align: right; }
td.org-left { text-align: left; }
td.org-center { text-align: center; }
dt { font-weight: bold; }
.footpara { display: inline; }
.footdef { margin-bottom: 1em; }
.figure { padding: 1em; }
.figure p { text-align: center; }
.equation-container {
display: table;
text-align: center;
width: 100%;
}
.equation {
vertical-align: middle;
}
.equation-label {
display: table-cell;
text-align: right;
vertical-align: middle;
}
.inlinetask {
padding: 10px;
border: 2px solid gray;
margin: 10px;
background: #ffffcc;
}
#org-div-home-and-up
{ text-align: right; font-size: 70%; white-space: nowrap; }
textarea { overflow-x: auto; }
.linenr { font-size: smaller }
.code-highlighted { background-color: #ffff00; }
.org-info-js_info-navigation { border-style: none; }
#org-info-js_console-label
{ font-size: 10px; font-weight: bold; white-space: nowrap; }
.org-info-js_search-highlight
{ background-color: #ffff00; color: #000000; font-weight: bold; }
.org-svg { }
</style>
</head>
<body>
<div id="content" class="content">
<h1 class="title">Extending a Language — Writing Powerful Macros in Scheme</h1>
<div id="table-of-contents" role="doc-toc">
<h2>Table of Contents</h2>
<div id="text-table-of-contents" role="doc-toc">
<ul>
<li><a href="#org62babe7">1. Preface</a></li>
<li><a href="#orgc7ffed7">2. Prerequisites</a>
<ul>
<li><a href="#org3d61cab">2.1. Chez Scheme</a></li>
<li><a href="#org1e5dbaf">2.2. Emacs</a></li>
<li><a href="#org21d06c2">2.3. Org</a></li>
<li><a href="#orgdd0bd51">2.4. Geiser</a></li>
<li><a href="#orgc08cb24">2.5. Paredit</a></li>
<li><a href="#orgfeac655">2.6. Initialization</a></li>
</ul>
</li>
<li><a href="#org4ccb527">3. The Scheme programming language</a></li>
<li><a href="#orgbd0169d">4. Some simple macros</a>
<ul>
<li><a href="#org23d8d4d">4.1. Incrementing a variable</a></li>
<li><a href="#org34d3bfa">4.2. A tracing <code>let</code></a></li>
<li><a href="#orgb20c886">4.3. Accessing vector locations through variables</a></li>
</ul>
</li>
<li><a href="#orgb09f098">5. Syntax objects</a>
<ul>
<li><a href="#orgd35e092">5.1. Identifiers</a></li>
<li><a href="#orgced5520">5.2. Constructing syntax objects</a></li>
<li><a href="#org5860e4f">5.3. Destructing syntax objects</a></li>
</ul>
</li>
<li><a href="#org24c2ba5">6. Syntax-case macros</a>
<ul>
<li><a href="#orga2ca29f">6.1. Macro transformers</a></li>
<li><a href="#org6163956">6.2. A fluid <code>let</code></a></li>
<li><a href="#org251a44b">6.3. Implementing a variant type in Scheme</a></li>
</ul>
</li>
<li><a href="#orgfac2e15">7. Breaking hygiene</a>
<ul>
<li><a href="#orgf76f6b0">7.1. A classical loop macro</a></li>
<li><a href="#org3570d26">7.2. Convenience syntax to bind implicit identifiers</a></li>
<li><a href="#org84f8d37">7.3. Definitions that make the bound name accessible</a></li>
<li><a href="#org6660d3a">7.4. Definitions of constants</a></li>
<li><a href="#org00a5c58">7.5. A pitfall</a></li>
</ul>
</li>
<li><a href="#orgb3b2938">8. Phasing</a>
<ul>
<li><a href="#org03e1249">8.1. (Relative) phases</a></li>
<li><a href="#orgdfa3cff">8.2. Identifier references at different phases</a></li>
</ul>
</li>
<li><a href="#orga704c43">9. Extensions</a>
<ul>
<li><a href="#org2fd1f18">9.1. Aliases</a></li>
<li><a href="#orge5209ea">9.2. Syntax parameters</a></li>
<li><a href="#orgabd5238">9.3. Identifier properties</a></li>
</ul>
</li>
<li><a href="#org22841b5">10. Complex examples</a>
<ul>
<li><a href="#org41bc2aa">10.1. An LR(1) parser generator implemented as a Scheme macro</a></li>
</ul>
</li>
<li><a href="#org597261d">11. Exercises</a></li>
</ul>
</div>
</div>
<p>
The canonical HTML-formatted version of this document can be found at
<a href="https://mnieper.github.io/scheme-macros/README.html">https://mnieper.github.io/scheme-macros/README.html</a>. The interactive
Org document is hosted at <a href="https://github.com/mnieper/scheme-macros">https://github.com/mnieper/scheme-macros</a>.
</p>
<div id="outline-container-org62babe7" class="outline-2">
<h2 id="org62babe7"><span class="section-number-2">1.</span> Preface</h2>
<div class="outline-text-2" id="text-1">
<p>
This document is an introduction to writing powerful macros in Scheme.
It was initially written on the occasion of a tutorial I give at the
<a href="https://bobkonf.de/2023/en/">BOB2023 Konferenz</a> in Berlin on 17 March 2023.
</p>
<p>
The macro facility, especially its built-in <i>hygiene</i>, is one of the
fundamental pillars of the Scheme programming language. While more
complicated than the simple token-replacing macros of other languages
like C, Scheme macros can be written in a way that make them robust
and so that the abstractions they offer seamless blend into the
language and cannot be distinguished from syntactic forms built into
the language. It is often felt that this expressiveness makes writing
Scheme macros more complicated (even something of a black art) than
writing C or Common Lisp macros, for example. One goal of this
tutorial is to convince the audience otherwise.
</p>
<p>
While the Scheme macro facility has always been avant-garde (and this
is one of the reasons why Scheme was chosen as the implementation
language for this tutorial), a lot of what is said here also applies
to languages that provide corresponding features. It is also a appeal
to language designers that languages should include a macro facility
as Scheme does, as this allows for small language cores and enables
the user to provide their own syntactic abstractions.
</p>
<p>
Another reason why the Scheme language is used in this tutorial is
that it has an exceptionally clear semantics, is a compact language,
and is easy to learn.
</p>
<p>
The document can both be read as is or used interactively in an Emacs
session. In the following section, a possible setup is described.
</p>
</div>
</div>
<div id="outline-container-orgc7ffed7" class="outline-2">
<h2 id="orgc7ffed7"><span class="section-number-2">2.</span> Prerequisites</h2>
<div class="outline-text-2" id="text-2">
</div>
<div id="outline-container-org3d61cab" class="outline-3">
<h3 id="org3d61cab"><span class="section-number-3">2.1.</span> Chez Scheme</h3>
<div class="outline-text-3" id="text-2-1">
<p>
We need a Scheme implementation. This tutorial assumes <a href="https://cisco.github.io/ChezScheme/">Chez Scheme</a>,
which is one of the most mature, standard-compliant Scheme
implementations. You can get Chez Scheme from its homepage. On
Debian-based GNU/Linux system like Ubuntu, it is prepackaged.
</p>
</div>
</div>
<div id="outline-container-org1e5dbaf" class="outline-3">
<h3 id="org1e5dbaf"><span class="section-number-3">2.2.</span> Emacs</h3>
<div class="outline-text-3" id="text-2-2">
<p>
We will use <a href="https://www.gnu.org/software/emacs/">GNU Emacs</a> as our development environment, which has great
tooling for Scheme. The typical GNU/Linux system ships with it.
</p>
<p>
For GNU Emacs < 28, enable the <a href="https://elpa.nongnu.org/">NonGNU Emacs Lisp Package Archive</a> in
your <a href="https://www.gnu.org/software/emacs/manual/html_node/emacs/Init-File.html">init file</a> or <a href="https://www.gnu.org/software/emacs/manual/html_node/emacs/Easy-Customization.html">customize</a> the variable <code>package-archives</code>.
Likewise, enable the <a href="https://elpa.nongnu.org/nongnu-devel/">NonGNU-devel ELPA Packages</a>.
</p>
</div>
</div>
<div id="outline-container-org21d06c2" class="outline-3">
<h3 id="org21d06c2"><span class="section-number-3">2.3.</span> Org</h3>
<div class="outline-text-3" id="text-2-3">
<p>
<a href="https://orgmode.org/">Org Mode</a> is a GNU Emacs major mode that allows to document, edit and
execute source code.
</p>
<p>
The current versions of Org packaged with Emacs hide Scheme evaluation
errors. This is fixed in the version in Org's git repository, for
which Org <a href="https://orgmode.org/org.html#Installation">provides installation instructions</a>.
</p>
<p>
Familiarize yourself with how one works with <a href="https://orgmode.org/org.html#Working-with-Source-Code">source code in an Org
document</a>, especially how to <a href="https://orgmode.org/org.html#Editing-Source-Code">edit</a> and <a href="https://orgmode.org/org.html#Evaluating-Code-Blocks">execute code</a>.
</p>
</div>
</div>
<div id="outline-container-orgdd0bd51" class="outline-3">
<h3 id="orgdd0bd51"><span class="section-number-3">2.4.</span> Geiser</h3>
<div class="outline-text-3" id="text-2-4">
<p>
<a href="https://www.nongnu.org/geiser/">Geiser</a> is a GNU Emacs package that allows to runs Scheme processes in
GNU Emacs, and which is used by Org's Babel. To install it, it is
enough to install the package <a href="https://gitlab.com/emacs-geiser/chez/-/blob/master/geiser-chez.el">geiser-chez</a> using GNU Emacs' <a href="https://www.gnu.org/software/emacs/manual/html_node/emacs/Package-Menu.html">package
menu</a>. We need the most recent development version.
</p>
</div>
</div>
<div id="outline-container-orgc08cb24" class="outline-3">
<h3 id="orgc08cb24"><span class="section-number-3">2.5.</span> Paredit</h3>
<div class="outline-text-3" id="text-2-5">
<p>
<a href="https://paredit.org/">Paredit</a>, a tool for parenthetical editing in Emacs makes working with
Scheme code a lot more pleasant. Like Geiser, it can be installed
through GNU Emacs' package manager.
</p>
</div>
</div>
<div id="outline-container-orgfeac655" class="outline-3">
<h3 id="orgfeac655"><span class="section-number-3">2.6.</span> Initialization</h3>
<div class="outline-text-3" id="text-2-6">
<p>
After the GNU Emacs packages have been installed, we want to customize
them for our needs. The following should go into your init file
unless you want to execute the following code every time you start GNU
Emacs.
</p>
<div class="org-src-container">
<pre class="src src-emacs-lisp">(<span style="color: #a020f0;">require</span> '<span style="color: #008b8b;">compile</span>)
(autoload 'enable-paredit-mode <span style="color: #8b2252;">"paredit"</span> <span style="color: #8b2252;">"Turn on pseudo-structural editing of Lisp code"</span> t)
(add-hook 'scheme-mode-hook #'enable-paredit-mode)
(show-paren-mode t)
(<span style="color: #a020f0;">setq</span> auto-mode-alist (cons '(<span style="color: #8b2252;">"\\.ss"</span> . scheme-mode) auto-mode-alist))
(<span style="color: #a020f0;">setq</span> auto-mode-alist (cons '(<span style="color: #8b2252;">"\\.sls"</span> . scheme-mode) auto-mode-alist))
(<span style="color: #a020f0;">setq</span> auto-mode-alist (cons '(<span style="color: #8b2252;">"\\.sps"</span> . scheme-mode) auto-mode-alist))
(add-to-list 'compilation-error-regexp-alist
'(<span style="color: #8b2252;">"^</span><span style="color: #8b2252; font-weight: bold;">\\</span><span style="color: #8b2252; font-weight: bold;">(</span><span style="color: #8b2252;">Exception</span><span style="color: #8b2252; font-weight: bold;">\\</span><span style="color: #8b2252; font-weight: bold;">|</span><span style="color: #8b2252;">Warning</span><span style="color: #8b2252; font-weight: bold;">\\</span><span style="color: #8b2252; font-weight: bold;">)</span><span style="color: #8b2252;">.*: .* </span><span style="color: #8b2252; font-weight: bold;">\\</span><span style="color: #8b2252; font-weight: bold;">(</span><span style="color: #8b2252;">line </span><span style="color: #8b2252; font-weight: bold;">\\</span><span style="color: #8b2252; font-weight: bold;">(</span><span style="color: #8b2252;">[0-9]+</span><span style="color: #8b2252; font-weight: bold;">\\</span><span style="color: #8b2252; font-weight: bold;">)</span><span style="color: #8b2252;">, char </span><span style="color: #8b2252; font-weight: bold;">\\</span><span style="color: #8b2252; font-weight: bold;">(</span><span style="color: #8b2252;">[0-9]+</span><span style="color: #8b2252; font-weight: bold;">\\</span><span style="color: #8b2252; font-weight: bold;">)</span><span style="color: #8b2252;"> of </span><span style="color: #8b2252; font-weight: bold;">\\</span><span style="color: #8b2252; font-weight: bold;">(</span><span style="color: #8b2252;">.*</span><span style="color: #8b2252; font-weight: bold;">\\</span><span style="color: #8b2252; font-weight: bold;">)</span><span style="color: #8b2252; font-weight: bold;">\\</span><span style="color: #8b2252; font-weight: bold;">)</span><span style="color: #8b2252;">"</span> 5 3 4 nil 2))
(<span style="color: #a020f0;">setq</span> geiser-default-implementation 'chez)
(org-babel-do-load-languages
'org-babel-load-languages
'((scheme . t)))
(<span style="color: #a020f0;">setq</span> org-confirm-babel-evaluate nil)
</pre>
</div>
</div>
</div>
</div>
<div id="outline-container-org4ccb527" class="outline-2">
<h2 id="org4ccb527"><span class="section-number-2">3.</span> The Scheme programming language</h2>
<div class="outline-text-2" id="text-3">
<p>
Scheme is programming language of the Lisp family. Its defining
properties are its uniform parenthesized syntax (inherited from Lisp),
first-class procedures and continuations, lexical scoping, dynamic
typing, proper tail calls and hygienic macros. It is primarly a
functional programming language but allows many other programming
paradigms.
</p>
<p>
The Scheme programming language was developed in the 1970s by Guy
L. Steele and Gerald Jay Sussman. Since then it has been refined and
further developed through a series of de facto standards called the
Revised<sup><i>n</i></sup> Report(s) on the Algorithmic Language Scheme (R/n/RS).
The two current standards are R6RS (2007) and R7RS-small (2013).
Despite the versioning and the timeline, R6RS is the more detailed,
more advanced and more modern standard<sup><a id="fnr.1" class="footref" href="#fn.1" role="doc-backlink">1</a></sup>.
</p>
<p>
In this tutorial, we work with the macro facility of R6RS, which is
far more powerful than the one of R7RS-small, and also discuss some
proposed or implemented extensions. Such extensions to the Scheme
programming language are often proposed, discussed and implemented
using the <a href="https://srfi.schemers.org/">Scheme Requests for Implementation</a> process, where everyone
can submit a <i>SRFI</i> extending the Scheme programming language.
Whenever we speak of the <i>Scheme</i> language in this text, we default to
the R6RS dialect.
</p>
<p>
For practical programming, one needs, of course, an implementation.
Scheme is possibly the programming language with the highest number of
implementations. The R6RS language has some very high-quality
implementations, including <a href="https://cisco.github.io/ChezScheme/">Chez Scheme</a>, <a href="https://www.gnu.org/software/guile/">GNU Guile</a>, <a href="https://scheme.fail/">Loko Scheme</a>, and <a href="https://racket-lang.org/">Racket</a>,
so for any application area, there will be a suitable Scheme system.
</p>
</div>
</div>
<div id="outline-container-orgbd0169d" class="outline-2">
<h2 id="orgbd0169d"><span class="section-number-2">4.</span> Some simple macros</h2>
<div class="outline-text-2" id="text-4">
<p>
Let us call a <i>combination</i> an expression in Scheme of the form
</p>
<div class="org-src-container">
<pre class="src src-scheme">(operator operand ...)
</pre>
</div>
<p>
An example is given by the following expression evaluating to the answer of life:
</p>
<div class="org-src-container">
<pre class="src src-scheme">(* 21 2)
</pre>
</div>
<pre class="example" id="orgc4d7cd4">
42
</pre>
<p>
Such a combination is usually evaluated by evaluating the operator and
the operands in some unspecific order and by then calling the
procedure resulting from the operator evaluation with arguments
resulting from the operand evaluations.
</p>
<p>
Scheme, however, also possesses special forms, which do not follow
this evaluation strategy. An example is given by the conditional <code>if</code>.
</p>
<div class="org-src-container">
<pre class="src src-scheme">(<span style="color: #a020f0;">if</span> (number? 2)
'ok
(/ 1 0))
</pre>
</div>
<pre class="example" id="orgb13069a">
ok
</pre>
<p>
If the conditional were a normal combination, the operands, and <code>(/ 1
0)</code> in particular, would have been evaluated first (and
unconditionally). Scheme recognizes special forms through the
operator in first position, namely if it is a keyword (a special type
of identifier). The Scheme macro facility allows the programmer to
define their own keywords.
</p>
</div>
<div id="outline-container-org23d8d4d" class="outline-3">
<h3 id="org23d8d4d"><span class="section-number-3">4.1.</span> Incrementing a variable</h3>
<div class="outline-text-3" id="text-4-1">
<p>
Let us ignore for a moment that mutation is frowned upon in functional
programming and let us assume that we have to frequently increase the
value of variables in our program. Given a variable <code>x</code>, this is done
in Scheme through the following expression:
</p>
<div class="org-src-container">
<pre class="src src-scheme">(<span style="color: #a020f0;">set!</span> x (+ x 1))
</pre>
</div>
<p>
That the variable <code>x</code> is repeated in this expression is unpleasant
(and may be considered a violation of the DRY principle), so we want
an operator akin to C's pre/post-increment operator. Unfortunately,
Scheme does not provide such an operator, but, fortunately, it doesn't
have to because we can build one ourself.
</p>
<p>
Our first attempt could be to write a procedure (the primary means of
abstraction in functional programming languages)<sup><a id="fnr.2" class="footref" href="#fn.2" role="doc-backlink">2</a></sup>:
</p>
<div class="org-src-container">
<pre class="src src-scheme">(<span style="color: #a020f0;">define</span> <span style="color: #0000ff;">incr!</span>
(<span style="color: #a020f0;">lambda</span> (x)
(<span style="color: #a020f0;">set!</span> x (+ x 1))))
</pre>
</div>
<p>
This attempt, however, is failed:
</p>
<div class="org-src-container">
<pre class="src src-scheme">(<span style="color: #a020f0;">define</span> <span style="color: #0000ff;">x</span> 1)
(incr! x)
x
</pre>
</div>
<pre class="example" id="org83d146f">
1
</pre>
<p>
The reason that it doesn't work — the variable's value is still 1
and not 2 — is that <code>(incr! x)</code> is a normal combination as
introduced earlier. As the arguments are evaluated first and the
procedure is called with their values, in this example, <code>incr!</code> is
called with the argument <code>1</code>. This is then bound to a new variable
<code>x</code> locally to <code>incr!</code>. It is this variable, which is increased by 1
and not the top-level variable.
</p>
<p>
The solution is, of course, to define <code>incr!</code> not as a procedure<sup><a id="fnr.3" class="footref" href="#fn.3" role="doc-backlink">3</a></sup>
but as a keyword. In the Scheme programming language, the
<code>define-syntax</code> keyword can be used for it:
</p>
<div class="org-src-container">
<pre class="src src-scheme">(<span style="color: #a020f0;">define-syntax</span> <span style="color: #a0522d;">incr!</span>
(<span style="color: #a020f0;">syntax-rules</span> ()
((incr! x)
(<span style="color: #a020f0;">set!</span> x (+ x 1)))))
</pre>
</div>
<p>
This definition says that <code>incr!</code> is defined to be a new keyword,
implemented as a macro. The <code>syntax-rules</code> line shall be viewed as
boilerplate for the moment (and we will come back to it later).
Important are the next two lines. The form <code>(incr! x)</code> is a pattern
saying that the macro matches against a use of the form <code>(keyword
form)</code> (where <code>keyword</code> is necessarily <code>incr!</code>). When the macro is
used, the pattern variable <code>x</code> is bound to the <code>form</code>. The form
<code>(set! x (+ x 1))</code> is a template. When the macro is used, the pattern
variables in the template are replaced with the forms they are bound
to and the substituted template is then used in place of the macro.
</p>
<p>
In the following example, <code>(incr! y)</code> is effectively substituted by
<code>(set! y (+ y 1))</code>, so we have achieved what we wanted<sup><a id="fnr.4" class="footref" href="#fn.4" role="doc-backlink">4</a></sup>:
</p>
<div class="org-src-container">
<pre class="src src-scheme">(<span style="color: #a020f0;">define</span> <span style="color: #0000ff;">y</span> 10)
(incr! y)
y
</pre>
</div>
<pre class="example" id="org5db5199">
11
</pre>
<p>
As a side note, we see from the discussion that <code>set!</code> is another
keyword (like <code>if</code>, it cannot be a procedure for the same reasons why
our attempt to write <code>incr!</code> as a procedure doesn't work).
</p>
<p>
As any other identifier in Scheme, the identifier <code>set!</code> can also be
rebound as in the following example:
</p>
<div class="org-src-container">
<pre class="src src-scheme">(<span style="color: #a020f0;">let</span> ([<span style="color: #a020f0;">set!</span> (<span style="color: #a020f0;">lambda</span> (x y) (+ x y))])
(<span style="color: #a020f0;">define</span> <span style="color: #0000ff;">x</span> 1)
(<span style="color: #a020f0;">set!</span> x 2))
</pre>
</div>
<pre class="example" id="org1f95af7">
3
</pre>
<p>
In the body of the <code>let</code> form, <code>set!</code> has lost its usual meaning and
is bound to a procedure adding its two arguments. It is most
interesting to see what happens when we use our <code>incr!</code> macro, which
refers to <code>set!</code>, in the body of the <code>let</code> form:
</p>
<div class="org-src-container">
<pre class="src src-scheme">(<span style="color: #a020f0;">let</span> ([<span style="color: #a020f0;">set!</span> (<span style="color: #a020f0;">lambda</span> (x y) (/ 1 0))])
(<span style="color: #a020f0;">define</span> <span style="color: #0000ff;">x</span> 1)
(incr! x)
x)
</pre>
</div>
<pre class="example" id="orgc7a2868">
2
</pre>
<p>
This example yields the correct result <code>2</code>, although calling <code>set!</code>
within the <code>let</code> body would raise an exception. The reason for this
is the already mentioned hygiene of Scheme macros. The identifier
<code>set!</code> in the output of the <code>incr!</code> macro didn't occur in its input
but came from the macro definition. Scheme macro hygiene now ensures
that it still refers to the lexical binding it had where it occured in
the program source. Note that the C preprocessor — as an example
for a very simple, if not primitive macro facility — wouldn't have
ensured it. Whether a C macro works correctly or not often depends on
the lexical environment of the macro use site.
</p>
<p>
We say that hygienic Scheme macros are referentially transparent.
This is already known from procedures in functional programming
languages and lexical scoping:
</p>
<div class="org-src-container">
<pre class="src src-scheme">(<span style="color: #a020f0;">define</span> <span style="color: #0000ff;">f</span>
(<span style="color: #a020f0;">let</span> ([x 1])
(<span style="color: #a020f0;">lambda</span> () x)))
(list (f)
(<span style="color: #a020f0;">let</span> ([x 2])
(f)))
</pre>
</div>
<pre class="example" id="org6596779">
(1 1)
</pre>
<p>
Wherever the procedure <code>f</code> is called, it always evaluates to <code>1</code>.
</p>
<p>
We finish this subsection with another example of hygiene:
</p>
<div class="org-src-container">
<pre class="src src-scheme">(<span style="color: #a020f0;">let</span> ([<span style="color: #a020f0;">set!</span> 2])
(incr! set!)
set!)
</pre>
</div>
<pre class="example" id="org99bd3d0">
3
</pre>
<p>
The result, which is the increment of the original value of the
variable <code>set!</code> by one, can again be explained by hygiene and by
distinguishing the identifier <code>set!</code> that appears in the macro use and
the same-named identifier <code>set!</code> appearing in the macro source.
Without distinguishing both, the macro use <code>(incr! set!)</code> is
transcribed to <code>(set! set! (+ set! 1))</code>. In this transcription, the
first <code>set!</code> originates from the macro transformer and thus still
refers to the lexical binding it had at that place. The other two
occurrences of <code>set!</code> are copies from the macro input and thus refer
to the lexical binding of <code>set!</code> as a let-bound variable.
</p>
</div>
</div>
<div id="outline-container-org34d3bfa" class="outline-3">
<h3 id="org34d3bfa"><span class="section-number-3">4.2.</span> A tracing <code>let</code></h3>
<div class="outline-text-3" id="text-4-2">
<p>
Simple loops are often written using the named <code>let</code> form as in the following example:
</p>
<div class="org-src-container">
<pre class="src src-scheme">(<span style="color: #a020f0;">define</span> <span style="color: #0000ff;">fact</span>
(<span style="color: #a020f0;">lambda</span> (n)
(<span style="color: #a020f0;">let</span> <span style="color: #0000ff;">f</span> ([n n] [a 1])
(<span style="color: #a020f0;">if</span> (zero? n)
a
(f (- n 1) (* a n))))))
</pre>
</div>
<p>
In order to facilitate debugging, let us define a version of the named
<code>let</code> form that prints the arguments with which the loop recursion is
entered and with which it is exited<sup><a id="fnr.5" class="footref" href="#fn.5" role="doc-backlink">5</a></sup>. As <code>let</code> is a special
form, this has to be a special form as well, so let us write our second macro:
</p>
<div class="org-src-container">
<pre class="src src-scheme"><span style="color: #b22222;">;; </span><span style="color: #b22222;">A form of a named let that prints information about each recursive</span>
<span style="color: #b22222;">;; </span><span style="color: #b22222;">call.</span>
(<span style="color: #a020f0;">define-syntax</span> <span style="color: #a0522d;">trace-let</span>
(<span style="color: #a020f0;">syntax-rules</span> ()
[(<span style="color: #a020f0;">trace-let</span> name ([var expr] ...) body1 ... body2)
(<span style="color: #a020f0;">let</span> <span style="color: #0000ff;">f</span> ([depth 0] [var expr] ...)
(<span style="color: #a020f0;">define</span> <span style="color: #0000ff;">name</span>
(<span style="color: #a020f0;">lambda</span> (var ...)
(f (+ depth 1) var ...)))
(indent depth)
(display <span style="color: #8b2252;">"("</span>)
(display 'name)
(<span style="color: #a020f0;">begin</span>
(display <span style="color: #8b2252;">" "</span>)
(display var))
...
(display <span style="color: #8b2252;">")"</span>)
(newline)
(call-with-values
(<span style="color: #a020f0;">lambda</span> ()
body1 ... body2)
(<span style="color: #a020f0;">lambda</span> val*
(indent depth)
(fold-left
(<span style="color: #a020f0;">lambda</span> (sep val)
(display sep)
(display val)
<span style="color: #8b2252;">" "</span>)
<span style="color: #8b2252;">""</span> val*)
(newline)
(apply values val*))))]))
<span style="color: #b22222;">;; </span><span style="color: #b22222;">Helper procedure referenced by the macro output of the macro above.</span>
(<span style="color: #a020f0;">define</span> <span style="color: #0000ff;">indent</span>
(<span style="color: #a020f0;">let</span> ([pattern <span style="color: #8b2252;">"| "</span>])
(<span style="color: #a020f0;">lambda</span> (depth)
(<span style="color: #a020f0;">do</span> ([i 0 (+ i 1)])
((> i depth))
(display (string-ref pattern (mod i 2)))))))
</pre>
</div>
<p>
In this macro, the pattern is given by <code>(trace-let name ([var expr]
...) body1 ... body2)</code>, while the template makes up the bulk of the
macro. Already in the pattern, we see a new syntax, the ellipsis
<code>...</code>. It means that the subpattern preceding it may appear repeated
zero or more times in the input. When such a subpattern is matched,
the contained pattern variables represent lists of forms.
</p>
<p>
In the template, the ellipsis means to repeat the preceding
subtemplate as many times as the pattern variables contained in it
represent forms. For this to work, every such subtemplate has to
contain at least one pattern variable, obviously, and all pattern
variables contained in it have to represent lists of forms of the same
length.
</p>
<p>
Note the occurrence of <code>begin</code> in the macro. Normally, in a procedure
body, <code>(begin expression ...)</code> is equivalent to the list of
<code>expressions</code>, here, however, we have to use it. The reason is that
following ellipsis refers the immediately preceding subtemplate, so it
is crucial that the two display commands (which we both want to
repeated once per variable) appear in a single form.
</p>
<p>
When we run the following test, we see the given result printed.
</p>
<div class="org-src-container">
<pre class="src src-scheme">(<span style="color: #a020f0;">define</span> <span style="color: #0000ff;">fact</span>
(<span style="color: #a020f0;">lambda</span> (n)
(<span style="color: #a020f0;">trace-let</span> f ([n n])
(<span style="color: #a020f0;">if</span> (zero? n)
1
(* (f (- n 1)) n)))))
(fact 3)
</pre>
</div>
<pre class="example" id="org8cc2160">
|(f 3)
| (f 2)
| |(f 1)
| | (f 0)
| | 1
| |1
| 2
|6
</pre>
<p>
We can demonstrate another facet of hygiene with this particular
macro. In the macro template, which is part of the macro's source,
the identifier <code>f</code> is introduced and is bound by <code>let</code> appearing next
to in the source. In the particular use of the macro above, the
pattern variable <code>name</code> represents another identifier name <code>f</code>, namely
the identifier with that name that appears in the macro use. Although
<code>f</code> coming from the macro use is bound in the macro output within the
scope of the binding of <code>f</code> coming from the macro text, it does not
shadow the other <code>f</code> as this would be a violation of hygiene.
Instead, the identifier <code>f</code> coming from the macro text is renamed by
the Scheme macro expander, at least conceptually (as it isn't inserted
as a free identifier, the precise name obviously doesn't matter).
</p>
<p>
The ellipsis can also be used to turn our <code>incr!</code> macro into one that
accepts more than one variable to increment:
</p>
<div class="org-src-container">
<pre class="src src-scheme">(<span style="color: #a020f0;">define-syntax</span> <span style="color: #a0522d;">incr!</span>
(<span style="color: #a020f0;">syntax-rules</span> ()
((incr! x ...)
(<span style="color: #a020f0;">begin</span>
(<span style="color: #a020f0;">set!</span> x (+ x 1))
...))))
</pre>
</div>
<p>
Let us briefly test our new extended macro:
</p>
<div class="org-src-container">
<pre class="src src-scheme">(<span style="color: #a020f0;">define</span> <span style="color: #0000ff;">x</span> 10)
(<span style="color: #a020f0;">define</span> <span style="color: #0000ff;">y</span> 20)
(incr! x y)
(list x y)
</pre>
</div>
<pre class="example" id="orgd97c078">
(11 21)
</pre>
<p>
The role of <code>begin</code> in the macro definition of the extended <code>incr!</code>
differs from the role in our previous use of <code>begin</code>. Here it is used
to solve the problem that the template that prescribes the macro
output has to be a single form.
</p>
<p>
One can also write the multi-variable <code>incr!</code> macro without the
ellipsis by letting the macro expand into itself. This is not
necessarily how one would do it, but here it serves as a demonstration
for further macro techniques:
</p>
<div class="org-src-container">
<pre class="src src-scheme">(<span style="color: #a020f0;">define-syntax</span> <span style="color: #a0522d;">incr!</span>
(<span style="color: #a020f0;">syntax-rules</span> ()
((incr!)
(values))
((incr! x . x*)
(<span style="color: #a020f0;">begin</span>
(<span style="color: #a020f0;">set!</span> x (+ x 1))
(incr! . x*)))))
</pre>
</div>
<p>
First of all, this is our first macro with two transcription <i>rules</i>,
where each rule consists of a pattern and of a template. The pattern
of the first rule is <code>(incr!)</code>, the pattern of the second rule is
<code>(incr! x . x*)</code>. Scheme's macro expander tries to match the macro
input against the patterns in the order in which the patterns appear
in the <code>syntax-rules</code> form.
</p>
<p>
The second new thing is a a pattern of the form <code>(incr! x . x*)</code>,
which matches an (improper) list of at least two elements, the first
being the macro keyword and the second one being bound to the pattern
variable <code>x</code>. The rest arguments are bound as an (improper) list to
the pattern variable <code>x*</code>.
</p>
<p>
Finally, this example demonstrates a recursive macro, that is a macro
that transforms the input into an instance of itself. As long as the
output of a macro use involves a new macro use (possibly with the same
keyword), the Scheme expander continues with transcribing the macro.
</p>
<p>
Let us not forget to test the new version of the macro:
</p>
<div class="org-src-container">
<pre class="src src-scheme">(<span style="color: #a020f0;">define</span> <span style="color: #0000ff;">x</span> 100)
(<span style="color: #a020f0;">define</span> <span style="color: #0000ff;">y</span> 200)
(incr! x y)
(list x y)
</pre>
</div>
<pre class="example" id="org9b0c3a7">
(101 201)
</pre>
</div>
</div>
<div id="outline-container-orgb20c886" class="outline-3">
<h3 id="orgb20c886"><span class="section-number-3">4.3.</span> Accessing vector locations through variables</h3>
<div class="outline-text-3" id="text-4-3">
<p>
A <i>vector</i> in Scheme is a collection of locations in the store that
can be linearly addressed. A new vector can be allocated with the
<code>vector</code> procedure:
</p>
<div class="org-src-container">
<pre class="src src-scheme">(<span style="color: #a020f0;">define</span> <span style="color: #0000ff;">v</span> (vector 1 2 3))
v
</pre>
</div>
<pre class="example" id="org0237271">
#(1 2 3)
</pre>
<p>
Vector elements can be retrieved using <code>vector-ref</code> and mutated using <code>vector-set!</code>:
</p>
<div class="org-src-container">
<pre class="src src-scheme">(vector-ref v 2)
</pre>
</div>
<pre class="example" id="org715b37c">
3
</pre>
<div class="org-src-container">
<pre class="src src-scheme">(vector-set! v 1 4)