neue Version

Robi, der Roboter

Ein Programmsystem für

die Einführung in die Algorithmik

Dr. Bernd Kokavecz, Humboldt-Gymnasium Berlin-Tegel

Landesbildstelle Berlin

(BICS)

August 1994

für Modula-2

(mcs)

Inhaltsverzeichnis:

Vorwort .............................................. 3

Vorgehensweise und Überblick über die Programme ...... 3

Besonderheiten des Konzepts .......................... 3

Arbeiten mit den Programmen (Landeslizenzen) ......... 4

Der Welteditor robied ................................ 4

Das Programm robiti (teach-in) ....................... 4

Das Programmieren ..................................... 5

Die erste Aufgabe ..................................... 6

Algorithmen ........................................... 7

Prozedurspezifikationen ............................... 10

Die zweite Aufgabe .................................... 11

Weitere Aufgaben ...................................... 15

Installation .......................................... 16

Anhang ................................................ 17

Literatur ............................................. 18

Vorwort:

In Anlehnung an Einstiegskonzepte bei der Logo-Programmierung veröffentlichte Heiner Pinke 1987 bei Vieweg (ISBN 3-528-04439-X) das Buch "Murmeltierwelt und Modula-2", eine Einführung in die strukturierte Programmierung. - Von Alfred Hermes und Dieter Stobbe erschien etwa ein Jahr später bei Klett ein Informatik-Buch mit ähnlichen Konzepten (ISBN 3-12-738400-9).

Seit 1988 benutze ich im Informatik-Anfängerunterricht an meiner Schule eine für unser damaliges UNIX-System (NCR-TOWER, NCR-Pascal selbstentwickelte Sammlung von Programmen und Tools, um entsprechend der in der o.a. Literatur vorgestellten Methode eine variablenfreie Einführung in die strukturierte Programmierung zu geben. Dabei haben sich vor allem die didaktisch gut aufbereiteten und durchaus anspruchsvollen Beispiele aus dem Buch von Pinke als Anregungen bewährt, während die Anknüpfung an die Vorstellung eines programmierten Roboters (NIKI) bei Hermes und Stobbe für eine günstige Motivationslage bei den Schülern sorgt.

Nachdem eine Weiterentwicklung der "Niki-Roboterwerkzeuge" den Berliner Schulen für LPI-Pascal (SCO-UNIX, interactive) seit 1993 zur Verfügung steht und auch eine Version für Turbo-Pascal 6 / 7 (MS-DOS) existiert, wird hier nun die Version ,,ROBI``für Modula-2 (für LINUX und interactive, SCO-Unix) vorgestellt. (Die Software ist in der Landesbildstelle Berlin erhältlich).

Vorgehensweise und Überblick über die Programme

Abbildungen aus Industriebetrieben, Filme und ggf. auch Besuche in Firmen, die programmierbare Fahrzeuge durch ihre Werkhallen fahren lassen, bieten Anknüpfungspunkte für die Eigenschaften von ROBI, dem Roboter.

In der Simulation "arbeitet" Robi in einer schachbrettartig eingeteilten "Werkhalle", durch die er sich mit Hilfe des Steuerbefehls "vor" und der 90 - Grad - Drehung "links" bewegen kann. Robi hat einen Sensor, der ihm meldet, ob vor ihm ein Hindernis liegt (vorne_frei), und einen Sensor, der meldet, ob auf dem Feld unter ROBI Gegenstände liegen (Feld_leer). Robi kann Gegenstände aufnehmen (nimm) oder Gegenstände aus seinem Vorrat ablegen (gib). Ein weiterer Sensor meldet, ob noch Gegenstände geladen sind (Tasche_leer).

In der Bildschirmdarstellung werden Robi durch einen Pfeil, Gegenstände (z.B. Werkzeuge) mit Hilfe der "0" dargestellt. Mit Hilfe einer Textdatei bzw. eines "Welteditors" (Programm ROBIED) lassen sich in ROBIs Welt auch Hindernisse einbauen (Vorgabe des Lehrers).

Das Programm ROBI-Teach-In erlaubt es, mit Hilfe von Steuertasten Robi manuell zu führen und beispielsweise "Aufräumarbeiten" in der Halle ausführen zu lassen. Das Programm erzeugt dabei automatisch eine Textdatei, die ein ROBI-Quellcode-Modula-2-Programm darstellt, das anschließend mit dem mcs-Compiler übersetzt werden kann und dann automatisch abläuft.

Die Wartung dieses linearen Musterprogramms (erforderlich z.B. nach Änderungen in der ROBI-Welt) ist fast unmöglich und verlangt geradezu die Einführung von Prozeduren.

Die Forderung, nicht nur eine Einzellösung, sondern Problemlösungsklassen zu programmieren, bedingt die Einführung von werteliefernden Prozeduren, Ablaufstrukturen und den Einsatz der "Sensoren". Nun werden die Programme mit Hilfe eines Editors geschrieben (ohne ROBI-Teach-In), wobei vorübersetzte Programmteile (Darstellung von ROBI und seiner Welt auf dem Bildschirm) eingebunden werden (MODULE Robi).

Besonderheit des Konzepts

Die Einführung in die Programmierung wird erlernt, ohne sich mit Variablen und den unterschiedlichen Datentypen belasten zu müssen, auch Ein- und Ausgabebefehle und deren Formatierung spielen keine Rolle. Im Vordergrund der Schülerarbeit steht die Entwicklung von Problemlösungen, verschiedene Darstellungsformen von Algorithmen, die Methode der schrittweisen Verfeinerung, Eigenschaften von Algorithmen usw. Gleichzeitig spielt die Dokumentierung der Arbeit eine große Rolle.

Gleich zu Beginn werden Prozeduren (parameterlos) als Mittel zur Verfeinerung benutzt. Die Prozeduren liefern Werte vom Typ BOOLEAN oder keine. Die üblichen Ablaufstrukturen werden zur Lösung der Aufgaben benötigt.

Da relativ wenig formale Modula-2-Kenntnisse vermittelt werden müssen, um interessante Programme zu gestalten, besteht nicht die Gefahr, gleich zu Beginn in einen reinen Programmierkurs zu münden.

Andererseits bleibt Raum, parallel auf die wesentlichen Elemente einer typischen Programmier-Arbeitsumgebung einzugehen (Editor, Compiler, Bibliotheken, Betriebssystem mit Verzeichnisstruktur).

Das Arbeiten mit den Programmen (Landeslizenzen)

Die Installation der Software wird im Anhang beschrieben.

Der Welteditor ROBIED:

Dieses Programm erlaubt es, für die einzelnen Programmieraufgaben entsprechende Umgebungen für den Roboter Robi zu definieren. Zunächst wird der Lehrer dieses Hilfsmittel benutzen.

Das Programm wird mit robied gestartet. Robied erwartet als "Standardwelt" den (lesenden) Zugriff auf die Datei welt0 in einem von der Umgebungsvariablen ROBI angegebenen Verzeichnis!

Der erste Bildschirm des Programms erwartet die Eingabe eines Dateinamens. Wird der Name einer noch nicht existierenden Welt eingegeben, so wird eine neue Welt angelegt. Zusammen mit den Programmen werden die Welten welt0, welt1 und welt2 ausgeliefert.

Der zweite Bildschirm zeigt die zu edierende Welt. Mit Hilfe der Pfeiltasten kann der Cursor (X) in der Welt herumgeführt werden. Durch Drücken der Leertaste kann ein Hindernis auf das entsprechende Feld gelegt oder von ihm genommen werden. Mit den Tasten g oder n können Gegenstände auf die Felder gelegt oder von ihnen genommen werden. Mit der Taste e wird das Programm beendet.

In der so edierten Welt steht ROBI beim Start mit Blickrichtung "NORD" auf demjenigen Feld, das zuletzt vom Cursor besetzt war. Die Anzahl der dabei mitgeführten Gegenstände wird beim Abschluß des Programms Robied festgelegt. (Wie viele Gegenstände soll Robi mit sich führen?)

Das Programm ROBITI (teach in):

Das Programm wird mit robiti gestartet. Die Schüler haben den Namen der Welt (welt1) und den Namen einer Programmdateit (z.B. mein1 = Mein erstes Modula-2-Programm) einzugeben. Bei der Eingabe des Weltnamens läßt sich das Programm mit der F10-Taste abbrechen. Natürlich ist bei der Eingabe der Weltdatei der entsprechende Pfad mit anzugeben (Lesezugriff für alle Schüler).

Die Schüler sollen nun in einer manuellen Steuerung Robi die Werkhalle aufräumen lassen (welt1). Dabei sind alle herumliegenden Werkstücke einzusammeln und anschließend restlos auf dem letzten Feld (unten rechts) abzulegen. Robi ist anschließend wieder auf seinen Parkplatz zu führen (oben links). Zur Verfügung stehen die Tasten v(=vor), l(=links), n(=nimm), g(=gib) und e(=ende). Während der Aktionen wird ein entsprechender Robi-Programm-Quelltext generiert.

Nach Abschluß von Robiti steht nun die entsprechende Programmdatei zur Verfügung (z.B.: mein1.mod), die mit Hilfe des Editors oder cat mein1.mod | more betrachtet werden kann:

robi_94.gif

Das vorliegende Programm kann nun übersetzt werden (rmc mein1), wobei die Robibefehle vorübersetzt mit Hilfe des Linkers (rml mein1) eingebunden werden (MODULE Robi). Die ausführbare Datei (mein1) zeigt den zuvor per Hand gesteuerten Ablauf.

Das Programmieren

Die Analyse des Programmquelltextes mein1.mod zeigt, daß ein solches Programm nicht zu warten ist. Insbesondere bei Veränderungen in der Robiwelt (Größe des Raums, Lage der Werkstücke, Anzahl der Werkstücke) sind andere Methoden gefordert. Zusammenhängende Befehle, Teillösungen der Gesamtlösung werden zu Prozeduren zusammengefaßt, Prozedur-Funktionen erlauben, eigene Tests zu definieren.

Mit Hilfe eines Editors (z.B.: vi) wird der entsprechende Programmtext geschrieben, nachdem entsprechende Algorithmen entwickelt und dargestellt worden sind.

Der formale Aufbau aller Programme gestaltet sich nach folgendem Muster:

MODULE muster;

FROM Robi IMPORT

initialisiere_die_Robiwelt, links, vor,

nimm, gib, vorne_frei, Tasche_leer, Feld_leer, Sensor;

FROM EKScreen IMPORT

Standardschirm;

(* Platz fuer die Deklaration eigener Robi-Prozeduren *)

BEGIN

initialisiere_die_Robiwelt('/hst/pool/welt1');

(* Platz fuer Robi-Befehle und Prozeduraufrufe *)

Standardschirm;

END muster.

Der Initialisierungsbefehl sorgt dabei für die Darstellung der Robiwelt auf dem Bildschirm. Alle Prozeduren werden mit Hilfe der Elementarbefehle "vor", "links", "nimm", "gib" aufgebaut. Eigene Tests lassen sich mit Hilfe der Abfragen "vorne_frei" , "Feld_leer" und "Tasche_leer" formulieren.

1. Aufgabe

Aufgabe: Robi soll alles aufräumen, auch wenn die Größe des rechteckigen Raumes sich verändert und andere Anordnungen der Werkstücke vorliegen.

Die Erfahrung zeigt, daß die Schüler zumeist das Feld spiralförmig abarbeiten möchten, jedoch ergeben sich hier Schwierigkeiten, die Endposition zu ermitteln und Bedingungen für ein Abbiegen von Robi zu formulieren.

Als Problemlösungsidee wird deshalb das systematische Absuchen des Raumes nach der "Rasenmähermethode" verfolgt. Hierbei wird die erste (linke) Spalte von oben nach unten bearbeitet, danach geht Robi mit einer Linkskurve in die benachbarte Spalte, um diese von unten nach oben abzuräumen. Nach einer Rechtskurve wird dann die dritte Spalte wieder von oben nach unten bearbeitet (usw.).

Zunächst kann der entsprechende Algorithmus umgangssprachlich formuliert werden. Sehr fruchtbar ist dabei eine Entwicklung im Klassengespräch, wobei die einzelnen Schritte als Tafelanschrift festgehalten werden.

Folgende "Stationen" innerhalb der Argumentation tauchen dabei immer wieder auf: Nach einem einmaligen "Kehrt" von Robi ist in einer Wiederholung solange spaltenweise aufzuräumen, bis der Übergang zur nächsten Spalte nicht mehr möglich ist. Da nicht klar ist, ob eine gerade oder eine ungerade Anzahl von Spalten vorliegt, ist nach einer von oben nach unten bearbeiteten Spalte abzufragen, ob eine Linkskurve noch möglich ist, nach einer von unten nach oben bearbeiteten Spalte, ob eine Rechtskurve noch möglich ist. Ist dies der Fall, so wird die jeweilige Kurve ausgeführt und Robi kann fortfahren. Anderenfalls bleibt Robi vor der Wand stehen (Abbruchbedingung).

Das Ergebnis einer solchen Diskussion wird dann formalisert und (hier) als Lindsey-Structure-Chart dargestellt (Hauptalgorithmus).

Nun sind (Methode der schrittweisen Verfeinerung) die nicht als Elementaroperationen verfügbaren Formulierungen in Unteralgorithmen und ggf. davon weiteren Unteralgorithmen darzustellen:

Beispiel: räume eine Spalte auf

Unabhängig davon, ob von oben nach unten oder umgekehrt gearbeitet wird, ist das momentane Feld zu leeren und anschließend auf das davorliegende Feld überzugehen. Die Abbruchbedingung ergibt sich aus der Abfrage, ob eine Wand erreicht wurde. (Zur Übung formuliere man den Algorithmus alternativ mit einer vorprüfenden Schleife!) Eine weitere Verfeinerung stellt "leere das Feld" dar.

Beispiel für die Darstellung eines Algorithmus nach Lindsey (folgende Seite)

Die Umsetzung in ein Modula-2-Programm erfordert noch die Einführung von Prozeduren und Funktionen:

Programmtext :

MODULE Robir;

FROM Robi IMPORT

initialisiere_die_Robiwelt, links, vor,

nimm, gib, vorne_frei, Tasche_leer, Feld_leer, Sensor;

FROM EKScreen IMPORT

Standardschirm;

PROCEDURE kehrt;

BEGIN

  links; links;

  END kehrt;

PROCEDURE leere_das_Feld;

BEGIN

  WHILE NOT Feld_leer() DO

     nimm;

  END;

END leere_das_Feld;

PROCEDURE raeume_eine_Spalte_auf;

BEGIN

REPEAT

   leere_das_Feld;

   vor;

UNTIL NOT vorne_frei();

leere_das_Feld;

END raeume_eine_Spalte_auf;

PROCEDURE rechts;

BEGIN

  kehrt; links;

END rechts;

PROCEDURE Rechtskurve;

BEGIN

   rechts;

   vor;

   rechts;

END Rechtskurve;

PROCEDURE Linkskurve;

BEGIN

   links;

   vor;
 
   links;

END Linkskurve;

PROCEDURE links_frei():BOOLEAN;

BEGIN

links;

Sensor:=vorne_frei();

rechts;

RETURN Sensor; (* Seiteneffektfreiheit ! *)

END links_frei;

PROCEDURE rechts_frei(): BOOLEAN;

BEGIN

rechts;

Sensor:=vorne_frei();

links;

RETURN Sensor;

END rechts_frei;

BEGIN

initialisiere_die_Robiwelt('/hst/pool/welt1');

kehrt;

WHILE vorne_frei() DO

   raeume_eine_Spalte_auf;
 
   IF links_frei()

   THEN Linkskurve;

        raeume_eine_Spalte_auf;

        IF rechts_frei()

        THEN Rechtskurve;

         END;

    END;

END;

Standardschirm;

END Robir.

Einige der entstandenen Unterprogramme sind geeignet, auch bei anderen Aufgaben zur ROBI-Thematik verwendet zu werden. Hierzu ist eine formalisierte Dokumentation (Prozedurspezifikation ) vorgesehen.

Beispiel für ein Formular für ROBI -Prozedurspezifikationen:
 
 

Um zu testen, ob die programmierte Problemlösung tatsächlich eine Problemlösungsklasse repräsentiert, überschreibt der Lehrer zu geeigneten Zeitpunkten die Weltdatei mit anderen Inhalten, so daß für verschiedene Tests die Schülerprogramme nicht neu übersetzt zu werden brauchen. Hierzu erforderlich ist freilich ein Mehrplatzsystem, bei dem die Schüler zwar ihre individuellen Programme erzeugen, aber auf eine gemeinsame Weltdatei zugreifen.

2. Aufgabe:

Olympia: Robi soll das Olympiastadion suchen, dann dessen Eingang finden, eine Runde drehen und nach Hause laufen. Sein Heim markiert er zu Beginn durch Ablage eines Gegenstandes.


Hier kann der vierzeilige Hauptalgorithmus vom Lehrer vorgegeben werden. Die Unteralgorithmen werden teils im Klassengespräch, teils in Gruppen und teils in Einzelarbeit erstellt.

Interessant ist die von den Schülern gefundene Lösung für das Finden des Stadions. Robi sucht wieder nach der "Rasenmähermethode". Da sichergestellt ist (s. ausf. Aufgabentext), daß das Stadion freisteht, wird wie folgt argumentiert: Hat Robi eine Randbegrenzung seiner Welt erreicht, dann ist auch links und rechts von Robi kein Vorwärtsgehen mehr möglich. Hat Robi aber eine Ecke des Stadions erreicht (von oben oder von unten kommend), so ist es möglich, entweder rechts oder links von Robi weiter geradeaus zu laufen (vorne links frei, bzw. vorne rechts frei). Bei allen Tests wird darauf geachtet, daß keine Seiteneffekte auftreten (s. Algorithmus).

Ist eine Ecke des Stadions gefunden, wird durch den Befehl "rechts" erreicht, daß Robi in jedem Fall entgegen dem Uhrzeigersinn an der Außenmauer des Stadions entlangläuft. Ist dabei "links frei", so ist entweder der Eingang oder eine Stadionecke gefunden.

In jedem Fall dreht sich dann Robi nach links und geht zwei Schritte vor. Hat er dabei eine Ecke erreicht, dann ist "links frei" falsch, anderenfalls aber, wenn sich Robi im Inneren des Stadions befindet, ist "links frei" wahr.

Weitere Einzelheiten zeigen die Lindsey-Diagramme (hier heißt ROBI noch `` Murmel``). Es sind unterschiedliche Lösungen von den Schülern zu erwarten!

Die Beschäftigung mit der Aufgabe zeigt, daß weitere Eigenschaften für die Lage und die Abmessungen des Stadions festgelegt sein müssen (Anforderungsdefinition)!

Weitere Aufgaben

In der angegebenen Literatur finden sich eine Reihe weiterer Aufgaben, die von den Schülern bearbeitet werden können. Einige Beispiele für Aufgaben sollen hier nur kurz vorgestellt werden:

1. Robi verfolgt eine Spur von verteilten Gegenständen

2. Robi umgeht Hindernisse (Robi als Bergsteiger)

3. Robi hat aus einem Labyrinth herauszufinden

4. Robi lernt rechnen (Addition, Subtraktion)

5. Robi lernt multiplizieren

6. Robi sortiert Zahlen

7. Robi als Turing-Maschine

Anhang : Installation:

SCO Unix oder interactive mit mcs-Modula-2

Die Software berücksichtigt, daß bei verschiedenen Terminalemulationen nur 23 Zeilen verwendet werden, während in anderen Fällen der volle Umfang eines PC-Ansi-Terminals (Farbe, 25 Zeilen) zur Verfügung steht.

Die entsprechende Diskette wird in den UNIX-Zentralrechner eingelegt. Der Superuser begibt sich in ein Verzeichnis, auf das alle Schüler (lesend) Zugriff haben (z.B.: /hst/pool ). Mit dem Befehl

cpio -ivd < /dev/rfd0135ds9

werden die erforderlichen Dateien kopiert.

Um mit dem Programmpaket arbeiten zu können, ist es erforderlich, die Umgebungsvariable ROBI zu definieren. Dabei gibt ROBI das Verzeichnis an, in das die Software eingespielt wurde (hier: /hst/pool).

ROBI=/hst/pool

export ROBI

Zusätzlich wird das entsprechende Verzeichnis in den Programm-Suchpfad eingebunden:

PATH=$PATH:/hst/pool

export PATH

Die entsprechenden Befehle werden zweckmäßigerweise in die entsprechenden .profile-Dateien der Schüler eingebaut.

Die Schüler können dann die Programme Robied und Robiti starten. Für die Compilierung der mit robiti erzeugten Programme oder eigener Programme ist es erforderlich, die shell-scripts rmc (Robi-Modula-Compiler) und rml (Robi-Modula-Linker) aufzurufen. Der Dateiname ist dabei ohne die Extension .mod anzugeben.

rmc muster

rml muster

Das fertige Programm wird gestartet mit

muster

Disketteninhalt:

. / robied Welteditor

. / robiti Robi-Teach-In

. / welt0 Default-Welt für robied

. / rmc Robi-Modula-Compiler

. / rml Robi-Modula-Linker

. / cls Reset Bildschirm (Farben aus...)

. / m_tools / ....... Modula-Bibliothek und Robi-Software mit Quellen und

... ct.cfg Konfigurationsdatei für Linker

... termcap Terminalbeschreibungen für m_tools

. / beispiele / ......

Das Softwarepaket wertet die Umgebungsvariable TERM aus, liest jedoch die o.a. eigene Datei termcap. In einigen Fällen ist eine Anpassung für die Ausgabe der Strichgrafik oder für die Farbansteuerung erforderlich. Die entsprechende Dokumentation findet sich in . / m_tools / kscreen.def. Für das Terminal ansi ist die entsprechende Anpassung beispielhaft vorgegeben.

Anhang:

Beispiel für eine Schülerdatei .profile:

# /hst/pool ist ein Beispiel für das Robi-Installationsverzeichnis !

PATH=$PATH:/hst/pool/:$HOME/bin:/usr/mcs/prgs:

# use default system file creation mask

eval `tset -m ansi:ansi -m :\?${TERM:-ansi} -r -s -Q`

stty -istrip

M2ENV=/usr/mcs/env

M2OVR=/usr/mcs/prgs

HTERMCAP=/usr/mcs/hterm

MROOT=/usr/mcs

# /hst/pool ist ein Beispiel für das Robi-Installationsverzeichnis !

ROBI=/hst/pool

export TERM PATH M2ENV M2OVR HTERMCAP MROOT ROBI

set -o emacs

stty intr ^C

Das shell-script rmc:

mc $1 -a:${ROBI}/m_tools ${ROBI}/m_tools/ct

Das shell-script rml:

ml $1 -a:${ROBI}/m_tools ${ROBI}/m_tools/ct

__________________________________________________________________________________

ACHTUNG !!!!!

Die Disketten für SCO UNIX oder interactive lassen sich auf jedem MS DOS - Rechner mit dem Befehl

diskcopy a: a:

kopieren!

Literatur:

Heiner Pinke Murmeltierwelt in Pascal Braunschweig, 1987 (Vieweg)

Alfred Hermes, Dieter Stobbe INFORMATIK EINS Stuttgart, 1988 (Klett)

Jürgen Gulbins UNIX Berlin, Heidelberg, 1988 (Springer)

Ingenieurbüro Jaeger MCS-Modula-2- Cross-System V 4.4

Franz Stetter Softwaretechnologie Zürich, 1981 (BI)

Materialien der zentralen Beratungsgruppe (ZEBIS) an der Landesbildstelle Berlin (jetzt BICS)