skip to main content
10.1145/1159842.1159859acmconferencesArticle/Chapter ViewAbstractPublication PagesicfpConference Proceedingsconference-collections
Article

Statically typed linear algebra in Haskell

Published: 17 September 2006 Publication History

Abstract

Numerical computations are often specified in terms of operations on vectors and matrices. This is partly because it is often natural to do so; but it is also partly because, being otherwise useful, such operations have been provided very fast implementations in linear algebra libraries such as ATLAS (implementing BLAS), LAPACK, fftw, etc. Due to their better cache awareness and use of specialized processor instructions, a high-level invocation of an operation such as matrix multiplication using these libraries may execute orders of magnitude more quickly than a straightforward low-level implementation written in, say, C. The combination of efficiency and expressivity has made the framework of linear algebra an exceedingly popular one for scientists. For example, Matlab[1], an interpreter of a simple linear algebra language, has become a standard research tool in many fields.The process of expressing an algorithm in terms of matrices can be error-prone. Matlab and other popular matrix languages are dynamically-typed, which means that type errors are only detected at run-time. Even statically typed languages rarely keep track of more information in an object type than its tensor rank (e.g., to discriminate between matrices and vectors) and element type.If we could additionally expose object dimensions to the type system then we would ideally be able to detect a much wider variety of common errors at compile time than is currently possible. This would in turn make it easier to build and maintain larger numericsintensive software projects.We call our idea of exposing dimensions to the type system "strongly typed linear algebra". We have written a prototype implementation in Haskell, which is based on Alberto Ruiz's GSLHaskell[2] and which uses techniques from Kiselyov and Shan's "Implicit Configurations" paper[3].The presentation will cover the key aspects of our design such as the use of GADTs to combine matrix and vector types, and the use of higher-rank types and staging (namely, Template Haskell) to closely approximate a dependent-type system. Then, we will give a demonstration of interactive use, and compare our system to existing systems in the areas of speed and usability.

References

[1]
Matlab. http://www.mathworks.com/.
[2]
A. Ruiz. Matrix computations in haskell based on the gsl. http://dis.um.es/~alberto/GSLHaskell/matrix.pdf, June 2005.
[3]
O. Kiselyov and C. Shan. Functional pearl: implicit configurations-or, type classes reflect the values of types. In Haskell '04: Proceedings of the 2004 ACM SIGPLAN workshop on Haskell, pages 33--44, New York, NY, USA, 2004. ACM Press.
[4]
SciViews. http://www.sciviews.org/benchmark/index.html, August 2003.
[5]
J.W. Eaton. GNU Octave: a high-level interactive language for numerical applications. GNU/Free Software Foundation, Boston, 1998.
[6]
F. Eaton. Statically typed linear algebra in haskell (papers and sourcecode). http://ofb.net/~frederik/stla/, July 2006.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
Haskell '06: Proceedings of the 2006 ACM SIGPLAN workshop on Haskell
September 2006
131 pages
ISBN:1595934898
DOI:10.1145/1159842
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 September 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. existential types
  2. higher-rank polymorphism
  3. linear algebra
  4. staging
  5. template Haskell

Qualifiers

  • Article

Conference

ICFP06
Sponsor:

Acceptance Rates

Overall Acceptance Rate 57 of 143 submissions, 40%

Upcoming Conference

ICFP '25
ACM SIGPLAN International Conference on Functional Programming
October 12 - 18, 2025
Singapore , Singapore

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Gradual Tensor Shape CheckingProgramming Languages and Systems10.1007/978-3-031-30044-8_8(197-224)Online publication date: 22-Apr-2023
  • (2022)ReftyProceedings of the 44th International Conference on Software Engineering10.1145/3510003.3510077(1843-1855)Online publication date: 21-May-2022
  • (2017)Typesafe abstractions for tensor operations (short paper)Proceedings of the 8th ACM SIGPLAN International Symposium on Scala10.1145/3136000.3136001(45-50)Online publication date: 22-Oct-2017
  • (2017)APLicative Programming with Naperian FunctorsProgramming Languages and Systems10.1007/978-3-662-54434-1_21(556-583)Online publication date: 19-Mar-2017
  • (2015)A Simple and Practical Linear Algebra Library Interface with Static Size CheckingElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.198.1198(1-21)Online publication date: 5-Dec-2015
  • (2015)Type inference for array programming with dimensioned vector spacesProceedings of the 27th Symposium on the Implementation and Application of Functional Programming Languages10.1145/2897336.2897341(1-12)Online publication date: 14-Sep-2015
  • (2012)Statically typed matrixProceedings of the Fifth Balkan Conference in Informatics10.1145/2371316.2371359(217-222)Online publication date: 16-Sep-2012

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media