Factor Pattern Matching Additions

I've made a couple of additions to the pattern matching library I wrote for Factor. The idea came from a suggestion from Slava in #concatenative.

The main addition is a 'match-replace' word. This matches an object against a pattern and constructs a new object given a second pattern. The second pattern can use pattern matching variables from the first pattern to control the object construction. Here are some examples:

USE: match
MATCH-VARS: ?a ?b ?c ;

{ 1 2 } { ?a ?b } { ?b ?a } match-replace .
! => { 2 1 }

TUPLE: foo one two ;
{ 1 2 { 3 4 } } { ?a _ { _ ?b } } T{ foo f ?a ?b } match-replace .
! => T{ foo f 1 4 }

1 2  T{ foo f ?a ?b } T{ foo f ?b ?a } match-replace .
! => T{ foo f 2 1 }

This is built on top of a 'replace-patterns' word which replaces pattern matching variables with the relevant symbol values in the accessable namespaces:

{ 1 2 } { ?a ?b } match [
  { ?b ?a } replace-patterns
] bind .
! => { 2 1 }

These words have been added to the 'libs/match' library and should appear in the darcs version of Factor soon. They are in my repository if you want them now.

Just for fun I created a 'shuffle' word that lets you do stack shuffling via pattern matching. The implementation of the word is complex as it manipulates Factor's datastack directly:

: shuffle ( pattern1 pattern2 -- )
  dupd >vector >r >vector >r length >r 
  datastack clone r> over length swap - 2dup
  tail r> r> match-replace 
  >r head r> append set-datastack ;

As it uses 'datastack' and 'set-datastack' this word cannot be compiled. I haven't added it to the library for this reason and it encourages complex stack effects which should be avoided but it's pretty neat that Factor allows this sort of thing to be written.

It takes two patterns on the stack. The first is how the stack looks now, the second is how it should look after the shuffling. Here's some examples of how standard Factor stack shuffling words look using this method:

! drop
1 2 3 { _ } { } shuffle .s clear
! => 1 
!    2

! nip
1 2 3 { _ ?b } { ?b } shuffle .s clear
! => 1 
!    3

! pick
1 2 3 { ?a ?b ?c } { ?a ?b ?c ?a } shuffle .s clear
! => 1
!    2
!    3
!    1

! 2dup
1 2 3 { ?a ?b } { ?a ?b ?a ?b } shuffle .s clear
! => 1
!    2
!    3
!    2
!    3

Categories: factor

Search and Replace with Parser Combinators

I've added some code to the Factor parser combinator library to allow search and replace using parser combinators. The idea was to be able to do similar things with parser combinators that regular expressions are commonly used for. I've also started adding some simple reusable parsers for numbers, strings, etc.

The 'search' word takes a string and a parser off the stack. It returns a sequence of all substrings in the original string that successfully parse by the parser. The result returned in the sequence is actually the result returned by the parser. For example:

"hello *world* from *factor*" 'bold' search . 
 => { "world" "factor" } 

"one 100 two 300" 'integer' search .
 => { 100 300 }

"one 100 two 300" 'integer' [ 2 * ] <@ search .
 => { 200 600 }

The 'search*' word takes a string and a sequence of parsers off the stack. It returns a sequence of all substrings in the original string that successfully parse by any of the parsers in the sequence. It is functionally the same as combining parsers with the <|> combinator.

"hello 123 \"world\" from 456 factor" 'string' 'integer' 2array search* . 
 => { 123 "world" 456 }

The 'replace' word takes a string and parser off the stack. It returns the original string with all substrings that successfully parse by the parser replaced by the result of that parser.

"Hello *World*" 'bold' [ "<strong>" swap "</strong>" 3append ] <@ replace .
 => "Hello <strong>World</strong>"

The 'replace*' word takes a string and sequence of parsers off the stack. It does a fold, iterating through the sequence applying 'replace' using the parser and the results of the previous 'replace' call. The result is a string with all matching substrings from the parsers in the sequence being replaced by the results of those parsers.

