Sachverhalt:
A.
A.a. Der 1958 geborene A._ schloss im April 1977 seine Lehre als Mauer ab. Zuletzt arbeitete er vom 12. Juli 1982 bis 18. August 1992 als Maurer-Vorarbeiter für die B._ AG. Im Dezember 1994 meldete er sich bei der Invalidenversicherung zum Leistungsbezug an. Die IV-Stelle Basel-Stadt sprach ihm mit Wirkung ab 1. September 1995 aufgrund eines ermittelten Invaliditätsgrades von 100 % eine ganze Invalidenrente zu (Verfügung vom 20. Oktober 1995). In den folgenden Jahren bestätigte die IV-Stelle den Anspruch wiederholt revisionsweise (Mitteilungen vom 18. Januar 1999, 8. September 2000 und 27. Februar 2006).
A.b. Im Rahmen eines im September 2009 eingeleiteten weiteren Revisionsverfahrens holte die IV-Stelle beim Spital C._ einen Bericht ein (erstattet am 28. Oktober 2009, ergänzt mit Stellungnahme vom 4. Dezember 2009). Mit Wirkung auf 1. April 2010 setzte die IV-Stelle die ganze Rente auf eine halbe herab (Vorbescheid vom 6. Januar 2010; Verfügung vom 26. Februar 2010). Auf Anregung des Prof. Dr. med. D._, Chefarzt am Spital C._, veranlasste die IV-Stelle eine psychiatrische Begutachtung des Versicherten durch Dr. med. E._, Psychiatrie und Psychotherapie FMH, (Gutachten vom 16. September 2010). Gleichzeitig hob sie die Verfügung vom 26. Februar 2010 wiedererwägungsweise auf und bestätigte den weiteren Anspruch auf eine ganze Rente (Verfügung vom 1. September 2010).
A.c. Nach Eingang des psychiatrischen Gutachtens des Dr. med. E._ vom 16. September 2010, in welchem aus psychiatrischer Sicht eine Einschränkung der Arbeitsfähigkeit um 20 % attestiert wurde, und erneuter Durchführung des Vorbescheidverfahrens verfügte die Verwaltung die Herabsetzung auf eine halbe Rente (Verfügung vom 14. April 2011). Die von A._ dagegen erhobene Beschwerde hiess das Sozialversicherungsgericht Basel-Stadt mit Entscheid vom 31. August 2011 gut; es wies die Sache zur Durchführung von beruflichen Massnahmen nach einem sechsmonatigen Besuch des Drogenersatzprogramms F._ an die Verwaltung zurück. Nach Eingang des Verlaufsberichts der Universitären Psychiatrischen Kliniken, Sozialdienst F._, vom 25. Januar 2012 bejahte die IV-Stelle den Anspruch auf "Berufsberatung und Abklärung der beruflichen Eingliederungsmöglichkeiten" (Mitteilung vom 8. Februar 2012). Auf die Information von A._, er sei ab 2. April 2012 hospitalisiert (vgl. Bericht des Spital C._, Neurologisch-Neurochirurgische Poliklinik, vom 26. Oktober 2012), verfügte die IV-Stelle den vorläufigen Abschluss der Massnahme (Vorbescheid vom 25. April 2012 und Verfügung vom 12. Juni 2012).
A.d. Im November 2012 leitete die IV-Stelle ein weiteres Rentenrevisionsverfahren ein. Sie liess den Versicherten durch das Ärztliche Begutachtungsinstitut (ABI) GmbH, Basel, polydisziplinär begutachten (Gutachten vom 19. August 2013). Des Weitern verfügte sie am 16. April 2013 den Abschluss der beruflichen Massnahmen mit der Begründung, es seien weitere medizinische Untersuchungen durchzuführen und es komme deshalb vorläufig zu einem Unterbruch der Gespräche mit der Berufsberatung. Vorbescheidsweise stellte sie A._ die Aufhebung der (ganzen) Rente bei einem ermittelten Invaliditätsgrad von 32 % in Aussicht, wogegen der Versicherte Einwände erhob. Am 17. Oktober 2014 verfügte die Verwaltung im angekündigten Sinne.
B.
Die von A._ mit dem Antrag auf Aufhebung der Verfügung erhobene Beschwerde hiess das Sozialversicherungsgericht des Kantons Basel-Stadt mit Entscheid vom 20. Mai 2015 gut. Es hob die Verfügung vom 17. Oktober 2014 auf und verpflichtete die IV-Stelle, dem Versicherten ab 1. Dezember 2014 eine Dreiviertelsrente auszurichten.
C.
Die IV-Stelle Basel-Stadt führt Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem Rechtsbegehren, der kantonale Entscheid sei aufzuheben. Die Sache sei zu weiteren Abklärungen an sie, eventualiter an die Vorinstanz, zurückzuweisen.
A._ lässt die Abweisung der Beschwerde, soweit auf sie einzutreten sei, beantragen. Das Bundesamt für Sozialversicherungen verzichtet auf eine Vernehmlassung.

