43:
535:*, a version of the interpreter that only runs that source code, is written in the implementation language of the interpreter, does not require the source code to be resupplied, and runs faster than the original combination of the interpreter and the source. In this case
259:
343:
398:
288:
891:
499:
434:
463:
1038:
152:
200:
181:. The most straightforward application is to produce new programs that run faster than the originals while being guaranteed to behave in the same way.
436:
is called the "residual program" and should run more efficiently than the original program. The act of partial evaluation is said to "residualize"
1072:
531:
is source code designed to run inside that interpreter, then partial evaluation of the interpreter with respect to this data/program produces
884:
559:
Specializing the specializer for itself (as applied in #2), yielding a tool that can convert any interpreter to an equivalent compiler.
1244:
811:
682:
587:
145:
86:
64:
1121:
1022:
509:
A particularly interesting example of the use of partial evaluation, first described in the 1970s by
Yoshihiko Futamura, is when
1270:
1163:
877:
572:
174:
773:
300:
1058:
1275:
1142:
138:
1193:
1158:
348:
1082:
957:
937:
606:
126:
57:
51:
942:
514:
1090:
1067:
1043:
972:
829:
751:
712:
178:
68:
1219:
1214:
1168:
1095:
919:
914:
266:
1249:
1173:
1017:
748:
POPL '93: Proceedings of the 20th ACM SIGPLAN-SIGACT Symposium on
Principles of Programming Languages
703:
Futamura, Y. (1999). "Partial
Evaluation of Computation Process—An Approach to a Compiler-Compiler".
518:
834:
756:
1229:
1100:
992:
900:
717:
582:
102:
31:
1224:
1007:
997:
947:
850:
779:
730:
601:
1105:
929:
807:
769:
678:
468:
403:
192:
121:
1239:
1178:
1048:
1027:
987:
967:
761:
722:
670:
662:
185:
1234:
439:
111:
556:
Specializing the specializer for the interpreter (as applied in #1), yielding a compiler.
1209:
1183:
982:
977:
962:
1264:
743:
863:
734:
638:"Partial Evaluation of Computation Process --- An approach to a Compiler-Compiler",
549:
This technique is known as the first
Futamura projection, of which there are three:
783:
640:
Transactions of the
Institute of Electronics and Communications Engineers of Japan
17:
952:
864:
Applying
Dynamic Partial Evaluation to dynamic, reflective programming languages
822:
592:
577:
1032:
726:
666:
661:. Lecture Notes in Computer Science. Vol. 147. Springer. pp. 1–35.
1126:
563:
They were described by
Futamura in Japanese in 1971 and in English in 1983.
166:
801:
765:
553:
Specializing an interpreter for given source code, yielding an executable.
869:
674:
823:"Partial Evaluation and Semantics-Based Program Manipulation PEPM'99"
254:{\displaystyle prog:I_{\text{static}}\times I_{\text{dynamic}}\to O,}
855:
843:
Veldhuizen, Todd L. (1999). "C++ Templates as
Partial Evaluation".
873:
36:
800:
Jones, Neil D.; Gomard, Carsten K.; Sestoft, Peter (1993).
750:. Association for Computing Machinery. pp. 493–501.
657:
Futamura, Y. (1983). "Partial computation of programs".
625:
294:, is the part of the input data known at compile time.
338:{\displaystyle \langle prog,I_{\text{static}}\rangle }
471:
442:
406:
351:
303:
269:
203:
1202:
1151:
1135:
1114:
1081:
1057:
1006:
928:
907:
803:
Partial
Evaluation and Automatic Program Generation
493:
457:
428:
400:by precomputing all static input at compile time.
392:
337:
282:
253:
659:RIMS Symposia on Software Science and Engineering
746:(1993). "Tutorial Notes on Partial Evaluation".
393:{\displaystyle prog^{*}:I_{\text{dynamic}}\to O}
1039:Induction variable recognition and elimination
173:is a technique for several different types of
885:
146:
8:
332:
304:
892:
878:
870:
153:
139:
98:
854:
833:
755:
716:
485:
470:
441:
420:
405:
378:
365:
350:
326:
302:
274:
268:
236:
223:
202:
87:Learn how and when to remove this message
50:This article includes a list of general
1073:Sparse conditional constant propagation
845:
618:
539:* is effectively a compiled version of
101:
705:Higher-Order and Symbolic Computation
7:
56:it lacks sufficient corresponding
27:Technique for program optimization
25:
588:Run-time algorithm specialisation
297:The partial evaluator transforms
283:{\displaystyle I_{\text{static}}}
1023:Common subexpression elimination
195:of input data into output data:
41:
1164:Compile-time function execution
573:Compile-time function execution
384:
242:
1:
1143:Interprocedural optimization
626:Yoshihiko Futamura's website
1194:Profile-guided optimization
1159:Bounds-checking elimination
1292:
958:Loop-invariant code motion
29:
938:Automatic parallelization
667:10.1007/3-540-11980-9_13
607:Template metaprogramming
494:{\displaystyle prog^{*}}
429:{\displaystyle prog^{*}}
127:Short-circuit evaluation
30:Not to be confused with
943:Automatic vectorization
821:Danvy, O., ed. (1999).
727:10.1023/A:1010095604496
71:more precise citations.
1271:Compiler optimizations
1091:Instruction scheduling
1068:Global value numbering
1044:Live-variable analysis
973:Loop nest optimization
901:Compiler optimizations
495:
459:
430:
394:
339:
284:
255:
1220:Control-flow analysis
1215:Array-access analysis
1169:Dead-code elimination
1127:Tail-call elimination
1096:Instruction selection
920:Local value numbering
915:Peephole optimization
766:10.1145/158511.158707
496:
460:
431:
395:
340:
285:
256:
103:Evaluation strategies
1250:Value range analysis
1174:Expression templates
1018:Available expression
519:programming language
505:Futamura projections
469:
458:{\displaystyle prog}
440:
404:
349:
301:
267:
201:
175:program optimization
1276:Evaluation strategy
1230:Dependence analysis
1101:Register allocation
993:Software pipelining
583:Partial application
32:partial application
1225:Data-flow analysis
1189:Partial evaluation
998:Strength reduction
948:Induction variable
696:General references
602:Strength reduction
491:
455:
426:
390:
335:
280:
251:
171:partial evaluation
117:Partial evaluation
18:Yoshihiko Futamura
1258:
1257:
1106:Rematerialization
806:. Prentice Hall.
742:Consel, Charles;
381:
329:
277:
239:
226:
163:
162:
122:Remote evaluation
97:
96:
89:
16:(Redirected from
1283:
1240:Pointer analysis
1179:Inline expansion
1049:Use-define chain
1028:Constant folding
988:Loop unswitching
968:Loop interchange
894:
887:
880:
871:
860:
858:
849:. pp. 15–.
839:
837:
827:
817:
787:
759:
738:
720:
689:
688:
654:
648:
647:
635:
629:
623:
500:
498:
497:
492:
490:
489:
464:
462:
461:
456:
435:
433:
432:
427:
425:
424:
399:
397:
396:
391:
383:
382:
379:
370:
369:
344:
342:
341:
336:
331:
330:
327:
289:
287:
286:
281:
279:
278:
275:
260:
258:
257:
252:
241:
240:
237:
228:
227:
224:
186:computer program
155:
148:
141:
99:
92:
85:
81:
78:
72:
67:this article by
58:inline citations
45:
44:
37:
21:
1291:
1290:
1286:
1285:
1284:
1282:
1281:
1280:
1261:
1260:
1259:
1254:
1235:Escape analysis
1203:Static analysis
1198:
1147:
1131:
1110:
1083:Code generation
1077:
1053:
1009:
1002:
924:
903:
898:
868:
842:
835:10.1.1.164.2284
825:
820:
814:
799:
795:
790:
776:
757:10.1.1.114.7330
741:
702:
698:
693:
692:
685:
656:
655:
651:
646:: 721–728, 1971
637:
636:
632:
624:
620:
615:
596:
569:
545:
530:
507:
481:
467:
466:
438:
437:
416:
402:
401:
374:
361:
347:
346:
322:
299:
298:
270:
265:
264:
232:
219:
199:
198:
159:
112:Lazy evaluation
93:
82:
76:
73:
63:Please help to
62:
46:
42:
35:
28:
23:
22:
15:
12:
11:
5:
1289:
1287:
1279:
1278:
1273:
1263:
1262:
1256:
1255:
1253:
1252:
1247:
1245:Shape analysis
1242:
1237:
1232:
1227:
1222:
1217:
1212:
1210:Alias analysis
1206:
1204:
1200:
1199:
1197:
1196:
1191:
1186:
1184:Jump threading
1181:
1176:
1171:
1166:
1161:
1155:
1153:
1149:
1148:
1146:
1145:
1139:
1137:
1133:
1132:
1130:
1129:
1124:
1118:
1116:
1112:
1111:
1109:
1108:
1103:
1098:
1093:
1087:
1085:
1079:
1078:
1076:
1075:
1070:
1064:
1062:
1055:
1054:
1052:
1051:
1046:
1041:
1036:
1030:
1025:
1020:
1014:
1012:
1004:
1003:
1001:
1000:
995:
990:
985:
983:Loop unrolling
980:
978:Loop splitting
975:
970:
965:
963:Loop inversion
960:
955:
950:
945:
940:
934:
932:
926:
925:
923:
922:
917:
911:
909:
905:
904:
899:
897:
896:
889:
882:
874:
867:
866:
861:
840:
818:
812:
796:
794:
793:External links
791:
789:
788:
774:
744:Danvy, Olivier
739:
718:10.1.1.10.2747
711:(4): 381–391.
699:
697:
694:
691:
690:
683:
649:
630:
617:
616:
614:
611:
610:
609:
604:
599:
594:
590:
585:
580:
575:
568:
565:
561:
560:
557:
554:
543:
528:
506:
503:
488:
484:
480:
477:
474:
454:
451:
448:
445:
423:
419:
415:
412:
409:
389:
386:
377:
373:
368:
364:
360:
357:
354:
334:
325:
321:
318:
315:
312:
309:
306:
273:
250:
247:
244:
235:
231:
222:
218:
215:
212:
209:
206:
179:specialization
161:
160:
158:
157:
150:
143:
135:
132:
131:
130:
129:
124:
119:
114:
106:
105:
95:
94:
49:
47:
40:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1288:
1277:
1274:
1272:
1269:
1268:
1266:
1251:
1248:
1246:
1243:
1241:
1238:
1236:
1233:
1231:
1228:
1226:
1223:
1221:
1218:
1216:
1213:
1211:
1208:
1207:
1205:
1201:
1195:
1192:
1190:
1187:
1185:
1182:
1180:
1177:
1175:
1172:
1170:
1167:
1165:
1162:
1160:
1157:
1156:
1154:
1150:
1144:
1141:
1140:
1138:
1134:
1128:
1125:
1123:
1122:Deforestation
1120:
1119:
1117:
1113:
1107:
1104:
1102:
1099:
1097:
1094:
1092:
1089:
1088:
1086:
1084:
1080:
1074:
1071:
1069:
1066:
1065:
1063:
1060:
1056:
1050:
1047:
1045:
1042:
1040:
1037:
1034:
1031:
1029:
1026:
1024:
1021:
1019:
1016:
1015:
1013:
1011:
1005:
999:
996:
994:
991:
989:
986:
984:
981:
979:
976:
974:
971:
969:
966:
964:
961:
959:
956:
954:
951:
949:
946:
944:
941:
939:
936:
935:
933:
931:
927:
921:
918:
916:
913:
912:
910:
906:
902:
895:
890:
888:
883:
881:
876:
875:
872:
865:
862:
857:
852:
848:
847:
841:
836:
831:
824:
819:
815:
813:9780130202499
809:
805:
804:
798:
797:
792:
785:
781:
777:
771:
767:
763:
758:
753:
749:
745:
740:
736:
732:
728:
724:
719:
714:
710:
706:
701:
700:
695:
686:
684:3-540-11980-9
680:
676:
672:
668:
664:
660:
653:
650:
645:
641:
634:
631:
627:
622:
619:
612:
608:
605:
603:
600:
598:
591:
589:
586:
584:
581:
579:
576:
574:
571:
570:
566:
564:
558:
555:
552:
551:
550:
547:
542:
538:
534:
527:
522:
520:
516:
512:
504:
502:
486:
482:
478:
475:
472:
452:
449:
446:
443:
421:
417:
413:
410:
407:
387:
375:
371:
366:
362:
358:
355:
352:
323:
319:
316:
313:
310:
307:
295:
293:
271:
261:
248:
245:
233:
229:
220:
216:
213:
210:
207:
204:
196:
194:
191:is seen as a
190:
187:
182:
180:
176:
172:
168:
156:
151:
149:
144:
142:
137:
136:
134:
133:
128:
125:
123:
120:
118:
115:
113:
110:
109:
108:
107:
104:
100:
91:
88:
80:
70:
66:
60:
59:
53:
48:
39:
38:
33:
19:
1188:
844:
802:
747:
708:
704:
658:
652:
643:
639:
633:
621:
562:
548:
540:
536:
532:
525:
523:
510:
508:
296:
291:
262:
197:
188:
183:
170:
164:
116:
83:
74:
55:
1035:elimination
953:Loop fusion
908:Basic block
675:2433/103401
578:Memoization
515:interpreter
292:static data
69:introducing
1265:Categories
1115:Functional
1033:Dead store
856:cs/9810010
775:0897915607
613:References
52:references
1008:Data-flow
830:CiteSeerX
752:CiteSeerX
713:CiteSeerX
487:∗
422:∗
385:→
367:∗
333:⟩
305:⟨
243:→
230:×
167:computing
1010:analysis
735:12673078
567:See also
77:May 2013
846:PEPM'99
597:theorem
380:dynamic
238:dynamic
193:mapping
65:improve
1136:Global
1061:-based
832:
810:
784:698339
782:
772:
754:
733:
715:
681:
544:static
529:static
517:for a
513:is an
328:static
290:, the
276:static
263:where
225:static
54:, but
1152:Other
851:arXiv
826:(PDF)
780:S2CID
731:S2CID
345:into
930:Loop
808:ISBN
770:ISBN
679:ISBN
644:54-C
537:prog
533:prog
511:prog
189:prog
1059:SSA
762:doi
723:doi
671:hdl
663:doi
524:If
465:to
177:by
165:In
1267::
828:.
778:.
768:.
760:.
729:.
721:.
709:12
707:.
677:.
669:.
642:,
595:mn
546:.
521:.
501:.
184:A
169:,
893:e
886:t
879:v
859:.
853::
838:.
816:.
786:.
764::
737:.
725::
687:.
673::
665::
628:.
593:s
541:I
526:I
483:g
479:o
476:r
473:p
453:g
450:o
447:r
444:p
418:g
414:o
411:r
408:p
388:O
376:I
372::
363:g
359:o
356:r
353:p
324:I
320:,
317:g
314:o
311:r
308:p
272:I
249:,
246:O
234:I
221:I
217::
214:g
211:o
208:r
205:p
154:e
147:t
140:v
90:)
84:(
79:)
75:(
61:.
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.