Higher Order Functions

In Smojo, higher-order functions refer specifically to words that enable implicit loops.

To understand what higher order functions are and how are they useful, consider the following three words:

  1. NATURAL-SUM
    computes the sum of natural numbers (i.e. 1 + 2 + 3 + ...)
  2. CUBE-SUM
    computes the sum of the cubes of natural numbers (i.e. 13 + 23 + 33 + ... )
  3. HARMONIC-SUM
    computes the sum of the reciprocals of natural numbers (i.e. 1 ⁄ 1 + 1 ⁄ 2 + 1 ⁄ 3 + ... )

We observe that these three words share a couple of common patterns:

Seen this way, we would then prefer to have:

Words which accomplish these looping tasks are known in Smojo as "higher order functions", or HOFs for short. The value in this approach is that we can then compose these HOFs to create new and perhaps complex loops easily.

To see this combination capability clearly, imagine we had words 
SUM ( seq -- n )
to sum a sequence and
MAP ( seq xt -- seq )
that transforms a given sequence by applying the XT to each member of the sequence. We can then easily write
NATURAL-SUM
,
CUBE-SUM
and
HARMONIC-SUM
this way:
		: NATURAL-SUM ( -- n )
			1 2 ... SUM ; 
		
		: CUBE-SUM ( -- n )
			1 2 ... [: dup dup * * ;] MAP SUM ; 
			
		: HARMONIC-SUM ( -- n )
			1 2 ... [: 1 swap /. ;] MAP SUM ; 		
	
Here you can see the output of
MAP
being fed into the input of
SUM
to compute an answer. This idea of composing new loops from two or more old ones is the key idea behind Smojo's higher order functions.

Can we go further?

