unentgeltliche Verbeiständung, hat sich ergeben:
A.- Mit Urteil vom 17. Juli 1997 wurde K._ wegen versuchter vorsätzlicher Tötung und Gefährdung des Lebens zu zweieinhalb Jahren Gefängnis verurteilt. Das Strafgericht Basel-Stadt stellte fest, dass K._ an einer schweren Alkoholsucht sowie an einer Persönlichkeitsstörung mit vorwiegend narzisstischen und impulsiven Zügen leide. Es schob daher den Vollzug der Strafe gemäss Art. 43 Ziff. 2 Abs. 1 und Art. 44 Ziff. 1 StGB auf und wies K._ in eine Trinkerheilanstalt ein. Nachdem K._ unter Anrechnung der Untersuchungshaft bzw. des vorläufigen Strafvollzugs 16 Monate der Strafe verbüsst hatte, trat er am 22. September 1997 in die Psychiatrische Universitätsklinik Basel (PUK) ein. Das stationäre Therapieprogramm umfasste therapeutische Einzel- und Gruppengespräche. Am 1. April 1998 konnte K._ in ein Wohnexternat übertreten und hielt sich nur noch vormittags zur Therapie in der Universitätsklinik auf.
B.-Am 3. April 1998 ersuchte K._, vertreten durch Advokat Guido Ehrler, um die Entlassung aus der Massnahme und stellte für dieses Verfahren ein Gesuch um unentgeltliche Prozessführung. Die Abteilung Straf- und Massnahmenvollzug (SMV) des Polizei- und Militärdepartementes des Kantons Basel-Stadt (im Folgenden: die Vollzugsbehörde), teilte K._ am 8. April 1998 mit, es bestehe keine gesetzliche Grundlage für die Übernahme der Anwaltskosten im nichtstreitigen Verwaltungsverfahren; zudem handle es sich um ein Gesuch, das ohne weiteres auch von einem juristischen Laien eingereicht werden könne. Die Vollzugsbehörde holte bei der Psychiatrischen Universitätsklinik einen Bericht ein. Die Universitätsklinik kam am 21. April 1998 zum Ergebnis, eine bedingte Entlassung könne aus forensisch-psychiatrischer Sicht noch nicht befürwortet werden. Daraufhin teilte die Vollzugsbehörde Advokat Guido Ehrler am 8. Mai 1998 mit, sie erachte es nicht als sinnvoll, die Angelegenheit der Strafvollzugskommission zu unterbreiten. Es werde beabsichtigt, sich im Oktober 1998 erneut bei der Psychiatrischen Universitätsklinik über den Verlauf der Massnahme zu erkundigen und erst dann, je nach Bericht, die Angelegenheit der Strafvollzugskommission vorzulegen. Mit Schreiben vom 19. Juni 1998 erklärte sich Advokat Guido Ehrler mit diesem Vorgehen einverstanden. Er erneuerte indessen am 3. November 1998 sein Gesuch um unentgeltliche Prozessführung. Mit Schreiben vom 30. November 1998 teilte ihm die Vollzugsbehörde mit, seinem Gesuch werde nicht entsprochen.
C.-Am 2. Dezember 1998 beantragte die Vollzugsbehörde der Strafvollzugskommission, gestützt auf einen neuen Bericht der Psychiatrischen Universitätsklinik vom 16. November 1998, die bedingte Entlassung von K._ aus dem Massnahmenvollzug. Am 6. Januar 1999 liess sich K._ durch seinen Rechtsvertreter vernehmen und verlangte seine definitive, eventualiter seine bedingte Entlassung. Am 3. Februar 1999 bewilligte die Strafvollzugskommission K._ per Entscheiddatum die bedingte Entlassung aus dem Massnahmenvollzug. Es wurde eine Probezeit von 2 Jahren angeordnet und für die Dauer von einem Jahr eine Schutzaufsicht errichtet. K._ wurde angewiesen, sich auf eigene Kosten weiterhin einer ambulanten psychiatrischen Behandlung zu unterziehen, solange der behandelnde Arzt dies als notwendig erachte, längstens jedoch bis zum Ablauf der Probezeit.
D.-Mit Eingabe vom 17. Februar 1999 an das Polizei- und Militärdepartement rügte der Rechtsvertreter K._s, die Strafvollzugskommission habe sich nicht zu seinem Gesuch um unentgeltliche Prozessführung geäussert. Er legte eine Honorarnote bei, in der er einen Zeitaufwand von 6 Stunden 45 Minuten im Zeitraum vom 24. Februar 1998 bis zum 17. Februar 1999 geltend machte. Die Strafvollzugskommission wies das Gesuch am 5. März 1999 ab.
E.-Hiergegen erhob K._ Rekurs an den Regierungsrat mit dem Antrag, es sei ihm für das am 3. Februar 1999 abgeschlossene Entlassungsverfahren die unentgeltliche Rechtspflege mit Advokat Guido Ehrler als Rechtsbeistand zu gewähren; zudem ersuchte er um unentgeltliche Prozessführung und Verbeiständung im Rekursverfahren. Der Regierungsrat überwies den Rekurs dem Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht zum Entscheid. Dieses wies den Rekurs am 26. Mai 1999 ab und lehnte implizit auch den Anspruch auf unentgeltliche Verbeiständung im Rekursverfahren ab.
F.- Gegen den Entscheid des Appellationsgerichts, der ihm am 20. September 1999 eröffnet worden war, erhob K._ am 20. Oktober 1999 staatsrechtliche Beschwerde ans Bundesgericht. Er beantragt, das angefochtene Urteil sei aufzuheben und die Angelegenheit sei an die Vorinstanz zur Neubeurteilung der Kostenfrage zurückzuweisen. Ferner sei ihm für das staatsrechtliche Verfahren die unentgeltliche Prozessführung mit Advokat Guido Ehrler als Rechtsbeistand zu gewähren.
G.-Das Appellationsgericht und die Justizvollzugskommission beantragen die Abweisung der staatsrechtlichen Beschwerde.

