zurück zum Artikel

Die Syntax von Lisp ist minimalistisch, dennoch (oder gerade deswegen) birgt die Sprache ein enormes Potenzial. Um Lisp zu lernen und zu üben, hilft das regelmäßige Schreiben von Code mehr als eine rein theoretische Beschäftigung mit der Sprache. Zum Auftakt ist das Ziel eine Funktion zum Berechnen von Primzahlen.

Die Syntax von Lisp ist minimalistisch, dennoch (oder gerade deswegen) birgt die Sprache ein enormes Potenzial. Um Lisp zu lernen und zu üben, hilft das regelmäßige Schreiben von Code mehr als eine rein theoretische Beschäftigung mit der Sprache. Zum Auftakt ist das Ziel eine Funktion zum Berechnen von Primzahlen.

Gesucht ist eine Funktion get-primes, die die Parameter min und max entgegennimmt und eine Liste aller Primzahlen zurückgibt, die sich im durch min und max definierten Intervall befinden. Enthält das Intervall keine Primzahlen, ist die leere Liste zurückzugeben. Ist max kleiner als min, ist die Rückgabe ebenfalls die leere Liste.

Die Funktion get-primes

Das Grundgerüst für die Funktion get-primes lässt sich leicht definieren, wobei zunächst eine statische Liste mit den Primzahlen zwischen 1 und 20 zurückgegeben wird, unabhängig von den Parametern min und max:

(defun get-primes (min max)
  '(2 3 5 7 11 13 17 19))

Im nächsten Schritt ist es sinnvoll, über alle Zahlen zwischen min und max zu iterieren und sie dynamisch als Liste aufzubauen. Sie lässt sich dann nämlich in einem weiteren Schritt filtern. Dazu dient das loop-Makro in Verbindung mit collect. Da es sich bei den Zahlen zwischen min und max nicht zwingend um Primzahlen handelt, kann man die Laufvariable beispielsweise guess nennen, um den Umstand auszudrücken, dass es sich vorerst nur um eine Vermutung handelt:

(defun get-primes (min max)
  (loop
    for guess from min to max
    collect guess))

Als Nächstes ist das Sammeln der Zahlen auf jene einzuschränken, die tatsächlich Primzahlen sind. Angenommen, es gäbe eine Prädikatsfunktion is-prime, ließe sich das wie folgt schreiben:

(defun get-primes (min max)
  (loop
    for guess from min to max
    when (is-prime guess)
    collect guess))

Die Funktion is-prime

Da die Funktion is-prime nicht existiert, gilt es nun, sie zu definieren. Dazu ist ein Blick auf den Wikipedia-Eintrag von Primzahlen [1] hilfreich. Dort heißt es:

"Eine Primzahl ist eine natürliche Zahl, die genau zwei natürliche Zahlen als Teiler hat. Eine Primzahl ist also eine natürliche Zahl größer als 1, die nur durch sich selbst und durch 1 ganzzahlig teilbar ist."

Da jede natürliche Zahl durch sich selbst und durch 1 teilbar ist, werden die beiden Teiler als "triviale Teiler" bezeichnet. Das Gegenteil davon sind die "nichttrivialen Teiler", die zwischen 1 und der zu teilenden Zahl liegen müssen.

Im ersten Schritt lässt sich die Funktion is-prime daher so definieren, dass sie nur Zahlen akzeptiert, die größer als 1 sind:

(defun is-prime (guess)
  (> guess 1))

Zusätzlich gilt es zu überprüfen, ob die Zahl nur triviale Teiler besitzt – oder, mit anderen Worten, ob sie keine nichttrivialen Teiler besitzt:

(defun is-prime (guess)
  (and (> guess 1)
       (not (has-non-trivial-divisors guess))))

Die Funktion has-non-trivial-divisors

Für die Funktion has-non-trivial-divisors lässt sich mit Hilfe der rem-Funktion schreiben. Sie ermittelt den Rest einer Modulo-Division. Um beispielsweise zu prüfen, ob eine Zahl durch 2 teilbar ist, lässt sich has-non-trivial-divisors wie folgt definieren:

(defun has-non-trivial-divisors (n)
  (zerop (rem n 2)))

Die Prädikatsfunktion zerop prüft dabei, ob der ihr übergebene Wert gleich 0 ist. Auf dem Weg liefert die Funktion den Wahrheitswert T für alle Zahlen, die durch 2 teilbar sind. Für alle anderen gibt die Funktion NIL zurück.

Nun gilt es aber, nicht nur die 2, sondern alle möglichen Teiler zu überprüfen. Das lässt sich erneut mit dem loop-Makro lösen. Allerdings lässt sich die Schleife abbrechen, sobald ein erster Teiler gefunden wurde. Wie viele Teiler es tatsächlich gibt, ist für die Frage, ob es überhaupt Teiler gibt, unerheblich:

(defun has-non-trivial-divisors (n)
  (loop
    for i from 2 to (1- n)
    thereis (zerop (rem n i))))

Zum Verbessern der Leistung bietet es sich an, die Schleife nicht bis n-1 auszuführen, sondern nur bis zur Quadratwurzel von n. Wurde dann noch kein Teiler gefunden, kann es auch keinen mehr geben:

(defun has-non-trivial-divisors (n)
  (loop
    for i from 2 to (sqrt n)
    thereis (zerop (rem n i))))

Das Ergebnis überprüfen

Nun sind die Funktion get-primes und alle Abhängigkeiten implementiert. Ruft man die Funktion mit den Werten 1 und 20 auf, gibt sie die ersten acht Primzahlen korrekt aus:

(get-primes 1 20)
; => (2 3 5 7 11 13 17 19)

Der Aufruf der Funktion mit einem Intervall, in dem sich keine Primzahlen befinden, liefert wie gefordert die leere Liste zurück:

(get-primes 8 10)
; => NIL

Ruft man die Funktion schließlich mit vertauschten min- und max-Werten auf, ist das Ergebnis ebenfalls die leere Liste:

(get-primes 20 1)
; => NIL

Die Aufgabe ist somit gelöst. Ein Blick auf den Code zeigt, wie elegant und zugleich mächtig das loop-Makro ist. Eine hervorragende Einführung in das Thema findet sich im 22. Kapitel [2] des Buchs "Practical Common Lisp [3]" von Peter Seibel.

tl;dr: Das Berechnen von Primzahlen lässt sich in Lisp gut mit dem loop-Makro lösen, das vielfältige Möglichkeiten bietet, zu iterieren. Auch wenn die Rechenleistung des gezeigten Ansatzes deutlich verbesserungswürdig ist, zeigt das Beispiel doch gut, wie das Makro genutzt werden kann. ( [4])

URL dieses Artikels:
https://www.heise.de/-3077388

Links in diesem Artikel:
[1] https://de.wikipedia.org/wiki/Primzahl
[2] http://www.gigamonkeys.com/book/loop-for-black-belts.html
[3] http://www.gigamonkeys.com/book/
[4] mailto:webmaster@goloroden.de

Copyright © 2016 Heise Medien