Alexander A. Stepanov

This site is a collection of Alex Stepanov's books, papers, class notes, and source code, covering generic programming and other topics. Technical contact: paul@mcjones.org.

Books

• From Mathematics to Generic Programming
  • Alexander A. Stepanov and Daniel E. Rose: From Mathematics to Generic Programming. Addison-Wesley Professional, November 7, 2014. See www.fm2gp.com for more information, including sample chapter, source code, and errata. See below for the videos and slides of the Three Algorithmic Journeys course from which this book evolved.
• Elements of Programming
  • Alexander Stepanov and Paul McJones: Elements of Programming. Semigroup Press, June 2019 and Addison-Wesley Professional, June 2009. See elementsofprogramming.com for a free PDF version, a link to purchase a paperback copy, source code, and errata.
  • Alexander Stepanov: Transformations and their orbits. Lecture based on Chapter 2 of Elements of Programming presented at Yandex, April 20, 2010.
    • Video. Part 1 Part 2
    • Slides. PDF (See also Chapter 2.)
  • Alexander Stepanov and Paul McJones: Elements of Programming. Lecture presented at Stanford University Department of Electrical Engineering Computer Systems Colloquium (EE380), November 3, 2010.
    • Abstract
    • Slides. PDF
    • Video: Stanford / YouTube / iTunes
• C++ Standard Template Library
  • P.J. Plauger, Meng Lee, David Musser, and Alexander A. Stepanov:  C++ Standard Template Library. Prentice Hall PTR, December 2000, 498 pages.
• The Ada Generic Library Linear List Processing Packages
  • David R. Musser and Alexander A. Stepanov: The Ada Generic Library Linear List Processing Packages. Springer-Verlag, 1989, 289 pages.

Generic programming

• D. Kapur, D. R. Musser, and A. A. Stepanov: Operators and Algebraic Structures. Proceedings of the 1981 conference on Functional programming languages and computer architecture, pages 59-63. PDF (online at acm.org)
  • Also appears as General Electric Company, Corporate Research and Development, Report 81CRD114. PDF
• Deepak Kapur, David R. Musser, and Alexander A. Stepanov: Tecton: A Language for Manipulating Generic Objects. In Program Specification, Proceedings of a Workshop, Aarhus, Denmark, August 1981, J. Staunstrup, editor, Lecture Notes In Computer Science, volume 134, Springer-Verlag, London, pages 402-414. PDF
• Alexander Stepanov and Aaron Kershenbaum: Using Tournament Trees to Sort, Center for Advanced Technology in Telecommunications Technical Report 86-13, Polytechnic University of New York, 1986. PDF
• Alexander A. Stepanov, Aaron Kershenbaum, and David R. Musser: Higher Order Programming. March 5, 1987. PDF
• David R. Musser and Alexander A. Stepanov: A library of generic algorithms in Ada. Proceedings of the 1987 annual ACM SIGAda international conference on Ada, pages 216-225. PDF  (online at acm.org)
  • Also: slides from conference presentation. PDF
• Aaron Kershenbaum, David Musser, and Alexander Stepanov: Higher Order Imperative Programming. Rensselaer Polytechnic Institute Computer Science Department, Technical Report 88-10. April 1988. PDF PostScript
• David R. Musser and Alexander A. Stepanov: Generic Programming. ISSAC 1988, pages 13-25. PDF PostScript
• D. R. Musser and A. A. Stepanov: Ada Generic Library Linear Data Structure Packages, Release 1.1, General Electric Company, Corporate Research and Development.
  • Volume One, Report 88CRD112, March 4, 1988. PDF
  • Volume Two, Report 88CRD113, March 3, 1988. PDF
