9 ms·
Just introduce a syntax to define immutable variables (e.g. like "val" in Scala) and to mark particular functions as pure (easy to implement manually as a decor
by qwerty456127 8y ago
Just introduce a syntax to define immutable variables (e.g. like "val" in Scala) and to mark particular functions as pure (easy to implement manually as a decorator in Python, I've been using it a lot) and memoization becomes a seemingly easy task. Why a new language?
By the way it seems very sad to me that the majority of imperative and hybrid (functional×imperative) languages lack syntax for immutable variables: in just so many cases I introduce a variable to store an intermediate result of an operation an don't mean to re-assign it ever after, it's nice of a developer to define this intention explicitly and of a compiler to raise an error when the variable is re-assigned accidentally - this simple feature is among the reasons why Scala programs usually are comparably easy to debug and run as expected as soon as they get compiled successfully.
- vjeux 8y agoThe problem that the language is trying to solve is essentially building safe caches. Once a value is in the cache it cannot be changed from inside the program (the solution we opted for is to make it deeply immutable) and externally (if it depends on some external data, we need to invalidate the cache when it changes). The big challenge is how do you maintain those guarantees while having a language that product engineers would want to write in. You can decide to not allow mutability in your language but developers need to think about code in a very very different way than what they do now. It’s also going to be challenging to convert/translate existing codebases and patterns to it. So we decided to allow both mutability and immutability. But it poses very interesting challenges. For example in the standard library, what is the type of x.map(y -> z). Which pieces are mutable or immutable. If you are not precise enough in your type system, then you are going to type it as “i don’t know (readonly)” or “mutable” but then you can’t pass the result of this to a memoized function, so you lost the point of the language. The other interesting aspect is that the backend relies on the fact that the invariant are true in order to output optimized code and garbage collector. So we cannot “cheat” like many gradual typed languages like Hack, TypeScript, C# where they can just say, actually this type is wrong but i’m just going to ignore it and it’ll throw an exception at runtime if the programmer got it wrong. It would segfault in Skip case.
- qwerty456127 8y agoIt feels like I didn't really get it given your explanation as I still can't understand why doesn't Scala (as a language, I know its actual compiler doesn't handle memoization on itself and won't remember the exact type in many cases (see "type erasure") actually) suit these needs?
- vjeux 8y agoThis goes far beyond having a local variables being assigned (assuming you mean the local being assigned and not mutating the object assigned to the local). For Skip to have to know that the actual instance is immutable, and that no one has a reference to a mutable version of that instance. If the inputs/outputs change after the memoization, we cannot guarantee the correctness of the reactivity/cache-invalidation. Thus for memoizing the inputs/outputs to a function, we need to know that the object, and any of its fields, will never be modified. In other words, we need to know if the object is transitively immutable. In order to get this sort of analysis, you need the type system to provide the information, and it is not enough to have a simple local analysis. [[This was written by Todd Nowacki but his new HN account has been flagged as commenting too fast...]]
- qwerty456127 8y agoI understand this, but can't an object be considered immutable when all its fields are immutable and all its member functions (but the constructor perhaps) are pure? And isn't this what C# structs (and Scala case classes although both can be equipped with mutable fields and impure methods if the developer wants but this isn't a recommended pattern) are meant to be? If this doesn't solve the problem then what is the solution proposed? PS: Whatever, it pleases me that somebody has finally come to the idea of a heavily-memoized language that would still support mutable imperative parts and tried implementing it. I've been thinking "why the eck there is no language that would memoize pure functions automatically" for so many years already (but I've always been dismising the idea of building it myself as I lack sufficient background in computer science to build a compiler that would produce reasonably fast programs so it would be impractical to invest time). The only language I've found easy to add automatic memoization to is Python. PPS: That's a pity Todd Nowacki has been flagged, HN should really learn to distinguish between garbage fast commenters and qualified resourceful writers.
- vjeux 8y agoThe ! syntax is really cosmetic, we could have gone the let/const route. The bigger aspect is deep immutability. Most languages implement memoize by doing pointer equality and have a notion of shallow immutability. But if someone mutates some value deep down in the object, then they’re fine with it. The other approach is to do deep copies but it’s very expensive in practice.
- int_19h 8y agoThe other other approach is to make references explicit in the syntax, so that it is possible to say things like "this is an immutable reference for a mutable object" and "this is a mutable reference for an immutable object". Because sometimes I really do want shallow mutability, and sometimes I want something even more complicated than that (e.g. deep to a certain level and then shallow, or vice versa). Kinda like C++'s const, except that's actually "readonly" (which is also handy to have!), while what we really need is "immutable". Or rather make immutable the default, and then "readonly" and "mutable" have to be explicit everywhere.
- taneq 8y ago> and run as expected as soon as they get compiled successfully If a non-trivial program runs as expected on the first try I get really suspicious.
- qwerty456127 8y agoSo did I, the first Scala experience was shockingly pleasant (I indeed "couldn't believe my eyes" and literally thought "that's so weird, it probably works just so wrong that it results in an illusion of working right", it felt like magic and this way frightening): it either fails at compile time (throwing very informative error messages some of which can be unintuitive and seem weird as long as you don't know what do they mean but let you identify a problem easily as soon as you learn to read them) or just does what you meant it to do. But the programs I've written can indeed be considered trivial - I didn't make any serious use of actors or weird types, I mostly used it as "a better C#" + humble amount of FP but it seems to me that this makes my point make even more sense - write almost the same program in a very similar style in 2 languages and one of them requires a way less debugging.
- taneq 8y agoThe hardest part of software development is figuring out exactly what you mean it to do, though. Making a program that runs without crashing and does something is relatively easy.
- PeterisP 8y agoThat tends to happen with very strict type systems; in my earlier experience with Haskell usually non-trivial programs got correct results on the first try; though they not always had the expected time or space complexity on the first try.
- Recursing 8y ago> implement manually as a decorator in Python Why don't you just use the functools.lru_cache decorator in the standard library?
- qwerty456127 8y agoIt seems I couldn't find it by googling "python memoization" when I've initially come to the point where memoization has become a necessity for me. I've found some custom solutions and built my own inspired by them but suiting my needs better (e.g. memoize to a database + cache in the memory). I'll take a look at functools.lru_cache and consider migrating to it in the cases where I don't need persistent memoization of big datasets, it's always better to use a standard solution when it's enough, thanks.
- bwasti 8y agobeyond memoization you can do cool stuff with scheduling if you annotate pure functions and execute lazily. I actually mocked this up a little while back https://github.com/bwasti/lazy https://github.com/bwasti/lazy also just shared it here https://news.ycombinator.com/item?id=18080598 https://news.ycombinator.com/item?id=18080598 if you have comments
- deleted 8y ago[deleted]
- sagichmal 8y ago> Scala programs usually are comparably easy to debug and run as expected as soon as they get compiled successfully. I am quite frankly speechless that anyone could hold this opinion.
- baddox 8y agoDon’t you also need the requirement that inputs with the “same value” will have the same references? Just because a string is immutable doesn’t mean that two “identical” strings will have the same reference, which is something you would want for a memoized function.
- vjeux 8y agoSkip has a concept of a "intern heap" that contains all the values that are going to be used for memoization. By default everything is allocated on the stack/heap. When you want to memoize a function, then we move all the arguments to the intern heap which makes structurally equal values have the same pointer. Then we can figure out quickly if two immutable values are equal. We have an intern() function that lets you move a value to the intern heap manually. We are also thinking about adding a field for objects such that once it is interned somewhere, if you intern it again, it's a no-op and we use the pointer in the object. This would avoid accidentally increasing the complexity of an algorithm by repeatedly interning the same value.
- Fiahil 8y ago> Scala programs usually are comparably easy to debug and run as expected as soon as they get compiled successfully. I wholeheartedly disagree. Scala is among the most difficult languages to master. From experience, a successful compilation do not shield you from bugs and runtime exceptions. NullPointerException being my favourite, as a reminder that lots of libraries are built on top of Java's ecosystem, and thus plagued with the same curse. And even if you're toying with pure Scala code, without any dependencies, it's still possible to end up in a state where the given traceback would be absolutely useless and full of (Anonymous) calls. Good luck with that.