Tuesday, December 23, 2008

GCD

The Factor IRC channel (#concatenative) can be a helpful resource when trying to learn how to code in Factor. Today, someone asked for help implementing the Greatest Common Denominator algorithm in Factor. There are a variety of algorithms for solving for the GCD of two numbers (and many are documented on the Wikipedia entry).

One possible solution uses the Euclidean Algorithm, which is implemented like so:

def gcd(a, b):
    if b = 0:
        return a
    else:
        return gcd(b, a % b)

We can translate that fairly directly to a recursive Factor word:

: gcd ( a b -- c )
    dup zero?
    [ drop ]
    [ [ mod ] keep swap gcd ]
    if ;

It's worth noting that Factor has a builtin word gcd in the math vocabulary calculating this problem.

To learn how it works:

( scratchpad ) USE: math

( scratchpad ) \ gcd help

To see how it is implemented:

( scratchpad ) USE: math

( scratchpad ) \ gcd see

Monday, December 15, 2008

Tuesday, December 9, 2008

wp.factor

I came across a benchmark for comparing languages today. It did not contain a version for Factor, so I thought I would contribute one.

The idea is fairly straightforward, and in the words of the author:

read stdin, tokenize into words
for each word count how often it occurs
output words and counts, sorted in descending order by count

My attempt is below:

USING: arrays assocs kernel io math math.parser 
prettyprint sequences splitting sorting ;

IN: wp

: count-words ( assoc string -- assoc' )
    " " split harvest [ over inc-at ] each ;

: sort-assoc ( assoc -- seq )
    >alist sort-values reverse ;

: print-results ( seq -- )
    [ number>string "    " glue print ] assoc-each ;

: wp ( -- )
    H{ } clone
    [ [ count-words ] each-line ]
    [ sort-assoc print-results ]
    bi drop ;

MAIN: wp

You can run this from factor by putting it in a file called wp.factor and running from the shell:

cat file.txt | ./factor -run=wp