Bluish Coder

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

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' [ "&lt;strong>" swap "&lt;/strong>" 3append ] <@ replace .
 => "Hello &lt;strong>World&lt;/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' [ "&lt;strong>" swap "&lt;/strong>" 3append ] <@
  'italic' [ "&lt;emphasis>" swap "&lt;/emphasis>" 3append ] <@ 
  2array replace* .
 => "&lt;strong>Hello &lt;emphasis>World&lt;/emphasis>&lt;/strong>"

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.

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

i

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

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