"*Hello _World_*" 
  'bold' [ "<strong>" swap "</strong>" 3append ] <@
  'italic' [ "<emphasis>" swap "</emphasis>" 3append ] <@ 
  2array replace* .
 => "<strong>Hello <emphasis>World</emphasis></strong>"

Categories: factor

Cross Domain JSON with fjsc

I've added support to fjsc for cross domain AJAX calls to web services that use the JSON format.

Usually Ajax requests from a web page are limited to requesting resources on the server that the web page originated from. A way to work around this is to load cross domain Javascript by creating an HTML SCRIPT tag dynamically, setting the 'src' attribute to the resource required, and inserting it into the HEAD of the document. This results in the script being executed. Here is some jQuery code that demonstrates this:

  $("head/script#jsonrequest").remove();
  var script = document.createElement("script");
  script.id = "jsonrequest";    
  script.type = "text/javascript";
  script.src = "http://someotherdomain.com/test.js";
  $("head").append(script);

A problem with this approach is that if the src URL points to JSON data then it gets evaluated but you can't do anything with it since JSON is data, not code.

Bob Ippolito described the idea of JSONP. This is a JSON file served by a remote server that allows the resulting JSON to be wrapped in a function call named by a parameter passed to the URL of the service. This means the data is now executed by a function chosen by the web page author and can process the data. Something like this would be how you could use such a service:

function handler(data) { alert(data); }
$("head/script#jsonrequest").remove();
var script = document.createElement("script");
script.id = "jsonrequest";    
script.type = "text/javascript";
script.src = "http://someotherdomain.com/myapi?callback=handler";
$("head").append(script);

This is what I've added to fjsc. Two new words:

load-script ( url -- )

Dynamically add a script tag to the page that loads and evaluates the given URL

json-request ( url -- data )

Calls load-request to load and evaluate the given URL. The URL should be to a JSON service with a query parameter that allows a callback function name to be inserted into the JSON result. Use 'handle_json' as the callback name. This will result in the data from the service being left on the stack.

An example using Yahoo's image search:

"http://api.search.yahoo.com/ImageSearchService/V1/imageSearch?appid=YahooDemo&query=factor+language&output=json&callback=handle_json"
json-request 
"ResultSet" swap alien-property 
"totalResultsAvailable" swap alien-property alert

This makes the call to the service using the Cross Domain JSON functionality. It takes the 'ResultSet' member from the returned Javascript object, and the 'totalResultsAvailable' member from that to display in an alert box.

There are some security considerations to keep in mind when doing cross domain calls this way. The server receiving the request can inject any javascript into the result. What they can do is limited due to the Javascript sandbox but a carefully crafted injection could do bad things. They receiving server also has access to all the cookies and resources that the originating web page has. See here for some questions and answers on this approach.

Categories: factor, fjsc

Continuations added to fjsc

I've added support for continuations to the Factor to Javascript compiler. The public interface is the same as the standard Factor continuation support. Namely the 'callcc0', 'callcc1', 'continue' and 'continue-with' words.

This involved quite a few changes to the internals of the compiler. The Javascript generated code is now in continuation passing style (CPS). It makes the generated code harder to understand but exposes the continuations directly. This is what the expression '1 2 + alert' gets compiled to:

factor.push_data(1,
       function() {
         factor.push_data(2,
           function() {
             factor.find_word("+").execute(
               function() {
                 factor.find_word("alert").execute(factor.cont.next)
             })
           })
         })

I do no optimisation of the code yet so its not that efficient. I can work on that later as I'm more interested in getting this working at the moment.

Javascript does not have tail call optimisation so this form of transformation will eventually overflow the call stack given a long enough word definition. To work around this I keep a count of each continuation called and when it exceeds a threshold I pass the next one to setTimeout and exit immediately.

This has the effect of jumping out of the call stack and has the side effect of occasionally giving the browser some processing, which prevents the 'this script seems to be running for a long time...' type of error.

