hakank.blogg

« Bloggforum 3.0: 19 november | Main | Recension: Lars Våge, Erik Stattin och Gunnar Nygren: Bloggtider »

oktober 24, 2005

Programspråket J: en kort reseskildring

Introduktion

Som en del kanske vet tycker jag programspråk är fascinerande och försöker följa rådet i boken The Pragmatic Programmer att lära mig ett nytt programspråk om året (helst ett nytt paradigm), vilket funkar ibland.

Ett programspråk som jag har kollat in tidigare men av olika skäl inte mer än ytligt är J som är en utveckling (utökning) av APL (som jag även kollat in men det kräver ett eget tangentbord med speciella tecken så det var inte så skoj). J har i princip samma konstruktioner, men man använder rena ASCII-tecken i stället.

De senaste veckorna har jag faktiskt lyckats lära mig en del av språket. Det följande är egensinnig introduktion av J och visar inte språkets alla styrkor; man bör snarare se det som en reseskildring av några av mina upptäckter i språket.

Kort om J

J är ett mycket kärnfullt (och kärvt) språk som väl än mer än Perl ser ut som line noise. Det tillhör programmeringsparadigmen funktionella språken (ungefär som Haskell, Scheme, Lisp och liknande) samt de s.k. vektorspråken såsom Matlab, GNU Octave och R (ett av mina favoritspråk).

Det som är speciellt med J är dess arv från APL, nämligen att det finns många färdiga funktioner och dessa är definerade med ett eller ett fåtal tecken. Det gör att man inte behöver skriva långa avhandlingar för att skapa ett program. Såtillvida är det ett VHLL (Very High Level Language) såsom Perl, Ruby och Python, samtliga mycket trevliga programspråk. Man kan också notera att J är, liksom de tre nämnda språket, ett interpreterande språk (scriptspråk, eller som det nu bör kallas pragmatiska eller agila programspråk). Och det är en stor poäng eftersom språket inbjuder till att sitta och leka vid prompten eller i GUI:t.

Några installationskommentarer

* Program till Linux, Windows och Mac finns att hämta hos Jsoftware.
* Mer information såsom dokumentation om språket och systemet finns i Se även-avsnittet nedan.

Program / funktioner

Låt oss ta några exempel på saker som har skrivits här eller annorstädes den senaste tiden. När jag lär mig nya programspråk finns det en del standardexempel som alltid implementeras, t.ex. konkordanstabeller, läsa in filer för att matcha med reguljära uttryck, skapa hashtabeller etc. Några av dessa standardexempel beskrivs även här nedan.

Text i fetstil anger resultatet av en operation. Nota bene: NB. anger en kommentar.

Summan av 7 första primtalen = 666

Henrik Sundström glada upptäckt att summan av kvadraten på de första 7 primtalen är 666 skrivs så här i J.


p: i. 7
2 3 5 7 11 13 17

(p: i. 7)^2
4 9 25 49 121 169 289

+/ (p: i. 7)^2
666


Förklaring:

p: skapar det i:te primtalet.
i. n genererar talen 0 .. (n-1).
^ är naturligtvis "upphöjt till"
+/ gör en summering av samtliga tal i listan, där / anger att man ska göra något (här summera) över alla element i listan och reducera till ett enda tal. (Mer tekniskt lägger / till "+" mellan samtliga element i listan. Det kallas för "insert".)

Om man nu vill testa om det finns flera roliga sådana tal kan man göra en "running sum", med +/\. Det verkar dock inte finnas några fler roliga sådana tal. I alla fall inte bland de första 20 primtalen.


+/\ (p: i.20x)^2
4 13 38 87 208 377 666 1027 1556 2397 3358 4727 6408 8257 10466 13275 16756 20477 24966 30007

NB. Ladda in liten färdiga rutiner, t.ex. diff
load 'strings regex misc files'

diff +/\ (p: i.20x)^2
9 25 49 121 169 289 361 529 841 961 1369 1681 1849 2209 2809 3481 3721 4489 5041


