Programming/Kdb/Factorial - Revision history

Admin at 22:12, 21 December 2021

2021-12-21T22:12:13Z

← Older revision		Revision as of 22:12, 21 December 2021
Line 244:		Line 244:
	* returns a function as its result.		* returns a function as its result.

	This is what Jeffry A. Borror says about iterators in ~~<span class="plainlinks">~~[https://code.kx.com/q4m3/ Q for Mortals]~~</span>~~:		This is what Jeffry A. Borror says about iterators in [https://code.kx.com/q4m3/ Q for Mortals]:
	<blockquote>		<blockquote>
	If you are new to functional programming, you my think, "Big deal, I write <tt>for</tt> loops in my sleep." Granted. But the advantage of the higher-order function approach is that there is no chance of being off by one in the loop counter or accidentally running off the end of a data structure. More importantly, you can focus on ''what'' you want done without the irrelevant scaffolding of ''how'' to set up control structures. This is called '''declarative programming'''.		If you are new to functional programming, you my think, "Big deal, I write <tt>for</tt> loops in my sleep." Granted. But the advantage of the higher-order function approach is that there is no chance of being off by one in the loop counter or accidentally running off the end of a data structure. More importantly, you can focus on ''what'' you want done without the irrelevant scaffolding of ''how'' to set up control structures. This is called '''declarative programming'''.

Admin at 07:42, 1 July 2021

2021-07-01T07:42:01Z

@@ Line 278: / Line 278: @@
 </pre>
-==Assessing the performance of our implementations==
+=Assessing the performance of our implementations=
 Let us list all of our implementations of the factorial:
@@ Line 312: / Line 312: @@
 Unsurprisingly, <tt>fact6</tt> emerges as a leader, followed closely by <tt>fact5</tt>. We can see that there is a performance reason for preferring iterators over loops, in addition to the previously stated observation that iterators are more idiomatic that loops. However, the fastest results are obtained by using an optimized function, <tt>prd</tt>, written in low-level C.

Admin at 07:32, 1 July 2021

2021-07-01T07:32:12Z

← Older revision		Revision as of 07:32, 1 July 2021
Line 248:		Line 248:
	If you are new to functional programming, you my think, "Big deal, I write <tt>for</tt> loops in my sleep." Granted. But the advantage of the higher-order function approach is that there is no chance of being off by one in the loop counter or accidentally running off the end of a data structure. More importantly, you can focus on ''what'' you want done without the irrelevant scaffolding of ''how'' to set up control structures. This is called '''declarative programming'''.		If you are new to functional programming, you my think, "Big deal, I write <tt>for</tt> loops in my sleep." Granted. But the advantage of the higher-order function approach is that there is no chance of being off by one in the loop counter or accidentally running off the end of a data structure. More importantly, you can focus on ''what'' you want done without the irrelevant scaffolding of ''how'' to set up control structures. This is called '''declarative programming'''.
	</blockquote>		</blockquote>

			==An implementation using <tt>prd</tt>==

			Our latest implementation is more idiomatic than the previous ones.

			However, there is still the question of '''code reuse'''—the use of existing software, or software knowledge, to build new software following the reusability principles.

			There is something that we are not reusing, but could reuse, to our advantage.

			<tt>prd x</tt> returns the product of the numeric list <tt>x</tt>. Moreover, unlike, for example, <tt>ij</tt>, which is implemented in k,
			<pre>
			q)ij
			k){.Q.ft[{x[j],'(. y)i j:&(#y)>i:(!y)?(!+!y)#x}[;y]]x}
			</pre>
			<tt>prd</tt> is implemented in low-level C:
			<pre>
			q)prd
			prd
			</pre>
			We confirm this—<tt>prd</tt> is in <tt>.Q.res</tt>:
			<pre>
			q).Q.res
			`abs`acos`asin`atan`avg`bin`binr`cor`cos`cov`delete`dev`div`do`enlist`exec`exit`exp`getenv`hopen`if`in`insert`last`like`log`max`min`prd`select`setenv`sin`sqrt`ss`sum`tan`update`var`wavg`while`within`wsum`xexp
			</pre>

			Here is the resulting implementation:
			<pre>
			fact6:{prd 1+til x}
			</pre>

			==Assessing the performance of our implementations==

			Let us list all of our implementations of the factorial:
			<pre>
			fact:{$[x;x*.z.s x-1;1]};
			fact1:{if[x>0;:x*.z.s x-1];1};
			fact2:{do[-1+f:r:x;r*:f-:1];r};
			fact3:{r:1;do[x;r*:x;x-:1];r};
			fact4:{r:1;while[x;r*:x;x-:1];r};
			fact5:{(*/)1+til x};
			fact6:{prd 1+til x}
			</pre>

			Which one is the most efficient?

			Let's time them:
			<pre>
			q)\t:100000 fact first 1?26
			1154
			q)\t:100000 fact1 first 1?26
			1314
			q)\t:100000 fact2 first 1?26
			934
			q)\t:100000 fact3 first 1?26
			963
			q)\t:100000 fact4 first 1?26
			1020
			q)\t:100000 fact5 first 1?26
			408
			q)\t:100000 fact6 first 1?26
			378
			</pre>

			Unsurprisingly, <tt>fact6</tt> emerges as a leader, followed closely by <tt>fact5</tt>. We can see that there is a performance reason for preferring iterators over loops, in addition to the previously stated observation that iterators are more idiomatic that loops. However, the fastest results are obtained by using an optimized function, <tt>prd</tt>, written in low-level C.

Admin at 07:13, 1 July 2021

2021-07-01T07:13:57Z

← Older revision		Revision as of 07:13, 1 July 2021
Line 239:		Line 239:
	fact5:{(*/)1+til x}		fact5:{(*/)1+til x}
	</pre>		</pre>

			Iterators are examples of higher-order functions of '''functional programming'''. In functional programming, a '''higher-order function''' is a function that does at least one of the following:
			* takes one or more functions as arguments,
			* returns a function as its result.

			This is what Jeffry A. Borror says about iterators in <span class="plainlinks">[https://code.kx.com/q4m3/ Q for Mortals]</span>:
			<blockquote>
			If you are new to functional programming, you my think, "Big deal, I write <tt>for</tt> loops in my sleep." Granted. But the advantage of the higher-order function approach is that there is no chance of being off by one in the loop counter or accidentally running off the end of a data structure. More importantly, you can focus on ''what'' you want done without the irrelevant scaffolding of ''how'' to set up control structures. This is called '''declarative programming'''.
			</blockquote>

Admin at 07:05, 1 July 2021

2021-07-01T07:05:59Z

← Older revision		Revision as of 07:05, 1 July 2021
Line 235:		Line 235:
	which equals 120.		which equals 120.

	Hence here is our next implementation of the factorial using the Over iterator:		Hence here is our next implementation of the factorial—using the Over iterator:
	<pre>		<pre>
	fact5:{(*/)1+til x}		fact5:{(*/)1+til x}
	</pre>		</pre>

Admin at 07:05, 1 July 2021

2021-07-01T07:05:30Z

← Older revision		Revision as of 07:05, 1 July 2021
Line 194:		Line 194:
	</pre>		</pre>

	=An iterative implementation using the Over iterator=		==An iterative implementation using the Over iterator==

	'''Iterators''', which used to be called '''adverbs''', modify the meaning of verbs.		'''Iterators''', which used to be called '''adverbs''', modify the meaning of verbs.

Admin at 07:05, 1 July 2021

2021-07-01T07:05:06Z

@@ Line 192: / Line 192: @@
 <pre>
 fact4a:{f:r:x;while[f-:1;r*:f];r}
 </pre>

Admin at 06:41, 1 July 2021

2021-07-01T06:41:53Z

@@ Line 122: / Line 122: @@
 if[expr_cond;expr_1;...;expr_n]
 </pre>
-Unlike <tt>$[...]</tt>, it is not a function and does not return a value. Therefore we need to force the return using <tt>:</tt>:
 <pre>
 fact1:{if[x>0;:x*.z.s x-1];1}
@@ Line 129: / Line 134: @@
 ==A problem with the recursive implementations==
-Recursive implementations tend to underperform their iterative peers. In addition, they may run out of stack space:
+Recursive implementations tend to underperform their iterative peers.
 <pre>
 q)fact 2001
@@ Line 137: / Line 144: @@
 </pre>
-It doesn't matter so much specifically for the factorial, because the factorial of 26 is already enormous and overflows the <tt>long</tt>:
+This doesn't matter that much specifically for the factorial, because the factorial of 26 is already enormous and overflows the <tt>long</tt>:
 <pre>
 q)fact 25
@@ Line 145: / Line 152: @@
 </pre>
-==An iterative implementation==
+For many other recursive functions <tt>'stack</tt> is a serious issue.
 <pre>
-fact2:{r:1;do[x;r*:x;x-:1];r}
+fact4a:{f:r:x;while[f-:1;r*:f];r}
 </pre>

Admin at 06:15, 1 July 2021

2021-07-01T06:15:50Z

← Older revision		Revision as of 06:15, 1 July 2021
Line 23:		Line 23:
	We'll start with a dummy, incorrect implementation that always returns <tt>1</tt>:		We'll start with a dummy, incorrect implementation that always returns <tt>1</tt>:
	<pre>		<pre>
	fact:{[x]1f}		fact:{[x]1}
	</pre>		</pre>
	This defines a function, <tt>{...}</tt>, which takes a single argument, <tt>[x]</tt>, which always (irrespective of the argument) returns <tt>1f</tt>. We assign, <tt>:</tt>, a name to that function, <tt>fact</tt>, so we can call it again and again, as required.		This defines a function, <tt>{...}</tt>, which takes a single argument, <tt>[x]</tt>, which always (irrespective of the argument) returns <tt>1</tt>. We assign, <tt>:</tt>, a name to that function, <tt>fact</tt>, so we can call it again and again, as required.

	This is a function of a single argument, in other words, a '''monadic''' or '''unary''' function. We could have a '''dyadic''' ('''binary'''), '''triadic''' ('''ternary'''), etc. function. Here is an example of a dyadic function:		This is a function of a single argument, in other words, a '''monadic''' or '''unary''' function. We could have a '''dyadic''' ('''binary'''), '''triadic''' ('''ternary'''), etc. function. Here is an example of a dyadic function:
	<pre>		<pre>
	add:{[x;y]x+y}		add:{[x;y]x+y}
			</pre>

			Incidentally, it is possible to have a '''niladic''' ('''nullary''') function. Such functions are not necessarily constant and may have useful side effects. The following function will print out the current time:
			<pre>
			tm:{[].z.p}
	</pre>		</pre>

Line 50:		Line 55:
	The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.		The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.
	</blockquote>		</blockquote>
	<p style="text-align:right">—Niklaus Wirth, ''Algorithms + Data Structures = Programs'', 1976.		<p style="text-align:right">—Niklaus Wirth, ''Algorithms + Data Structures = Programs'', 1976.</p>

	Most computer programming languages support recursion by allowing a function to call itself from within its own code. Q is no exception:		Most computer programming languages support recursion by allowing a function to call itself from within its own code. Q is no exception:
	<pre>		<pre>
	fact:{$[x=0f;1f;x*fact x-1]}		fact:{$[x=0;1;x*fact x-1]}
	</pre>		</pre>

	~~Here we~~ have used the '''conditional evaluation''', the ternary overload of $:		We have just used the '''conditional evaluation''', the ternary overload of $:
	<pre>		<pre>
	$[expr_cond; expr_true; expr_false]		$[expr_cond; expr_true; expr_false]
Line 65:		Line 70:
	Notice that we don't need to have a ''boolean'' zero in <tt>expr_cond</tt> for <tt>expr_false</tt> to be evaluated; it could well be a long zero. Thus we can rewrite <tt>fact</tt> more tersely:		Notice that we don't need to have a ''boolean'' zero in <tt>expr_cond</tt> for <tt>expr_false</tt> to be evaluated; it could well be a long zero. Thus we can rewrite <tt>fact</tt> more tersely:
	<pre>		<pre>
	fact:{$[x;x*fact x-1;1f]}		fact:{$[x;x*fact x-1;1]}
	</pre>		</pre>

	How would the function call itself if it weren't assigned to the ~~variable~~ <tt>fact</tt>? In q, there is a provision for that. The function can call itself using <tt>.z.s</tt> ~~even if it is anonymous~~:		How would the function call itself if it weren't assigned the name <tt>fact</tt>? In q, there is a provision for that. The function can call itself using <tt>.z.s</tt>:
	<pre>		<pre>
	fact:{$[x;x*.z.s x-1;1]}		fact:{$[x;x*.z.s x-1;1]}
			</pre>
			This works even if the function is anonymous, for example:
			<pre>
			q){$[x;x*.z.s x-1;1]}[5]
			120
	</pre>		</pre>

Line 88:		Line 98:
	120		120
	</pre>		</pre>

			Let us look at our recursive function again:
			<pre>
			fact:{$[x;x*.z.s x-1;1]}
			</pre>

			A recursive function definition has one or more '''base cases''', meaning input(s) for which the function produces a result trivially (without recurring), and one or more '''recursive cases''', meaning input(s) for which the program recurs (calls itself).

			In our case the base case is <math>0! = 1</math>. You can see it here:
			<pre>
			fact:{$[x;...;1]}
			</pre>
			Our recursive case is, for all <math>x > 0</math>, <math>n! = n(n - 1)!</math>. You can see it here:
			<pre>
			fact:{$[...;x*.z.s x-1;...]}
			</pre>
			Because the base case breaks the chain of recursion, it is sometimes also called the "terminating case".

	==A recursive implementation using the imperative <tt>if</tt> statement==		==A recursive implementation using the imperative <tt>if</tt> statement==

Admin at 12:50, 30 June 2021

2021-06-30T12:50:03Z

← Older revision		Revision as of 12:50, 30 June 2021
Line 70:		Line 70:
	How would the function call itself if it weren't assigned to the variable <tt>fact</tt>? In q, there is a provision for that. The function can call itself using <tt>.z.s</tt> even if it is anonymous:		How would the function call itself if it weren't assigned to the variable <tt>fact</tt>? In q, there is a provision for that. The function can call itself using <tt>.z.s</tt> even if it is anonymous:
	<pre>		<pre>
	fact:{$[x;x*.z.s x-1;1f]}		fact:{$[x;x*.z.s x-1;1]}
	</pre>		</pre>

Line 76:		Line 76:
	<pre>		<pre>
	q)fact[0]		q)fact[0]
	1f		1
	q)fact[1]		q)fact[1]
	1f		1
	q)fact[2]		q)fact[2]
	2f		2
	q)fact[3]		q)fact[3]
	6f		6
	q)fact[4]		q)fact[4]
	~~24f~~		24
	q)fact[5]		q)fact[5]
	~~120f~~		120
	</pre>		</pre>

Line 98:		Line 98:
	<pre>		<pre>
	fact1:{if[x>0;:x*.z.s x-1];1}		fact1:{if[x>0;:x*.z.s x-1];1}
			</pre>

			==A problem with the recursive implementations==

			Recursive implementations tend to underperform their iterative peers. In addition, they may run out of stack space:
			<pre>
			q)fact 2001
			'stack
			[1799fact:{$[x;x*.z.s x-1;1f]}
			^
			</pre>

			It doesn't matter so much specifically for the factorial, because the factorial of 26 is already enormous and overflows the <tt>long</tt>:
			<pre>
			q)fact 25
			7034535277573963776
			q)fact 26
			-1569523520172457984
			</pre>

			==An iterative implementation==

			<pre>
			fact2:{r:1;do[x;r*:x;x-:1];r}
	</pre>		</pre>