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

I'm not mutable, I'm partially instantiated

blog.dnmfarrell.com

Post reply on HN
Print view View original

31–40 of 77 posts

Re: I'm not mutable, I'm partially instantiated

#31

Post by skybrian »

anfelor wrote: post #16

Partially instantiated data structures are also available in Haskell (via Laziness), in OCaml (via tail modulo cons, https://inria.hal.science/hal-03146495/document ) and Koka (via constructor contexts, https://dl.acm.org/doi/pdf/10.1145/3656398 )

Also, you can do lazy initialization in any language that has functions by passing a getter function around instead of a value.

I recently had need for this to implement validation for recursive data structures in TypeScript. It depends on support for forward references in the body of a function. The tricky bit is ensuring that the getter isn’t called until the cycle is completed by defining the forward reference’s target. The type system doesn’t help; you just have to write the implementation so it doesn’t call the getter.

Re: I'm not mutable, I'm partially instantiated

#32

Post by skybrian »

bmacho wrote: post #27
anfelor wrote: post #16

Partially instantiated data structures are also available in Haskell (via Laziness), in OCaml (via tail modulo cons, https://inria.hal.science/hal-03146495/document ) and Koka (via constructor contexts, https://dl.acm.org/doi/pdf/10.1145/3656398 )

I don't think Haskell can do this, can have a growable linked list for example. 'last a' is 'last a', regardless what is between them (modulo shadowing and such). And I suspect that Prolog's Partial Instantiation is, while not mutating data, but it is mutating references somewhere

Haskell has cyclic data structures, which also can’t be implemented without a mutable reference somewhere, though it may be buried in the implementation.

The difference is being able to define an incomplete data structure (with a forward reference) and then defining the target of the reference at runtime. Most languages will complain about an undefined reference if it’s not defined by the end of a module.

You could do it with soft references, though. Use a symbol or string to refer to something and define it later.

Re: I'm not mutable, I'm partially instantiated

#33

Post by whateveracct »

bmacho wrote: post #27
anfelor wrote: post #16

Partially instantiated data structures are also available in Haskell (via Laziness), in OCaml (via tail modulo cons, https://inria.hal.science/hal-03146495/document ) and Koka (via constructor contexts, https://dl.acm.org/doi/pdf/10.1145/3656398 )

I don't think Haskell can do this, can have a growable linked list for example. 'last a' is 'last a', regardless what is between them (modulo shadowing and such). And I suspect that Prolog's Partial Instantiation is, while not mutating data, but it is mutating references somewhere

Technically, Haskell laziness is just mutability under the hood :)

And the "difference list" mentioned in the article is also in Haskell - although framed differently (more "functionally")

    type DList a = [a] -> [a]

    concat :: DList a -> DList a -> DList a
    concat = (.)

    toList :: DList a -> [a]
    toList d = d []

    fromList :: [a] -> DList a
    fromList = (++)

Re: I'm not mutable, I'm partially instantiated

#34

Post by colanderman »

anfelor wrote: post #16

Partially instantiated data structures are also available in Haskell (via Laziness), in OCaml (via tail modulo cons, https://inria.hal.science/hal-03146495/document ) and Koka (via constructor contexts, https://dl.acm.org/doi/pdf/10.1145/3656398 )

Laziness and TMC are fundamentally different from partial instantiation in that they are implementation details, mostly/wholly invisible to the language semantics themselves.

A key aspect of partial instantiation is that the "holes" may be filled in by a semantically unrelated piece of code, which is not the case for either laziness or TMC (wherein the contents data structure must be defined in one place, even if the implementation does not evaluate it immediately).

(I don't know Koka so I can't speak to that.)

Re: I'm not mutable, I'm partially instantiated

#35

Post by skybrian »

bedobi wrote: post #24

Partial instantiation is cool and all, but tbh I prefer just capturing the initial incomplete attributes in one complete record, pass that around, and then instantiate the real thing when you have all attributes data class IncompletePerson(val name: String) data class Person( val name: String, val email: String ) or data class Person( val initialAttributes: IncompletePerson, val email: String ) if you want to nest it…

How would you define a cyclic data structure?

Re: I'm not mutable, I'm partially instantiated

#36

Post by [deleted] »

skybrian wrote: post #32
bmacho wrote: post #27

Earlier quoted context omitted.

I don't think Haskell can do this, can have a growable linked list for example. 'last a' is 'last a', regardless what is between them (modulo shadowing and such). And I suspect that Prolog's Partial Instantiation is, while not mutating data, but it is mutating references somewhere

Haskell has cyclic data structures, which also can’t be implemented without a mutable reference somewhere, though it may be buried in the implementation. The difference is being able to define an incomplete data structure (with a forward reference) and then defining the target of the reference at runtime. Most languages will complain about an undefined reference if it’s not defined by the end of a module. You could d…

[deleted]

Re: I'm not mutable, I'm partially instantiated

#37

Post by coliveira »

wizzwizz4 wrote: post #20
openasocket wrote: post #17

I've never used it in production, but I have a deep love of Prolog, just because of how different it is from any other programming language I've used. As a programming paradigm, it found it as eye-opening as functional programming. What I found interesting is that you are operating on logical statements and pattern matching, which often means that the same "function" can be used for multiple different things. For exa…

It doesn't scale that well because integers are their own, opaque thing in Prolog, and the is predicate is unidirectional. However, there's no inherent reason this has to be the case: you can construct your own representation of the integers from the Peano axioms, and recover bidirectionality of addition. (You'll want to be using some typed variant of Prolog with the "unary tree of units" optimisation, otherwise inte…

Modern Prolog libraries have handled the issues of unidirectional integer predicates, so the old ways of handling numeric values is not relevant for most problems.

Re: I'm not mutable, I'm partially instantiated

#38

Post by lynx23 »

openasocket wrote: post #17

I've never used it in production, but I have a deep love of Prolog, just because of how different it is from any other programming language I've used. As a programming paradigm, it found it as eye-opening as functional programming. What I found interesting is that you are operating on logical statements and pattern matching, which often means that the same "function" can be used for multiple different things. For exa…

Do you have a suggestion on where to / how to start learning Prolog beyond towers-of-hanoi? Prolog is basically the last language on my list of things I want to look at, but whenever I tried, I failed to find anything practical to do/try.

Re: I'm not mutable, I'm partially instantiated

#39

Post by bmacho »

skybrian wrote: post #32
bmacho wrote: post #27

Earlier quoted context omitted.

I don't think Haskell can do this, can have a growable linked list for example. 'last a' is 'last a', regardless what is between them (modulo shadowing and such). And I suspect that Prolog's Partial Instantiation is, while not mutating data, but it is mutating references somewhere

Haskell has cyclic data structures, which also can’t be implemented without a mutable reference somewhere, though it may be buried in the implementation. The difference is being able to define an incomplete data structure (with a forward reference) and then defining the target of the reference at runtime. Most languages will complain about an undefined reference if it’s not defined by the end of a module. You could d…

I rather think the fact the the same symbol/string always denotes the same thing is especially helpful for cyclic structures.

Anyway I think I misunderstood the article, I thought they added things to a dictionary in the prolog repl, which would be impossible in haskell/ghci afaik.

Re: I'm not mutable, I'm partially instantiated

#40

Post by coliveira »

openasocket wrote: post #17

I've never used it in production, but I have a deep love of Prolog, just because of how different it is from any other programming language I've used. As a programming paradigm, it found it as eye-opening as functional programming. What I found interesting is that you are operating on logical statements and pattern matching, which often means that the same "function" can be used for multiple different things. For exa…

I always thought that pattern matching would be an excellent feature for other programming languages, but it seems that it hasn't become popular. Many strategies available to Prolog could become possible just by the addition of this feature. One possible implementation of the idea occurs with C++ templates specialized with numerical parameters. It also seems that Mathematica provides pattern matching, but I don't use that language.
Post reply on HN