Man kan notera att allt inte är konstiga symboler och om det är för förvirrande kan man definera symbolerna till namn. Tack och lov finns det många färdigdefinierade funktioner lätt åtkomliga, t.ex. diff som i exemplet ovan, som ger differensen mellan två närstående tal i listan.

Jämförelse med naturliga språk

Något som är speciellt utmärkande för J (och APL) är att man i dokumentationen presenterar idiom, fraser (phrases) som man som utvecklare bör lära sig att känna igen. Vilket nog är nödvändigt eftersom det annars är svårt att lära sig språket. Jämför med hur man lär sig naturliga språk: I början lär man sig ord och mindre fraser, varpå man sedan lär sig mer komplicerad grammatik och skapar fullständiga meningar etc.

Jämförelsen med naturliga språk är också något som genomsyrar hela J. I stället för funktioner pratar man om verb, variabler är substantiv (noun) etc. Denna fokusering på naturliga språk har även fått mig att fundera på hur jag just nu lär mig J och i förlängningen hur man lär sig programspråk. Jag använder dock termerna från den vanliga programmeringsvokabulären här nedan.

Man kan även tänka på hur barn lär sig språk: genom att leka med orden och språket för att se om det blir något av denna lek. Detta lekfulla angreppssätt känns naturligt i J, och är till viss del nödvändig eftersom dokumentationen kan vara rätt kärv emellanåt.

Språknära exempel

Eftersom mina intressen är både tal och språk har jag lekt lite med mer språknära problem, t.ex. fördelning av bokstäver i ord. Låt oss ta ett enkelt exempel.


NB. En tilldelning av en sträng till variabeln str
str =: 'hakan kjellerstrand'

NB. Skapar antal tecken som finns för respektive position i ordet.
NB. Dvs 'h' finns 1 gång, 'a' finns 3 gånger, liksom 'k' etc,
+/"1 = str
1 3 2 2 1 1 2 2 2 1 1 1

NB. Ordningen vilket bokstäverna i ovanstående listas
NB. visas får med "nub", dvs de unika bokstäverna
~. str
hakn jelrstd