Das Bundesgericht zieht in Erwägung:
1.- a) Das angefochtene verwaltungsgerichtliche Urteil ist ein kantonal letztinstanzlicher Entscheid, gegen den die staatsrechtliche Beschwerde wegen Verletzung verfassungsmässiger Rechte grundsätzlich offensteht (Art. 84 Abs. 1 lit. a und Art. 86 Abs. 1 OG). Der Beschwerdeführer wendet sich ausschliesslich gegen die Versagung der unentgeltlichen Verbeiständung und nicht gegen den Hauptsacheentscheid (bedingte Entlassung aus dem Massnahmevollzug). Diese Rüge kann mit keinem anderen bundesrechtlichen Rechtsmittel geltend gemacht werden (Art. 84 Abs. 2 OG, vgl. <ref-ruling> E. 2e S. 278 mit Hinweis).
b) Der Beschwerdeführer macht mit der staatsrechtlichen Beschwerde einen Anspruch auf unentgeltliche Verbeiständung nicht nur vor dem Appellationsgericht, sondern auch im Administrativverfahren geltend, und zwar für den Zeitraum vom 24. Februar 1998 bis zum 17. Februar 1999. Seine Beschwerde betrifft somit nicht nur das von der Vollzugsbehörde im Dezember 1998 von Amtes wegen eingeleitete Verfahren, das zu seiner Entlassung führte (vgl. oben, Abschnitt C; im Folgenden: 2. Verfahrensabschnitt), sondern auch das vorangegangene, auf seinen Antrag eingeleitete Prüfungsverfahren (vgl. oben, Abschnitt B, im Folgenden: 1. Verfahrensabschnitt). Fraglich ist, ob auf die Beschwerde insoweit eingetreten werden kann. Dies wäre zu verneinen, wenn über den Anspruch auf unentgeltliche Verbeiständung im 1. Verfahrensabschnitt bereits rechtskräftig durch die Verfügungen der Vollzugsbehörde vom April und vom November 1998 entschieden worden wäre, gegen die der Beschwerdeführer nicht rekurriert hat.
Das Appellationsgericht verneinte dies mit der Begründung, beide Schreiben der Vollzugsbehörde hätten keine Rechtsmittelbelehrung enthalten; zudem sei die Justizvollzugskommission in ihrem Entscheid vom 5. März 1999 auf die Frage zurückgekommen. Das Appellationsgericht trat daher vollumfänglich auf den Rekurs ein und prüfte den Anspruch auf unentgeltliche Verbeiständung für beide Verfahrensabschnitte.
Liegt somit ein materieller Entscheid des Appellationsgerichts zu beiden Verfahrensabschnitten vor, kann der Beschwerdeführer auch im vorliegenden Verfahren für beide Verfahrensabschnitte noch geltend machen, die Versagung der unentgeltlichen Verbeiständung verstosse gegen Verfassungsrecht.
c)Auf die rechtzeitig erhobene Beschwerde (Art. 89 OG) des legitimierten Beschwerdeführers (Art. 88 OG) ist daher einzutreten.
2.-a) Der Anspruch auf unentgeltliche Rechtspflege wurde bisher als Minimalgarantie aus Art. 4 aBV abgeleitet: Danach hat die bedürftige Partei in einem für sie nicht aussichtslosen Verfahren den Anspruch auf unentgeltliche Rechtspflege, der auch die Vertretung durch einen unentgeltlichen Rechtsbeistand umfasst, sofern ein solcher zur gehörigen Interessenwahrung erforderlich ist (<ref-ruling> E. 2a S. 306). Dieser Anspruch ist nunmehr in <ref-law> ausdrücklich gewährleistet worden. Im vorliegenden Fall rügt der Beschwerdeführer ausschliesslich die Verletzung dieses verfassungsrechtlichen Minimalanspruchs und macht nicht geltend, das kantonale Recht gewähre einen darüber hinausgehenden Anspruch.
b) Nach der bundesgerichtlichen Rechtsprechung hat die bedürftige Partei Anspruch auf unentgeltliche Verbeiständung, wenn ihre Interessen in schwerwiegender Weise betroffen sind und der Fall in tatsächlicher und rechtlicher Hinsicht Schwierigkeiten bietet, die den Beizug eines Rechtsvertreters erforderlich machen (<ref-ruling> E. 2c/bb S. 51 f., 275 E. 3a S. 276; <ref-ruling> E. 2a S. 44 f. mit Hinweisen). Falls das in Frage stehende Verfahren besonders stark in die Rechtsposition des Betroffenen eingreift, ist die Bestellung eines unentgeltlichen Rechtsvertreters grundsätzlich geboten. Dies trifft insbesondere im Strafprozess zu, wenn dem Angeschuldigten eine schwerwiegende freiheitsentziehende Massnahme oder eine Strafe droht, deren Dauer die Gewährung des bedingten Strafvollzuges ausschliesst. In <ref-ruling> E. 5b/bb S. 282 hat das Bundesgericht offen gelassen, ob in einem Verfahren betreffend Rückversetzung in den Massnahmenvollzug nach bedingter oder probeweiser Entlassung gemäss <ref-law> für den Betroffenen derart viel auf dem Spiel stand, dass die Notwendigkeit einer anwaltlichen Verbeiständung von vornherein zu bejahen gewesen wäre. Droht zwar eine erhebliche, nicht aber eine besonders schwere Freiheitsbeschränkung, müssen zur relativen Schwere des Eingriffs besondere tatsächliche oder rechtliche Schwierigkeiten hinzukommen, denen der Betroffene - auf sich allein gestellt - nicht gewachsen wäre. Als besondere Schwierigkeiten, die eine Verbeiständung rechtfertigen können, fallen auch Gründe in der Person des Gesuchstellers in Betracht, insbesondere dessen Fähigkeit, sich im Verfahren zurechtzufinden (<ref-ruling> E. 2c/bb S. 51/52, 275 E. 3a S. 276; je mit Hinweisen). Bei offensichtlichen Bagatelldelikten, bei denen nur eine Busse oder eine geringfügige Freiheitsstrafe in Frage kommt, verneint das Bundesgericht einen unmittelbaren verfassungsmässigen Anspruch auf unentgeltliche Rechtsprechung (<ref-ruling> E. 2c/bb S. 51; <ref-ruling> E. 2a S. 45 mit Hinweisen).
3.-a) Die allgemeinen Voraussetzungen der unentgeltlichen Rechtspflege liegen unstreitig vor: Der Beschwerdeführer ist bedürftig und sein Antrag auf Entlassung aus dem Massnahmenvollzug war nicht von vornherein aussichtslos: Immerhin war dem Beschwerdeführer bereits gestattet worden, eine eigene Wohnung in Basel zu beziehen; zudem waren sämtliche Alkoholtests, denen er sich unterziehen musste, negativ ausgefallen.
b) Der beantragte Entscheid (Entlassung aus dem Massnahmevollzug) war für den Beschwerdeführer von einiger Tragweite: Bei einer Verweigerung der (bedingten) Entlassung drohte ihm eine Fortsetzung der stationären Behandlung in der Psychiatrischen Universitätsklinik von mindestens mehreren Monaten. Die Behandlung wegen Trunksucht hätte gemäss <ref-law> längstens bis zum September 1999 fortgeführt werden können (d.h. noch knapp eineinhalb Jahre lang). Dagegen hätte die Behandlung der Persönlichkeitsstörung des Beschwerdeführers, die sich auf <ref-law> stützte, möglicherweise noch über diesen Zeitpunkt hinaus fortdauern können: Im Unterschied zur bedingten Entlassung aus dem Strafvollzug, bei deren Verweigerung der Gesuchsteller höchstens die ganze Freiheitsstrafe zu verbüssen hat, werden Massnahmen gemäss <ref-law> auf unbestimmte Zeit angeordnet und enden erst, wenn der Betroffene als geheilt entlassen oder die Behandlung als erfolglos eingestellt wird. Ihre Dauer hängt somit vom Entscheid der zuständigen Behörde über die bedingte oder definitive Entlassung ab, dem deshalb grosse Bedeutung zukommt.
Im vorliegenden Fall wird allerdings die Tragweite des Entlassungsentscheids durch den Umstand eingeschränkt, dass der Beschwerdeführer seit April 1998 nicht mehr in der Psychiatrischen Universitätsklinik untergebracht war, sondern eine eigene Wohnung hatte, in der er einen grossen Teil des Tages und die Nacht frei verbringen durfte; nur am Vormittag war er verpflichtet, sich in der Psychiatrischen Universitätsklinik aufzuhalten und einer Therapie zu unterziehen (vgl. Bericht der PUK vom 21. April 1998 S. 2). Damit näherte sich die stationäre Behandlung bereits einer ambulanten Behandlung an und war nicht mehr mit der gleichen Einschränkung der persönlichen Freiheit verbunden wie zu Beginn der Massnahme. Für den Beschwerdeführer stand deshalb nicht derart viel auf dem Spiel, dass die Notwendigkeit einer anwaltlichen Verbeiständung von vornherein zu bejahen gewesen wäre. Andererseits aber handelte es sich auch nicht um eine blosse Bagatelle, bei der ein verfassungsmässiger Anspruch auf unentgeltliche Verbeiständung ausgeschlossen gewesen wäre.
c) Damit ist zu prüfen, ob besondere Schwierigkeiten im vorliegenden Fall den Beistand eines Anwalts erforderten.
aa) Dies hat das Appellationsgericht verneint: Gemäss Art. 45 Ziff. 1 Abs. 1 prüfe die zuständige Behörde von Amtes wegen, ob und wann die bedingte oder probeweise Entlassung anzuordnen sei; sie müsse in allen Fällen den zu Entlassenden oder dessen Vertreter anhören und von der Anstaltsleitung einen Bericht einholen. Die Behörde sei an den Untersuchungsgrundsatz gebunden, weshalb die sachlichen Voraussetzungen der Bewilligung der unentgeltlichen Verbeiständung streng zu beurteilen seien. Im vorliegenden Fall hätte es genügt, wenn der Rekurrent ein Gesuch um bedingte Entlassung gestellt hätte, woraufhin die weiteren Schritte von Amtes wegen eingeleitet worden wären. Hierzu sei er ohne weiteres selbst in der Lage gewesen, zumal er dasselbe Verfahren bereits einmal im Jahre 1990 durchlaufen habe. Der Beizug eines Anwaltes wäre allenfalls erforderlich gewesen, wenn die Justizvollzugskommission das Gesuch der Vollzugsbehörde vom 2. Dezember 1998 auf bedingte Entlassung abgewiesen hätte. Den Entscheid der Vollzugsbehörde vom Mai 1998 habe der Beschwerdeführer akzeptiert.
bb) Die Geltung der Offizialmaxime schliesst die unentgeltliche Verbeiständung nicht aus (<ref-ruling> E. 4a S. 34 f. mit Überblick über die Rechtsprechung); entscheidend ist vielmehr deren sachliche Gebotenheit im konkreten Fall, unter Berücksichtigung der Umstände des Einzelfalls, der Eigenheiten der anwendbaren Verfahrensvorschriften und der Besonderheiten des jeweiligen Verfahrens (BGE 125 V E. 4b S. 35 mit Hinweisen). Im vorliegenden Fall musste die zuständige Behörde beurteilen, ob der Beschwerdeführer von seiner Alkoholsucht geheilt und seine Persönlichkeitsstörung überwunden hatte oder seine Heilung zumindest soweit fortgeschritten war, dass er aus der stationären Behandlung entlassen werden konnte. Diese tatsächlichen Fragen sind nicht leicht zu beurteilen und erfordern in aller Regel den Beizug medizinischer Sachverständiger. Im vorliegenden Fall stützten sich Vollzugsbehörde und Justizvollzugskommission denn auch auf die Berichte der Abteilung Forensische Psychiatrie der Psychiatrischen Universitätsklinik Basel. Für den Beschwerdeführer als medizinischen Laien war es schwer, derartige Gutachten objektiv zu würdigen. Das gilt umso mehr, als es um seinen eigenen Geistes- und Gesundheitszustand ging und er das Vertrauen zu den behandelnden Ärzten verloren hatte. Hinzu kommt, dass der Beschwerdeführer im Zeitpunkt der Stellung des Verbeiständungsgesuchs noch an Persönlichkeitsstörungen litt, die seine Beziehungs- und Kommunikationsfähigkeit sowie seine Selbstkontrolle beeinträchtigten (vgl. Bericht der PUK vom 21. April 1998 S. 2). In dieser Situation war er auf den Beistand eines Vertreters schon im Administrativverfahren angewiesen. Möglicherweise hätte auch der Beistand eines Arztes oder einer anderen Vertrauensperson genügt; mangels einer derartigen Vertrauensperson durfte der Beschwerdeführer aber auch anwaltliche Hilfe in Anspruch nehmen.
d) Nach dem Gesagten hatte der Beschwerdeführer im April 1998 Anspruch auf unentgeltliche Verbeiständung in dem von ihm eingeleiteten Verfahren auf Entlassung aus dem Massnahmevollzug (1. Verfahrensabschnitt). Fraglich ist allerdings, ob dies auch für den zweiten, von der Vollzugsbehörde von Amtes wegen eingeleiteten Verfahrensabschnitt zutrifft.
Es liesse sich die Auffassung vertreten, mit dem Vorliegen des positiven Berichts der Psychiatrischen Universitätsklinik vom 16. November 1998 und dem Entlassungsantrag der Vollzugsbehörde vom 2. Dezember 1998 sei der Sachverhalt klar gewesen und habe der Beschwerdeführer keines Beistands mehr bedurft.
Für die Beurteilung eines Gesuchs um unentgeltliche Verbeiständung ist jedoch grundsätzlich auf den Zeitpunkt abzustellen, in dem das Gesuch gestellt wird (<ref-ruling> E. 2c S. 307; <ref-ruling> E. 4 S. 6 f.). Dies geschah für den zweiten Verfahrensabschnitt spätestens am 3. November 1998, als der Rechtsvertreter des Beschwerdeführers das Gesuch um unentgeltliche Rechtspflege für das "hängige Entlassungsverfahren" erneuerte. Nachdem die Vollzugsbehörde dem Beschwerdeführer angekündigt hatte, sie werde im Oktober 1998 ein neues Gutachten der Psychiatrischen Universitätsklinik zur Entlassungsfrage einholen, konnte sich dieses Schreiben bei vernünftiger Auslegung nicht nur auf die Vergangenheit beziehen, sondern enthielt gleichzeitig ein Gesuch um unentgeltliche Verbeiständung auch für den 2. Verfahrensabschnitt. Anfang November 1998 aber lag der neue Bericht der Psychiatrischen Universitätsklinik noch nicht vor und stand auch der Antrag der Vollzugsbehörde noch nicht fest.
Angesichts der Besonderheiten des vorliegenden Falles (einverständliche Sistierung des Entlassungsgesuchs des Beschwerdeführers bis Oktober 1998) lässt sich auch nicht sagen, der Beschwerdeführer habe sein Gesuch um unentgeltliche Verbeiständung vorzeitig, vor Einleitung des Entlassungsprüfverfahrens durch die Vollzugsbehörde gestellt, und damit den für die Beurteilung des Gesuchs massgeblichen Zeitpunkt in unzulässiger Weise vorverlegt.
e) Stand dem Beschwerdeführer somit ein Anspruch auf unentgeltliche Verbeiständung in beiden Abschnitten des Verwaltungsverfahrens gestützt auf Verfassungsrecht zu, kann offen bleiben, ob sich dieser Anspruch, wie der Beschwerdeführer meint, auch aus Art. 6 Ziff. 3 EMRK begründen liesse.
4.-Nach dem Gesagten ist die Beschwerde gutzuheissen und das angefochtene Urteil ist aufzuheben. Da das Appellationsgericht in seinem neuen Entscheid den Rekurs des Beschwerdeführers gutheissen und diesem eine Parteientschädigung zusprechen muss, erübrigt es sich, den Anspruch auf unentgeltliche Verbeiständung im Verfahren vor dem Appellationsgericht zu prüfen. Gleiches gilt für das Gesuch auf unentgeltliche Rechtspflege im bundesgerichtlichen Verfahren, in dem keine Kosten erhoben werden (Art. 156 Abs. 2 OG) und der Beschwerdeführer Anspruch auf eine Parteientschädigung hat (Art. 159 OG).

Demnach erkennt das Bundesgericht:
1.- Die staatsrechtliche Beschwerde wird gutgeheissen und das Urteil des Appellationsgerichts des Kantons Basel- Stadt als Verwaltungsgericht vom 26. Mai 1999 aufgehoben.
2.- Es werden keine Kosten erhoben.
3.- Der Kanton Basel-Stadt hat den Beschwerdeführer mit Fr. 2'000. -- für das bundesgerichtliche Verfahren zu entschädigen.
4.-Dieses Urteil wird dem Beschwerdeführer, der Strafvollzugskommission und dem Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht schriftlich mitgeteilt.
_
Lausanne, 19. Januar 2000
Im Namen der I. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident:
Die Gerichtsschreiberin: