Am 27. Oktober 1987 beantragten 19 im Kanton Basel-Stadt tätige Kindergärtnerinnen, Arbeits- und Hauswirtschaftslehrerinnen dem Regierungsrat des Kantons Basel-Stadt, es sei ihnen gestützt auf Art. 4 Abs. 2 Satz 3 BV ab dem Jahr 1986 ein höherer Lohn zu bezahlen. Den ablehnenden Entscheid des Regierungsrates zogen sie an das Appellationsgericht des Kantons Basel-Stadt weiter, welches die Beschwerde abwies. Eine dagegen erhobene staatsrechtliche Beschwerde wurde vom Bundesgericht am 31. Mai 1991 gutgeheissen (BGE 117 Ia 262). In der Folge hiess das Appellationsgericht mit Urteil vom 9. Juli 1993 die 19 Rekurse teilweise gut und wies den Kanton an, die damaligen Rekurrentinnen ab 1. November 1987 um zwei Lohnklassen höher zu entlöhnen, da die bisherige Lohneinstufung geschlechtsdiskriminierend sei.

Nachdem das Bundesgericht auf eine dagegen erhobene staatsrechtliche Beschwerde des Kantons Basel-Stadt nicht eingetreten war (BGE 120 Ia 95), reihte der Kanton alle Kindergärtnerinnen und Kindergärtner bzw. Arbeits- und Hauswirtschaftslehrerinnen und -lehrer auf den 1. August 1994 um zwei Lohnklassen höher ein.

Am 29. April 1994 reichten 582 am ersten Verfahren nicht beteiligte Kindergärtnerinnen, Arbeits- und Hauswirtschaftslehrer und -lehrerinnen den Antrag ein, sie seien rückwirkend per 1. Mai 1989 in die entsprechenden höheren Lohnklassen einzureihen und es sei ihnen ab 1. Mai 1989 die sich aus dieser Neueinreihung ergebende Lohndifferenz nachzuzahlen. Mit Entscheid vom 21. November 1995 beschloss der Regierungsrat des Kantons Basel-Stadt, den Antragstellerinnen eine Lohnnachzahlung für die Zeit vom 1. Mai 1994 bis 31. Juli 1994 zu leisten. Im Übrigen wies er die Begehren ab. Dagegen erhoben 581 der Gesuchstellerinnen Rekurs an das Appellationsgericht des Kantons Basel-Stadt mit dem Antrag, es seien ihnen die entsprechenden Lohnnachzahlungen seit 1. Mai 1989 auszurichten.

Das Appellationsgericht hiess mit Urteil vom 16. Mai 1997 die Rekurse teilweise gut und stellte fest, die Rekurrentinnen seien ab 1. November 1993 um jeweils zwei Lohnklassen höher einzustufen und entsprechend zu entlöhnen. Im Übrigen wies es die Rekurse ab. Den Rekurrentinnen wurde eine Gebühr von je Fr. 50.-- auferlegt. Das Gericht erwog, dass die im alten Lohngesetz von 1970 vorgesehene Einstufung der drei Fachrichtungen das Gleichheitsgebot (Art. 4 Abs. 2 Satz 3 BV) verletze und jeweils eine um zwei Lohnklassen höhere Einreihung angemessen wäre. Der Anspruch auf geschlechtsneutrale Entlöhnung könne grundsätzlich auch rückwirkend geltend gemacht werden. Diese Befugnis werde aber nicht nur durch die Verjährung, sondern auch in weiteren Fällen eingeschränkt. Erst mit der im Oktober 1993 erfolgten Eröffnung des Urteils vom 9. Juli 1993 habe der Kanton Kenntnis von Vorliegen und Ausmass einer Verletzung von Art. 4 Abs. 2 Satz 3 BV erhalten. Diejenigen Bediensteten, die vor diesem Zeitpunkt ihre Lohneinstufung nicht angefochten hätten, hätten nach Treu und Glauben ihre Ansprüche eingebüsst. Zum Kostenpunkt erwog das Gericht, die in Art. 12 (recte: Art. 13 Abs. 5) des Bundesgesetzes vom 24. März 1995 über die Gleichstellung von Frau und Mann (Gleichstellungsgesetz, GlG; SR 151) vorgesehene Kostenfreiheit komme nicht zum Tragen, da dieses Gesetz noch keine Anwendung finde.