NB. Och om man av någon anledning vill veta i vilken position en bokstav börjar i kan man
NB. använda följande funktion:
char_pos =:((>:&# @ ~. @ ]) - (+/ @ (+/\ @ (=@ ]))))
char_pos str
1 2 3 2 4 3 5 3 6 7 8 8 7 9 10 11 9 2 4 12


Det där med line noise är kanske inte så långt ifrån...

Thebes talmagi

Ett annat aktuellt exempel. I Thebes Gåta (i kommentarerna) gjorde följande talmagiska konstruktion: B A C H -> 2 1 3 8 (dvs Bach).

Uppdrag: Skapa ett program för en sådan konvertering.


alpha=: 'abcdefghijklmnopqrstuvxyzåäö0123456789'
str =: 'bach'

NB. Själva konverteringen.
NB. # ger antalet element i listan
NB. =/ matchar tecken för tecken
NB. :| transonerar vektorn
NB. , gör det till en fin lista
,(|:(alpha =/ str)) # (>:i.38)
2 1 3 8

NB. Som explicit definition:
convert=: 3 : 0
(,(|:('abcdefghijklmnopqrstuvxyzåäö0123456789' =/ y.)) # (>:i.38))
)

NB. Detta kan även skrivas på en rad där man använder strängdefinition
NB. convert=: 3 : '(,(|:(''abcdefghijklmnopqrstuvxyzåäö0123456789'' =/ y.)) # (>:i.38))'

convert 'bach'
2 1 3 8

Thebe-tvärsumma

Som en klo på kvällens kräfta skapar vi även "Thebe-tvärsumman".


NB. Tvärsumman från 'bach' definieras på följande sätt.
NB. +/ känner vi igenom från ovan, nämligen summan av talen i listan
+/ (,(|:(alpha =/ 'bach')) # (>:i.#alpha))
14

NB. Definition av tvärsumma mer generellt
NB. Not: argumentet är ett tal och endast ett tal
digit_sum =: 3 : '+/ > ". &. > ;/ ":y.'

NB. Den reducerade tvärsumman
NB. Argument är _ett_ tal
NB. Notera att det även finns vanliga programkonstruktioner såsom while. ... do. .. end.
reduced_digit_sum =: 3 : 0
tmp =. y.
while. tmp > 9 do.
tmp =. digit_sum tmp
end.
tmp
)

NB. Test av detta:
7+7+7
21

digit_sum 777
21

reduced_digit_sum 777
3


NB. Och ett mer fullständigt exempel:
> (digit_sum t); (reduced_digit_sum t); [t =: +/ convert 'hakan kjellerstrand'
7 7 215


Augusti-pyssel

I Augusti-pyssel ställdes några pyssel. Svaren finns i Svaren på Augusti-pyssel och jag följer de lösningar som finns där.

1) Vad står här egentligen och varför (dvs enligt vilken metod): 1045668080
[Not: Det bör finnas en bättre och mer generell metod för detta, speciellt eftersom man här måste leta fram antalet 36:or. Troligen kan man göra det med en loop av divisioner med 36 eller liknande. Detta lämnas som en övning åt läsaren eller skrivaren.]


NB. b #: n är talet n i bas b
NB. n # y innebär att en lista av n stycken y
alphanum =: '0123456789abcdefghijklmnopqrstuvwyxyz'
((6 # 36) #: 1045668080 ) { alphanum
hakank


2) Vad står här egentligen och varför: 15604225

alpha =: 'abcdefghijklmnopqrstuvwyxyz'
q: 15604225
5 5 7 13 19 19 19

NB. Men J är 0-baserat, dvs "a" finns i position 0, "e" i position 4 etc så vi
NB. minskar med 1, vilket är precis det som <: gör.
<: q: 15604225
4 4 6 12 18 18 18

NB. Bokstäverna för respektive index
(<: q: 15604225) { alpha
eegmsss


Fråga 3
Denna fråga bestod av flera delar.

...., 1596, ?
Det är alltså summan av de första n Fibonacci-talen

NB. Definiera Fibonaccifunktionen
NB. (Det finns fler varianter på
NB. http://en.wikipedia.org/wiki/Fibonacci_number_program#J_examples )
fib=: 3 : '{. +/\@|.^:y. 0 1x'

NB. De första 15 Fibonaccitalen
> fib each >:i.15
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610

N.B. Listan av summeringen av de första 16 talen
+/\ > fib each >:i.16
1 2 4 7 12 20 33 54 88 143 232 376 609 986 1596 2583


3 b) ...., 78, ?
Summan av de 12 första naturliga talen

+/ >:i.11
66

+/\ >:i.11
1 3 6 10 15 21 28 36 45 55 66

+/ >:i.12
78

+/\ >:i.12
1 3 6 10 15 21 28 36 45 55 66 78

3 c) ...., 129, ?
Summan av de första primtalen.


N.B. De första 10 primtalen
p: i.10
2 3 5 7 11 13 17 19 23 29

+/ p: i.11
160

+/\ p: i.11
2 5 10 17 28 41 58 77 100 129 160


Simulering

Ett stort skäl till att jag började med J var att det verkar finnas bra stöd för simulering där jag tidigare främst använt statistikpaketet R, som ju också har en kärv syntax. Se t.ex. Kort om R och simulering - ett praktikfall.

Jag har inte suttit med detta så mycket i J, men några trevliga saker finns.

NB. Slå en tärning 10 gånger
NB. ? innebär randomisering
NB. >: öka talen i listan med 1
>: ? 10 $ 6
6 4 2 4 3 2 2 4 5 5


Låt oss se i vilken position 1:an kommer i en slumpmässig permutation (dragning utan återläggning) av 20 tal.

]x =: >:?~ # i.10
8 7 9 1 6 10 4 2 3 5

NB. Positionen av 1:an i en lista visas med boolean (0 = falsk, 1 = sann)
NB. (om programmet är korrekt ska det ju bli det fjärde talet).
(1 = x)
0 0 0 1 0 0 0 0 0 0

NB. Här räknar vi ut vilken position detta är.
NB. Notera att J är 0-baserad, så vi får lägga till 1 (>:)
NB. För att få bas 1-positionen
>: (1 = x) # i.#x
4

NB. Detta som en oneliner på en annan slumpad lista
>: (1= x=:>:?~ 10) # i.10
9

NB. Och här visas den slumpade listan
x
4 3 10 9 8 6 7 2 1 5

NB. Här är 20 sådana körningar i en lista, dvs positionen av talet 1.
,(1= x=: >:?~ 20 $ 10) # >:i.10
1 9 4 2 4 3 2 10 6 4 9 1 10 1 8 8 10 5 2 8


Jag kommer troligen att återkomma med simuleringar i J. På ett eller annat sätt.

Fler språkligheter

Jag tänker avsluta med några andra språkligheter, utan egentliga kommentarer.
Låt oss anta att vi har följande namn i en fil som heter words (för det har vi):


kalle
nisse
pelle
anna
olle
eva
paula
ulla
abcd



NB. Läs in filen till variabeln words
NB. ('b' innebär att man läser in filen som en "boxed vector"
words =: 'b' fread 'words'

NB. Längden för respektive ord:
> #&.> words
5 5 5 4 4 3 5 4 4

NB. Sortera respektive ord
words /:&. > words

+-----+-----+-----+----+----+---+-----+----+----+
|aekll|einss|eellp|aann|ello|aev|aalpu|allu|abcd|
+-----+-----+-----+----+----+---+-----+----+----+

NB. Vilka av dessa ord har bokstäver i bokstavsordning?
NB. Booleanlistan visar att det är det sista ordet.
words = (words /:&. > words)
0 0 0 0 0 0 0 0 1

NB. Vilket är det sista ordet, då?
> (words = (words /:&. > words)) # words
abcd

NB. Om man kör detta på en av mina vanliga ordlistor på 391084 ord
NB. blir det 533 träffar, däribland följande (någor redigerat)
abbot abbé abc aber abort abé accent accept access accis ack ad adel adeln adelns adels adelsö adeps adept adjö af affin affint affix ....

NB. Jag gjorde en timing av inläsning av den stora ordlistan.
NB. Det tar alltså cirka 0.8 sekunder.
timer=: 6!:2

NB. ] är argumentet
sorted =: (] = (] /:&. > ])) # ]