Consider the word 
NATURAL-PRODUCT
that gives the product of natural numbers: (i.e., 1 * 2 * 3 ... ). Clearly there is a common pattern with
NATURAL-SUM
: you get the one from the other by simply replacing
+
with
*
. To solve this problem, we could imagine a word
REDUCE ( seq xt -- * )
that simply captures the idea of looping alone. The output of
REDUCE
depends purely on the action of the XT. We could then write
NATURAL-SUM
and
NATURAL-PRODUCT
this way:
			: SUM ( seq -- n )
			        0 SWAP
				['] + REDUCE ;

			: NATURAL-SUM ( -- n )
				1 2 ... SUM ; 

			: PRODUCT ( seq -- n )
				1 SWAP
				['] * REDUCE ; 
				
			: NATURAL-PRODUCT ( -- n )
				1 2 ... PRODUCT ; 
		
Superficially,
REDUCE ( seq xt -- * )
may seem like
MAP ( seq xt -- seq )
, but there are huge differences:


          Quick Quiz: based on what you have learnt in this section, write a word 
.LIST ( seq -- )
that prints out all the elements of a sequence.

Composability

The idea of composibility is an important design principle in Smojo: when writing your Smojo programs, always choose designs that preserve or enhance composibility of words.

As an example, consider the following re-design of our first example:

			: CUBES ( -- seq )
				1 2 ... [: dup dup * * ;] MAP ; 
			
			: CUBE-SUM ( -- n )
				CUBES SUM ; 

			: RECIPROCALS ( -- seq )		
				1 2 ... [: 1 swap /. ;] MAP ; 

			: HARMONIC-SUM ( -- n )
				RECIPROCALS SUM ; 		
		
This is a poor design choice because none of these words are composable. This alternative is much better:
			: CUBED ( seq -- seq )
				[: dup dup * * ;] MAP ; 
			
			: CUBE-SUM ( -- n )
				1 2 ... CUBED SUM ; 

			: INVERTED ( seq -- seq )		
				[: 1 swap /. ;] MAP ; 

			: HARMONIC-SUM ( -- n )
				1 2 ... INVERTED SUM ; 		
		
The words
CUBED ( seq -- seq )
and
INVERTED ( seq -- seq )
are composable, either with themselves or with each other. This offers us the immediate possibility of creating new sums using these words:
			
			: X^9-SUM ( -- n )
				1 2 ... CUBED CUBED SUM ; 

			: 1/X^3-SUM ( -- n )
				1 2 ... INVERTED CUBED SUM ; 		
		
Well-designed programs have this idea of composibility on multiple levels. Refining the example above:
			
			: CUBE ( n -- n )
				dup dup * * ; 
			
			: CUBED ( seq -- seq )
				['] CUBE MAP ; 
			
			: CUBE-SUM ( -- n )
				1 2 ... CUBED SUM ; 

			: RECIPROCAL ( n -- n )
				1 swap /. ; 

			: INVERTED ( seq -- seq )		
				['] RECIPROCAL MAP ; 

			: HARMONIC-SUM ( -- n )
				1 2 ... INVERTED SUM ; 		
		
In this design, we have additional words
CUBE ( n -- n )
and
RECIPROCAL ( n -- n )
that are composable too. This helps us:
  1. during testing, by giving us a "toolbox" of words to experiment with through composition,
  2. design "one-off" combination words that might not be used again,
  3. build new functionality using words across multiple levels,
  4. optimize for speed by selecting more efficient combinations.
As examples of the last two:
  1. CUBED :> RECIPROCAL 0.0000001 > ; TAKE-WHILE
    will return a finite subsequence of cubes whose reciprocal is greater than 10-7.
  2. [: CUBE CUBE ;] MAP
    is more efficient than
    CUBED CUBED
    , but less clear.

Laziness

Higher order functions are very useful as they are able to transform, consolidate or combine sequences. 
	   With the exception of 
REDUCE
, these functions are lazy in Smojo, which means they only perform their task when an answer is needed.


	   This property is useful especially in data processing or whenever we need to handle infinite lists. 
	   Once an actual value is needed and read using words like 
HEAD
, or indirectly with
REDUCE
is the sequence evaluated, and even then only until the desired element is reached. Laziness therefore reduces both the running time and amount of memory space needed by your program by avoiding making calculations before they are actually used.

Below are Smojo's primary higher order functions. All are Lazy except 
REDUCE
.

Word Action
MAP ( seq xt -- seq )
Takes a sequence and an XT as arguments. The XT must be a single-valued function. The resulting sequence is a sequence with elements being the output of the function on the elements in the original sequence.
FILTER ( seq xt -- seq )
Takes a sequence and an XT as arguments. The XT must be a boolean function. The resulting sequence is a sub-sequence of the original with elements such that the output of the function is true.
REDUCE ( seq xt -- * )
Takes a finite sequence and an XT as arguments, and reduces the sequence to a single value. It is not lazy.
ZIPWITH ( seq seq xt -- seq )
Takes two sequences and an XT as arguments. The XT is used to combine the sequences element-wise, resulting with a third sequence.
TAKE-WHILE ( seq xt -- seq )
Creates a sub-sequence by selecting elements as long as the XT is true. It stops taking elements when the XT returns false. For example:
1 2 ... :> 5 < ; TAKE-WHILE
returns the sequence (1,2,3,4).

Examples

Example 1: Find all squares

	: ^2 dup * ;
		
	1 2 ... ' ^2 map .list
	1 4 9 16 25 ...
	
or
	1 2 ... :> dup * ; map .list
	1 4 9 16 25 ...
	
Example 2: Find all even numbers
	: even? 2 mod 0 = ;

	1 2 ... ' even? filter .list
	2 4 6 8 10 ...
	
Example 3: Find the numbers divisible by 5
	: div? ( n -- xt ) 
		{ n } [: n mod 0 = ;] ;
	
	1 2 ... 5 div? filter .list
	5 10 15 20 25 30 ...
	
Example 4: Find the maximum number
	0 1 2 ... 100 take ' max reduce .
	100.0 ok
	
Remember that unlike
MAP
,
FILTER
and
ZIPWITH
,
REDUCE
is not lazy.
REDUCE
will try to iterate over the entire sequence, so you must ensure it is finite before attempting a reduction. In this example, the word
MAX
needs two arguments. Note that 0, which acts as the first argument is already on the stack and is constantly updated by
MAX
during reduction. The second argument is obtained from the sequence as
REDUCE
iterates through it.

Example 5: Find the sequence resulting from the element-wise summation between the two sequences

	1 2 ...
	100 99 ...
	' + zipwith .list
	101 101 101 101 ...
	
Example 6: Find all squares divisible by 17 and 23
 	1 2 ... ' ^2 map 17 div? filter 23 div? filter .list
	152881 611524 1375929 2446096 3822025 ... 
	

Quiz

Question 1

Write a word 
MINIMUM ( seq -- n )
to find the minimum value of a sequence. Does your word make any assumptions about the maximum value?



Question 2

Write a word 
REVERSE
that reverses any finite sequence. Can this word be Lazy? Is it possible to reverse infinite sequences?



Question 3*

Given a sequence s = (s0, s1, s2, ... ), write a word 
SUM3 ( seq -- seq )
which produces a new sequence sum3(s) = (s0 + s1 + s2, s1 + s2 + s3, ... )



Question 4*

Generalize 
SUM3
to
SUMN ( seq n -- seq )
, which is able to sum any length window N.
SUMN
should take the initial sequence and N as input.



Question 5*

Write a word 
ZIP ( seq seq -- seq )
that produces 2-tuples from each pair of elements of the input sequences.



Question 6*

Write a word 
TAKE ( seq n -- seq )
that produces a sequence of the first N elements of an infinite sequence. Hint: You may have to use
ZIPWITH
and
TAKE-WHILE
.



Question 7

Is:

1 2 ... 
	255 TAKE 
		:> 31 MOD 0 = ; FILTER
the same as
1 2 ... 
	:> 31 MOD 0 = ; FILTER 
		255 TAKE 
? Explain why.



Question 8*

Write a word that performs this sum over N terms:

61*3 + 73*7 + 89*11 + 927*15 + ...



Question 9

Write a word 
CONSA ( seq seq -- seq )
that
CONS
es the second (finite) list to the first.



Next: Application: Mapped Filters*