Show HN: Conway's Game of Life in TypeScript's type system (opens in new tab)

(github.com)

186 pointscandleknight2y ago45 comments

TypeScript playground: https://www.typescriptlang.org/play?#code/KYDwDg9gTgLgBDAnmY...

45 comments

In the typescript playground, the best way to see the output of any evolution number is to have it autocomplete a string literal!

Uncomment one of the PGunXX types that you want to see, then below it type this:

    const boardstr: PGun10 = ``;

Then put the cursor inside the two backticks and press Control+Space for intellisense autocomplete, and press enter on the first entry there. Then intellisense will put the computed board into a string literal, looking like:

    const boardstr: PGun10 = `............................................
    ........................xx..................
    ........................x..x................
    ..........x.x...............x......xx.......
    ........x...x..xxx..........x......xx.......
    .xx.....x...................x...............
    .xx....x....x.......xx..x..x................
    ........x.......x.x..x..xx..................
    ........x...x.....xxx.......................
    ..........x.x...............................
    ............................................`;

eyelidlessness2y ago

You can also use twoslash[1] caret comments in the playground to display type representations inline, even for uninitialized/declared values, so eg something like this should work:

  declare const boardstr: PGun10
  //            ^?

1: https://www.npmjs.com/package/@typescript/twoslash

vishnumenon2y ago

Love it! Reminds me of the hilarious "Typing the technical interview" [1] and "Typescripting the technical interview" [2], a couple of my favorite blog posts of all time.

[0] https://aphyr.com/posts/342-typing-the-technical-interview

[1] https://www.richard-towers.com/2023/03/11/typescripting-the-...

epgui2y ago

I think you have an off-by-one error there!

other_herbert2y ago

Just a ui bug, the presentation layer doesn’t match the data layer

mizzao2y ago

Don't forget "Rewriting the technical interview":

https://aphyr.com/posts/353-rewriting-the-technical-intervie...

hbn2y ago

Sometimes I think I don't understand TypeScript's type system and then I see something like this and I realize I know even less than I thought

awesomeMilou2y ago

Any sufficiently capable type system will make it possible to implement a form of functional programming.

These advanced type systems are essentially a form of pre-compile time scripting to assert certain guarantees about user defined types. It's the same mechanism that makes C++ templates turing complete.

chatmasta2y ago

In the case of TypeScript, most of the magic and crazy hacks are dependent on Template Literal Types [0], which is what allows inference based on arbitrary strings. Once you have that abstraction, you can just keep adding complexity to it.

[0] https://www.typescriptlang.org/docs/handbook/2/template-lite...

prologist2y ago

Any sufficiently advanced type system is indistinguishable from Prolog.

2 more replies

bazoom422y ago

Typescript has conditional types, which means it can be used as a programming language itself. In theory you can write any arbitrary program - game of life is just an example. You have to define numbers and arithmetics from scratch though, so it is not very practical.

Conditional types are probably rarely used in practial code, but it opens the door for a lot of geekery.

ushakov2y ago

We’re using conditional types for type inference in garph (https://garph.dev)

kiechu2y ago

It is year 2035. TypeScript type system gained conscious.

franky472y ago

Considering that in 2035 all software runs on top of JavaScript [1], I'm not surprised.

[1] https://www.destroyallsoftware.com/talks/the-birth-and-death...

jhirshman2y ago

Nice work, Ruyi! You've definitely taken typescript mastery to a new level. It was great to have you intern with us.

If anyone else is interested in an internship or full-time position in typescript: https://www.uncountable.com/hiring/hn

heroku2y ago

Stop overcalculating a mess out of junk, learn Rust and see what a Typesystem should and shouldn't have to do.

brundolf2y ago

Cute :)

Any sufficiently advanced type system is indistinguishable from an interpreter!

evolveyourmind2y ago

You can also easily implement meta-languages. Eg. lambda calculus: https://github.com/desi-ivanov/ts-lambda-calc

