Front Page | Atom Feed | Admin

[ planet-factor ]

John Benediktsson: Non-repeating

The Programming Praxis blog, which recently achieved the milestone of One Million Hits, posted a challenge a couple days to find the first unrepeated character in a string:

Given a string, find the first character that appears only once in the string. For instance, given the string “aabbcddd”, the first character that appears only once is the “c” found at the 4th character in the string, counting from 0. Be sure that your program properly handles the case that all characters appear more than once.

Our quick-and-dirty solution, using lexical variables, will add each element in the sequence to a hash-set, adding the element to an accumulator if not seen before, removing the element otherwise:

:: non-repeating ( seq -- seq' )
    HS{ } clone :> visited
    0 seq new-resizable :> accum
    seq [
        dup visited ?adjoin
        [ accum push ] [ accum remove! drop ] if
    ] each accum seq like ;

We can then use it like so:

! find all non-repeating characters (in-order)
IN: scratchpad "abcddd" non-repeating .
"abc"

! find the first non-repeating character
IN: scratchpad "abcddd" non-repeating first "%c" printf
a

An improvement might be, instead of using remove! which will look for and remove all occurrences of an object in a sequence, we could instead only remove the first occurrence (knowing an object will only ever be in a sequence once):

: remove-first! ( obj seq -- seq )
    [ index ] keep over [ remove-nth! ] [ nip ] if ;

How else might we improve it?

Thu, 2 May 2013 15:18:00

John Benediktsson: Terminfo

While investigating how to determine if a terminal is color capable, I re-discovered terminfo databases. These database files store the capabilities of terminals in a device-independent manner.

tput

The simple answer is to use the tput program to lookup the terminal functionality (using the TERM environment variable):

$ TERM=xterm-256color tput colors
256

$ TERM=xterm tput colors
8

$ TERM=vt100 tput colors
-1

If you trace the system calls that tput makes, you will see that it is loading a terminfo file to provide the answer:

...
stat64("/usr/share/terminfo\0", 0x7FFF5F21A120, 0x7FB279403AD0)
access("/usr/share/terminfo/78/xterm-256color\0", 0x4, 0xE)
open("/usr/share/terminfo/78/xterm-256color\0", 0x0, 0x0)
read(0x3, "\032\001%\0", 0x1001)
...

I wanted to have access to these capabilities from Factor, without running tput, and chose instead to directly parse the terminfo files.

terminfo

The compiled terminfo file is created by the tic program, and begins with a header containing six two-byte short integers:

  1. the magic number (octal 0432)
  2. the size, in bytes, of the names section
  3. the number of bytes in the boolean section
  4. the number of short integers in the numbers section
  5. the number of offsets (short integers) in the strings section
  6. the size, in bytes, of the string table

We can parse this header pretty easily using the pack vocabulary:

TUPLE: terminfo-header names-bytes boolean-bytes #numbers
#strings string-bytes ;

C: <terminfo-header> terminfo-header

: read-header ( -- header )
    12 read "ssssss" unpack-le unclip
    0o432 = [ "bad magic" throw ] unless
    5 firstn <terminfo-header> ;

The names section comes next, containing the various names for the terminal separated by a "|" character and terminated by a NUL byte ("0"):

: read-names ( header -- names )
    names-bytes>> read but-last "|" split [ >string ] map ;

The boolean section is stored as one byte per boolean flag, either a 0 or 1:

: read-booleans ( header -- booleans )
    boolean-bytes>> read [ 1 = ] { } map-as ;

The number section is stored as a sequence of two-byte short integers, aligned to an even byte (meaning if the name and boolean sections consume an "odd" number of bytes, an extra byte is inserted that should be skipped over to ensure the numbers start on an even byte):

: read-shorts ( n -- seq' )
    2 * read 2 <groups> [ signed-le> dup 0 < [ drop f ] when ] map ;

: align-even-bytes ( header -- )
    [ names-bytes>> ] [ boolean-bytes>> ] bi + odd?
    [ read1 drop ] when ;

: read-numbers ( header -- numbers )
    [ align-even-bytes ] [ #numbers>> read-shorts ] bi ;

The strings are more complex, stored in two sections. The first section is a sequence of two-byte short integers and the second section is a sequence of bytes. To rebuild the string capabilities, interpret the integers as an offset into the string table:

: read-strings ( header -- strings )
    [ #strings>> read-shorts ] [ string-bytes>> read ] bi '[
        [ _ 0 2over index-from swap subseq >string ] [ f ] if*
    ] map ;

Putting this all together, we can "parse" our terminfo file into an object:

TUPLE: terminfo names booleans numbers strings ;

C: <terminfo> terminfo

: read-terminfo ( -- terminfo )
    read-header {
        [ read-names ]
        [ read-booleans ]
        [ read-numbers ]
        [ read-strings ]
    } cleave <terminfo> ;

Finally, we can write a parsing word to convert a terminfo file into a terminfo object:

: file>terminfo ( path -- terminfo )
    binary [ read-terminfo ] with-file-reader ;

/usr/share/terminfo

The terminfo files are stored in /usr/share/terminfo. If we wanted to get a list of all available terminfo files, we can just list this directory:

MEMO: terminfo-names ( -- names )
    "/usr/share/terminfo" [
        [ directory-files ] map concat
    ] with-directory-files ;

If instead, we wanted to lookup a specific terminal, we can map the name of the terminal to a directory. On Mac OS X, these are stored in a sub-directory with the hexadecimal representation of the first byte in the string. On Linux, the first character is the name of the sub-directory:

HOOK: terminfo-path os ( name -- path )

M: macosx terminfo-path ( name -- path )
    [ first >hex ] keep "/usr/share/terminfo/%s/%s" sprintf ;

M: linux terminfo-path ( name -- path )
    [ first ] keep "/usr/share/terminfo/%c/%s" sprintf ;

Success!

With just this much implemented, we can lookup our "max_colors" attribute, knowing it is the 14th number in the numbers table:

: max-colors ( name -- n/f )
    terminfo-path file>terminfo numbers>> 13 swap ?nth ;

IN: scratchpad "xterm-256color" max-colors .
256

IN: scratchpad "xterm" max-colors .
8

IN: scratchpad "vt100" max-colors .
f

I added support for parsing all the capabilities into a hashtable, and allowing named lookup (rather than needing to know the offset like we used above).

This is available now in the terminfo vocabulary.

Fri, 26 Apr 2013 16:00:00

John Benediktsson: Factor 0.96 now available

"You're smart too late and old too soon." - Mike Tyson

I'm very pleased to announce the release of Factor 0.96!

OS/CPUWindowsMac OS XLinux
x86
0.96
0.96
0.96
x86-64
0.96
0.96
0.96

Source code: 0.96

This release is brought to you with over 1100 commits by the following individuals:

Alex Vondrak, Benjamin Pollack, Daniel Nagel, Doug Coleman, John Benediktsson, Jon Harper, Michael T. Richter, and @PGGB.

Aside from bug fixes and various library improvements, I want to highlight the following changes:

  • Major compiler improvements (thanks Alex Vondrak!):
    • Global Value Numbering (disabled currently by default)
    • Parallel-Copy Semantics
  • Performance improvements to hashtables, hash-sets, heaps, and bloom-filters.
  • Support for Retina Displays on OS X
  • Greatly improved table gadget performance
  • PDF streams (and related PDF documentation)!
  • Speed up math comparisons
  • Support resize-window (thanks Jon Harper!)
  • New logo and icons for Factor
  • Added editor support for Textadept, Sublime Text, Geany, BBEdit, and XCode.

Some possible backwards compatibility issues:

  • Changed <groups>, <clumps>, and <circular-clumps> to use slices.
  • Removed <slicing-groups>, <slicing-clumps>, <slicing-circular-clumps>.
  • Renamed editors.notepadpp to editors.notepad++.

Since quite a few performance improvements have been made, I thought I would highlight some improvements using our benchmarks against version 0.95. The chart below shows benchmark time in 0.96 as a percent of the time it took in 0.95, lower is better:


What is Factor

Factor is a concatenative, stack-based programming language with high-level features including dynamic types, extensible syntax, macros, and garbage collection. On a practical side, Factor has a full-featured library, supports many different platforms, and has been extensively documented.

The implementation is fully compiled for performance, while still supporting interactive development. Factor applications are portable between all common platforms. Factor can deploy stand-alone applications on all platforms. Full source code for the Factor project is available under a BSD license.


New Libraries

Sun, 21 Apr 2013 04:38:00

John Benediktsson: Factorial

Calculating factorial numbers is frequently used to compare programming languages. Usually the implementation is simple, as is the one in Factor:

MEMO: factorial ( n -- n! )
    dup 1 > [ [1,b] product ] [ drop 1 ] if ;

I hadn't realized until I skimmed the Wikipedia article on Factorials that there are actually many more kinds of factorials and what Factor really needed was implementations of all of them!

Lots of Factorials

primorial

Similar to the factorial, the primorial is the product of the first n prime numbers.

double-factorial

The product of all the odd integers up to some odd positive integer n is called the double factorial of n, and denoted by n!!.

multifactorial

The multifactorial is a product of integers in steps of two (n!!, the "double factorial"), three (n!!!), or more (in general for a given k step: n!(k)).

quadruple-factorial

The so-called quadruple factorial, however, is not the multifactorial n!(4); it is a much larger number given by (2n)!/n!.

super-factorial

The super factorial is the product of the first n factorials.

hyper-factorial

The hyper factorial is defined as:

alternating-factorial

The alternating factorial is the absolute value of the alternating sum of the first n factorials.

exponential-factorial

The exponential factorial is a positive integer n raised to the power of n−1, which in turn is raised to the power of n − 2, and so on and so forth.

Be careful with n > 4: the exponential factorial of 5 is 5262144 which is approximately 6.206069878660874 × 10183230.

factorial-prime?

A factorial prime is a prime number that is one less or one more than a factorial.

primorial-prime?

A primorial prime is a prime number that is one less or one more than a primorial.

falling-factorial

The "descending factorial", "falling sequential product", or "lower factorial".

factorial-power

A generalized version of falling factorial.

rising-factorial

The "ascending factorial", "rising sequential product", or "upper factorial".

Now available!

That's probably more factorials than anyone really cares to know about, but now Factor has more than ten times as many factorials as before! The code could probably use some cleanup, but it is available now in the math.factorials vocabulary.

Mon, 15 Apr 2013 17:43:00

John Benediktsson: Bitwise permutations

Using bit twiddling hacks can be fun. When I noticed compute the lexicographically next bit permutation, I knew it could be a neat feature for Factor.

The idea is that given a number like 7 (represented as 00111 in bits), the next few lexicographic permutations of numbers with 3 bits set would be 01011, 01101, 01110, 10011, 10101, 10110.

Next Permutation

The "bit hacks" website uses this C code to calculate the next permutation of bits:

unsigned int v; // current permutation of bits
unsigned int w; // next permutation of bits

unsigned int t = (v | (v - 1)) + 1;
w = t | ((((t & -t) / (v & -v)) >> 1) - 1);

A direct translation into Factor looks like this:

: next-permutation-bits ( v -- w )
    [ dup 1 - bitor 1 + dup ] keep
    [ dup neg bitand ] bi@ /i 2/ 1 - bitor ;

Permutation Words

Factor has a math.combinatorics vocabulary containing useful operations on permutations and combinations for sequences. Now that we have a way of obtaining the next bitwise permutation of a number, I thought we should have similar words for operating on permutations of bits.

A helper word takes bit-count (the number of set bits) and bits (the overall number of bits), and quot (a quotation to apply to each permutation), returning an initial starting permutation, a predicate to continue as long as we are generating valid numbers, and a body that applies the quotation then calculates the next permutation in the sequence:

: permutation-bits-quot ( bit-count bits quot -- n pred body )
    [ [ on-bits dup '[ dup _ >= ] ] [ on-bits ] bi* ] dip swap
    '[ _ [ next-permutation-bits _ bitand ] bi ] ; inline

That might look a little complicated, but it makes these operations fairly simple:

: each-permutation-bits ( bit-count bits quot: ( n -- ) -- )
    permutation-bits-quot while drop ; inline

: map-permutation-bits ( bit-count bits quot: ( n -- m ) -- seq )
    permutation-bits-quot [ swap ] compose produce nip ; inline

: filter-permutation-bits ( bit-count bits quot: ( n -- ? ) -- seq )
    selector [ each-permutation-bits ] dip ; inline

: all-permutation-bits ( bit-count bits -- seq )
    [ ] map-permutation-bits ;

: find-permutation-bits ( bit-count bits quot: ( n -- ? ) -- elt/f )
    [ f f ] 3dip [ 2nip ] prepose [ keep swap ] curry
    permutation-bits-quot [ [ pick not and ] compose ] dip
    while drop swap and ; inline

Try It

You can then do things like this:

! find all 5-bit numbers with 3 bits set
IN: scratchpad 3 5 all-permutation-bits .
{ 7 11 13 14 19 21 22 25 26 28 }

! find the first 5-bit number with 3 bits set, multiples of 5
IN: scratchpad 3 5 [ 5 divisor? ] find-permutation-bits .
25

! print all the even 5-bit numbers with 3 bits set
IN: scratchpad 3 5 [ even? ] filter-permutation-bits [ .b ] each
01110
10110
11010
11100

This is available in the main repository in the math.combinatorics.bits vocabularly.

Thu, 11 Apr 2013 18:31:00

John Benediktsson: move

I've used Factor to build several common unix programs including copy, cat, fortune, wc, and others.

Today, I wanted to show how to build the mv ("move") program using the simple file manipulation words available in Factor. If we look at the man page, we can see that its usage is two-fold:

  1. Rename a source file to a destination file
  2. Move source file(s) to a destination directory

We can make a nice usage string to display if the arguments are not correct:

: usage ( -- )
    "Usage: move source ... target" print ;

Moving files into a directory (and displaying the usage if the destination is not a directory):

: move-to-dir ( args -- )
    dup last file-info directory?
    [ unclip-last move-files-into ] [ drop usage ] if ;

If we specify two arguments, we are either moving a single file into a directory, or renaming a file using the move-file word:

: move-to-file ( args -- )
    dup last file-info directory?
    [ move-to-dir ] [ first2 move-file ] if ;

A "main" word checks the number of arguments and performs the appropriate action:

: run-move ( -- )
    command-line get dup length {
        { [ dup 2 > ] [ drop move-to-dir  ] }
        { [ dup 2 = ] [ drop move-to-file ] }
        [ 2drop usage ]
    } cond ;

MAIN: run-move

An improvement that could be made would be producing better error messages when files don't exist. Something like the errors mv produces:

$ mv src dst
mv: rename src to dst: No such file or directory

The code for this is available on my Github.

Tue, 2 Apr 2013 18:08:00

John Benediktsson: Improved hash-sets

For quite a long time, the hash-sets vocabulary in Factor has had this note at the top:

! In a better implementation, less memory would be used
TUPLE: hash-set { table hashtable read-only } ;

By wrapping a hashtable, we had a pleasantly simple set implementation:

M: hash-set in? table>> key? ;
M: hash-set adjoin table>> dupd set-at ;
M: hash-set delete table>> delete-at ;
M: hash-set members table>> keys ;
M: hash-set null? table>> assoc-empty? ;
M: hash-set cardinality table>> assoc-size ;

Unfortunately, this implementation had the consequence of increased memory usage (members of the set would be stored twice - as both key and value in the hashtable) and some performance implications due to collecting the underlying hashtable into an array and then throwing out the values to return only the keys.

After a new hash-set implementation and a series of minor improvements, we had a greatly improved hash-set. While working on this, I realized we could speed up growing the backing array and applied a similar improvement to hashtables.

Some performance results using our benchmark.hash-sets test:

Before:

IN: scratchpad gc [ hash-sets-benchmark ] time
Running time: 3.066324117 seconds

After:

IN: scratchpad gc [ hash-sets-benchmark ] time
Running time: 0.746381819 seconds

I have since converted various parts of the compiler infrastructure to use hash-sets which had previously used hashtables for set operations and have gotten some overall performance improvements. This is available now in the development version of Factor.

Fri, 22 Mar 2013 17:41:00

John Benediktsson: Faster "shuffle"

A funny comment on a Reddit discussion of my last post about "shuffle" said:

"Turtle races are fun indeed."

Improvements

Well, that is perhaps true given the performance of Factor, Python, and Ruby compared with implementations in C (or SBCL and LuaJIT). However, I'm happy to say that as of today, the performance of randomize (the standard library "shuffle" word) in Factor is greatly improved.

IN: scratchpad 10,000,000 iota >array
Before:
IN: scratchpad gc [ randomize ] time
Running time: 2.78315852 seconds
After:
IN: scratchpad gc [ randomize ] time
Running time: 1.373153681 seconds

Commits

So, what changed?

Well, while investigating the overhead of Factor versus C, I fixed a few things:

Looking at other programming languages is useful to know where your performance can improve and by approximately how much. Since Factor is an attempt at making a high level language that produces relatively fast code, I hope someday to turn this "turtle" into a "hare". Every little bit helps!

Thu, 28 Feb 2013 01:24:00

Blogroll

planet-factor is an Atom/RSS aggregator that collects the contents of Factor-related blogs. It is inspired by Planet Lisp.

Syndicate