147:. However, it is still possible that an eager evaluation may not terminate while the lazy evaluation of the same program halts. An advantage of this is that lazy evaluation can be implemented much more easily; as all expressions will return the same result at any moment (regardless of program state), their evaluation can be delayed as much as necessary.
155:
In a purely functional language, the only dependencies between computations are data dependencies, and computations are deterministic. Therefore, to program in parallel, the programmer need only specify the pieces that should be computed in parallel, and the runtime can handle all other details such
159:
To ensure a speedup, the granularity of tasks must be carefully chosen to be neither too big nor too small. In theory, it is possible to use runtime profiling and compile-time analysis to judge whether introducing parallelism will speed up the program, and thus automatically parallelize purely
156:
as distributing tasks to processors, managing synchronization and communication, and collecting garbage in parallel. This style of programming avoids common issues such as race conditions and deadlocks, but has less control than an imperative language.
223:
In general, conversion of an imperative program to a purely functional one also requires ensuring that the formerly-mutable structures are now explicitly returned from functions that update them, a program structure called
68:
paradigm, will only depend on their arguments, regardless of any global or local state. A pure functional subroutine only has visibility of changes of state represented by state variables included in its scope.
220:. Therefore, purely functional data structures can be used in languages which are non-functional, but they may not be the most efficient tool available, especially if persistency is not required.
422:
243:
A purely functional language is a language which only admits purely functional programming. Purely functional programs can however be written in languages which are not purely functional.
181:. Persistency is required for functional programming; without it, the same computation could return different results. Functional programming may use persistent non-purely functional
139:
which ends on a purely functional program returns the same result. In particular, it ensures that the programmer does not have to consider in which order programs are evaluated, since
564:
1311:
470:
534:
355:
automatically. In order to accomplish this, they had to invent a language and a paradigm which, which viewed retrospectively, embeds functional programming.
213:
77:
The exact difference between pure and impure functional programming is a matter of controversy. Sabry's proposed definition of purity is that all common
483:
57:
of a state-transforming function, which returns the updated state as part of its return value. This style handles state changes without losing the
633:
568:
1304:
108:
that use mutable cells, which update their state as side effects. In fact, the earliest programming languages cited as being functional,
463:
200:
with constant-time access and update is a basic component of most imperative languages and many imperative data-structures, such as
697:
237:
1297:
1047:
909:
1404:
1394:
1053:
160:
functional programs. In practice, this has not been terribly successful, and fully automatic parallelization is not practical.
53:, as explicit variables that represent the program state at each step of a program execution: a variable state is passed as an
345:
claims that he, Al Newell, and Cliff Shaw are "commonly adjudged to be the parents of artificial intelligence ", for writing
1452:
1409:
1399:
1389:
456:
1366:
1238:
986:
706:
407:
365:
314:
440:
342:
81:(call-by-name, call-by-value, and call-by-need) produce the same result, ignoring strategies that error or diverge.
1381:
1078:
758:
702:
174:
169:
1475:
1361:
938:
811:
742:
677:
600:
109:
1470:
1441:
1356:
1116:
879:
509:
1371:
894:
884:
105:
1278:
1258:
1188:
1131:
1093:
1083:
1043:
968:
904:
874:
801:
790:
687:
667:
642:
605:
1233:
996:
963:
858:
834:
796:
776:
672:
581:
559:
544:
113:
1430:
1180:
1166:
1073:
1033:
958:
864:
844:
711:
590:
524:
432:
400:
Parallel and
Concurrent Programming in Haskell: Techniques for Multicore and Multithreaded Programming
1273:
1038:
948:
928:
914:
178:
1253:
1213:
1156:
1088:
826:
657:
274:
96:. However, a first-class function need not be purely functional, as it may use techniques from the
58:
1263:
1243:
1184:
1171:
1151:
978:
715:
619:
577:
448:
1223:
1198:
1192:
1136:
1098:
786:
781:
733:
628:
529:
501:
492:
269:
209:
193:
97:
85:
65:
36:
1125:
1121:
1063:
1015:
585:
351:
93:
1349:
1320:
1268:
1248:
1208:
1010:
869:
738:
725:
479:
197:
101:
89:
28:
8:
1203:
1141:
953:
933:
919:
651:
519:
514:
225:
136:
130:
78:
1020:
973:
943:
889:
748:
647:
539:
287:
1344:
1339:
1176:
1068:
923:
899:
839:
806:
768:
753:
692:
436:
403:
369:
338:
310:
31:—a style of building the structure and elements of computer programs—that treats all
291:
216:, which admits purely functional implementation, but the access and update time is
1058:
990:
854:
595:
377:
330:
279:
140:
20:
1289:
1108:
982:
848:
549:
144:
54:
1160:
816:
682:
346:
189:
182:
50:
283:
64:
Purely functional programming consists of ensuring that functions, inside the
1464:
1146:
428:
185:, while those data structures may not be used in purely functional programs.
42:
72:
1334:
381:
1028:
205:
84:
A program is usually said to be functional when it uses some concepts of
32:
201:
217:
260:
Sabry, Amr (January 1993). "What is a purely functional language?".
478:
46:
116:, are both "impure" functional languages by Sabry's definition.
119:
374:
In ACM SIGPLAN History of
Programming Languages Conference
73:
Difference between pure and impure functional programming
124:
192:
are often represented in a different way than their
1319:
208:, are based on arrays. Arrays can be replaced by
238:List of programming languages by type § Pure
1462:
16:Programming paradigm entirely based on functions
1305:
464:
231:
120:Properties of purely functional programming
1312:
1298:
471:
457:
535:Programming in the large and in the small
273:
393:
391:
364:
349:, a program which proved theorems from
304:
1463:
397:
1293:
452:
388:
259:
150:
307:Functional Programming in Javascript
253:
236:For a more comprehensive list, see
125:Strict versus non-strict evaluation
13:
163:
14:
1487:
424:Purely functional data structures
262:Journal of Functional Programming
175:Purely functional data structures
49:objects are usually modeled with
1079:Partitioned global address space
402:. O'Reilly Media. pp. 5–6.
170:Purely functional data structure
143:will return the same result as
1321:Types of programming languages
416:
398:Marlow, Simon (18 June 2013).
358:
323:
305:Atencio, Luis (18 June 2016).
298:
1:
246:
25:purely functional programming
1453:Programming paradigms navbox
606:Uniform Function Call Syntax
196:counterparts. For example,
61:of the program expressions.
7:
1421:
1074:Parallel programming models
1048:Concurrent constraint logic
10:
1494:
1167:Metalinguistic abstraction
1034:Automatic mutual exclusion
433:Cambridge University Press
235:
232:Purely functional language
167:
128:
1380:
1327:
1222:
1107:
1039:Choreographic programming
1009:
825:
767:
724:
627:
618:
558:
500:
491:
284:10.1017/S0956796897002943
1089:Relativistic programming
309:. Manning Publications.
59:referential transparency
1476:Functional programming
1099:Structured concurrency
484:Comparison by language
94:higher-order functions
86:functional programming
37:mathematical functions
1471:Programming paradigms
1442:Programming languages
1064:Multitier programming
880:Interface description
480:Programming paradigms
382:10.1145/800025.808387
352:Principia Mathematica
90:first-class functions
79:evaluation strategies
35:as the evaluation of
27:usually designates a
29:programming paradigm
1204:Self-modifying code
812:Probabilistic logic
743:Functional reactive
698:Expression-oriented
652:Partial application
226:store-passing style
137:evaluation strategy
131:Evaluation strategy
1117:Attribute-oriented
890:List comprehension
835:Algebraic modeling
648:Anonymous function
540:Design by contract
510:Jackson structures
214:random access list
188:Purely functional
151:Parallel computing
100:paradigm, such as
1431:Computer language
1418:
1417:
1287:
1286:
1177:Program synthesis
1069:Organic computing
1005:
1004:
910:Non-English-based
885:Language-oriented
663:Purely functional
614:
613:
370:"History of Lisp"
335:Models of My Life
1483:
1457:
1451:
1446:
1440:
1435:
1429:
1314:
1307:
1300:
1291:
1290:
1189:by demonstration
1094:Service-oriented
1084:Process-oriented
1059:Macroprogramming
1044:Concurrent logic
915:Page description
905:Natural language
875:Grammar-oriented
802:Nondeterministic
791:Constraint logic
693:Point-free style
688:Functional logic
625:
624:
596:Immutable object
515:Block-structured
498:
497:
473:
466:
459:
450:
449:
443:
420:
414:
413:
395:
386:
385:
362:
356:
331:Herbert A. Simon
327:
321:
320:
302:
296:
295:
277:
257:
141:eager evaluation
104:or input/output
21:computer science
1493:
1492:
1486:
1485:
1484:
1482:
1481:
1480:
1461:
1460:
1455:
1449:
1444:
1438:
1433:
1427:
1424:
1419:
1414:
1376:
1367:Very high-level
1323:
1318:
1288:
1283:
1225:
1218:
1109:Metaprogramming
1103:
1019:
1014:
1001:
983:Graph rewriting
821:
797:Inductive logic
777:Abductive logic
763:
720:
683:Dependent types
631:
610:
582:Prototype-based
562:
560:Object-oriented
554:
550:Nested function
545:Invariant-based
487:
477:
447:
446:
421:
417:
410:
396:
389:
363:
359:
328:
324:
317:
303:
299:
258:
254:
249:
241:
234:
190:data structures
183:data structures
172:
166:
164:Data structures
153:
145:lazy evaluation
133:
127:
122:
75:
55:input parameter
17:
12:
11:
5:
1491:
1490:
1479:
1478:
1473:
1459:
1458:
1447:
1436:
1423:
1420:
1416:
1415:
1413:
1412:
1407:
1402:
1397:
1392:
1386:
1384:
1378:
1377:
1375:
1374:
1369:
1364:
1359:
1353:
1352:
1347:
1342:
1337:
1331:
1329:
1325:
1324:
1317:
1316:
1309:
1302:
1294:
1285:
1284:
1282:
1281:
1276:
1271:
1266:
1261:
1256:
1251:
1246:
1241:
1236:
1230:
1228:
1220:
1219:
1217:
1216:
1211:
1206:
1201:
1196:
1174:
1169:
1164:
1154:
1149:
1144:
1139:
1134:
1129:
1119:
1113:
1111:
1105:
1104:
1102:
1101:
1096:
1091:
1086:
1081:
1076:
1071:
1066:
1061:
1056:
1051:
1041:
1036:
1031:
1025:
1023:
1007:
1006:
1003:
1002:
1000:
999:
994:
979:Transformation
976:
971:
966:
961:
956:
951:
946:
941:
936:
931:
926:
917:
912:
907:
902:
897:
892:
887:
882:
877:
872:
867:
865:Differentiable
862:
852:
845:Automata-based
842:
837:
831:
829:
823:
822:
820:
819:
814:
809:
804:
799:
794:
784:
779:
773:
771:
765:
764:
762:
761:
756:
751:
746:
736:
730:
728:
722:
721:
719:
718:
712:Function-level
709:
700:
695:
690:
685:
680:
675:
670:
665:
660:
655:
645:
639:
637:
622:
616:
615:
612:
611:
609:
608:
603:
598:
593:
588:
574:
572:
556:
555:
553:
552:
547:
542:
537:
532:
527:
525:Non-structured
522:
517:
512:
506:
504:
495:
489:
488:
476:
475:
468:
461:
453:
445:
444:
415:
409:978-1449335946
408:
387:
366:McCarthy, John
357:
347:Logic Theorist
329:The memoir of
322:
316:978-1617292828
315:
297:
275:10.1.1.27.7800
251:
250:
248:
245:
233:
230:
168:Main article:
165:
162:
152:
149:
129:Main article:
126:
123:
121:
118:
74:
71:
51:temporal logic
15:
9:
6:
4:
3:
2:
1489:
1488:
1477:
1474:
1472:
1469:
1468:
1466:
1454:
1448:
1443:
1437:
1432:
1426:
1425:
1411:
1408:
1406:
1403:
1401:
1398:
1396:
1393:
1391:
1388:
1387:
1385:
1383:
1379:
1373:
1370:
1368:
1365:
1363:
1360:
1358:
1355:
1354:
1351:
1348:
1346:
1343:
1341:
1338:
1336:
1333:
1332:
1330:
1326:
1322:
1315:
1310:
1308:
1303:
1301:
1296:
1295:
1292:
1280:
1277:
1275:
1272:
1270:
1267:
1265:
1262:
1260:
1257:
1255:
1252:
1250:
1249:Data-oriented
1247:
1245:
1242:
1240:
1237:
1235:
1232:
1231:
1229:
1227:
1221:
1215:
1212:
1210:
1207:
1205:
1202:
1200:
1197:
1194:
1190:
1186:
1182:
1178:
1175:
1173:
1170:
1168:
1165:
1162:
1158:
1155:
1153:
1150:
1148:
1147:Homoiconicity
1145:
1143:
1140:
1138:
1135:
1133:
1130:
1127:
1123:
1120:
1118:
1115:
1114:
1112:
1110:
1106:
1100:
1097:
1095:
1092:
1090:
1087:
1085:
1082:
1080:
1077:
1075:
1072:
1070:
1067:
1065:
1062:
1060:
1057:
1055:
1054:Concurrent OO
1052:
1049:
1045:
1042:
1040:
1037:
1035:
1032:
1030:
1027:
1026:
1024:
1022:
1017:
1012:
1008:
998:
995:
992:
988:
984:
980:
977:
975:
972:
970:
967:
965:
962:
960:
957:
955:
952:
950:
949:Set-theoretic
947:
945:
942:
940:
937:
935:
932:
930:
929:Probabilistic
927:
925:
921:
918:
916:
913:
911:
908:
906:
903:
901:
898:
896:
893:
891:
888:
886:
883:
881:
878:
876:
873:
871:
868:
866:
863:
860:
856:
853:
850:
846:
843:
841:
838:
836:
833:
832:
830:
828:
824:
818:
815:
813:
810:
808:
805:
803:
800:
798:
795:
792:
788:
785:
783:
780:
778:
775:
774:
772:
770:
766:
760:
757:
755:
752:
750:
747:
744:
740:
737:
735:
732:
731:
729:
727:
723:
717:
713:
710:
708:
707:Concatenative
704:
701:
699:
696:
694:
691:
689:
686:
684:
681:
679:
676:
674:
671:
669:
666:
664:
661:
659:
656:
653:
649:
646:
644:
641:
640:
638:
635:
630:
626:
623:
621:
617:
607:
604:
602:
599:
597:
594:
592:
589:
587:
583:
579:
576:
575:
573:
570:
566:
561:
557:
551:
548:
546:
543:
541:
538:
536:
533:
531:
528:
526:
523:
521:
518:
516:
513:
511:
508:
507:
505:
503:
499:
496:
494:
490:
485:
481:
474:
469:
467:
462:
460:
455:
454:
451:
442:
441:0-521-66350-4
438:
434:
430:
429:Chris Okasaki
426:
425:
419:
411:
405:
401:
394:
392:
383:
379:
375:
371:
368:(June 1978).
367:
361:
354:
353:
348:
344:
343:0-465-04640-1
340:
336:
332:
326:
318:
312:
308:
301:
293:
289:
285:
281:
276:
271:
267:
263:
256:
252:
244:
239:
229:
227:
221:
219:
215:
211:
207:
203:
199:
195:
191:
186:
184:
180:
176:
171:
161:
157:
148:
146:
142:
138:
132:
117:
115:
111:
107:
103:
99:
95:
91:
87:
82:
80:
70:
67:
62:
60:
56:
52:
48:
44:
43:Program state
40:
38:
34:
30:
26:
22:
1456:}}
1450:{{
1445:}}
1439:{{
1434:}}
1428:{{
1254:Event-driven
662:
658:Higher-order
586:Object-based
423:
418:
399:
373:
360:
350:
334:
325:
306:
300:
265:
261:
255:
242:
222:
187:
173:
158:
154:
134:
83:
76:
63:
41:
24:
18:
1350:Interpreted
1264:Intentional
1244:Data-driven
1226:of concerns
1185:Inferential
1172:Multi-stage
1152:Interactive
1029:Actor-based
1016:distributed
959:Stack-based
759:Synchronous
716:Value-level
703:Applicative
620:Declarative
578:Class-based
376:: 217–223.
337:pp.189-190
268:(1): 1–22.
218:logarithmic
206:binary heap
33:computation
1465:Categories
1382:Generation
1362:High-level
1239:Components
1224:Separation
1199:Reflective
1193:by example
1137:Extensible
1011:Concurrent
987:Production
974:Templating
954:Simulation
939:Scientific
859:Spacecraft
787:Constraint
782:Answer set
734:Flow-based
634:comparison
629:Functional
601:Persistent
565:comparison
530:Procedural
502:Structured
493:Imperative
247:References
202:hash table
194:imperative
179:persistent
98:imperative
88:, such as
66:functional
1357:Low-level
1126:Inductive
1122:Automatic
944:Scripting
643:Recursive
270:CiteSeerX
1422:See also
1372:Esoteric
1345:Compiled
1340:Assembly
1279:Subjects
1269:Literate
1259:Features
1214:Template
1209:Symbolic
1181:Bayesian
1161:Hygienic
1021:parallel
900:Modeling
895:Low-code
870:End-user
807:Ontology
739:Reactive
726:Dataflow
435:, 1998,
333:(1991),
292:30595712
1335:Machine
1234:Aspects
1142:Generic
1132:Dynamic
991:Pattern
969:Tactile
934:Quantum
924:filters
855:Command
754:Streams
749:Signals
520:Modular
106:methods
47:mutable
1405:Fourth
1395:Second
997:Visual
964:System
849:Action
673:Strict
439:
406:
341:
313:
290:
272:
102:arrays
1410:Fifth
1400:Third
1390:First
1328:Level
1274:Roles
1157:Macro
920:Pipes
840:Array
817:Query
769:Logic
678:GADTs
668:Total
591:Agent
288:S2CID
198:array
135:Each
922:and
569:list
437:ISBN
404:ISBN
339:ISBN
311:ISBN
204:and
177:are
114:Lisp
112:and
92:and
45:and
827:DSL
427:by
378:doi
280:doi
212:or
210:map
110:IPL
19:In
1467::
1191:,
1187:,
1183:,
989:,
985:,
714:,
705:,
584:,
580:,
567:,
431:,
390:^
372:.
286:.
278:.
264:.
228:.
39:.
23:,
1313:e
1306:t
1299:v
1195:)
1179:(
1163:)
1159:(
1128:)
1124:(
1050:)
1046:(
1018:,
1013:,
993:)
981:(
861:)
857:(
851:)
847:(
793:)
789:(
745:)
741:(
654:)
650:(
636:)
632:(
571:)
563:(
486:)
482:(
472:e
465:t
458:v
412:.
384:.
380::
319:.
294:.
282::
266:8
240:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.