klysm2y ago

=> turing completeness

calebegg2y ago

How do I run this/see the results? I'm a little lost.

aazo112y ago

Same here. I hit "run" but get an error

_jab2y ago

Because it's all just types, there's nothing _to_ run. Instead, you'll want to hover your cursor over the `PGunX` types at the end of the file in the playground; this will cause the TS editor to compute that type and it should display a string corresponding to the board state.

brap2y ago

At this point, TypeScript should just let us define types using plain imperative TS code that will execute during static analysis. Might as well.

type MyType<T> = someFunc(T)

Of course these functions might be typed too…

phpnode2y ago

this is exactly what I want from the Types as Comments proposal[0] as I think it's the only way that types can feasibly become part of the language. It's hard to imagine how all of the concepts TS introduces via special syntax can be covered otherwise.

[0] https://tc39.es/proposal-type-annotations

brap2y ago

I mean this seems like a nice proposal, but I guess I’m missing something, how does it relate to my comment?

1 more reply

quickthrower22y ago

That is a great idea. It also crystalizes the syntax so organisations other than MS can invest in building tooling as the target wont be as fast moving.

bafe2y ago

I recently had the insight- surely induced by reading something on HN or listening to some podcast- that types are simply functions from the set of all possible "values" to a logical value...

brap2y ago

Yeah, a type is really just a set (in the mathematical sense). And a set can be defined by a function to {0, 1}. I don’t know if this function has a formal name, byt you can think of it as a “is this value a member of the set?” function.

nimos2y ago

Ha! More performant than I'd have guessed. I tried commenting `PrintBoard<EvolveN<GosperGliderGun, 100>>` in and out and it took about 3 seconds (in the ts playground).

candleknightOP2y ago

the power of tail call optimization :)

JoeAltmaier2y ago

SO many ways.

In college I did it in assembler (a couple hundred bytes of code) on a PDP11/34 and displayed the results on an oscilloscope screen :)

koolala2y ago

It can do a Y Combinator with types can't it?

thamer2y ago

Yes: https://gist.github.com/forivall/a80d382b8c399044eb7d45d9124...

Playground: https://www.typescriptlang.org/play?#code/PTAEHkCUEkHFoHIEEA...

maxbendick2y ago

I'm happy to see people learning the Curry–Howard isomorphism the fun way.

dmalvarado2y ago

I though I knew TypeScript pretty well, but I can barely read that.

Thaxll2y ago

I'm really confused, is it what TS is supposed to looks like?

prologist2y ago

It's just a demonstration of how to encode the transition rules for Conway's game of life as a set of types, aka logical constraints. TypeScript's type system has unification, same as in Prolog, and since Prolog is basically Turing complete so is TypeScript's type system.

EMM_3862y ago

TypeScripts Type System is Turing Complete #14833

https://github.com/microsoft/TypeScript/issues/14833

thdespou2y ago

This is probably the slowest Game of Life ever.

nathanfig2y ago

I like having type hints, I really do- but I've definitely been on projects where TS began to feel a lot like a nerd snipe https://xkcd.com/356/

j / k navigate · click thread line to collapse

45 comments

dag112y ago

In the typescript playground, the best way to see the output of any evolution number is to have it autocomplete a string literal!

Uncomment one of the PGunXX types that you want to see, then below it type this:

    const boardstr: PGun10 = ``;

    const boardstr: PGun10 = `............................................
    ........................xx..................
    ........................x..x................
    ..........x.x...............x......xx.......
    ........x...x..xxx..........x......xx.......
    .xx.....x...................x...............
    .xx....x....x.......xx..x..x................
    ........x.......x.x..x..xx..................
    ........x...x.....xxx.......................
    ..........x.x...............................
    ............................................`;

eyelidlessness2y ago

You can also use twoslash[1] caret comments in the playground to display type representations inline, even for uninitialized/declared values, so eg something like this should work:

  declare const boardstr: PGun10
  //            ^?

