Hashing Modulo Alpha Equivalence • Simon Peyton Jones • YOW! 2021

This presentation was recorded at YOW! 2021. #GOTOcon #YOW https://yowcon.com Simon Peyton Jones - Key Contributor of Haskell & Lead Designer Glasgow Haskell Compiler (GHC) RESOURCES https://simon.peytonjones.org https://en.wikipedia.org/wiki/Simon_Peyton_Jones https://twitter.com/simonpj0 https://github.com/simonpj https://www.linkedin.com/in/simonpj ABSTRACT In many applications, one wants to identify identical subtrees of a program syntax tree. This identification should ideally be robust to alpha-renaming of the program, but no existing technique has been shown to achieve this with good efficiency (better than O(n^2) in expression size). We present a new, asymptotically efficient way to hash modulo alpha-equivalence. A key insight of our method is to use a weak (commutative) hash combiner at exactly one point in the construction, which admits an algorithm with O(n*(log n)^2) time complexity. We prove that the use of the commutative combiner nevertheless yields a strong hash with low collision probability. [...] RECOMMENDED BOOKS Simon Peyton Jones • The Implementation of Functional Programming Languages • https://amzn.to/3QxzD5m Vitaly Bragilevsky • Haskell in Depth • https://amzn.to/3EXpmbe Rebecca Skinner • Effective Haskell • https://amzn.to/3VgUKsh Graham Hutton • Programming in Haskell • https://amzn.to/3Fi8rBC John Whitington • Haskell from the Very Beginning • https://amzn.to/3VmX68R https://twitter.com/GOTOcon https://www.linkedin.com/company/goto- https://www.facebook.com/GOTOConferences #ModuloAlpha #Hashing #Haskell #GHC #GlasgowHaskellCompiler #SoftwareEngineering #Programming #FunctionalProgramming #Tech #SoftwareDevelopment #SoftwareTechnology #-SimonPeytonJones #YOWcon Looking for a unique learning experience? Attend the next GOTO conference near you! Get your ticket at https://gotopia.tech Sign up for updates and specials at https://gotopia.tech/newsletter SUBSCRIBE TO OUR CHANNEL - new videos posted almost daily. https://www.youtube.com/user/GotoConferences/?sub_confirmation=1