Another change is I've moved to using the jQuery library for the Ajax and DOM manipulation support. This seems to be easier to use when doing POST requests, and has some nice DOM routines. In the bootstrap.factor file that gets run on startup by the browser I have a few simple examples of calling jQuery from Factor:

: elements ( string -- result )
  #! Call JQuery's $ function
  window { "result" } "" "$" { "string" } alien-invoke ;
  
: html ( string -- element ) 
  #! Set the innerHTML of element using jQuery
  { } "" "html" { "string" } alien-invoke ;

: bind-event ( name element quot -- )
  >function swap { } "" "bind" { "string" "function" } alien-invoke ;

In the main REPL page I've added a DIV with the id 'playground' for experimenting with the interface. 'example1' creates a button in this div:

: example1 ( -- )
  "<button id='test'>Press Me</button>" "#playground" elements html ;

Clicking the button does nothing though. An event handler that calls a quotation can be added with 'bind-event':

: example2 ( -- )
  "click" "#test" elements [ "clicked" alert ] bind-event ;

Clicking the button now displays the alert. Continuations can be used from event handlers:

: example3 ( -- )
  [
    [
      >r "click" "#test" elements r> [ continue ] curry bind-event
      "Waiting for click on button" alert
      continue
    ] callcc0
    drop "Click done!" alert 
  ] callcc0 ;

This example captures a continuation and curries it to the '[ continue ]' quotation which is bound to the event. So clicking the button will run the continuation. This continuation is the "Click Done!" part of the word. Clicking the button will display that message. And it can be clicked multiple times to resume the continuation multiple times.

Other additions to the fjsc system include:

Retain Stack

The retain stack has been added. >r and r> work as expected.

Vocabulary Support

Words now belong to Vocabularies. I don't have USE:, USING: or IN: yet as I don't support parsing words. Instead there is "in", "use" and "using" which work in a similar manner:

"scratchpad" in
{ "kernel" "math" } using
"foo" use

Quotations on the server compilable to Javascript

Previously you could only compile strings of Factor code to Javascript. Now you can compile quotations as well. This allows generation of Javascript without have to do any string concatenation. When compiling from a quotation, the vocabs for the words in the quotation will match the vocabs for the words that are executed in Javascript. When compiling strings, as there is no USE information, it looks up the word in the current USE list at run time.

"1 2 +" fjsc-parse fjsc-compile .
[ 1 2 + ] fjsc-parse fjsc-compile .

On my list to add are:

• DOM wrappers
• A better REPL
• Better code generation
• Documentation
• Threads and Concurrency

Categories: factor

Parser Combinator enhancements

While working on the Factor to Javascript compiler I struck some performance issues with how I was using Parser Combinators.

The problem manifested when parsing word definitions. For example:

: foo ( a b -- c d ) one two ;

This would parse very quickly. But as the identifiers became longer, or more got added, it got much slower:

: foo ( a b -- c d ) oneoneoneoneone twotwotwotwotwo ;

The reason for this is related to how the 'identifier' parsing word was defined. It can be demonstrated with a simple number parser as well:

[ digit? ] satisfy <+>

This is a parser that accepts one or more digits in a sequence. Like all parsers it returns a lazy list of successful parses. If at some point a parser fails to parse something successfully then the lazy list is traversed trying each parse in turn. For the digit parser you can see it creates an item in the list for each possible string of numbers:

"1234567890" [ digit? ] satisfy <+> parse [ . ] leach
  => T{ parse-result f { 49 50 51 52 53 54 55 56 57 48 } { ... } }
     T{ parse-result f { 49 50 51 52 53 54 55 56 57 } { ... } }
     T{ parse-result f { 49 50 51 52 53 54 55 56 } { ... } }
     T{ parse-result f { 49 50 51 52 53 54 55 } { ... } }
     T{ parse-result f { 49 50 51 52 53 54 } { ... } }
     T{ parse-result f { 49 50 51 52 53 } { ... } }
     T{ parse-result f { 49 50 51 52 } { ... } }
     T{ parse-result f { 49 50 51 } { ... } }
     T{ parse-result f { 49 50 } { ... } }
     T{ parse-result f { 49 } { ... } }