• D. Kapur, D. Musser, W. Olthoff, A. Snyder, A. Stepanov, and A. Szymanski. A Prototyping Language for Rapid Reuse : Technical Proposal. Software Technology Laboratory Report STL-89-10, Hewlett-Packard Laboratories, 1989. PDF
• Alexander A. Stepanov: Design of Generic Libraries. Lecture given at SRI, 1991. PDF
• David R. Musser and Alexander A. Stepanov: Algorithm-oriented Generic Libraries.
  • Software—Practice and Experience, Vol. 24(7), July 1994, pages 623-642. PDF PostScript
  • HP Laboratories Technical Report 94-13, February 1994. PDF (online at hp.com)
  • Preprint. September 1993. PDF PostScript
  • Algorithm-Oriented Generic Libraries. Rensselaer Polytechnic Institute Computer Science Department Technical Report 92-23, 1993.
  • Algorithm-Oriented Generic Software Library Development. HPL-92-65(R.1), November 1993 PDF (online at hp.com)
  • Algorithm-Oriented Generic Software Library Development. Rensselaer Polytechnic Institute Computer Science Department Technical Report 92-13, April 1992.
• Mehdi Jazayeri, Meng Lee, and Alex Stepanov: Generic C++ Components. Hewlett-Packard Laboratories/CSL/CCD/PAP/CLL talk, October 4, 1993, 17 slides. PDF
• Alexander A. Stepanov: Science of C++ Programming. Invited presentation to C++ standards committee, San Jose, California, November 11, 1993, 25 slides. PDF
  
• Meng Lee & Alexander Stepanov: Science of C++ Programming. Hewlett-Packard Laboratories, January 1994, 45 slides. PDF
• Alexander Stepanov & Meng Lee: The Standard Template Library. Presentation to the C++ standards committee, March 7, 1994, 19 slides. PDF
• Alexander Stepanov and Meng Lee: The Standard Template Library. HP Laboratories Technical Report 95-11(R.1), November 14, 1995. PDF PostScript FrameMaker
  • Revised version of A. A. Stepanov and M. Lee: The Standard Template Library, Technical Report X3J16/94-0095, WG21/N0482, ISO Programming Language C++ Project, May 1994.
  • Supercedes Alexander Stepanov and Meng Lee: The Standard Template Library. HP Laboratories Technical Report 94-34(R.1), April 13, 1994.
• Alexander Stepanov: The Standard Template Library. BYTE Magazine, October 1995. HTML (online at byte.com via Internet Archive)

  Note: in the code for remove_copy_if, the expression !prod(*first) should be !pred(*first).

• Matthew H. Austern, Ross A. Towle, and Alexander A. Stepanov: Range partition adaptors: a mechanism for parallelizing STL. ACM SIGAPP Applied Computing Review, Volume 4, Issue 1. Spring 1996, pages 5-6. PDF (online at acm.org)
• Alexander Stepanov: Generic Programming. Keynote Lecture presented at The Second International Andrei Ershov Memorial Conference on Perspectives of System Informatics; abstract appears in Lecture Notes In Computer Science, volume 1181, June 1996, page 40.
• David R. Musser and Alexander A. Stepanov: Generic Programming Projects and Open Problems. August 25, 1998. online at rpi.edu (local) PDF PostScript
• James C. Dehnert and Alexander A. Stepanov: Fundamentals of Generic Programming. Report of the Dagstuhl Seminar on Generic Programming, Schloss Dagstuhl, Germany, Apr. 1998. Lecture Notes in Computer Science, PDF PostScript
• Alexander Stepanov: Greatest Common Measure: the Last 2500 Years. Originally prepared as the 1999 Arthur Schoffstall Lecture in Computer Science and Computer Engineering at the Rensselaer Polytechnic Institute.
  • Slides. Updated June 2004. PDF PowerPoint
  • Video of same lecture presented at SmartFriends U, September 27, 2003 (by permission of SmartFriends). QuickTime
  • Video of same lecture presented at Yandex, Moscow, April 19, 2010.
    • Part 1 Part 2
    • Slides (Russian): PDF PowerPoint
• Alexander Stepanov: Foreword. Appears in David R. Musser, Gillmer J. Derge, and Atul Saini, STL Tutorial and Reference Guide, Second Edition: C++ Programming with the Standard Template Library. Boston, MA: Addison-Wesley, 2001. PDF
• Alexander Stepanov: STL and Its Design Principles. Talk presented at Adobe Systems Inc., January 30, 2002. PDF PowerPoint Real Player
• Alexander Stepanov: Foreword. Appears in Jeremy G. Siek, Lie-Quan Lee and Andrew Lumsdaine: The Boost Graph Library: User Guide and Reference Manual. Boston, MA: Addison-Wesley, 2002. HTML PDF
• Alexander Stepanov: Future of Abstraction. A keynote address at Joint ACM Java Grande - ISCOPE 2002 Conference, Seattle, Washington, November 3-5, 2002. Abstract PDF PowerPoint
• Alexander Stepanov: Designing Efficient Libraries. Talk presented at Adobe System Inc., July 21, 2003. PDF PowerPoint
• Alexander Stepanov: Short History of STL. Contributed to Evolving a language in and for the real world: C++ 1991-2007 by Bjarne Stroustrup, August 10, 2006. PDF

Information retrieval

• Alexander A. Stepanov, Anil R. Gangolli, Daniel E. Rose, Ryan J. Ernst, and Paramjit S. Oberoi: SIMD-Based Decoding of Posting Lists. ACM Conference on Information and Knowledge Management (CIKM 2011), October 24–28, 2011, Glasgow, Scotland, UK.
  • Paper. PDF
  • Slides: PowerPoint PDF
• Alexander A. Stepanov, Anil R. Gangolli, Daniel E. Rose, Ryan J. Ernst, and Paramjit S. Oberoi: SIMD-Based Decoding of Posting Lists. A9 Technical Report A9TR-2011-01, revision 2, June 2014, 30 pages. Appendix includes C++ code. PDF

Logic

• D. Kapur, D. R. Musser, and A. A. Stepanov: A Guide to Tecton and Natural Logic. Working document, General Electric Research & Development Center, July 1983. PDF
• D. Kapur, D. R. Musser, and A. A. Stepanov: Notes on a Logic of Objects. Working document, General Electric Research & Development Center, July 1983. PDF
• D. Kapur, D. R. Musser, and A. A. Stepanov: Modalities, Abstraction and Reasoning. Working document, General Electric Research & Development Center, July 1983. PDF
• D. Kapur, D. R. Musser, and A. A. Stepanov: Syntax of the Tecton Language. Working document, General Electric Research & Development Center, February 1983. PDF
• Alexander Stepanov: Towards a Theory of Causal Implication. Department of Electrical Engineering and Computer Science, Polytechnic University of New York, 1985. PDF Word
  • Original. PDF

Robotics

• V. Lumelsky and A. Stepanov: Navigation Strategies for an Autonomous Vehicle with Incomplete Information on the Environment. General Electric Company, Corporate Research and Development, Report 84CRD070. PDF
• Vladimir J. Lumelsky and Alexander A. Stepanov: Effect of Uncertainty on Continuous Path Planning for an Autonomous Vehicle. Proceedings of 23rd Conference on Decision and Control, Las Vegas NV, December 1984, pages 1616-1621. PDF
• V. Lumelsky and A. Stepanov: Dynamic path planning for a mobile automaton with limited information on the environment. IEEE Trans. on Automatic Control, AC-31, pages 1058-1063, 1986. PDF
• V. Lumelsky and A. Stepanov: Path planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape. Algorithmica, Volume 2, pages 403-430, 1987. PDF Republished in Autonomous robot vehicles, pages 363-390, 1990.

Storage systems

• Robert M. English and Alexander A. Stepanov: Loge: a self-organizing disk controller. Proceedings of USENIX Winter 1992 Technical Conference, January 20-24, 1992 (San Francisco, CA), pages 237-251. PDF PostScript
• Chia Chao, Robert English, David Jacobson, Alexander Stepanov, and John Wilkes: Mime: a high performance parallel storage device with strong recovery guarantees. HP Laboratories Technical Report HPL-CSP-92-9rev1, March 1992, revised November 1992. PDF PostScript
• John Wilkes, Chia Chao, Robert English, David Jacobson, Bart Sears, Carl Staelin, and Alex Stepanov: DataMesh parallel storage servers. ACM SIGOPS Operating Systems Review, Volume 26 , Issue 2, April 1992, page 11. PDF (online at acm.org)
• John Wilkes, with Chia Chao, Robert English, David Jacobson, Sai-Lai Lo, Chris Ruemmler, Bart Sears, Alex Stepanov, and Rebecca Wright: DataMesh research project, phase 1. Proceedings of USENIX Workshop on File Systems (Ann Arbor, MI), 21-22 May 1992, pages 63-69. PDF PostScript
• Chia Chao, Robert English, David Jacobson, Bart Sears, Alexander Stepanov, and John Wilkes: DataMesh Architecture 1.0. HP Laboratories Technical Report HPL-92-153, December 1992. PDF PostScript

