(USG; LRV; kant. Massnahmenplan; Parkplatzvorschriften), hat sich ergeben:
A.- Die Genossenschaft Coop Basel Liestal Fricktal beabsichtigt, auf dem in Zone 4 mit Gewerbeerleichterung liegenden Areal St. Jakobs-Strasse 175 in Basel einen Verbrauchermarkt mit einer Verkaufsfläche von rund 14'500 m2 zu errichten. Das Bauinspektorat des Kantons Basel-Stadt lehnte das entsprechende generelle Baubegehren, dem ein Umweltverträglichkeitsbericht (UVB) und ein Verkehrsgutachten beigefügt waren, am 4. Februar 1997 ab. Es stellte insbesondere fest, das Projekt erfülle die zonenrechtlichen Anforderungen gemäss dem Hochbautengesetz vom 11. Mai 1939 (HBG) nicht und die geplanten 700 Parkplätze widersprächen den Zielen der Luftreinhaltung. Gleichzeitig formulierte das Bauinspektorat die Bedingungen und Auflagen, die bei einem Baubegehren zu berücksichtigen wären. U.a. verlangte es einen vom Grossen Rat zu genehmigenden Überbauungsplan und die Beschränkung auf 310 Parkplätze.
Gegen diesen Entscheid gelangte die Coop Basel Liestal Fricktal an die Baurekurskommission des Kantons Basel-Stadt, welche den Rekurs am 29. Oktober 1997 teilweise guthiess. Die Kommission bezeichnete die vorgesehene Nutzung als grundsätzlich zonenkonform, bestätigte indessen die Beschränkung auf 310 Parkplätze.
B.- Die Coop Basel Liestal Fricktal gelangte gegen den Rekursentscheid an das Appellationsgericht des Kantons Basel-Stadt, welches (als Verwaltungsgericht) das Rechtsmittel teilweise guthiess und die Sache zur Neubeurteilung im Sinne der Erwägungen an die Vorinstanz zurückwies. Den Erwägungen ist zu entnehmen, dass das Appellationsgericht insgesamt 567 Parkplätze für zulässig erachtet.
C.- Der Verkehrs-Club der Schweiz (VCS) führt gegen das Urteil des Appellationsgerichts vom 12. Februar 1999 beim Bundesgericht Verwaltungsgerichtsbeschwerde. Neben verfahrensrechtlichen Anträgen ersucht er um die Rückweisung der Angelegenheit an die Vorinstanz, eventuell um die generelle Bewilligung von 310 Parkplätzen.
Das Appellationsgericht und Coop Basel Liestal Fricktal schliessen auf Abweisung der Beschwerde. Das Baudepartement des Kantons Basel-Stadt hält an der Begrenzung der Anzahl Parkplätze auf 310 fest.
Das Bundesamt für Umwelt, Wald und Landschaft hat am 14. September 1999 zur Beschwerde Stellung genommen. Die Parteien erhielten Gelegenheit, sich dazu zu äussern. Ausserdem fand ein zweiter Schriftenwechsel statt. Dabei zog der VCS seine formellen Anträge zurück. Die übrigen Verfahrensbeteiligten halten an ihren Anträgen fest.

