Factor pt. 2 - Sequences and Control Structures
Tags: factor, concatenative, tutorial, esoteric
Published: 2021-10-03 15:18:17

In the first part of the tutorial I have shown how to use Factor words to put numbers on the stack, shuffle them and perform arithmetic operations on them. I also presented how you can define your own words if you want to reuse code often. All of this only involved numbers on a stack, but Factor can do much more than that. Today I will show you basic sequence types and how to use them for flow control, but first I need to cover something I forgot to mention in the previous article.

### Boolean values
###### And operations
Factor recognises two boolean values: `t` for true and `f` for false. In addition to that `f` is a general value representing lack of other suitable values like Nil or None in other languages, and any other value will be interpreted as `t` in tests and boolean arithmetics. Factor provides all standard boolean arithmetics operations: `not`, `or`, `and` and `xor`. Words `or`, `and` and `xor` don't convert their inputs to booleans for testing so their output can also be non-boolean (this behaviour is out of scope of this series, but if you want to know more, check their respective help pages for more information). For the sake of clarity I will only be using them for operations on booleans, but remember that any value that is not `f` is considered true.
```Factor
t t and f or t xor
! S: t
```
Numbers can be compared to produce boolean values:
```Factor
3 5 < 3 5 > 0 0 >=
! S: f t t
```
With that out of the way let's proceed to sequences.

### Quotations
###### Lambdas, anonymous functions, etc.
The most commonly used sequence type in Factor is a **quotation** which stores a series of words. The word that creates quotations, as well as most other collections, is a syntax word. Syntax word for literal quotations is `[` with syntax:
```Factor
[ elements... ]
```
Note spaces separating brackets from the elements.
Quotations store words for later execution on the stack. You can think of them as anonymous functions or lambdas if it helps you.
Words that operate on quotations are called combinators and control structures are implemented using them.

The simplest combinator is `call` which simply executes contents of the quotation on top of the stack.
```Factor
[ 2 4 5 + ] call
! S: 2 9
```
Way more useful are the cleave combinators: `bi`, `tri` and `cleave`. They take some quotations and execute them one after another on separate copies of the stack element that is just beneath them. `bi` works with two quotations, `tri` with three and `cleave` works with a sequence of quotations.
```Factor
3 [ 2 + ] [ 1 - ] bi
! S: 5 2
2dup

3 [ 2 + ] [ 1 - ] [ 4 * ] tri
! S: 5 2 12
3dup

3 [ [ 2 + ] [ 1 - ] [ 4 * ] [ dup * ] ] cleave
! S: 5 2 12 9
```
*Note: I used a quotation containing quotations for `cleave` but normally an array of quotations is used instead.*

If you have the Listener handy I encourage you to try experimenting with the cleave combinators, they are used all the time and can let you skip some janky stack shuffling. Also make sure to take a look at their help pages, as well as some similar words like `2bi` or `bi@`. Help is invoked by executing `\ bi help`.

### Control flow
###### Using combinators
Factor has combinators that can serve the functions of standard control flow structures: if-else, while, for and for-each. Let's first focus on the first three, as for-each requires other sequences and I will touch upon it later.

If-else behaviour is achieved using words `if`, `when`, `unless` or any of the other conditional combinators. Word `if` expects a flag (`t` or `f`) and two quotations. The bottom one will be called when the flag is true, else the top one will be executed:
```Factor
5 3 f [ + ] [ - ] if
! S: 2
```
It is important that both quotations have the same stack effects or the compiler will not be able to unambiguously derive the stack effect of the construction and will throw an error. `when` and `unless` are variants of `if` with no false or true quotations respectively.
```Factor
3 t [ 6 + ] when
5 f [ drop 1 ] unless
! S: 9 1
```
Quotations supplied to `when` and `unless` have to have the same stack effects as their nonexistent counterparts, which means they mustn't change the depth of the stack.

While and for behaviour can be implemented using looping combinators like `while`, `until` or `loop`. The simplest of them, `loop`, takes a quotation and executes it until it leaves an `f` on top of the stack:
```Factor
5 [ 1 swap 1 - dup 0 > ] loop drop
! S: 1 1 1 1 1
```
The other two looping combinators take two quotations - a predicate and a body - and execute them repeatedly until (or while) the predicate leaves a true value on top of the stack. I'm not going to provide any examples for these because I have never used them and they aren't very useful in practice. A much more important behaviour of for-each will be discussed later.

### Basic sequences
###### Arrays and strings
The most basic sequence type taught for most languages is usually an **array**. It's a simple ordered sequence of values which can be anything you can put on the stack. Literal arrays are created by a syntax word `{` with syntax:
```Factor
{ elements... }
```
**Strings** are arrays of numbers representing unicode characters.
Literal strings are created by a syntax word `"` which has the usual syntax:
```Factor
"string..."
```
Note the lack of spaces separating the quotes from the string itself. Factor strings have full unicode support and allow a lot of escape sequences to specify various characters. For more info check `\ " help`.

### Iterating over sequences
###### Sequences plus combinators
Sequences come with their own words like `nth`, `length` or `set-nth`, but here I would like to focus on sequence combinators, because they allow us to implement the for-each behaviour. There are many words used to iterate over contents of sequences, I will focus on the three most common: `each`, `map` and `filter`.

`each` takes a sequence and a quotation and executes this quotation on every element of the sequence in order. The quotation can use other elements of the stack but it has to consume exactly one - the sequence element. It can be used for example to implement a sequence reduce combinator:
```Factor
0 { 0 1 2 3 4 5 6 7 8 9 } [ + ] each
! S: 45
```
In this example each of the numbers is added to 0 resulting in a sum of all numbers from 0 to 9. This usage actually has its own word, `reduce`.

`map` will apply the quotation to each element of the sequence producing new elements that are then collected into a new sequence. It lets you apply a transformation on many values at once. For example if you wanted an array of squares of numbers up to 10:
```Factor
{ 0 1 2 3 4 5 6 7 8 9 10 } [ sq ] map
! S: { 0 1 4 9 16 25 36 49 64 81 100 }
```
`sq` is a word I mentioned in the previous tutorial. It executes `dup *` which multiplies the number by itself.

`filter` will apply the quotation to each element of the sequence and create a new sequence with elements for which the quotation returned a true value.
```Factor
{ 6 925 2 94 0 4 5 3 474 11 } [ even? ] filter
! S: { 6 2 94 0 4 474 }
```
`even?`, as the name suggests, returns `t` for even inputs and `f` for odd. It is used here to filter out the odds.

### Calculating primes
###### A practical example
Given what we learned today we can finally write something useful. I will be using a top-down design order, meaning I will start with the most general word and figure out what helper words will be needed to implement it. Almost everything I come up in this section is already available in the `math.primes` vocabulary, but it's a good example so let's pretend we don't know that.

Let's say we want to write a word that will filter only prime numbers from a sequence. For that we can use the word `filter` with a predicate quotation that returns true if a number is prime. Our general word looks like this:
```Factor
: filter-primes ( seq -- new-seq )
    [ prime? ] filter
;
```
If you write it like this into the listener it will complain that word `prime?` is not in the currently used vocabularies, so let's define `prime?`.

The simplest way to check if a number is prime is to check if any number from 2 to its square root is its divisor. This method is called a trial division and it's not the most efficient way of looking for primes, but it is simple. To do this we will first transform a sequence of numbers from 2 to sqrt(n) into boolean values indicating divisibility and then reduce this sequence using the function `or`:
```Factor
: prime? ( n -- ? )
    dup [2,sqrt(n)]             ! Construct the sequence
    [ over multiple? ] map nip  ! Check divisibility
    f [ or ] reduce not         ! Take a logic or of the whole sequence
;
```
This didn't help at all! Now we have two undefined words: `[2,sqrt(n)]` and `multiple?`! The solution is to keep defining until everything works out.

`[2,sqrt(n)]` should return a sequence of integers from 2 to sqrt(n). Procedurally generating sequences is not an easy topic so I will yield and use a word from `math.ranges` vocabulary: `[a,b]`. This word constructs a sequence of numbers starting at it's first argument and incrementing by one up to but not exceeding the second argument. It's now only a matter of calculating these arguments:
```Factor
USING: math.ranges math.functions ;
: [2,sqrt(n)] ( n -- range )
    sqrt 2 swap [a,b]
;
```
`USING:` and `USE:` are syntax words that tell Factor in what vocabularies it should search for words we use. Here `[a,b]` is from `math.ranges` and `sqrt` is from `math.functions`.

Now we are again left with one undefined word: `multiple?`. It's function is to check whether its second argument is a multiple of the first. A usual way to check for divisibility is by using the modulo function:
```Factor
: multiple? ( n m -- ? )
    swap mod 0 =
;
```
And that's it! We're done! If you enter those definitions in a correct order you will have a working `filter-primes` word!

Now, this code has a bunch of problems. For starters it considers 2 to be composite. It will also break when checking if zero is prime. Check if you can use some constructions we learned today to fix these problems. Bonus points if you can keep all word definitions to three short lines (tip: define more words).

#### Practical example code
```Factor
USING: math.functions math.ranges ;

: multiple? ( n m -- ? )
    swap mod 0 =
;

: [2,sqrt(n)] ( n -- range )
    sqrt 2 swap [a,b]
;

: prime? ( n -- ? )
    dup [2,sqrt(n)]
    [ over multiple? ] map nip
    f [ or ] reduce not
;

: filter-primes ( seq -- new-seq )
    [ prime? ] filter
;

! Example use:
3 40 [a,b] filter-primes
! S: V{ 3 5 7 11 13 17 19 23 29 31 37 }
```
Don't worry about `V{`. It's a syntax word for literal vectors and it does the same thing as `{` for arrays. The difference isn't important here.

### Conclusion
###### We did something!
In this tutorial you learned about basic sequences in Factor as well as quotations and how to use them with control flow combinators. I went through a top-down design process for a simple word. Next time I will be looking into Factor's object system: class tuples.

P.S.  You may have noticed a style change in the middle of this article. That's because my editor/corrector unfortunately no longer has enough time to edit my articles as fast as I write them. Subsequent articles will be released uncorrected and (hopefully) edited at a later date.