/
interpreter
executable file
·2423 lines (1926 loc) · 85.5 KB
/
interpreter
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
#!/usr/bin/perl
use File::Temp 'tempfile';
use Carp 'carp';
use Digest::SHA 'sha256_base64';
$|++;
my %data;
my %transient;
my %externalized_functions;
my @data_types;
my @script_args;
sub meta::define_form {
my ($namespace, $delegate) = @_;
push @data_types, $namespace;
*{"meta::${namespace}::implementation"} = $delegate;
*{"meta::$namespace"} = sub {
my ($name, $value) = @_;
chomp $value;
$data{"${namespace}::$name"} = $value;
$delegate->($name, $value);
};
}
meta::define_form 'meta', sub {
my ($name, $value) = @_;
eval $value;
carp $@ if $@;
};
meta::meta('datatypes::bootstrap', <<'__guYWiOv4zBmdrlI3k3sW7f/q/xsX38Xvzz0dwwLCIRM');
meta::define_form 'bootstrap', sub {};
__guYWiOv4zBmdrlI3k3sW7f/q/xsX38Xvzz0dwwLCIRM
meta::meta('datatypes::code_filter', <<'__gIaVDqDoWT04Y/vzEYyoyadmT36MLhB1ERa09udQZ9M');
meta::define_form 'code_filter', sub {
my ($name, $value) = @_;
*{"code_filter::$name"} = eval "sub {\n$value\n}";
carp $@ if $@;
};
__gIaVDqDoWT04Y/vzEYyoyadmT36MLhB1ERa09udQZ9M
meta::meta('datatypes::cpp_section', <<'__iSq5SVn3Vw0i1zHw0zegKAuS4cKl8QE2lqgoLXAYscI');
meta::define_form 'cpp_section', sub {
my ($name, $value) = @_;
$externalized_functions{$name} = "cpp_section::$name";
*{$name} = sub {
edit("cpp_section::$name");
};
};
__iSq5SVn3Vw0i1zHw0zegKAuS4cKl8QE2lqgoLXAYscI
meta::meta('datatypes::data', <<'__s2euAFkA/SbXvMzOkLZXrqX3TdtBzEODSWBAt7wXECA');
meta::define_form 'data', sub {
my ($name, undef) = @_;
$externalized_functions{$name} = "data::$name";
*{$name} = sub {
associate("data::$name", $_[1] || join('', <STDIN>)) if @_ > 0 && $_[0] eq '=';
edit("data::$name") if $_[0] eq 'edit';
retrieve("data::$name");
};
};
__s2euAFkA/SbXvMzOkLZXrqX3TdtBzEODSWBAt7wXECA
meta::meta('datatypes::function', <<'__XSIHGGHv0Sh0JBj9KIrP/OzuuB2epyvn9pgtZyWE6t0');
meta::define_form 'function', sub {
my ($name, $value) = @_;
$externalized_functions{$name} = "function::$name";
*{$name} = eval "sub {\n$value\n}";
carp $@ if $@;
};
__XSIHGGHv0Sh0JBj9KIrP/OzuuB2epyvn9pgtZyWE6t0
meta::meta('datatypes::internal_function', <<'__heBxmlI7O84FgR+9+ULeiCTWJ4hqd079Z02rZnl9Ong');
meta::define_form 'internal_function', sub {
my ($name, $value) = @_;
*{$name} = eval "sub {\n$value\n}";
carp $@ if $@;
};
__heBxmlI7O84FgR+9+ULeiCTWJ4hqd079Z02rZnl9Ong
meta::meta('datatypes::java_section', <<'__+OMNe3P39/PtqlXYIuMYT/tIyOF3QVpZJcXdO0xbkRw');
meta::define_form 'java_section', sub {
my ($name, $value) = @_;
$externalized_functions{$name} = "java_section::$name";
*{$name} = sub {
edit("java_section::$name");
};
};
__+OMNe3P39/PtqlXYIuMYT/tIyOF3QVpZJcXdO0xbkRw
meta::meta('datatypes::library', <<'__Uu9nRiHABRn+x19zBWmHpJF8gbfMA5v5MlpNoSE8MqE');
meta::define_form 'library', sub {
my ($name, $value) = @_;
eval $value;
$externalized_functions{$name} = "library::$name";
*{$name} = sub {edit("library::$name")};
warn $@ if $@;
};
__Uu9nRiHABRn+x19zBWmHpJF8gbfMA5v5MlpNoSE8MqE
meta::meta('datatypes::line_filter', <<'__/k1BhEweDsgaEdqrALbIEjvKhsVrk/hv//e/KPydA6A');
meta::define_form 'line_filter', sub {
my ($name, $value) = @_;
*{"line_filter::$name"} = eval "sub {\n$value\n}";
carp $@ if $@;
};
__/k1BhEweDsgaEdqrALbIEjvKhsVrk/hv//e/KPydA6A
meta::meta('datatypes::list-type', <<'__OKczvJ+6wi8VPNFcZ9ohlXjw+ychodWCfcELdli9p+w');
meta::define_form '_list_type', sub {
my ($outer_name, $outer_value) = @_;
$externalized_functions{$outer_name} = "_list_type::$outer_name";
*{$outer_name} = sub {
associate("${outer_value}::$_", '') for @_;
};
meta::define_form $outer_value, sub {
my ($name, $value) = @_;
$externalized_functions{$name} = "${outer_value}::$name";
*{$name} = sub {
my ($command, @xs) = @_;
my $xs = join "\n", @xs;
return grep length, split /\n/, retrieve("${outer_value}::$name") if $command eq 'items';
associate("${outer_value}::$name", retrieve("${outer_value}::$name") . "\n$xs") if $command eq 'add' || $command eq '<<';
edit("${outer_value}::$name") if $command eq 'edit';
return retrieve("${outer_value}::$name");
};
};
};
__OKczvJ+6wi8VPNFcZ9ohlXjw+ychodWCfcELdli9p+w
meta::meta('datatypes::message-color', <<'__nWmJgsP4S3LFdMPQnL+foYc9c5fgqIlEm6RppolzoX0');
meta::define_form 'message_color', sub {
my ($name, $value) = @_;
$externalized_functions{$name} = "message_color::$name";
terminal::color($name, $value);
*{$name} = sub {
associate("message_color::$name", $_[1] || join('', <STDIN>)) if @_ > 0 && $_[0] eq '=';
edit("message_color::$name") if $_[0] eq 'edit';
retrieve("message_color::$name");
};
};
__nWmJgsP4S3LFdMPQnL+foYc9c5fgqIlEm6RppolzoX0
meta::meta('datatypes::note', <<'__TGOjJwmj+QJp1giUQqg2bEaQe8RvqnrFEqyZhIpSC34');
meta::define_form 'note', sub {
my ($name, undef) = @_;
$externalized_functions{$name} = "note::$name";
*{$name} = sub {edit("note::$name")};
};
__TGOjJwmj+QJp1giUQqg2bEaQe8RvqnrFEqyZhIpSC34
meta::meta('datatypes::unlit_converter', <<'__2X1thh9LQ0oUWCfeWj297YwiGJA/klB7hVI2sWEFtEE');
meta::define_form 'unlit_converter', sub {
my ($name, $value) = @_;
*{"unlit_converter::$name"} = eval "sub {\n$value\n}";
carp $@ if $@;
};
__2X1thh9LQ0oUWCfeWj297YwiGJA/klB7hVI2sWEFtEE
meta::meta('datatypes::vim-highlighter', <<'__vsGBLVDC3S+pX/k/zl5CgXeAQz2QjpBkLgx0CJ4vcn0');
meta::define_form 'vim_highlighter', \&meta::bootstrap::implementation;
__vsGBLVDC3S+pX/k/zl5CgXeAQz2QjpBkLgx0CJ4vcn0
meta::meta('internal::runtime', <<'__Nd6Dp1A6nL7yAGeoRfeZETeaW8vnPN8HI9Diqo66vDA');
meta::define_form 'internal', \&meta::meta::implementation;
__Nd6Dp1A6nL7yAGeoRfeZETeaW8vnPN8HI9Diqo66vDA
meta::_list_type('list', <<'__ozA5XMClOtEgdzZUav/0c1lAk3Vku/dc4e2tQHgNkTk');
list
__ozA5XMClOtEgdzZUav/0c1lAk3Vku/dc4e2tQHgNkTk
meta::bootstrap('initialization', <<'__plktoDCjGQioE48vwfrH0xL3ulcYnTWp+fUvaFwRnnc');
#!/usr/bin/perl
use File::Temp 'tempfile';
use Carp 'carp';
use Digest::SHA 'sha256_base64';
$|++;
my %data;
my %transient;
my %externalized_functions;
my @data_types;
my @script_args;
sub meta::define_form {
my ($namespace, $delegate) = @_;
push @data_types, $namespace;
*{"meta::${namespace}::implementation"} = $delegate;
*{"meta::$namespace"} = sub {
my ($name, $value) = @_;
chomp $value;
$data{"${namespace}::$name"} = $value;
$delegate->($name, $value);
};
}
meta::define_form 'meta', sub {
my ($name, $value) = @_;
eval $value;
carp $@ if $@;
};
__plktoDCjGQioE48vwfrH0xL3ulcYnTWp+fUvaFwRnnc
meta::bootstrap('pod', <<'__3uM+GRhsAnxE6BFehM2nkGju4J93JQjqONxKbpE0Cdg');
=head1 NAME
object - Stateful file-based object
=head1 SYNOPSYS
object [options] action [arguments...]
object shell
=head1 DESCRIPTION
Stateful objects preserve their state between executions by rewriting themselves. Each time the script exits it replaces its contents with its new state. Thus
state management, for user-writable scripts, is completely transparent.
An object rewrites itself only if its state has changed. This may seem like a dangerous operation, but some checks are put into place to ensure that it goes
smoothly. First, the object is initially written to a separate file. Next, that file is executed and asked to provide a hashsum of its contents. The original
object is rewritten only if that hashsum is correct. This ensures that the replacement object is functional and has the right data.
Currently the only known way to lose your data is to edit the serialization-related functions in such a way that they no longer function. However, this is not
something most people will normally do. In the future there may be a locking mechanism to prevent unintentional edits of these attributes.
=cut
__3uM+GRhsAnxE6BFehM2nkGju4J93JQjqONxKbpE0Cdg
meta::code_filter('cpp', <<'__RnBPiqLeW7JfaMHW0CgoNF/vpNWmNs4SJULj+/ehEjo');
use File::Path 'mkpath';
use File::Basename 'dirname';
my ($line, %settings) = @_;
my $settings = $settings{'name'};
if ($settings =~ /\scpp(\s|$)/) {
my %properties;
my @keys_and_values = split /\s+/, $settings;
for (@keys_and_values) {
my ($k, $v) = split /=/;
$properties{$k} = $v;
}
if (my $filename = $properties{'name'}) {
mkpath(dirname(my $path = &{'source-directory'}() . "/$filename"));
open my $fh, $settings{'begin'} ? '>' : '>>', $path;
print $fh "$line\n" unless $settings{'begin'} || $settings{'end'};
close $fh;
return "\\lstset{caption=$filename}\n\\begin{cppcode}" if $settings{'begin'};
} else {
return '\begin{cppcode}' if $settings{'begin'};
}
return '\end{cppcode}' if $settings{'end'};
}
return $line;
__RnBPiqLeW7JfaMHW0CgoNF/vpNWmNs4SJULj+/ehEjo
meta::code_filter('java', <<'__Q16rFeNkyBdV6W9RLL9GKTJwnstfRqIfBpmDbVFNOqQ');
use File::Path 'mkpath';
my ($line, %settings) = @_;
my $settings = $settings{'name'};
if ($settings =~ /\sjava(\s|$)/) {
my %properties;
my @keys_and_values = split /\s+/, $settings;
for (@keys_and_values) {
my ($k, $v) = split /=/;
$properties{$k} = $v;
}
if ($properties{'class'}) {
my $classname = $properties{'class'};
my $package_directory = $properties{'package'};
$package_directory =~ tr[.][/];
mkpath(my $directory = &{'source-directory'}() . '/' . $package_directory);
open my $fh, $settings{'begin'} ? '>' : '>>', "$directory/${classname}.java";
print $fh "$line\n" unless $settings{'begin'} || $settings{'end'};
close $fh;
return "\\lstset{caption=$properties{package}.$properties{class}}\n\\begin{javacode}" if $settings{'begin'};
}
return '\begin{javacode}' if $settings{'begin'};
return '\end{javacode}' if $settings{'end'};
}
return $line;
__Q16rFeNkyBdV6W9RLL9GKTJwnstfRqIfBpmDbVFNOqQ
meta::code_filter('resource', <<'__gnuMnVX94wNmeabRscK/Tp+seTmMoqXAeoOdJ+H8ZX0');
use File::Path 'mkpath';
use File::Basename 'dirname';
my ($line, %settings) = @_;
my $settings = $settings{'name'};
if ($settings =~ /\sresource(\s|$)/) {
my %properties;
my @keys_and_values = split /\s+/, $settings;
for (@keys_and_values) {
my ($k, $v) = split /=/;
$properties{$k} = $v;
}
if (my $filename = $properties{'name'}) {
mkpath(dirname(my $path = &{'source-directory'}() . "/$filename"));
open my $fh, $settings{'begin'} ? '>' : '>>', $path;
print $fh "$line\n" unless $settings{'begin'} || $settings{'end'};
close $fh;
return "\\lstset{caption=$filename}\n\\begin{resource}" if $settings{'begin'};
} else {
return '\begin{resource}' if $settings{'begin'};
}
return '\end{resource}' if $settings{'end'};
}
return $line;
__gnuMnVX94wNmeabRscK/Tp+seTmMoqXAeoOdJ+H8ZX0
meta::code_filter('verbatim', <<'__AON9bxWzZOMpERGSJVrit8dkijYb5Re8IIg2PEC5i1s');
my ($line, %settings) = @_;
unless ($settings{'name'}) {
return '\begin{verbatim}' if $settings{'begin'};
return '\end{verbatim}' if $settings{'end'};
}
return $line;
__AON9bxWzZOMpERGSJVrit8dkijYb5Re8IIg2PEC5i1s
meta::cpp_section('beta', <<'__XoBWQ8N+vb29FEehFz/rRdmXNiF6/8kRcZ70uS4UOw8');
- $\beta$-Rewrite Representation
\label{sec:beta}
This section outlines the conversion process from a simple $\beta$-rewrite calculus to template metaprogramming constructs. This rewrite system then is combined with an \verb|eval| function
to form the basis for the metacircular interpreter defined in \Ref{section}{sec:metacircular}.
__XoBWQ8N+vb29FEehFz/rRdmXNiF6/8kRcZ70uS4UOw8
meta::cpp_section('cpp-introduction', <<'__dIO7xsJfuJqvPXdHd7TAMttntR4IjRjbT8tXbJv6WXI');
- Introduction to C++ Literate Coding
The C++ literate code interface is much like the Java one, except that code sections use the \verb|name=x| attribute rather than \verb|class=| and \verb|package=|. The name is expected to
include an extension, so for example \verb|:: cpp name=src/foo.h| is a correct heading.
:: cpp name=hello.cc
#include<iostream>
int main () {
std::cout << "Hello world!" << std::endl;
}
:.
__dIO7xsJfuJqvPXdHd7TAMttntR4IjRjbT8tXbJv6WXI
meta::cpp_section('introduction', <<'__36lFNhCinAJc2hlpemtaX2ZxHW/pZ5qFDb/SlqXBEVM');
- Introduction to Template Patterns
\label{sec:introduction}
Template expansion provides a pure untyped lambda calculus. All equality is extensional and the calculus supports higher-order functions (templates) with annotations at invocation, but not
declaration, time.\footnote{This makes it untyped. C++ templates also support function types using nested template syntax -- see \Ref{section}{sec:higher-order-function-types}.} This section
goes over the encoding of lambda calculus in the template system.
- Encoding constants
Constants are simply \verb|struct|s, \verb|class|es, or other types that don't take template parameters. It isn't a problem if they do take template parameters, of course; those will
simply be specified later once the constant has propagated through the lambda expansion.
:: cpp name=examples/introduction/constants.hh
// Defining a constant term
struct foo {
enum {value = 10};
};
// Defining a global constant also_foo = foo
typedef foo also_foo;
// Defining two templated terms that act as constants
template<class t> struct has_a_field {
t field;
};
template<int n> struct has_a_number {
enum {number = n};
};
:.
- First-order function encoding
The idea is to have \verb|struct|s that represent terms of the calculus. If they are templates, then they represent functions (which are also terms). For example:
:: cpp name=examples/introduction/first-order-functions.cc
#include <iostream>
#include "constants.hh"
// Defining the identity function, where the result
// can be retrieved by specifying bar<T>::type
template<class t> struct bar {
typedef t type;
};
// Defining a global constant identity_result = bar(also_foo)
typedef bar<also_foo>::type identity_result;
int main () {
std::cout << "foo::value = " <<
foo::value << std::endl <<
"also_foo::value = " <<
also_foo::value << std::endl <<
"identity_result::value = " <<
identity_result::value << std::endl;
}
:.
In practice there is some difficulty already. Notice the use of \verb|::type| to retrieve the value of a function application. This slot had to be assumed by the caller; it is similar to
JavaScript code like this:
:: resource name=examples/introduction/unfriendly-identity.js
// An unfriendly identity function.
var identity = function (x) {
return {type: x};
};
// Invocations must now look like this:
var y = identity(x).type;
:.
Having issues like this percolating through the design can be a real problem. Unless the slot is passed to every invocation site,\footnote{It also must be forwarded, which isn't possible
in C++ to the best of my knowledge.} invocations will be divergent and will create errors. This means that return values should be unified to a single slot, in this library (and the Boost
MPL) called \verb|::type|.\footnote{This may seem counter-intuitive, since the types here encode values in lambda-calculus. However, it does serve a mnemonic purpose later when value types
are used as template parameters, and dependent value-type relations are established. Once this happens it becomes useful to explicitly distinguish between type template parameters and
value template parameters.}
So we establish some conventions up front. Whenever you define a constant, it is used as-is without a contained \verb|typedef| that we have to know about. This is OK because we shouldn't
ever make assumptions about the members of types that are used as template parameters.
- Higher-order function encoding
Higher-order functions are possible by encoding slots for invocations.\footnote{This is equivalent to the distinction between pure, extensional object-oriented programming and pure,
extensional functional programming. In the latter, term juxtaposition (e.g. {\tt f x}) constitutes invocation of the default slot, generally referred to as {\em apply}. In the former,
slots are explicitly named, as would be the case in a language such as Java -- thus juxtaposition has no meaning on its own.} We do this by declaring another template inside the first:
:: cpp name=examples/introduction/higher-order-functions.cc
#include <iostream>
#include "constants.hh"
// Defining the K combinator
template<class t>
struct k {
template<class u>
struct apply {
typedef t type;
};
};
// Using that on two types
typedef has_a_number<5> t1;
typedef has_a_number<6> t2;
typedef k<t1>::apply<t2>::type should_be_t1;
int main () {
std::cout << "t1::number = " << t1::number << std::endl <<
"should_be_t1::number = " << should_be_t1::number << std::endl;
}
:.
In this example, \verb|k| has a call slot \verb|apply| that ultimately provides the value. So, for example, \verb|k<x>::apply<y>::type| is equivalent to the more concise \verb|k x y| in
Haskell, or \verb|((k x) y)| in Scheme.
At this point it should be clear that nothing is standardized here. Top-level functions are invoked directly, whereas returned functions use \verb|::apply<x>|. Type results from template
invocations are accessed as \verb|::type|. One way to go about fixing it is to make a rule that a function gets encoded a bit less directly:
:: cpp name=examples/introduction/indirect-functions-broken.cc
// Encoding the K combinator uniformly, but with compile errors
struct k {
template<class t>
struct apply {
template<class u>
struct apply {
typedef t type;
};
};
};
:.
However, if you compile it you get an error stating that you can't define a nested \verb|struct| with the same name as the outer one. The solution is to use an intermediate \verb|::type|
dereference to wrap the inner \verb|::apply<x>|.
:: cpp name=examples/introduction/indirect-functions.cc
#include <iostream>
#include "constants.hh"
// Encoding the K combinator uniformly
struct k {
template<class t>
struct apply {
struct type {
template<class u>
struct apply {
typedef t type;
};
};
};
};
typedef has_a_number<5> t1;
typedef has_a_number<6> t2;
typedef k::apply<t1>::type::apply<t2>::type should_be_t1;
int main () {
std::cout << "t1::number = " << t1::number << std::endl <<
"should_be_t1::number = " << should_be_t1::number << std::endl;
}
:.
At this point a nice pattern emerges. Whenever we apply a function to something, we get its \verb|::type| as well. So constants map to themselves, and function invocations are all of the
form \verb|f::apply<...>::type|.
- Higher-order function type signatures
\label{sec:higher-order-function-types}
C++ lets you specify type signatures for higher-order templates. This can be useful to ensure that a function possesses at least a certain Church arity\footnote{I use this term to refer to
the arity of the uncurried form of the function. For example, the Church arity of $\lambda x. \lambda y. x$ is 2, since uncurrying yields $\lambda(x,y).x$.} or takes at least so many
arguments. It also provides some notational convenience at invocation-time.
Here is the Haskell function that we will model in C++ templates:
:: resource name=examples/introduction/apply-two-function.hs
apply_two :: ((a, a) -> b) -> a -> b
apply_two f x = f (x, x)
:.
In template metaprogramming it isn't possible to express the constraints about values, but we can express constraints about arity and function status:
:: cpp name=examples/introduction/apply-two-function.cc
#include <iostream>
#include "constants.hh"
// Encoding the type signature as a template parameter specification
struct apply_two {
template<template<class arg1, class arg2> class f>
struct apply {
struct type {
template<class x>
struct apply {
typedef f<x, x> type;
};
};
};
};
// An example value for f
template<class x, class y>
struct sample_f {
typedef x x_type;
typedef y y_type;
};
typedef has_a_number<10> t1;
typedef has_a_number<12> t2;
typedef apply_two::apply<sample_f>::type::apply<t1>::type two_of_t1;
int main () {
std::cout << "t1::number = " << t1::number << std::endl <<
"two_of_t1::x_type::number = " << two_of_t1::x_type::number << std::endl <<
"two_of_t1::y_type::number = " << two_of_t1::y_type::number << std::endl;
}
:.
The parameter definition \verb|<template<class arg1, class arg2> class f>| is equivalent to the Haskell type signature \verb|f :: (a, b) -> c|; none of the individual types are specified,
but the template must be invoked on two parameters or not invoked at all.\footnote{Note that at this point I'm not referring to invocation using the {\tt ::apply} convention established
earlier. This invocation is just regular template expansion.} The other thing of note is that you can arbitrarily refine the left-hand side; for example:
::
template<template<template<class x> class f,
template<class y> class g> class compose>
struct composer {...};
:.
This is equivalent to \verb|composer :: ((a -> b), (c -> d)) -> e|. As far as I know there is no way to specify anything about the return type of a function using template syntax.
I'm not using template types in this project for a couple of reasons. First, declaring formals uses names (I'm actually not sure whether those names are considered reserved by C++, but I
assume so). Second, it isn't possible to encode slot types, and all invocation in the lambda-calculus encoding is done with the \verb|::apply| slot.
- Conditionals
Templates don't model conditionals {\em per se}. Rather, you can create conditionals by using pattern matching and explicit specialization. There are some weird limitations about this, but
here is the basic idea:
:: cpp name=examples/introduction/specialization.cc
#include <iostream>
#include "constants.hh"
// General case
template<class t>
struct piecewise {
typedef t type;
};
// When t = has_a_number<50>, do this instead
template<>
struct piecewise<has_a_number<50>> {
typedef has_a_number<100> type;
};
typedef piecewise<has_a_number<3>>::type general;
typedef piecewise<has_a_number<50>>::type specialized;
int main () {
std::cout << "general::number = " << general::number << std::endl <<
"specialized::number = " << specialized::number << std::endl;
}
:.
- Limitations of inner specialization
\label{sec:limitations-of-inner-specialization}
Because terminal (i.e.~non-expanding) types are extensionally equivalent, pattern matching can be used to reliably specialize template expansions. The only case where this doesn't work
is inside a class:
:: cpp name=examples/introduction/inner-specialization-broken.cc
template<class t>
struct container {
template<class u>
struct piecewise {
typedef u type;
};
// Compiler complains about this:
template<>
struct piecewise<int> {
typedef t type;
};
};
typedef container<int>::piecewise<int>::type foo;
:.
The solution to this problem is to break the inner class outside of the outer one and uncurry its arguments:
:: cpp name=examples/introduction/inner-specialization.cc
#include <iostream>
#include "constants.hh"
namespace inside_container {
template<class t, class u>
struct piecewise {
typedef u type;
};
template<class t>
struct piecewise<t, int> {
typedef t type;
};
}
template<class t>
struct container {
template<class u>
struct piecewise {
typedef typename inside_container::piecewise<t, u>::type type;
};
};
typedef has_a_number<1> t1;
typedef has_a_number<2> t2;
typedef container<t1>::piecewise<t2>::type general;
typedef container<t1>::piecewise<int>::type specialized;
int main () {
std::cout << "general::number = " << general::number << std::endl <<
"specialized::number = " << specialized::number << std::endl;
}
:.
The namespace here isn't necessary, but it hides what normally gets hidden when you create an anonymous closure. Also notice that it must be declared before \verb|container| due to C++'s
forward-reference semantics.\footnote{Despite this, template expansion is generally lazy in other ways.}
__36lFNhCinAJc2hlpemtaX2ZxHW/pZ5qFDb/SlqXBEVM
meta::cpp_section('lists', <<'__LfhvwpW0gQEWzwp/Qnhop9qi6JffJEXgVSTCx0qFyzA');
- List Functions
\label{sec:lists}
This section implements a Church-encoded linked list that forms the basic data structure for the $\beta$ rewrite process implemented in \Ref{section}{sec:beta}.
- Cons cells
The $\beta$ rewrite system assumes the existence of two data types. One is the {\em term}, which corresponds to a value that might get replaced, and the other is a cons cell of two values.
The first step to modeling these things is defining a cons cell, which for this system is Church-encoded:
:: cpp name=core/cons.hh
#ifndef CORE_CONS_HH
#define CORE_CONS_HH
#include "module/begin.hh"
def(cons) {
when(class h, class t) {
local_def(closure) fn(class f, call(f, h, t));
ret(closure);
};
def(hd) fn(q(class h, class t), h);
def(tl) fn(q(class h, class t), t);
def(nil) fn(class f, nil);
};
#include "module/end.hh"
#endif
:.
:: cpp name=tests/core/cons.cc
#include "core/cons.hh"
#include "unit/test.hh"
#include "unit/fixtures.hh"
deftest(cons_instantiation) {
let(foo, call_static(cons, n(5), n(6)));
let(five, call_static(foo, cons::hd));
let(six, call_static(foo, cons::tl));
assert_types_equal(five, n(5));
assert_types_equal(six, n(6));
assert_types_equal(foo, call_static(cons, n(5), n(6)));
};
runtest(cons_instantiation);
:.
Next to define a variadic list constructor. This uses C++0x variadic templates for specialized expansion. It's sort of possible without variadic templates, though the result is less
elegant. Note that because GCC doesn't yet implement variadic template argument unpacking this is not legal. Hopefully they will implement that soon, but until then it's probably going to
be longhand \verb|cons| invocation.
- Identity function
This is primarily useful for a fall-through case in a conditional.
:: cpp name=core/id.hh
#ifndef CORE_ID_HH
#define CORE_ID_HH
#include "module/begin.hh"
def(id) fn(class x, x);
#include "module/end.hh"
#endif
:.
:: cpp name=tests/core/id.cc
#include "core/cons.hh"
#include "core/id.hh"
#include "unit/test.hh"
#include "unit/fixtures.hh"
deftest(id_invocation) {
assert_types_equal(n(5), call_static(id, n(5)));
assert_types_equal(cons, call_static(id, cons));
};
:.
- {\tt map}, {\tt filter}, and {\tt fold}
These can all be implemented in terms of cons-cell juxtaposition, and that's what I'm doing here. (The Church encoding is very convenient for this reason.) Here are the mathematical
definitions of these functions:
\begin{align*}
\text{map}~f~xs & = xs~\lambda xy . [\text{cons}~(f~x),y] \\
\text{filter}~f~xs & = xs~\lambda xy . [(\text{cons}~x,y)~(f~x~\text{cons}~\text{tl})] \\
\text{fold}~f~(\text{cons}~x,xs) & = f~x~(\text{fold}~f~xs) \\
\text{fold}~f~(\text{cons}~x,\text{nil}) & = x
\end{align*}
__LfhvwpW0gQEWzwp/Qnhop9qi6JffJEXgVSTCx0qFyzA
meta::cpp_section('preprocessor', <<'__ru5k56Qd++9HNT0pf5XPca19NjbfGrBXwtGn3PEdJR8');
- Preprocessor Definitions
\label{sec:preprocessor-definitions}
The goal of this section is to implement a layer of abstraction over the base template constructs. Roughly, the operations are:
e[
+ Defining a global constant
+ Defining a local variable
+ Applying a function to an expression \label{itm:apply-function-to-expression}
+ Returning a value from a function
+ Defining a named function
]e
Each of these operations has a standard form.\footnote{There are two for \Ref{item}{itm:apply-function-to-expression}; one form is used outside of a function body and the other is used
inside. The difference has to do with disambiguating template expansions and is covered in \Ref{section}{sec:function-application}. Also a great article about the role of {\tt typename} in
C++, its uses, and its limitations: \url{http://pages.cs.wisc.edu/~driscoll/typename.html}.} The definition of a shorthand for each is given in the following subsections.
- Preprocessor limitations
One notable limitation of the C preprocessor when working with templates is that it doesn't treat \verb|<| and \verb|>| as nested parentheticals.\footnote{It wouldn't be possible for it to
do the right thing here anyway, since the preprocessor sees code before types have been defined. However, template punctuation was an unfortunate choice considering its ambiguity with
relational operators, and the fact that relational operators are always ungrouped while template parameter delimiters are always grouped.} This has the unfortunate effect of splitting on
commas that separate template parameters, e.g.:
::
#define f(x) ...
template<class x, class y>
struct foo {...};
f(foo<bar, bif>); // Error here; too many arguments
:.
In value-space you can deal with this by explicitly parenthesizing expressions, but parentheses aren't a transparent construct in type-space. The way I'm getting around this for now is to
make macros variadic and always put any template invocations at the end:
::
#define f(x...) typedef x bar;
:.
This will preserve the commas in the original expression, although its use may be limited to the GNU preprocessor.\footnote{A more standard way to do this is to use the {\tt
\_\_VA\_ARGS\_\_} builtin and an anonymous ellipsis.} This macro is called \verb|q| and is defined in \Ref{section}{sec:variadic-protection}.
Another limitation has to do with brace matching. In order to write syntax in a natural way, it is helpful to write macros that behave more or less with standard C syntax; that is, the
block occurs after the macro invocation:
::
macro_invocation(x, y, z) { block }
:.
However, a problem arises when the macro is responsible for expanding two sets of braces, as might be the case for a nested \verb|struct|:
::
// Need to generate this code:
struct foo {
struct bar { stuff };
};
// This macro definition won't do it:
#define generate() \
struct foo { \
struct bar
// This code:
generate() {
stuff
};
// Expands to this:
struct foo {
struct bar {
stuff
};
// <- No closing brace!
:.
However, certain cases where this would have been used can be worked around. It comes into play when defining templates as functions; see \Ref{section}{sec:defun}.
- Variadic protection
\label{sec:variadic-protection}
As mentioned earlier, we need a way to work around the C preprocessor's inability to identify \verb|<>| groups for template parameters. The simplest way is to introduce a protecting macro
\verb|q| to quote a variadic construct but group it into just one argument.
:: cpp name=preprocessor/q.hh
#ifdef LISP_PREPROCESSOR_DEFINE
# define LISP_PREPROCESSOR_Q_ENABLED
# define q(x...) x
#else
# undef LISP_PREPROCESSOR_Q_ENABLED
# undef q
#endif
:.
- Global constants
\label{sec:global-definitions}
A global constant is just a standalone \verb|struct|. To encode this, we create the \verb|def()| macro, which basically just expands out to \verb|struct|. However, it is a bit clearer than
its expansion, especially in the context of defining functions and values.
This module, like all of the preprocessor utilities, can be enabled and disabled multiple times during preprocessing. This prevents the macros from interfering with regular code, which
ultimately enables clearer macro naming. The mechanism that governs enabling and disabling is the \verb|LISP_PREPROCESSOR_DEFINE| preprocessor variable. If defined, then the header is run
in ``definition mode'' and will create macros. Otherwise it will undefine the macros. You can see whether a macro is defined as well; each header file defines a macro called
\verb|LISP_PREPROCESSOR_X_ENABLED|, where \verb|X| is the upper-case name of the header file. This macro is undefined when the header is disabled.
Note that you shouldn't ever include this header file directly. See \Ref{section}{sec:preprocessor-interface} for a simple interface to enable and disable preprocessor macros.
:: cpp name=preprocessor/def.hh
#ifdef LISP_PREPROCESSOR_DEFINE
# define LISP_PREPROCESSOR_DEF_ENABLED
# define def(name) struct name
#else
# undef LISP_PREPROCESSOR_DEF_ENABLED
# undef def
#endif
:.
- Local variables
Within a \verb|struct|, local variables are prefixed with \verb|private|.
:: cpp name=preprocessor/let.hh
#ifdef LISP_PREPROCESSOR_DEFINE
# define LISP_PREPROCESSOR_LET_ENABLED
# define let(name, value...) private: typedef value name
# define local_def(name) private: struct name
#else
# undef LISP_PREPROCESSOR_LET_ENABLED
# undef let
# undef local_def
#endif
:.
- Function application
\label{sec:function-application}
It is assumed that function application involves dependent types.\footnote{In the C++ sense, not the type-theoretic sense. C++ dependent types are the transitive closure of template
variables through the expansion graph.} In that case, the default \verb|call(x, ...)| works fine. If, however, the function call's types are already resolved and do not depend on template
variables, then you will probably want to use \verb|call_static| instead.
:: cpp name=preprocessor/call.hh
#ifdef LISP_PREPROCESSOR_DEFINE
# define LISP_PREPROCESSOR_CALL_ENABLED
# define call(lhs, rhs...) typename lhs::template apply<rhs>::type
# define call_static(lhs, rhs...) lhs::apply<rhs>::type
#else
# undef LISP_PREPROCESSOR_CALL_ENABLED
# undef call
# undef call_static
#endif
:.
- Returning a value
It is straightforward to return a named value. This always takes the form \verb|typedef x type|, where \verb|x| is the value to be returned. For simplicity's sake, I'm going to assume that
whatever value should be returned has a name to preserve the uniformity of the return expansion. Note that it is prefixed with \verb|public| to override any previous local variables that
were defined.
:: cpp name=preprocessor/ret.hh
#ifdef LISP_PREPROCESSOR_DEFINE
# define LISP_PREPROCESSOR_RET_ENABLED
# define ret(value...) public: typedef value type
#else
# undef LISP_PREPROCESSOR_RET_ENABLED
# undef ret
#endif
:.
- Defining a named function
To remain in the mindset of the model C++ uses for template specialization, defining a named function is a two-step process. First, you define the outer \verb|struct| using \verb|def()|
(see \Ref{section}{sec:global-definitions}). Inside that you can specify the cases using the \verb|when()| macro.
:: cpp name=preprocessor/when.hh
#ifdef LISP_PREPROCESSOR_DEFINE
# define LISP_PREPROCESSOR_WHEN_ENABLED
# define when(parameters...) template <parameters> struct apply
#else
# undef LISP_PREPROCESSOR_WHEN_ENABLED
# undef when
#endif
:.
- Defining and returning closures
\label{sec:defun}
It is fairly simple to return a closure. The idea is that you create a local named function and then return that by name, so to implement the K combinator, for example, you would do
something like this:
::
def(k) {
when(class x) {
local_def(inner) {
when(class y) {
ret(x);
};
};
ret(inner);
};
};
:.
However, that's a bulky representation given that no explicit specialization is occurring. It would be tempting to implement a \verb|defun| macro like this:
::
#define defun(name, params...) \
def(name) {}; \
template<params> struct name::apply
:.
\noindent however C++ doesn't allow you to define inner \verb|struct|s after the fact.\footnote{While it might allow a forward definition for a normal {\tt struct}, this isn't possible for
a templated {\tt struct}, so we're back to square one.} What is possible, on the other hand, is to use a shorthand macro to return a single expression. As long as you're not using any
\verb|let| variables, this is a quick and easy way to do it. Unfortunately it is necessary to use the \verb|q| macro here, since otherwise it would be impossibile to distinguish the
parameters from the return value.
:: cpp name=preprocessor/fn.hh
#ifdef LISP_PREPROCESSOR_DEFINE
# define LISP_PREPROCESSOR_FN_ENABLED
# define fn(params, return_value...) {\
public: template<params> struct apply { \
ret(return_value); \
}; \
}
#else
# undef LISP_PREPROCESSOR_FN_ENABLED
# undef fn
#endif
:.
The usage of this construct, then, would be something like this: