· 7 years ago · Oct 15, 2018, 09:38 PM
1
2# fml
3
4## The function manipulation language
5
6"I just implemented Conway's Game of Life in two lines of code. #fml"
7
8 pad = x flip[stitch] 0, stitch 0, flip[cat] 0, cat 0
9 life = pad, neighborhoods[3 3], [ravel, [sum in?: [x @ 4, + 3; 3]]]/2
10
11 [0 1 0 1
12 0 1 1 0
13 0 0 1 0
14 0 0 0 0] replicate[life]-times[5]
15 ###
16 [0 1 0 1
17 0 1 1 0
18 0 0 1 0
19 0 0 0 0
20
21 0 1 0 0
22 0 1 0 1
23 0 1 1 0
24 0 0 0 0
25
26 0 0 1 0
27 1 1 0 0
28 0 1 1 0
29 0 0 0 0
30
31 0 1 0 0
32 1 0 0 0
33 1 1 1 0
34 0 0 0 0
35
36 0 0 0 0
37 1 0 1 0
38 1 1 0 0
39 0 1 0 0]
40 ###
41
42### Summary
43
44fml is an optimizing, function-oriented, array programming language. Unlike other array
45programming languages, it aims to have a less symbol-heavy but still concise
46syntax, and non-strict semantics that allow for high-level optimization.
47
48Note that fml is not:
49
50* meant for serious use
51* always faster than systems languages like C/C++/etc.
52* always more expressive than general-purpose languages like Python, Javascript, etc.
53* suitable for cryptography, real-time, or low-level applications that require fine
54 control of time and space complexity
55
56### License
57
58The fml implementation is licensed under an MIT-style license; see `LICENSE.txt` for
59details. This document and the other included fml documentation are in the public domain.
60
61### Syntax
62
63#### Character set
64
65fml source code is UTF-8 encoded Unicode text. On-disk source code should be
66pre-normalized to NFC form; an off-line interpreter or compiler may not normalize
67source code text by itself. The characters `[](){},.'":;#/` are reserved and used
68in fml's syntax. All printable, non-whitespace characters not reserved are free
69for making up identifiers. The characters `+-_` and digit characters have special
70meaning in numeric literals but may be also used in identifiers.
71
72#### Comments
73
74`#` begins a line comment that ends at the end of the line. A line beginning with `###`
75begins a block comment that ends at the next line identical to the starting line. `###`
76comments can envelop other lines beginning with `###` as long as those lines are followed
77by different text.
78
79 # This is a line comment
80
81 ###
82 This is a block comment
83 ###
84
85 ### LICENSE ###
86 (c) 2012 ORIGINAL LANGUAGE DO NOT STEAL
87 ### LICENSE ###
88
89 ###FIXME
90 ###
91 Add one to a value
92 ###
93 inc = x - 1
94 ###FIXME
95
96#### Brackets
97
98Bracketing characters are used for many purposes in fml. The matching pairs `[]`, `()`,
99`{}` may be used as brackets interchangeably, though they must match and nest correctly.
100
101 # These are all the same
102 [[1 + 2] - 3]
103 [(1 + 2) - 3]
104 ([1 + 2] - 3)
105 ({1 + 2} - 3)
106
107 # This is invalid
108 [(1 + 2] - 3}
109
110Anywhere in this document brackets or `[]` are mentioned, matching pairs of `()` and `{}`
111may be substituted.
112
113#### Literals
114
115##### Numbers
116
117A numeric literal begins with an optional `+` or `-` sign followed immediately by one
118or more digits. `.` marks a floating-point decimal point, and `/` marks a rational
119denominator.
120
121 123
122 +123
123 -123
124 1/3
125 +1/-3
126 1.01
127
128The prefixes `0x`, `0o`, and `0b` introduce hexadecimal, octal, and binary literals.
129
130 0xFFFF
131 0o755
132 0b10110111
133
134A decimal floating-point literal may include an exponent marked
135by `e`.
136
137 1.5e10
138 1.5e-10
139
140Hexadecimal and binary floating-point literals are supported; they must include
141a base-2 exponent marked by `p`.
142
143 -0x1.8p12 # (1 + 8/16) * (2 ^ 12)
144 0b1.1p-12 # (1 + 1/2) * (2 ^ -12)
145
146Complex floating-point literals are supported; the real and imaginary part
147are separated by a sign followed by `j`.
148
149 1+j0
150 0.707-j0.707
151
152`_` may be used freely within numeric literals for human readability; it
153does not affect the value of the literal.
154
155 1_000_000
156 1_00_00_000
157 0xFFFF_0000
158 0x1.8000_0000_0000_1p0
159
160fml tries to deduce an appropriate type for number literals, which is sufficient most
161of the time. An explicit type may be asked for with a type suffix:
162
163 1b # 1-bit/boolean 1 (note: cannot be used with 0x)
164 1o # 8-bit octet 1
165 1s # 16-bit short 1
166 1i # 32-bit int 1
167 1L # 64-bit long 1
168 1f # single-precision float 1
169 1F # double-precision float 1
170 1I # arbitrary-precision 1
171 1R # arbitrary-precision rational 1
172
173If `-`, `+`, or a digit does not begin a numeric literal, it is treated as an identifier
174character. Outside of numeric literals, `_` may also be used as an identifier character;
175`.` is used as the module path separator in identifiers; and `/` as the rank modifier.
176
177The special values infinity and NaN can be referred to as `1/0` and `0/0` respectively.
178
179##### Strings
180
181`'single quotes'` and `"double quotes"` may be used to delimit string
182literals. Two quotes in a row, `''` or `""`, escapes a
183quote character within a literal. The C-style escapes `\'`, `\"`, `\r`, `\n`, `\t` are
184also supported. An additional escape `\s` is provided for the space character.
185Combining characters may also be escaped with `\`. Unicode code points may be
186referenced by hexadecimal index with `\u012ABC`.
187
188 'What are you, a lawyer?'
189 'I always wanted to be in one of your fuckin'' plays.'
190 "Garçon!"
191 'Garc\̧on!'
192
193Strings with escaped combining characters are never normalized. `'e\Ì'` and `'é'` are
194different strings.
195
196String literals may span multiple lines. Single newlines within a string literal are
197combined with any adjacent whitespace into a single space character inside the literal.
198Blank lines in the string literal, along with any whitespace represented by escape
199sequences such as `\s` or `\n`, are preserved.
200
201 # No newlines in the string's value
202 "The secret, I don't know. I guess you just gotta find something you
203 love and then do it for the rest of your life. For me, it's going to
204 Rushmore."
205
206 # blank lines preserved in the string's value
207 '"I like your nurse''s uniform, guy."
208
209 "These are O.R. scrubs."
210
211 "O.R. they?"'
212
213Preformatted strings may be delimited with `''' '''` or `""" """`. Leading and trailing
214whitespace is stripped, along with any indentation whitespace up to the indentation
215level of the first non-whitespace character. Newlines (including the final newline
216before the closing `"""`, if any) and additional indentation are preserved. Within
217a triple-quoted string, `'` and `"` are literal, as is the one of `'''` or `"""` not
218used to delimit the string. Literal quotes may also be used at the end of the string;
219in a literal ending with more than three `"""`; the final three are taken as the
220delimiter.
221
222 # no ending newline; internal newlines preserved
223 # also note that final " is included inside string
224 """"She's my Rushmore, Max."
225 "I know. She was mine, too.""""
226
227 # newline at end preserved
228 '''
229 def factorial(n):
230 """and now for something completely different"""
231 fac = 1
232 if n > 2:
233 for i in xrange(2,n):
234 fac *= i
235 return fac
236 '''
237
238An escape sequence such as `\s` or `\n` can be used to represent significant
239space that will not be trimmed.
240
241 """
242 \s MR. BLUME
243
244 You guys have it real easy. I never had it like this
245 where I grew up. But I send my kids here. Because, the
246 fact is, whether you deserve it or not: you go to one
247 of the best schools in the country.
248
249 Max's eyes light up.
250
251 MR. BLUME
252
253 Rushmore. You lucked out.
254
255 Max leans forward to the railing and begins to listen intently.
256
257 MR. BLUME
258
259 Now, for some of you it doesn't matter. You were born
260 rich, and you're going to stay rich. But here's my
261 advice to the rest of you: take dead aim on the rich
262 boys. Get them in the crosshairs. And take them down.
263 """
264
265If a string literal appears in an expression by itself preceding a binding expression
266(using `=`, described below), the string becomes a docstring attached to the following
267binding.
268
269 """
270 Calculates the factorial of a positive integer X. Returns 1 for zero or
271 negative integers.
272 """
273 factorial = 2 to x, fold[*]
274
275##### Arrays
276
277Literal one-dimensional arrays, called lists, may be specified as series of literals
278separated by whitespace inside brackets.
279
280 [1 2 3]
281
282Multiple-code-point strings are lists of code points, so the following forms are
283equivalent.
284
285 'abc'
286 ['a' 'b' 'c']
287
288Literal two-dimensional arrays, called tables, may be specified as series of lists
289separated by newlines or semicolons. Table literals are interpreted in row-major
290order.
291
292 # 2x3 table
293 [1 2 3
294 2 4 6]
295
296 # Same
297 [1 2 3; 2 4 6]
298
299N-dimensional table literals may be specified with the major axes delimited by blank
300lines or repeated semicolons. The Nth dimension is delimited by N - 2 blank lines, or
301N - 1 semicolons.
302
303 # 2x3x3
304 [ 1 2 3
305 4 5 6
306 7 8 9
307
308 10 11 12
309 13 14 15
310 16 17 18]
311
312 # Same
313 [1 2 3; 4 5 6; 7 8 9;; 10 11 12; 13 14 15; 16 17 18]
314
315 # 2x2x2x2
316 [ 1 2
317 3 4
318
319 5 6
320 7 8
321
322
323 9 10
324 11 12
325
326 13 14
327 15 16]
328
329 # Same
330 [1 2; 3 4;; 5 6; 7 8;;; 9 10; 11 12;; 13 14; 15 16]
331
332To specify a type suffix for the elements of a numeric list, the suffix can be applied
333once to the last element of the list.
334
335 [0 1 0f] # list of single-precision floats
336 [0 1 0b] # list of bits
337
338The empty list is `[]`. The empty two-dimensional table is `[;]`, three-dimensional is
339`[;;]`, and so on.
340
341Note that brackets and `;` are also used for nesting expressions and list construction, described
342below. A bracketed expression is parsed as a literal if there is a single literal, newline, or `;`
343token inside the brackets, or if the first two tokens inside the brackets are literals, newlines,
344or `;`. The comma `,`, described below, can force expression parsing.
345
346 [1] # one-element list
347 [1 2] # two-element list
348 [1 A] # syntax error: invalid list literal; A isn't a literal
349 [1;2] # 2x1 table
350 [1;A] # syntax error: invalid table literal; A isn't a literal
351
352 [, 1] # ===> 1
353 [, 1; A] # ===> 1; A
354
355Array literals must be homogeneous and rectangular. Heterogeneous arrays or
356ragged arrays-of-arrays are supported but must be created using list construction
357expressions, described below.
358
359#### Identifiers
360
361Identifiers are used to name nouns (values) and verbs (functions). Identifiers may be
362made up of any non-whitespace, non-reserved characters, but may not begin with a
363digit or with `+` or `-` followed by a digit. Capitalized and lowercased identifiers have
364distinct syntactic roles. A capitalized identifier begins with an uppercase or title-case
365letter or the symbol `_`. A lowercased identifier begins with any non-uppercase,
366non-title-case character. Identifiers are separated by whitespace or by reserved
367characters; symbols can be intermixed with letters and digits and do not separate
368identifiers by themselves.
369
370 # Capitalized identifiers
371 X
372 X* # one identifier
373 Even?
374 _foo
375 _å™æ‚Ÿç©º
376
377 # Lowercased identifiers
378 sin
379 ro-sham-bo
380 exists?
381 +
382 -
383 **
384
385The token `=` is reserved as the binding operator; however, longer identifiers may
386include `=`.
387
388 ==
389 >=
390
391`/` is used as the rank modifier; however, it may also be used by itself as a lowercased
392identifier.
393
394 / # the identifier '/', used for the division function
395 foo/1 # 'foo' rank 1
396 //1 # '/' rank 1
397
398A trailing `:` is reserved for keyword syntax, but identifiers may include embedded
399`:`s.
400
401 if:else
402
403`.` is used to provide qualified module paths.
404
405 math.functions.sqrt
406 math.constants.Pi
407
408`.` by itself is also the "black hole" identifier used in binding patterns (see Binding,
409below). Directives, such as `.import`, are prefixed with `.`.
410
411#### Expressions
412
413Each line of fml source code is an expression. Newlines normally separate expressions,
414although indentation may be used to span expressions across lines.
415
416fml distinguishes values, functions, and higher-order functions syntactically. In the
417APL tradition these are referred to as "nouns", "verbs", and "adverbs" respectively.
418
419##### Nouns
420
421Nouns are values. Literals are nouns, as are the results of
422applying verbs. Noun variables are named by capitalized identifiers.
423
424 1
425 'two'
426 [3 4 5]
427
428 Pi = 3.14159
429
430##### Verbs
431
432Verbs are first-order functions; they take nouns as inputs and output new nouns.
433Verbs are named with lowercased identifiers. A unary verb is applied using postfix notation,
434and a binary or higher-arity verb is applied using infix notation; the verb being
435applied is the second expression in any case.
436
437 1 neg # apply unary 'neg' to 1 ===> -1
438 1 + 2 # apply binary '+' to 1 and 2 ===> 3
439 X? if:else 'yes' 'no' # apply ternary 'if:else' to X?, 'yes', 'no'
440
441Most verbs are pure functions; their output depends only on their inputs. If a verb name ends
442with `!`, it is impure and may read or write external state.
443
444 'Hello world!' print!
445 'foo.bin' read!, + 1, & 0xFF, write! 'foo+1.bin'
446
447A higher-arity verb may be given `.` as its right argument. It will then be given the
448left argument for all of its arguments.
449
450 4 + . # ===> 8
451 1 + 2, * . # ===> 9
452
453##### Nesting expressions
454
455Brackets `[]` and the comma `,` can be used to nest verb applications and
456other expressions. Brackets nest expressions, like parens in many programming languages.
457
458 [1 + 2] * 3 # ===> 9
459 1 + [2 * 3] # ===> 7
460 [2 neg] * 3 # ===> -6
461
462Note that a left bracket must be separated from a preceding verb by whitespace. Without
463whitespace it is parsed as an adverb (see below).
464
465 1 + [2 * 3] # brackets
466 [1 2 3] fold[+] # adverb
467
468A comma brackets from the beginning of the expression up to the comma, for
469left-associative composition.
470
471 1 + 2, neg # -3
472 1 neg, + 2 # 1
473 2 * 3, + 1 # 7
474 1 + 2, * 3 # 9
475 1 + 2, * 3, neg # -9
476
477A comma can be used at the beginning of an expression, where it has no effect.
478This can be used to disambiguate list literals from expression brackets. A single
479literal in brackets is parsed as a one-element list literal. Literals should
480never otherwise need to be bracketed by themselves, but if this is desired, an extra
481comma can be used to force parsing as expression brackets.
482
483 [1] # one-element list [1]
484 [, 1] # ===> 1
485
486##### Keyword verbs
487
488Higher-arity verbs may be applied using Smalltalk-esque keyword syntax.
489`X a: Y b: Z c: W` applies the verb `a:b:c` to the arguments `X`, `Y`, `Z`, and `W`.
490It generalizes for any number of keywords. The `:` must not be preceded by whitespace and
491must be followed by whitespace.
492
493 X? if: 'yes' else: 'no' # X? if:else 'yes' 'no'
494
495For arguments after the first two, a lone colon may be used as a separator without an
496identifier, preceded and followed by whitespace, as an argument separator.
497`X a: Y : Z : W` applies `a` to the arguments `X`, `Y`, and `Z`.
498
499 'hello-world.txt' create!: 0o644 : 'Hello world!'
500
501The first "keyword" can be a bracketed verb expression. The subsequent keyword
502names, if any, are ignored.
503
504 # A lambda expression; see "bindings" below
505 1 [X . Y Z = X * Y, + Z]: 2 : 3 # ===> 6
506 # same
507 1 [X . Y Z = X * Y, + Z]: 2 and: 3 # ===> 6
508
509Keyword application has lower precedence than non-keyword verb application and `,`.
510This can be taken advantage of to lower the precedence of a verb without brackets.
511
512 1 / 2 +: 2 * 3 # [1 / 2] + [2 * 3] ===> 13/2
513 1 / 2 +: 2 * 3, neg # [1 / 2] + [(2 * 3) neg] ===> -11/2
514
515##### Composing verbs
516
517Verbs can be applied to other verbs to yield new verbs that compose the input verbs.
518Composing two unary verbs, `uv1 uv2`, gives a unary verb that applies `uv1` to its input
519then `uv2` to the result. Composing a unary verb with a higher-arity verb, `uv bv`, gives a
520higher-arity verb that applies `uv` to each of its inputs then `bv` over the results. Composing a
521higher-arity verb with a unary verb the other way, `bv uv`, gives a higher-arity verb that
522applies `bv` over its inputs then `uv` to the result.
523
524 X [uv1 uv2] X [uv bv] Y X [bv uv] Y
525
526 X X Y X Y
527 | | | \ /
528 uv1 uv uv bv
529 | \ / |
530 uv2 bv uv
531
532 X uv1, uv2 [X uv] bv [Y uv] X bv Y, uv
533
534Composing two higher-arity functions is an error. However, "forks" can be composed using
535verbs of any arity. In a fork, R arity-B verbs are each applied over the inputs, and the
536results are used as the inputs to one arity-R root verb `rv` to give the result of the fork.
537
538 X [uv1 rv uv2] X [bv1 rv bv2] Y
539
540 X X X Y X Y
541 | | \ / \ /
542 uv1 uv2 bv1 bv2
543 \ / \ /
544 rv rv
545
546 [X uv1] rv [X uv2] [X bv1 Y] rv [X bv2 Y]
547
548A tine of a fork may also be a noun, which is used directly as the corresponding input for the
549root verb.
550
551 mersenne = ^ - 1 # X mersenne Y = [X ^ Y] - 1
552 2 mersenne 7 # ===> 127
553
554 # x is the identity function; X x == X
555 inc = x + 1
556 5 inc # ===> 6
557
558A fork may also be formed with `.` as its right side, to reuse the left-hand result for the
559rest of the root verb's arguments.
560
561 sq = x * .
562
563These composition rules allow many functions to be defined implicitly without explicit
564reference to arguments.
565
566 hypot = sq, +, sqrt # ===> X hypot Y = [X sq] + [Y sq], sqrt
567 mean = sum / length # ===> X mean = [X sum] / [X length]
568 variance = x - mean, sq, sum # ===> X variance = X - [X mean], sq, sum
569
570##### List construction
571
572Semicolons `;` collect the results of multiple expressions into a list. It has
573lower precedence than verb application, `,`, and keywords.
574
575 1 + 2, * 3; 1 +: 2 * 3; 1 + 2 # ===> [9 7 3]
576
577A list of same-arity verbs is itself a verb. When a verb list is applied, each verb in
578the list is applied to its argument(s) and the results are collected into a list. Nouns
579can be included in a verb list; they become values in the result of the verb.
580
581 5 [+;-;*;floor[/];0] 2 # ===> [7 3 10 2 0]
582
583Using `;` with equal-sized list or table elements builds a higher-rank table.
584
585 [1 2]; [3 4] # ===> [1 2; 3 4]
586 [1 2; 3 4]; [5 6; 7 8] # ===> [1 2; 3 4;; 5 6; 7 8]
587
588Using `;` with heterogeneous elements of different types or array sizes creates
589a heterogeneous list.
590
591 [1 2]; 3 # ===> [, [1 2]; 3]
592
593Higher-rank table constructions can be expressed using repeated `;`.
594
595 4 + 2; 4 - 2;; 4 * 2; 4 / 2 # ===> [6 2; 8 2]
596
597Note that brackets and `;` are also used as table literals; the first two tokens inside
598the brackets are used to differentiate: if there is a single literal, newline, or `;`
599token inside the brackets, or if the first two tokens inside the brackets are
600literals, newlines, or `;`, it is parsed as a literal. `,` or brackets can
601be used to force parsing as an expression if the first element is a literal.
602
603 [1; 2; 3] # 3x1 literal table
604 [1; A; 3] # syntax error; A isn't a literal
605
606 [A; 2; 3] # 3-element lists
607 [, 1; A; 3]
608 [, 1; 2; 3]
609
610##### Adverbs
611
612Adverbs are higher-order functions; they take one or more noun or verb arguments and yield
613a new noun or verb as a result. `adverb[arg]` applies an adverb; the left bracket must
614not be preceded by whitespace. The unapplied adverb is named with empty brackets, as in
615`adverb[]`. Adverbs that produce verbs are named by lowercased identifiers.
616
617 # 'flip[]' takes a binary verb and reverses its arguments
618 3 flip[-] 2 # ===> -1
619
620 # bind an alias to flip[]
621 flop[] = flip[]
622 3 flop[-] 2 # ===> -1
623
624 # 'fold[]' takes a binary verb and yields a unary verb applying the verb
625 # between all the elements of a list
626 [1 2 3] fold[+] # ===> 6
627
628 # 'case[]' applies one of a list of unary verbs to each element of its right argument
629 # selected by values from its left argument
630 [1 2 0] case[x + 1; x - 1; x * 2] [1 2 3] # ===> [0 4 2]
631
632Multiple-argument adverbs have the form `a[arg][arg]` or `a[arg]-b[arg]`, without
633whitespace between the brackets and identifiers.
634
635 # 'do[f]-while[g]' applies 'f' repeatedly while 'g' returns nonzero.
636
637 # Find the first Fibonacci number greater than 100
638 [1 1] do[x @ 1; fold(+)]-while[x @ 1, <= 100], @ 1 # ===> 144
639
640A partially-applied adverb can be referred to by leaving one or more of the argument
641brackets empty.
642
643 inc-while[] = do[x + 1]-while[]
644 while-odd[] = do[]-while[x % 2, != 0]
645
646 1.5 inc-while[x < 4] # ===> 4.5
647 39 while-odd[x floor[/] 2] # ===> 4
648
649Unapplied or partially applied adverbs may also be used in verb composition or fork
650expressions to give new adverbs. The unapplied parameters become parameters of the result
651adverb in source order.
652
653 foldsquares[] = sq fold[]
654 fold[]-minus[] = fold[] - fold[]
655
656 [1 2 3] foldsquares[+] # ===> 14
657 [2 3 4] fold[*]-minus[+] # ===> 24 - 9 ===> 15
658
659Adverbs may also be named and applied with keyword syntax. `X a[f]: Y b: Z c: W` applies
660the adverb `a[]:b:c` with the verb argument `f`, then applies the resulting verb
661to `X`, `Y`, `Z`, and `W`. Adverb arguments and keywords may be
662interspersed freely in the adverb name, for example, `X a[f]-b[g]: Y c: Z d[h]: W` applies
663`a[]-b[]:c:d[]`.
664
665Adverbs that produce nouns are named by capitalized identifiers. These can be used to
666query properties of verbs or nouns.
667
668 # 'Rank' yields the rank(s) of a verb
669 Rank[+] # ===> [0 0]
670 Rank[x] # ===> 1/0
671 Rank[is] # ===> [1/0 1/0]
672
673 # 'Name' yields the name of a verb as a string
674 Name[sqrt] # ===> 'sqrt'
675
676 # 'Help' yields the docstring for a verb or noun
677 Help[sqrt] # ===> 'Outputs the square root yadda yadda yadda'
678
679##### Bindings
680
681`=` binds variables. It has lower precedence than verb application, `,`, keywords, and `;`.
682
683 # Noun binding
684 Pi = 1 atan, * 4
685
686 # Verb binding
687 sq = x * x
688 hypot = sq, +, sqrt
689
690 # Adverb binding
691 flop[] = flip[]
692 inc-while[] = do[x + 1]-while[]
693
694The left-hand side may look like a list of identifiers to bind the destructured elements
695of a list. The special name `.` can be bound to discard a value.
696
697 One; Two; Three = [1 2 3]
698 One; .; Three = [1 2 3]
699
700The left-hand side may also look like a verb application to bind a verb with explicit
701named arguments. The argument names are lexically scoped to the right side of the binding.
702
703 # Explicit definitions of the above tacit bindings
704 X sq = X * X
705 X hypot Y = [X sq] + [Y sq], sqrt
706
707 # Define keyword verb pow:mod
708 Base pow: Exp mod: Mod = Base ^ Exp, % Mod
709
710Verb arguments may look like lists to destructure a list argument.
711
712 [A;B;C] quadratic = B neg, [+;-] [B sq, - [4 * A, * C], sqrt] /: 2 * A
713
714 [2 0 -8] quadratic # ===> [2 -2]
715
716The left-hand side may also look like an adverb application, to bind an adverb with
717explicit arguments. A verb-producing adverb may have explicit or implicit verb arguments.
718
719 # Noun-producing adverb
720 Arity[] = Rank[] length
721
722 # Noun-producing adverb, explicit adverb argument
723 Arity[f] = Rank[f] length
724
725 # Verb-producing adverb, implicit verb arguments
726 ofsquares[f] = sq f
727 3 ofsquares[+] 4 # ===> 25
728
729 # Verb-producing adverb, explicit verb arguments
730 X flip[f] Y = Y f X
731 3 flip[/] 1 # ===> 1/3
732
733Bindings are lexically scoped. A noun binding's scope begins from the line after the
734binding; a noun name may thus be rebound referencing the previous value bound to that name.
735
736 X = 1
737 X print! # prints: 1
738 X = X + 1
739 X print! # prints: 2
740
741Verb bindings are lexically scoped beginning from the binding itself, so that verbs may
742reference themselves recursively.
743
744 X factorial = X == 0 if: 1 else: X * [X - 1, factorial]
745
746If a verb or adverb definition uses impure verbs (named ending in `!`), the new verb or
747adverb must also be marked impure with a name ending in `!`. "Pure" adverbs may however
748be applied to impure verb arguments; `a[f!]` will result in an impure verb.
749
750 X spam! =
751 X print!
752 X spam!
753
754 show![f] = f print!
755
756 1 show![+] 2 # prints: 3
757
758 [1 2 3 4] case[(); print!] [1 0 1 0]
759
760Binding expressions self-evaluate to the bound value. A variable bound in a subexpression
761is lexically scoped to the line it appears in and can be used within the same expression.
762
763 X foo Y = [(X1 = X + 1) *: Y + 1] / [X1 *: Y - 1]
764
765Binding `.` as a verb with explicit arguments can thus be used as a lambda expression.
766
767 [1 2 3] case[(X . = X + 1); (X . = X - 1)] [0 1 0] # ===> [2 1 4]
768
769#### Indentation
770
771A binding `=` sign may be followed by an indent to introduce a multiline definition.
772All subsequent lines up to the matching outdent become part of the definition.
773The last line becomes the final value of the binding for a noun binding, or the result of a verb
774binding. Bindings within the definition are lexically scoped to the definition.
775
776 Pi =
777 Pi/4 = 1 atan
778 Pi/4 * 4
779
780 [A;B;C] quadratic =
781 D = B sq, - [4 * A, * C], sqrt
782 B neg, [+;-] D /: 2 * A
783
784 X totient =
785 Factors; Powers = X factor
786 Factors - 1, * [Factors ^: Powers - 1], product
787
788An indented definition is ended either by an outdent or by a closing bracket if the
789definition is inside of a bracketed expression.
790
791 X foo =
792 Bar # definition goes from here...
793 Bas
794 Zim
795 Zang # ...to here
796 Zung
797
798 2 [X bar Y =
799 Bar # indentation goes from here...
800 Bas
801 Zim] 3 + 4 bar 5 # ...to closing bracket
802
803Indentation after a non-`=` token acts as a line continuation.
804
805 'foo.bin' read!, sha256, print!
806
807 # equivalent
808 'foo.bin' read!,
809 sha256,
810 print!
811
812Multi-argument adverb applications may also be split over indented lines.
813
814 39 do[x floor[/] 2]-while[x % 2, != 0]
815
816 # equivalent
817 39 do[x floor[/] 2]
818 -while[x % 2, != 0]
819
820#### Directives
821
822Directives are special lines that have syntax and semantics of their own. Directives
823all start with a name of the form `.foo`; new directives may be added by future versions
824of the language.
825
826##### .import and .from
827
828The `.import <module>` directive imports a module into the current lexical scope.
829Bindings in the module can be referenced by qualified name.
830
831 .import math.constants
832 area = x * math.constants.Pi, ^ 2
833
834The `.from <module> import <names>` directive imports bindings from a module directly
835into the current lexical scope. `.from <module> import .` imports all exported bindings
836from `<module>` into the current scope.
837
838 .from math.constants import Pi, E
839 area = x sq, * Pi
840 polar = a * [E ^ [b * 0+j1]]
841
842##### .module
843
844The `.module <module> exports <names>` directive names a module, and lists the publicly
845exported names in the module. Without a `.module` directive a source file may not be
846imported as a module, and only exported names may be imported.
847
848 .module math.constants exports Pi, E
849
850 Pi = 3.14159
851 E = 2.71828
852
853### Semantics
854
855#### Execution order
856
857With few exceptions, fml is pure functional and referentially transparent. The
858implementation uses an execution planner (similar to the query planner used by many SQL
859databases), which may reorder, combine, or eliminate calculations, and copy or share storage among
860values as it sees fit. Computation is only guaranteed to occur if an externally-visible result
861depends on it. In this respect fml is similar to lazy languages such as Haskell. However,
862fml is not a true lazy language, because it also does not generally guarantee that
863unobserved computations will not be executed, so array computations that contain
864unused infinite-time or -space elements cannot be reliably expressed. However, branching
865computations will short-circuit; `X? if: Y else: Z` will not evaluate its Y argument if
866`X?` is all-zero or its `Z` argument if `X?` is all-nonzero. Recursive expressions with
867terminating cases may thus be safely expressed.
868
869Some verbs and adverbs are provided that act as hints to the execution planner. They do
870not change the result of the computation, but change how the planner arrives at the
871result and may thereby affect time and space complexity.
872
873##### Impure operations
874
875The primary exception to fml's purity is impure verbs, whose names must end with `!`.
876Impure verbs act as sequence points; they are guaranteed to be executed even if their
877outputs are discarded, and will execute relative to each other in source order. Within
878expressions, side-effecting arguments are executed depth-first, left-to-right.
879
880 . discard . = []
881 . f! . = 'F' print!
882
883 # print ABCDEF
884 . abcdef! =
885 'A' print!
886 'B' print! discard: 'C' print!
887 'D' print! f!: 'E' print!
888
889When an impure verb is applied over an array, it applies to cells in row-major order,
890least index to greatest index.
891
892 # print!/1 applies 'print!' to each rank-1 cell (see "Verb rank" below)
893 # This prints '[1 2 3]', then '[4 5 6]', then '[7 8 9]'
894 [1 2 3
895 4 5 6
896 7 8 9] print!/1
897
898#### Types
899
900fml supports the following scalar types:
901
902* Number types:
903 * 1-bit booleans
904 * 8-, 16-, 32-, and 64-bit signed integers
905 * 32-bit single-precision and 64-bit double-precision floating-point numbers,
906 in real, imaginary, and complex flavors
907 * Arbitrary-precision integers and rationals
908* The character type, representing a single Unicode code point. A character is represented
909 by a single-code-point string literal, such as `'x'` or `'é'`. Strings are just lists of
910 code points.
911* The pointer type, used to reference foreign resources. These do not have a literal
912 representation.
913
914Numeric calculations normally give the result type that best accurately contains the
915result. Integer results will be machine-word sized if possible (that is, 32-bit on 32
916bit hosts and 64-bit on 64-bit hosts), spilling into 64-bit or arbitrary precision if
917necessary. Results can be truncated into a smaller type by composing a bitwise-and or
918modulus operation onto the calculations. Results known to only be 0 or 1 will be reduced
919to boolean type.
920
921 10 ^ 0 # 1-bit
922 10 ^ 8 # a 32- or 64-bit result
923 10 ^ 100 # a bignum result
924 10 ^ 100, & 0xFF # an 8-bit result
925
926Irrational and transcendental operations such as `sqrt` will give approximate
927floating-point results even with arbitrary-precision inputs. The adverbs `floor`,
928`trunc` and `ceil` give accurate integer versions of many of these operations.
929
930 10 ^ 101, sqrt # a floating-point result
931 10 ^ 101, floor[sqrt] # a bignum result
932
933Floating-point results will be double-precision, unless all inputs are single-precision
934or the result is coerced to single-precision. For performance, fml takes algebraic
935liberties with floating-point calculations; strict floating-point conformance can be had
936with the `strictfp` adverb.
937
938 X sort[<], fold[+] # the sort may not affect the result in the
939 # intended way here; algebraically it's redundant
940 # and could be discarded
941
942 X sort[<], fold[strictfp(+)] # add up list least-to-greatest for best accuracy
943 # strictfp[+] isn't assumed to be associative so
944 # the sort is significant
945
946#### Arrays
947
948Scalars of the same type may be composed into arrays. One-dimensional arrays are also
949referred to as lists.
950
951 [1 2 3]
952
953Strings are arrays of characters.
954
955 'hello' is [ 'h' 'e' 'l' 'l' 'o' ] # ===> 1
956
957Heterogeneous arrays, including arrays of arrays, are supported; internally these arrays
958have an extra layer of indirection. They must be constructed explicitly using the `;`
959syntax. The printer will display these as a construction expression.
960
961 1; 'two'; [4 5 6] # ===> [, 1; 'two'; [4 5 6]]
962
963Rectangular multidimensional arrays are supported as well. The dimensionality of an
964array is referred to as its rank. A scalar has rank 0. A list has rank 1. An MxN table
965has rank 2, a MxNxO table rank 3, and so on.
966
967The in-memory representation of arrays is unspecified. The implementation may choose
968sparse or dense representations and arbitrary row-major, column-major, or
969locality-optimized tiled orderings as it sees fit. Impure verbs
970that read or write arrays to memory or disk will specify the ordering in
971which they read or write data.
972
973#### Verb rank
974
975Every verb also has a rank, which determines the rank of the values the verb operates on,
976and how the verb generalizes when applied to higher-rank values. Verbs cut their inputs
977up into "cells" of the appropriate rank. For example, a verb of
978rank 2 will operate once over the entirety of a rank-2 table, or over every rank-2 cell
979of a 3-or-higher dimensional table. The results of a higher-rank computation are collected
980into a new result list.
981
982 # rank 2 determinant
983 [A;B;;C;D] det = [A * B] - [C * D]
984 Rank[det] # ===> 2
985
986 [1 0; 0 1] det # ===> 1
987
988 [1 0; 0 1;; 2 0; 0 2;; 3 2; 2 3] det
989 # ===> [1 4 5]
990
991Higher-arity verbs require agreement in the dimensions of their arguments; the arguments
992must have a common prefix among their dimensions.
993For instance, applying a rank-0 verb to two 3-element lists will apply
994the verb to each corresponding pair of elements, and applying it between a 3-element list
995and a 3x3 table will pair each element of the list with each row of the table.
996
997 X = [1 2 3]
998 Y = [10 20 30]
999 X + Y # Apply + to each corresponding pair of elements in X and Y
1000 # ===> [11 22 33]
1001
1002 X + 1 # Apply + to 1 and each element of X
1003 # ===> [2 3 4]
1004
1005 Z = [ 10 20 30
1006 100 200 300
1007 1000 2000 3000]
1008 X + Z # Apply + to each element of X and the corresponding row in Z
1009 # ===> [ 11 21 31
1010 # 102 202 302
1011 # 1003 2003 3003]
1012
1013Higher-arity verbs may have different ranks for each argument. For instance, a binary verb
1014with left rank M and right rank N will apply each rank-M cell of its left argument to the
1015corresponding rank-N cell of the right.
1016
1017 # rank 2 determinant + rank 0 scalar
1018 M det+ N = M det, + N
1019
1020 Rank[det+] # ===> 2 0
1021 [1 0; 0 1] det+ 2 # ===> 3
1022 [1 0; 0 1] det+ [2 3; 4 5] # ===> [3 4; 5 6]
1023 [1 0; 0 1;; 2 0; 0 2;; 3 2; 2 3] det+ [2 3 4]
1024 # ===> [3 7 9]
1025
1026A verb may have infinite rank, in which case it always operates on the entirety of its
1027input, or negative rank, in which case it operates on `ArgumentRank + VerbRank`-rank
1028cells of its argument. For instance, the `is` verb, which compares entire values for
1029equivalence, has infinite rank in both arguments, whereas `==` has rank 0 and compares
1030elementwise.
1031
1032 Rank[==] # ===> 0 0
1033 Rank[is] # ===> 1/0 1/0
1034
1035 [1 2 3] is [1 2 3] # ===> 1
1036 [1 2 3] is [1 2 4] # ===> 0
1037 [1 2 3] is [1 1 1
1038 2 2 2
1039 3 3 3] # ===> 0
1040
1041 [1 2 3] == [1 2 3] # ===> [1 1 1]
1042 [1 2 3] == [1 2 4] # ===> [1 1 0]
1043 [1 2 3] == [1 1 1
1044 2 2 2
1045 3 3 3] # ===> [1 1 1; 1 1 1; 1 1 1]
1046
1047The rank of a verb may be modified. `verb/N` produces a variant
1048of `verb` that operates on `N`-cells of its argument(s); if `N` is a list, each
1049element of `N` specifies the rank of the cells for the corresponding argument.
1050For instance, `*` can be modified to apply each element of its right argument to its
1051entire left argument as follows:
1052
1053 [1 2 3 4] */[1/0 0] . # ===> [ 1 2 3 4
1054 # 2 4 6 8
1055 # 3 6 9 12
1056 # 4 8 12 16]
1057
1058The order in which pure verbs are applied to cells is unspecified. Impure verbs are
1059applied to cells in row-major order, least index to greatest.
1060
1061### Errata
1062
1063* Are non-strict, non-lazy semantics too slushy? "Lazy" and "strict" verb modifiers?
1064 Additional order-of-operations guarantees needed besides `if:else` shortcircuiting?
1065* Maybe too many weird rules for when whitespace between tokens is significant and when
1066 certain characters have meaning in identifiers
1067* Overloading `[;]` for list literals, parens, and list construction is goofy
1068* Shorthand for common HOFs like flip, fold?
1069* `,` for nesting and `;` for lists is a bit hard to read without syntax highlighting
1070 because `,` and `;` both visually register below the baseline. At a glance, how many
1071 elements in the list `1 + 2, * 3; 4 * 5, sqrt, floor`?
1072* `,` looks alright with named verbs, like `X foo, bar Y, bas`, but looks a bit noisy
1073 with math symbols like `X + Y, * Z`. `X + Y * Z` also syntactically tries to create
1074 a fork, and requires semantic knowledge of `+` to catch the error
1075* Would the relative precedence of keywords and `,` be better with `,` lower?
1076* Finer-grained effect types than pure/impure?
1077* What is a module?
1078* Construct to run impure code in a pure context, such as `log` or `observe`?
1079* Lists inside adverb brackets? `foo[1 2 3]`
1080* Some national keyboard layouts lack `#`, also it's a shifted character, so it violates
1081 the "no shifted symbols; no US-only symbols" rules