558 der ursprünglichen Gesuchstellerinnen erhoben am 15. August 1997 staatsrechtliche Beschwerde und Verwaltungsgerichtsbeschwerde an das Bundesgericht. Mit staatsrechtlicher Beschwerde beantragen sie, das Urteil des Verwaltungsgerichts vom 16. Mai 1997 aufzuheben. Mit Verwaltungsgerichtsbeschwerde stellen sie den Antrag, dieses Urteil bezüglich des Kostenentscheids aufzuheben.

Das Bundesgericht heisst die staatsrechtliche Beschwerde gut und erklärt die Verwaltungsgerichtsbeschwerde für gegenstandslos.

Aus den Erwägungen:

2.- a) Die Beschwerdeführerinnen haben beide Rechtsmittel in einer einzigen Beschwerdeschrift erhoben, was grundsätzlich nicht zu beanstanden ist. Welches Rechtsmittel zulässig ist, ob vorliegend beide Rechtsmittel ergriffen werden können und in welchem Umfang darauf einzutreten ist, prüft das Bundesgericht von Amtes wegen und mit freier Kognition. Entsprechend der subsidiären Natur der staatsrechtlichen Beschwerde ist zunächst zu prüfen, ob die Verwaltungsgerichtsbeschwerde offen steht (BGE 123 II 289 E. 1a S. 290, mit Hinweis).

b) Die Beschwerdeführerinnen rügen hauptsächlich eine Verletzung von Art. 4 Abs. 2 Satz 3 BV. Der in dieser Bestimmung statuierte Anspruch auf gleichen Lohn für gleichwertige Arbeit ist - soweit es wie vorliegend um öffentlichrechtliche Arbeitsverhältnisse geht - ein verfassungsmässiges Recht, welches vorbehältlich anderslautender Regelungen mit staatsrechtlicher Beschwerde durchzusetzen ist (BGE 124 II 409 E. 1a S. 411 f.; 120 Ia 95 E. 1c/bb S. 98 f.; je mit Hinweisen). Dieser Anspruch wird heute durch das am 1. Juli 1996 in Kraft getretene Bundesgesetz vom 24. März 1995 über die Gleichstellung von Frau und Mann konkretisiert, welches bezüglich öffentlichrechtlicher Dienstverhältnisse öffentliches Recht des Bundes darstellt und mit Verwaltungsgerichtsbeschwerde durchgesetzt werden kann (BGE 124 II 409 E. 1d). Vorliegend stehen jedoch einzig Lohnansprüche für die Zeit vor dem Inkrafttreten des Gleichstellungsgesetzes zur Diskussion. Da der erstinstanzliche Entscheid des Regierungsrates bereits am 21. November 1995, mithin vor dem Inkrafttreten des Gleichstellungsgesetzes erging, ist dieses Gesetz gemäss seinem Art. 17 auf die vorliegende Streitsache nicht anwendbar, so dass die Verwaltungsgerichtsbeschwerde unzulässig ist. Auf die staatsrechtliche Beschwerde ist daher einzutreten.

c) Wie es sich mit der Nichtanwendung von Art. 13 Abs. 5 GlG bezüglich der Kosten für das verwaltungsgerichtliche Verfahren verhält, kann angesichts des Ausgangs der staatsrechtlichen Beschwerde offen bleiben.

3.- a) Nach dem insoweit rechtskräftigen Urteil des Appellationsgerichts haben die Beschwerdeführerinnen Anspruch auf den um zwei Lohnklassen höheren Lohn, da die im Lohngesetz vorgesehene Besoldung diskriminierend ist. Zur Diskussion steht einzig, ob dieser Lohnanspruch - wie das Appellationsgericht entschieden hat - erst für die Zeit seit dem 1. November 1993 besteht, oder aber - wie die Beschwerdeführerinnen vorbringen - bereits seit dem 1. Mai 1989.