1: https://www.npmjs.com/package/@typescript/twoslash

vishnumenon2y ago

Love it! Reminds me of the hilarious "Typing the technical interview" [1] and "Typescripting the technical interview" [2], a couple of my favorite blog posts of all time.

[0] https://aphyr.com/posts/342-typing-the-technical-interview

[1] https://www.richard-towers.com/2023/03/11/typescripting-the-...

epgui2y ago

I think you have an off-by-one error there!

other_herbert2y ago

Just a ui bug, the presentation layer doesn’t match the data layer

mizzao2y ago

Don't forget "Rewriting the technical interview":

https://aphyr.com/posts/353-rewriting-the-technical-intervie...

hbn2y ago

Sometimes I think I don't understand TypeScript's type system and then I see something like this and I realize I know even less than I thought

awesomeMilou2y ago

Any sufficiently capable type system will make it possible to implement a form of functional programming.

chatmasta2y ago

[0] https://www.typescriptlang.org/docs/handbook/2/template-lite...

prologist2y ago

Any sufficiently advanced type system is indistinguishable from Prolog.

2 more replies

bazoom422y ago

Conditional types are probably rarely used in practial code, but it opens the door for a lot of geekery.

ushakov2y ago

We’re using conditional types for type inference in garph (https://garph.dev)

kiechu2y ago

It is year 2035. TypeScript type system gained conscious.

franky472y ago

Considering that in 2035 all software runs on top of JavaScript [1], I'm not surprised.

[1] https://www.destroyallsoftware.com/talks/the-birth-and-death...

jhirshman2y ago

Nice work, Ruyi! You've definitely taken typescript mastery to a new level. It was great to have you intern with us.

If anyone else is interested in an internship or full-time position in typescript: https://www.uncountable.com/hiring/hn

heroku2y ago

Stop overcalculating a mess out of junk, learn Rust and see what a Typesystem should and shouldn't have to do.

brundolf2y ago

Cute :)

Any sufficiently advanced type system is indistinguishable from an interpreter!

evolveyourmind2y ago

You can also easily implement meta-languages. Eg. lambda calculus: https://github.com/desi-ivanov/ts-lambda-calc

klysm2y ago

=> turing completeness

calebegg2y ago

How do I run this/see the results? I'm a little lost.

aazo112y ago

Same here. I hit "run" but get an error

_jab2y ago

brap2y ago

At this point, TypeScript should just let us define types using plain imperative TS code that will execute during static analysis. Might as well.

type MyType<T> = someFunc(T)

Of course these functions might be typed too…

phpnode2y ago

[0] https://tc39.es/proposal-type-annotations

brap2y ago

I mean this seems like a nice proposal, but I guess I’m missing something, how does it relate to my comment?

1 more reply

quickthrower22y ago

That is a great idea. It also crystalizes the syntax so organisations other than MS can invest in building tooling as the target wont be as fast moving.

bafe2y ago

I recently had the insight- surely induced by reading something on HN or listening to some podcast- that types are simply functions from the set of all possible "values" to a logical value...

brap2y ago

nimos2y ago

Ha! More performant than I'd have guessed. I tried commenting `PrintBoard<EvolveN<GosperGliderGun, 100>>` in and out and it took about 3 seconds (in the ts playground).

candleknightOP2y ago

the power of tail call optimization :)

JoeAltmaier2y ago

SO many ways.

In college I did it in assembler (a couple hundred bytes of code) on a PDP11/34 and displayed the results on an oscilloscope screen :)

koolala2y ago

It can do a Y Combinator with types can't it?

thamer2y ago

Yes: https://gist.github.com/forivall/a80d382b8c399044eb7d45d9124...

Playground: https://www.typescriptlang.org/play?#code/PTAEHkCUEkHFoHIEEA...

maxbendick2y ago

I'm happy to see people learning the Curry–Howard isomorphism the fun way.