/ README.rst
README.rst
1 ================================================================================ 2 Concatenative Calculus Evaluator 3 ================================================================================ 4 5 6 An online tool for playing with concatenative calculus. Supports defining your 7 own base operators as well as chosing from several presets, and evaluating 8 expressions using those operators. In the future it is planned to add support 9 for defining words as reusable code snippets. 10 11 It's currently hosted on `my homepage`_. 12 13 .. _my homepage: https://olus2000.pl/concat_eval 14 15 16 Concantenative calculus overview 17 ================================ 18 19 For the purpose of this tool CC (concatenative calculus) is a pattern 20 substitution based evaluation scheme. Given a set of rules (operators) it will 21 repeatedly find the first occurence of a rule and perform a matching 22 substitution. 23 24 25 Expressions 26 ----------- 27 28 A CC expression consists of words, some of which can correspond to operators, 29 and bracketed subexpressions. Any string of non-whitespace characters is a valid 30 word, other than brackets. Any string of whitespace-separated words with 31 balanced brackets is a valid expression. Expressions in brackets are called 32 quotations or quotes. 33 34 This tool additionally restricts the word ``--`` for future use. 35 36 37 .. _Operators: 38 39 Operators 40 --------- 41 42 Substitution rules in CC consist of a pattern and a substitution. Patterns 43 always have the form of some number of quotes followed by the operator word. 44 They capture contents of the argument quotes for use in the substitution. The 45 substitution can be any valid expression, but it can only use words referencing 46 the captured arguments. 47 48 In this tool you can adjust the number of arguments of an operator using the 49 ``+-`` buttons, set its name, and provide a substitution using numbers to 50 reference captured arguments. For example this pattern represents an operator 51 that duplicates a quotation:: 52 53 [ 1 ] dup -> [ 1 ] [ 1 ] 54 55 56 Words 57 ----- 58 59 You may see that some code snippets are used often in bigger expressions. You 60 can name the snippets, and whenever the evaluator encounters them it will 61 replace them with their definition. 62 63 In standard CC words either don't exist or can only have non-recursive 64 definitions. Concat Eval doesn't check for recursion in definitions though, so 65 you are free to experiment outside the classical rules. 66 67 68 Numbers 69 ------- 70 71 As in many math-level computer science settings you can define natural numbers 72 as functions that do something N times with their argument. In this tool it's 73 done by defining an expression representing zero, and a successor expression 74 representing a function that increments a number. If you define both then 75 natural numbers in expressions will be replaced with a zero expression followed 76 by an appropriate number of successor expressions. 77 78 79 Comments 80 -------- 81 82 Just looking at CC expressions often doesn't easily convey what the expression 83 does, especially if it uses few words and many operators. You can put text in 84 parenthesis ``( )`` to help anyone who reads it understand its purpose. Comments 85 can be nested in one another and span multiple lines, but both parenthesis must 86 be separated from surrounding text with spaces! You can use comments in word and 87 number definitions and in the main expression. 88 89 90 The stack 91 --------- 92 93 Another way to think about CC is in terms of operators working with a stack of 94 quotations. Evaluating the expression from left to right quotations are put on 95 the stack, and whenever an operator is encountered it's performs some operation 96 on the top values of the stack. 97 98 99 Functionality 100 ============= 101 102 Operators can be created using the ``Add operator`` row, edited using their 103 interface and deleted using the trash icon. For the meaning of operator 104 interface see Operators_. Operators with errors will not be included in 105 evalutation. 106 107 Similar interface exists for word definitions. 108 109 You can toggle the replacement of numbers with zero-successor expressions using 110 the checkboxes. The replacement will not occur if the appropriate expression has 111 an error. 112 113 Help button links to this file or a halp page if I make it. 114 115 The blue buttons under the title will set the operators to one of preset bases 116 and allow `importing and exporting`_ presets as text files. 117 118 After you enter the expression into the textbox at the bottom and resolve any 119 errors you can step through its evaluation using the buttons below the textbox. 120 You can set the step size and then do that many steps forward or backward, or 121 five times that many steps forward or backward. 122 123 124 .. _importing and exporting: `Import/Export format`_ 125 126 127 Import/Export format 128 ==================== 129 130 Just like the application UI an exported file consists of four parts: operators, 131 numbers, words and an expression. Sections are separated by two newline 132 characters, which usually correspond to one empty line. However if a section is 133 empty it should still be separated by two newlines from other sections, which 134 will correspond to three or more empty lines. Examples of the format can be seen 135 in the examples_ folder. 136 137 138 .. _examples: ./examples/ 139 140 141 Operators 142 --------- 143 144 Operator definitions are placed in separate consecutive lines. Each operator 145 requires defining its arity (how many argument it has), name and definition. For 146 example this is how operators for the minimal base are defined:: 147 148 2 cake [ [ 2 ] 1 ] [ 1 [ 2 ] ] 149 1 k 1 150 151 152 Numbers 153 ------- 154 155 The numbers section includes definitions of Zero and Successor in its first two 156 lines, in that order. Any additional lines will be ignored. For example this is 157 how numbers are defined for the default operator base:: 158 159 [ drop ] 160 [ dup quote cat call ] swap cat 161 162 163 Words 164 ----- 165 166 Definitions of words are placed in separate consecutive lines, just like 167 operators. Each line consists of the name of a word and its definition. For 168 example these are representations of some of the default words:: 169 170 take ( [A] [B] -- [B[A]] ) swap quote cat 171 dip ( [A] [B] -- B [A] ) take call 172 cons ( [A] [B] -- [[A]B] ) swap quote swap cat 173 174 Note that the comments (in parenthesis) in this example are a part of word 175 definitions and are not required by the format. 176 177 178 Expression 179 ---------- 180 181 The rest of the file contains a concatenative calculus expression without any 182 restrictions on its format. 183 184 185 Compilation 186 =========== 187 188 To compile the application to runnable javascript you will need Elm_. After 189 installing Elm run the following command in the project root:: 190 191 elm make src/Main.elm --output main.js 192 193 This should compile the file ``main.js`` which is referenced by ``index.html``, 194 and ``index.html`` should now display the application when opened with a 195 browser. 196 197 .. _Elm: https://guide.elm-lang.org/install/elm.html 198 199 200 Factor runner 201 ============= 202 203 Concatenative evaluator functionality is also available as a runner written in 204 Factor. It works with files written in concat eval export syntax and evaluates 205 the expressions in the files for a given amount of steps. You can execute the 206 runner with Factor:: 207 208 factor runner/runner.factor [limit] script 209 210 Or place this repo in your Factor work folder and 211 ``"concat-evaluator.runner" deploy`` to compile it into a standalone executable. 212 213 214 Credits 215 ======= 216 217 This software has been created by `Aleksander "olus2000" Sabak`_ in 2023 and 218 released under the `GPL v3 license`_. Thanks to the QWD community for help! 219 220 .. _Aleksander "olus2000" Sabak: https://github.com/olus2000 221 .. _GPL v3 license: ./LICENSE 222 .. QWD community: https://qwd.software QWD.software is no more :(