Futhark (programming language): Difference between revisions

Revision as of 22:18, 14 November 2019

Latest revision as of 23:40, 25 January 2025

(23 intermediate revisions by 9 users not shown)

Line 1:

{{Short description|Programming language}}

{{Infobox programming language

|name = Futhark

|paradigm = [[arrayArray programming|Arrayarray]], [[Functional programming|functional]]

|family = [[ML (programming language)|ML]]

|year = 2014

|designer = Troels Henriksen, Cosmin Oancea, Martin Elsman

|developer = [[University of Copenhagen]]<ref>{{Cite web |title=License |url=https://futhark-lang.org/license.html |access-date=2023-03-26 |website=futhark-lang.org |quote=Developed at [[UCPH Department of Computer Science|DIKU]]}}</ref>

|developer =

|released = {{Start date and age|2014}}

|latest release version =

|latest release date =

|typing = [[staticType inference|inferred]], [[Static typing|static]], [[strongStrong and weak typing|strong]], [[Hindley–Milner type system|Hindley–Milner]], [[Uniqueness type|uniqueness]], [[Dependent type|dependent]]

|implementations =

|dialects =

|influenced_byinfluenced by = [[APL (programming language)|APL]], [[Haskell (programming language)|Haskell]], [[NESL]], [[Standard ML]]

|influenced =

|operating_systemoperating system = [[Cross-platform software|cross-platform]]

|license = [[ISC license|ISC]]

|website = https://{{URL|futhark-lang.org}}

}}

'''Futhark''' is a [[functionalComparison of multi-paradigm programming languages|multi-paradigm]], [[High-level programming language|high-level]], [[Functional programming|functional]], [[dataData parallelism|data parallel]], [[arrayArray programming|array]] [[programming language]]. It is a [[Dialect (computing)|dialect]] of the language [[ML (programming language)|ML]], originally developed at [[DIKUUCPH Department of Computer Science]] (DIKU) as part of the HIPERFIT project.<ref>{{cite web |url=http://hiperfit.dk/ |title=Home |website=hiperfit.dk}}</ref>. It focuses on enabling data parallel programs written in a functional style to be executed with high performance on [[massively parallel]] hardware, in particular onespecially [[GPGPU|GPUgraphics processing unit]]s (GPUs). Futhark is strongly inspired by [[NESL]], and its implementation uses a variant of the [[flattening transformation]], but imposes constraints on how parallelism can be expressed in order to enable more aggressive compiler optimisations. In particular, irregular nested data parallelism is not supported.<ref>{{cite conference |url=https://futhark-lang.org/publications/pldi17.pdf|title=Futhark: Purely Functional GPU-Programming with Nested Parallelism and In-Place Array Updates|last1=Henriksen |first1=Troels |last2=Serup |first2=Niels G. W. |last3=Elsman |first3=Martin |last4=Henglein |first4=Fritz |last5=Oancea |first5=Cosmin |date=2017 |url=https://futhark-lang.org/publications/pldi17.pdf |title=Futhark: Purely Functional GPU-Programming with Nested Parallelism and In-Place Array Updates |publisher=ACM |book-title=Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation |conference=PLDI 2017}}</ref> It is [[free and open-source software]] released under an [[ISC license]].

== Overview ==

Futhark is a language in the [[ML (programming language)|ML]] family, with an indentation-insensitive syntax derived from [[OCaml]], [[Standard ML]], and [[Haskell]]. The [[type system]] is based on a [[Hindley–Milner type system]] with a variety of extensions, such as [[uniqueness type]]s and size-[[dependent type]]s. Futhark is not intended as a [[general-purpose programming language]] for writing full applications, but is instead focused on writing ''[[compute kernel]]s'' (not always the same as a ''GPU kernel'') which are then invoked from applications written in conventional languages.<ref>{{cite web |url=https://futhark.readthedocs.io/en/latest/ |title=Futhark User's Guide |website=futhark.readthedocs.io}}</ref>

Futhark is named after [[Runes#Runic_alphabets|the first six letters of the Runic alphabet]].<ref>{{cite thesis |last=Troels |first=Henriksen |date=November 2017 |title=Design and Implementation of the Futhark Programming Language |url=https://futhark-lang.org/publications/troels-henriksen-phd-thesis.pdf |degree=PhD |publisher=University of Copenhagen |access-date=2024-05-25}}</ref>{{rp|2}}

== Examples ==

=== Dot product ===

The following program computes the [[dot product]] of two vectors containing double-precision numbers.

<syntaxhighlight lang="futhark">

def dotprod xs ys = f64.sum (map2 (*) xs ys))

</syntaxhighlight>

It can also be equivalently written with explicit type annotations as follows.

<syntaxhighlight lang="futhark">

def dotprod [n] (xs: [n]f64) (ys: [n]f64) : f64 = f64.sum (map2 (*) xs ys))

</syntaxhighlight>

This makes the size-dependent types explicit: this function can only be invoked with two arrays of the same size, and the type checker will reject any program where this cannot be statically determined.

=== Matrix multiplication ===

The following program performs [[matrix multiplication]], using the definition of dot product above.

<syntaxhighlight lang="futhark">

def matmul [n][m][p] (A: [n][m]f64) (B: [m][p]f64) : [n][p]f64 =

map (\A_row ->

map (\B_col -> dotprod A_row B_col)

(transpose B))

A

</syntaxhighlight>

This shows how the types enforce that the function is only invoked with matrices of compatible size. Also, it is an example of nested [[data parallelism]].

== References ==

{{Reflist}}<!-- Inline citations added to your article will automatically display here. See en.wikipedia.org/wiki/WP:REFB for instructions onshows how to add citations. -->

{{reflist}}

{{ML programming}}

{{Parallel computing}}

[[Category:Programming languages]]

[[Category:High-level programming languages]]

[[Category:Functional languages]]

[[Category:Parallel computing]]

[[Category:Array programming languages]]

[[Category:Dependently typed languages]]

[[Category:Dependently typed programming]]

[[Category:Statically typed programming languages]]

[[Category:ML programming language family]]

[[Category:Free and open source compilers]]

[[Category:2014 software]]

[[Category:Programming languages created in 2014]]

[[Category:Software using the ISC license]]