NB. Läs in filen
words=:'b' fread 'sv_spelling_org.txt'

timer 'sorted words'
0.853685


Reguljära uttryck

Som ytterligare exempel: Vilka ord finns det i ordlistan som innehåller bokstavskombinationen a...b...c...d . För detta använder jag en an mina favoritkonstruktioner, nämligen reguljära uttryck (regular expressions, regex). För att använda detta måste man - som jag förstått hittills - läsa in ordlistan som en stor fet sträng.

load 'regex' NB. Ladda regex-paketet

words2 =: 's' fread 'sv_spelling_org.txt' NB. 's': läs in som sträng

NB. Inledande och avslutande ".*" är för att hela ordet ska
NB. komma med i matchningen
matched =: '.*a.+b.+c.+d.*' rxmatches words2

NB. Hur många ord matchade?
#matched
31

NB. Vilka ord var det?
> , matched rxfrom words2

arbetsblockad
arbetscykeltid
arbetscylinder
arbetsprocedur
arboricid
auxinherbicid
avbackningsanordning
avbackningsdon
avblockningskondensator
bakåtblickande
epiduralblockad
framåtblickande
halvbackskedja
handelsblockad
handelsblockaden
handelsblockadens
handelsblockader
handelsblockaderna
handelsblockadernas
handelsblockaders
handelsblockads
hårdmetallbestyckad
kalibercylinder
kalibreringscylinder
parabolarbetscylinder
paracervikalblockad
raketbestyckad
samarbetsprocedur
sambandsprocedur
snabbtryckande
tillbakablickande



