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

71–80 of 103 posts

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

#71

Post by vjeux »

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.

This is something that was a big source of discussions in the team. The state we're in so far is that we have two different classes for those two use cases.

The hashmap version of immutable maps are really useful for the "builder pattern". This is very common in product code. You create a mutable local map by slicing the inputs in many ways and freeze it at the end. We have an optimization that makes freeze a no-op if we can prove that there are no references to the variable that escape (it's true in many cases). We often talked about doing a compaction step at this point but haven't played with it.

The tree version of immutable maps are really useful when you are mutating (hmmm...) it after it escapes the function.

The problem is that the two have a very different API and complexity trade-offs. We haven't found a way to unify the two APIs and have the compiler able to pick one or the other transparently behind the scenes.

Also, one thing the language tries to have is predictable performance. Having a different complexity based on whether an optimization is kicking in or not is something that bit us many many many times on the dynamic languages we're working on (Hack, JavaScript, Python) that it is something we're trying to avoid with Skip.

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

#72

Post by mpartel »

jverlaguet wrote: post #60
mpartel wrote: post #57

This could be really useful for game development! Certain kinds of networked games are built as a model, deterministically updated by clock ticks and commands from the server, and a view layer on top of that. And even model-level objects often monitor each other for changes. Seems like a perfect fit. Game objects often have graph-like (not tree-like) dependencies though. E.g. two characters may want to move towards e…

It's definitely possible. You need to "break the cycle" by adding an additional layer. You can encode any graph as an array of objects were you replaced the pointers with indexes within the array. Of course, the granularity (how big the arrays are) is up to you, and there is a tradeoff here. The other very important thing to note is that Skip has a memory model suitable for that use case. Every function has a GC over…

So, say I have: `characters = [A, B, ...]` and I want to maintain for each character `x` the invariant: `x.target = (first y in 'characters' where y.score > x.score)`

Can Skip maintain such a self-referential invariant automatically? Does the answer depend on A and B's mutability?

(This "graph as array" escape hatch seems to come up in many language designs with compile-time pointer analysis. It's useful, maybe even essential, but you tend to lose some nice language features/guarantees with it, in my limited experience.)

The GC thing sounds excellent!

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

#73

Post by baddox »

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…

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

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

#74

Post by vjeux »

baddox wrote: post #73
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…

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

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

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

#75

Post by vjeux »

mpartel wrote: post #72
jverlaguet wrote: post #60

Earlier quoted context omitted.

It's definitely possible. You need to "break the cycle" by adding an additional layer. You can encode any graph as an array of objects were you replaced the pointers with indexes within the array. Of course, the granularity (how big the arrays are) is up to you, and there is a tradeoff here. The other very important thing to note is that Skip has a memory model suitable for that use case. Every function has a GC over…

So, say I have: `characters = [A, B, ...]` and I want to maintain for each character `x` the invariant: `x.target = (first y in 'characters' where y.score > x.score)` Can Skip maintain such a self-referential invariant automatically? Does the answer depend on A and B's mutability? (This "graph as array" escape hatch seems to come up in many language designs with compile-time pointer analysis. It's useful, maybe even…

Not responding to your question directly but I just want to mention that if you mark your class as mutable and use mutable instances, you can write code as you’d expect from other languages. The only downside is that you can’t pass those values to a memoized function unless you do a deep copy.

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

#76

Post by qwerty456127 »

SatvikBeri wrote: post #70
qwerty456127 wrote: post #48

Earlier quoted context omitted.

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…

I know this (and even use this occasionally), that's why there are whole separate families of collections in Scala - mutable and immutable collections. And I think it is possible for the compiler to figure out if a type (e.g. a collection type) is mutable or not given its source code and even if it isn't it probably can be made possible by introducing some sort of special annotations to class definitions.

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

#77

Post by qwerty456127 »

By the way, I've got a question to programming language engineers and people keeping track of emerging and experimental languages: is there a language where everything (or almost everything, excluding elementary types and structs perhaps) is an "actor" and every class method call is an asynchronous message passing? Together with an idea of a heavily-memoized language (which Skip is meant to be an implementation of) this idea won't leave my mind for years since I've first learnt about the actor model.

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

#78

Post by bitexploder »

qwerty456127 wrote: post #77

By the way, I've got a question to programming language engineers and people keeping track of emerging and experimental languages: is there a language where everything (or almost everything, excluding elementary types and structs perhaps) is an "actor" and every class method call is an asynchronous message passing? Together with an idea of a heavily-memoized language (which Skip is meant to be an implementation of) t…

Well, Obj-C used true message passing to call methods. And SmallTalk is also a True OO language in that sense. I wonder if SmallTalk isn’t a good starting point for such a language.

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

#79

Post by scroot »

qwerty456127 wrote: post #77

By the way, I've got a question to programming language engineers and people keeping track of emerging and experimental languages: is there a language where everything (or almost everything, excluding elementary types and structs perhaps) is an "actor" and every class method call is an asynchronous message passing? Together with an idea of a heavily-memoized language (which Skip is meant to be an implementation of) t…

I believe that some Smalltalkers were able to turn objects into things that were "like actors" when implementing Croquet / OpenCobalt [1]. These systems relied upon creating their own sense of "time" via a protocol named TeaTime [2]. I have tried to get more information on the actual implementation of TeaTime but have come up short so far.

[1] https://en.wikipedia.org/wiki/Croquet_Project

[2] http://www.vpri.org/pdf/tr2003001_croq_collab.pdf

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

#80

Post by jitl »

qwerty456127 wrote: post #77

By the way, I've got a question to programming language engineers and people keeping track of emerging and experimental languages: is there a language where everything (or almost everything, excluding elementary types and structs perhaps) is an "actor" and every class method call is an asynchronous message passing? Together with an idea of a heavily-memoized language (which Skip is meant to be an implementation of) t…

On the subject of actor-concurrency languages, you should check out Pony. In Pony, actors are very common, but they are not the ubiquitous data-type. Actors exist along side regular classes in the language. See https://tutorial.ponylang.io/types/actors.html
Post reply on HN