maj 03, 2009

spipat: SNOBOL/SPITBOL-patterns i C++ och Python

spitpat är ett C/C++-bibliotek som implementerar SNOBOL/SPITBOL-patterns för C++ och Python. Så här presenteras spitpat i distributionens fil README:
This is a transliteration (largely mechanincal translation) to C99
of the GNU Ada Translator (GNAT) SPITBOL.Pattern (spipat) package by
Robert Dewar, the creator of SPITBOL GCC v3 provides all needed
features.

The primary goal is to enable embedding SNOBOL4 style patterns in
popular scripting languages (ie; Ruby, Python, Perl, JavaScript),
which are almost universally written in C.

Testing and programming pattern construction in C is painful, due to
the lack of operator overload. To hasten testing, I've written a C++
wrapper "Pattern" around the C spipat library. The goal is to enable
testing, and provide an experience familiar to SNOBOL programmers. A
more pure C++ approach might be to use method chaining to construct
patterns, and to implement the entire package as a template that takes
an arbitrary scalar type to represent a character.
Naturligtvis är det Phil Budne som gjort denna translitterering; det är han som ligger bakom den fria SNOBOL4-implementationen CSNOBOL4 full av klockor och visslor.

C++
Så här kan SNOBOL/SPITBOL se ut i C++: 
#include 
#include 

using namespace std; 

#include 

int main() {
 string subject1("Hello World!");
 string hello("Hello");
 Pattern hello_pattern(hello);
 Pattern world_pattern("World");
  
 // pattern w/ concatenation
 Pattern p1 = hello_pattern & ' ' & world_pattern;
 Pattern p2 = hello_pattern & ' ' & world_pattern & Arb();
 Pattern p3 = hello_pattern & Arb() & world_pattern;

 Matchres m1;
 cout << "p1: " << p1 << "\n";
 cout << "p2: " << p2 << "\n";
 cout << "p3: " << p3 << "\n";
 cout << "subject1 ~ p1: " << Match(subject1, p1) << "\n";
 cout << "subject1 ~ p2: " << Match(subject1, p2) << "\n";
 cout << "subject1 ~ p3: " << Match(subject1, p3) << "\n";

 return(0);
}
Pythonstöd
Än så länge finns det - av de agila programspråken - endast stöd för Python men ovanstående antyder att det även kan komma stöd för andra programspråk. Det finns ett par exempel i distributionen, t.ex. nqueens där det emfatiska området är de SNOBOL-specifika delarna 
# from Victor Berstis' Minnesota SNOBOL4 distribution
# N queens problem, a string oriented version to demonstrate the power
# of pattern matching.

# translated to Python w/ spipat by Phil Budne

from spipat import *

n = 8
nm1 = n - 1
np1 = n + 1
nsz = n * np1

# This pattern tests if the first queen attacks any of the others:
test = break_("Q") + "Q" + (arbno(len_(n) + "-") + len_(n) + "Q"  |
			    arbno(len_(np1) + "-") + len_(np1) + "Q" |
                            arbno(len_(nm1) + "-") + len_(nm1) + "Q")
p = len_(nm1) * 'x' + len_(1)
l = "Q" + "-" * nm1 + " "

solution = 0
def solve(b):
    global solution

    if len(b) == nsz:
        solution = solution + 1
        print "Solution number", solution, "is:"
        while len(b) >= np1:
            print b[0:np1]
            b = b[np1:]
    else:
        # Add another row with a queen:
        b = l + b
        # "LOOP"
        i = 0
        while i < n:
            i += 1
            if not test.match(b):
                solve(b)

            # "NEXT"
            # Try queen in next square:
            m = p.match(b)
            if m:
                b = m.repl('-' + m.dict()['x'])

solve('')
Se även
* För andra SNOBOL/SPITBOL-relaterade saker, se www.snobol4.org.
* David Shield har nyligen skrivit en del SNOBOL/SPITBOL-relaterat på sin blogg The Wayward Word Press , t.ex. Announcing New LinkedIn Group, SPITBOL , Announcing spitbol, a New Project Hosted at Google Code.

Posted by hakank at 09:42 FM Posted to SNOBOL/SPITBOL | Comments (0)

april 28, 2009

Karl Wettin intervjuas om Lucene and Mahout

Karl Wettin har blivit långintervjuad i Interview with Karl Wettin on Lucene and Mahout.

Grant Ingersoll talks to Karl Wettin, an Apache Lucene and Mahout Committer and independent Lucene Solr consultant. Karl talks about lexically complex European languages, using terms with shingles to simplify queries rather than complex span queries, and improving spellchecking with reinforcement learning, and looking at Mahout NLP.

Kul, Kalle!

Via Clas på Frisim som faktiskt lyckades avkoda att "Wolkan Schellestum" är mitt namn. (Jag har inte lyckats lyssna på ljudversionen; där är det kanske tydligare.)

Det skrevs för övrigt om Kalle anno 2003 i Silvertejp.

Posted by hakank at 09:07 EM Posted to Machine learning/data mining | Comments (0)

april 10, 2009

Mitt föredrag på SweConsNet Workshop 2009: "Learning Constraint Programming (MiniZinc, JaCoP, Choco, Gecode/R, Comet, Gecode): Some Lessons Learned"

