Organizace Apache Software Foundation (ASF) vydala verzi 18 integrovaného vývojového prostředí a vývojové platformy napsané v Javě NetBeans (Wikipedie). Přehled novinek na GitHubu. Instalovat lze také ze Snapcraftu a Flathubu.
Byla vydána verze 1.70.0 programovacího jazyka Rust (Wikipedie). Podrobnosti v poznámkách k vydání. Vyzkoušet Rust lze například na stránce Rust by Example. Jako reakce na rostoucí obavy z vlivu korporací na vývoj Rustu a předložený návrh restriktivních zásad používání ochranných známek Rustu, byl nedávno představen komunitní fork Rustu se 100 % méně byrokracie: Crab (CrabLang).
Oliver Smith z Canonicalu shrnuje základní vlastnosti „neměnné“ distribuce Ubuntu Core také ve srovnání s protějšky Chrome OS, Fedora Silverblue a MicroOS. Canonical připravuje desktopovou variantu Ubuntu Core vedle dosavadní serverové/embedded.
Z aktualizovaného seznamu chyb (pdf) procesoru AMD EPYC 7002: #1474 - procesor se po 1044 dnech od posledního resetu zasekne [reddit].
Fossil (Wikipedie) byl vydán ve verzi 2.22. Jedná se o distribuovaný systém správy verzí propojený se správou chyb, wiki stránek a blogů s integrovaným webovým rozhraním. Vše běží z jednoho jediného spustitelného souboru a uloženo je v SQLite databázi.
David Malcolm se ve svém příspěvku na blogu vývojářů Red Hatu rozepsal o vylepšeních statické analýzy (volba -fanalyzer) v GCC 13.
Byla vydána nová stabilní verze 23.05 linuxové distribuce NixOS (Wikipedie). Její kódové označení je Stoat. Podrobný přehled novinek v poznámkách k vydání. O balíčky se v NixOS stará správce balíčků Nix.
Příspěvek na blogu CZ.NIC upozorňuje na nový útok na weby v Česku. Na honeypotech na Turrisech byla zaznamenána nová aktivita útočníků - probíhající útok na FTP servery, které se vyskytují na stejné IP adrese, jako aktivní WEB server.
Rakudo (Wikipedie), tj. překladač programovacího jazyka Raku (Wikipedie), byl vydán ve verzi 2023.05. Programovací jazyk Raku byl dříve znám pod názvem Perl 6.
Linux Foundation Europe představila projekt RISE (RISC-V Software Ecosystem), jehož cílem je urychlit vývoj open source softwaru pro architekturu RISC-V.
Ve funkcionalnim programovani (a la Haskell) mame jen ciste funkce. Tedy realny program (na realnem pocitaci) lze chapat jako jeden velky stavovy automat, nad kterym je jedna cista funkce, ktera vstup a vnitrni stav prevadi do vystupu a noveho vnitrniho stavu.Tady jsem se ztratil. I když fyzicky nakonec program v Haskellu provádí CPU, na který se lze dívat jako na stavový automat, tak ten program není formulován jako nějaký převod jednoho stavu do jiného, ale jako výpočet (představitelný prostě jako dosazování vzorců do jiných vzorců).
pokud je jazyk jako haskell referencne transparentni (u vsech funkci krome IO), tj. je zajisteno ze hodnota funkce je pro jedny parametry vzdy stejna, muzou se takove optimalizace provadet i na urovni prekladace, ale nevim jestli to nejake konkretni implementace provadi.
btw. jestli chcete fundovanou odpoved, tak polozte otazku na stackoverflow.com. tam je daleko vetsi sance, ze ji dostanete.
nektere numericke algoritmy by treba (bez memoizace) dokazaly odvodit napr. vyraz pro vypocet n-teho clenu fibonacciho posloupnosti s O(1), ale u obecne funkce si takovou redukci nedokazu predstavit.
vyraz pro vypocet n-teho clenu fibonacciho posloupnosti s O(1), ale u obecne funkce si takovou redukci nedokazu predstavit.To jde? Sám to umím v O(log n) pomocí mocnění matic (viz anglická wiki).
PS nerýpu, jen se ptám.
Na to si nepotřebujete hrát s maticemi, na to stačí ten vzoreček pro F_{m+n}, který odvodíte buď indukcí nebo z toho, že F_n je počet způsobů, jak poskládat úsečku délky n z úseček délek 1 a 2.
Konstantní složitost má v jistém smyslu ten explicitní vzoreček, který máte v odkazovaném článku také, ale to předpokládá, že s konstantní složitostí umocníte reálné číslo s dostatečnou přesností, což v praktické implementaci nedokážete.
to co hledas by ale imho vyzadovalo specialni typovou tridu, ktera by pro prekladac indikovala ze to zobrazeni je grupova operace a podle toho by s ni taky zachazel. tohle ale standardni typovy system haskellu afaik neobsahuje, nevim jak je to jinde. lze urcite definovat vlastni datove typy a operace nad nimi, ktere by vyhovovaly podminkam pro grupovou algebru, ale tady se asi bavime o obecne metode, ktera by z libovolne funkce vytvorila funkci vyssiho radu, ktera by optimalizovala vypocet vyuzitim grupove algebry. v implementaci by ale stejne pak musela byt nejaka forma memoizingu, protoze tu "konecnou" mnozinu hodnot proste musi vypocitat, i kdyz muze vyuzit vyhody lineho vyhodnocovani. na mnozinach typu cela cisla by to imho ani jinak neslo.
pokud bych se vratil k map, filter, reduce (foldl, foldr v haskellu), tak je podstatne co presne si predstavujes tim doplnenim prvku. pokud se pridanim zachova indukce vypoctu, tak ten puvodni pozadavek lze trivialne splnit uzaverou nebo pro narocnejsi pozadavky nekterou ze stavovych monad. v opacnem pripade plati to co je v predchozim odstavci - bud se definuje cely vlastni typovy system pro grupove operace a bude to fungovat na explicitne resene omezene mnozine nebo pokud by to melo fungovat genericky tak se uz presouvame na uzemi umele inteligence rad se necham vyvest z omylu, pokud tohle uz nejaky jazyk zvlada.
bylo by mozne to priohnout tak, aby funkce v reduce grupova byla?Typový systém Haskellu je příliš slabý na to, aby tuto vlastnost vyjádřil. Existují programovací jazyky, kde to možné je. Mj. v Haskellu lze využít invarianty funkcí (např.
map f . map g == map (f . g)
) v přepisovacích pravidlech pro optimalizaci.
Typový systém Haskellu je příliš slabý na to, aby tuto vlastnost vyjádřil.Předpokládejme, že máme
reduce : (a -> a -> a) -> List a -> a
a chceme zajistit asociativitu prvního parametru (například, aby reduce
mohl počítat paralelně). Jednou z možností, jak to udělat, je přidat funkci reduce
další parametr, který bude sloužit jako konstruktivní důkaz oné asociativity.
Předně si první parametr pojmenujeme, abychom se na něj mohli odkazovat v dalších parametrech:
reduce : (f:(a -> a -> a)) -> List a -> a
.
Nyní se zamyslíme, co je konstruktivním důkazem asociativity f
?. Je to funkce, jenž pro každé x : a
, y : a
, z : a
vrátí důkaz, že f x (f y z) = f (f x y) z
. To jest nový parametr pro reduce
bude funkce x:a -> y:a -> z:a -> f x (f y z) = f (f x y) z
.
Takže paralelní reduce
může mít typ reduce : (f:(a -> a -> a)) -> (x:a -> y:a -> z:a -> f x (f y z) = f (f x y) z) -> List a -> a
.
V Haskellu tento postup nebude fungovat minimálně ze dvou důvodů. Hlavním důvodem je fakt, že Haskell neumí vynutit totální funkce (term undefined = undefined
je důkazem čehokoliv, neboť má libovolný typ) a má pouze koinduktivní typy. Druhým důvodem je to, že Haskell zatím nedovoluje mít aplikaci funkce f
v typu (typ, jenž závisí na termu f
).
Existují programovací jazyky, kde to možné je.Například jazyky Idris nebo Agda 2. Programovat lze též v důkazových asistentech Isabelle a Coq a kód z nich lze pak extrahovat do nějakého normálního funkcionálního jazyka. Další jazyky, kde to pravděpodobně je možné, jsou v tabulce v článku o závislých typech.
Mj. v Haskellu lze využít invarianty funkcí (např. map f . map g == map (f . g)) v přepisovacích pravidlech pro optimalizaci.Mám na mysli přepisovací pravidla v GHC. Používá se to v knihovnách Haskellu a hezkou aplikací je článek Stream Fusion. From Lists to Streams to Nothing at All.
Coq jsem se chtel naucit, ale zatim jsem na to nesebral odvahu.Až se odhodláte, tak doporučuji začít se Software Foundations a poté pokračovat Certified Programming with Dependent Types.
ten zmineny clanek, akorat nejde stahnoutTeď jsem to zkoušel a podařilo se to. Možná to chce jen správné načasování.
Jenom moc nechapu, je opravdu nutne nejak deklarovat pro ta prepisovaci pravidla tu asociativitu (a tedy mit typovy system takto silny)Na přepisovací pravidla v GHC nejsou kladena žádná velká omezení. Je to čistě vaše věc, jestli pravidla zachovají význam programu nebo jestli přepisování vůbec skončí – nic z toho se nekontroluje.
nebylo by mozne to proste rict, ze ta konkretni funkce vstupujici do toho reduce je asociativni (treba soucet)? Nedalo by se to prece jen nejak obejit?Pokud vám nevadí, že to nekontroluje kompilátor, tak dalo. Nejjednodušší je udělat dvě funkce
reduce
a reducePar
, přičemž ta první není paralelní a nepotřebuje asociativitu, ta druhá je paralelní a potřebuje asociativitu (ale kompilátor o tom nic neví). Nebo mohu vyžadovat, aby datový typ byl instancí typové třídy, jenž má asociativní operaci a používat výhradně onu operaci:
import Data.Monoid -- Funguje i s prazdnym seznamem, protoze monoid ma neutralni prvek. reduce :: Monoid a => [a] -> a reduce = mconcatA do třetice mohu napsat opět dvě varianty
reduce
–
jednu pro obyčejné binární funkce a druhou pro asociativní (ve skutečnosti ta druhá není pro funkce, ale pro prvky typu Assoc a
):
{-# LANGUAGE TypeFamilies, FlexibleInstances #-} import qualified Debug.Trace as D class Reduction f where type El f reduce :: f -> [El f] -> El f instance Reduction (a -> a -> a) where type El (a -> a -> a) = a reduce = foldl1 . D.trace "normalni" newtype Assoc a = Assoc { unassoc :: (a -> a -> a) } instance Reduction (Assoc a) where type El (Assoc a) = a reduce = foldl1 . unassoc . D.trace "paralelni"Když pak v GHCi zavolám
reduce (+) [1..5]
, tak dostanu výstup
normalni 15a když zavolám
reduce (Assoc (+)) [1..5]
, tak dostanu výstup
paralelni 15Problém všech třech řešení je v tom, že kompilátor asociativitu nekontroluje, neboť ani neví, že daná funkce má být asociativní. Výhodou silnějších typových systémů je, že asociativitu nebo jinou vlastnost může ověřovat kompilátor.
Tak ctu ted trosku o Curry-Howard izomorfismu a pribuznych tematech na Wikipedii a musim rict, ze jedna vec, ktera me na tom celem pristupu trochu trapi, a to je, ze se tam uplne ignoruje vypocetni narocnost. U matematickeho dukazu mi prece nezalezi na tom, jak dlouho vypocet potrva; a v tom ta analogie fatalne kulha.Myslíte, že to nějak vadí při programování? Třeba u příkladu s
reduce
jsem C-H izomorfismus využil jednou, a to když jsem chtěl, aby f
byla asociativní.
Místo důkazu asociativity jsem požadoval, aby byl typ x:a -> y:a -> z:a -> f x (f y z) = f (f x y) z
obydlený
– tj. uživatel musel funkci reduce
předat term (funkci) proof
typu x:a -> y:a -> z:a -> f x (f y z) = f (f x y) z
.
Při implementaci reduce
však není třeba volat funkci proof
, tudíž na její časové složitosti nezáleží
a kompilátor ji nemusí vůbec překládat.
Nie som si uplne isty, ze som spravne pochopil otazku, ale ak hej, tak ciastocne riesenie existuje. Kompilator moze hladat dostupne vyrazy a nasledne nahradit vypocet podla vypocitaneho zoznamu za premennu, kde je vypocet ulozeny (v skutocnosti je to trocha zlozitejsie, pre detaily ide o problem AVAIL - hladania dostupnych vyrazov pri analyze toku dat, str. 23, zide sa aj uvod - prvych par stran, po problem LIVE).
Co sa tyka uplneho riesenia, tj. v podstate najdenie optimalnej funkcie voci nejakej cenovej funkcii, tak nic take (aspon pre turing-complete jazyky) neexistuje [jednoducha logika - mat podobne riesenie, tak vsetky ostatne optimalizacie by razom stratili zmysel]. Navyse sa obavam, ze na nieco podobne by sa dal spravit aj dokaz (pre zaciatok by mohlo byt problematicke, ze dany optimalizator by mal skoncit aj pri funkciach, ktore nad nejakym vstupom cyklia a detekovat nieco take - problem zastavenia - nie je rekurzivny problem).
Spravnou cestou je v tom pripade az obmedzovanie moznosti (vyjadrovacej sily) programovacich jazykov. Napr. vo forme konecnych automatov je taka optimalizacia mozna a aj jednoducha (viz minimalizacia konecnych automatov).
Uz som si precital dokladnejsie otazku a hlavne diskusiu a myslienka pouzitia informacii navyse pre kompilator je zaujimava a v podstate sa pouziva uz celkom dlho (napriklad register alebo inline v gcc) aj ked ide prevazne o velmi jednoduche veci. Rozne obmedzenia (tie nove abstrakcie) z ktorych vyplyvaju lepsie vlastnosti systemov sa studuju uz tiez celkom dlho, horsie je to s ich aplikaciou na realne programovacie jazyky (zvacsa sa pouzivaju skor matematicke modely, ktore su relativne vzdialene od bezneho programovania).
Teoreticky by nemuselo byt zlozite nieco podobne pre haskell spravit. Runtime optimalizacie by asi nemali moc zmysel, kedze rezia spojena s optimalizaciou by pravdepodobne bola vyssia nez to, co poskytne optimalizacia. V case kompilacie by to uz zmysel mohlo mat (tu by sa asi skutocne hodil modifikovany AVAIL problem pre vypocet dostupnych vyrazov, z ktorych sa da vychadzat v danom bode programu). Realizacia by tiez nemusela byt velmi obtiazna (na high-level urovni, programovania to bude chciet urcite dost). Technicky by stacilo pridat do gramatiky pre jazyk pravidlo, ktore by umoznovalo pri definicii funkcie davat priznaky (splna asociativitu, ma nulovy prvok 'm' a pod.) a nasledne vyuzivat tieto informacie pre optimalizacii.
Este som nepocul o projekte, ktory by sa nieco podobne snazil spravit, co samozrejme neznamena, ze taky projekt neexistuje. Kazdopadne ako napad to vyzera zaujimavo.
btw: Na programy (vsetky, nie len funkcionalne) sa casto pozera ako na transformatory stavovej funkcie, takze napojenie len na funkcionalne jazyky a pripadne line vyhodnocovanie by som v tomto pripade ako klucove nevidel.
Tiskni
Sdílej: