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
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
#![doc(html_logo_url = "https://raw.githubusercontent.com/cuplv/adapton-talk/master/logos/adapton-logo-bonsai.png",
       html_root_url = "https://docs.rs/adapton/")]
/*!

Adapton for Rust
================

This Rust implementation embodies the latest implementation
[Adapton](http://adapton.org), which offers a foundational,
language-based semantics for [general-purpose incremental computation](wikipedia.org/en/Incremental_computing).

Programming model
--------------------

- The [documentation below](#adapton-programming-model) gives many
  illustrative examples, with pointers into the other Rust documentation.
- The [`engine` module](https://docs.rs/adapton/0/adapton/engine/index.html)
  gives the core programming interface.

Resources
---------------

- [Presentations and benchmark results](https://github.com/cuplv/adapton-talk#benchmark-results)
- [IODyn: Adapton collections, for algorithms with dynamic input and output](https://github.com/cuplv/iodyn.rust)
- [Adapton Lab: Evaluation and testing](https://github.com/cuplv/adapton-lab.rust)

Background
---------------

Adapton proposes the _demanded computation graph_ (or **DCG**), and a
demand-driven _change propagation_ algorithm. Further, it proposes
first-class _names_ for identifying cached data structures and
computations. For a quick overview of the role of names in incremental
computing, we give [background on incremental computing with names](#background-incremental-computing-with-names), below.

The following academic papers detail these technical proposals:

- **DCG, and change propagation**: [_Adapton: Composable, demand-driven incremental computation_, **PLDI 2014**](http://www.cs.umd.edu/~hammer/adapton/).
- **Nominal memoization**: [_Incremental computation with names_, **OOPSLA 2015**](http://arxiv.org/abs/1503.07792).
- **Type and effect structures**: The draft [_Typed Adapton: Refinement types for incremental computation with precise names_](https://arxiv.org/abs/1610.00097).

Why Rust?
----------

Adapton's first implementations used Python and OCaml; The latest
implementation in Rust offers the best performance thus far, since (1)
Rust is fast, and (2) [traversal-based garbage collection presents
performance challenges for incremental
computation](http://dl.acm.org/citation.cfm?doid=1375634.1375642).  By
liberating Adapton from traversal-based collection, [our empirical
results](https://github.com/cuplv/adapton-talk#benchmark-results) are
both predictable and scalable.

Adapton programming model
==========================

**Adapton roles**: Adapton proposes _editor_ and _achivist roles_:

 - The **Editor role** _creates_ and _mutates_ input, and _demands_ the
   output of incremental computations in the **Archivist role**.

 - The **Archivist role** consists of **Adapton thunks**, where each is
   cached computation that consumes incremental input and produces
   incremental output.

**Examples:** The examples below illustrate these roles, in increasing complexity:

 - [Start the DCG engine](#start-the-dcg-engine)
 - [Create incremental cells](#create-incremental-cells)
 - [Observe `Art`s](#observe-arts)
 - [Mutate input cells](#mutate-input-cells)
 - [Demand-driven change propagation](#demand-driven-change-propagation) and [switching](#switching)
 - [Memoization](#memoization)
 - [Create thunks](#create-thunks)
 - [Use `force_map` for more precise dependencies](#use-force_map-for-more-precise-dependencies)
 - [Nominal memoization](#nominal-memoization)
 - [Nominal cycles](#nominal-cycles)
 - [Nominal firewalls](#nominal-firewalls)

**Programming primitives:** The following list of primitives covers
the core features of the Adapton engine.  Each primitive below is
meaningful in each of the two, editor and archivist, roles:

 - **Ref cell allocation**: Mutable input (editor role), and cached data structures that change across runs (archivist role).
   - [**`cell!`**](https://docs.rs/adapton/0/adapton/macro.cell.html) -- Preferred version
   - [`let_cell!`](https://docs.rs/adapton/0/adapton/macro.let_cell.html)  -- Useful in simple examples
   - [`engine::cell`](https://docs.rs/adapton/0/adapton/engine/fn.cell.html) -- Engine's raw interface
 - **Observation** and **demand**: Both editor and archivist role.
   - [**`get!`**](https://docs.rs/adapton/0/adapton/macro.get.html) -- Preferred version
   - [`engine::force`](https://docs.rs/adapton/0/adapton/engine/fn.force.html) -- Engine's raw interface
   - [`engine::force_map`](https://docs.rs/adapton/0/adapton/engine/fn.force_map.html) -- A variant for observations that compose before projections
 - **Thunk Allocation**: Both editor and archivist role.
   - Thunk allocation, **_without_ demand**:
     - [**`thunk!`**](https://docs.rs/adapton/0/adapton/macro.thunk.html) -- Preferred version
     - [`let_thunk!`](https://docs.rs/adapton/0/adapton/macro.let_thunk.html) -- Useful in simple examples
     - [`engine::thunk`](https://docs.rs/adapton/0/adapton/engine/fn.thunk.html) -- Engine's raw interface (can be cumbersome)
   - Thunk allocation, **_with_ demand**:
     - [**`memo!`**](https://docs.rs/adapton/0/adapton/macro.memo.html) -- Preferred version
     - [`let_memo!`](https://docs.rs/adapton/0/adapton/macro.let_memo.html) -- Useful in simple examples

Start the DCG engine
=====================

The call `init_dcg()` below initializes a DCG-based engine, replacing
the `Naive` default engine.

```
#[macro_use] extern crate adapton;
use adapton::macros::*;
use adapton::engine::*;

fn main() {
    manage::init_dcg();

    // Put example code below here
# let c : Art<usize> = cell!( 123 );
# assert_eq!( get!(c), 123 );
}
```

# Create incremental cells

Commonly, the input and intermediate data of Adapton computations
consists of named reference `cell`s.  A reference `cell` is one
variety of `Art`s; another are [`thunk`s](#create-thunks).

## Implicit `cell` names

Behind the scenes, the (editor's) invocation `cell!(123)` uses an
imperative global counter to choose a unique name to hold the number
`123`. After each use, it increments this global counter, ensuring
that each such number is used at most once.

```
# #[macro_use] extern crate adapton;
# fn main() {
# use adapton::macros::*;
# use adapton::engine::*;
# manage::init_dcg();
let c : Art<usize> = cell!( 123 );

assert_eq!( get!(c), 123 );
# }
```

## Naming strategy: *Global counter* ###

Using a global counter to name cells, as above, _may_ be appopriate
for the Editor role, but is _never appropriate for the Archivist
role_, since this global counter is too sensitive to global
(often-changing) properties, such as an index into the sequence of all
allocations, globally.

To replace this global counter, we the Archivist may give names
*explicitly*, as shown in various forms, below.


## Explicitly named `cell`s

### Names via Rust "identifiers"

Sometimes we name a cell using a Rust identifier.  We specify this
case using the notation `[ name ]`, which specifies that the cell's
name is a string, constructed from the Rust identifer `name`:

```
# #[macro_use] extern crate adapton;
# fn main() {
# use adapton::macros::*;
# use adapton::engine::*;
# manage::init_dcg();
let c : Art<usize> = cell!([c] 123);

assert_eq!(get!(c), 123);
# }
```

### Optional `Name`s

Most generally, we supply an expression `optional_name` of type
`Option<Name>` to specify the name for the `Art`.  This `Art` is
created by either `cell` or `put`, in the case that `optional_name` is
`Some(name)` or `None`, respectively:

```
# #[macro_use] extern crate adapton;
# fn main() {
# use adapton::macros::*;
# use adapton::engine::*;
# manage::init_dcg();
let n : Name = name_of_str(stringify!(c));
let c : Art<usize> = cell!([Some(n)]? 123);

assert_eq!(get!(c), 123);

let c = cell!([None]? 123);

assert_eq!(get!(c), 123);
# }
```

# Observe `Art`s

The macro `get!` is sugar for `engine::force!`, with reference
introduction operation `&`:

```
# #[macro_use] extern crate adapton;
# fn main() {
# use adapton::macros::*;
# use adapton::engine::*;
# manage::init_dcg();
let c : Art<usize> = cell!(123);

assert_eq!( get!(c), force(&c) );
# }
```

Since the type `Art<T>` classifies both `cell`s and
[`thunk`s](#create-thunks), the operations `force` and `get!` can be
used interchangeably on `Art<T>`s that arise as `cell`s or `thunk`s.

Mutate input cells
=========================

One may mutate cells explicitly, or _implicitly_, which is common in Nominal Adapton.

The editor (implicitly or explicitly) mutates cells that hold input
and they re-demand the output of the archivist's computations.  During
change propagation, the archivist mutates cells with implicit
mutation.

**Implicit mutation uses nominal allocation**: By allocating a cell
with the same name, one may _overwrite_ cells with new content:

```
# #[macro_use] extern crate adapton;
# fn main() {
# use adapton::macros::*;
# use adapton::engine::*;
# manage::init_dcg();
let n : Name = name_of_str(stringify!(c));
let c : Art<usize> = cell!([Some(n.clone())]? 123);

assert_eq!(get!(c), 123);

// Implicit mutation (re-use cell by name `n`):
let d : Art<usize> = cell!([Some(n)]? 321);

assert_eq!(d, c);
assert_eq!(get!(c), 321);
assert_eq!(get!(d), 321);
# }
```

**No names implies no effects**: Using `None` to allocate cells always
**gives distinct cells, with no overwriting:

```
# #[macro_use] extern crate adapton;
# fn main() {
# use adapton::macros::*;
# use adapton::engine::*;
# manage::init_dcg();

let c = cell!([None]? 123);
let d = cell!([None]? 321);

assert_eq!(get!(c), 123);
assert_eq!(get!(d), 321);
# }
```

**Explicit mutation, via `set`**: If one wants mutation to be totally
explicit, one may use `set`:

```
# #[macro_use] extern crate adapton;
# fn main() {
# use adapton::macros::*;
# use adapton::engine::*;
# manage::init_dcg();
let n : Name = name_of_str(stringify!(c));
let c : Art<usize> = cell!([Some(n)]? 123);

assert_eq!(get!(c), 123);

// Explicit mutation (overwrites cell `c`):
set(&c, 321);

assert_eq!(get!(c), 321);
# }
```


Demand-driven change propagation
=================================

The example below demonstrates _demand-driven change propagation_,
which is unique to Adapton's DCG, and its approach to incremental
computation.  The example DCG below consists of two kinds of nodes:

- [Cells](#create-incremental-cells) consist of data that changes over
  time, including (but not limited to) incremental input.

- [Thunks](#create-thunks) consist of computations whose observations
  and results are cached in the DCG.

The simple example below uses two mutable input cells, `num` and
`den`, whose values are used by an intermediate subcomputation `div`
that divides the numerator in `num` by the denominator in `den`, and a
thunk `check` that first checks whether the denominator is zero
(returning zero if so) and if non-zero, returns the value of the
division:

```
# #[macro_use] extern crate adapton;
# fn main() {
# use adapton::macros::*;
# use adapton::engine::*;
# manage::init_dcg();
#
// Two mutable inputs, for numerator and denominator of division
let num = cell!(42);
let den = cell!(2);

// In Rust, cloning is explicit:
let den2 = den.clone(); // clone _global reference_ to cell.
let den3 = den.clone(); // clone _global reference_ to cell, again.

// Two subcomputations: The division, and a check thunk with a conditional expression
let div   = thunk![ get!(num) / get!(den) ];
let check = thunk![ if get!(den2) == 0 { None } else { Some(get!(div)) } ];
# }
```

After allocating `num`, `den` and `check`, the editor changes `den`
and observes `check`, inducing the following change propagation
behavior.  In sum, _whether_ `div` runs is based on _demand_ from the
Editor (of the output of `check`), _and_ the value of input cell
`den`, via the condition in `check`:

1. When the editor demands thunk `check` the first time, Adapton
   executes the condition, and cell `den` holds `2`, which is non-zero.
   Hence, the `else` branch executes `get!(div)`, which demands the
   output of the division, `21`.

2. After this first observation of `check`, the editor changes cell
   `den` to `0`, and re-demands the output of thunk `check`.  In
   response, Adapton's change propagation algorithm first re-executes
   the condition (not the division), and the condition branches to the
   `then` branch, resulting in `None`; in particular, it does _not_
   re-demand the `div` node, though this node still exists in the DCG.

3. Next, the programmer changes `den` back to its original value, `2`,
   and re-demands the output of `check`.  In response, change
   propagation re-executes the condition, which re-demands the output
   of `div`.  Change propagation attempts to "clean" the `div` node
   before re-executing it.  To do so, it compares its _last
   observations_ of `num` and `den` to their current values, of `42`
   and `2`, respectively.  In so doing, it finds that these earlier
   observations match the current values.  Consequently, it _reuses_
   the output of the division (`21`) _without_ having to re-execute
   the division.


```
# #[macro_use] extern crate adapton;
# fn main() {
# use adapton::macros::*;
# use adapton::engine::*;
# manage::init_dcg();
#
# // Two mutable inputs, for numerator and denominator of division
# let num = cell!(42);
# let den = cell!(2);
#
# // In Rust, cloning is explicit:
# let den2 = den.clone(); // clone _global reference_ to cell.
# let den3 = den.clone(); // clone _global reference_ to cell, again.
#
# // Two subcomputations: The division, and a check thunk with a conditional expression
# let div   = thunk![ get!(num) / get!(den) ];
# let check = thunk![ if get!(den2) == 0 { None } else { Some(get!(div)) } ];
#
// Observe output of `check` while we change the input `den`
// Editor Step 1: (Explained in detail, below)
assert_eq!(get!(check), Some(21));

// Editor Step 2: (Explained in detail, below)
set(&den3, 0);
assert_eq!(get!(check), None);

// Editor Step 3: (Explained in detail, below)
set(&den3, 2);
assert_eq!(get!(check), Some(21));  // division is reused
# }
```
[Slides with illustrations](https://github.com/cuplv/adapton-talk/blob/master/adapton-example--div-by-zero/)
of the graph structure and the code side-by-side may help:

**Editor Step 1**

<img src="https://raw.githubusercontent.com/cuplv/adapton-talk/master/adapton-example--div-by-zero/Adapton_Avoiddivbyzero_10.png"
   alt="Slide-10" style="width: 800px;"/>

**Editor Steps 2 and 3**

<img src="https://raw.githubusercontent.com/cuplv/adapton-talk/master/adapton-example--div-by-zero/Adapton_Avoiddivbyzero_12.png"
   alt="Slide_12" style="width: 200px;"/>
<img src="https://raw.githubusercontent.com/cuplv/adapton-talk/master/adapton-example--div-by-zero/Adapton_Avoiddivbyzero_16.png"
   alt="Slide_16" style="width: 200px;"/>
<img src="https://raw.githubusercontent.com/cuplv/adapton-talk/master/adapton-example--div-by-zero/Adapton_Avoiddivbyzero_17.png"
   alt="Slide-17" style="width: 200px;"/>
<img src="https://raw.githubusercontent.com/cuplv/adapton-talk/master/adapton-example--div-by-zero/Adapton_Avoiddivbyzero_23.png"
   alt="Slide-23" style="width: 200px;"/>

[Full-sized slides](https://github.com/cuplv/adapton-talk/blob/master/adapton-example--div-by-zero/)

In sum, _whether_ `div` runs is based on _demand_ from the Editor (of
`check`), _and_ the value of input `den`.  The reuse of `div`
illustrates the _switching pattern_, which is unique to Adapton's
approach to incremental computation.

Switching
-----------

In the [academic literature on Adapton](http://matthewhammer.org/adapton/),
we refer to the three-step
pattern of change propagation illustrated above as _switching_:

1. [The demand of `div` switches from being present (in step 1)](https://github.com/cuplv/adapton-talk/tree/master/adapton-example--div-by-zero#initial-graph-after-initial-demand-due-to-1st-get),
2. [to absent (in step 2)](https://github.com/cuplv/adapton-talk/tree/master/adapton-example--div-by-zero#updated-graph-after-first-cleaning-phase-due-to-2nd-get),
3. [to present (in step 3)](https://github.com/cuplv/adapton-talk/tree/master/adapton-example--div-by-zero#updated-graph-after-second-cleaning-phase-due-to-3rd-get).

Past work on self-adjusting computation does not support the
switching pattern directly: Because of its change propagation
semantics, it would "forget" the division in step 2, and rerun it
_from-scratch_ in step 3.

Furthermore, some other change propagation algorithms base their
re-execution schedule on "node height" (of the graph's topological
ordering).  These algorithms may also have undesirable behavior.  In
particular, they may re-execute the division `div` in step 2, though
it is not presently in demand. For an example, see [this
gist](https://gist.github.com/khooyp/98abc0e64dc296deaa48).

Memoization
============

Memoization provides a mechanism for caching the results of
subcomputations; it is a crtical feature of Adapton's approach to
incremental computation.

In Adapton, each _memoization point_ has three ingredients:

- A function expression (of type `Fn`)

- Zero or more arguments.  Each argument type must have an
  implementation for the traits `Eq + Clone + Hash + Debug`.  The
  traits `Eq` and `Clone` are both critical to Adapton's caching and
  change propagation engine.  The trait `Hash` is required when
  Adapton's naming strategy is _structural_ (e.g., where function
  names are based on the hashes of their arguments).  The trait
  `Debug` is useful for debugging, and reflection.

- An optional _name_, which identifies the function call for reuse later.

    - When this optional name is `None`, the memoization point may be
      treated in one of two ways: either as just an ordinary, uncached
      function call, or as a cached function call that is identified
      _structurally_, by its function pointer and arguments.  Adapton
      permits structural subcomputations via the engine's
      [structural](https://docs.rs/adapton/0/adapton/engine/fn.structural.html)
      function.

    - When this is `Some(name)`, the memoization point uses `name` to
      identify the work performed by the function call, and its
      result.  Critically, in future incremental runs, it is possible
      for `name` to associate with different functions and/or argument
      values.

Each memoization point yields two results:

- A [thunk](#create-thunks) articulation, of type `Art<Res>`, where
  `Res` is the result type of the function expression.

- A result value of type `Res`, which is also cached at the articulation.


Optional name version
----------------------

The following form is preferred:

`memo!( [ optional_name ]? fnexp ; lab1 : arg1, ..., labk : argk )`

It accepts an optional name, of type `Option<Name>`, and an arbitrary
function expression `fnexp` (closure or function pointer).  Like the
other forms, it requires that the programmer label each argument.

Example
-------

```
# #[macro_use] extern crate adapton;
# fn main() {
# use adapton::macros::*;
# use adapton::engine::*;
# manage::init_dcg();
let (t,z) : (Art<usize>, usize) =
  memo!([Some(name_unit())]?
    |x:usize,y:usize|{ if x > y { x } else { y }};
     x:10,   y:20   );

assert_eq!(z, 20);
# }
```

[More examples of `memo!` macro](https://docs.rs/adapton/0/adapton/macro.memo.html#memoization)

Create thunks
===============

**Thunks** consist of suspended computations whose observations,
allocations and results are cached in the DCG, when `force`d.  Each
thunk has type `Art<Res>`, where `Res` is the return type of the thunk's
suspended computation.

Each [_memoization point_](#memoization) is merely a _forced thunk_.
We can also create thunks without demanding them.

The following form is preferred:

`thunk!( [ optional_name ]? fnexp ; lab1 : arg1, ..., labk : argk )`

It accepts an optional name, of type `Option<Name>`, and an arbitrary
function expression `fnexp` (closure or function pointer).  Like the
other forms, it requires that the programmer label each argument.

Example
-------

```
# #[macro_use] extern crate adapton;
# fn main() {
# use adapton::macros::*;
# use adapton::engine::*;
# manage::init_dcg();
let t : Art<usize> =
  thunk!([ Some(name_unit()) ]?
    |x:usize,y:usize|{ if x > y { x } else { y }};
     x:10,   y:20   );

assert_eq!(get!(t), 20);
# }
```

[More examples of `thunk!` macro](https://docs.rs/adapton/0/adapton/macro.thunk.html#thunks)

Use `force_map` for more precise dependencies
==============================================

Suppose that we want to project only one field of type `A` from a pair
within an `Art<(A,B)>`.  If the field of type `B` changes, our
observation of the `A` field will not be affected.

Below, we show that using `force_map` prunes the dirtying phase of
change propagation.  Doing so means that computations that would
otherwise be dirty and cleaned via re-execution are never diritied in
the first place.  We show a simple example of projecting a pair.

To observe this fact, this test traces the engine, counts the number
of dirtying steps, and ensures that this count is zero, as expected.

```
# #[macro_use] extern crate adapton;
# fn main() {
# use adapton::macros::*;
# use adapton::engine::*;
# use adapton::reflect;
# manage::init_dcg();
#
// Trace the behavior of change propagation; ensure dirtying works as expected
reflect::dcg_reflect_begin();

let pair  = cell!((1234, 5678));
let pair1 = pair.clone();

let t = thunk![{
  // Project the first component of pair:
  let fst = force_map(&pair, |_,x| x.0);
  fst + 100
}];

// The output is `1234 + 100` = `1334`
assert_eq!(get!(t), 1334);

// Update the second component of the pair; the first is still 1234
set(&pair1, (1234, 8765));

// The output is still `1234 + 100` = `1334`
assert_eq!(get!(t), 1334);

// Assert that nothing was dirtied (due to using `force_map`)
let traces = reflect::dcg_reflect_end();
let counts = reflect::trace::trace_count(&traces, None);
assert_eq!(counts.dirty.0, 0);
assert_eq!(counts.dirty.1, 0);
# }
```


Nominal memoization
=========================

Adapton offers **nominal memoization**, which uses first-class _names_
(each of type `Name`) to identify cached computations and data.

```
# #[macro_use] extern crate adapton;
# fn main() {
# use adapton::macros::*;
# use adapton::engine::*;
# use adapton::reflect;
#
# // create an empty DCG (demanded computation graph)
# manage::init_dcg();
#
fn sum(x:usize, y:usize) -> usize {
    x + y
}

// create a memo entry, named `a`, that remembers that `sum(42,43) = 85`
let res1 : usize = get!(thunk!([a] sum; x:42, y:43));
# }
```
Behind the scenes, the name `a` controls how and when the Adapton engine
_overwrites_ the cached computation of `sum`.  As such, names permit
patterns of programmatic _cache eviction_.

The macro `memo!` relies on programmer-supplied variable names in its
macro expansion of these call sites, shown as `x` and `y` in the uses
above.  These can be chosen arbitrarily: So long as these symbols are
distinct from one another, they can be _any_ symbols, and need not
actually match the formal argument names.

**Example as Editor role**
For a simple illustration, we memoize several function calls to `sum`
with different names and arguments.  In real applications, the
memoized function typically performs more work than summing two
machine words. :)

```
# #[macro_use] extern crate adapton;
# fn main() {
# use adapton::macros::*;
# use adapton::engine::*;
# use adapton::reflect;
# manage::init_dcg();
# fn sum(x:usize, y:usize) -> usize {
#     x + y
# }
#
// Optional: Traces what the engine does below (for diagnostics, testing, illustration)
reflect::dcg_reflect_begin();

// create a memo entry, named `a`, that remembers that `sum(42,43) = 85`
let res1 : usize = get!(thunk!([a] sum; x:42, y:43));

// same name `a`, same arguments (42, 43), Adapton reuses cached result
let res2 : usize = get!(thunk!([a] sum; x:42, y:43));

// different name `b`, same arguments (42, 43), Adapton re-computes `sum` for `b`
let res3 : usize = get!(thunk!([b] sum; x:42, y:43));

// same name `b`, different arguments, editor overwrites thunk `b` with new args
let res4 : usize = get!(thunk!([b] sum; x:55, y:66));
# }
```

Below we confirm the following facts:

- The Editor:
  - allocated two thunks (`a` and `b`),
  - allocated one thunk without changing it (`a`, with the same arguments)
  - allocated one thunk by changing it (`b`, with different arguments)
- The Archivist allocated nothing.

```
# #[macro_use] extern crate adapton;
# fn main() {
# use adapton::macros::*;
# use adapton::engine::*;
# use adapton::reflect;
#
# // create an empty DCG (demanded computation graph)
# manage::init_dcg();
#
# // a simple function (memoized below for illustration purposes;
# //                    probably actually not worth it!)
# fn sum(x:usize, y:usize) -> usize {
#     x + y
# }
#
# // Optional: Traces what the engine does below (for diagnostics, testing, illustration)
# reflect::dcg_reflect_begin();
#
# // create a memo entry, named `a`, that remembers that `sum(42,43) = 85`
# let res1 : usize = get!(thunk!([a] sum; x:42, y:43));
#
# // same name `a`, same arguments (42, 43) => reuse cached result
# let res2 : usize = get!(thunk!([a] sum; x:42, y:43));
#
# // different name `b`, same arguments (42, 43) => recomputes `sum` for `b`
# let res3 : usize = get!(thunk!([b] sum; x:42, y:43));
#
# // same name `b`, different arguments; *overwrite* `b` with new args & result
# let res4 : usize = get!(thunk!([b] sum; x:55, y:66));
#
// Optional: Assert what happened above, in terms of analytical counts
let traces = reflect::dcg_reflect_end();
let counts = reflect::trace::trace_count(&traces, None);

// Editor allocated two thunks (`a` and `b`)
assert_eq!(counts.alloc_fresh.0, 2);

// Editor allocated one thunk without changing it (`a`, with same args)
assert_eq!(counts.alloc_nochange.0, 1);

// Editor allocated one thunk by changing it (`b`, different args)
assert_eq!(counts.alloc_change.0, 1);

// Archivist allocated nothing
assert_eq!(counts.alloc_fresh.1, 0);
# drop((res1,res2,res3,res4));
# }
```

Nominal Cycles
===================

In many settings, we explore structures that contain cycles, and it is
useful to use Adapton's DCG mechanism to detect such cycles.


Example problem: Recursive computation over a directed graph
---------------------------------------------------------------

As a tiny example, consider the following graph, defined as a table of
adjacencies:

```
// Node | Adjacency pair
//      | (two outgoing edges to other nodes):
// -----+-------------------------------------
// 0    | (1, 0)
// 1    | (2, 3)
// 2    | (3, 0)
// 3    | (3, 1)
// 4    | (2, 5)
// 5    | (5, 4)
```

This is a small arbitrary directed graph, and it has several cycles
(e.g., `0 --> 0`, `3 --> 3`, `0 --> 1 --> 2 --> 0`).  It also has
distinct strongly-connected components (SCCs), e.g., the one involving
`0` versus the one involving `4`.

**Problem statement:** Suppose that we wish to explore this graph, to
build a list (or `Vec`) of all of the nodes that it contains.

**Desired solution program:**
Consider the simple (naive) recursive exploration logic, defined
as `explore_rec` below.  The problems with this logic are that

1. **Repeated work**: `explore_rec` re-explores some sub-graphs multiple times, and
2. **Divergence**: `explore_rec` diverges on graphs with cycles.

To address the first problem, we can leverage the DCG, which performs
function caching.  To address the second problem, the algorithm needs
a mechanism to detect cycles.

In terms of DCG evaluation, we can detect a cycle if we can remember
and check whether we are "currently" visiting the node (on the
recursive call stack) before we evaluate a node recursively.

Regardless of how we detect the cycle, we wish to do something
different (other than recur).

### DCG cycles: Detection and valuation

Rather than implement this cycle-detection mechanism directly, we can
use Adapton's DCG, which operates behind the scenes. Specifically, we
can use the engine operation [`force_cycle`](https://docs.rs/adapton/0/adapton/engine/fn.force_cycle.html)
to specify a "cycle value" for the result of a thunk `t` when `t` is forcing itself, or when `t`
is forcing another thunk `s` that transitively forces `t`.

In either case, the force operation that forms the cycle in the DCG
evaluates to this programmer-specified cycle value, rather than
diverging, or using the cached value at the thunk, which generally is
not sound (e.g., it may be stale, from a prior run).

### Example cycle valuation

Notice that in `explore` below, we use `get!(_, vec![])` on `at` and
`bt` instead of `get!(_)`.  This macro uses `force_cycle` in its
expansion.  The empty vector gives the cycle value for when this force
forms a cycle in the DCG.

```
# #[macro_use] extern crate adapton;
# fn main() {
# use adapton::macros::*;
# use adapton::engine::*;
// Define the graph, following the table above
fn adjs (n:usize) -> (usize, usize) {
    match n {
        0 => (1, 0),
        1 => (2, 3),
        2 => (3, 0),
        3 => (3, 1),
        4 => (2, 5),
        5 => (5, 4),
        _ => unimplemented!()
    }
}

// This version will diverge on all of the cycles (e.g., 3 --> 3)
#[warn(unconditional_recursion)]
fn explore_rec(cur_n:usize) -> Vec<usize> {
    let (a,b) = adjs(cur_n);
    let mut av = explore_rec(a);
    let mut bv = explore_rec(b);
    let mut res = vec![cur_n];
    res.append(&mut av);
    res.append(&mut bv);
    res
}

// This version will not diverge; it gives an empty vector value
// as "cycle output" when it performs each `get!`.  Hence, when
// Adapton detects a cycle, it will not re-force this thunk
// cyclicly, but rather return this predetermined "cycle output"
// value. For non-cyclic calls, the `get!` ignores this value, and
// works in the usual way.
fn explore(cur_n:usize) -> Vec<usize> {
    let (a,b) = adjs(cur_n);
    let at = explore_thunk(a);
    let bt = explore_thunk(b);
    let mut av = get!(at, vec![]);
    let mut bv = get!(bt, vec![]);
    let mut res = vec![cur_n];
    res.append(&mut av);
    res.append(&mut bv);
    res
}
fn explore_thunk(cur_n:usize) -> Art<Vec<usize>> {
    thunk!([Some(name_of_usize(cur_n))]? explore ; n:cur_n)
}

adapton::engine::manage::init_dcg();
assert_eq!(get!(explore_thunk(0)), vec![0,1,2,3,3])
# }
```

Nominal Firewalls
===================

Nominal firewalls use nominal allocation to dirty the DCG
incrementally, _while change propagation cleans it_.

In some situations (Run 2, below), these firewalls prevent dirtying
from cascading, leading to finer-grained dependency tracking, and more
incremental reuse.  Thanks to
[@nikomatsakis](https://github.com/nikomatsakis) for suggesting the
term "firewall" in this context.

First, consider this graph, as Rust code (graph picture below):

Example: nominal firewall
-------------------------

```
# #[macro_use] extern crate adapton;
# fn main() {
# use adapton::macros::*;
# use adapton::engine::*;
fn demand_graph(a: Art<i32>) -> String {
    let_memo!{
      d =(f)= {
        let a = a.clone();
        let_memo!{ b =(g)={ let x = get!(a); cell!([b] x * x) };
                   c =(h)={ format!("{:?}", get!(b)) };
                   c }};
      d }
}
# drop(demand_graph) }
```

The use of `let_memo!` is [convenient sugar](#let_memo-example) for `thunk!` and `force`.
This code induces DCGs with the following structure:

```
/*                                             +---- Legend ------------------+
cell a                                         | [ 2 ]   ref cell holding 2   |
[ 2 ]            "Nominal                      |  (g)    thunk named 'g'      |
  ^               firewall"                    | ---->   force/observe edge   |
  | force            |                         | --->>   allocation edge      |
  | 2               \|/                        +------------------------------+
  |                  `
  |   g allocs b    cell    g forces b          When cell a changes, g is dirty, h is not;
  |   to hold 4      b      observes 4          in this sense, cell b _firewalls_ h from g:
 (g)------------->>[ 4 ]<--------------(h)  <~~ note that h does not observe cell a, or g.
  ^                                     ^
  | f forces g                          | f forces h,
  | g returns cell b                    | returns String "4"
  |                                     |
 (f)------------------------------------+
  ^
  | force f,
  | returns String "4"
  |
(demand_graph(a))                                                                        */
```

In this graph, the ref cell `b` acts as the "firewall".

Below, we show a particular input change for cell `a` where a
subcomputation `h` is never dirtied nor cleaned by change propagation
(input change 2 to -2). We show another change to the same input where
this subcomputation `h` *is* _eventually_ dirtied and cleaned by
Adapton, though not immediately (input change -2 to 3).

Here's the Rust code for generating this DCG, and these changes to its
input cell, named `"a"`:

```
# #[macro_use] extern crate adapton;
# fn main() {
# use adapton::macros::*;
# use adapton::engine::*;
#
# fn demand_graph(a: Art<i32>) -> String {
#    let_memo!{
#      d =(f)= {
#        let a = a.clone();
#        let_memo!{ b =(g)={ let x = get!(a); cell!([b] x * x) };
#                   c =(h)={ format!("{:?}", get!(b)) };
#                   c }};
#      d }
# }
#
# manage::init_dcg();
#
// 1. Initialize input cell "a" to hold 2, and do the computation illustrated above:
assert_eq!(demand_graph(let_cell!{a = 2; a}), "4".to_string());

// 2. Change input cell "a" to hold -2, and do the computation illustrated above:
assert_eq!(demand_graph(let_cell!{a = -2; a}), "4".to_string());

// 3. Change input cell "a" to hold 3, and do the computation illustrated above:
assert_eq!(demand_graph(let_cell!{a = 3; a}),  "9".to_string());
# }
```

**Run 1.** In the first computation, the input cell `a` holds 2, and
the final result is `"4"`.

**Run 2.** When the input cell `a` changes, e.g., from 2 to -2, thunks
`f` and `g` are dirtied.  Thunk `g` is dirty because it observes the
changed input.  Thunk `f` is dirty because it demanded (observed) the
output of thunk `g` in the extent of its own computation.

_Importantly, thunk `h` is *not* immediately dirtied when cell `a`
changes._ In a sense, cell `a` is an indirect ("transitive") input to
thunk `h`.  This fact may suggest that when cell `a` is changed from 2
to -2, we should dirty thunk `h` immediately.  However, thunk `h` is
related to this input only by reading ref cell `b`.

Rather, when the editor re-demands thunk `f`, Adapton will necessarily
perform a cleaning process (aka, "change propagation"), re-executing
`g`, its immediate dependent, which is dirty.  Since thunk `g` merely
squares its input, and 2 and -2 both square to 4, the output of thunk
`g` will not change in this case.  Consequently, the observers of cell
`b`, which holds this output, will not be dirtied or re-executed.  In
this case, thunk `h` is this observer.  In situations like these,
Adapton's dirtying + cleaning algorithms do not dirty nor clean thunk
`h`.

In sum, under this change, after `f` is re-demanded, the cleaning
process will first re-execute `g`, the immediate observer of cell `a`.
Thunk `g` will again allocate cell `b` to hold 4, the same value as
before.  It also yields this same cell pointer (to cell `b`).
Consequently, thunk `f` is not re-executed, and is cleaned.
Meanwhile, the outgoing (dependency) edges thunk of `h` are never
dirtied.  Effectively, the work of `h` is reused from cache as well.

Alternatively, if we had placed the code for `format!("{:?}",get!(b))`
in thunk `f`, Adapton _would_ have re-executed this step when `a`
changes from `2` to `-2`: It would be dirtied when `a` changes, since
it directly observes `g`, which directly observes cell `a`.

**Run 3.** For some other change, e.g., from 2 to 3, thunk `h` would
_eventually_ _will be_

 - dirtied, when `f` redemands `g`, which will overwrite cell `b` with `9`,
 - and cleaned, when `f` re-demands `h`, which will `format!` a new `String` of `"9"`.


`let_memo!` example
----------------------------

The [use of `let_memo!` macro above](#example-nominal-firewall) expands as follows:

```
# #[macro_use] extern crate adapton;
# fn main() {
# use adapton::macros::*;
# use adapton::engine::*;
fn demand_graph__mid_macro_expansion(a: Art<i32>) -> String {
    let f = thunk!([f]{
              let a = a.clone();
              let g = thunk!([g]{ let x = get!(a);
                                  cell!([b] x * x) });
              let b = force(&g);
              let h = thunk!([h]{ let x = get!(b);
                                  format!("{:?}", x) });
              let c = force(&h);
              c });
    let d = force(&f);
    d
};
# }
```

Incremental sequences
========================

A _level tree_ consists of a binary tree with levels that decrease
monotonically along each path to its leaves.

Here, we implement incremental level trees by including `Name`s and
`Art`s in the tree structure, with two additional constructors for the
recursive type, `Rec<X>`:

```
# #[macro_use] extern crate adapton;
# fn main() {
# use adapton::macros::*;
# use adapton::engine::*;
use std::fmt::Debug;
use std::hash::Hash;

