1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
<head><link href="style.css" rel="stylesheet"/></head>
<h1 id="functional-programming">Functional programming</h1>
<p>BQN boasts of its functional capabilities, including first-class functions. What sort of functional support does it have, and how can a BQN programmer exercise these and out themself as a Schemer at heart?</p>
<p>First, let's be clear about what the terms we're using mean. A language has <em>first-class functions</em> when functions (however they are defined) can be used in all the same ways as "ordinary" values like numbers and so on, such as being passed as an argument or placed in a list. Lisp and JavaScript have first-class functions, C has unsafe first-class functions via function pointers, and Java and APL don't have them as functions can't be placed in lists or used as arguments. This doesn't mean every operation is supported on functions: for instance, numbers can be added, compared, and sorted; while functions could perhaps be added to give a train, comparing or sorting them as functions (not representations) isn't computable, and BQN doesn't support any of the three operations when passing functions as arguments.</p>
<p>Traditionally APL has worked around its lack of first-class functions with operators or second-order functions. Arrays in APL are first class while functions are second class and operators are third class, and each class can act on the ones before it. However, the three-tier system has some obvious limitations that we'll discuss, and BQN removes these by making every type first class.</p>
<p>The term <em>functional programming</em> is more contentious, and has many meanings some of which can be vague. Here I use it for what might be called <em>first-class functional programming</em>, programming that makes significant use of first-class functions; in this usage, Scheme is probably the archetypal functional programming language. However, two other definitions are also worth mentioning. APL is often called a functional programming language on the grounds that functions can be assigned and manipulated, and called recursively, all characteristics it shares with Lisp. I prefer the term <em>function-level programming</em> for this usage. A newer usage, which I call <em>pure functional programming</em>, restricts the term "function" to mathematical functions, which have no side effects, so that functional programming is programming with no side effects, often using monads to accumulate effects as part of arguments and results instead. Finally, <em>typed functional programming</em> is closely associated with pure functional programming and refers to statically-typed functional languages such as Haskell, F#, and Idris (the last of which even supports <em>dependently-typed functional programming</em>, but I already said "finally" so we'll stop there). Of these, BQN supports first-class functional and function-level programming, allows but doesn't encourage pure functional programming, and does not support typed functional programming, as it is dynamically and not statically typed.</p>
<p>Another topic we are interested in is <em>lexical scoping</em> and <em>closures</em>. Lexical scoping means that the realm in which a variable exists is determined by its containing context (in BQN, the surrounding set of curly braces <code><span class='Brace'>{}</span></code>, if any) within the source code. A closure is really an implementation mechanism, but it's often used to refer to a property of lexical scoping that appears when functions defined in a particular block can be accessed after the block finishes execution. For example, they might be returned from a function or assigned to a variable outside of that function's scope. In this case the functions can still access variables in the original scope. I consider this property to be a requirement for a correct lexical scoping implementation, but it's traditionally not a part of APL: implementation might not have lexical scoping (for example, J and I believe A+ use static scoping where functions can't access variables in containing scopes) or might cut off the scope once execution ends, leading to value errors that one wouldn't predict from the rules of lexical scoping.</p>
<h2 id="functions-in-apl">Functions in APL</h2>
<p>This seems like a good place for a brief and entirely optional discussion of how APL handles functions and why it does it this way. As mentioned above, APL's functions are second class rather than first class. However, it's worth noting that the barriers to making functions first-class objects have been entirely syntactic and conceptual, not technical. In fact, the J language has for a long time had <a href="http://www.jsoftware.com/pipermail/programming/2013-January/031260.html">a bug</a> that allows an array containing a function to be created: by selecting from the array, the function itself can even be passed through tacit functions as an argument!</p>
<p>The primary reason why APL doesn't allow functions to be passed as arguments is probably syntax: in particular, there's no way to say that a function should be used as the left argument to another function, as an expression like <code><span class='Function'>F</span> <span class='Function'>G</span> <span class='Value'>x</span></code> with functions <code><span class='Function'>F</span></code> and <code><span class='Function'>G</span></code> and an array <code><span class='Value'>x</span></code> will simply be evaluated as two monadic function applications. However, there's no syntactic rule that prevents a function from returning a function, and Dyalog APL for example allows this (so <code><span class='Value'>⍎</span><span class='String'>'+'</span></code> returns the function <code><span class='Function'>+</span></code>). Dyalog's <code><span class='Value'>⎕</span><span class='Function'>OR</span></code> is another interesting phenomenon in this context: it creates an array from a function or operator, which can then be used as an element or argument like any array. The mechanism is essentially the same as BQN's first class functions, and in fact <code><span class='Value'>⎕</span><span class='Function'>OR</span></code>s even share a form of BQN's <a href="../problems.md#syntactic-type-erasure">syntactic type erasure</a>, as a <code><span class='Value'>⎕</span><span class='Function'>OR</span></code> of a function passed as an operand magically becomes a function again. But outside of this property, it's cumbersome and slow to convert functions to and from <code><span class='Value'>⎕</span><span class='Function'>OR</span></code>s, so they don't work very well as a first-class function mechanism.</p>
<p>Another reason for APL's reluctance to adopt first-class functions is that Iverson and others seemed to believe that functions fundamentally are not a kind of data, because it's impossible to uniquely represent, compare, and order them. One effect of this viewpoint is J's gerund mechanism, which converts a function to an array representation, primarily so that lists of gerunds can be created. Gerunds are nested arrays containing character vectors at the leaves, so they are arrays as Iverson thought of them. However, I consider this conversion of functions to arrays, intended to avoid arrays that contain "black box" functions, to be a mistake: while it doesn't compromise the purity of arrays, it gives the illusion that a function corresponds to a particular array, which is not true from the mathematical perspective of functions as mappings from an arbitrary input to an output. I also think the experience of countless languages with first-class functions shows that there is no practical issue with arrays that contain functions. While having all arrays be concrete entities with a unique canonical representation seems desirable, I don't find the existence of arrays without this property to be detract from working with arrays that do have it.</p>
<h2 id="functional-programming-in-bqn">Functional programming in BQN</h2>
<p><em>Reminder: I am discussing only first-class functional programming here, and not other concepts like pure or typed functional programming!</em></p>
<p>What does functional programming in BQN look like? How is it different from the typical APL style of manipulating functions with operators?</p>
<h3 id="working-with-roles">Working with roles</h3>
<p>First, let's look at the basics: a small program that takes a function as its argument and result. The function <code><span class='Function'>Lin</span></code> below gives a linear approximation to its function argument based on the values at 0 and 1. To find these two values, we call the argument as a function by using its uppercase spelling, <code><span class='Function'>𝕏</span></code>.</p>
<pre><span class='Function'>Lin</span> <span class='Gets'>←</span> <span class='Brace'>{</span>
<span class='Value'>v0</span> <span class='Gets'>←</span> <span class='Function'>𝕏</span> <span class='Number'>0</span>
<span class='Value'>v0</span> <span class='Function'>+</span> <span class='Paren'>((</span><span class='Function'>𝕏</span> <span class='Number'>1</span><span class='Paren'>)</span> <span class='Function'>-</span> <span class='Value'>v0</span><span class='Paren'>)</span> <span class='Function'>×</span> <span class='Function'>⊢</span>
<span class='Brace'>}</span>
</pre>
<p>We can pass it the exponential function as an argument by giving it the name <code><span class='Function'>Exp</span></code> and then referring to it in lowercase (that is, in a value role). The result is a train that adds 1 to <em>e</em>-1 times the argument.</p>
<pre> <span class='Function'>Exp</span> <span class='Gets'>←</span> <span class='Function'>⋆</span>
<span class='Function'>Lin</span> <span class='Value'>exp</span>
<span class='Paren'>(</span><span class='Number'>1</span> <span class='Function'>+</span> <span class='Paren'>(</span><span class='Number'>1.71828182845905</span> <span class='Function'>×</span> <span class='Function'>⊢</span><span class='Paren'>))</span>
</pre>
<p>As with all functions, the result of <code><span class='Function'>Lin</span></code> has a value role. To use it as a function, we give it a name and then use that name with an uppercase spelling.</p>
<pre> <span class='Value'>expLin</span> <span class='Gets'>←</span> <span class='Function'>Lin</span> <span class='Value'>exp</span>
<span class='Function'>ExpLin</span> <span class='Number'>5</span>
<span class='Number'>9.59140914229523</span>
</pre>
<p>A tricker but more compact method is to use the modifier <code><span class='Brace'>{</span><span class='Function'>𝔽</span><span class='Brace'>}</span></code>, as the input to a modifier can have a value or function role but its output always has a function role.</p>
<pre> <span class='Paren'>(</span><span class='Function'>Lin</span> <span class='Value'>exp</span><span class='Paren'>)</span><span class='Brace'>{</span><span class='Function'>𝔽</span><span class='Brace'>}</span> <span class='Number'>5</span>
<span class='Number'>9.59140914229523</span>
</pre>
<p>Not the most accurate approximation, though.</p>
<pre> <span class='Function'>Exp</span> <span class='Number'>5</span>
<span class='Number'>148.413159102577</span>
</pre>
<p>Note also in this case that we could have used a modifier with a very similar definition to <code><span class='Function'>Lin</span></code>. The modifier is identical in definition except that <code><span class='Function'>𝕏</span></code> is replaced with <code><span class='Function'>𝔽</span></code>.</p>
<pre><span class='Modifier'>_lin</span> <span class='Gets'>↩</span> <span class='Brace'>{</span>
<span class='Value'>v0</span> <span class='Gets'>←</span> <span class='Function'>𝔽</span> <span class='Number'>0</span>
<span class='Value'>v0</span> <span class='Function'>+</span> <span class='Paren'>((</span><span class='Function'>𝔽</span> <span class='Number'>1</span><span class='Paren'>)</span> <span class='Function'>-</span> <span class='Value'>v0</span><span class='Paren'>)</span> <span class='Function'>×</span> <span class='Function'>⊢</span>
<span class='Brace'>}</span>
</pre>
<p>Its call syntax is simpler as well. In other cases, however, the function version might be preferable, for example when dealing with arrays of functions or many arguments including a function.</p>
<pre> <span class='Function'>Exp</span> <span class='Modifier'>_lin</span> <span class='Number'>5</span>
<span class='Number'>9.59140914229523</span>
</pre>
<h3 id="arrays-of-functions">Arrays of functions</h3>
<p>It's very convenient to put a function in an array, which is fortunate because this is one of the most important uses of functions as values. Here's an example of an array of functions with a reduction applied to it, composing them together.</p>
<pre> <span class='Brace'>{</span><span class='Function'>𝕎</span><span class='Composition'>∘</span><span class='Function'>𝕏</span><span class='Brace'>}</span><span class='Modifier'>´</span> <span class='Function'>⋆</span><span class='Ligature'>‿</span><span class='Function'>-</span><span class='Ligature'>‿</span><span class='Paren'>(</span><span class='Function'>×</span><span class='Modifier'>˜</span><span class='Paren'>)</span>
<span class='Function'>⋆</span><span class='Composition'>∘</span><span class='Paren'>(</span><span class='Function'>-</span><span class='Composition'>∘</span><span class='Paren'>(</span><span class='Function'>×</span><span class='Modifier'>˜</span><span class='Paren'>))</span>
</pre>
<p>Like any function, this one can be given a name and then called. A quirk of this way of defining a function is that it has a value role (it's the result of the function <code><span class='Brace'>{</span><span class='Function'>𝕎</span><span class='Composition'>∘</span><span class='Function'>𝕏</span><span class='Brace'>}</span><span class='Modifier'>´</span></code>) and so must be defined with a lowercase name.</p>
<pre> <span class='Value'>gauss</span> <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Function'>𝕎</span><span class='Composition'>∘</span><span class='Function'>𝕏</span><span class='Brace'>}</span><span class='Modifier'>´</span> <span class='Function'>⋆</span><span class='Ligature'>‿</span><span class='Function'>-</span><span class='Ligature'>‿</span><span class='Paren'>(</span><span class='Function'>×</span><span class='Modifier'>˜</span><span class='Paren'>)</span>
<span class='Function'>Gauss</span> <span class='Number'>2</span>
<span class='Number'>0.0183156388887342</span>
</pre>
<p>Another, and probably more common, use of arrays of functions is to apply several different functions to one or more arguments. Here we apply three different functions to the number 9:</p>
<pre> <span class='Bracket'>⟨</span><span class='Function'>√</span><span class='Separator'>,</span> <span class='Number'>2</span><span class='Composition'>⊸</span><span class='Function'>∾</span><span class='Separator'>,</span> <span class='Function'>⊢-⋆</span><span class='Bracket'>⟩</span> <span class='Brace'>{</span><span class='Function'>𝕎</span><span class='Value'>𝕩</span><span class='Brace'>}</span><span class='Modifier'>¨</span> <span class='Number'>9</span>
<span class='Value'>[</span> <span class='Number'>3</span> <span class='Value'>[</span> <span class='Number'>2</span> <span class='Number'>9</span> <span class='Value'>]</span> <span class='Number'>¯8094.083927575384</span> <span class='Value'>]</span>
</pre>
<p>The composition Choose (<code><span class='Composition'>◶</span></code>) relies on arrays of functions to… function. It's very closely related to Pick <code><span class='Function'>⊑</span></code>, and in fact when the left operand and the elements of the right operand are all value types there's no real difference: Choose returns the constant function <code><span class='Value'>𝕗</span><span class='Function'>⊑</span><span class='Value'>𝕘</span></code>.</p>
<pre> <span class='Number'>2</span><span class='Composition'>◶</span><span class='String'>"abcdef"</span> <span class='String'>"arg"</span>
<span class='Value'>c</span>
</pre>
<p>When the operands contain functions, however, the potential of Choose as a ternary-or-more operator opens up. Here's a function for a step in the Collatz sequence, which halves an even input but multiplies an odd input by 3 and adds 1. To get the sequence for a number, we can apply the same function many times. It's an open problem whether the sequence always ends with the repetition 4, 2, 1, but it can take a surprisingly long time to get there—try 27 as an argument.</p>
<pre> <span class='Paren'>(</span><span class='Number'>2</span><span class='Composition'>⊸</span><span class='Function'>|</span><span class='Paren'>)</span><span class='Composition'>◶</span><span class='Bracket'>⟨</span><span class='Function'>÷</span><span class='Composition'>⟜</span><span class='Number'>2</span><span class='Separator'>,</span><span class='Number'>1</span><span class='Function'>+</span><span class='Number'>3</span><span class='Function'>×⊢</span><span class='Bracket'>⟩</span><span class='Modifier'>¨</span> <span class='Number'>6</span><span class='Ligature'>‿</span><span class='Number'>7</span>
<span class='Value'>[</span> <span class='Number'>3</span> <span class='Number'>22</span> <span class='Value'>]</span>
<span class='Paren'>(</span><span class='Number'>2</span><span class='Composition'>⊸</span><span class='Function'>|</span><span class='Paren'>)</span><span class='Composition'>◶</span><span class='Bracket'>⟨</span><span class='Function'>÷</span><span class='Composition'>⟜</span><span class='Number'>2</span><span class='Separator'>,</span><span class='Number'>1</span><span class='Function'>+</span><span class='Number'>3</span><span class='Function'>×⊢</span><span class='Bracket'>⟩</span><span class='Composition'>⍟</span><span class='Paren'>(</span><span class='Function'>↕</span><span class='Number'>10</span><span class='Paren'>)</span> <span class='Number'>6</span>
<span class='Value'>[</span> <span class='Number'>6</span> <span class='Number'>3</span> <span class='Number'>10</span> <span class='Number'>5</span> <span class='Number'>16</span> <span class='Number'>8</span> <span class='Number'>4</span> <span class='Number'>2</span> <span class='Number'>1</span> <span class='Number'>4</span> <span class='Value'>]</span>
</pre>
|
