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