Sedan jag startade min engelskspåkiga My Constraint Programming Blog kring årsskiftet har jag fått flera nya kontakter och haft mycket intressanta maildiskussioner.

Några av dessa diskussioner har lett till att jag kommer att prata på SweConsNet Workshop 2009 27 maj 2009 i Linköping. SweConsNet (Network for Sweden-based researchers and practitioners of Constraint programming) presenteras mer här (Uppsala Universitet), workshoppen beskrivs även i bloggartikeln SweConsNet Workshop 2009.

Titeln på föredraget är Learning Constraint Programming (MiniZinc, JaCoP, Choco, Gecode/R, Comet, Gecode): Some Lessons Learned och kommer att innehålla findings funna under tiden jag kollat in och lärt mig olika constraint programming-system (och jag lär mig nya saker hela tiden), jämförelser mellan systemen och kanske ett och annat önskemål.

För mer om de system som kommer att tas upp, se vidare :

Tiden före den specialinriktade bloggen skrevs om dessa saker (främst MiniZinc, JaCoP samt Gecode/R) på denna svenska blogg i kategorin Constraint programming.

Under tiden jag förbereder föredraget planerar jag att blogga mer systematiskt kring de olika saker som kommer att tas upp.


Not: Jag skrev ungefär samma saker häromdagen i My talk at SweConsNet Workshop 2009: "Learning Constraint Programming (MiniZinc, JaCoP, Choco, Gecode/R, Comet, Gecode): Some Lessons Learned", men tyckte det kunde vara kul att skriva om det här också.

Posted by hakank at 09:52 FM Posted to Constraint Programming | Comments (0)

mars 16, 2009

Lite om vad som händer på andra bloggen: My Constraint Programming Blog

Som tidigare nämnts är det inte här utan på My Constraint Programming Blog ("Min villkorsprogrammeringsblogg") jag numera mest håller till.

Här är en liten sammanfattning om vad som hänt där och i samband med detta.

* En stor drös med Comet modeller på My Comet page. Några exempel:


* En mycket mindre drös med MiniZinc-modeller på My MiniZinc page.

Men de modeller som tagit mest tid är följande

Nonogram
Här är de blogganteckningarna som presenterar de olika varianterna, i normal sorterad tidordning:
1) More Comet models, e.g. Nonogram, Steiner triplets, and different set covering problems som presenterade den första Nonogram-modellen. Långsam var den.
2) Comet: regular constraint, a much faster Nonogram with the regular constraint, some OPL models, and more presenterade en mycket snabbare Nonogram-modell som använder principen bakom reguljära uttryck (villkoret regular).
3) samt slutligen Comet: Nonogram improved: solving problem P200 from 1:30 minutes to about 1 second där jag hittade lite mer saker att förbättra, bl.a. med hjälp av en av mina husgudar Pascal Van Hentenryck och som är en av skaparna av just Comet.

Ungefär samtidigt kom jag i kontakt med gänget bakom Gecode (C++ baserat), det snabbate constraint programming-systemet som jag känner till. Roligt nog har de nu lagt in samma förbätring i sitt Nonogramprogram.


Pi Day Sudoku
I lördags var det Pi-dagen (3.14 som vissa skriver den 14 mars) och som hyllning skapade Brainfree Puzzles några dagar tidigare en tävling: Pi Day Sudoku 2009. Det är som vanliga Sudoku fast med knorr: förutom att det ska vara 1..9 på samtliga rader och kolumner ska det finnas exakt tre stycken Pi. Till detta kommer att man inte har de vanliga kvadratiska regionerna som kräver samma fördelning av siffror utan det är även olika former på regionerna (kolla sajten så förstår ni bättre). Jag har slutat med att lösa Sudokuproblem för hand, däremot var de speciella kriterierna ett intressant problem att modellera med villkorsprogrammering (constraint programming).

Första modellen, som var rätt långsam, skrevs om i Pi Day Sudoku 2009. Efter lite funderande, och framförallt diskuterande med Mikael Zayenz Lagerkvist (från sagda Gecode team), snabbades modellen upp avsevärt. Detta beskrevs i Solving Pi Day Sudoku 2009 with the global cardinality constraint.

Till förfång för alla de som som söker på Pi Day Sudoku har varken lösningen på problemet eller modellerna presenterats på bloggen (det blir inte förrän tävlingen är över).


Gecode 3.0.0
Vi får ju inte heller glömma att version 3.0.0 av Gecode släpptes för några dagar sedan. Jag rekommenderar varmt den mycket trevliga introduktion till modellering i Gecode: Modeling with Gecode (PDF).

I och med att version 3 har släppts kommer det inom kort även stöd för det grafiska verktyget Gist till MiniZinc, dvs när man har Gecode/FlatZinc som lösare (och det har man alltid som förstaval). Det ser jag mycket fram emot.


Till sist: MiniZinc Challenge 2008
Resultat av constraint programming-tävlingen MiniZinc Challenge 2008 kom förra vecka. Inte förvånande vann Gecode. Mer om detta skrevs i MiniZinc Challenge 2008 Results.

Posted by hakank at 08:34 EM Posted to Constraint Programming | Reguljära uttryck etc | Comments (0)