Swift Algorithms(swift.org)
swift.org
Swift Algorithms
https://swift.org/blog/swift-algorithms/
79 comments
“rust just got AVR support which I suppose swift could get pretty quickly with llvm as well”
In theory, yes, but in practice I don’t see Swift going there comfortably. Its more dynamic runtime (compared to C or rust) needs more metadata, eating memory, which is precious on AVR (384 kilobytes, max, reading https://en.wikipedia.org/wiki/AVR_microcontrollers)
In theory, yes, but in practice I don’t see Swift going there comfortably. Its more dynamic runtime (compared to C or rust) needs more metadata, eating memory, which is precious on AVR (384 kilobytes, max, reading https://en.wikipedia.org/wiki/AVR_microcontrollers)
Just like you don't do ANSI C there, so a similar constrained version might be possible, not much different from Pascal.
https://www.mikroe.com/mikropascal-avr
https://www.mikroe.com/mikropascal-avr
[deleted]
Yeah, back when we first started using it there was a lot of interest in using it to create back-ends as well, but there just wasn't a lot of support for it. For one, it needed to be developed and compiled on a not-Mac environment to be viable, and that has just never been much of a thing. Might be better now, it does just use LLVM in the back-end and IntelliJ has a good editor for it, but still.
I think C# had that problem for a long time, but Microsoft did a great job / made a great strategic decision with .NET Core I think.
I think C# had that problem for a long time, but Microsoft did a great job / made a great strategic decision with .NET Core I think.
Still Mono, Xamarin and Unity preceded that decision.
True, but even now the C# library ecosystem is lacking compared to e.g. JVM/JavaScript/Python ecosystems. And that's definitely because it was historically closed source and mostly (but not entirely) single-platform.
I dont agree with "C# library ecosystem is lacking". The nuget ecosystem is massive, and the paid offerings side is much larger (owing to more of an enterprise audience generally). There arent a lot of well known projects that _run_ on the CLR like there are on the JVM, but the in-language ecosystem is just as robust as those other ecosystems if not more so.
> the paid offerings side is much larger
The fact that a lot of the offerings are paid is a massive negative to me. I don't know of any other language ecosystem that is like this.
The fact that a lot of the offerings are paid is a massive negative to me. I don't know of any other language ecosystem that is like this.
.NET CLR + BCL was originally released as BSD code, Rotor project, but no one cared about it.
.NET was also available in other platforms where Microsoft saw commercial value, via partner agreements.
http://www.jot.fm/issues/issue_2006_04/article4.pdf
https://www.sidiary.org/press-Diabetes_Symbian-968.asp
.NET was also available in other platforms where Microsoft saw commercial value, via partner agreements.
http://www.jot.fm/issues/issue_2006_04/article4.pdf
https://www.sidiary.org/press-Diabetes_Symbian-968.asp
I saw posts on r/rust talking about making a rust-like language for non system programming. I think Swift fits exactly that purpose, only frustrated by Apple giving it Windows support a decade after it's creation.
> only frustrated by Apple giving it Windows support a decade after it's creation.
Swift was only publicly announced six years ago.
Swift was only publicly announced six years ago.
This looks great. I'm looking forward to this and swift-numerics maturing.
If you haven't seen it, check out the 2018 WWDC session "Embracing Algorithms" (https://developer.apple.com/videos/play/wwdc2018/223/). It's worth watching, even if you don't work with Swift.
If you haven't seen it, check out the 2018 WWDC session "Embracing Algorithms" (https://developer.apple.com/videos/play/wwdc2018/223/). It's worth watching, even if you don't work with Swift.
I second that. So far every talk by Dave Abrahams has been entertaining and insightful to me.
He was also recently interviewed on a podcast here: https://swiftbysundell.com/podcast/71/.
I'm watching the talk now, the way the speaker describes the things he does seems to me like hes making fun of the Silicon Valley type lifestyle. I think the talk is really great and funny, thank you for sharing !
He's satirizing the rigid and dismissive Gilfoyle type of person (HBO Silicon Valley character) while also exploring what app developers can learn from them.
Do you mean Crusty, because in my Opinion with the character he is portraying he is satirizing the typical health "crazed" silicon valley developer, is he not ?
One issue with Go's lack of generics is exactly that it can't have such a package (and have it be type safe, fast, and work across all relevant types), except with repeated code.
Yeah, though a solution is in the works, and looking pretty likely to happen. Here's the official draft design for generics or "type parameters" in Go: https://go.googlesource.com/proposal/+/refs/heads/master/des...
Dependently typed Golang when??
In all seriousness, it feels like go's reputation of simplicity is at odds with its design. Instead of making a simple and highly generalized core from which anything can be composed, it has a specialized, familiar core that engineers are comfortable with.
When I take this question further, I begin to wonder why we even use text syntax for programming. What if we just had a graph structured programming "language" that is edited indirectly through different projected syntaxes that aren't necessarily monospaced text. Almost like lisp, but translated into different frontend languages, potentially graphical. (Maybe off topic but whatever)
In all seriousness, it feels like go's reputation of simplicity is at odds with its design. Instead of making a simple and highly generalized core from which anything can be composed, it has a specialized, familiar core that engineers are comfortable with.
When I take this question further, I begin to wonder why we even use text syntax for programming. What if we just had a graph structured programming "language" that is edited indirectly through different projected syntaxes that aren't necessarily monospaced text. Almost like lisp, but translated into different frontend languages, potentially graphical. (Maybe off topic but whatever)
You can do that but the cognitive overhead of understanding what code is represented becomes more of a burden than the burden of producing logic that is correct and fulfills requirements. You can see part of this in lisps where the arguments of many functions form their own de-facto languages. Then you are not only writing code, but writing it in a variety of different languages that share only a common syntax.
The thing is, I've never found this to be a huge issues in lisps: partly because plenty of languages have libraries that are essentially the same sort of thing, but less ergonomic: Spring/Hibernate in Java, Spark and the various FP stuff in Scala, Ruby on Rails, React. Any sufficiently complex library is essentially an embedded language that must be learned in addition to the base language: the cost of learning a language made out of macros isn't much different from learning a library with a large API surface area.
In fact, since macros reduce the noise in the "language" a library implements, I've generally found that macro-based libraries are somewhat easier to learn than libraries in other languages.
In fact, since macros reduce the noise in the "language" a library implements, I've generally found that macro-based libraries are somewhat easier to learn than libraries in other languages.
Here's the dilemma as I see it:
A carefully designed library that introduces a small set of coherent concepts can make good use of powerful syntactic abstractions and result in readable and succinct code.
But application code that implements a large number of one-off requirements is far harder to read if you cannot rely on fixed semantics of basic syntactical elements.
The usual response to that is to say that we shouldn't restrict the features available to good developers just because bad developers might abuse them.
But this argument is flawed. If you read syntax that can be overloaded then you have to account for the possibility that it actually is. It's the possibility that creates the mental burden, not the fact.
I think the solution is for languages to provide a basic set of syntactical elements that cannot be overloaded and are sufficient to write all code. Additionally, there should be optional syntactical elements that can be overloaded even to the point of creating DSLs.
The important point is, there has to be a local cue that tells you whether or not you have to watch out for redefined semantics.
A carefully designed library that introduces a small set of coherent concepts can make good use of powerful syntactic abstractions and result in readable and succinct code.
But application code that implements a large number of one-off requirements is far harder to read if you cannot rely on fixed semantics of basic syntactical elements.
The usual response to that is to say that we shouldn't restrict the features available to good developers just because bad developers might abuse them.
But this argument is flawed. If you read syntax that can be overloaded then you have to account for the possibility that it actually is. It's the possibility that creates the mental burden, not the fact.
I think the solution is for languages to provide a basic set of syntactical elements that cannot be overloaded and are sufficient to write all code. Additionally, there should be optional syntactical elements that can be overloaded even to the point of creating DSLs.
The important point is, there has to be a local cue that tells you whether or not you have to watch out for redefined semantics.
Like Jetbrains MPS? https://www.jetbrains.com/mps/concepts/
Text is readily manipulated using a variety of tools.
Sounds to me like a job for a DSL that compiles down to Golang for the final output. That way, the repeated code only exists in the Golang output and not in the code that humans actually write.
the solution is... to not use Golang!
more specifically, fairly basic operations on a list of data does not seem like it should call for the complexity of a DSL. IMO unless you need to do this quite a bit on random datatypes, copy & paste would probably be the better alternative. Unless you're referring to a DSL that looks exactly like Golang but with generics & monomorphism.... in which case ok I guess
more specifically, fairly basic operations on a list of data does not seem like it should call for the complexity of a DSL. IMO unless you need to do this quite a bit on random datatypes, copy & paste would probably be the better alternative. Unless you're referring to a DSL that looks exactly like Golang but with generics & monomorphism.... in which case ok I guess
When that solution is possible, sometimes project requirements make us use tools that we rather not, but have to.
If you do that you have no soul. Why complicate it when you can just have generics that work from the get go
Because generics is a nontrivial problem to solve in languages and compilers; a really great comment that I bookmarked is here: https://news.ycombinator.com/item?id=9622417. I read elsewhere (can't find it now) just how much lines of code and language spec is dedicated to generics in Java.
Right now, the Go spec + compiler chain are a lot simpler; adding generics would have made things a ton more complicated. Second, by first spending a lot of time perfecting the core language, understanding it, and resolving early issues, they have a much more stable base now to build generics on top of it. As the comment also implies, they take things slow and steady when it comes to Go; it's a language made to run core systems (e.g. at Google) for the next 30-50 years.
Right now, the Go spec + compiler chain are a lot simpler; adding generics would have made things a ton more complicated. Second, by first spending a lot of time perfecting the core language, understanding it, and resolving early issues, they have a much more stable base now to build generics on top of it. As the comment also implies, they take things slow and steady when it comes to Go; it's a language made to run core systems (e.g. at Google) for the next 30-50 years.
All I can say to that is: Taking Java and C++ to be generics as god intended is not a particularly good thing to plan around. D's generics are concise, strict, relatively simple, and mostly understandable by mere mortals (in the compiler) - this is a totally solved problem for a language like D, if Go can't do it then it's their own fault.
Googling about this (I assumed the actual 'solution' would be a to use C-style awful macro kludges) eventually lead me to:
https://blog.golang.org/generate
Now I'm wondering if you joke was not actually a joke.
https://blog.golang.org/generate
Now I'm wondering if you joke was not actually a joke.
This is how C++ compilers used to work before templates came into the picture.
For example Borland's BIDS 1.0 in Borland C++ for MS-DOS, it was based on the C pre-processor, as you would define a set of macros and then include the desired type, something like
To be fair, Go generics seem to be finally on their way to be adopted into the language.
For example Borland's BIDS 1.0 in Borland C++ for MS-DOS, it was based on the C pre-processor, as you would define a set of macros and then include the desired type, something like
#define LIST_T int
#include <bids/list.h>
#define LIST_T float
#include <bids/list.h>
To be fair, Go generics seem to be finally on their way to be adopted into the language.
We have a lot of codegen in our codebase right now and I can't wait for the day that generics are finally added.
As heavy critic, but also fan, I have been following up on it, and the last update on the document is from September, so I am positive they might make it, it just appears the proper implementation still has some engineering challenges.
https://go.googlesource.com/proposal/+/refs/heads/master/des...
https://go.googlesource.com/proposal/+/refs/heads/master/des...
Well, and there is also kinda sorta support foir generics on top of it:
https://github.com/vasilevp/aboriginal
There is no engineering challenge that can't be overcome by ingenious thought!
https://github.com/vasilevp/aboriginal
There is no engineering challenge that can't be overcome by ingenious thought!
Instead of just using an actual good language?! Go is the problem!
"Good" is meaningless – there is no absolute measure of the relative value of one programming language over another. C is not "better" than Python, or vice versa, just different tradeoffs for different problems and programming styles. The same is for Go.
I think there is some measure of value to not having to use a whole different language to generate go because it's incapable of making maintainable code without it.
This is stockholm syndrome.
This is stockholm syndrome.
Part of Go’s tradeoff is managing that extra effort (or delay in waiting for the features to hit the main branch) in return for an extremely stable, simple language.
You might find that to be a terrible idea, but others ostensibly think differently (Go is quite popular)
Personally, I prefer more advanced type systems. But I understand Go can be a good choice in other situations.
You might find that to be a terrible idea, but others ostensibly think differently (Go is quite popular)
Personally, I prefer more advanced type systems. But I understand Go can be a good choice in other situations.
> Go is quite popular
Well sure, but inheritance and enterprise-style Java were all the rage in the 90s, but they largely haven't stood the test of time. I rather suspect Go will be similar. It has some good ideas, and it's compiler toolchain is top-quality. But I'd be willing to bet that the languages we're using in 20 years time look a lot more like Rust/Swift/Kotlin and TypeScript/Julia than Go.
Well sure, but inheritance and enterprise-style Java were all the rage in the 90s, but they largely haven't stood the test of time. I rather suspect Go will be similar. It has some good ideas, and it's compiler toolchain is top-quality. But I'd be willing to bet that the languages we're using in 20 years time look a lot more like Rust/Swift/Kotlin and TypeScript/Julia than Go.
Go will eventually grew up to be like Java and Cä# in 2020.
Java was released in 1996, and only got enterprise-style C++ adoption around 2000.
Until then, the inheritance and enterprise-style programming was done in a mix of Smalltalk, Eiffel, C++ and C based OOP.
Julia is basically Dylan/Common Lisp at its kernel, Java and C# are getting all the ML like goodies to stay relevant, see C# vs F#.
Java was released in 1996, and only got enterprise-style C++ adoption around 2000.
Until then, the inheritance and enterprise-style programming was done in a mix of Smalltalk, Eiffel, C++ and C based OOP.
Julia is basically Dylan/Common Lisp at its kernel, Java and C# are getting all the ML like goodies to stay relevant, see C# vs F#.
Kind of, but C and Python have undergone many iterations to try to become as good as they can be, while Go has lagged behind and almost prides itself on how uncomplex it is which is unfortunate only because people crave for it to be more complex. With languages like C and Python, the complexity and capability is there; it’s on you to decide when to use it. With Golang, you are just SOL.
The thing is, do you want so many iterations to get something close to being good. Or do you want people to work with the community and decide together what a feature should look like and then get it in a good shape at day 1.
Like, ask any python dev what dependency management is like. That's what iteration gets you. Take your time and you get in a much better shape.
Like, ask any python dev what dependency management is like. That's what iteration gets you. Take your time and you get in a much better shape.
Thing is, I’m not convinced Go is actually “taking their time,” it’s just intentionally crap and there won’t be any significant improvements. Generics have been “coming” since the language became popular ~10 years ago.
Ah the original templates from C++.
> Sounds to me like a job for a DSL that compiles down to Golang for the final output.
So, you mean it's the job for generics. Which is a DSL for, well, generic types that compiles to final output. That way, the repeated code doesn't even exist, especially not in the code that humans actually write.
So, you mean it's the job for generics. Which is a DSL for, well, generic types that compiles to final output. That way, the repeated code doesn't even exist, especially not in the code that humans actually write.
I love this, and best of luck to Nate and the Apple team. I wonder how many of the (awesome) algorithms on Ray Wenderlich's similar repo fit in: https://github.com/raywenderlich/swift-algorithm-club
I'm really, really happy to see this. I know this is going to sound like parody or satire, but I swear I'm being sincere: this is a huge deal for applying to FAANG (and companies that do FAANG interviews) and leetcoding in Swift.
It's incredibly painful and off-putting to re-implement stuff you get for free in Python and Java when you're trying to learn everything else at the same time. Some companies give you the option to use whatever you want if you're applying for an iOS position (Google), and some don't (Apple, Facebook). But either way, if you do iOS, odds are you spend 99% of your time at work writing Swift and/or Objective-C, which means you'll have to put in extra effort in learning/re-learning Python or Java.
This is especially great for string algorithm problems. Manipulating strings in Swift in an interview is a traumatic experience if you haven't drilled it repeatedly, and you rarely need to do it during Real Work if you have functional backend developers.
It's incredibly painful and off-putting to re-implement stuff you get for free in Python and Java when you're trying to learn everything else at the same time. Some companies give you the option to use whatever you want if you're applying for an iOS position (Google), and some don't (Apple, Facebook). But either way, if you do iOS, odds are you spend 99% of your time at work writing Swift and/or Objective-C, which means you'll have to put in extra effort in learning/re-learning Python or Java.
This is especially great for string algorithm problems. Manipulating strings in Swift in an interview is a traumatic experience if you haven't drilled it repeatedly, and you rarely need to do it during Real Work if you have functional backend developers.
Is Swift worth learning if you're not going to be doing Apple development?
As an iOS engineer, I'm a bit biased, but I'd still say it's currently not practical to learn it if you're not doing Apple development.
That said, I love the language, and it's a big part of what motivates me to continue being an iOS engineer (I'm not sure I'd still be at if we had kept on with Objective-C).
I would love to see server-side Swift take off, but the ecosystem is still fairly new, so any large project would require you to roll your own solutions more often that you would need to in other languages. I was also excited to see https://www.tensorflow.org/swift — Swift being used for ML. Swift is working on support for differential programming, which is a cool development in the space. More info here: https://github.com/apple/swift/blob/main/docs/Differentiable...
Perhaps eventually there will be enough applications outside of the Apple ecosystem to reach a critical mass.
That said, I love the language, and it's a big part of what motivates me to continue being an iOS engineer (I'm not sure I'd still be at if we had kept on with Objective-C).
I would love to see server-side Swift take off, but the ecosystem is still fairly new, so any large project would require you to roll your own solutions more often that you would need to in other languages. I was also excited to see https://www.tensorflow.org/swift — Swift being used for ML. Swift is working on support for differential programming, which is a cool development in the space. More info here: https://github.com/apple/swift/blob/main/docs/Differentiable...
Perhaps eventually there will be enough applications outside of the Apple ecosystem to reach a critical mass.
As a developer in non-tech enterprise, my biggest dream is probably swift being capable of targeting web and android.
We don’t have the resources to currently target all three platforms, and we don’t have much hope for google frameworks as they tend to be changed/abandoned faster than we can afford to adopt them, and we can’t really rely on Facebook tech too much because of corporate ethics (I know it don’t make much sense, but it’s non-tech enterprise, this is probably the least weird ethics rule).
I mean, it doesn’t really have to be swift, it could be python, .net or kotlin, for all I care, but it’s probably more likely to be swift.
We don’t have the resources to currently target all three platforms, and we don’t have much hope for google frameworks as they tend to be changed/abandoned faster than we can afford to adopt them, and we can’t really rely on Facebook tech too much because of corporate ethics (I know it don’t make much sense, but it’s non-tech enterprise, this is probably the least weird ethics rule).
I mean, it doesn’t really have to be swift, it could be python, .net or kotlin, for all I care, but it’s probably more likely to be swift.
Then try to see how much of it is possible as mobile Web, specially if it is just a CRUD application at heart.
Android's NDK is quite limited, its main purpose is to implement native methods for Android Java/Kotlin, outside games, there is very little you can achieve without going through JNI or Android IPC into Java land.
Android's NDK is quite limited, its main purpose is to implement native methods for Android Java/Kotlin, outside games, there is very little you can achieve without going through JNI or Android IPC into Java land.
That github differentiable programming link was an interesting read. It reminded me of interval arithmetic in the same sort of "But wait, why can't we just jam math into this program" vibe. Very neat.
I can't really see a reason to use Swift if you're not targeting Apple platforms.
I think between Nodejs, Python, Go, (and maybe Rust), I can't really see much of a compelling usecase for Swift on the server. Even if you're developing a server component for an iOS app, I don't think it really is all that common to share a core between the two.
I think between Nodejs, Python, Go, (and maybe Rust), I can't really see much of a compelling usecase for Swift on the server. Even if you're developing a server component for an iOS app, I don't think it really is all that common to share a core between the two.
Swift is faster than all three of those. Vapor is now a very elegant framework, and very easy to use if you already know swift.
I agree that it’s not a language to adopt yet if you don’t also target apple platforms. Primarily I disagree with you about it not being good if you are developing a server component for an iOS app.
I agree that it’s not a language to adopt yet if you don’t also target apple platforms. Primarily I disagree with you about it not being good if you are developing a server component for an iOS app.
I've been using Swift for over 5 years now I think.. and I would say no. Outside of the Apple ecosystem the only thing that is really of interest right now is Vapor.
It's a nice language though. I worry it's getting too complex, but the new features enable SwiftUI to work so I can't complain too much.
It's a nice language though. I worry it's getting too complex, but the new features enable SwiftUI to work so I can't complain too much.
Only if you are a language geek, and want to open you mind that C and C++ aren't the only game in town for systems programming.
Other than that, outside Apple platforms is still in a worse state than clang Objective-C + GNUStep.
Other than that, outside Apple platforms is still in a worse state than clang Objective-C + GNUStep.
No IMO, but Apple (iOS, macOS not so much) development is still an incredibly lucrative niche, and will continue to be so until the United States collapses. It might even still be useful after that.
Looks great.
But I wonder why there are platform requirements for what seems to me like pretty basic functions.
In RandomSample.swift:
2. Why release a package that does not support windows now that windows is officially supported?
In RandomSample.swift:
// For log(_:) and exp(_:)
#if canImport(Glibc)
@_implementationOnly
import Glibc
#elseif canImport(Darwin)
@_implementationOnly
import Darwin
#endif
2. Why release a package that does not support windows now that windows is officially supported?
They _are_ in Numerics (including Windows support). I think Nate is just trying to keep dependencies to a minimum, but feel free to raise an issue.
Swift blog also has enough of such examples right on the introduction.
I don't understand the hype honestly. Every modern high level language should provide these algorithms.
I tried Swift and it has some nice features, but i in my opinion it's not suited for system programming, because it has some very religious design desicions. For example:
- You can't use a for loop to loop over array elements by reference.
- Just look how to work with pointers in swift. There is nothing more to say about it. https://www.raywenderlich.com/7181017-unsafe-swift-using-poi...
A system programming language is a language in which you can write an memory allocator, or a function like dlopen(). While you can possibly do this in Swift, it would be much easier even in C.
I don't want to say swift is bad. The design desicions are ok for an application programming language.
- You can't use a for loop to loop over array elements by reference.
- Just look how to work with pointers in swift. There is nothing more to say about it. https://www.raywenderlich.com/7181017-unsafe-swift-using-poi...
A system programming language is a language in which you can write an memory allocator, or a function like dlopen(). While you can possibly do this in Swift, it would be much easier even in C.
I don't want to say swift is bad. The design desicions are ok for an application programming language.
How much of this collection had decent open source packages already available?
How much more efficient are Apple’s algorithms over what was generally accepted as the best prior open source version?
Were these algos already a standard set for Apple engineers internally?
It seems like customers win if Swift apps are more efficient and less error prone.
How much more efficient are Apple’s algorithms over what was generally accepted as the best prior open source version?
Were these algos already a standard set for Apple engineers internally?
It seems like customers win if Swift apps are more efficient and less error prone.
Nice! Similar space to https://github.com/xixixao/jfl, might steal a couple (rotation is a good one)
Worse nomenclature than any other big language I can think of, including Go and Python. Why should this package be called "algorithms"?
C++ has similar nomenclature - - the std::algorithms library has generic functions for working with collections: https://en.cppreference.com/w/cpp/algorithm
Whether C++ is a good model to follow is another question entirely, of course! But at least Swift isn’t being completely idiosyncratic in its naming choices.
Whether C++ is a good model to follow is another question entirely, of course! But at least Swift isn’t being completely idiosyncratic in its naming choices.
[deleted]
Huh? It sounds like it shouldn't be called anything BUT algorithms. It implements standard generic algorithms for various operations. The kinds you'd be asked about in an algorithmic test, learn in algorithms 101, and so on.
Of course technically any part of a program is an algorithm, but usually (like here) we reserve the name for general things like here (from path and graph to partition and search algorithms), not for our "business logic" algorithm.
Of course technically any part of a program is an algorithm, but usually (like here) we reserve the name for general things like here (from path and graph to partition and search algorithms), not for our "business logic" algorithm.
These functions are designed to be highly generic so can be used as building blocks for many other more specific algorithms while it is not specifically tied to other concepts like container or iterator. Do you have any concise alternatives that reflect these properties?
I agree this is a poor use of namespace. Python has that in itertools, Numpy has combinatorics and random sampling
in numpy.random. Maybe they just planned to stop here? Or the algorithm namespace is bound to become overcrowded.
>a new open-source package of sequence and collection algorithms, along with their related types.
This is exactly what algorithms are at the level of almost any language's included libraries. The name seems spot on.
This is exactly what algorithms are at the level of almost any language's included libraries. The name seems spot on.
Article is very nice
I've picked rust instead, it feels like the exact opposite of the single large actor supporting swift, instead it's a huge community effort with lots of use cases already being seen in many spaces. AND rust just got AVR support which I suppose swift could get pretty quickly with llvm as well