Naivní závislostní typ (úvaha)

Re:Naivní závislostní typ (úvaha)
« Odpověď #45 kdy: 15. 11. 2019, 19:32:41 »
Tohle je fakt non-issue
Jestli ti pole integerů zabírá 32G nebo 64G úplně non-issue není :)


Idris

  • *****
  • 2 286
    • Zobrazit profil
    • E-mail
Re:Naivní závislostní typ (úvaha)
« Odpověď #46 kdy: 15. 11. 2019, 19:33:50 »
Tohle je fakt non-issue
Jestli ti pole integerů zabírá 32G nebo 64G úplně non-issue není :)
Mám RAM 128GB :P

BoneFlute

  • *****
  • 2 047
    • Zobrazit profil
Re:Naivní závislostní typ (úvaha)
« Odpověď #47 kdy: 15. 11. 2019, 19:38:57 »
Překladač tohle za tebe řešit nemůže, protože k tomu dochází až v runtime. (Překladač nemůže tušit, že při běhu bude ausgerechnet třetí prvek pole Age a ne Int).
Tohle už jsi kdysi kdesi tvrdil, a já s tebou v tomto stále nesouhlasím. Žádný runtime, a překladač to může zajistit. Viz ten kód.
On myslí, že když máš instanci List<Int> a žádné další informace, tak jen za běhu můžeš zjistit, že nějaký prvek je třeba typu Age (nebo prostě nějakého podtypu). To je ten základní důvod pro existenci virtuálních metod. Zmíněné aserce v Go jsou vlastně jen (konceptuálně) dynamic_cast.

Já mu snad rozumím dobře, ale stejně nesouhlasím :-)

Mám instnaci List<Int> a pokud mohu do List<Int> uložit Age, kterýžto je subtyp Int, tak si sice musím někde evidovat, že zrovna tato třetí hodnota není Int, ale Age, to jako jo, a to asi bude muset být nějak naimplementováno...

Každopádně překladač a nikoliv runtime mi zajistí, abych nemohl k těm prvkům List<Int> přistupovat jen jako k Age, a že k nim mohu přistupovat (po patřičném switchi) jako Age, a nemůžu jako k String.

Můj cíl je vždycky compile time, i za cenu složitější práce překladače. A v tomto případě bych řekl, že to stále jde.
« Poslední změna: 15. 11. 2019, 19:40:45 od BoneFlute »

Idris

  • *****
  • 2 286
    • Zobrazit profil
    • E-mail
Re:Naivní závislostní typ (úvaha)
« Odpověď #48 kdy: 15. 11. 2019, 19:46:04 »
Můj cíl je vždycky compile time, i za cenu složitější práce překladače.
Jo, to je jediná rozumná cesta. Akorát třeba v Agdě pak kompilace trvá třeba dva dny. A když pak na tebe vyskočí "sorry vole error," tak to nepotěší.

Jinak nedávno mě málem vypískali, když jsem na přednášce při výkladu potřetí před vysvětlením příkladu řekl "let's take any language, say, Agda." Hulváti...

BoneFlute

  • *****
  • 2 047
    • Zobrazit profil
Re:Naivní závislostní typ (úvaha)
« Odpověď #49 kdy: 15. 11. 2019, 19:49:46 »
Můj cíl je vždycky compile time, i za cenu složitější práce překladače.
Jo, to je jediná rozumná cesta. Akorát třeba v Agdě pak kompilace trvá třeba dva dny. A když pak na tebe vyskočí "sorry vole error," tak to nepotěší.

Jinak nedávno mě málem vypískali, když jsem na přednášce při výkladu potřetí před vysvětlením příkladu řekl "let's take any language, say, Agda." Hulváti...

:-D


BoneFlute

  • *****
  • 2 047
    • Zobrazit profil
Re:Naivní závislostní typ (úvaha)
« Odpověď #50 kdy: 15. 11. 2019, 19:52:56 »
Ne ne, bylo by to div : Numeric -> (y:Numeric) -> Not (y=0) -> Numeric . V těchto jazycích jakákoliv hodnota typu se bere jako důkaz platnosti formule odpovídající tomu typu (Curry-Howard). S tou rovností to je trik, že když předám příslušnou hodnotu ("důkaz"), můžu tu funkci zavolat a mám zaručenou nenulovost. Jinak kód vůbec nepřeložím. Fakt si místo Not (y=0) vezmi NonZero y. Tento typ má konstruktor MkNonZero (S n). No a teď si zkus s tímto zavolat div na nulu ;) Tady je vidět, že to není (u takto jednoduchých příkladů) žádná věda, zvlášť když ten důkaz musíš dodat sám. Síla záv. typů je jen a pouze v tom, co za tebe dosadí ("odvodí") překladač automaticky.
Jak by vypadalo volání funkce div když by měla závislostní typy?

Kód: [Vybrat]
div :: Numeric -> (y:Numeric) -> Not (y=0) -> Numeric
div a b = a / b

calculate :: Numeric -> Numeric -> Numeric
calculate a b =
    (div a b) + 1

calculate 10 0

Má to tři argumenty, ale volám (volal bych) to jen se dvěma.
No to nejde, musíš zavolat div a b proof.

Mohl by jsi mi prosím ten můj "zdroják" upravit, jak by to vypadalo? A kde že vezme tu proof?

Idris

  • *****
  • 2 286
    • Zobrazit profil
    • E-mail
Re:Naivní závislostní typ (úvaha)
« Odpověď #51 kdy: 15. 11. 2019, 20:07:28 »
Ne ne, bylo by to div : Numeric -> (y:Numeric) -> Not (y=0) -> Numeric . V těchto jazycích jakákoliv hodnota typu se bere jako důkaz platnosti formule odpovídající tomu typu (Curry-Howard). S tou rovností to je trik, že když předám příslušnou hodnotu ("důkaz"), můžu tu funkci zavolat a mám zaručenou nenulovost. Jinak kód vůbec nepřeložím. Fakt si místo Not (y=0) vezmi NonZero y. Tento typ má konstruktor MkNonZero (S n). No a teď si zkus s tímto zavolat div na nulu ;) Tady je vidět, že to není (u takto jednoduchých příkladů) žádná věda, zvlášť když ten důkaz musíš dodat sám. Síla záv. typů je jen a pouze v tom, co za tebe dosadí ("odvodí") překladač automaticky.
Jak by vypadalo volání funkce div když by měla závislostní typy?

Kód: [Vybrat]
div :: Numeric -> (y:Numeric) -> Not (y=0) -> Numeric
div a b = a / b

calculate :: Numeric -> Numeric -> Numeric
calculate a b =
    (div a b) + 1

calculate 10 0

Má to tři argumenty, ale volám (volal bych) to jen se dvěma.
No to nejde, musíš zavolat div a b proof.

Mohl by jsi mi prosím ten můj "zdroják" upravit, jak by to vypadalo? A kde že vezme tu proof?
Sorry, teď musím pryč, ale vrátím se k tomu ;)

To proof, pokud nemáš dostatečně inteligentní překladač, musíš dodat sám ;)

Idris

  • *****
  • 2 286
    • Zobrazit profil
    • E-mail
Re:Naivní závislostní typ (úvaha)
« Odpověď #52 kdy: 15. 11. 2019, 21:49:38 »
Ne ne, bylo by to div : Numeric -> (y:Numeric) -> Not (y=0) -> Numeric . V těchto jazycích jakákoliv hodnota typu se bere jako důkaz platnosti formule odpovídající tomu typu (Curry-Howard). S tou rovností to je trik, že když předám příslušnou hodnotu ("důkaz"), můžu tu funkci zavolat a mám zaručenou nenulovost. Jinak kód vůbec nepřeložím. Fakt si místo Not (y=0) vezmi NonZero y. Tento typ má konstruktor MkNonZero (S n). No a teď si zkus s tímto zavolat div na nulu ;) Tady je vidět, že to není (u takto jednoduchých příkladů) žádná věda, zvlášť když ten důkaz musíš dodat sám. Síla záv. typů je jen a pouze v tom, co za tebe dosadí ("odvodí") překladač automaticky.
Jak by vypadalo volání funkce div když by měla závislostní typy?

Kód: [Vybrat]
div :: Numeric -> (y:Numeric) -> Not (y=0) -> Numeric
div a b = a / b

calculate :: Numeric -> Numeric -> Numeric
calculate a b =
    (div a b) + 1

calculate 10 0

Má to tři argumenty, ale volám (volal bych) to jen se dvěma.
No to nejde, musíš zavolat div a b proof.

Mohl by jsi mi prosím ten můj "zdroják" upravit, jak by to vypadalo?
Jak na to koukám, tak tam není moc co upravovat, prostě musíš zavolat div a b (MkNonZero (prec b)), kde prec: (Succ n) ↦ n. Teď z hlavy nevím, jak přesně to řeší sofistikovanější jazyky, podívám se.

BoneFlute

  • *****
  • 2 047
    • Zobrazit profil
Re:Naivní závislostní typ (úvaha)
« Odpověď #53 kdy: 15. 11. 2019, 22:30:22 »
Ne ne, bylo by to div : Numeric -> (y:Numeric) -> Not (y=0) -> Numeric . V těchto jazycích jakákoliv hodnota typu se bere jako důkaz platnosti formule odpovídající tomu typu (Curry-Howard). S tou rovností to je trik, že když předám příslušnou hodnotu ("důkaz"), můžu tu funkci zavolat a mám zaručenou nenulovost. Jinak kód vůbec nepřeložím. Fakt si místo Not (y=0) vezmi NonZero y. Tento typ má konstruktor MkNonZero (S n). No a teď si zkus s tímto zavolat div na nulu ;) Tady je vidět, že to není (u takto jednoduchých příkladů) žádná věda, zvlášť když ten důkaz musíš dodat sám. Síla záv. typů je jen a pouze v tom, co za tebe dosadí ("odvodí") překladač automaticky.
Jak by vypadalo volání funkce div když by měla závislostní typy?

Kód: [Vybrat]
div :: Numeric -> (y:Numeric) -> Not (y=0) -> Numeric
div a b = a / b

calculate :: Numeric -> Numeric -> Numeric
calculate a b =
    (div a b) + 1

calculate 10 0

Má to tři argumenty, ale volám (volal bych) to jen se dvěma.
No to nejde, musíš zavolat div a b proof.

Mohl by jsi mi prosím ten můj "zdroják" upravit, jak by to vypadalo?
Jak na to koukám, tak tam není moc co upravovat, prostě musíš zavolat div a b (MkNonZero (prec b)), kde prec: (Succ n) ↦ n. Teď z hlavy nevím, jak přesně to řeší sofistikovanější jazyky, podívám se.

Tobě se to mluví, ty tomu už rozumíš. Já ještě furt ne.

Kód: [Vybrat]
prec :: (Succ n) -> n
prec a = ...

div :: Numeric -> (y:Numeric) -> Not (y=0) -> Numeric
div a b = a / b

calculate :: Numeric -> Numeric -> Numeric
calculate a b =
    (div a b (MkNonZero (prec b))) + 1

calculate 10 0

Tak, teď už vím, jak se to volá, ale teď zase nevím co je prec, uff.

Když se na to podívám, tak mi ten můj "způsob" přijde jednodužší. Takže předpokládám, že v těch dep. typech musí být něco víc.

Idris

  • *****
  • 2 286
    • Zobrazit profil
    • E-mail
Re:Naivní závislostní typ (úvaha)
« Odpověď #54 kdy: 15. 11. 2019, 22:46:49 »
Ne ne, bylo by to div : Numeric -> (y:Numeric) -> Not (y=0) -> Numeric . V těchto jazycích jakákoliv hodnota typu se bere jako důkaz platnosti formule odpovídající tomu typu (Curry-Howard). S tou rovností to je trik, že když předám příslušnou hodnotu ("důkaz"), můžu tu funkci zavolat a mám zaručenou nenulovost. Jinak kód vůbec nepřeložím. Fakt si místo Not (y=0) vezmi NonZero y. Tento typ má konstruktor MkNonZero (S n). No a teď si zkus s tímto zavolat div na nulu ;) Tady je vidět, že to není (u takto jednoduchých příkladů) žádná věda, zvlášť když ten důkaz musíš dodat sám. Síla záv. typů je jen a pouze v tom, co za tebe dosadí ("odvodí") překladač automaticky.
Jak by vypadalo volání funkce div když by měla závislostní typy?

Kód: [Vybrat]
div :: Numeric -> (y:Numeric) -> Not (y=0) -> Numeric
div a b = a / b

calculate :: Numeric -> Numeric -> Numeric
calculate a b =
    (div a b) + 1

calculate 10 0

Má to tři argumenty, ale volám (volal bych) to jen se dvěma.
No to nejde, musíš zavolat div a b proof.

Mohl by jsi mi prosím ten můj "zdroják" upravit, jak by to vypadalo?
Jak na to koukám, tak tam není moc co upravovat, prostě musíš zavolat div a b (MkNonZero (prec b)), kde prec: (Succ n) ↦ n. Teď z hlavy nevím, jak přesně to řeší sofistikovanější jazyky, podívám se.

Tobě se to mluví, ty tomu už rozumíš. Já ještě furt ne.

Kód: [Vybrat]
prec :: (Succ n) -> n
prec a = ...

div :: Numeric -> (y:Numeric) -> Not (y=0) -> Numeric
div a b = a / b

calculate :: Numeric -> Numeric -> Numeric
calculate a b =
    (div a b (MkNonZero (prec b))) + 1

calculate 10 0

Tak, teď už vím, jak se to volá, ale teď zase nevím co je prec, uff.

Když se na to podívám, tak mi ten můj "způsob" přijde jednodužší. Takže předpokládám, že v těch dep. typech musí být něco víc.
To fakt není nejjednodušší příklad na naučení. Lepší je možná začít třeba s typem pro sudá přirozená čísla nebo tak něco.

BoneFlute

  • *****
  • 2 047
    • Zobrazit profil
Re:Naivní závislostní typ (úvaha)
« Odpověď #55 kdy: 15. 11. 2019, 23:41:25 »
To fakt není nejjednodušší příklad na naučení. Lepší je možná začít třeba s typem pro sudá přirozená čísla nebo tak něco.

Jsem pro.

Kód: [Vybrat]
type Even = 2, 4, 6, ...

inc :: Even -> Number
inc b = a + 1

calculate :: Number -> Number -> Number

-- nepřeloží se
calculate a b = (inc b) + a

-- přeloží se
calculate a b = (inc (toEvenOr b 2)) + a
  where
    toEvenOr a default = ...

Jak by se to dělalo pomocí dep. types, prosím?

Re:Naivní závislostní typ (úvaha)
« Odpověď #56 kdy: 16. 11. 2019, 00:00:41 »
Mám RAM 128GB :P
V tom případě tě bude zajímat, jestli pole Intů zabírá 128G  nebo 256G ;)

Já mu snad rozumím dobře, ale stejně nesouhlasím :-)

Mám instnaci List<Int> a pokud mohu do List<Int> uložit Age, kterýžto je subtyp Int, tak si sice musím někde evidovat, že zrovna tato třetí hodnota není Int, ale Age, to jako jo, a to asi bude muset být nějak naimplementováno...

Každopádně překladač a nikoliv runtime mi zajistí, abych nemohl k těm prvkům List<Int> přistupovat jen jako k Age, a že k nim mohu přistupovat (po patřičném switchi) jako Age, a nemůžu jako k String.

Můj cíl je vždycky compile time, i za cenu složitější práce překladače. A v tomto případě bych řekl, že to stále jde.
Pak mi rozumíš docela přesně a moc není, s čím bys mohl nesouhlasit :) Prostě místo pole intů budeš mít pole dvojic (typ, hodnota), kde "typ" říká, jestli na tom konkrétním místě v poli je Int nebo Age (nebo nějaký jiný podtyp) a "hodnota" je ta integerová hodnota. Snadno si to naimplementuješ v Haskellu pomocí dvojic ("product type" - nevím, jak se tomu říká česky). A zároveň si po tom, co to takhle naimplementuješ, vyžereš všechny ty nevýhody :) Stačí nadefinovat pro takový typ funkce třídy Num a jsi skoro tam, kdes chtěl být, ne?

BoneFlute

  • *****
  • 2 047
    • Zobrazit profil
Re:Naivní závislostní typ (úvaha)
« Odpověď #57 kdy: 16. 11. 2019, 00:13:16 »
Pak mi rozumíš docela přesně a moc není, s čím bys mohl nesouhlasit :) Prostě místo pole intů budeš mít pole dvojic (typ, hodnota), kde "typ" říká, jestli na tom konkrétním místě v poli je Int nebo Age (nebo nějaký jiný podtyp) a "hodnota" je ta integerová hodnota. Snadno si to naimplementuješ v Haskellu pomocí dvojic ("product type" - nevím, jak se tomu říká česky). A zároveň si po tom, co to takhle naimplementuješ, vyžereš všechny ty nevýhody :) Stačí nadefinovat pro takový typ funkce třídy Num a jsi skoro tam, kdes chtěl být, ne?
No jasně. Tak já v prvé řadě nebudu dělat pole dvojic, ale zadrátuju to do toho typového systému.

A v druhé řadě, nesouhlasil jsem s tím, že by mi to typovej systém neohlídal compile time. Proč by nemohl. Všechny informace má.

Re:Naivní závislostní typ (úvaha)
« Odpověď #58 kdy: 16. 11. 2019, 00:16:59 »
A v druhé řadě, nesouhlasil jsem s tím, že by mi to typovej systém neohlídal compile time. Proč by nemohl. Všechny informace má.
No, Idris ti to už napsal: máš pole Intů, nic víc nevíš. Třeba jsi ho načetl serializované z disku nebo ze sítě. V compile time víš jenom, že to je pole intů. Teprve až to načteš z toho disku, můžeš zjistit, že třetí, pátý a sedmdesátý osmý je Age :)

BoneFlute

  • *****
  • 2 047
    • Zobrazit profil
Re:Naivní závislostní typ (úvaha)
« Odpověď #59 kdy: 16. 11. 2019, 00:22:57 »
A v druhé řadě, nesouhlasil jsem s tím, že by mi to typovej systém neohlídal compile time. Proč by nemohl. Všechny informace má.
No, Idris ti to už napsal: máš pole Intů, nic víc nevíš. Třeba jsi ho načetl serializované z disku nebo ze sítě. V compile time víš jenom, že to je pole intů. Teprve až to načteš z toho disku, můžeš zjistit, že třetí, pátý a sedmdesátý osmý je Age :)

Hele, mám pocit, že tady někdo něco přeskočil. Právě na tomhle scénáři jsem to přeci vysvětloval.

Zkusil jsem uvést příklad, popsal jsem skoro komplet kód, popsal jsem to na několik způsobů. Víc po mě už chtít nemůžeš. Asi bych pasáž, compiletime versus runtime vypustil.

A budu se těšit, jestli mi Idris řekne něco k těm sudejm číslům.
« Poslední změna: 16. 11. 2019, 00:24:45 od BoneFlute »