Das Bundesgericht zieht in Erwägung:
1.- Die Verwaltungsgerichtsbeschwerde ist zulässig gegen Verfügungen, die sich auf öffentliches Recht des Bundes stützen oder hätten stützen sollen (<ref-law> in Verbindung mit Art. 97 OG), sofern diese von einer in Art. 98 OG genannten Vorinstanz erlassen worden sind und keiner der in Art. 99 ff. OG oder in der Spezialgesetzgebung vorgesehenen Ausschlussgründe greift. Sodann unterliegen der Verwaltungsgerichtsbeschwerde gemischtrechtliche Verfügungen bzw. (auch) auf unselbständiges kantonales Ausführungsrecht zum Bundesrecht gestützte Anordnungen sowie auf übrigem kantonalem Recht beruhende Anordnungen, die einen hinreichend engen Sachzusammenhang mit der im Rahmen der Verwaltungsgerichtsbeschwerde zu beurteilenden Frage des Bundesverwaltungsrechts aufweisen. Soweit dem angefochtenen Entscheid selbständiges kantonales Recht ohne den genannten Sachzusammenhang zum Bundesrecht zugrunde liegt, steht die staatsrechtliche Beschwerde zur Verfügung (<ref-ruling> E. 1a/aa). Soweit die Verwaltungsgerichtsbeschwerde zulässig ist, kann der Beschwerdeführer auch geltend machen, der angefochtene Entscheid verletze Bundesverfassungsrecht, weil dieses zum Bundesrecht im Sinne von Art. 104 lit. a OG gehört (<ref-ruling> E. 2d/bb S. 47 mit Hinweisen).
a) Der angefochtene Entscheid ist in Anwendung sowohl von Bundesrecht wie von kantonalem Recht ergangen. Beim angewendeten Bundesrecht handelt es sich um das Bundesgesetz über den Umweltschutz vom 7. Oktober 1983 (Umweltschutzgesetz, USG; SR 814. 01) und die Luftreinhalte-Verordnung vom 16. Dezember 1985 (LRV; SR 814. 318.142. 1). Weiter beruht das angefochtene Urteil auf der Verordnung des Regierungsrats des Kantons Basel-Stadt vom 22. Dezember 1992 über die Erstellung von Parkplätzen für Personenwagen auf privatem Grund (Parkplatzverordnung, PPV). Die Parkplatzverordnung wurde in Konkretisierung des Luftreinhalteplans beider Basel vom Februar 1990 erlassen und steht mit der Umweltschutzgesetzgebung des Bundes in engem sachlichem Zusammenhang. Ihre Anwendung ist entsprechend der zitierten Praxis im Rahmen der Verwaltungsgerichtsbeschwerde zu prüfen. Hinsichtlich der Anwendung des kantonalen Rechts richtet sich die Kognition des Bundesgerichts nach den für die staatsrechtliche Beschwerde geltenden Grundsätzen (<ref-ruling> E. 1b mit Hinweisen).
Die vom Beschwerdeführer vorgebrachten Rügen können vollumfänglich im Rahmen des Verfahrens der Verwaltungsgerichtsbeschwerde behandelt werden. Für die subsidiäre staatsrechtliche Beschwerde bleibt somit kein Raum. Soweit der Beschwerdeführer seine Eingabe als staatsrechtliche Beschwerde verstanden haben will, ist darauf nicht einzutreten.
b) Dementsprechend hätte das Appellationsgericht seinen Entscheid mit einer Rechtsmittelbelehrung versehen (Art. 35 Abs. 1 und 2 in Verbindung mit <ref-law>) und mit der Aktenauflösung bis nach Ablauf der Rechtsmittelfrist zuwarten sollen. Da der Beschwerdeführer seine diesbezüglichen Rügen zurückgezogen hat, erübrigen sich weitere Bemerkungen dazu.
c) Das Bauvorhaben untersteht der Umweltverträglichkeitsprüfung (UVP) gemäss <ref-law>. Der Beschwerdeführer erfüllt die Voraussetzungen von <ref-law> und ist daher zur Beschwerde legitimiert. Da er sich am kantonalen Verfahren von Anfang an beteiligt hat (Art. 55
Abs. 4 und 5 USG) und auch die übrigen formellen Voraussetzungen erfüllt sind, ist auf die Beschwerde grundsätzlich einzutreten.
d) Nicht einzutreten ist auf die Beschwerde allerdings insoweit, als der Beschwerdeführer die zonenplanerischen
Voraussetzungen des Projekts in Frage stellt. Die kantonale Baurekurskommission hat die vorgesehene Nutzung abweichend vom Bauinspektorat als grundsätzlich zonenkonform bezeichnet. Der Beschwerdeführer hat sich damit abgefunden, weshalb auch das Appellationsgericht auf diesen Punkt ausdrücklich nicht mehr eingegangen ist. Insofern fehlt es an der Erschöpfung des Instanzenzugs (Art. 98 lit. g OG) und hat sich das Bundesgericht mit der Zonenkonformität ebenfalls nicht mehr zu befassen.
e) Der rechtserhebliche Sachverhalt ergibt sich hinreichend deutlich aus den Akten. Es besteht kein Anlass, einen Augenschein vorzunehmen.
2.- Zu entscheiden ist, ob das Appellationsgericht zu Recht 567 Parkplätze, an Stelle der von der Baurekurskommission bewilligten 310 Plätze, als zulässig bezeichnet hat.
a) Bei der geplanten Überbauung handelt es sich um eine (neue) Anlage im Sinne von <ref-law>, die Einwirkungen u.a. in Form vom Luftverunreinigungen erzeugen wird. Diese sind gesamthaft zu beurteilen, d.h. es sind alle Emissionen zu berücksichtigen, die durch die bestimmungsgemässe Nutzung der Anlage verursacht werden, einschliesslich der von den Bewohnern, Beschäftigten, Besuchern und Kunden verursachten Verkehrsemissionen in der Umgebung der Anlage (<ref-ruling> E. 2a mit Hinweisen).
Vorliegend ist unbestritten, dass das Baugrundstück in einem lufthygienisch übermässig belasteten Gebiet liegt. So wird der Jahresmittelgrenzwert gemäss Anhang 7 LRV für Stickstoffdioxid (NO2) um gut 50% überschritten und liegt auch die Belastung mit Ozon und Schwebestaub (PM10) über den Immissionsgrenzwerten. Daher ist das Vorhaben nicht nur vorsorglichen, sondern verschärften Emissionsbegrenzungen zu unterstellen (<ref-law>, Art. 9 Abs. 4 und Art. 31 ff. LRV). Unbestritten ist ferner, dass die übermässigen Belastungen zu einem erheblichen Teil durch den motorisierten Individualverkehr verursacht werden.
b) Verursachen, wie hier, eine Vielzahl von Anlagen die übermässige Luftbelastung, so sind die erforderlichen Emissionsbegrenzungen durch einen Massnahmenplan gemäss <ref-law> und Art. 31 ff. LRV zu koordinieren (vgl. dazu ausführlich <ref-ruling> E. 4a S. 279 mit Hinweisen). Es ist grundsätzlich Sache des Massnahmenplans, die für die Verbesserung der Luftqualität erforderlichen Massnahmen aufzuzeigen, Art und Weise ihres Vollzugs zu bestimmen und den Realisierungszeitraum festzulegen (vgl. Art. 32 Abs. 1 lit. e-g LRV in der Fassung vom 15. Dezember 1997).
aa) Vorliegend massgebend ist der "Luftreinhalteplan beider Basel" vom Februar 1990, ergänzt durch die "Standortbestimmung 1995 und Nachfolgestrategie". Der Plan sieht neben Massnahmen im Bereich Nutzungsplanung und zur Verbesserung des öffentlichen Verkehrs eine Änderung der Parkraumpolitik vor. Der Massnahmenplan geht davon aus, dass die Verringerung von Parkierungsmöglichkeiten an den Zielorten über kurz oder lang zu einer Verringerung von Autofahrten, zu Fahrverzichten oder zur vermehrten Benützung der öffentlichen Verkehrsmittel und damit zu einer Abnahme der verkehrsbedingten Emissionen führt. Massnahme V 2.3 sieht daher vor, dass die kantonalen Baugesetze im Sinne einer Plafonierung der Anzahl der erforderlichen bzw. zulässigen Parkplätze bei Neubauten, Umbauten und Nutzungsänderungen, die sich auf den Motorfahrzeugverkehr auswirken, geändert bzw. ergänzt werden. Dementsprechend wurde das Hochbautengesetz des Kantons Basel-Stadt am 13. März 1991 durch einen § 132a mit folgendem Wortlaut ergänzt:
"1 Der Regierungsrat bestimmt durch Verordnung die maximal zulässige Anzahl der Parkplätze bei Neubauten und wesentlichen Änderungen bestehender Bauten.
2 Die Regelung hat folgende Kriterien zu berücksichtigen:
a) die überbaute Fläche;
b) anhand der Erfahrung gewonnene Mittelwerte für die Anzahl Wohnungen bzw. Arbeitsplätze, die auf der vorgesehenen Fläche eingerichtet werden können;
c) die Qualität der bereits vorhandenen Verkehrserschliessung, insbesondere die Erreichbarkeit mit öffentlichen Verkehrsmitteln.
3 Die maximal zulässige Zahl der Parkplätze gemäss dieser Regelung soll in der Regel 1,0 pro Wohnung bzw. 0,2 pro Arbeitsplatz nicht überschreiten. "
bb) Der Regierungsrat erliess die auf § 132a HBG gestützte Parkplatzverordnung (PPV) am 22. Dezember 1992 und unterzog sie am 26. Januar 1999 einer ab 31. Januar 1999 wirksamen Teilrevision. Bei Ladengeschäften ergibt sich die Zahl der Parkplätze durch Multiplikation der nach § 6 PPV ermittelten Ausgangszahl mit dem Faktor für die Qualität der Erschliessung mit öffentlichen Verkehrsmitteln gemäss § 5 Abs. 2 (vgl. § 7 PPV).
Die Ausgangszahl gemäss § 6 PPV wächst degressiv mit der Bruttogeschossfläche (BGF) gemäss einer in § 6 Abs. 1 enthaltenen Tabelle für Flächen bis 10'000 m2. Für Läden über 10'000 m2 BGF legt das Baudepartement die Ausgangszahl in einer Richtlinie mit degressivem Zuwachs fest (§ 6 Abs. 3 PPV).
§ 5 Abs. 2 PPV unterscheidet drei Faktoren für die Qualität der Erschliessung mit öffentlichen Verkehrsmitteln:
- 0.7 für das Kerngebiet,
- 0.8 für gute bis durchschnittliche Erschliessung,
- 1.0 für durchschnittliche bis schlechte Erschliessung.
Gemäss § 5 Abs. 3 PPV ergeben sich die drei Gebiete aus dem Plan des Hochbau- und Planungsamtes Nr. 11799 vom 9. Dezember 1992. Der Plan (im Format A3) weist das ganze städtische Siedlungsgebiet einer dieser drei Erschliessungsqualitäten zu.
Kraft § 9 PPV kann das Baudepartement "in einzelnen Fällen, wenn das öffentliche Interesse eine Abweichung erheischt, eine grössere Anzahl von Parkplätzen bewilligen".
3.- a) Alle kantonalen Instanzen haben übereinstimmend festgestellt, dass die Ausgangszahl gemäss § 6 PPV, entsprechend der massgeblichen Bruttogeschossfläche von 19'160 m2, 338 Parkplätze beträgt. Sie beruht auf einem Ergänzungsblatt zur Parkplatzverordnung des kantonalen Hochbau- und Planungsamtes für Läden bis 100'000 m2 BGF vom 16. Oktober 1995, das entsprechend § 6 PPV einen degressiven Zuwachs der Parkplätze vorsieht. Die Anwendung dieser Richtlinie ergibt für 19'000 m2 BGF 336 Parkplätze; für die zusätzlichen 120 m2 BGF wurden noch zwei weitere Parkplätze zugestanden, was nicht zu beanstanden ist.
b) Bei der Ermittlung des massgeblichen Erschliessungsfaktors hat das Appellationsgericht angenommen, der Plan des Hochbau- und Planungsamtes vom 9. Dezember 1992 stelle eine für das Gericht nicht verbindliche Verwaltungsverordnung oder Dienstanweisung dar. Das Gericht hielt sich daher für berechtigt, frei zu überprüfen, welche Erschliessungsqualität das Baugrundstück aufweist.
c) Dieser Auffassung kann nicht beigepflichtet werden. Die Parkplatzverordnung des Regierungsrats verweist ausdrücklich auf den genau bezeichneten und damit eindeutig identifizierten Plan, der beim Erlass der Parkplatzverordnung bereits vorlag. Damit hat der Regierungsrat den Plan zum Bestandteil der Parkplatzverordnung gemacht und die Faktoren für die Erschliessungsqualität für das gesamte Siedlungsgebiet verbindlich festgelegt. Dabei kann dahingestellt bleiben, ob der Plan als solcher publiziert wurde. Es genügt, dass er in der (unbestrittenermassen korrekt publizierten) Verordnung eindeutig bezeichnet wurde. Weiter steht ausser Zweifel, dass er beim Hochbauamt eingesehen werden kann.
Die Rechtslage lässt sich mit jener vergleichen, die beim Bundesinventar der Landschaften und Naturdenkmäler von nationaler Bedeutung (BLN) sowie den verschiedenen Verordnungen zum Schutz von Biotopen von nationaler Bedeutung anzutreffen ist. Diese Objekte werden in einer bundesrätlichen Verordnung aufgezählt, jedoch in einer gesonderten Publikation umschrieben und planlich abgegrenzt. Diese Publikation wird nicht amtlich veröffentlicht, kann aber bei näher bezeichneten Amtsstellen jederzeit eingesehen werden (vgl. z.B. Art. 1 und 2 der Verordnung vom 7. September 1994 über den Schutz der Flachmoore von nationaler Bedeutung; SR 451. 33). Die Umschreibung und Abgrenzung dieser Objekte ist damit, unter Vorbehalt der Aufgaben der Kantone, durch die Verordnung des Bundesrats geregelt.
d) Eine Überprüfung der Erschliessungsqualität des betroffenen Gebiets hätte daher nur im Rahmen einer akzessorischen Normenkontrolle vorgenommen werden können. Das Appellationsgericht hat nicht dargelegt, und es deutet im Übrigen auch nichts darauf hin, dass die entsprechenden Voraussetzungen erfüllt sind. Zunächst würde sich die Frage stellen, ob die fragliche Zuordnung nicht den Charakter eines Nutzungsplans aufweist, so dass eine akzessorische Überprüfung von vornherein nur unter den diesbezüglich geltenden Voraussetzungen (vgl. <ref-ruling> E. 5c S. 486 mit Hinweisen) in Frage käme. Falls eine akzessorische Überprüfung zulässig wäre - was hier offen bleiben kann - wäre jedenfalls zu beachten gewesen, dass die Delegationsnorm von § 132a HBG dem Regierungsrat einen erheblichen Beurteilungsspielraum zugesteht, der sich u.a. auf die Festlegung bzw. Beurteilung der Erschliessungsqualität bezieht. In diesem Fall durfte das Gericht nicht in den Gestaltungsbereich eingreifen, welcher kraft gesetzlicher Vorschrift dem Regierungsrat zusteht, sondern konnte lediglich prüfen, ob die Verordnung den Rahmen der dem Regierungsrat delegierten Kompetenzen sprenge oder sich aus anderen Gründen als gesetz- oder verfassungswidrig erweise (<ref-ruling> E. 2a; <ref-ruling> E. 3a und 4a/b S. 102 ff., je mit Hinweisen).
Diese Fragen hat das Appellationsgericht nicht geprüft. Es hat die Lage des Baugrundstücks lediglich mit anderen, besonders gut gelegenen Grundstücken im Gebiet mit guter bis durchschnittlicher Erschliessung verglichen und auf gewisse nicht bestreitbare Mängel der Erschliessung des Baugrundstücks hingewiesen. Allerdings ist festzustellen, dass sich in knapp 10 Minuten Fussdistanz zwei Tramhaltestellen befinden, ab denen mit insgesamt vier Linien direkte Verbindungen zur Innerstadt und weiteren Quartieren bestehen. Wenn der Regierungsrat diese Erschliessung als gut bis durchschnittlich klassiert hat, hat er jedenfalls die ihm zustehenden Kompetenzen im Rahmen der Beurteilung der Erschliessungsqualität nicht überschritten. Das Appellationsgericht hatte daher offensichtlich keinen Anlass, die Parkplatzverordnung in diesem Punkt nicht anzuwenden.
e) Damit ergibt sich in Anwendung von § 9 PPV eine Parkplatzzahl von 338 x 0.8, d.h. 270, zuzüglich der nicht umstrittenen je 20 Parkplätze für Angestellte und Fahrzeuge mit alternativem Antrieb, total 310. Dies entspricht der Berechnung, welche die kantonalen Verwaltungsbehörden vorgenommen haben und die vom Beschwerdeführer anerkannt wurde.
4.- Umstritten ist weiter, ob das Appellationsgericht eine Erhöhung der Parkplatzzahl im Sinne einer Ausnahme anordnen durfte, weil § 9 PPV in der bis 31. Januar 1999 geltenden Fassung einen Abs. 2 mit folgendem Wortlaut enthielt:
"Für Läden können, wenn ein entsprechendes Bewirtschaftungskonzept vorliegt, zusätzliche Parkplätze für die Spitzen am Freitag und am Samstag gestattet werden; in der übrigen Zeit müssen diese Parkplätze durch geeignete Massnahmen für das Abstellen von Fahrzeugen geschlossen werden. "
Dieser Absatz wurde mit der Revision der Parkplatzverordnung vom 26. Januar 1999 (in Kraft seit 31. Januar 1999) ersatzlos gestrichen.
a) Das Appellationsgericht hat in seinem Urteil vom 12. Februar 1999 ohne weitere Begründung unter Hinweis auf seine Praxis erwogen, es übe grundsätzlich eine nachträgliche Kontrolle aufgrund der tatsächlichen und rechtlichen Verhältnisse zur Zeit des angefochtenen Entscheids aus. Im konkreten Fall lägen keine Gründe für ein abweichendes Vorgehen vor. Massgeblich für die Beurteilung sei daher die bis zum 25. (bzw. 30.) Januar 1999 geltende Fassung der Parkplatzverordnung. Der Beschwerdeführer verlangt hingegen eine Beurteilung nach der Rechtslage, wie sie seit dem 31. Januar 1999 in Kraft steht.
b) Umstritten ist somit die intertemporalrechtliche Frage, ob im Rechtsmittelverfahren gegen baurechtliche Bewilligungen das im Entscheidungszeitpunkt geltende Recht massgebend ist oder ob auf das im Zeitpunkt der Gesuchseinreichung oder des Erlasses der unterinstanzlichen Verfügung in Kraft stehende Recht abzustellen ist. Diese Frage wird, soweit ersichtlich, im Recht des Kantons Basel-Stadt nicht ausdrücklich geregelt. Die Praxis und die rechtliche Regelung in den Kantonen ist uneinheitlich und wird in der Lehre teilweise kritisiert (Alfred Kölz, Intertemporales Verwaltungsrecht, in ZSR 102/1983, 2. Halbbd. , S. 101 ff., S. 208 f.; René Rhinow/Beat Krähenmann, Schweizerische Verwaltungsrechtsprechung, Ergänzungsband, Nr. 15 IIa; Leo Schürmann/ Peter Hänni, Planungs-, Bau- und besonderes Umweltschutzrecht, 3. Aufl. , Bern 1995, S. 257; Walter Haller/Peter Karlen, Raumplanungs-, Bau- und Umweltrecht, 3. Aufl. , Zürich 1999, S. 222 f.; Aldo Zaugg, Kommentar zum Baugesetz des Kantons Bern vom 9. Juni 1985, N. 1 zu Art. 148; vgl. <ref-ruling> E. 5e/aa S. 598; <ref-ruling> E. 2a; <ref-ruling> E. 1c; <ref-ruling> E. 2a S. 137, je mit Hinweisen).
c) Wie es sich damit im Einzelnen verhält, ist im vorliegenden Verfahren nicht zu prüfen, da die Parkplatzverordnung aufgrund ihrer Funktion und der Rechtsprechung des Bundesgerichts zur Anwendung umweltrechtlicher Normen im Rechtsmittelverfahren in ihrer neuen Fassung sofort anzuwenden ist. In Erwägung 2b/aa hiervor wurde festgestellt, dass die Parkplatzverordnung unmittelbar lufthygienische Ziele verfolgt, soweit sie die Zahl der zulässigen Parkplätze begrenzt. Diese Verordnung ist somit als umweltrechtlicher Erlass zu bezeichnen. Das Bundesgericht hat in konstanter Rechtsprechung entschieden, dass Änderungen umweltrechtlicher Erlasse um der öffentlichen Ordnung willen auf alle noch nicht (letztinstanzlich) abgeschlossenen Verfahren anzuwenden seien (<ref-ruling> E. 5e/aa S. 598; <ref-ruling> E. 4c/cc S. 331; <ref-ruling> E. 3a; <ref-ruling> E. 1c S. 42, je mit Hinweisen).
Es besteht vorliegend kein Anlass, vom Grundsatz der sofortigen Anwendbarkeit umweltrechtlicher Normen abzuweichen. In der Standortbestimmung 1995 und der Nachfolgestrategie zum Luftreinhalteplan beider Basel wird festgehalten, dass weiterhin Handlungsbedarf besteht. Die NOx- Emissionen lagen in den beiden Basel 1994 zwischen 7'500 und 8'000 Tonnen pro Jahr und damit weit über dem angestrebten Emissionsziel von 3'500 Tonnen pro Jahr. Auch heute sind, wie das Appellationsgericht festgestellt hat, die Immissionsgrenzwerte zum Teil deutlich überschritten.
Die tatsächlichen Verhältnisse belegen die Notwendigkeit, die Bemühungen um eine verbesserte Luftqualität unvermindert fortzusetzen.
d) In seiner Vernehmlassung an das Bundesgericht deutet das Appellationsgericht an, die Änderung der Parkplatzverordnung sei möglicherweise mit Blick auf den vorliegenden Fall vorgenommen worden. Indessen fehlen für diese Behauptung ausreichende Hinweise. Die Aufhebung von § 9 Abs. 2 PPV erfolgte im Zusammenhang einer Revision, die verschiedene Anliegen aufgriff. Es liegt nichts vor, was die Berücksichtigung der Verordnungsänderung in der vorliegenden Angelegenheit als gegen Treu und Glauben verstossend erscheinen liesse.
e) Es ergibt sich zusammenfassend, dass das Appellationsgericht den aufgehobenen § 9 Abs. 2 PPV zu Unrecht angewendet hat. Die Verwaltungsgerichtsbeschwerde ist daher insoweit gutzuheissen, ohne dass die übrigen Rügen des Beschwerdeführers geprüft werden müssten, und das angefochtene Urteil ist aufzuheben. Angesichts des im Übrigen nicht angefochtenen Rückweisungsentscheids der Baurekurskommission vom 29. Oktober 1997 wird sich nun wiederum das Bauinspektorat mit der Sache zu befassen haben.
5.- Entsprechend dem Ausgang des bundesgerichtlichen Verfahrens wird die Beschwerdegegnerin kostenpflichtig (Art. 156 Abs. 1 OG). Zudem hat sie den Beschwerdeführer für dessen Aufwand im bundesgerichtlichen Verfahren angemessen zu entschädigen (Art. 159 Abs. 2 und 3 OG).

Demnach erkennt das Bundesgericht:
1.- Die Verwaltungsgerichtsbeschwerde wird gutgeheissen, soweit darauf eingetreten wird. Das Urteil des Appellationsgerichts (als Verwaltungsgericht) des Kantons Basel-Stadt vom 12. Februar 1999 wird aufgehoben.
2.- Die Gerichtsgebühr von Fr. 4'000. -- wird der Beschwerdegegnerin auferlegt.
3.- Die Beschwerdegegnerin hat dem Beschwerdeführer eine Parteientschädigung von Fr. 3'000. -- zu bezahlen.
4.- Dieses Urteil wird den Parteien, dem Bauinspektorat, der Baurekurskommission und dem Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht sowie dem Bundesamt für Umwelt, Wald und Landschaft schriftlich mitgeteilt.
_
Lausanne, 26. Mai 2000
Im Namen der I. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident:
Der Gerichtsschreiber: