« Filosofer som actionhjältar | Main | Fortsatt stavning av "Henning Mankell". Samt lite om agrep »

april 22, 2004

Programspråket Icon och stavningen av "Henning Mankell"

Jonas Söderström på Blind Höna riktade uppmärksamheten på problemet att veta exakt hur en känd svensk författare stavar sitt namn. Är det "Menking Hannell", "Manking Hannall", "Manning Henkell"? Artikeln visar en massa alternativ.

Det är enkelt att skapa alla dessa varianter genom permutationer. Anledningen till denna blogganteckning är att visa hur elegant man kan göra detta i programspråket Icon. Själv använder jag Unicon, en efterföljande och superset av Icon, som i sin tur är en utveckling av och efterföljare till det fantastiska språket SNOBOL.

Problemformulering
Generera alla möjliga varianter av följande reguljära uttryck

  [HM][ea](nk|n|nn)(ing|ell|all)

där [HM] betyder endera bokstaven "H" eller bokstaven "M", och ing|ell|all innebär någon av strängarna "ing", "ell" eller "all". (Egentligen kan man skriva [HM] som (H|M), men vanligen används [...] för sådana "character classes".)

Både för- och efternamn genereras av detta uttryck med restriktionen att de inte får börja på samma bokstav.

En Icon-lösning på detta problem ser ut så här.

procedure main()
   every x:= HM() do write(x)
end

procedure HM()
   suspend ("H" || _HM() || " " || "M" || _HM()) |
      ("M" || _HM() || " " || "H" || _HM())
end

procedure _HM()
  suspend (!"ea" || !["nk","n", "nn"] || !["ing","ell","all"]);
end

Lite förklaringar av Icon-koden:
Operatorn ! (utropstecken) gör själva genereringen, när man använder every.

!"ea" motsvarar det reguljära uttrycket [ea], och genererar både "e" och "a", dvs alla tecken som finns i strängen. Kontruktionen !["ing","ell","all"] motsvarar det reguljära uttrycket (ing|ell|all) och genererar alla element i listan.

| (enkelt "pipe"-tecken) innebär alternation, dvs "eller". Man skulle kunna uttrycka !"ea" på följande sätt: !("e"|"a").

|| (dubbla "pipe"-tecken) är strängkonkatenator, dvs slår ihop två strängar.

Funktionen suspend är en speciellt funktion som håller reda på var någonstans i genereringen man är. Denna typ av funktioner kallas även för generator eller closure.

Ovanstående program skapar 648 namnvarianter, varav samtliga är med i listan på den ovan nämnda sajten. Programmet pattern_generation.icn är en utbyggd version som visar lite mer information etc. Här är output från detta program.

Not: skulle vi inte haft restriktionen att för-/efternamn inte får börja på samma bokstav skulle programmet bli ännu enklare:


procedure main()
   every x:= (HM2() || " " || HM2()) do write(x)
end

procedure HM2()
  suspend !"HM" || !"ea" || !["nk","n", "nn"] || !["ing","ell","all"]
end

Detta program genererar 1298 namn.


Lite mer om Icon
Icon har många andra trevliga features, framförallt ett mycket kraftfullt system för pattern matching (influerat av SNOBOL) som är helt olikt den numera förhärskande metoden med reguljära uttryck.

Förutom ovan nämnda sajter finns det några PDF-böcker om Icon/Unicon som rekommenderas:

Ralph E. Griswold, Madge T. Griswold: The Icon Programming Language (3rd ed)
Clinton Jeffery, Shamim Mohamed, Ray Pereda, Robert Parlett: Programming with Unicon (eventuellt en blivande O'Reilly-bok).
Thomas W Christopher: Icon Programming Language Handbook


För mer om reguljär uttryck (regular expressions) se t.ex. blogganteckningen Reguljära uttryck.

Posted by hakank at april 22, 2004 01:39 EM Posted to Reguljära uttryck etc | Språk