#[derive(Clone,PartialEq,Eq,Debug,Hash)]
enum Rec<X> {
    Bin(BinCons<X>),
    Leaf(LeafCons<X>),
    Name(NameCons<X>),
    Art(Art<Rec<X>>),
}

#[derive(Clone,PartialEq,Eq,Debug,Hash)]
struct LeafCons<X> {
    elms:Vec<X>,
}

#[derive(Clone,PartialEq,Eq,Debug,Hash)]
struct BinCons<X> {
    level: u32,
    recl:Box<Rec<X>>,
    recr:Box<Rec<X>>
}

#[derive(Clone,PartialEq,Eq,Debug,Hash)]
struct NameCons<X> {
    level:u32,
    name:Name,
    rec:Box<Rec<X>>,
}
# }
```

Example: Nominal memoization and recursion
--------------------------------------------

**Introduction forms:**

```
# #[macro_use] extern crate adapton;
# fn main() {
#
# use std::fmt::Debug;
# use std::hash::{Hash};
# use adapton::macros::*;
# use adapton::engine::*;
#
# #[derive(Clone,PartialEq,Eq,Debug,Hash)]
# struct BinCons<X> {
#    level: u32,
#    recl:Box<Rec<X>>,
#    recr:Box<Rec<X>>
# }
# #[derive(Clone,PartialEq,Eq,Debug,Hash)]
# struct NameCons<X> {
#    level:u32,
#    name:Name,
#    rec:Box<Rec<X>>,
# }
# #[derive(Clone,PartialEq,Eq,Debug,Hash)]
# struct LeafCons<X> {
#     elms:Vec<X>,
# }
# #[derive(Clone,PartialEq,Eq,Debug,Hash)]
# enum Rec<X> {
#    Leaf(LeafCons<X>),
#    Bin(BinCons<X>),
#    Name(NameCons<X>),
#    Art(Art<Rec<X>>),
# }
impl<X:'static+Clone+PartialEq+Eq+Debug+Hash>
    Rec<X> {

pub fn leaf(xs:Vec<X>) -> Self {
    Rec::Leaf(LeafCons{elms:xs})
}
pub fn bin(lev:u32, l:Self, r:Self) -> Self {
    Rec::Bin(BinCons{level:lev,recl:Box::new(l),recr:Box::new(r)})
}
pub fn name(lev:u32, n:Name, r:Self) -> Self {
    Rec::Name(NameCons{level:lev,name:n, rec:Box::new(r)})
}
fn art(a:Art<Rec<X>>) -> Self {
    Rec::Art(a)
}
# }
# }
```

**Elimination forms:** Folds use `memo!` to create and `force` `thunks`:

```
# #[macro_use] extern crate adapton;
# fn main() {
#
# use std::fmt::Debug;
# use std::hash::{Hash};
# use adapton::macros::*;
# use adapton::engine::*;
#
# #[derive(Clone,PartialEq,Eq,Debug,Hash)]
# struct BinCons<X> {
#    level: u32,
#    recl:Box<Rec<X>>,
#    recr:Box<Rec<X>>
# }
# #[derive(Clone,PartialEq,Eq,Debug,Hash)]
# struct NameCons<X> {
#    level:u32,
#    name:Name,
#    rec:Box<Rec<X>>,
# }
# #[derive(Clone,PartialEq,Eq,Debug,Hash)]
# struct LeafCons<X> {
#     elms:Vec<X>,
# }
# #[derive(Clone,PartialEq,Eq,Debug,Hash)]
# enum Rec<X> {
#    Leaf(LeafCons<X>),
#    Bin(BinCons<X>),
#    Name(NameCons<X>),
#    Art(Art<Rec<X>>),
# }
# impl<X:'static+Clone+PartialEq+Eq+Debug+Hash>
#    Rec<X>
# {
#    pub fn leaf(xs:Vec<X>) -> Self {
#        Rec::Leaf(LeafCons{elms:xs})
#    }
#    pub fn bin(lev:u32, l:Self, r:Self) -> Self {
#        Rec::Bin(BinCons{level:lev,recl:Box::new(l),recr:Box::new(r)})
#    }
#    pub fn name(lev:u32, n:Name, r:Self) -> Self {
#        Rec::Name(NameCons{level:lev,name:n, rec:Box::new(r)})
#    }
#    fn art(a:Art<Rec<X>>) -> Self {
#        Rec::Art(a)
#    }
#
pub fn fold_monoid<B:'static+Clone+PartialEq+Eq+Debug+Hash>
   (t:Rec<X>, z:X, b:B,
    bin:fn(B,X,X)->X,
    art:fn(Art<X>,X)->X)
   -> X
{
  fn m_leaf<B:Clone,X>(m:(B,fn(B,X,X)->X,X), elms:Vec<X>) -> X {
#    let mut x = m.2;
#    for elm in elms {
#      x = m.1(m.0.clone(), x, elm)
#    };
#    x
     // ...
  }
  fn m_bin<B,X>(_n:Option<Name>, m:(B,fn(B,X,X)->X,X), _lev:u32, l:X, r:X) -> X {
      m.1(m.0, l, r)
  }
  Self::fold_up_namebin::<(B,fn(B,X,X)->X,X),
                          (B,fn(B,X,X)->X,X),X> (t, (b.clone(),bin,z.clone()), m_leaf,
                                                 None, (b,bin,z), m_bin, art)
}

fn fold_up_namebin
   <L:'static+Clone+PartialEq+Eq+Debug+Hash,
    B:'static+Clone+PartialEq+Eq+Debug+Hash,
    R:'static+Clone+PartialEq+Eq+Debug+Hash>
   (t:Rec<X>,
    l:L, leaf:fn(L,Vec<X>)->R,
    n:Option<Name>, b:B,
    namebin:fn(Option<Name>,B,u32,R,R)->R,
    art:fn(Art<R>,R)->R)
   -> R
{
  match t {
    Rec::Art(a) => Self::fold_up_namebin(get!(a), l, leaf, n, b, namebin, art),
    Rec::Leaf(leafcons) => leaf(l, leafcons.elms),
    Rec::Bin(bincons)   => {
        let (n1,n2) = forko!(n.clone());
        let r1 = memo!([n1]? Self::fold_up_namebin;
                       t:*bincons.recl,
                       l:l.clone(), leaf:leaf, n:None, b:b.clone(), namebin:namebin, art:art);
        let r1 = art(r1.0,r1.1);
        let r2 = memo!([n2]? Self::fold_up_namebin;
                       t:*bincons.recr,
                       l:l.clone(), leaf:leaf, n:None, b:b.clone(), namebin:namebin, art:art);
        let r2 = art(r2.0,r2.1);
        namebin(n, b, bincons.level, r1, r2)
    }
    Rec::Name(namecons) => {
        Self::fold_up_namebin(
            *namecons.rec,
            l, leaf, Some(namecons.name), b, namebin, art
        )
    }
  }
}
# }}
```


Background: Incremental Computing with Names
=============================================

We explain the role of names in incremental computing.

## Pointer locations in incremental computing

Suppose that we have a program that we wish to run repeatedly on
similar (but changing) inputs, and that this program constructs a
dynamic data structure as output.  To cache this computation,
including its output, we generally require caching some of its
function calls, their results, and whatever allocations are relevant
to represent these results, including the final output structure.
Furthermore, to quickly test for input and output changes (in `O(1)`
time per "change") we would like to _store allocate_ input and output,
and use allocated _pointer locations_ (globally-unique "names") to
compare structures, giving a cheap, conservative approximation of
structural equality.

## Deterministic allocation

The first role of explicit names for incremental computing concerns
_deterministic pointer allocation_, which permits us to give a
meaningful definition to _cached_ allocation.  To understand this
role, consider these two evaluation rules:

```
// l ∉ dom(σ)                                    n ∉ dom(σ)
// ---------------------------- :: alloc_1       ------------------------------- :: alloc_2
// σ; cell(v) ⇓ σ{l↦v}; ref l                    σ; cell[n](v) ⇓ σ{n↦v}; ref n
```

Each rule is of the judgement form `σ1; e ⇓ σ2; v`, where `σ1` and
`σ2` are stores that map pointers to thunks and values, and `e` is an
expression to evaluate, and `v` is its valuation.

The left rule is conventional: it allocates a value `v` at a store
location `l`; because the program does not determine `l`, the
implementor of this rule has the freedom to choose `l` any way that
they wish.  Consequently, this program is not deterministic, and not a
function.  Hence, it is not immediately obvious what it means to
_cache_ this kind of dynamic allocation using a technique like
_function caching_, or techniques based on it.

To address this question, the programmer can determine a name `n`
for the value `v` as in the right rule.  The point of this version is
to expose the naming choice directly to the programmer.

### Structural names

In some systems, the programmer chooses this name as the hash value of
value `v`.  This naming style is often called "hash-consing".  We
refer to it as _structural naming_, since by using it, the name of
each ref cell reflects the _entire structure_ of that cell's
content. (Structural hashing approach is closely related to Merkle
trees, the basis for revision-control systems like `git`.)

### Independent names

By contrast, in a _nominal_ incremental system, the programmer
generally chooses `n` to be related to the _evaluation context of
using `v`_, and often, to be _independent_ of the value `v` itself.
We give one example of such a naming strategy below.

## Nominal independence

Names augment programs to permit memoization and change propagation to
exploit independence among dynamic dependencies.  Specifically, the
name value `n` is (generally) unrelated to the content value `v`.
In many incremental applications, its role is analogous to that of
location `l` in the left rule, where `l` is only related to `v` by the
final store.  When pointer name `n` is independent of pointer
content `v`, we say this name, via the store, affords the program
_nominal independence_.

Suppose that in a subsequent incremental run, value `v` changes to
`v2` at name `n`.  The pointer name `n` localizes this change,
preventing any larger structure that contains cell `n` from itself
having a changed identity.  By contrast, consider the case of
structural naming, which lacks nominal indirection: by virtue of being
determined by the value `v`, the allocated name `n` must change to
`n2` when `v` changes to `v2`.  Structural naming is deterministic,
but lacks nominal independence, by definition.

## Simple example of nominal independence

The independence afforded by nominal indirection is critical in many
incremental programs.
As a simple illustrative example, consider `rev`, which
recursively reverses a list that, after being reversed, undergoes
incremental insertions and removals.

```
// rev : List -> List -> List
// rev l r = match l with
//  | Nil       => r
//  | Cons(h,t) =>
//     memo(rev !t (Cons(h,r)))
```

The function `rev` reverses a list of `Cons` cells, using an
accumulator value `r`.
To incrementalize the code for `rev`, in the `Cons` case, we
memoize the recursive call to `rev`, which involves matching its
arguments with those of cached calls.

Problematically, if we do not introduce any indirection for it, the
accumulator `Cons(h,r)` will contain any incremental changes to head
value `h`, as well as any changes in the prefix of the input list (now
reversed in the previous accumulator value `r`).  This is a problem
for memoization because, without indirection in this accumulator list,
such changes will repeatedly prevent us from `memo`-matching the
recursive call.  Consequently, change propagation will re-evaluate all
the calls that follow the position of an insertion or removal: This
change is recorded in the accumulator, which has changed structurally.

To address this issue, which is an example of a general pattern
(c.f. the output accumulators of quicksort and quickhull), past
researchers suggest that we introduce nominal `cell`s into the
accumulator, each allocated with a name associated with their
corresponding input `Cons` cell.  In place of "names", prior work
variously used the terms _(allocation)
keys_~\cite{AcarThesis,Hammer08,AcarLeyWild09} and
_indices_~\cite{Acar06,Acar06ML}, but the core idea is the same.

```
// | Cons(n,h,t) =>
//    let rr = ref[n](r) in
//    memo(rev !t (Cons(h,rr)))
```

In this updated version, each name `n` localizes any change to the
accumulator argument `r` via nominal indirection.
When and if a later part of the program consumes the output in ref
cell `rr`, the system will process any changes associated with
this accumulator; they may be relevant later, but they are not
_directly_ relevant for reversing the tail `!t` in
cell `t`: The body of `rev` never inspects `r`, it
merely uses it to construct its output, for the `Nil` base case.

In summary, this example illustrate a general principle: Nominal
indirection augments programs to permit memoization and change
propagation to exploit dynamic independence.  Specifically, we exploit
the independence of the steps that reverse the pointers of a linked
list.

*/

//#![feature(associated_consts)]
#![feature(box_patterns)]
#![feature(box_syntax)]

#![crate_name = "adapton"]
#![crate_type = "lib"]

extern crate core;

#[macro_use]
pub mod macros ;
pub mod engine ;
pub mod catalog ;
pub mod parse_val;
pub mod reflect;


mod adapton {
    pub use super::*;
}