Various talks

• Alexander Stepanov: Professionalism in Programming. Presented at Adobe Systems Inc., April 17, 2003. PDF PowerPoint
• Alexander Stepanov: Industrializing Software Development. A keynote address at The First International Conference on Embedded Software and System, Zhejiang University, Hangzhou, P. R. China, December 9, 2004. PDF PowerPoint
• Alexander Stepanov: Educating Programmers: A Customer Perspective. Presented at Workshop on Quality Software: A Festschrift for Bjarne Stroustrup, Texas A&M University, April 27‐28, 2012. Video at YouTube PDF PowerPoint
• Alexander Stepanov: One algorithm from The Book: A tribute to Ira Pohl. Invited lecture at Ira Fest – in Honor of Computer Science Professor Emeritus Ira Pohl, University of California Santa Cruz, April 26, 2014. PDF PowerPoint

Interviews

• Al Stevens Interviews Alex Stepanov: Dr. Dobb's Journal, March 1995. PDF HTML (online at sgi.com via Internet Archive)
• Graziano Lo Russo: An Interview with A. Stepanov: Edizioni Infomedia S.r.l. PDF HTML (online at stlport.org) Original Italian version. PDF
• Yuyong Zhao: An interview with Alex Stepanov. Chinese Popular Computer Week, 28 February 2005. PDF Original Chinese version. PDF HTML
• Andrew Binstock: An interview with Alexander Stepanov and Paul McJones on Elements of Programming. informIT, August 2009. (online at informit.com)
• Robert Rozeboom: Alexander Stepanov and Daniel E. Rose Answer Your Questions. Slashdot, January 2015. (online at slashdot.org)
• John Lakos: From Mathematics to Generic Programming: An Interview with Alexander Stepanov and Daniel Rose. informIT, February 2015. (online at informit.com)

Bibliographies

• DBLP Bibliography Server entry for Alexander A. Stepanov (local copy)

Source code