Tacita definitioner

En sak som jag fortfarande har lite svårt för är att skapa "rena funktioner", "tacit definitions", dvs där man bara skriver funktioner utan några parametrar. Sådana definitioner beskrivs också som något som kommer senare vid inlärningen av språket.

Standardexemplet är medelvärde:

NB. Den tacita, implicita, definitionen
mean =: +/ % #
mean (i.10)^2
28.5

NB. Motsvarande explicita, dvs som kräver ett argument (y)
y=: (i.10)^2
+/y % # y
28.5

NB. ... eller något kärvare. Notera att tilldelning görs inne i funktionen.
+/y % # y=: ((i.10)^2)
28.5

NB. Tack och lov kan man definiera funktioner "imperativt",
NB. där y. motsvarar höger argument
mean2 =: 3 : '+/y. % # y.'

mean2 (i.10)^2
28.5


Slutord

Ovanstående exempel är från sådant jag själv tenderar att sitta och leka med. J används för betydligt mer avancerade matematiska saker, t.ex. linjär algebra, singular value decomposition etc. Man kan notera att det även finns stöd för DLL, grafik, socketprogrammering, MS Windows-anrop etc etc.

Det finns även ett GUI med onlinehjälp etc, men jag använder mestades kommandoradsvarianten. En stor fördel med GUI-versionen är att man kan köra Labs, dvs laborationer dels för att exemplifiera delar av språket och dels för att visa hur man löser vissa matematiska övningar i J.

Se även

Huvudsajten för J är alltså Jsoftware.
Innehållsförteckningen över dokumentation, böcker, artiklar etc: Documentation

För några dagar sedan ändrade man sajten till en Wiki så det inträffa att några länkar inte fungerar ännu.

De dokument/böcker som jag främst rekommenderar att läsa är följande:
* J Primer redogör för grunderna i språket.

* För en översikt över systemet, t.ex. installation och vilka paket som finns, är User manual oumbärlig, men där står inte så mycket om själva språket.

* Dictionary är referensen. Tyvär gjorde jag misstaget att börja med denna bok, vilket inte var så bra eftersom förklaringarna inte är för nybörjare. Det är mycket bättre att börja med J Primer.

* För erfarna programmerare kan även rekommenderas J for C programmers som har bra tips om debugging och liknande. Finns även som zippad PDF.

Det finns ett flertal böcker som beskriver hur man programmerar i J inom olika matematiska områden. Se avdelningen Books.

* Glöm inte bort mailinglistan jforum. Deltagarna verkar vara mestadels trevliga och tillmötesgående. Ett arkiv finns här

NB. Delningen av mailinglistan i flera delar är något väldigt nytt, och alla har inte kommit igång ännu.

Något om historiken bakom J (och APL):
* Kenneth IversonA personal view of APL (PDF)
* Roger Hui om APL, J och Iverson

Andra läsvärda saker:
* Roger Hui: A Sudoku Solver. Programmet är snabbt men - understatmentvarning - inte helt enkelt att förstå.

* Olika versioner av Fibonacci-definitioner wikipedia

* Fler länkar: Links.

* Tidskriften Vector, som handlar om APL, J och liknande språk.

Posted by hakank at oktober 24, 2005 08:42 EM Posted to Systemutveckling

Comments

Posted by: Hans at oktober 24, 2005 09:25 EM

Posted by: hakank at oktober 24, 2005 10:26 EM

Posted by: Christian Davén at oktober 25, 2005 11:49 FM

Posted by: hakank at oktober 25, 2005 06:06 EM

Posted by: Hans at oktober 25, 2005 07:35 EM

Posted by: Christian Davén at oktober 25, 2005 08:22 EM

Posted by: hakank at oktober 26, 2005 08:09 EM

Posted by: thebe at oktober 26, 2005 08:57 EM

Posted by: hakank at oktober 26, 2005 10:09 EM

Posted by: thebe at oktober 26, 2005 11:31 EM