{"id":1959,"date":"2021-03-31T19:14:37","date_gmt":"2021-03-31T18:14:37","guid":{"rendered":"https:\/\/xmau.com\/wp\/ilpost\/?p=1959"},"modified":"2021-03-31T17:30:38","modified_gmt":"2021-03-31T16:30:38","slug":"il-premio-turing-2020-a-aho-e-ullman","status":"publish","type":"post","link":"https:\/\/xmau.com\/ilpost\/2021\/03\/31\/il-premio-turing-2020-a-aho-e-ullman\/","title":{"rendered":"Il premio Turing 2020 a Aho e Ullman"},"content":{"rendered":"<p>Come probabilmente sapete, io non sono solamente un matematico (non praticante), ma anche un informatico (sempre non praticante: quando ho mai tempo di fare qualcosa?) Informatico teorico, per la precisione: non che io non sappia programmare, se serve, ma i miei studi sono stati sul versante teorico dell&#8217;informatica, che si era stabilizzato nella dozzina di anni precedenti alla mia laurea. Quando ho saputo che il premio Turing 2020 <a href=\"https:\/\/awards.acm.org\/about\/2020-turing\">era stato assegnato ad Aho e Ullman<\/a>, il mio primo pensiero \u00e8 stato &#8220;come? non ce l&#8217;avevano gi\u00e0?&#8221;<\/p>\n<p><!--more--> Il premio Turing \u00e8 per gli informatici quello che il premio Abel \u00e8 per i matematici: l&#8217;equivalente di un Nobel. \u00c8 ovvio che Alfred Nobel non avrebbe potuto immaginare di creare un premio per una branca della scienza che sarebbe nata pi\u00f9 di mezzo secolo dopo la sua morte; ma in ogni caso immagino che &#8211; un po&#8217; come per la matematica &#8211; avrebbe trovato l&#8217;informatica troppo poco pratica da meritare di essere nobilitata. Eppure non \u00e8 proprio cos\u00ec! Alfred Aho e Jeffrey Ullman hanno cominciato a lavorare insieme nel posto pi\u00f9 bello possibile negli anni &#8217;60 per chi amava i computer: i Bell Labs. Nella loro collaborazione pluridecennale hanno stabilito una volta per tutte come dobbiamo misurare la validit\u00e0 di un algoritmo, nel loro testo del 1974 &#8216;<i>The Design and Analysis of Computer Algorithms<\/i> scritto con John Hopcroft, ma soprattutto nel 1977 hanno scritto &#8220;l&#8217;Aho-Ullman&#8221;: <i>Principles of Compiler Design<\/i>, il &#8220;libro del drago&#8221;. <\/p>\n<p>Oggi la situazione \u00e8 molto diversa dagli anni &#8217;60 e &#8217;70. La potenza dei computer attuali \u00e8 tale da permettere spesso di scrivere la maggior parte dei programmi in un linguaggio interpretato (il computer traduce una riga per volta il codice sorgente in linguaggio macchina), salvo per le routine pi\u00f9 critiche; allora non era cos\u00ec, e si costruivano i compilatori per tradurre e ottimizzare il codice sorgente e farlo girare pi\u00f9 veloce. Solo che non era affatto facile scrivere un compilatore; ed ecco che Aho e Ullman tirano fuori un certo tipo di struttura per un linguaggio di programmazione che poteva essere trasformata senza grossi problemi in un compilatore, e spiegano nel libro come usare <tt>lex<\/tt> e <tt>yacc<\/tt> (se preferite le versioni GNU, <tt>flex<\/tt> e <tt>bison<\/tt>) per farti in casa il tuo compilatorino. Il corso di LFC &#8211; Linguaggi formali e compilatori &#8211; era praticamente una parafrasi di quel libro, per la precisione della seconda edizione in cui Ravi Sethi si era unito al duo. In pratica, almeno vent&#8217;anni di sviluppo dell&#8217;informatica sono merito o colpa loro&#8230;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Il mio pacato commento: solo ora?<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"activitypub_content_warning":"","activitypub_content_visibility":"","activitypub_max_image_attachments":4,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[1],"tags":[],"class_list":["post-1959","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/phh2yP-vB","jetpack-related-posts":[{"id":384,"url":"https:\/\/xmau.com\/ilpost\/2014\/08\/13\/non-solo-fields\/","url_meta":{"origin":1959,"position":0},"title":"Non solo Fields","author":".mau.","date":"13\/08\/2014","format":false,"excerpt":"Le Fields Medal sono i premi pi\u00f9 importanti del Congresso Internazionale dei Matematici, ma non sono gli unici premi assegnati!","rel":"","context":"In \"Adri\u00e1n Paenza\"","block_context":{"text":"Adri\u00e1n Paenza","link":"https:\/\/xmau.com\/ilpost\/tag\/adrian-paenza\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":756,"url":"https:\/\/xmau.com\/ilpost\/2016\/03\/18\/il-premio-abel-2016-a-sir-andrew-wiles\/","url_meta":{"origin":1959,"position":1},"title":"Il premio Abel 2016 a sir Andrew Wiles","author":".mau.","date":"18\/03\/2016","format":false,"excerpt":"Il suo contributo non sar\u00e0 forse stato \"profondo\", ma sicuramente ha avuto un'enorme influenza.","rel":"","context":"In \"Andew Wiles\"","block_context":{"text":"Andew Wiles","link":"https:\/\/xmau.com\/ilpost\/tag\/andew-wiles\/"},"img":{"alt_text":"[Mica capita a tutti di avere un edificio a proprio nome!]","src":"http:\/\/www.abelprize.no\/aim\/dnva\/75\/52\/storage\/file.image.jpg\/Scale?geometry=516x510","width":350,"height":200},"classes":[]},{"id":2618,"url":"https:\/\/xmau.com\/ilpost\/2013\/06\/18\/quando-conviene-fermarsi\/","url_meta":{"origin":1959,"position":2},"title":"Quando conviene fermarsi?","author":".mau.","date":"18\/06\/2013","format":false,"excerpt":"Un problemino con una risposta non cos\u00ec banale come sembrerebbe a prima vista","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"valore atteso per il gioco \"lancia un dado da 100\"","src":"https:\/\/i0.wp.com\/www.ilpost.it\/wp-content\/uploads\/bloggers\/2013\/06\/dado-da-100.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":199,"url":"https:\/\/xmau.com\/ilpost\/2012\/11\/26\/il-paradosso-di-braess\/","url_meta":{"origin":1959,"position":3},"title":"Il paradosso di Braess","author":".mau.","date":"26\/11\/2012","format":false,"excerpt":"Aggiungere nuove connessioni a una rete in certi casi pu\u00f2 portare a peggiorare le sue prestazioni. Sembra incredibile, ma \u00e8 una conseguenza matematica dell'ipotesi che ognuno sia egoista.","rel":"","context":"In \"paradossi\"","block_context":{"text":"paradossi","link":"https:\/\/xmau.com\/ilpost\/tag\/paradossi\/"},"img":{"alt_text":"[il paradosso di Braess]","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2012\/11\/braess.png?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2012\/11\/braess.png?resize=350%2C200 1x, https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2012\/11\/braess.png?resize=525%2C300 1.5x"},"classes":[]},{"id":1474,"url":"https:\/\/xmau.com\/ilpost\/2019\/05\/06\/raffreddamento-globale-e-giochi-di-azzardo\/","url_meta":{"origin":1959,"position":4},"title":"&#8220;Raffreddamento globale&#8221; e giochi di azzardo","author":".mau.","date":"06\/05\/2019","format":false,"excerpt":"Non sono poi cos\u00ec diversi tra di loro: si tende sempre a sovrastimare la probabilit\u00e0 di eventi estremi.","rel":"","context":"In \"probabilit\u00e0\"","block_context":{"text":"probabilit\u00e0","link":"https:\/\/xmau.com\/ilpost\/tag\/probabilita\/"},"img":{"alt_text":"mappa satellitare","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2019\/05\/NASA-VIIRS-190505-280x300.jpg?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":2646,"url":"https:\/\/xmau.com\/ilpost\/2013\/10\/14\/carnevale-della-matematica-66\/","url_meta":{"origin":1959,"position":5},"title":"Carnevale della matematica #66","author":".mau.","date":"14\/10\/2013","format":false,"excerpt":"La raccolta dei post di argomento matematico nell'ultimo mese","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"Carnevale della Matematica","src":"https:\/\/i0.wp.com\/www.ilpost.it\/wp-content\/uploads\/bloggers\/2010\/07\/20090928-carnevale_matematica.jpg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]}],"_links":{"self":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/1959","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/comments?post=1959"}],"version-history":[{"count":1,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/1959\/revisions"}],"predecessor-version":[{"id":1960,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/1959\/revisions\/1960"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/media?parent=1959"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/categories?post=1959"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/tags?post=1959"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}