• Alexander Stepanov: Scheme higher order programming library, August 1986. .tar unpacked notes
• Alexander Stepanov: gclib, AT&T Bell Laboratories, 1987. With only cosmetic changes, this becam Array_alg within the USL C++ Standard Components. C documentation
• David R. Musser and Alexander A. Stepanov: Ada Generic Library (source files described in The Ada Generic Library: Linear List Processing Packages, Compass Series, Springer-Verlag, 1989). .zip unpacked README
• Alexander Stepanov: Algorithmic simulation and measurement codes, 1993. .zip unpacked
• Alexander Stepanov and Meng Lee: The Standard Template Library, HP Laboratories, release of October 31, 1995.
  • Release directory. Contains STL, FAQ, and related materials. unpacked (originally from ftp://butler.hpl.hp.com/stl/)
  • stl.zip unpacked (originally from ftp://butler.hpl.hp.com/stl/stl.zip)
• Alex Stepanov: Abstraction Penalty Benchmark, version 1.2 (KAI). Silicon Graphics, Incorporated, 199?. C++
• Also appears as Appendix D.3 of Technical Report on C++ Performance, ISO/IEC PDTR 18015, 11 August 2003 PDF
• Matthew Austern and Alexander Stepanov: jal (Java Algorithm Library), Silicon Graphics, Incorporated, 1996.
  • Source (generic) version: .tar.gz unpacked
  • Source (instantiated) version: .jar documentation
• Matt Austern with Hans Boehm (managed by Alexander Stepanov). SGI Standard Template Library. Source code and documentation for the version of the Standard Template Library developed at Silicon Graphics, Inc. during 1996-1999. (online at sgi.com/tech/stl/ via Internet Archive)
• Bjarne Stroustrup and Alex Stepanov: Standard Container Benchmark, version 0.9. May 2003 C++

Class notes and videos

Note: The documents in this section have been superseded by From Mathematics to Generic Programming and Elements of Programming (see above).

• Alexander Stepanov: Notes for the Higher Order Programming in Scheme course taught at the General Electric Corporate R&D Center. Schenectady, New York, July 1986. PDF text
• A. A. Stepanov: CS 603 Notes. Department of Electrical Engineering and Computer Science, Polytechnic University of New York, 1986(?). PDF
• Alexander A. Stepanov: Handouts for the Advanced Programming class taught by David R. Musser at Rensselaer Polytechnic Institute. 1990. PDF
• Jim Dehnert, Alexander Stepanov, and John Wilkinson: Incomplete notes for the Generic Programming course taught by Alex at Silicon Graphics Inc. December 1998. HTML PDF
• Alexander Stepanov: Incomplete notes for the Foundations of Programming course taught at Adobe. May 2004 (corrected version May 2005). PDF Word
• Alexander A. Stepanov and Matthew A. Marcus: Notes for the Foundations of Programming course at Adobe. 2004-2005.
  • Section 1 (mathematical preliminaries up to RSA). PDF
  • Section 2 (generic programming). PDF
  • Section 3 (partition algorithms). PDF Word
• Alexander Stepanov: Notes for the Programming course at Adobe. 2005-2006 (updated October 2007 to fix bugs in partition_bidirectional and December 2012 to fix a bug in partition_3way_bidirectional). PDF Word
• Alexander Stepanov: Three Algorithmic Journeys. Lectures presented at A9.com, 2012. A fourth journey was originally planned but there are no immediate plans to complete it.
  • I. Spoils of the Egyptians: How elementary properties of commutativity and associativity of addition and multiplication led to fundamental algorithmic and mathematical discoveries. Video at YouTube PDF
  • II. Heirs of Pythagoras: How division with remainder led to discovery of many fundamental abstractions. Video at YouTube PDF
  • III. Successors of Peano: The axioms of natural numbers and their relation to iterators.Video at YouTube PDF
  • Epilogue. Video at YouTube PDF
• Alexander A. Stepanov and Daniel E. Rose: Three Algorithmic Journeys. Preliminary draft 0.3, January 4, 2013. PDF
• Alexander A. Stepanov and Daniel E. Rose: Notes on Set Theory, Logic, and Computation. August 29, 2013. PDF

  Authors' Note: This document contains material from the Three Algorithmic Journeys course taught by Alex Stepanov at A9 in 2012, which we decided to remove from the forthcoming book based on the course.



Alex with students at the end of the course
• Alexander A. Stepanov: Efficient Programming with Components. Lectures at A9.com, 2013.
  • Video at YouTube
  • Source code: .tar.gz GitHub project
• Alexander A. Stepanov and Paramjit Oberoi: Programming Conversations. Ongoing lectures at A9.com, 2014.
  • Video at YouTube
  • Source code: GitHub project

Civilization

• Alexander A. Stepanov: Civilizing the Barbarians. Lectures at A9.com, 2015. Reading list and video
• The Short Canon: A short list of materials for civilizing programmers. Reading list

Alex Fest

• Alex Fest: A celebration of the work of Alexander A. Stepanov. Held by A9 on January 11, 2016 in Palo Alto, California.
• Talks by Bjarne Stroustrup, David Musser, Sean Parent, Daniel Rose, and Paul McJones. Video at YouTube
• Photographs at Google Photos

Acknowledgments

Paul McJones maintains this collection. He began in the spring of 2004, and has been assisted by Dave Musser, Meng Lee, Jim Dehnert, Jeremy Siek, Mat Marcus, Paramjit Oberoi, and Alex Stepanov.

Notice: Some of the documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.