Friday, March 9, 2007

Series in Factor

Played around with Factor again. Still feels strange but is even more fascinating. I tried to implement some helper functions for series. The lesson I learned and what I like the most about Factor: code is data!!! I think Factor surpasses by far the possibilities of Lisp with its defmacro system. Slowly I realize the meaning of a concatenative language.

Here is the code:


! TODO:
! Define unit tests
! help files
! signatures
! parsing words

IN: series

USING: math words sequences kernel tools quotations arrays ;

TUPLE: il list quote ; ! il = infinite list

: get-il-list ( il -- seq )
dup il-list ;

: get-il-quote ( il -- quot )
dup il-quote ;

: unfold ( seq -- stackseq )
[ ] each ;

: push-next-element ( il -- )
over il-list push ;

: rev-il-list ( il -- )
get-il-list nreverse ;

: (pop-first-element) ( il -- element )
get-il-list pop ;

: pop-first-element ( il -- element )
rev-il-list (pop-first-element) ;

: remove-first-element ( il -- element )
pop-first-element >r rev-il-list drop r> ;

: calc-next-element ( seq -- element )
get-il-quote >r get-il-list unfold r> call ;

: il-next ( il -- next )
calc-next-element push-next-element remove-first-element ;

: repeat-if ( il-quot crit-quot -- el ) ! acts as a filter
over call 2dup swap call [ 2nip ] [ drop repeat-if ] if ;

: collect ( n quot -- seq )
V{ } -rot [ add ] append times ;

: not-dividable ( n divisor -- ? )
mod zero? not ;

: naturals ( -- n )
V{ 1 } [ 1+ ] <il> il-next ;

: squares ( -- n )
V{ } [ naturals dup * ] <il> il-next ;

: ones ( -- n )
V{ } [ 1 ] <il> il-next ;

: from2 ( -- n )
V{ 2 } [ 1+ ] <il> il-next ;

: factorial ( -- n )
V{ 1 } [ from2 * ] <il> il-next ;

: powers-of-two ( -- n )
V{ 1 } [ dup + ] <il> il-next ;

: fib ( -- n )
V{ 0 1 } [ + ] <il> il-next ;

: odds ( -- n )
[ naturals ] [ odd? ] repeat-if ;

: evens ( -- n )
[ naturals ] [ even? ] repeat-if ;

: (primes) ( -- )
V{ 2 } [ 1+ ] <il> il-next ; ! => from2

: call-word-def ( word -- res )
word-def dup call dup ;

: prime-criteria ( n -- quot )
[ not-dividable ] curry ;

: gen-quot ( -- quot )
\ repeat-if 3array >quotation ;

: update-word ( x y z -- word-def )
rot define-compound ;

: primestep ( word -- n )
dup >r call-word-def >r prime-criteria
gen-quot r> r> update-word ;

: primes ( -- n )
\ (primes) primestep ;

PROVIDE: demos/series ;



You can use it as follows, e.g.

  1. naturals returns because its invoked the first time "1"
  2. naturals returns "2"
  3. 10 [ primes ] collect returns the first 10 primes in a vector
  4. 10 [ fib ] collect returns the first 10 fibonacci numbers in a vector


Here is a screenshot:

Friday, February 16, 2007

Factor Development Environment

The Factor command line switches have been changed so that I give you an updated version for rlwrap.

rlwrap -b '(){}[],+=&^%$#@"";|\' -f factor.words -r -s 2000 -D 2 -l factor.log /scratch/repos/Factor/f -i=/scratch/repos/Factor/factor.image -shell=tty

When you are on the command line you can run the Factor graphical user interface in the background by typing:

[ ui ] in-thread

Isn't that great? So you have the best of both worlds at hand at the same time.

Tuesday, January 9, 2007

Screencasts demonstrating rlwrap with Factor

First screencast demonstrates completion by pressing TABs.



The second screencast demonstrates mainly the history functionality of readline and also editor integration. (Reverse search is invoked by pressing C-r. Please see the readline documentation -> info readline)

Monday, January 8, 2007

GNU Readline

Today I was playing around with the command-line version of Factor. I am one of those guys who don't wanna touch the mouse whenever possible. So the command line is always a good option esp. when you have completion available. As far as I can see Factor doesn't use the GNU readline library. But there is a cheap workaround. Just download rlwrap and you can wrap readline around Factor. Installation is a piece of cake. Next step is to have command completion in Factor. So you must tell rlwrap all the words that are available in Factor.

Piece of cake: Just give rlwrap a file with all the words and you can call it like this:

rlwrap -f factor.words ./f -shell=tty

where all Factor words have been written in the file "factor.words".

So the question is: how do you get all the Factor words. Nothing easier than that. Factor is very reflective. What you have to do in the Factor listener is this:


all-words
[ word-name ] map
"allcomms.txt" <file-writer>
swap
[ dupd swap stream-write stream-terpri ] each-with
stream-flush


Just for cosmetic reasons I sorted this file with "sort" in the GNU/Linux shell:

sort allcomms.txt > factor.words

Per default some characters are word separators in rlwrap. Unfortunately "-" too which is heavily used in Factor. Therefore just define all word breaking characters leaving out the dash. I put the whole thing in a file called "rf" and that's it's content:


rlwrap -b '(){}[],+=&^%$#@"";|\' -f factor.words -r ./f -shell=tty

(Added also the -r option which remembers words you type that are not in the completion file.)

I run Factor from the command-line by invoking "rf" and when I need the user interface I call "ui" in the Factor listener.

In the Factor listener you can also complete words. It's actually much better because its fuzzier. Whereas in the command-line with rlwrap you have to type in the first correct letters.

Sunday, January 7, 2007

FFT

Wrote FFT in Factor. Developing is very nice. Just the final code looks a bit ugly because of all the stack operations. I guess that's the price you have to pay for a stack based programming language.


IN: fft

USING: arrays sequences math kernel ;

: omega ( n -- n )
recip -2 pi i * * * exp ;

: n^v ( n v -- w )
[ ^ ] map-with ;

: v^n ( v n -- w )
swap n^v ;

: even ( seq -- seq )
2 group 0 <column> ;

: odd ( seq -- seq )
2 group 1 <column> ;

: two ( seq -- seq )
1/2 v*n dup append ;

: twiddle ( seq -- seq )
dup length dup omega v^n v* ;

: fft ( seq -- seq )
dup length 1 =
[ dup odd fft two twiddle swap even fft two v+ ] unless ;

PROVIDE: demos/fft ;

Haar in Factor

So the journey went on today. Tried to implement the Haar transformation. Slava already wrote it but I wanted to do it on my own. Slava's version is much more condense whereas mine looks like real beginner's code. I must apologize again but I'm a rookie if it comes to stackbased programming.

Here we go:


IN: haarwavelet
USING: sequences math kernel ;

: sdup ( x y -- y x x )
swap dup ;

: get-avgs-diffs ( avg-diff -- diff avg avg )
first2 sdup ;

: mean ( avg -- avg-next )
get-avgs-diffs 2 group [ first2 + 2 / ] map ;

: append-diffs ( diff avg diff-next -- avg diff )
rot append ;

: make-avg-diff ( avg diff -- avg-diff )
{ } swap add swap add* ;

: diffs ( avg avg-next -- avg-next diff )
dup rot 2 group 1 [ - ] 2map
append-diffs make-avg-diff ;

: concat-first2 ( avg-diff -- haar-result )
first2 append ;

: haar-finished? ( avg-diff -- avg-diff bool )
dup first length 1 <= ;

: mean&diffs
mean diffs ;

: haar-wavelet ( avg-diff -- avg-diff )
haar-finished?
[ mean&diffs haar-wavelet ] unless ;

: haar ( avg-diff -- haar-result )
haar-wavelet concat-first2 ;

: rev-diffs
sdup first2 length dup rot length + swap - swap
second swap tail make-avg-diff ;

: frame-x-with-y ( x y -- y x x y )
dup rot dup rot ;

: -rswap ( x y z -- y x z )
-rot swap ;

: rev-mean
frame-x-with-y + -rswap - make-avg-diff ;

: rev-means
dup first2 [ rev-mean ] 2map flatten ;

: rev-means&diffs
rev-means rev-diffs ;

: haar-inv-finished?
dup second length zero? ;

: haar-wavelet-inv ( avg-diff -- avg-diff )
haar-inv-finished?
[ rev-means&diffs haar-wavelet-inv ] unless ;

PROVIDE: demos/haarwavelet ;


You can use it like this:

{ { 56 40 8 24 48 48 40 16 } { } } haar-wavelet haar-wavelet-inv






In Ocaml it would look like this:


let rec haar ?(s=[]) ?(d=[]) l = match l, s with
| ([] | [_] as s), [] -> s @ d
| [], s -> haar ~s:[] ~d s
| h1::h2::t, s -> haar ~s:(h1+h2::s) ~d:(h1-h2::d) t
| _ -> invalid_arg "haar";;


Not bad either!

I'd say the actual core lines of my Factor code is this:

: haar-wavelet ( avg-diff -- avg-diff )
haar-finished?
[ mean&diffs haar-wavelet ] unless ;

This is very terse, too.

I can't really say why I am so thrilled by Factor. I think it's the interactivity. It doesn't really feel like programming. It feels more like talking to Factor.

Haar code is of course not finished. It would need some polishing. Next things I wanna try is the help and unit testing facility of Factor. Stay tuned!

Saturday, January 6, 2007

First Steps with Factor

Today I did my first steps in Factor a stackbased programming language developed mainly by Slava Pestov. This guy must be a bloody genius!! Factor's development environment is great because it is very interactive. I never had the chance to get access to a Lisp Symbolics box but Factor must come very close to it. Slava wants to make Factor the best stackbased programming language. Hey, Slava, you already did!

So I played around with it and wrote the Hello programs of the Lisp world: factorial and fibonacci. Here we go:



: factorial ( n -- n! )
dup 1 <=
[ dup 1 - factorial * ] unless ;

: fibonacci ( n -- fib-n )
dup 1 <=
[ dup 1 - fibonacci swap 2 - fibonacci + ] unless ;



Looks strange and bizarr. But once you get the hang of it you never wanna stop.

I wrote the Factor code in Emacs. There is a factor mode file in the Factor distribution. The factor-listener function is broken (telnet function is not available any more in the latest release 0.87). But there is so much interactivity in the Factor listener that you don't need Emacs for it.

So these are the steps you have to do for Emacs integration:
1.) Add the following lines to your .emacs file:

(load-file "path-to/Factor/libs/factor.el")
(server-start)


2.) In Factor load the Emacs library from the listener

"libs/emacs" require


That's it. When you want to edit code press 'C+e' in Factor, choose the file from the pop-up, switch to your Emacs session and happy factoring.

Helpful functions in the listener:

  • see, e.g "\ dup see" to see definition of duplicate
  • help, e.g. "\ dup help" to get online help for duplicate
  • where, e.g. "\ send-button-up where" to see in which file the word (Factor term for a function) 'send-button-up' is defined
  • edit, e.g. "\ send-button-up edit" opens file where 'send-button-up' is defined and jumps to the appropriate line


Thank you, Slava!!!