b) Das Bundesgericht hat am 3. Juli 1998 in einem ähnlich gelagerten Fall entschieden, dass das Lohngleichheitsgebot eine zwingende Bestimmung ist und ein sich daraus ergebender Anspruch im Rahmen der Verjährungsfrist auch nachträglich noch geltend gemacht werden kann. Das ergibt sich aus der Natur des Lohngleichheitsgebots als unmittelbar anwendbares subjektives Individualrecht (BGE 124 II 436 E. 10d/e S. 450 ff.). Zwar gibt das Diskriminierungsverbot grundsätzlich keinen Anspruch auf eine bestimmte Lohnhöhe, sondern nur darauf, dass keine diskriminierenden Lohnunterschiede bestehen. Da es aber rechtlich nicht zulässig ist, rückwirkend Löhne zu reduzieren, kann eine in der Vergangenheit erfolgte Diskriminierung nur dadurch beseitigt werden, dass den rechtswidrig Benachteiligten eine entsprechende Lohnnachzahlung geleistet wird (BGE 124 II 436 E. 11 S. 456 ff.).

c) Im zitierten Urteil war bereits das Gleichstellungsgesetz anwendbar, während der vorliegende Fall einzig nach Art. 4 Abs. 2 Satz 3 BV zu entscheiden ist. Das ändert jedoch nichts an der Beurteilung. Das Bundesgericht ist schon in früheren Entscheiden davon ausgegangen, dass unter der Herrschaft von Art. 4 Abs. 2 BV ein Anspruch auf Nachzahlung besteht (vgl. BGE 124 II 436 E. 10c S. 450, mit Hinweisen). Das entspricht der Rechtslage bei privatrechtlichen Arbeitsverhältnissen, wo das Lohngleichheitsgebot als zwingende Bestimmung im Sinne von Art. 341 Abs. 1 OR gilt (vgl. BGE 124 II 436 E. 10e/bb S. 451 f., mit zahlreichen Hinweisen). Die Tragweite des verfassungsrechtlichen Anspruchs auf Lohngleichheit kann nicht weniger weit gehen als diejenige des privatrechtlichen (BGE 124 II 436 E. 10e/cc S. 452).

d) Das Appellationsgericht ist grundsätzlich gleicher Ansicht. Es geht jedoch davon aus, die Zulässigkeit der Nachforderung werde nicht nur durch den Eintritt der Verjährung, sondern auch in weiteren Fällen eingeschränkt. Soweit keine klare Verletzung des Gleichheitsgebots vorliege, würde die Rechtssicherheit in unerträglicher Weise verletzt, wenn der Arbeitgeber gezwungen wäre, rückwirkend Lohnnachzahlungen zu gewähren. Er müsse deshalb auf die geltende Rechtslage, wie sie durch Lohnabrede oder rechtskräftige Lohnverfügung geschaffen worden sei, vertrauen können und brauche nicht mit rückwirkenden Lohnforderungen zu rechnen. Vorliegend habe der Kanton erst im Oktober 1993 mit der Eröffnung des verwaltungsgerichtlichen Urteils vom 9. Juli 1993 Kenntnis von der Verletzung der Lohngleichheit erhalten. Diejenigen Bediensteten, die nicht vorher bereits eine Lohnnachforderung gestellt hätten, hätten nach Treu und Glauben ihre Ansprüche für die Zeit bis zum Erlass des die Ungewissheit beendenden Gerichtsurteils eingebüsst. Das Appellationsgericht beruft sich damit nicht auf eine kantonalrechtliche Verjährungsbestimmung, sondern auf die Grundsätze der Rechtssicherheit und des Vertrauensschutzes. Das sind bundesverfassungsrechtliche Grundsätze, deren Anwendung das Bundesgericht frei prüft.

e) Im zitierten Urteil vom 3. Juli 1998 hat das Bundesgericht entschieden, dass die im Rahmen des Gleichstellungsgesetzes anwendbare Verjährungsfrist eine bundesrechtliche sei (BGE 124 II 436 E. 10k S. 456). Das muss auch gelten für die unmittelbar aus Art. 4 Abs. 2 Satz 3 BV fliessenden Ansprüche. Es ist somit zu prüfen, ob die vom Appellationsgericht angerufenen verfassungsrechtlichen Grundsätze die bundesrechtliche Verjährungsfrist abzukürzen vermögen.

f) Der Hinweis des Appellationsgerichts auf die Rechtssicherheit läuft darauf hinaus, dass der Zeitraum, für welchen eine Nachzahlung geschuldet ist, davon abhängt, ob die Rechtslage klar und sich der Schuldner seiner Zahlungspflicht bewusst war. Eine solche Auffassung ist willkürlich. Es gibt zahlreiche Fälle, in denen sich ein Schuldner auf Grund einer unklaren Rechts- oder Sachlage seiner Schuld nicht bewusst ist und deren Bestand oder Umfang auch nicht kennen kann. Das ist insbesondere dann der Fall, wenn es um neuere Gesetze geht, deren Auslegung und Tragweite mangels gefestigter Praxis noch nicht ohne weiteres klar ist. Damit ist unausweichlich eine gewisse Rechtsunsicherheit verbunden. Das ist keine Besonderheit des Diskriminierungsverbots, sondern gilt in vielen anderen Bereichen gleichermassen und kann keinen Einfluss auf den Bestand oder die Durchsetzbarkeit einer Forderung haben. Der Zustand der Rechtsunsicherheit wird durch die Verjährung zeitlich begrenzt. Das subjektive Bewusstsein des Schuldners kann diese Frist nicht zusätzlich verkürzen. Dass der Kanton keine Rückstellungen gebildet hat, vermag daran nichts zu ändern. Die Durchsetzbarkeit einer Forderung kann klarerweise nicht davon abhängen, ob der Schuldner Mittel für die Bezahlung bereitgestellt hat. Das gilt auch, wenn der Schuldner ein Gemeinwesen ist; Zahlungen, die sich aus übergeordnetem Recht bzw. aus gerichtlichen Urteilen ergeben, sind gebundene Ausgaben und müssen unabhängig von finanzrechtlichen Gegebenheiten des betreffenden Gemeinwesens geleistet werden (BGE 124 II 436 E. 10h</a> S. 455, mit Hinweisen).

g) Auch die Geltendmachung von Lohnansprüchen ist an die Schranke des Rechtsmissbrauchsverbots bzw. des Gebots von Treu und Glauben gebunden. Wie das Bundesgericht im privaten Arbeitsrecht entschieden hat, ist jedoch das blosse Zuwarten mit der Geltendmachung eines Anspruchs kein Rechtsmissbrauch (BGE 110 II 273 E. 2 S. 275; 105 II 39 E. b S. 42). Generell darf innerhalb der Verjährungsfrist eine Anspruchsverwirkung wegen rechtsmissbräuchlicher Verzögerung nur mit grosser Zurückhaltung angenommen werden (BGE 94 II 37 E. 6b S. 41). Zum Zeitablauf müssen weitere Umstände hinzutreten, welche die Rechtsausübung mit der früheren Untätigkeit des Berechtigten in einem unvereinbaren Widerspruch erscheinen lassen (BGE 116 II 428 E. 2 S. 431; 95 II 109 E. 4 S. 116; 94 II 37 E. 6c S. 42). Der Umstand, dass eine in diskriminierender Weise entlöhnte Stelle angetreten und beibehalten wurde, ohne eine Nachzahlung zu fordern, kann für sich allein nicht als gültiger Verzicht auf die Geltendmachung des Anspruchs auf Lohngleichheit betrachtet werden, wäre doch sonst das Diskriminierungsverbot praktisch nicht durchsetzbar (BGE 124 II 436 E. 10e/dd S. 453). Auch dass sich die Beschwerdeführerinnen am ersten, im Jahre 1987 von 19 Lehrkräften eingeleiteten Verfahren nicht beteiligt haben, vermag keinen rechtsgültigen Verzicht darzustellen. Eine Anspruchsverwirkung infolge Rechtsmissbrauchs kann nicht schon darin liegen, dass die Beschwerdeführerinnen ihren Anspruch später geltend gemacht haben als andere Personen in ähnlicher Situation. Besondere Umstände, welche die Annahme eines Rechtsmissbrauchs begründen könnten, werden vom Kanton nicht vorgebracht.

h) Dass der fragliche Lohn durch die damals anwendbare Besoldungsregelung rechtssatzmässig festgelegt worden war, vermag die Nachforderung ebenfalls nicht auszuschliessen. Denn im Rahmen der Beurteilung individueller Lohnbegehren ist vorfrageweise zu prüfen, ob die für die fragliche Zeitdauer anwendbare generelle Besoldungsregelung mit dem in Art. 4 Abs. 2 BV enthaltenen (seit 1981 in Kraft stehenden) Diskriminierungsverbot vereinbar ist (BGE 124 II 436 E. 10f S. 453 f.).

i) Im Verwaltungsrecht gilt zwar der Grundsatz, dass eine formell rechtskräftige Verfügung ein Rechtsverhältnis verbindlich regelt. Namentlich kann sie in einem späteren Verantwortlichkeitsverfahren nicht mehr in Frage gestellt werden (vgl. Art. 12 VG). In diesem Lichte liesse sich fragen, ob nicht ein Lohn, der durch rechtskräftige Anstellungsverfügung festgelegt wurde, als verbindlich zu gelten hat (vgl. auch das obiter dictum in BGE 105 Ia 120, 122). Jedoch schafft schon nach den Regeln des allgemeinen Verwaltungsrechts eine Verwaltungsverfügung nicht in gleicher Weise materielle Rechtskraft wie ein gerichtliches Urteil. Sie kann unter bestimmten Voraussetzungen nachträglich widerrufen oder angepasst werden, wenn sie sich als rechtswidrig erweist (BGE 121 II 93 E. 3b S. 95, mit Hinweisen; ULRICH HÄFELIN/GEORG MÜLLER, Grundriss des Allgemeinen Verwaltungsrechts, 3. Aufl. Zürich 1998, S. 200 ff.; BLAISE KNAPP, Précis de droit administratif, 4. Aufl. Basel 1991, S. 248 ff.; RENÉ RHINOW/BEAT KRÄHENMANN, Schweizerische Verwaltungsrechtsprechung, Ergänzungsband, Basel 1990, S. 121 ff.). Im Bereich des Lohngleichheitsgebots hätte zudem die Annahme einer materiellen Rechtskraft von Anstellungsverfügungen eine Ungleichbehandlung privatrechtlicher und öffentlichrechtlicher Arbeitsverhältnisse zur Folge. Auch innerhalb der öffentlichrechtlichen Verhältnisse ergäben sich Ungleichbehandlungen je nachdem, ob die Höhe des Lohnes in der Anstellungsverfügung festgelegt ist oder ob diese auf generelle Besoldungsregelungen verweist. Insgesamt würde so die Durchsetzbarkeit des verfassungsrechtlichen Lohngleichheitsgebots in einem unerträglichen Mass von Zufälligkeiten in der Ausgestaltung des Arbeitsverhältnisses abhängen. Das Bundesgericht hat daher schon mehrmals entschieden, dass das Verbot der Lohndiskriminierung im öffentlichen und privaten Arbeitsverhältnis unterschiedslos gilt, und - ausser in dem genannten obiter dictum in BGE 105 Ia 120 - nie darauf abgestellt, ob eine formelle Anstellungsverfügung vorliegt oder nicht (vgl. BGE 124 II 436 E. 10e</a>/cc/dd S. 452 f.; 117 Ia 262 E. 3c S. 267, 270 E. 2b S. 272 f.). Im Gegenteil wurde in BGE 118 Ia 35 die staatsrechtliche Beschwerde einer Berufsberaterin gutgeheissen, welche 1982 durch Regierungsratsbeschluss in eine bestimmte Lohnklasse eingereiht worden war und erst im Jahre 1988 eine Nachforderung gestellt hatte. Das setzt voraus, dass eine Nachforderung auch zulässig ist, wenn die ursprüngliche Einreihung mit förmlichem Beschluss festgesetzt wurde.

k) Der in Art. 4 Abs. 2 Satz 3 BV enthaltene Anspruch auf diskriminierungsfreien Lohn kann somit im Rahmen der ordentlichen Verjährungsfrist auch nachträglich geltend gemacht werden. Das Appellationsgericht hat diese Bestimmung verletzt, indem es den Anspruch der Beschwerdeführerinnen auf Lohnnachzahlung erst seit dem 1. November 1993 anerkannt hat.