Meta tags:
Headings (most frequently used words):
programming, functional, comparison, to, imperative, and, functions, strict, non, contents, history, concepts, logic, applications, see, also, notes, references, further, reading, external, links, first, class, higher, order, pure, recursion, versus, evaluation, type, systems, referential, transparency, data, structures, vs, simulating, state, efficiency, issues, in, languages, text, editors, spreadsheets, microservices, academia, industry, education, abstraction, cost,
Text of the page (most frequently used words):
the (317), #programming (201), and (197), #functional (168), for (94), retrieved (79), languages (66), language (65), functions (60), with (58), from (57), are (56), that (53), can (50), function (39), such (38), data (36), imperative (34), this (32), order (32), edit (31), programs (30), 2009 (29), archived (29), original (29), higher (28), doi (28), which (28), use (27), logic (26), not (26), evaluation (26), have (26), recursion (25), used (25), pure (24), other (23), first (23), pdf (22), some (22), example (21), type (21), program (21), lambda (21), computer (21), java (20), haskell (19), isbn (19), 2024 (19), state (19), has (19), code (18), was (18), lisp (18), based (18), 2006 (18), also (18), its (18), mother (18), acm (17), using (16), types (16), object (16), lazy (16), 1145 (16), developed (16), all (15), org (15), oriented (15), style (15), class (15), 2011 (15), may (14), structures (14), john (14), calculus (14), scheme (14), clojure (14), s2cid (14), while (14), list (13), strict (13), 2013 (13), 2021 (13), science (13), most (13), arguments (13), they (13), been (13), side (13), effects (13), concurrent (12), immutable (12), part (12), python (12), implementation (12), 2008 (12), 2020 (12), like (12), scala (12), being (12), tail (12), history (12), their (12), purely (11), 978 (11), rust (11), compiler (11), but (11), articles (10), level (10), system (10), more (10), article (10), new (10), theory (10), 2007 (10), erlang (10), journal (10), systems (10), values (10), conference (10), one (10), including (10), however (10), into (10), even (10), result (10), main (10), non (9), computing (9), april (9), common (9), university (9), cufp (9), same (9), classes (9), expressions (9), since (9), when (9), many (9), any (9), them (9), called (9), features (8), design (8), simon (8), peter (8), press (8), structure (8), closures (8), charles (8), well (8), form (8), harry (8), loop (8), time (8), wikipedia (7), terms (7), paradigms (7), array (7), application (7), large (7), does (7), 2018 (7), perl (7), approach (7), book (7), why (7), communications (7), standard (7), 2012 (7), march (7), popular (7), notation (7), optimizations (7), applications (7), ocaml (7), between (7), turing (7), concepts (7), these (7), sometimes (7), several (7), research (7), means (7), map (7), implemented (7), number (7), memory (7), int (7), allow (7), page (6), july (6), javascript (6), august (6), php (6), third (6), second (6), machine (6), paradigm (6), comparison (6), space (6), algebraic (6), specific (6), value (6), anonymous (6), persistent (6), david (6), vol (6), 1998 (6), 2005 (6), sigplan (6), development (6), references (6), 2015 (6), analysis (6), church (6), industry (6), elizabeth (6), two (6), written (6), where (6), than (6), might (6), mutable (6), arrays (6), computations (6), way (6), toggle (5), about (5), text (5), statements (5), links (5), international (5), structured (5), concurrency (5), pattern (5), user (5), expression (5), dependent (5), recursive (5), nested (5), created (5), 1996 (5), limited (5), through (5), mit (5), how (5), curry (5), cambridge (5), 2017 (5), prevents (5), properties (5), returns (5), software (5), lang (5), computation (5), june (5), monads (5), hughes (5), uses (5), proceedings (5), information (5), proper (5), formal (5), concept (5), burstall (5), backus (5), landin (5), had (5), will (5), related (5), introduced (5), though (5), execution (5), strategy (5), diana (5), only (5), often (5), because (5), support (5), access (5), general (5), certain (5), express (5), return (5), variable (5), referential (5), transparency (5), transparent (5), typed (5), contents (4), search (4), developers (4), under (4), categories (4), cs1 (4), errors (4), description (4), control (4), very (4), high (4), multi (4), symbolic (4), parallel (4), actor (4), stack (4), english (4), declarative (4), syntax (4), introduction (4), external (4), paul (4), robert (4), combinatory (4), 1985 (4), interpretation (4), making (4), 2019 (4), department (4), com (4), richard (4), microservices (4), jones (4), issn (4), freeze (4), method (4), existing (4), doc (4), loops (4), runtime (4), hardware (4), optimization (4), february (4), programmer (4), without (4), complete (4), notes (4), guide (4), caml (4), inference (4), cite (4), 1993 (4), checking (4), equivalent (4), semantics (4), 1987 (4), 1994 (4), efficiency (4), make (4), association (4), machinery (4), algebra (4), abstract (4), who (4), kotlin (4), examples (4), commercial (4), finance (4), elixir (4), applied (4), see (4), teach (4), basis (4), implement (4), early (4), spreadsheets (4), generally (4), implementations (4), enable (4), emacs (4), parent (4), simply (4), generate (4), special (4), input (4), consider (4), fully (4), libraries (4), always (4), filter (4), reduce (4), each (4), allowing (4), constant (4), cost (4), argument (4), integer (4), issues (4), usually (4), thus (4), applying (4), different (4), numlist (4), update (4), referentially (4), changes (4), then (4), lets (4), mathematical (4), built (4), calls (4), hide (4), move (4), sidebar (4), add (3), table (3), view (3), statement (3), 2026 (3), states (3), low (3), assembly (3), lists (3), driven (3), separation (3), abstraction (3), inductive (3), automatic (3), models (3), constraint (3), production (3), transformation (3), simulation (3), natural (3), modeling (3), domain (3), streams (3), reactive (3), total (3), partial (3), call (3), procedural (3), mertz (3), help (3), file (3), addison (3), wesley (3), publishing (3), prentice (3), hall (3), practice (3), mark (3), north (3), holland (3), william (3), company (3), guy (3), sussman (3), gerald (3), jay (3), framework (3), allegro (3), need (3), 2016 (3), 2010 (3), building (3), implementing (3), december (3), defined (3), alan (3), peyton (3), 1017 (3), symposium (3), changed (3), added (3), addition (3), item (3), effective (3), operations (3), ibm (3), 135 (3), iterators (3), wiki (3), model (3), immutability (3), september (3), machines (3), lecture (3), springer (3), ways (3), category (3), san (3), diego (3), california (3), simple (3), unification (3), 185 (3), huet (3), gérard (3), later (3), launchbury (3), turner (3), fortran (3), 1977 (3), 1978 (3), liberated (3), von (3), neumann (3), correspondence (3), algol (3), writing (3), mccarthy (3), util (3), xml (3), range (3), web (3), wolfram (3), education (3), risk (3), similar (3), manner (3), given (3), considered (3), dialect (3), mid (3), 1990s (3), financial (3), active (3), there (3), academia (3), extensions (3), his (3), relational (3), father (3), relations (3), queried (3), case (3), represented (3), following (3), patterns (3), supported (3), aid (3), library (3), both (3), iteration (3), zero (3), abstractions (3), times (3), calling (3), 100 (3), version (3), efficiently (3), perform (3), modern (3), passing (3), seem (3), safe (3), fact (3), complex (3), create (3), purpose (3), counterparts (3), logarithmic (3), were (3), tasks (3), account (3), replaced (3), now (3), assignment (3), meaning (3), rocq (3), 1970s (3), accepts (3), makes (3), miranda (3), evaluate (3), requires (3), expressed (3), cannot (3), entities (3), treated (3), described (3), dialects (3), forms (3), iverson (3), tools (3), subsection (3), statistics (2), contact (2), privacy (2), policy (2), available (2), additional (2), apply (2), you (2), profit (2), organization (2), wikimedia (2), foundation (2), inc (2), commons (2), last (2), spoken (2), unsourced (2), template (2), wayback (2), deprecated (2), parameters (2), french (2), maint (2), location (2), missing (2), publisher (2), short (2), wikidata (2), comparisons (2), france (2), national (2), databases (2), generation (2), compiled (2), event (2), concerns (2), modifying (2), interactive (2), extensible (2), visual (2), graph (2), set (2), scripting (2), scientific (2), probabilistic (2), automata (2), query (2), applicative (2), point (2), free (2), gadts (2), prototype (2), small (2), modular (2), audio (2), subsequent (2), thompson (2), technical (2), englewood (2), cliffs (2), jersey (2), sullivan (2), reilly (2), world (2), 1990 (2), graham (2), dominus (2), jason (2), morgan (2), kaufmann (2), amsterdam (2), hindley (2), roger (2), brooks (2), feys (2), 1958 (2), 1985sicp (2), bibcode (2), abelson (2), hal (2), further (2), reading (2), imacs (2), better (2), life (2), what (2), students (2), introductory (2), engineering (2), berkeley (2), edition (2), wappalyzer (2), phoenix (2), commerce (2), stackshare (2), purescript (2), elm (2), companies (2), clojurescript (2), pascal (2), 1st (2), january (2), infoq (2), startup (2), 2003 (2), trading (2), derivative (2), whatsapp (2), 2014 (2), facebook (2), improving (2), 143 (2), 131 (2), spreadsheet (2), stallman (2), syntactic (2), combining (2), pages (2), 142 (2), daniel (2), freezing (2), removed (2), passed (2), mutability (2), michael (2), gosling (2), james (2), oracle (2), martin (2), project (2), functools (2), lua (2), developerworks (2), hartel (2), pieter (2), 2004 (2), 129 (2), experience (2), 2002 (2), cache (2), published (2), 2023 (2), scaleyourapp (2), understanding (2), collections (2), lifetimes (2), depth (2), benchmarks (2), game (2), vectors (2), 521 (2), berlin (2), heidelberg (2), 540 (2), 16761 (2), 1007 (2), 123 (2), change (2), identity (2), comprehensive (2), polymatheia (2), technology (2), matters (2), october (2), generalized (2), documentation (2), leroy (2), xavier (2), compcert (2), verified (2), citeseerx (2), undecidable (2), years (2), equations (2), 1973 (2), practical (2), harper (2), 751 (2), universal (2), cons (2), clinger (2), r6rs (2), revised (2), report (2), algorithmic (2), openscad (2), easier (2), 1093 (2), review (2), macqueen (2), sannella (2), hope (2), 1980 (2), 136 (2), darlington (2), paper (2), 641 (2), 359576 (2), 359579 (2), 613 (2), next (2), 700 (2), 101 (2), 308 (2), commonly (2), artificial (2), intelligence (2), field (2), proved (2), theorems (2), viewed (2), steele (2), evolution (2), link (2), formulation (2), 2266170 (2), jstor (2), 2307 (2), 1937 (2), 2268280 (2), known (2), dylan (2), tour (2), dlang (2), 1974 (2), processing (2), xslt (2), papers (2), lean (2), theorem (2), howard (2), 1238844 (2), hudak (2), commercially (2), aerospace (2), frequently (2), asked (2), training (2), mactech (2), editor (2), macscheme (2), 1984 (2), eager (2), portal (2), relatively (2), problem (2), classical (2), mechanics (2), methods (2), 137 (2), 138 (2), platforms (2), particularly (2), heavily (2), influenced (2), needed (2), seen (2), include (2), projects (2), wide (2), industrial (2), late (2), 1980s (2), become (2), computers (2), problems (2), areas (2), verification (2), static (2), initially (2), suitable (2), lack (2), academic (2), author (2), gnu (2), editors (2), ciao (2), resulting (2), prolog (2), phillip (2), grandparent (2), difference (2), here (2), maternal_grandmother (2), definition (2), relation (2), children (2), whereas (2), roughly (2), lambdas (2), simulate (2), basic (2), explicitly (2), feature (2), overhead (2), operation (2), elements (2), cpu (2), mean (2), direct (2), underlying (2), attributed (2), exception (2), involved (2), implements (2), various (2), slower (2), equals (2), must (2), true (2), running (2), optimize (2), speed (2), theoretical (2), leaks (2), analyzing (2), caches (2), schemes (2), suited (2), eliminating (2), allows (2), variants (2), instead (2), shared (2), mechanisms (2), message (2), cases (2), lead (2), itself (2), formally (2), less (2), efficient (2), easy (2), designed (2), clean (2), presence (2), effect (2), impure (2), current (2), still (2), around (2), difficult (2), understand (2), maintaining (2), simulating (2), avoids (2), amount (2), sum (2), traditional (2), numbers (2), older (2), would (2), returning (2), provides (2), random (2), trees (2), another (2), either (2), gives (2), never (2), gadt (2), avoiding (2), proposed (2), subset (2), proofs (2), intuitionistic (2), invalid (2), compilation (2), valid (2), reject (2), strong (2), test (2), false (2), milner (2), describes (2), proposes (2), fails (2), print (2), containing (2), failing (2), term (2), versus (2), unrestricted (2), cause (2), founded (2), unbounded (2), users (2), just (2), claim (2), among (2), approaches (2), compilers (2), operator (2), results (2), restriction (2), displaystyle (2), found (2), led (2), influence (2), associated (2), constructive (2), edinburgh (2), npl (2), incorporated (2), rather (2), 1960s (2), apl (2), ipl (2), extended (2), paradigmatic (2), numerous (2), 1930s (2), composing (2), appearance (2), upload (2), read (2), bahasa (2), log (2), donate (2), menu (2), topic, mobile, cookie, conduct, legal, safety, contacts, disclaimers, site, agree, registered, trademark, creative, attribution, sharealike, license, rendered, parsoid, edited, utc, hidden, haudio, microformats, 2022, webarchive, sources, matches, https, index, title, functional_programming, oldid, 1366590619, yale, lux, israel, spain, czech, republic, bnf, united, fast, gnd, authority, fifth, fourth, esoteric, interpreted, subjects, roles, literate, components, aspects, self, reflective, vibe, coding, demonstration, bayesian, synthesis, stage, metalinguistic, hygienic, macro, homoiconicity, generic, dynamic, attribute, metaprogramming, service, relativistic, process, partitioned, global, address, organic, multitier, macroprogramming, choreographic, mutual, exclusion, rewriting, templating, tactile, theoretic, quantum, filters, pipes, comprehension, interface, grammar, end, differentiable, spacecraft, command, action, dsl, ontology, nondeterministic, answer, abductive, synchronous, signals, flow, dataflow, monad, concatenative, uniform, agent, invariant, contract, block, jackson, akhmechet, slava, defmacro, rest, ford, neal, thinking, revision, dated, reflect, edits, minutes, listen, harlow, england, longman, craft, salus, handbook, indianapolis, indiana, macmillan, pratt, terrence, 3rd, marvin, victor, zelkowitz, brian, stewart, don, goerzen, real, michaelson, greg, courier, corporation, 486, 28029, maclennan, bruce, ansi, felleisen, matthias, findler, flatt, matthew, krishnamurthi, shriram, 1972, 7204, 2208, seldin, jonathan, craig, volume, cousineau, michel, mauny, 262, 51036, staff, thinkers, beneficial, home, adelphi, edu, network, twit, triangulation, interviewed, show, emmanuel, schanzer, bootstrap, denero, fall, electrical, sciences, 61a, preface, bsc, modules, imperial, college, london, oxford, www, websites, team, editorial, germany, news, know, best, polish, online, marketplace, herrick, justin, jah2488, bugnion, 9781785281372, packt, lorimer, live, announced, laurikari, ville, security, sims, steve, beating, averages, momtahan, lee, edf, pricing, blog, important, piece, our, infrastracture, million, november, sim, diasca, scale, discrete, engine, piro, christopher, rodger, manning, 9781638351733, tao, excel, blackwell, burnett, margaret, wakeling, 29429059, 0956, 7968, s0956796806006186, casas, cabeza, hermenegildo, 8th, flops, 162, friedman, byrd, oleg, kiselyov, hemann, reasoned, schemer, freezes, frozen, longer, changing, enumerability, configurability, writability, developer, mozilla, mdn, bloch, joshua, minimize, 0321356680, williams, quick, start, road, skarsaune, sics, port, translation, smalltalk, callable, objects, origins, van, rossum, guido, eich, brendan, popularity, golang, unofficial, faq, ufaq, digital, mars, henk, muller, hugh, glaser, 32346900, s0956796803004817, comparing, performance, dev, berthe, samuel, samber, nethercote, nicholas, mycroft, supplement, 0362, 1340, 773039, 773044, notices, behaviour, stock, realworldhaskell, chapter, profiling, cesarini, francesco, media, 596, 55585, build, blocking, throughput, distributed, docs, tutorials, essential, validating, borrowing, look, igor, pechtchanski, vivek, sarkar, specification, 662, 34527406, 1002, cpe, 853, 639, benchmarksgame, alioth, debian, fastest, spiewak, commit, 56543, working, paulson, larry, hartmanis, juris, hemachandra, lane, 1986, complexity, 226, 7_62, fun, thirteen, looking, turtle, newbern, monadic, barr, orange, jean, niklas, vector, 66350, chris, okasaki, chalmers, kennedy, andrew, russo, claudio, oopsla, 9781595930316, 1094811, 1094814, inria, manual, vytiniotis, dimitrios, geoffrey, washburn, icfp, weirich, stephanie, parameter, wells, typability, 3590, 176, tech, rep, 011, carreño, muñoz, tahar, eds, lncs, 2410, 15th, tphol, sep, 1976, universite, paris, vii, resolution, dans, des, langages, ordre, undecidability, 267, 1016, s0019, 9958, 90301, 257, foundations, principles, charleston, south, carolina, 154, 158511, 158618, 144, 768, 3217, jucs, 010, 0751, baker, henry, should, cheney, 16812984, 0897919874, 277650, 277719, 174, pldi, rationale, standardization, 338, 336, iso, iec, jtc, wg5, n2137, committee, draft, 007r2, pountain, dick, byte, comes, age, sean, tull, monoidal, leo, cheung, infoworld, your, leonard, stealthy, rise, bright, ars, technica, love, trendy, earn, discovering, assign, zhenjiang, meng, wang, mattered, 370, nsr, nwv042, 349, experimental, stanford, developing, considerations, invited, proc, infotech, art, conf, revolution, copenhagen, 0001, 0782, commun, 1966b, 166, 13409665, 365230, 365257, 157, 1965b, 165, 15781851, 363791, 363804, 158, 1965a, 6505810, 363744, 363749, diehl, stephan, sestoft, 2000, 739, future, 1964, 320, comjnl, british, society, mechanical, memoir, 1991, 189, 190, claims, newell, cliff, shaw, adjudged, parents, automatically, accomplish, invent, retrospectively, embeds, principia, mathematica, theorist, 465, 04640, herbert, gabriel, 330, 47047140, 201, 89502, 234286, 1057818, 233, 1960, 195, 1489409, 367177, 367199, 184, los, angeles, 800025, 808387, 173, hopl, 1940, 15889861, computability, definability, 163, 2317046, 153, package, vanderbauwhede, wim, cleaner, youtube, gophercon, meeus, cain, gang, ltd, metaclasses, holywell, architect, 9781940111056, 55860, 701, painter, ndc, oslo, sequel, 264, 249, sigfidet, boyce, raymond, chamberlin, donald, four, approached, novatchev, dimitre, proof, verlag, 387, 98503, chambers, schedule, includes, banz, matt, opensource, moura, leonardo, ullrich, sebastian, prover, automated, deduction, 12699, 635, 1611, 3349, 030, 79876, 5_37, 625, peake, alex, substantial, line, business, mansell, quantitative, wadler, 1238856, diverse, defense, startups, firms, lawnmower, manufacturers, minsky, yaron, weeks, stephen, 564, 30955392, s095679680800676x, 553, experiences, wall, street, larson, jim, 524392, 1467247, 1467263, armstrong, joe, 9781595937667, 1238850, questions, product, uncharted, colorado, math, cleis, kidd, eric, terrorism, response, hartheimer, anne, toolsmith, multitasking, 1989, 411, 207637854, 72551, 72554, 359, surveys, conception, topics, particular, choice, teaching, 141, outside, solving, geometric, 140, treat, others, 139, universities, analytics, investment, banks, factors, coded, interdependent, graphs, measure, correlations, market, shifts, regulatory, frameworks, variations, citation, categorical, capital, gröbner, widely, frontend, biggest, poland, classified, ads, platform, 134, lokalnie, 133, font, awesome, 132, 130, 128, 127, 126, 125, 124, employed, originally, intended, embedded, robot, driver, telescope, apple, macintosh, 122, 121, électricité, nortel, telecommunications, fault, tolerant, ericsson, swedish, area, publication, venues, focusing, trends, peer, reviewed, due, architectures, 120, composability, reuse, reusable, far, remain, primarily, nature, 119, 118, zeroth, highly, family, own, plugins, considers, favorite, 117, transforms, executes, representations, 116, needs, unnested, compared, compact, maternal, grandmother, instances, backwards, mothers, generalisation, every, output, inputs, outputs, 115, similarly, idea, included, tuple, 114, 113, expressible, dictates, corresponds, fold, catamorphism, visitor, necessary, replacements, capabilities, supports, replacement, 112, 111, 110, released, provide, expansive, inception, relegated, module, mainstream, 109, 108, 107, 106, 105, possible, traditionally, 104, 103, distinguishing, imposes, achieved, thanks, converted, standalone, instruction, controlling, iterative, writes, 102, stored, registers, unrolling, invocation, 1700, faster, handling, instance, benchmark, provided, profile, inlining, allocation, generics, str, illegalargumentexception, throw, uncheckedlongcast, bit, throws, defn, tool, linux, repl, leiningen, ryzen, 7900x, criterium, benchmarked, mod, check, asymptotically, slow, down, factor, introduce, improperly, discusses, give, advice, fixing, extensive, dereferenced, poorly, processors, deep, pipelines, miss, hundreds, cycles, potentially, virtue, reducing, hazards, locks, corresponding, synchronization, leverages, container, behavior, child, actors, queue, akka, atomic, nothing, assumptions, unsafe, increasing, opportunities, copying, implicit, dealing, computationally, costly, solve, issue, sharing, distinguishes, involves, inline, expansion, typically, straightforward, present, flat, accessed, deeply, pipelined, cpus, prefetched, handled, simd, instructions, equally, worst, slowdown, cells, balanced, tree, slowdowns, intensive, numerical, slightly, according, handle, multidimensional, matrices, pointer, chasing, alternative, track, explicit, uniqueness, hoare, managing, managed, updated, kind, enables, promoting, preferred, done, accept, together, leaving
Text of the page (random words):
pure to enable such optimizations fortran 95 also lets functions be designated pure 62 c 11 added constexpr keyword with similar semantics recursion edit main article recursion computer science iteration looping in functional languages is usually accomplished via recursion recursive functions invoke themselves letting an operation be repeated until it reaches the base case in general recursion requires maintaining a stack which consumes space in a linear amount to the depth of recursion this could make recursion prohibitively expensive to use instead of imperative loops however a special form of recursion known as tail recursion can be recognized and optimized by a compiler into the same code used to implement iteration in imperative languages tail recursion optimization can be implemented by transforming the program into continuation passing style during compiling among other approaches the scheme language standard requires implementations to support proper tail recursion meaning they must allow an unbounded number of active tail calls 63 64 proper tail recursion is not simply an optimization it is a language feature that assures users that they can use recursion to express a loop and doing so would be safe for space 65 moreover contrary to its name it accounts for all tail calls not just tail recursion while proper tail recursion is usually implemented by turning code into imperative loops implementations might implement it in other ways for example chicken intentionally maintains a stack and lets the stack overflow however when this happens its garbage collector will claim space back 66 allowing an unbounded number of active tail calls even though it does not turn tail recursion into a loop common patterns of recursion can be abstracted away using higher order functions with catamorphisms and anamorphisms or folds and unfolds being the most obvious examples such recursion schemes play a role analogous to built in control structures such as loops in imperative languages most general purpose functional programming languages allow unrestricted recursion and are turing complete which makes the halting problem undecidable can cause unsoundness of equational reasoning and generally requires the introduction of inconsistency into the logic expressed by the language s type system some special purpose languages such as rocq allow only well founded recursion and are strongly normalizing nonterminating computations can be expressed only with infinite streams of values called codata as a consequence these languages fail to be turing complete and expressing certain functions in them is impossible but they can still express a wide class of interesting computations while avoiding the problems introduced by unrestricted recursion functional programming limited to well founded recursion with a few other constraints is called total functional programming 67 strict versus non strict evaluation edit main article evaluation strategy functional languages can be categorized by whether they use strict eager or non strict lazy evaluation concepts that refer to how function arguments are processed when an expression is being evaluated the technical difference is in the denotational semantics of expressions containing failing or divergent computations under strict evaluation the evaluation of any term containing a failing subterm fails for example the python statement print len 2 1 3 2 1 0 5 4 fails under strict evaluation because of the division by zero in the third element of the list under lazy evaluation the length function returns the value 4 i e the number of items in the list since evaluating it does not attempt to evaluate the terms making up the list in brief strict evaluation always fully evaluates function arguments before invoking the function lazy evaluation does not evaluate function arguments unless their values are required to evaluate the function call itself the usual implementation strategy for lazy evaluation in functional languages is graph reduction 68 lazy evaluation is used by default in several pure functional languages including miranda clean and haskell hughes 1984 argues for lazy evaluation as a mechanism for improving program modularity through separation of concerns by easing independent implementation of producers and consumers of data streams 2 launchbury 1993 describes some difficulties that lazy evaluation introduces particularly in analyzing a program s storage requirements and proposes an operational semantics to aid in such analysis 69 harper 2009 proposes including both strict and lazy evaluation in the same language using the language s type system to distinguish them 70 type systems edit main article type system especially since the development of hindley milner type inference in the 1970s functional programming languages have tended to use typed lambda calculus rejecting all invalid programs at compilation time and risking false positive errors as opposed to the untyped lambda calculus that accepts all valid programs at compilation time and risks false negative errors used in lisp and its variants such as scheme as they reject all invalid programs at runtime when the information is enough to not reject valid programs the use of algebraic data types makes manipulation of complex data structures convenient the presence of strong compile time type checking makes programs more reliable in absence of other reliability techniques like test driven development while type inference frees the programmer from the need to manually declare types to the compiler in most cases some research oriented functional languages such as rocq agda cayenne and epigram are based on intuitionistic type theory which lets types depend on terms such types are called dependent types these type systems do not have decidable type inference and are difficult to understand and program with 71 72 73 74 but dependent types can express arbitrary propositions in higher order logic through the curry howard isomorphism then well typed programs in these languages become a means of writing formal mathematical proofs from which a compiler can generate certified code while these languages are mainly of interest in academic research including in formalized mathematics they have begun to be used in engineering as well compcert is a compiler for a subset of the language c that is written in rocq and formally verified 75 a limited form of dependent types called generalized algebraic data types gadt s can be implemented in a way that provides some of the benefits of dependently typed programming while avoiding most of its inconvenience 76 gadt s are available in the glasgow haskell compiler in ocaml 77 and in scala 78 and have been proposed as additions to other languages including java and c 79 referential transparency edit main article referential transparency functional programs do not have assignment statements that is the value of a variable in a functional program never changes once defined this eliminates any chances of side effects because any variable can be replaced with its actual value at any point of execution so functional programs are referentially transparent 80 consider c assignment statement x x 10 this changes the value assigned to the variable x let us say that the initial value of x was 1 then two consecutive evaluations of the variable x yields 10 and 100 respectively clearly replacing x x 10 with either 10 or 100 gives a program a different meaning and so the expression is not referentially transparent in fact assignment statements are never referentially transparent now consider another function such as int plusone int x return x 1 is transparent as it does not implicitly change the input x and thus has no such side effects functional programs exclusively use this type of function and are therefore referentially transparent data structures edit main article purely functional data structure purely functional data structures are often represented in a different way to their imperative counterparts 81 for example the array with constant access and update times is a basic component of most imperative languages and many imperative data structures such as the hash table and binary heap are based on arrays arrays can be replaced by maps or random access lists which admit purely functional implementation but have logarithmic access and update times purely functional data structures have persistence a property of keeping previous versions of the data structure unmodified in clojure persistent data structures are used as functional alternatives to their imperative counterparts persistent vectors for example use trees for partial updating calling the insert method will result in some but not all nodes being created 82 comparison to imperative programming edit functional programming is very different from imperative programming the most significant differences stem from the fact that functional programming avoids side effects which are used in imperative programming to implement state and i o pure functional programming completely prevents side effects and provides referential transparency higher order functions are rarely used in older imperative programming a traditional imperative program might use a loop to traverse and modify a list a functional program on the other hand would probably use a higher order map function that takes a function and a list generating and returning a new list by applying the function to each list item imperative vs functional programming edit the following two examples written in java achieve the same effect they multiply all even numbers in an array by 10 and add them all storing the final sum in the variable result traditional imperative loop int numlist 1 2 3 4 5 6 7 8 9 10 int result 0 for int i numlist if i 2 0 result i 10 functional programming with higher order functions import java util arrays int numlist 1 2 3 4 5 6 7 8 9 10 int result arrays stream numlist filter n n 2 0 map n n 10 reduce 0 integer sum sometimes the abstractions offered by functional programming might lead to development of more robust code that avoids certain issues that might arise when building upon large amount of complex imperative code such as off by one errors see greenspun s tenth rule simulating state edit there are tasks for example maintaining a bank account balance that often seem most naturally implemented with state pure functional programming performs these tasks and i o tasks such as accepting user input and printing to the screen in a different way the pure functional programming language haskell implements them using monads derived from category theory 83 monads offer a way to abstract certain types of computational patterns including but not limited to modeling of computations with mutable state and other side effects such as i o in an imperative manner without losing purity while existing monads may be easy to apply in a program given appropriate templates and examples many students find them difficult to understand conceptually e g when asked to define new monads which is sometimes needed for certain types of libraries 84 functional languages also simulate states by passing around immutable states this can be done by making a function accept the state as one of its parameters and return a new state together with the result leaving the old state unchanged 85 impure functional languages usually include a more direct method of managing mutable state clojure for example uses managed references that can be updated by applying pure functions to the current state this kind of approach enables mutability while still promoting the use of pure functions as the preferred way to express computations 86 alternative methods such as hoare logic and uniqueness have been developed to track side effects in programs some modern research languages use effect systems to make the presence of side effects explicit 87 efficiency issues edit functional programming languages are typically less efficient in their use of cpu and memory than imperative languages such as c and pascal 88 this is related to the fact that some mutable data structures like arrays have a very straightforward implementation using present hardware flat arrays may be accessed very efficiently with deeply pipelined cpus prefetched efficiently through caches with no complex pointer chasing or handled with simd instructions it is also not easy to create their equally efficient general purpose immutable counterparts for purely functional languages the worst case slowdown is logarithmic in the number of memory cells used because mutable memory can be represented by a purely functional data structure with logarithmic access time such as a balanced tree 89 however such slowdowns are not universal for programs that perform intensive numerical computations functional languages such as ocaml and clean are only slightly slower than c according to the computer language benchmarks game 90 for programs that handle large matrices and multidimensional databases array functional languages such as j and k were designed with speed optimizations immutability of data can in many cases lead to execution efficiency by allowing the compiler to make assumptions that are unsafe in an imperative language thus increasing opportunities for inline expansion 91 even if the involved copying that may seem implicit when dealing with persistent immutable data structures might seem computationally costly some functional programming languages like clojure solve this issue by implementing mechanisms for safe memory sharing between formally immutable data 92 rust distinguishes itself by its approach to data immutability which involves immutable references 93 and a concept called lifetimes 94 immutable data with separation of identity and state and shared nothing schemes can also potentially be more well suited for concurrent and parallel programming by the virtue of reducing or eliminating the risk of certain concurrency hazards since concurrent operations are usually atomic and this allows eliminating the need for locks this is how for example java util concurrent classes are implemented where some of them are immutable variants of the corresponding classes that are not suitable for concurrent use 95 functional programming languages often have a concurrency model that instead of shared state and synchronization leverages message passing mechanisms such as the actor model where each actor is a container for state behavior child actors and a message queue 96 97 this approach is common in erlang elixir or akka lazy evaluation may also speed up the program even asymptotically whereas it may slow it down at most by a constant factor however it may introduce memory leaks if used improperly launchbury 1993 69 discusses theoretical issues related to memory leaks from lazy evaluation and o sullivan et al 2008 98 give some practical advice for analyzing and fixing them however the most general implementat...
|
