New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Adapt differentiated F# and vectors, matrices, tensors as core data types #694

Open
zpodlovics opened this Issue Sep 16, 2018 · 8 comments

Comments

Projects
None yet
2 participants
@zpodlovics

zpodlovics commented Sep 16, 2018

A bit unusual to reference a research project / publication as a suggestion but this could be really important for future of the language and as a message for unique value proposition:

"Functional programming (FP) and automatic differentiation (AD) have been natural partners
for sixty years, and major functional languages all have elegant automatic differentiation
packages [6, 17, 29]. With the increasing importance of numerical engineering disciplines
such as machine learning, speech processing, and computer vision, there has never been a
greater need for systems which mitigate the tedious and error-prone process of manual coding
of derivatives. However the popular packages (TensorFlow, CNTK) all implement clunky
(E)DSLs in procedural languages such as Python and C++. Why? One reason is that the FP
packages are slower than their imperative counterparts, by many orders of magnitude [48],
because modern applications depend heavily on array processing, with vectors, matrices,
and tensors as the canonical datatypes.
In contrast, AD for FP has generally handled only
scalar workloads efficiently [29].
Our key contribution in this paper is to take a recently introduced F# subset designed
for efficient compilation of array-processing workloads
, and to augment it with vector AD
primitives, yielding a functional AD tool that is competitive with the best C/C++ and
Fortran tools on many benchmarks, and considerably faster on others.

Publication:
https://arxiv.org/abs/1806.02136

Pros and Cons

The engineering concepts could be unconfortable for some users, but could also attract lot's of users from engineering field.

Extra information

Estimated cost (XS, S, M, L, XL, XXL): XL

Related suggestions: (put links to related suggestions here)

Affidavit (please submit!)

Please tick this by placing a cross in the box:

  • This is not a question (e.g. like one you might ask on stackoverflow) and I have searched stackoverflow for discussions of this issue
  • I have searched both open and closed suggestions on this site and believe this is not a duplicate
  • This is not something which has obviously "already been decided" in previous versions of F#. If you're questioning a fundamental design decision that has obviously already been taken (e.g. "Make F# untyped") then please don't submit it.

Please tick all that apply:

  • This is not a breaking change to the F# language design
  • I or my company would be willing to help implement and/or test this
@cartermp

This comment has been minimized.

Show comment
Hide comment
@cartermp

cartermp Oct 3, 2018

Member

@zpodlovics Which paper are you referencing?

Member

cartermp commented Oct 3, 2018

@zpodlovics Which paper are you referencing?

@zpodlovics

This comment has been minimized.

Show comment
Hide comment
@zpodlovics

zpodlovics Oct 3, 2018

@cartermp It looks like for some reason the publication url was not in the issue text, I have updated the text now.

I am referring to this publication:
https://arxiv.org/abs/1806.02136

zpodlovics commented Oct 3, 2018

@cartermp It looks like for some reason the publication url was not in the issue text, I have updated the text now.

I am referring to this publication:
https://arxiv.org/abs/1806.02136

@cartermp

This comment has been minimized.

Show comment
Hide comment
@cartermp

cartermp Oct 3, 2018

Member

Thanks. My main question now is, why this should be in the language rather than a part of .NET, or in a library such as DiffSharp? I think it's reasonable to have nice things in the language for working against such types, but is the suggestion here to incorporate these sorts of data types into core F#? If so, which ones?

Member

cartermp commented Oct 3, 2018

Thanks. My main question now is, why this should be in the language rather than a part of .NET, or in a library such as DiffSharp? I think it's reasonable to have nice things in the language for working against such types, but is the suggestion here to incorporate these sorts of data types into core F#? If so, which ones?

@zpodlovics

This comment has been minimized.

Show comment
Hide comment
@zpodlovics

zpodlovics Oct 3, 2018

Because eliminating abstractions is only possible with the compiler, anything else will just introduce an another level of indirection. The suggestion is to (strategically) investigate this topic first, and if possible discuss this question with the publication authors as three of them works for Microsoft. The targeted data types would be as it mentioned in the paper: arrays, vectors, matrices, tensors.

Page 23:
"DiffSharp [7] is an AD library implemented in F#. This library provides both forward-
mode and reverse-mode AD techniques. As DiffSharp is a library implementation of AD (in
contrast to d ̃︀ f, which implements AD as source-to-source transformation rules), it cannot
not support the simplification rules such as loop-invariant code motion, loop fusion, and
partial evaluation.
"

From one of the author (Christoph Koch: Abstraction without regret in database systems building:
a manifesto) another publication from 2014:

"It has been said that all problems in computer science can be solved by adding another level of indirection, except for performance problems, which are solved by removing levels of indirection. Compilers are our tools for removing levels of indirection automatically. However, we do not trust them when it comes to systems building. Most performance-critical systems are built in low-level programming languages such as C. Some of the downsides of this compared to using modern high-level programming languages are very well known: bugs, poor programmer productivity, a talent bottleneck, and cruelty to programming language researchers."

https://infoscience.epfl.ch/record/197359/files/preprint.pdf

zpodlovics commented Oct 3, 2018

Because eliminating abstractions is only possible with the compiler, anything else will just introduce an another level of indirection. The suggestion is to (strategically) investigate this topic first, and if possible discuss this question with the publication authors as three of them works for Microsoft. The targeted data types would be as it mentioned in the paper: arrays, vectors, matrices, tensors.

Page 23:
"DiffSharp [7] is an AD library implemented in F#. This library provides both forward-
mode and reverse-mode AD techniques. As DiffSharp is a library implementation of AD (in
contrast to d ̃︀ f, which implements AD as source-to-source transformation rules), it cannot
not support the simplification rules such as loop-invariant code motion, loop fusion, and
partial evaluation.
"

From one of the author (Christoph Koch: Abstraction without regret in database systems building:
a manifesto) another publication from 2014:

"It has been said that all problems in computer science can be solved by adding another level of indirection, except for performance problems, which are solved by removing levels of indirection. Compilers are our tools for removing levels of indirection automatically. However, we do not trust them when it comes to systems building. Most performance-critical systems are built in low-level programming languages such as C. Some of the downsides of this compared to using modern high-level programming languages are very well known: bugs, poor programmer productivity, a talent bottleneck, and cruelty to programming language researchers."

https://infoscience.epfl.ch/record/197359/files/preprint.pdf

@cartermp

This comment has been minimized.

Show comment
Hide comment
@cartermp

cartermp Oct 3, 2018

Member

I don't understand what you mean by indirection. .NET already has backing types for arrays, vectors, matrices, and tensors. Part of the reason Span<T> was invented was to help with using these types without incurring performance hits from copies. There is work to be done there, but F# supports the necessary machinery to not incur any more cost than C#. Is it more language-level abstractions that you're after here?

Member

cartermp commented Oct 3, 2018

I don't understand what you mean by indirection. .NET already has backing types for arrays, vectors, matrices, and tensors. Part of the reason Span<T> was invented was to help with using these types without incurring performance hits from copies. There is work to be done there, but F# supports the necessary machinery to not incur any more cost than C#. Is it more language-level abstractions that you're after here?

@zpodlovics

This comment has been minimized.

Show comment
Hide comment
@zpodlovics

zpodlovics Oct 4, 2018

The backing types are low level implementations. No amount of low level code will be competetive with high level and domain specific compiler optimizations that could eliminate, transform or short circuit the lower level parts of the program. This is the main motivation behind this suggestion is to introduce higher level language concepts / abstractions for arrays, vectors, matrices, tensors. Assuming somewhere in the future we will have compiler plugins for AST -> AST transformations and/or staging it would be possible to implement - with these high level / domain specific compiler optimizations but without ballooning the core compiler (the most common optimizations could be also included here).

zpodlovics commented Oct 4, 2018

The backing types are low level implementations. No amount of low level code will be competetive with high level and domain specific compiler optimizations that could eliminate, transform or short circuit the lower level parts of the program. This is the main motivation behind this suggestion is to introduce higher level language concepts / abstractions for arrays, vectors, matrices, tensors. Assuming somewhere in the future we will have compiler plugins for AST -> AST transformations and/or staging it would be possible to implement - with these high level / domain specific compiler optimizations but without ballooning the core compiler (the most common optimizations could be also included here).

@cartermp

This comment has been minimized.

Show comment
Hide comment
@cartermp

cartermp Oct 4, 2018

Member

I'm afraid I still don't quite understand the language request here. Do you have some examples of these types and what they may look like in F#?

Member

cartermp commented Oct 4, 2018

I'm afraid I still don't quite understand the language request here. Do you have some examples of these types and what they may look like in F#?

@zpodlovics

This comment has been minimized.

Show comment
Hide comment
@zpodlovics

zpodlovics Oct 4, 2018

Right now there are no language level concepts and representation exists for vectors, matrices, tensors [1]. Both the AST both the TAST would be extended with Vectors, Matrices, Tensors. There will be defined operations on these new concepts, and also there will be optimizations for them. Domain specific optimizations would be also possible with eg.: AST -> AST compiler plugins (eg.: equivalent transformation, vectorized execution, etc.). Quotations could be also extended with NewVector, NewMatrix, NewTensor nodes and operations on them, so basic metaprogramming and transformation would be possible with F# snippets marked with reflecteddefinition this could be powerful with quotationcompiler.

[1] https://github.com/fsharp/fsharp/blob/master/src/fsharp/ast.fs#L439

zpodlovics commented Oct 4, 2018

Right now there are no language level concepts and representation exists for vectors, matrices, tensors [1]. Both the AST both the TAST would be extended with Vectors, Matrices, Tensors. There will be defined operations on these new concepts, and also there will be optimizations for them. Domain specific optimizations would be also possible with eg.: AST -> AST compiler plugins (eg.: equivalent transformation, vectorized execution, etc.). Quotations could be also extended with NewVector, NewMatrix, NewTensor nodes and operations on them, so basic metaprogramming and transformation would be possible with F# snippets marked with reflecteddefinition this could be powerful with quotationcompiler.

[1] https://github.com/fsharp/fsharp/blob/master/src/fsharp/ast.fs#L439

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment