\documentclass[11pt,a4paper]{article}
% save as utf-8-emacs-unix

% 2006-07-07 EW Adventures-1.tex
% 2006-07-22 EW Adventures-2.tex
% 2006-08-14 EW Adventures-2a.tex
% 2007-01-10 EW Adventures-3.tex
% 2007-01-13 EW Adventures-4.tex
% 2008-11-14 EW Adventures-5.tex
% 2011-01-07 EW Adventures-6.tex: rs485+mpc
% 2011-02-14 EW Adventures-7.tex: list
%
% Aufgebessert nachdem ich 'ne Reihe Optimierungen gemacht hatte
% Und dann nochmal komplett umgeräumt!
%

% language support
\usepackage[german]{babel}
%\usepackage{german}
\usepackage[utf8]{inputenc} % can use Umlauts now ü instead of "u
%\usepackage{lmodern} % better fonts
%\usepackage{pslatex} % use native PostScript fonts
%\usepackage{cm-super}

\usepackage{url} % \url{} \path{} with correct "hyphenation"
%\usepackage{fancyvrb} % for code examples

% \voffset-10mm
% \pagestyle{empty}
% \pagestyle{plain}
% \pagestyle{headings}
% \renewcommand{\baselinestretch}{1.08}
%\usepackage{xspace}
\parindent=0pt
%\newcommand{\amforth}{\texttt{amforth}}
%\newcommand{\zB}{z.\,B.\ }
\begin{document}

\title{Adventures in \texttt{\textbf{am}}Forth 7: Eine einfache Liste}

\author{Erich Wälde}

\maketitle

%\begin{multicols}{2}

% --------------------------------------------------------------------
%\section{Intro}
%\label{sec:intro}

\begin{abstract}\itshape
Auf meinen Messstationen wollte ich die Information über die
angeschlossenen Sensoren so verwalten, dass ich jederzeit neue Sensoren
dazuhängen kann, ohne den Kontroller neu zu programmieren. Ich wollte eine
einfach verkettete Liste, auch wenn ein Vektor mit zehn Einträgen
wahrscheinlich weit gereicht hätte. Ich habe mich für eine sehr simple,
einfach verkettete Liste entschieden. Der gezeigte Quelltext bezieht sich
auf \texttt{\textbf{am}}Forth $4.2$.
\end{abstract}

\begin{multicols}{2}

% --------------------------------------------------------------------
\section{Paarweise Zellen}
\label{sec:intro}

Der Eintrag in einer einfach verketteten Liste besteht nur aus zwei
Feldern: 
\begin{enumerate}
\item die Adresse des nächsten Eintrags (\texttt{next})
\item der zu speichernde Wert (\texttt{value})
\end{enumerate}
Das Ende der Liste markiere ich, indem das erste Feld den Wert null
erhält. Der Kopf (Anfang) der Liste (\texttt{head}) wird in einer
Variablen aufbewahrt, am besten in einer nicht--flüchtigen Variablen vom
Typ \texttt{value}.


{\small
\begin{verbatim}
0 value LISTE   \ define head
\end{verbatim}
}

Um einen Eintrag am Anfang der Liste einzufügen, definiere ich das Wort
\texttt{list.add}, welches auch \textit{unshift} heißen könnte.


{\small
\begin{verbatim}
: list.add ( value head -- new.head )
  dp >r         \ save new.head
  ,             \ store head as "next"
  ,             \ store "value"
  r>            \ new.head on stack
;
\end{verbatim}
}

An der nächsten freien Adresse im Flash-Speicher (\texttt{dp}) werden 
der Zeiger auf den nächsten Eintrag und der zu speichernde Wert
eingetragen. Der Wert kann natürlich ebenfalls eine Adresse sein, z.B.\
die Adresse einer Funktion oder eines weiteren Datenfelds. Die beiden
Felder sind von der Größe \texttt{cell}, also $2$\,Byte. 

Die Adresse des Eintrags verbleibt auf dem Stack und kann dann in
\texttt{head} eingetragen werden.

\textbf{Vorsicht:} Die Worte \texttt{dp} und \texttt{here} heißen in den
\texttt{\textbf{am}}Forth--Versionen vor $4.0$ \texttt{here} und \texttt{heap}.

Im ersten Eintrag der Liste soll die Zahl \texttt{\$0042} gespeichert werden:

{\small
\begin{verbatim}
> 0 value LISTE   LISTE hex .
0  ok
> $0042 LISTE list.add  to LISTE
 ok
> LISTE .
11B9  ok
> 
\end{verbatim}
}

Das bei jedem Eintrag benötigte Quelltext--Fragment lässt sich auch
schöner schreiben. Noch schöner wäre allerdings ein Wort, welches zum
Namen eines Listenkopfs das zugehörige Wort definiert.

{\small
\begin{verbatim}
: >LISTE        ( value -- )
  LISTE list.add to LISTE
;
\end{verbatim}
}

Um den Inhalt der Liste auszugeben, definieren wir drei Worte:

{\small
\begin{verbatim}
: list.next     ( addr -- addr' )  
  i@
;
: list.value    ( addr -- value )
  1+ i@
;
: list.show     ( 'head -- )
  dup 0= if   drop exit   then
  begin
    dup              4 u0.r space \ flash addr
    dup  list.next   4 u0.r space
    dup  list.value  4 u0.r cr
  list.next dup 0= until
  drop
;
\end{verbatim}
}


{\small
\begin{verbatim}
> LISTE list.show
11B9 0000 0042  ok
> $08FF >LISTE
 ok
> LISTE list.show
11BB 11B9 08FF
11B9 0000 0042
 ok
>
\end{verbatim}
}


Diese Liste ist sehr einfach. Man kann nur am Anfang neue Werte hinzufügen
und die ganze Liste ausgeben. Die Werte werden in umgekehrter Reihenfolge
des Speicherns ausgegeben, was u.U.\ stört. Immerhin muss die Liste nicht
am Stück im Speicher liegen. Man kann bequem noch ein paar Worte
definieren, und danach weitere Einträge für die Liste.


Mit der Liste will man irgendwann etwas Konkretes anfangen, sonst bräuchte
man sie nicht. Also schreibe ich eine Funktion, die einen Zeiger auf eine
weitere Funktion und den Kopf einer Liste als Argumente bekommt und dann
die übergebene Funktion auf alle gespeicherten Werte anwendet.

{\small
\begin{verbatim}
: list.walk     ( xt head -- )
  dup 0= if drop drop  exit  then
  begin         \ -- xt item
    over over   \ -- xt item  xt 'list.item
    list.value  \ -- xt item  xt value
    swap        \ -- xt item  value xt
    execute     \ -- xt item
    list.next   \ -- xt next
  dup 0= until
  drop drop
;
\end{verbatim}
}

Die übergebene Funktion verbraucht den obersten Wert auf dem Stack
(\texttt{value}), produziert aber keine Rückgabewerte.

{\small
\begin{verbatim}
> : doit ( value -- )  6 u0.r cr ;
 ok
> ' doit LISTE list.walk
0008FF
000042
 ok
\end{verbatim}
}

Ausgerüstet mit diesen Worten, erzeuge ich eine Liste, in der die Werte
weitere Adressen sind. Sie verweisen auf Datenstrukturen, in denen alles
Wissenswerte über einen bestimmten Sensor zu finden ist, etwa wie man
einen aktuellen Wert beschaffen kann, oder wie der beschaffte Wert
weiterverarbeitet wird. Eine regelmäßig aufgerufene Funktion
(\texttt{data.collect}) arbeitet dann die Liste ab. Die Werte werden im RAM
abgelegt und nicht auf dem Stapel behalten. Kommen jetzt neue Sensoren an
den Kontroller, dann erzeuge ich für jeden eine neue Datenstruktur und
verlinke sie zusätzlich in der Liste der Sensoren. Mit dem nächsten
Aufruf von \texttt{data.collect} werden auch die neuen Sensoren gelesen.
Weitere Funktionen \texttt{data.ls} und \texttt{data.reset} versenden die
gesammelten Daten bzw.\ löschen die entsprechenden Speicherbereiche.


Für eine ordentliche Liste fehlen weitere Funktionen, die einen bestimmten
Eintrag aufsuchen, löschen, oder einen zusätzlichen Eintrag dazwischen
verlinken. Für meine Anwendung habe ich das allerdings nicht gebraucht.


% --------------------------------------------------------------------
\section{Referenzen}

\begin{enumerate}
%\item \label{Adv1} E. Wälde, Adventures in Forth,   Die 4. Dimension 3/2006, Jahrgang 22
%      gforth-ec r8c, i2c von Hand, Thermometer
%\item \label{Adv2} E. Wälde, Adventures in Forth 2, Die 4. Dimension 4/2006, Jahrgang 22
%      timeup Uhr und Kalender, twotask
%\item \label{Adv3} E. Wälde, Adventures in Forth 3, Die 4. Dimension 1/2007, Jahrgang 23
%      usart0, redirection
%\item \label{Adv4} E. Wälde, Adventures in Forth 4, Die 4. Dimension 1/2007, Jahrgang 23
%      dcf-77 Uhr
%\item \label{Adv5} E. Wälde, Adventures in Forth 5, Die 4. Dimension 4/2008, Jahrgang 24
%      Umstieg auf amforth, bit flags, sensor:, filter_mean:

%\item \label{r8c-ds} Renesas R8C/13 datasheet auf \url{www.renesas.com}
%\item \label{Koenig} A.\ König und M.\ König, Das PICmicro Profi Buch, Franzis
%  Verlag 1999, ISBN 3-7723-4284-1
%\item \label{SPelc} Stephen Pelc, Programming Forth, \\ \url{http://www.mpeforth.com/arena/ProgramForth.pdf}
%\item \label{Deliano} \url{http://www.embeddedforth.de/emb3.pdf} S.\ 9
%\item \label{dcf} \url{http://de.wikipedia.org/wiki/DCF77} und Verweise darin
%\item \label{willem} ByteForth von Willem Ouwerkerk,\\  \url{http://www.forth.hccnet.nl/byteforth.htm}
\item \label{amforth} \url{http://amforth.sourceforge.net/}
%\item \label{ron} Ron Minke, Forth von der Pike auf  Die 4. Dimension 3+4/2005 \ldots 4/2006, sowie Sonderheft AVR und  3+4/2007
%\item \label{namedbits} M. Kalus, M. Trute, Named Bits, Die 4. Dimension 2/2007, Jahrgang 23
%\item \label{lubos} Lubo\v{s} P\v{e}kn\'{y}s Seite: \url{http://www.forth.cz}
%\item \label{RS485} Wikipedia (RS485) \url{de.wikipedia.org/wiki/RS485}
%\item \label{RS485a} \url{www.mikrocontroller.net/articles/RS-485}
%\item \label{g4.fs} Michael Kalus: g4.fs \url{www.forth-ev.de/repos/g4/g4.fs}
%\item \label{atmega32} atmega32 Datenblatt (doc2503.pdf) \url{www.atmel.com}
\end{enumerate}
\end{multicols}


%\newpage
% --------------------------------------------------------------------
\section{Listings}



\begin{quote}
\begin{small}
\begin{multicols}{2}
\listinginput[1]{1}{2011-02/list.fs}

\end{multicols}
\end{small}
\end{quote}


\end{document}