Erwägungen:
1.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten kann u.a. die Verletzung von Bundesrecht gerügt werden (<ref-law>), die Feststellung des Sachverhalts nur, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann deren Sachverhaltsfeststellung von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 beruht (<ref-law>).
2.
2.1. Im angefochtenen Entscheid werden die massgebenden Rechtsgrundlagen zutreffend wiedergegeben. Es betrifft dies insbesondere die Bestimmung und die Grundsätze zur Rentenrevision bei erheblicher Änderung des Invaliditätsgrades (<ref-law>), zum revisionsrechtlich massgebenden Vergleichszeitraum (<ref-ruling> E. 5.4 S. 114) sowie zum Beweiswert von Arztberichten (<ref-ruling> E. 3a S. 352; vgl. auch <ref-ruling> E. 5.1 S. 232). Darauf wird verwiesen.
2.2. Bei den gerichtlichen Feststellungen zum Gesundheitszustand und zur Arbeitsfähigkeit handelt es sich grundsätzlich um Fragen tatsächlicher Natur, die einer letztinstanzlichen Berichtigung oder Ergänzung nur im gesetzlichen Rahmen von <ref-law> zugänglich sind (<ref-ruling> E. 3.2 S. 397 ff.). Gleiches gilt in Bezug auf die Frage, ob sich eine Arbeits (un) fähigkeit in einem bestimmten Zeitraum in einem rentenrevisionsrechtlich relevanten Sinne verändert hat (Urteil 8C_105/2013 vom 24. Mai 2013 E. 2.2). Demgegenüber sind die unvollständige Feststellung rechtserheblicher Tatsachen sowie die Missachtung des Untersuchungsgrundsatzes (Art. 43 Abs. 1, <ref-law>) Rechtsfragen (SVR 2014 IV Nr. 20 S. 72, 9C_460/2013 E. 1.3).
3.
3.1. Im Rahmen der hier streitigen revisionsweisen Überprüfung des Rentenanspruchs im Sinne von <ref-law> steht fest und ist unbestritten, dass als zeitlicher Referenzpunkt im Sinne von <ref-ruling> die Verfügung vom 20. Oktober 1995 gilt. Damals wurden beim Versicherten eine HIV-Infektion Stadium C2 in Verbindung mit Drogenabusus (Methadon-Programm), ein Status nach Hepatitis A und B, ein Status nach rezidivierender Pankreatitis bei Aethylabusus sowie eine schwere HIV-assoziierte Thrombozytopenie festgestellt; es wurde ihm eine volle Arbeitsunfähigkeit attestiert (Berichte des Spitals G._, Medizinische Universitäts-Poliklinik, vom 16. Januar und 31. Juli 1995).
3.2. Die Vorinstanz hielt in für das Bundesgericht verbindlicher Weise (vgl. E. 2.2) fest, dass sich der Gesundheitszustand des Beschwerdegegners nach den medizinischen Unterlagen seit der Rentenzusprache im Oktober 1995 verbessert hat, weil seine HIV-Infektion aufgrund der deutlich optimierten Therapiemöglichkeiten in eine chronisch stabile Infektion überführt werden konnte. Daran vermag die gegenteilige Einschätzung des Beschwerdegegners, wonach sich seine gesundheitlichen Verhältnisse eher verschlechtert hätten, nichts zu ändern, bringt er doch nichts vor, was die vorinstanzliche Feststellung als offensichtlich unrichtig erscheinen liesse. Insbesondere genügt hierfür sein Einwand nicht, wonach eine Stabilisierung der Infektion einzig bedeute, dass diese nicht mehr voranschreite, was aber "rein logisch" keine Verbesserung sei. Auch die Teilnahme des Versicherten am Drogenersatzprogramm F._ seit Juli 2011 lassen auf verbesserte gesundheitliche Verhältnisse schliessen.
3.3. Nach Würdigung der medizinischen Akten gelangte die Vorinstanz zum Ergebnis, das ABI-Gutachten vom 19. August 2013 sei nicht beweiskräftig, weil die darin bescheinigte Arbeitsfähigkeit von 80 % nicht schlüssig sei und den im Gutachten festgehaltenen Befunden widerspreche. Der psychiatrische Teilgutachter habe ausser Acht gelassen, dass die Teilnahme am Drogenersatzprogramm F._ zeitintensiv sei und sich eine 80%ige Erwerbstätigkeit bereits aus diesem Grund nicht realisieren lasse. Zudem brächten auch die aufgrund der HIV-Erkrankung erforderlichen medizinischen Kontrollen einen gewissen Zeitaufwand mit sich. Der internistische Teilgutachter habe eingeräumt, dass die HIV-Medikation zu einer (leichten) Verminderung der Leistungsfähigkeit mit vermehrter Müdigkeit führen könne. Des Weitern stehe fest, dass der Versicherte immer wieder an Lungenentzündungen leide. Selbst wenn sich die im Teilgutachten festgehaltene 20%ige Beeinträchtigung aus internistischer Sicht vertreten lasse, sei jedenfalls die Gesamtbeurteilung nicht schlüssig. Es könne nicht nachvollzogen werden, weshalb die im neurologischem Teilgutachten festgestellten Befunde keinerlei Auswirkungen auf die Arbeitsfähigkeit haben sollten. Bei dieser Sachlage sei auf die weiterhin zutreffende Beurteilung des RAD vom 3. November 2010, welche sich auch an den Bericht des Spital C._ vom 12. Juli 2010 halte, abzustellen und von einer Restarbeitsfähigkeit von 50 % auszugehen.
3.4. Der Auffassung der Vorinstanz, wonach das ABI-Gutachten vom 19. August 2013 nicht schlüssig und damit nicht beweiskräftig sei, opponiert die IV-Stelle in ihrer Beschwerde nicht. Vielmehr hält auch sie das Gutachten im letztinstanzlichen Verfahren für widersprüchlich.
Die am ABI-Gutachten geäusserte Kritik scheint gerechtfertigt: Nicht zu überzeugen vermag insbesondere, weshalb der psychiatrische ABI-Gutachter sich zwar hinsichtlich der Arbeitsfähigkeit der Einschätzung des Dr. med. E._ vom 16. September 2010 anschloss, die weiteren Vorgaben des Dr. med. E._ - langsamer Wiedereinstieg ins Berufsleben, berufliche Massnahmen zur Unterstützung des Versicherten, spezielle Anforderungen erfüllender Arbeitsplatz - aber ohne weitere Begründung bzw. betreffend berufliche Massnahmen mit dem alleinigen Hinweis auf die "deutlich ausgeprägte Krankheits- und Behinderungsüberzeugung" als unnötig verwarf. Dies vermag umso weniger einzuleuchten, als die von Dr. med. E._ bereits im Jahr 2010 angesprochenen Schwierigkeiten bei der beruflichen Wiedereingliederung aufgrund der zwischenzeitlich im Zeitpunkt der ABI-Begutachtung (vom 5. Juni 2013) nochmals fast drei Jahre längeren und nun mehr als zwanzig Jahre betragenden Arbeitsabstinenz eher zugenommen haben dürften, wie deutlich auch dem ärztlichen Bericht des F._ Behandlungszentrum zu entnehmen ist (Verlaufsbericht vom 25. Januar 2012). Des Weitern ist schwer nachvollziehbar, dass die neu erhobenen neurologischen Befunde (vgl. insbesondere Berichte der Neurologisch-Neurochirurgischen Poliklinik des Spital C._ vom 26. Oktober 2012 und vom 28. März 2013) die Arbeitsfähigkeit des Versicherten in keiner Weise beeinträchtigen sollen.
3.5. Entgegen dem angefochtenen Entscheid geht es nun aber nicht an, wegen der fehlenden Verwertbarkeit des ABI-Gutachtens vom 19. August 2013 auf die Aktenbeurteilung des RAD vom 3. November 2010 abzustellen. Denn die Beurteilung des RAD-Arztes lag im Zeitpunkt des Verfügungserlasses (17. Oktober 2014) bereits fast vier Jahre zurück und datiert insbesondere noch vor dem Einbezug des Versicherten ins Drogenersatzprogramm F._ im Juli 2011 (vgl. Bericht der Universitären Psychiatrischen Kliniken, Sozialdienst F._, vom 25. Januar 2012).
3.6. Nach dem Gesagten bilden die medizinischen Akten keine genügende Grundlage für die Feststellung der Arbeits (un) fähigkeit des Versicherten. Praxisgemäss ist die Sache deshalb an die Vorinstanz zurückzuweisen. Diese hat zum Gesundheitszustand und zur Arbeitsfähigkeit des Beschwerdegegners eine umfassende, polydisziplinäre medizinische Expertise einzuholen (vgl. <ref-law>).
3.7. Für den Fall, dass sich aus dem einzuholenden Gutachten eine wiedergewonnene Arbeitsfähigkeit ergeben sollte, werden vor einer allfälligen Herabsetzung der Rente - angesichts der Tatsache, dass der Versicherte seit mehr als zwanzig Jahren eine Rente bezieht -befähigende berufliche Massnahmen zu prüfen sein (vgl. statt vieler: SVR 2011 IV Nr. 73 S. 220, 9C_228/2010 E. 3.3). Denn die erwerbliche Verwertbarkeit eines allfälligen medizinisch ausgewiesenen Zugewinns an funktionellem Leistungsvermögen dürfte im Falle des Beschwerdegegners von der Durchführung entsprechender Massnahmen abhängen (vgl. dazu SVR 2011 IV Nr. 30 S. 86, 9C_163/2009 E. 4.2.1 und 4.2.2), wie sie im Übrigen bereits Dr. med. E._ in seinem Gutachten vom 16. September 2010 für angezeigt hielt. Davon ging wohl auch die IV-Stelle aus, als sie am 8. Februar 2012 einen Anspruch des Versicherten auf Berufsberatung und Abklärung der beruflichen Eingliederungsmöglichkeiten bejahte, wobei sie am 16. April 2013 den Abschluss der Massnahme verfügte (vorläufig bereits am 12. Juni 2012) mit dem Hinweis, es komme wegen weiterer medizinischer Abklärungen "vorläufig zu einem Unterbruch der Gespräche mit der Berufsberatung". Einem allfälligen Widerstand des Beschwerdegegners wird mit dem Mahn- und Bedenkzeitverfahren nach <ref-law> zu begegnen sein (vgl. Urteil 9C_668/2015 vom 17. Februar 2016 E. 4.4).
4.
Bei diesem Ausgang des Verfahrens hat der Beschwerdegegner grundsätzlich die Gerichtskosten zu tragen (<ref-law>). Seinem Gesuch um unentgeltliche Rechtspflege kann jedoch entsprochen werden (<ref-law>; <ref-ruling> E. 4a S. 202). Es wird indessen ausdrücklich auf <ref-law> hingewiesen, wonach die begünstigte Partei der Gerichtskasse Ersatz zu leisten hat, wenn sie später dazu in der Lage ist.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen und der Entscheid des Sozialversicherungsgerichts des Kantons Basel-Stadt vom 20. Mai 2015 aufgehoben. Die Sache wird an die Vorinstanz zurückgewiesen, damit sie, nach erfolgter Abklärung im Sinne der Erwägungen, über die Beschwerde gegen die Verfügung der IV-Stelle Basel-Stadt vom 17. Oktober 2014 neu entscheide.
2.
Dem Beschwerdegegner wird die unentgeltliche Rechtspflege gewährt.
3.
Die Gerichtskosten von Fr. 800.- werden dem Beschwerdegegner auferlegt, indes vorläufig auf die Gerichtskasse genommen.
4.
Advokat Dominik Zehntner wird als unentgeltlicher Anwalt des Beschwerdegegners bestellt, und es wird ihm für das bundesgerichtliche Verfahren aus der Gerichtskasse eine Entschädigung von Fr. 2'800.- ausgerichtet.
5.
Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht des Kantons Basel-Stadt und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 12. April 2016
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Glanzmann
Die Gerichtsschreiberin: Keel Baumann