These are all valid parse results for the given input string. Most of the time when parsing a number you dont want all those extra results. You either want the entire number of nothing at all. There's no point having all those extra results being backtracked and taking time. By knowing in advance that we are only interested in the all or nothing result we can use a different word to that of <+>. The document I based the Factor parser combinators on outlines the solution to this and I implemented it in Factor. First a parser combinator called 'only-first' allows us to only get the first succesful result:

TUPLE: only-first-parser p1 ;

M: only-first-parser (parse) ( input parser -- list )
  #! Transform a parser into a parser that only yields
  #! the first possibility.
  only-first-parser-p1 parse 1 swap ltake ;

It takes an existing parser and uses 'ltake' to only return the first result in the list of successes. The existing combinators for matching sequences, <*> and <+>, can have alternatives for only matching the longest sequence:

LAZY: <!*> ( parser -- parser ) <*> only-first ;
LAZY: <!+> ( parser -- parser ) <+> only-first ;

Using <!+> instead of <+> in the number parser is now more efficient:

"1234567890" [ digit? ] satisfy <!+> parse [ . ] leach
  => T{ parse-result f { 49 50 51 52 53 54 55 56 57 48 } { ... } }

"1234567890" [ digit? ] satisfy <+> parse list>array length .
  => 10

"1234567890" [ digit? ] satisfy <!+> parse list>array length .
  => 1

By making sure identifiers and numbers used these optimised parser combinators I was able to make parsing of longer word definitions much more efficient. The new words have been added to the 'parser-combinator' module.

Categories: factor

Factor to Javascript compiler updates

I've done some minor updates to my compiler from a subset of Factor to Javascript. The updates are now running on the fjsc test page and available from my repository:

darcs get http://www.bluishcoder.co.nz/repos/factor

Javascript FFI

An FFI interface to Javascript modelled after Factor's 'alien-invoke'. This allows calling any method of a Javascript object. 'alien-invoke' takes three arguments on the stack. The first is an array of strings defining the type of the object returned by the Javascript call. The second is the name of the method. The third is an array of strings defining the type of the objects expected as parameters to the method. The resulting code generated by 'alien-invoke' expects the object to call the method on to be on the top of the stack. Here are some examples that work on the test page:

: my-alert ( string -- )
  #! Display an alert box with the given string.
  #! The 'window' word returns the 'window' javascript object
  window { } "alert" { "string" } alien-invoke

"hello world!" my-alert

: my-substr ( end start string -- string )
  #! Return the substring of the given string
  { "string" } "String.prototype.substr" { "number" "number" } alien-invoke ;

6 1 "Hello World" my-substr my-alert

The FFI is still a work in progress. As I write wrappers for DOM routines I expect it to change.

Parser Changes

The parser now supports escaping words with '\ word', stack effects and comments:

1 2 \ + execute
: square ( a -- b )
  #! Square the argument
  dup * ;

Some improvements to parser combinators have been made to speed up the parser as well. The number of backtracking possibilities has been dramatically reduced.

Ajax Support

Simple Ajax support has been added in the form of 'http-get' and 'run-file'. 'http-get' takes an URL on the stack and returns the data at that URL as a string. 'run-file' will compile and evaluate the Factor code at the given URL. Note that due to Ajax limitations these can only be URL's on the local server. I may add proxy capability to work around this in the future:

"/responder/fjsc-resources/bootstrap.factor" http-get
"/responder/fjsc-resources/bootstrap.factor" run-file

The limitations with the Ajax support also include the fact that they are run asyncronously. So they aren't much good in running programs, more for interactive use at the REPL. I'll either make this synchronous in the future or add continuations to the compiler.

Bootstrap Factor file

A file located at /responder/fjsc-resources/bootstrap.factor can contain Factor code that is compiled and run when the 'bootstrap' word is run. From the reply run 'bootstrap' and it will execute the code.

Todo

I plan to add (in no particular order):

• Continuations
• The ability to compile Factor quotations from the server into Javascript without having to have the Factor code in strings first. This way any code on the server can be compiled to Javascript and removes the need to manually craft Javascript to send to the client in web applications.
• Improve the code generation.
• Wrap various DOM routines, etc
• Write a better REPL in Factor itself

Categories: factor

Factor interface to Google Search

About a year ago I wrote some Factor code to use the Google SOAP API to run automated Google searches. I wanted to put together the results of a quick search so I fixed the code to work with the latest Factor release. The code is in my repository and will hopefully eventually make to the main Factor repository. You can get it with:

darcs get http://www.bluishcoder.co.nz/repos/factor

An example of usage is:

"mygooglekey" "factor language" google-search

This will return a sequence of 'search-item' tuples. These contain the url, snippet and title of the result from the search request. Only the top 10 results are currently returned.

The 'mygooglekey' must be the Google SOAP API key. The bad news is Google deprecated this api a couple of weeks ago. They are keeping the service running but aren't providing any new keys. The intent is to migrate people to the Ajax search API. Unfortunately this API only runs within browsers so is not much good for automated server side searches. There's some discussion on the Google API forums about this change.

So if you have a Google key for the SOAP service this code might be useful. Otherwise it won't be. If you google around you might be able to find keys...

Here's an example of usage (it may take a few seconds to run): http://factor.bluishcoder.co.nz/search-rankings. It gives the top ten results from a few google searches on Sit and Go Poker Tournament Strategy. It also gives the pagerank of the sites in the search. The pagerank was obtained from the trynt pagerank API service. The pageranks are cached so I don't keep hitting the trynt service.

Categories: factor

Compiling Factor to Javascript

A while back I wrote a toy Factor to Javascript compiler to use as an example in my Compilers and Interpreters post. I ended up using a different example in that post so didn't do any further work on it.

Yuuki from #concatenative is writing a Factor tutorial and I thought it might be useful to put something online to try some of the examples so I decided to do more work on it.

The current work in progress is here. Entering a simple Factor expression in the textarea and clicking 'submit' will send the factor code to the server where it is compiled to Javascript. The Javascript is returned to the browser and evaluated. The compiled javascript is displayed as well as the current stack contents.

It's pretty basic at the moment - it's more of a compiler from a stack based language with similar syntax to Factor rather than an actual Factor compiler. I hope to expand on it though. It can handle arrays, quotations, conditionals, some library words, some combinators and defining new words. The built in functions are:

• dup
• drop
• nip
• over
• +
• -
• *
• /
• .
• call
• map
• reduce
• clear
• =
• if
• t
• f
• empty?

Here are some examples you might like to try:

{ 1 2 3 } [ 2 * ] map
{ 1 2 3 } 0 [ + ] reduce
"hello world!" .
: fac dup 1 = [ ] [ dup 1 - fac * ] if ;
5 fac .
: product 1 [ * ] reduce ;
{ 2 3 4 } product
5 { 1 2 3 } [ over + ] map

I'll add more words and functionality over soon, as well as trying some DOM and Ajax functionality. Leave a comment if there's a feature you'd like to see!

Source code is in my repository and will be in the main Factor repository when Slava pulls from it.

Categories: factor, javascript

Factor gets XML-RPC

Factor has an XML-RPC library thanks to Dan (littledan in #concatenative). Slava has a post demonstrating how to use it to talk to the paste.lisp.org pastebin.

Categories: factor

Violence in Wellington

If you are at all concerned with personal safety in Wellington and opposed to violence then please consider contributing to this petition.

On Sunday morning the brother of a friend of mine was attacked in Wellington city while attempting to help in an altercation. He was severely beaten and kicked in the head and is fighting for his life in the hospital.

The attacker, [name removed], 21, a labourer from Newtown, looks likely to apply for bail according to the news reports.

The intent of the petition, started by the victims brother, Richard, is "to simply give a public opinion to the courts, and encourage this man's sentence to be the maximum to in turn keep him off the streets as long as possible."

Meanwhile please spare a thought for Andrew fighting for his life in hospital.

Categories: misc