The Garbage Collector

« first day (426 days earlier) ← previous day next day → last day (90 days later) »

Dannyu NDos

8:10 AM

Matsumoto Yukihiro's How To Make A Programming Language

2 hours later…

Eldritch Conundrum

10:02 AM

step #1: learn japanese

1 hour later…

Dannyu NDos

11:16 AM

@EldritchConundrum This is a Korean translation tho.

4 hours later…

RubenVerg

2:48 PM

i'm looking for introductory info on type inference

i know nothing about it

are there different styles? approaches?

which one is best for beginners?

i can write some code examples if it helps figure out the best suggestion but idk what features i particularly want

i just know that ideally i'd want 0 type annotations in my code

(making a golflang, explicit type annotations would be dumb)

(and yes, static typing as a whole in golflangs might be dumb, but i want to try out something new)

there's also some kind of prior art

this feels like the right place to ask, no?

RubenVerg

3:30 PM

hmm, if i can do all that i want to do the type inference might need to be a bit complex

i'll make an example

ratchet freak

the most basic of type inference comes from a+b where both a and b are integers, means that the result of the add is also an integer.

then recurse up the AST

RubenVerg

f := overload {
  { length }
  { + }
}
// f : (A | list[A] -- number ; number number -- number)
// or something like that, not sure how it'd work with hyperization
// + is hyperized

g := { dup f }
// g : (A | list[A] -- list[A] number ; number -- number)

ratchet freak

the neat part is that you can then do auto a = b; and use b's type to decide a's type

RubenVerg

@ratchetfreak forgot to mention it's a stacklang

so it's pretty much 100% tacit

ratchet freak

so you need to keep track of what's on the stack as you evaluate things

that's basically doing a dry run but instead of values on the stack you have their types on the stack

RubenVerg

3:37 PM

is that not typechecking?

that's how i've always done typechecking for stack languages

but can't see how it'd work for inference

ratchet freak

wouldn't you need to do that for type inference as well

you need to know the type at the inference point

then infer

RubenVerg

not sure i understand, sorry

ratchet freak

type inference happens when you infer a type based on other information rather than and explicit declarations,

so the first step is to propagate the known type information until you need to do an inference

RubenVerg

could you make an example of how that'd go with my code?

i hope the syntax is clear enough

ratchet freak

4:03 PM

depends on what exact semantics you want for overloads, but it might be

when you see an overloaded function check the top of the stack against the first argument of all functions in the overload set. filter out any that don't have a valid implicit conversion.

Then check the next argument etc.

if any function in the set runs out of arguments it's a possible overload

if you have multiple overloads then the program is ambiguous and you'll need to decide how to handle that

RubenVerg

no, but I want to know the type of g statically, not just when it's inlined in code

how does the interpreter/LSP/whatever infer the last commented line?

ratchet freak

4:18 PM

for that you can do the same but with a wildcard stack

if you match against a wildcard you keep all function in the overload set

then the stack state after g is duplicated for each function in the overload set

if you then hit another overload you do the same each stack state is matched against every function in the overload set

Eldritch Conundrum

4:31 PM

@RubenVerg for a golflang and inferring as much as possible... Maybe Hindley-Milner type inference would be good

RubenVerg

will look into it

know of good resources about it?

Seggan

@RubenVerg i suggest looking at how Factor does stack inference

2 hours later…

Michael Homer

6:17 PM

@RubenVerg Stack operations are symmetrical, so for inference this runs backwards, with f outputting its inputs to the stack, inference splitting into two branches at this point, dup consuming two values and producing one, and everything disjoined again at the end

You can end up with very complicated inference evaluations this way though, it’s much harder to type these than you’d expect

RubenVerg

6:42 PM

so maybe the type system I have in mind is too complex?

at least for a first attempt at type inference

New Posts

7:06 PM

Q: What are the ways compilers recognize complex patterns?

This answer is an example of a compiler recognizing that a complex expression is equivalent to a single operation: uint8_t pcnt64(uint64_t n) { n = n - ((n >> 1) & 0x5555555555555555ULL); n = (n & 0x3333333333333333ULL) + (n >> 2 & 0x3333333333333333ULL); n = (n + (n >> 4)) & 0xF0F0F...

Michael Homer

7:30 PM

If it’s your first type inference system I probably wouldn’t start out with overloading

Just regular direct inference is enough to handle to start with

Kitten is probably a good example of actual static typing in a concatenation language that you can refer to, I think it’s all written in Haskell

RubenVerg

@MichaelHomer i'd agree but it feels like an important feature for a golflang

maybe it's not and it's just the kind i'm used to

i don't even really want to do a strictly golflang

just a golf-inspired language

"lots of weird builtins" and "a short version that takes up less bytes" might be enough to satisfy me

except the way to combine those two is overloads

@MichaelHomer i'll look into that, thanks!

@MichaelHomer are concatenative langs a superset of stack langs? not super familiar with the terminology

Michael Homer

@RubenVerg You can overload at use site when you have a concrete stack created in the left with no issue, it’s just in abstractions when you don’t have ground truth to work from that it’s very complex

@RubenVerg “Concatenative” is a term originating in Joy, I think, to emphasise the compositional nature over implementation details. Strictly neither is a superset of the other but in practice mostly yes

It’s the “concatenating the code of two functions composes the functions” property

RubenVerg

8:26 PM

@MichaelHomer wouldn't that mean that all lambdas need to be typed?

even just length : (A | list[A] -- number ; string -- number) and then { length } would need to be typed

Michael Homer

8:39 PM

Yes, function types are where type inference gets much harder

So I'd suggest that the first type inference system you make probably shouldn't have first-class function values, then try one with HM inference after you've done that, and then overloading after that

RubenVerg

9:06 PM

alright thanks for the help!

2 hours later…

Eldritch Conundrum

11:18 PM

@NewPosts aw... I did not find the peephole one... I searched for 0x5555555555555555, but if I had searched for 0x55555555, I would have found it.

« first day (426 days earlier) ← previous day next day → last day (90 days later) »

all rooms