{"history":[],"article":{"id":"da998703-44ff-423b-9a18-328f3d7a50fb","title":"Refal","slug":"refal","content":":::summary\n**Name:** Refal \n**Released:** 1968 \n**Paradigm:** [Pattern-matching](https://bliptext.com/articles/pattern-matching) and [term-rewriting](https://bliptext.com/articles/term-rewriting) \n**Designer:** [Valentin Turchin](https://bliptext.com/articles/valentin-turchin) \n**Developer:** Valentin Turchin, S. Florentsev, V. Olyunin, et al. \n**Website:** http://www.refal.net \n**Typing:** [strong](https://bliptext.com/articles/strong-typing), [dynamic](https://bliptext.com/articles/dynamic-typing) \n**Implementations:** Refal-2, Refal-5, Refal-6, Refal+ \n:::\n\n# \n**Refal** (**\"Recursive functions algorithmic language\"**; ) \"is a [functional](https://bliptext.com/articles/functional-programming) [programming language](https://bliptext.com/articles/programming-language) oriented toward symbolic computations\", including \"[string processing](https://bliptext.com/articles/string-processing), [language translation](https://bliptext.com/articles/translation), [and] [artificial intelligence](https://bliptext.com/articles/artificial-intelligence)\".\nIt is one of the oldest members of this family, first conceived of in 1966 as a theoretical tool, with the first implementation appearing in 1968.\nRefal was intended to combine mathematical simplicity with practicality for writing large and sophisticated programs.\nOne of the first functional programming languages to do so, and unlike [Lisp](https://bliptext.com/articles/lisp-programming-language) of its time, Refal is based on [pattern matching](https://bliptext.com/articles/pattern-matching).\nIts pattern matching works in conjunction with [term rewriting](https://bliptext.com/articles/term-rewriting).\nThe basic [data structure](https://bliptext.com/articles/data-structure) of Lisp and [Prolog](https://bliptext.com/articles/prolog) is a linear list built by [cons operation](https://bliptext.com/articles/cons) in a sequential manner, thus with O(n) access to list's nth element.\nRefal's lists are built and scanned from both ends, with pattern matching working for nested lists as well as the top-level one.\nIn effect, the basic data structure of Refal is a [tree](https://bliptext.com/articles/tree-computer-science) rather than a [list](https://bliptext.com/articles/list-computer-science).\nThis gives freedom and convenience in creating data structures while using only mathematically simple control mechanisms of pattern matching and substitution.\nRefal also includes a feature called the freezer to support efficient [partial evaluation](https://bliptext.com/articles/partial-evaluation).\nRefal can be applied to the processing and transformation of tree structures, similarly to [XSLT](https://bliptext.com/articles/xslt).\n\n# Basics\nA Refal [Hello World](https://bliptext.com/articles/hello-world-program) example is shown below.\n$ENTRY Go { = ;}\nHello {\n= ;\n}\nThe program above includes two functions named Go and Hello.\nA function is written as the name of the function followed by the function body in curly braces.\nThe Go function is marked as the entry point of the program using the $ENTRY directive.\nOne could think of expressions in the function bodies as function \"calls\" in [Lisp](https://bliptext.com/articles/lisp-programming-language)-like syntax.\nFor example, the Hello function appears to call the built-in Prout function with the string 'Hello world' as the argument.\nThe meaning and the mechanism of the call, however, is quite different.\nTo illustrate the difference, consider the following function that determines whether a string is a [palindrome](https://bliptext.com/articles/palindrome).\nPal { = True;\ns.1 = True;\ns.1 e.2 s.1 = ;\ne.1 = False; }\nThis example shows a function with a more complex body, consisting of four sentences (clauses).\nA sentence begins with a pattern followed by an equal sign followed by a general expression on the right hand side.\nA sentence is terminated with a semicolon.\nFor example, the pattern of the second sentence of the function is \"s.1\" and the expression is \"True\".\nAs the example shows, patterns include pattern variables that have the form of a character identifying the type of the variable (what the variable matches) followed by the variable identifier.\nThe variables that begin with an \"s\" match a single symbol, those that begin with an \"e\" match an arbitrary expression.\nThe variable identifier can be an arbitrary alphanumeric sequence optionally separated from the type identifier by a dot.\nA function executes by comparing its argument with the patterns of its sentences in the order they appear in the definition, until the first pattern that matches.\nThe function then replaces the argument with the expression on the right hand side of the matched sentence.\nIf the result of a function application includes a subexpression in angle brackets (as it will after the third sentence of our example is applied), the result is further processed by Refal by invoking the function identified by the first symbol in the brackets.\nExecution stops when the result has no more angle brackets to expand in this way.\nThe function Pal can thus be read informally as: \"If the expression is empty, replace it with True. Otherwise if the expression is a single symbol, replace it with True. Otherwise if the expression is a symbol followed by an arbitrary expression e.2 followed by the same symbol, replace it with the expression . (In other words, throw away the two identical symbols at the beginning and the end and recurse). Otherwise replace the expression with False. (The pattern e.1 always matches).\"\nThe following are three step-by-step execution traces annotated with the sentence numbers applied at each step to produce the next\n (#3)\n (#3)\n (#1)\nTrue\n (#3)\n (#2)\nTrue\n (#3)\n (#3)\n (#3)\n (#4)\nFalse\nWe can now see that the Hello World example in fact executes as the sequence of the following expression transformations:\nSeed the machine with the initial expression marked by $ENTRY:\n (apply the sentence in Go)\n (apply the sentence in Hello)\n (Prout is a built-in that prints and expands to nothing)\n(nothing to apply; stop)\n\n# Other examples\n\n## Factorial\nFact { 0 = 1;\ns.N = <* s.N >>; }\nHere 0 matches 0 the number and produces 1.\nOn any other symbol which is a number, multiply it with the result of (Fact (- s.N 1))\nNote the prefix style of operators.\n\n## Factorial with loops\nFact { s.n = ; };\nLoop {\n0 s.f = s.f; s.n s.f = <* s.n s.f>>; }\nAs can be seen s.n acts as the loop counter.\n\n## Equality\nEqual {\n(e.1)(e.1) = T; (e.1)(e.2) = F; }\nHere the function is defined as, if given two terms, and the terms are same then the first clause matches and produces True.\nelse the second clause matches and produces False.\nAn important property of Refal is that all functions in refal are single argument.\n(But may be decomposed into terms in an expression as above.)\n\n## If\nDefining control structures is easy\nIf {\nT Then (e.1) Else (e.2) = e.1;\nF Then (e.1) Else (e.2) = e.2; }\nHere the e1 is evaluated only when the expression entered matches 'True' Then e1 Else e2 the same for e2.\n\n## Squeeze blanks\nSqueeze {\ne.1'__'e.2 = ;\ne.1 = e.1; }\n(Using '_' in place of space char so as to make the function call clear.)\nThe first clause matches whenever the function Squeeze encounters double\nblanks in its input expression, and replaces it with a single blank.\nThe second clause matches only when the first one did not, and returns the\nresultant value which is the current expression.\n\n## Squeeze using explicit looping\nSqueeze {\n'__'e.1 = ;\ns.A e.1 = s.A ;\n= ; };","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-26T10:19:44.858Z","updated_at":"2025-01-26T10:19:44.858Z","search_vector":"'refal':1","search_content":" \n**Name:** Refal \n**Released:** 1968 \n**Paradigm:** [Pattern-matching](https://bliptext.com/articles/pattern-matching) and [term-rewriting](https://bliptext.com/articles/term-rewriting) \n**Designer:** [Valentin Turchin](https://bliptext.com/articles/valentin-turchin) \n**Developer:** Valentin Turchin, S. Florentsev, V. Olyunin, et al. \n**Website:** http://www.refal.net \n**Typing:** [strong](https://bliptext.com/articles/strong-typing), [dynamic](https://bliptext.com/articles/dynamic-typing) \n**Implementations:** Refal-2, Refal-5, Refal-6, Refal+ \n \n\n# \n**Refal** (**\"Recursive functions algorithmic language\"**; ) \"is a [functional](https://bliptext.com/articles/functional-programming) [programming language](https://bliptext.com/articles/programming-language) oriented toward symbolic computations\", including \"[string processing](https://bliptext.com/articles/string-processing), [language translation](https://bliptext.com/articles/translation), [and] [artificial intelligence](https://bliptext.com/articles/artificial-intelligence)\".\nIt is one of the oldest members of this family, first conceived of in 1966 as a theoretical tool, with the first implementation appearing in 1968.\nRefal was intended to combine mathematical simplicity with practicality for writing large and sophisticated programs.\nOne of the first functional programming languages to do so, and unlike [Lisp](https://bliptext.com/articles/lisp-programming-language) of its time, Refal is based on [pattern matching](https://bliptext.com/articles/pattern-matching).\nIts pattern matching works in conjunction with [term rewriting](https://bliptext.com/articles/term-rewriting).\nThe basic [data structure](https://bliptext.com/articles/data-structure) of Lisp and [Prolog](https://bliptext.com/articles/prolog) is a linear list built by [cons operation](https://bliptext.com/articles/cons) in a sequential manner, thus with O(n) access to list's nth element.\nRefal's lists are built and scanned from both ends, with pattern matching working for nested lists as well as the top-level one.\nIn effect, the basic data structure of Refal is a [tree](https://bliptext.com/articles/tree-computer-science) rather than a [list](https://bliptext.com/articles/list-computer-science).\nThis gives freedom and convenience in creating data structures while using only mathematically simple control mechanisms of pattern matching and substitution.\nRefal also includes a feature called the freezer to support efficient [partial evaluation](https://bliptext.com/articles/partial-evaluation).\nRefal can be applied to the processing and transformation of tree structures, similarly to [XSLT](https://bliptext.com/articles/xslt).\n\n# Basics\nA Refal [Hello World](https://bliptext.com/articles/hello-world-program) example is shown below.\n$ENTRY Go { = ;}\nHello {\n= ;\n}\nThe program above includes two functions named Go and Hello.\nA function is written as the name of the function followed by the function body in curly braces.\nThe Go function is marked as the entry point of the program using the $ENTRY directive.\nOne could think of expressions in the function bodies as function \"calls\" in [Lisp](https://bliptext.com/articles/lisp-programming-language)-like syntax.\nFor example, the Hello function appears to call the built-in Prout function with the string 'Hello world' as the argument.\nThe meaning and the mechanism of the call, however, is quite different.\nTo illustrate the difference, consider the following function that determines whether a string is a [palindrome](https://bliptext.com/articles/palindrome).\nPal { = True;\ns.1 = True;\ns.1 e.2 s.1 = ;\ne.1 = False; }\nThis example shows a function with a more complex body, consisting of four sentences (clauses).\nA sentence begins with a pattern followed by an equal sign followed by a general expression on the right hand side.\nA sentence is terminated with a semicolon.\nFor example, the pattern of the second sentence of the function is \"s.1\" and the expression is \"True\".\nAs the example shows, patterns include pattern variables that have the form of a character identifying the type of the variable (what the variable matches) followed by the variable identifier.\nThe variables that begin with an \"s\" match a single symbol, those that begin with an \"e\" match an arbitrary expression.\nThe variable identifier can be an arbitrary alphanumeric sequence optionally separated from the type identifier by a dot.\nA function executes by comparing its argument with the patterns of its sentences in the order they appear in the definition, until the first pattern that matches.\nThe function then replaces the argument with the expression on the right hand side of the matched sentence.\nIf the result of a function application includes a subexpression in angle brackets (as it will after the third sentence of our example is applied), the result is further processed by Refal by invoking the function identified by the first symbol in the brackets.\nExecution stops when the result has no more angle brackets to expand in this way.\nThe function Pal can thus be read informally as: \"If the expression is empty, replace it with True. Otherwise if the expression is a single symbol, replace it with True. Otherwise if the expression is a symbol followed by an arbitrary expression e.2 followed by the same symbol, replace it with the expression . (In other words, throw away the two identical symbols at the beginning and the end and recurse). Otherwise replace the expression with False. (The pattern e.1 always matches).\"\nThe following are three step-by-step execution traces annotated with the sentence numbers applied at each step to produce the next\n (#3)\n (#3)\n (#1)\nTrue\n (#3)\n (#2)\nTrue\n (#3)\n (#3)\n (#3)\n (#4)\nFalse\nWe can now see that the Hello World example in fact executes as the sequence of the following expression transformations:\nSeed the machine with the initial expression marked by $ENTRY:\n (apply the sentence in Go)\n (apply the sentence in Hello)\n (Prout is a built-in that prints and expands to nothing)\n(nothing to apply; stop)\n\n# Other examples\n\n## Factorial\nFact { 0 = 1;\ns.N = >>; }\nHere 0 matches 0 the number and produces 1.\nOn any other symbol which is a number, multiply it with the result of (Fact (- s.N 1))\nNote the prefix style of operators.\n\n## Factorial with loops\nFact { s.n = ; };\nLoop {\n0 s.f = s.f; s.n s.f = >; }\nAs can be seen s.n acts as the loop counter.\n\n## Equality\nEqual {\n(e.1)(e.1) = T; (e.1)(e.2) = F; }\nHere the function is defined as, if given two terms, and the terms are same then the first clause matches and produces True.\nelse the second clause matches and produces False.\nAn important property of Refal is that all functions in refal are single argument.\n(But may be decomposed into terms in an expression as above.)\n\n## If\nDefining control structures is easy\nIf {\nT Then (e.1) Else (e.2) = e.1;\nF Then (e.1) Else (e.2) = e.2; }\nHere the e1 is evaluated only when the expression entered matches 'True' Then e1 Else e2 the same for e2.\n\n## Squeeze blanks\nSqueeze {\ne.1'__'e.2 = ;\ne.1 = e.1; }\n(Using '_' in place of space char so as to make the function call clear.)\nThe first clause matches whenever the function Squeeze encounters double\nblanks in its input expression, and replaces it with a single blank.\nThe second clause matches only when the first one did not, and returns the\nresultant value which is the current expression.\n\n## Squeeze using explicit looping\nSqueeze {\n'__'e.1 = ;\ns.A e.1 = s.A ;\n= ; };","revisionCount":0},"hasMore":false,"nextCursor":null}

History