Factor pt. 2 - Sequences and Control Structures

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.

t t and f or t xor
! S: t

Numbers can be compared to produce boolean values:

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:

[ 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.

[ 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.

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:

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.

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:

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:

{ elements... }

Strings are arrays of numbers representing unicode characters.
Literal strings are created by a syntax word " which has the usual syntax:

"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:

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:

{ 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.

{ 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:

: 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:

: 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:

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:

: 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

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.