Nichterneuerung der Aufenthaltsbewilligung, hat sich ergeben:
A.- Der türkische Staatsangehörige K._ heiratete am 23. November 1992 in seiner Heimat die Schweizer Bürgerin H._. Er reiste am 20. Februar 1993 in die Schweiz ein und erhielt am 19. März 1993 eine Aufenthaltsbewilligung zum Verbleib bei der Ehefrau.
B.- Die Kantonale Fremdenpolizei Basel-Stadt (im Folgenden:
Fremdenpolizei) verfügte am 27. November 1996, die K._ erteilte und letztmals bis zum 23. November 1996 verlängerte Aufenthaltsbewilligung werde nicht mehr erneuert.
Sie hielt dafür, K._ habe sich "die Ehe. ..
mit Geld erkauft" und an deren formellem Bestand werde in rechtsmissbräuchlicher Weise festgehalten.
Das Polizei- und Militärdepartement des Kantons Basel-Stadt wies am 10. September 1999 den hiegegen eingereichten Rekurs ab und setzte K._ bis 15. November 1999 Frist zur Ausreise. Auch es nahm eine Scheinehe an; zudem sei die Berufung auf die Ehe rechtsmissbräuchlich.
Das rechtsmissbräuchliche Verhalten habe schon vor Ablauf von fünf Ehejahren bestanden; deshalb könne K._ "heute gestützt auf seine Ehe weder die Niederlassung erteilt noch die Aufenthaltsbewilligung erneuert werden".
Der gegen den Departementsentscheid beim Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht (im Folgenden: Verwaltungsgericht) erhobene Rekurs blieb erfolglos. In seinem Urteil vom 20. Mai 2000 hielt das Verwaltungsgericht fest, dass im angefochtenen Entscheid zahlreiche Indizien dargelegt würden, aus denen das Vorliegen einer Scheinehe angenommen werden könne, liess diese Frage aber offen, da "von einem krassen Fall missbräuchlicher Berufung auf eine nur noch formell aufrechterhaltene Ehe auszugehen" sei; auch das Rückenleiden, auf das sich K._ berufe, vermöge keinen Anspruch auf die Verlängerung der Aufenthaltsbewilligung zu begründen.
C.- Hierauf hat K._ am 28. Juni 2000 beim Bundesgericht Verwaltungsgerichtsbeschwerde eingereicht mit folgenden Rechtsbegehren:
"1.Es sei das angefochtene Urteil des Appellationsgerichts
des Kantons Basel-Stadt aufzuheben und
dem Beschwerdeführer die Aufenthaltsbewilligung
zu erteilen.
Eventualiter seien die Akten im Sinne der Erwägungen
an die Vorinstanz zurückzuweisen.
2. Es sei der vorliegenden Beschwerde die aufschiebende
Wirkung zu erteilen.
3. Es sei dem Beschwerdeführer die unentgeltliche
Rechtspflege und Verbeiständung durch den Unterzeichneten
zu gewähren.
4. Alles unter o/e-Kostenfolge zulasten des Kantons
Basel-Stadt.. "
D.- Das Verwaltungsgericht sowie das Polizei- und Militärdepartement des Kantons Basel-Stadt schliessen auf Abweisung der Beschwerde. Das Bundesamt für Ausländerfragen wurde nicht zur Vernehmlassung aufgefordert.
E.- Mit Verfügung vom 3. Juli 2000 wies der Präsident der II. öffentlichrechtlichen Abteilung das Gesuch um aufschiebende Wirkung ab. Am gleichen Tag wies das Bundesgericht das Begehren um Gewährung der unentgeltlichen Rechtspflege ab. In der Folge bezahlte K._ den verlangten Kostenvorschuss.
F.- Mit Eingabe vom 26. Juli 2000 stellte K._ ein Ausstandsgesuch gegen den Abteilungspräsidenten sowie gegen die Richter und die Gerichtsschreiber, die am Entscheid über die Verweigerung der unentgeltlichen Rechtspflege bzw. an einem früheren Urteil (2P. 2/2000) mitgewirkt hatten, mit dem eine staatsrechtliche Beschwerde gegen die Verweigerung der unentgeltlichen Rechtspflege im kantonalen Verfahren abgewiesen worden war.

Das Bundesgericht zieht in Erwägung:
1.- Die Gerichtspersonen, gegen welche sich das Ausstandsbegehren vom 26. Juli 2000 richtet, wirken am vorliegenden Entscheid nicht mit. Aus diesem Grunde ist das Ausstandsgesuch gegenstandslos. Im Übrigen genügt für eine unzulässige Vorbefassung, die zum Ausstand führen müsste, nicht der Umstand allein, dass die Gerichtspersonen zuvor Gesuche um unentgeltliche Rechtspflege wegen offensichtlicher Aussichtslosigkeit der Beschwerdebegehren in der Sache abgewiesen haben (nicht veröffentlichte Urteile des Bundesgerichts vom 23. August 1994 i.S. Sahinli, E. 3c, und vom 23. September 1994 i.S. Krasniqi, E. 4b; vgl. auch <ref-ruling> E. 5b S. 20; <ref-ruling> E. 3d S. 57). Es müssten weitere tatsächliche Gesichtspunkte hinzukommen, die der Beschwerdeführer indes nicht geltend gemacht hat (vgl. Art. 25 OG).
2.- a) Nach Art. 100 Abs. 1 lit. b Ziff. 3 OG ist die Verwaltungsgerichtsbeschwerde auf dem Gebiet der Fremdenpolizei unzulässig gegen die Erteilung oder Verweigerung von Bewilligungen, auf die das Bundesrecht keinen Anspruch einräumt.
Gemäss Art. 4 des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; SR 142. 20) entscheidet die zuständige Behörde, im Rahmen der gesetzlichen Vorschriften und der Verträge mit dem Ausland, nach freiem Ermessen über die Bewilligung von Aufenthalt und Niederlassung. Der Ausländer hat damit grundsätzlich keinen Anspruch auf Erteilung bzw. Verlängerung einer Aufenthaltsbewilligung, und die Verwaltungsgerichtsbeschwerde ist ausgeschlossen, soweit er sich nicht auf eine Sondernorm des Bundesrechts oder eines Staatsvertrags berufen kann, die ihm einen Anspruch auf eine solche Bewilligung einräumt (<ref-ruling> E. 1a S. 363 f., mit Hinweisen).
b) aa) Der Beschwerdeführer kann aus dem von ihm im Hinblick auf sein Rückenleiden angeführten Art. 13 lit. b der Verordnung vom 6. Oktober 1986 über die Begrenzung der Zahl der Ausländer (Begrenzungsverordnung, BVO; SR 823. 21) keinen Anspruch auf Erteilung einer Aufenthaltsbewilligung ableiten (<ref-ruling> E. 1a S. 188, mit Hinweisen). Ebenso wenig kann er sich auf Art. 60 Abs. 2 des Asylgesetzes vom 26. Juni 1998 (AsylG, SR 142. 31) berufen, da ihm in der Schweiz kein Asyl gewährt wurde.
bb) Gemäss Art. 7 ANAG hat der ausländische Ehegatte eines Schweizer Bürgers Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung (Abs. 1 Satz 1); der Anspruch erlischt, wenn ein Ausweisungsgrund vorliegt (Abs. 1 Satz 3). Kein Anspruch besteht, wenn die Ehe eingegangen worden ist, um die Vorschriften über Aufenthalt und Niederlassung von Ausländern und namentlich jene über die Begrenzung der Zahl der Ausländer zu umgehen (Abs. 2). Im Zusammenhang mit der Eintretensfrage ist aber einzig darauf abzustellen, ob formell eine eheliche Beziehung besteht; anders als bei Art. 8 EMRK ist nicht erforderlich, dass die Ehe intakt ist und tatsächlich gelebt wird (<ref-ruling> E. 1b S. 266; <ref-ruling> E. 1b S. 292, mit Hinweisen).
c)Im vorliegenden Fall lebt der Beschwerdeführer von seiner schweizerischen Ehefrau getrennt. Die Ehe ist bisher aber nicht geschieden worden, so dass grundsätzlich ein Rechtsanspruch auf Bewilligungserteilung besteht. Die Frage, ob die Bewilligung zu verweigern sei, weil einer der in Art. 7 ANAG vorgesehenen Ausnahmetatbestände oder ein Verstoss gegen das Rechtsmissbrauchsverbot gegeben ist, betrifft nicht das Eintreten, sondern bildet Gegenstand der materiellen Beurteilung (<ref-ruling> E. 1b S. 266; <ref-ruling> E. 2b S. 291, je mit Hinweisen). Auf die Verwaltungsgerichtsbeschwerde ist somit einzutreten.
3.- a) Nach Art. 7 Abs. 2 ANAG hat der ausländische Ehegatte eines Schweizer Bürgers dann keinen Anspruch auf die Erteilung der ihm nach Abs. 1 dieser Bestimmung grundsätzlich zustehenden Bewilligung, wenn die Ehe eingegangen worden ist, um die Vorschriften über Aufenthalt und Niederlassung von Ausländern zu umgehen. Erfasst wird davon insbesondere die so genannte Scheinehe bzw. Ausländerrechtsehe, bei der die Ehegatten von vornherein keine echte eheliche Gemeinschaft beabsichtigen. Wie die Vorinstanzen zu Recht festgestellt haben, bestehen zahlreiche Indizien, dass der Beschwerdeführer H._ ausschliesslich zur Umgehung der in der Schweiz geltenden fremdenpolizeilichen Vorschriften geheiratet hat. Das Verwaltungsgericht hat aber offen gelassen, ob der Beschwerdeführer eine solche Ehe eingegangen war. Die Frage braucht auch hier nicht geklärt zu werden.
Selbst wenn nämlich die Ehe nicht bloss zum Schein eingegangen wurde, heisst dies nicht zwingend, dass einem Ausländer, der nicht mehr mit seinem schweizerischen Ehegatten zusammenlebt, der Aufenthalt weiterhin gestattet werden muss. Zu prüfen ist diesfalls, ob sich die Berufung auf die Ehe nicht als rechtsmissbräuchlich erweist (<ref-ruling> E. 4a S. 103; <ref-ruling> E. 3d S. 151). Das Verwaltungsgericht geht, ebenso wie schon die Fremdenpolizei sowie das Polizei- und Militärdepartement, von einem solchen Rechtsmissbrauch aus.
b)Rechtsmissbrauch liegt insbesondere dann vor, wenn ein Rechtsinstitut rechtswidrig zur Verwirklichung von Interessen verwendet wird, die es nicht schützen will (<ref-ruling> E. 3b S. 375; <ref-ruling> E. 4 S. 103, je mit Hinweisen).
Rechtsmissbrauch darf allerdings nicht leichthin angenommen werden, namentlich nicht schon deshalb, weil die Ehegatten nicht mehr zusammenleben oder ein Eheschutz- oder Scheidungsverfahren eingeleitet worden ist. Denn gerade darum, weil der ausländische Ehegatte nicht der Willkür des schweizerischen ausgeliefert sein soll, hat der Gesetzgeber darauf verzichtet, die Erteilung der Aufenthaltsbewilligung vom ehelichen Zusammenleben abhängig zu machen (<ref-ruling> E. 2 S. 100 und E. 4a S. 103; ausführlich: BGE <ref-ruling> E. 3 S. 149 ff.). Rechtsmissbrauch ist aber dann gegeben, wenn der ausländische Ehegatte sich auf eine Ehe beruft, die nur noch formell aufrechterhalten wird mit dem einzigen Ziel, die Aufenthalts- oder Niederlassungsbewilligung erhältlich zu machen (<ref-ruling> E. 4a in fine S. 104). Bestehen nicht genügend Anhaltspunkte für eine Scheinehe, geht es allerdings nicht an, einzig aus ihnen zu schliessen, die Berufung auf die bestehende Ehe sei rechtsmissbräuchlich (vgl. <ref-ruling> E. 4 und 5 S. 50 ff.).
Erforderlich sind konkrete Hinweise darauf, dass Ehegatten nicht (mehr) eine eigentliche Lebensgemeinschaft führen, sondern die Vorschriften über Aufenthalt und Niederlassung der Ausländer umgehen wollen (vgl. BGE <ref-ruling> E. 2a und b S. 294. f.). Wie es sich damit verhält, entzieht sich in der Regel einem direkten Beweis und ist oft - wie bei der so genannten Scheinehe oder früher bei der Bürgerrechtsehe (vgl. <ref-ruling> ff.) - nur durch Indizien zu erstellen.
Feststellungen über das Bestehen solcher Indizien können äussere Gegebenheiten, aber auch innere, psychische Vorgänge betreffen (Wille der Ehegatten). Es handelt sich so oder so um tatsächliche Gegebenheiten (<ref-ruling> E. 2a S. 6; vgl. auch <ref-ruling> E. 2c S. 248; <ref-ruling> E. 1 S. 146), und die entsprechenden Feststellungen binden das Bundesgericht, wenn eine richterliche Behörde als Vorinstanz den Sachverhalt nicht offensichtlich unrichtig, unvollständig oder unter Verletzung wesentlicher Verfahrensbestimmungen festgestellt hat (Art. 105 Abs. 2 OG). Frei zu prüfen ist dagegen die Rechtsfrage, ob die festgestellten Tatsachen (Indizien) darauf schliessen lassen, das Festhalten an der Ehe bezwecke die Umgehung fremdenpolizeilicher Vorschriften.
c)Das Bundesgericht hat Rechtsmissbrauch bei einem Ausländer angenommen, welcher sich auf eine lediglich noch formell bestehende Ehe mit einer Schweizerin berief, gleichzeitig aber eine Beziehung zu einer anderen Schweizerin unterhielt, mit der er ein Kind hatte (<ref-ruling> E. 4b S. 104). Ebenfalls erachtete es das Bundesgericht als rechtsmissbräuchlich, eine Aufenthaltsbewilligung in der Schweiz zu verlangen, wenn der schweizerische Ehegatte seinerseits nicht (mehr) hier lebte (nicht veröffentlichte Urteile vom 8. April 1997 i.S. Ertas, vom 26. März 1998 i.S.
Majerova und vom 7. September 1998 i.S. Läuffer). Rechtsmissbrauch kann aber auch gegeben sein, wenn die Dinge nicht derart offensichtlich zu Tage liegen (nicht veröffentlichtes Urteil vom 31. Januar 2000 i.S. Sertdemir, mit Hinweisen auf weitere nicht veröffentlichte Urteile des Bundesgerichts).
4.-a) Gemäss den Feststellungen der Vorinstanzen ging der Beschwerdeführer die Ehe am 23. November 1992 nach einer sehr kurzen Bekanntschaftszeit ein. Er lebte mit seiner Ehefrau nicht lange zusammen. Schon im März 1993 ergab sich für die Fürsorgebehörden, dass die Eheleute keinen gemeinsamen Haushalt führten. Im November 1993 zog die Ehefrau zu ihrem Freund U._. Am 26. April 1994 wurde das Ehepaar gerichtlich getrennt. Ab August 1995 war der Beschwerdeführer bei seiner Freundin P._ angemeldet, während seine Gattin nach wie vor mit U._ zusammenlebte. Am 17. Januar 1996 fand eine Verhandlung vor dem Ehegerichtspräsidenten statt. Da der Rekurrent seine Zustimmung zur einvernehmlichen Scheidung verweigerte, wurde das schriftliche Klageverfahren angeordnet. Am 21. Juni 1996 sagte die Ehefrau gegenüber der Staatsanwaltschaft aus, ihr Gatte habe nach der Einreise in die Schweiz lediglich drei Monate bei ihr gewohnt, bis er eine eigene Wohnung gefunden habe. Die Ehe sei nie gelebt worden. Der Beschwerdeführer habe sich seinerzeit bereits seit zwei bis drei Jahren illegal in der Schweiz aufgehalten und ihr für die Heirat Fr. 30'000.-- versprochen; Fr. 5'000.-- habe sie vor der Ehe, Fr. 18'000.-- nachher in Raten erhalten, Fr. 7'000.-- sei er ihr noch schuldig. Erst nachdem die Fremdenpolizei am 27. November 1996 verfügt hatte, die dem Beschwerdeführer erteilte Aufenthaltsbewilligung werde nicht mehr erneuert, widerrief dessen Ehefrau mit Schreiben vom 17. Dezember 1996 diese - zuvor noch bestätigten - Aussagen. Anlässlich einer weiteren Einvernahme durch die Staatsanwaltschaft im März 1997 gab sie an, die Scheidung der Ehe sei im nächsten Jahr vorgesehen; sie wolle jedoch nicht, dass der Beschwerdeführer seine Aufenthaltsbewilligung verliere. In diesem Zusammenhang äusserte der Beschwerdeführer, er sei gegen eine Scheidung, weil er sonst sein Aufenthaltsrecht verliere. Als die Ehefrau am 20. Juni 1997 zu ihrem im Dezember erklärten Widerruf ihrer Aussage von der Fremdenpolizei befragt wurde, behauptete sie, sie sehe von einer Scheidung ab, da sie zu ihrem Ehemann wieder ein gutes Verhältnis habe. Die fremdenpolizeilichen Erhebungen ergaben indes, dass sie im Zeitpunkt dieser Äusserung bereits ein Zusammenleben mit ihrem neuen Freund B._ geplant hatte. Dieses Vorhaben scheiterte lediglich an ihrer Verhaftung im Juli 1997. Ihr Hab und Gut war zu jenem Zeitpunkt immer noch bei U._ deponiert. Die Zeit zwischen Juli 1997 und Oktober 1998 verbrachte sie in der Strafvollzugsanstalt Hindelbank sowie in der Psychiatrischen Universitätsklinik. Obwohl sie das Militär- und Polizeidepartement am 16. November 1998 informiert hatte, sie lebe seit ihrer Entlassung mit ihrem Ehemann zusammen, stellte sich heraus, dass sie am 1. November 1998 ein eigenes Appartement gemietet hatte, während der Beschwerdeführer weiterhin an seiner alten Anschrift wohnte.
Dem Umstand, dass der Beschwerdeführer seine Ehefrau - laut ihrer Aussage - fast täglich während der Haft besucht hatte, legten die Vorinstanzen kein Gewicht bei. Es sei verständlich und nachvollziehbar, dass der Rekurrent seit Erhalt der angefochtenen Verfügung alles getan und nichts unterlassen habe, um den Vorwurf der Scheinehe sowie des rechtsmissbräuchlichen Festhaltens an der nur noch formell bestehenden Ehe von sich weisen zu können. Dass die Beteuerung des Beschwerdeführers, er wolle mit seiner Ehefrau einen Neubeginn versuchen, nicht ernst zu nehmen sei, gehe auch aus der Tatsache hervor, dass er monatlich Fr. 500.-- von seinem Einkommen in die Türkei überweist, währenddem seine Ehefrau seit Oktober 1998 wieder vollumfänglich vom Fürsorgeamt unterstützt werden muss.
b) Nach dem Gesagten hat der dem Beschwerdeführer zur Last gelegte Rechtsmissbrauch als erwiesen zu gelten und durfte vom Verwaltungsgericht zu Recht bejaht werden.
Bereits im Zeitpunkt des Erlasses der Verfügung der Fremdenpolizei am 27. November 1996 lebten die Eheleute seit rund drei Jahren getrennt, ohne dass Anzeichen für eine Wiederaufnahme der ehelichen Gemeinschaft bestanden. Auch im Zeitpunkt des Entscheides des Verwaltungsgerichts dauerte das Getrenntleben der Eheleute an; Anhaltspunkte für ein Zusammenleben waren damals ebenfalls nicht ersichtlich.
c) Der Beschwerdeführer macht demgegenüber im Wesentlichen geltend, die Haushaltgemeinschaft sei nicht "unabdingbare Voraussetzung, um das Bestehen einer ehelichen Beziehung zu bejahen". Getrennte, aber dennoch gelebte Paarbeziehungen seien heute zwar nicht die Regel, sie seien aber auch nicht überaus aussergewöhnlich. Grund für das Getrenntleben sei das deliktische Verhalten der Ehefrau gewesen, doch habe er sich auch in dieser Zeit "immer intensiv um seine Ehefrau gekümmert. .., insbesondere auch in der Zeit, in der die Ehefrau in Hindelbank eine Haftstrafe verbüsste".
Letzteres schliesst allerdings, wie das Polizei- und Militärdepartement mit einleuchtender Begründung festgehalten hat, die rechtsmissbräuchliche Berufung auf die bestehende Ehe keineswegs aus. Im Übrigen vermag der Einwand schon angesichts der Beteuerungen der Ehefrau über die angeblich bevorstehende Wiederaufnahme der Ehegemeinschaft nicht durchzudringen; hinzu kommen die weiteren konkreten Umstände, welche den Rechtsmissbrauch belegen. Abgesehen von den Besuchen während der Haft der Ehefrau legt der Beschwerdeführer nicht dar, inwiefern er sich "intensiv" um seine Ehefrau gekümmert hatte. Die Feststellung, dass auch nach der Haftentlassung der Ehefrau das Zusammenleben nicht verwirklicht wurde, hat der Beschwerdeführer nicht bestritten. Bei der gegebenen Sachlage durfte das Verwaltungsgericht von den ihm vorliegenden Akten ausgehen und - ohne Verletzung des rechtlichen Gehörs - von weiteren Beweiserhebungen, namentlich von einer Befragung der Eheleute, absehen. Immerhin hatte der Beschwerdeführer selber am 19. Mai 1997 in einer Einvernahme erklärt und mit seiner Unterschrift bestätigt: "Ich bin gegen eine Scheidung, weil ich sonst die Aufenthaltsbewilligung verliere. Schliesslich bin ich schon 5 Jahre in der Schweiz". Damit aber erübrigt sich auch, auf das mit der Beschwerdeschrift eingereichte Schreiben der Ehefrau vom 14. Juni 2000 näher einzugehen.
d) Der Rechtsmissbrauch war schon vor Ablauf der fünf Ehejahre gegeben, weshalb er sowohl der Erteilung der Niederlassungsbewilligung wie der Erneuerung der Aufenthaltsbewilligung entgegensteht (vgl. <ref-ruling> E. 4c S. 105). Angesichts dessen ist zudem schon von vornherein die Berufung des Beschwerdeführers auf eine entsprechende Anwendung von <ref-law> ausgeschlossen, da er sich nicht mindestens fünf Jahre "ordnungsgemäss" in der Schweiz aufgehalten hat.
5.- Das Verwaltungsgericht hat weiter festgehalten, die Berufung des Beschwerdeführers auf sein Rückenleiden und die besseren Behandlungsmöglichkeiten in der Schweiz vermöchten keinen Anspruch auf Verlängerung der Aufenthaltsbewilligung zu begründen; die medizinische Behandlung sei auch in der Türkei gewährleistet und die gegenteilige Behauptung des Beschwerdeführers lasse sich nicht auf das eingereichte Arztzeugnis stützen. Die bloss vagen Einwände des Beschwerdeführers vermögen diese Feststellungen nicht zu entkräften (Art. 105 Abs. 2 OG); sein Hinweis, die Region, in welcher seine Eltern leben, biete keine den Schweizer Verhältnissen vergleichbare Therapiemöglichkeiten, bedeutet insbesondere nicht, dass sein Leiden in der Türkei nicht behandelbar wäre.
6.- Der Beschwerdeführer rügt, das Verwaltungsgericht habe seinen in <ref-law> gewährleisteten Anspruch auf öffentliche Gerichtsverhandlung und Urteilsbegründung verletzt.
Richtig ist, dass der Beschwerdeführer in der Rekursbegründung vom 30. November 1999 seine eigene und die "Parteibefragung der Ehegatten K._ verlangt hat. Hievon durfte das Gericht aber, wie dargelegt, in antizipierter Beweiswürdigung absehen. Eine öffentliche Verhandlung und Urteilsverkündung hat der Beschwerdeführer jedoch, entgegen seinen Behauptungen in der Beschwerdeschrift, nicht verlangt.
Damit aber fehlte ein klarer und unmissverständlicher Antrag auf öffentliche Parteiverhandlung und Urteilsverkündung, wie er analog auch bei Art. 6 Ziff. 1 EMRK erforderlich ist (vgl. <ref-ruling> E. 3a S. 55); das erst vor dem Bundesgericht für die kantonale Verwaltungsgerichtsinstanz gestellte Begehren ist verspätet. Mangels eines entsprechenden Antrages war das Verwaltungsgericht auch gemäss § 25 des Gesetzes des Kantons Basel-Stadt vom 14. Juni 1928 über die Verwaltungsrechtspflege nicht zur Ansetzung einer öffentlichen Verhandlung verpflichtet.
7.- Die Beschwerde erweist sich mithin als unbegründet.
Entsprechend dem Ausgang des Verfahrens hat der Beschwerdeführer, dessen Gesuch um unentgeltliche Rechtspflege abgewiesen wurde, die bundesgerichtlichen Kosten zu tragen (Art. 156 Abs. 1, Art. 153 und Art. 153a OG). Eine Parteientschädigung ist nicht zuzusprechen (Art. 159 Abs. 2 OG).

Demnach erkennt das Bundesgericht:
1.- Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
2.- Die Gerichtsgebühr von Fr. 2'000.-- wird dem Beschwerdeführer auferlegt.
3.- Dieses Urteil wird dem Beschwerdeführer, dem Polizei- und Militärdepartement des Kantons Basel-Stadt, dem Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht sowie dem Bundesamt für Ausländerfragen schriftlich mitgeteilt.
_
Lausanne, 14. September 2000
Im Namen der II. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Das präsidierende Mitglied:
Der Gerichtsschreiber: