Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Skip – A programming language to skip the things you have already computed

skiplang.com

Post reply on HN
Print view View original

61–70 of 103 posts

Re: Skip – A programming language to skip the things you have already computed

#61

Post by [deleted] »

bwasti wrote: post #58
qwerty456127 wrote: post #45

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…

beyond 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 also just shared it here https://news.ycombinator.com/item?id=18080598 if you have comments

[deleted]

Re: Skip – A programming language to skip the things you have already computed

#62

Post by dom96 »

jverlaguet wrote: post #35
jasone wrote: post #31

Earlier quoted context omitted.

> Skip is not meant to be a system programming language. So the comparison with Rust for example is difficult. Can you elaborate on this comment in the context of some of the other languages listed by the grandparent (Go, Swift, Julia, Nim)? Granted, writing bare-metal operating system kernels may severely limit practical options, but I can imagine using Go, Swift, and Nim for slightly higher level "systems programmi…

Right. It really depends what one means by "system programming". I would add Java/C# and many others to that list.

I'm curious what your thoughts are on Nim. Especially seeing as we're both FB employees :)

I think you've done a really good job with Skip. I really love the incremental type-checking. It's a breath of fresh air to see a compiler created with IDEs in mind from the beginning.

Effect tracking is something that Nim also boasts so I'm curious how that works in Skip. Are there any docs/articles going into detail about this?

Re: Skip – A programming language to skip the things you have already computed

#63

Post by tnowacki »

qwerty456127 wrote: post #53
vjeux wrote: post #50

Earlier quoted context omitted.

This 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. Th…

I 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 s…

I got unflagged!

> 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?

How exactly do you expect to track this accurately without integrating it into the type system? It's not an issue of whether or not the field itself is assignable, but whether or not the type that it points to is mutable. This becomes much more difficult to determine when generics are involved. This sort of type level knowledge for generics would make it hard to staple onto an existing type system. Even if you did, you would likely end up with a lot of code duplication as you would need two forms of types, immutable and mutable, e.g. `ImmVector` and `MutVector`, `ImmMap` and `MutMap`, `ImmMyObject` and `MutMyObject`, etc. To make this more ergonomic, Skip has a mode based mutability model, where the mutability is determined not at the class declaration, but rather at the type annotation/object instantiation. So we would then have `Vector` and `mutable Vector`, two modes of the same class.

You can read more here: http://skiplang.com/blog/2018/04/10/understanding-mutability...

Re: Skip – A programming language to skip the things you have already computed

#64

Post by sagichmal »

qwerty456127 wrote: post #45

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…

> 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.

Re: Skip – A programming language to skip the things you have already computed

#65

Post by tomp »

tnowacki wrote: post #63
qwerty456127 wrote: post #53

Earlier quoted context omitted.

I 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 s…

I got unflagged! > 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? How exactly do you expect to track this accurately without integrating it into the type system? It's not an issue of whether or not the field itself is assignable, but whether or not the type that it points to is mutable. This becomes much more difficult…

Are different modes implemented differently? E.g. an immutable (but extensible) Map should be implemented as a tree, whereas mutable maps are best implemented using arrays.

Re: Skip – A programming language to skip the things you have already computed

#66

Post by PeterisP »

taneq wrote: post #49
qwerty456127 wrote: post #45

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…

> 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.

That 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.

Re: Skip – A programming language to skip the things you have already computed

#67

Post by zackmorris »

vjeux wrote: post #10
zellyn wrote: post #2

Apparently this was a research project. Anyone have links to papers, conclusions, results? Should be interesting…

We posted about some of those in the blog over the years. http://skiplang.com/blog Some of the interesting ones: - An overview of how memoization works and the MVCC model behind the scenes: http://skiplang.com/blog/2017/01/04/how-memoization-works.ht... - How pattern matching is implemented and the tricks to make goto work in JavaScript: http://skiplang.com/blog/2017/11/15/simulating-goto-in-javas... - The work done…

Thank you, I feel like Skip is very close to the language I've always wanted. Its MVCC looks very similar to Clojure's, I'm having trouble finding a good link about it:

https://sw1nn.com/blog/2012/04/11/clojure-stm-what-why-how/

The gist of it is that instead of tracking multiple separate locations in memory for values, the software transactional memory (STM) references data by value. So if you assign the value {a: 42, b: 24} to two variables x and y, that value is only stored in memory in one place that the variables both point to. Then if one of the variables changes something, for example y.b = 25, this big tree structure works like copy-on-write and makes copies of branches when mutations occur. So internally, a: 42 is one reference and b: (24 or 25) is another reference. So rather than using 4 cells of memory, we've only used 3.

This frees the developer from having to micromanage memory resources and makes a lot of other things like concurrency "just work" without locks. Do I have this correct?

Re: Skip – A programming language to skip the things you have already computed

#68

Post by vjeux »

zackmorris wrote: post #67
vjeux wrote: post #10

Earlier quoted context omitted.

We posted about some of those in the blog over the years. http://skiplang.com/blog Some of the interesting ones: - An overview of how memoization works and the MVCC model behind the scenes: http://skiplang.com/blog/2017/01/04/how-memoization-works.ht... - How pattern matching is implemented and the tricks to make goto work in JavaScript: http://skiplang.com/blog/2017/11/15/simulating-goto-in-javas... - The work done…

Thank you, I feel like Skip is very close to the language I've always wanted. Its MVCC looks very similar to Clojure's, I'm having trouble finding a good link about it: https://sw1nn.com/blog/2012/04/11/clojure-stm-what-why-how/ The gist of it is that instead of tracking multiple separate locations in memory for values, the software transactional memory (STM) references data by value. So if you assign the value {a: 4…

Your explanation looks correct!

The practical application is having a webserver that runs a bunch of requests in parallel but that can all share the same memoization cache. We don't want to lock the full memoization cache and therefore block all the other requests when one thread writes a new value.

Re: Skip – A programming language to skip the things you have already computed

#69

Post by tnowacki »

tomp wrote: post #65
tnowacki wrote: post #63

Earlier quoted context omitted.

I got unflagged! > 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? How exactly do you expect to track this accurately without integrating it into the type system? It's not an issue of whether or not the field itself is assignable, but whether or not the type that it points to is mutable. This becomes much more difficult…

Are different modes implemented differently? E.g. an immutable (but extensible) Map should be implemented as a tree, whereas mutable maps are best implemented using arrays.

No. The modes are there so that you don't need to completely switch what you are doing and do a fully copy when you need to memoize; it does not switch the underlying implementation.

Re: Skip – A programming language to skip the things you have already computed

#70

Post by SatvikBeri »

qwerty456127 wrote: post #48
vjeux wrote: post #46

Earlier quoted context omitted.

The 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 eng…

It 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?

As an example in Scala, consider:

  val buf = scala.collection.mutable.ArrayBuffer.empty[Int]
  buf += 1
is perfectly valid. You can't reassign buf to another object, but you can change the underlying object. Making something "truly" immutable when that's allowed is tricky. Apache Spark (built on top of Scala) goes a long way to try and achieve this, and is able to do a number of optimizations as a result, but IIRC there are still significant cases it isn't able to resolve.
Post reply on HN