Upgrade to Pro — share decks privately, control downloads, hide ads and more …

NaturalSet: enumerable, streamable, understandable

NaturalSet: enumerable, streamable, understandable

This talk explores the MapSet API and the implementation of protocols and streaming, through the construction of NaturalSet, a full-featured but simpler set type designed for dense sets of small integers.

Presented at ElixirConf USA 2020 (online)

Luciano Ramalho

September 04, 2020
Tweet

More Decks by Luciano Ramalho

Other Decks in Programming

Transcript

  1. e n u m e r a b l e

    , s t r e a m a b l e , u n d e r s t a n d a b l e NATURAL SET Learning about protocols and streams by implementing a new data type from scratch Luciano Ramalho @ramalhoorg
  2. 30 MINUTES 2 50% 8% 25% 8% 8% Sets FTW!

    The MapSet API NaturalSet under the hood Q&A
  3. 4 Nobody has yet discovered a branch of mathematics that

    has successfully resisted formalization into set theory.
 Thomas Forster
 Logic Induction and Sets, p. 167
  4. USE CASE #1: NEWS PAGE 5 Show newest headlines on

    side bar S, excluding headlines shown in the main content area M.
  5. USE CASE #1: NEWS PAGE 6 S M That's set

    difference S ∖ M Show newest headlines on side bar S, excluding headlines shown in the main content area M. Georg Cantor in 1870 (age 25)
  6. USE CASE #2: UNICODE DATABASE (FLAT FILE SCAN) 7 source:

    https://github.com/standupdev/rf Show character if all words in the query Q appear in name field N.
  7. USE CASE #2: UNICODE DATABASE (FLAT FILE SCAN) 8 query

    = ["FACE", "CAT", "EYES"] ... 1F637;FACE WITH MEDICAL MASK 1F638;GRINNING CAT FACE WITH SMILING EYES 1F639;CAT FACE WITH TEARS OF JOY 1F63A;SMILING CAT FACE WITH OPEN MOUTH 1F63B;SMILING CAT FACE WITH HEART-SHAPED EYES 1F63C;CAT FACE WITH WRY SMILE 1F63D;KISSING CAT FACE WITH CLOSED EYES 1F63E;POUTING CAT FACE 1F63F;CRYING CAT FACE 1F640;WEARY CAT FACE 1F641;SLIGHTLY FROWNING FACE 1F642;SLIGHTLY SMILING FACE 1F643;UPSIDE-DOWN FACE 1F644;FACE WITH ROLLING EYES ... That's a subset test! Q ⊆ N Show character if all words in the query Q appear in name field N.
  8. Q USE CASE #2: UNICODE DATABASE (FLAT FILE SCAN) 9

    Show character if all words in the query Q appear in name field N. That's a subset test! Q ⊆ N grinning with smiling cat face eyes N
  9. USE CASE #3: UNICODE DATABASE (INVERTED INDEX) Given a mapping

    from each word (eg. "FACE") to a set of code points with that word in their names (eg. 9860, 128516, etc.)... 10 source: https://github.com/standupdev/gimel
  10. USE CASE #3: UNICODE DATABASE (INVERTED INDEX) To find emoji

    with the words "CAT FACE EYES" you need to compute... 11 source: https://github.com/standupdev/gimel
  11. USE CASE #3: UNICODE DATABASE (INVERTED INDEX) 12 That's intersection

    of intersection! (F ∩ E) ∩ C ⚄ ⾯面 ☹ ὺ ⚃ ☺ ⚀ ⚂ ⚁ ☻ ⚅ Face Cat Eyes Simplified diagram. There are more characters in: F ∩ C, F ∩ E, C ∩ E
  12. USE CASE #3: UNICODE DATABASE (INVERTED INDEX) Fortunately, Elixir MapSet

    provides intersection/2: 13 source: https://github.com/standupdev/gimel
  13. USE CASE #3: UNICODE DATABASE (INVERTED INDEX) Fortunately, Elixir MapSet

    provides intersection/2: 14 source: https://github.com/standupdev/gimel
  14. MAPSET: ELEMENT API Any basic set API supports these operations:

    16 new() Creates new empty MapSet. new(enum) Creates new MapSet with elements from enumerable. new(enum, transform) Same as above, applying transform to each element. member?(set, element) Is element included MapSet? Same as: e ∈ M put(set, element) Inserts element. No-op if element already in set. delete(set, element) Removes element from set. size(set) Returns number of elements in set. to_list(set) Builds new list from elements in set.
  15. MAPSET: ELEMENT API Any basic set API supports these operations:

    17 new() Creates new empty MapSet. new(enum) Creates new MapSet with elements from enumerable. new(enum, transform) Same as above, applying transform to each element. member?(set, element) Is element included MapSet? Same as: e ∈ M put(set, element) Inserts element. No-op if element already in set. delete(set, element) Removes element from set. size(set) Returns number of elements in set. to_list(set) Builds new list from elements in set. These are all the operations JS ES6 gives you...
  16. MAPSET: SET API Operations between whole sets:
 declarative code, no

    error-prone looping.
 20 intersection(set1, set2) Intersection between sets. A ∩ B union(set1, set2) Union of two sets. A ∪ B difference(set1, set2) Difference of set1 ➖ set2. A ∖ B subset?(set1, set2) Are all elements of set1 in set2? A ⊆ B equal?(set1, set2) Do set1 and set2 have all equal elements? A = B disjoint?(set1, set2) Do set1 and set2 have only distinct elements? A ∩ B = ∅
  17. MAPSET: SET API Operations between whole sets:
 declarative code, no

    error-prone looping.
 21 intersection(set1, set2) Intersection between sets. A ∩ B union(set1, set2) Union of two sets. A ∪ B difference(set1, set2) Difference of set1 ➖ set2. A ∖ B subset?(set1, set2) Are all elements of set1 in set2? A ⊆ B equal?(set1, set2) Do set1 and set2 have all equal elements? A = B disjoint?(set1, set2) Do set1 and set2 have only distinct elements? A ∩ B = ∅ Beyond the von Neumann bottleneck!
  18. SOURCE OF THE IDEA: THE GO PROGRAMMING LANGUAGE The Go

    Programming Language Alan A. A. Donovan & Brian W. Kernighan 23
  19. natural_set hex package 128 LOC (docstrings excluded) 567 LOC total

    (with docstrings + test module) THE CODE 25 https://hex.pm/packages/natural_set
  20. ZOOM-IN: HOW TO PUT AN ELEMENT 44 Given ns with

    elements [0, 4, 5],
 then ns.bits is 49, a.k.a. 0b110001. To put element 2: •shift 1 left by 2:
 result is 4, a.k.a. 0b100 •bitwise OR 0b100 with ns.bits:
 result is 53, a.k.a. 0b110101 •build new set with those bits:
 result is #NaturalSet<[0, 2, 4, 5]>
  21. ZOOM-IN: HOW TO PUT AN ELEMENT 45 Given ns with

    elements [0, 4, 5],
 then ns.bits is 49, a.k.a. 0b110001. To put element 2: •shift 1 left by 2:
 result is 4, a.k.a. 0b100 •bitwise OR 0b100 with ns.bits:
 result is 53, a.k.a. 0b110101 •build new set with those bits:
 result is #NaturalSet<[0, 2, 4, 5]>
  22. ZOOM-IN: HOW TO PUT AN ELEMENT 46 Given ns with

    elements [0, 4, 5],
 then ns.bits is 49, a.k.a. 0b110001. To put element 2: •shift 1 left by 2:
 result is 4, a.k.a. 0b100 •bitwise OR 0b100 with ns.bits:
 result is 53, a.k.a. 0b110101 •build new set with those bits:
 result is #NaturalSet<[0, 2, 4, 5]>
  23. ZOOM-IN: HOW TO PUT AN ELEMENT 47 Given ns with

    elements [0, 4, 5],
 then ns.bits is 49, a.k.a. 0b110001. To put element 2: •shift 1 left by 2:
 result is 4, a.k.a. 0b100 •bitwise OR 0b100 with ns.bits:
 result is 53, a.k.a. 0b110101 •build new set with those bits:
 result is #NaturalSet<[0, 2, 4, 5]>
  24. ELEMENT BY ELEMENT OPERATIONS •||| bitwise OR •&&& bitwise AND

    •^^^ bitwise XOR •<<< shift left •>>> shift right 48
  25. LENGTH: HOW MANY ELEMENTS ARE PRESENT? The corresponding function in

    MapSet is size/1. However, counting the elements in NaturalSet takes O(n) time. Therefore, by convention, this function must be named length/1. 50
  26. PROTOCOLS IN ELIXIR 1.10 Predefined protocols •Collectable •Enumerable •Inspect •Inspect.Algebra

    •Inspect.Opts •List.Chars •String.Chars Support for building protocols •Protocol 52
  27. AN ESSENTIAL PROTOCOL: STRING.CHARS Protocol String.Chars is used by Kernel.to_string,

    IO.puts and string interpolation. The Elixir standard library does not implement String.Chars for MapSet. 53
  28. A protocol is defined by defprotocol. Inside defprotocol there are

    function signatures with no body. In this example: to_string(term) STRING.CHARS PROTOCOL DEFINITION 54
  29. To implement a protocol for a type in a different

    module, use defimpl, for: ANY MODULE CAN IMPLEMENT STRING.CHARS FOR MAPSET 55 https://github.com/ramalho/ElixirConf-NaturalSet
  30. To implement Collectable, write an into/1 function. I copied this

    from the MapSet implementation. Only line 112 was changed to call NaturalSet.put/2. COLLECTABLE PROTOCOL IMPLEMENTATION 60
  31. Enumerable supports many functions in Enums and Streams. Implementation has

    count/1, member?/2, slice/1 and reduce/3. slice/1 would require size/1, so this implementation returns an error. This is a convention. ENUMERABLE PROTOCOL IMPLEMENTATION 61
  32. STREAMS 101: THE GOOD OLD FIBONACCI EXAMPLE stream/0 lazily yields

    Fibonacci numbers forever.* * the size on an Elixir integer is limited only by memory 63
  33. STREAMS 101: THE GOOD OLD FIBONACCI EXAMPLE Stream.unfold/2 takes: accumulator

    and function/1. In this example: •initial accumulator is {0, 1}: first pair of the sequence, passed to function/1. •function/1 must return: {number_to_emit, next_accumulator} •next_accumulator is {next_a, next_b} 64
  34. STREAMS 101: A FIBONACCI EXAMPLE THAT STOPS stream_max/1 lazily yields

    numbers from the Fibonacci series until the next number a is larger than the max argument. Stream.unfold/2 stops when the inner function yields nil. 65
  35. STREAM: LAZILY YIELD THE ELEMENTS, ONE BY ONE Here, Stream.unfold/2

    takes accumulator and next_one/1: •accumulator is {bits, index}, where index is the value of a (possible) element. •next_one/1 returns: nil or {element_to_emit, {next_bits, next_index}} 67
  36. TAKE AWAYS •If you've never used MapSet, I bet you've

    written a lot of redundant code. 69
  37. TAKE AWAYS •If you've never used MapSet, I bet you've

    written a lot of redundant code. •MapSet has a rich API, including powerful operations with whole sets. 70
  38. TAKE AWAYS •If you've never used MapSet, I bet you've

    written a lot of redundant code. •MapSet has a rich API, including powerful operations with whole sets. •Implementing protocols allow custom types to interoperate with core parts of the Elixir standard library: Kernel, Enums, Streams... 71
  39. TAKE AWAYS •If you've never used MapSet, I bet you've

    written a lot of redundant code. •MapSet has a rich API, including powerful operations with whole sets. •Implementing protocols allow custom types to interoperate with core parts of the Elixir standard library: Kernel, Enums, Streams... •Streaming can be implemented with the help of Streams.unfold/2 (and other helpers in the Streams module). 72
  40. TAKE AWAYS •If you've never used MapSet, I bet you've

    written a lot of redundant code. •MapSet has a rich API, including powerful operations with whole sets. •Implementing protocols allow custom types to interoperate with core parts of the Elixir standard library: Kernel, Enums, Streams... •Streaming can be implemented with the help of Streams.unfold/2 (and other helpers in the Streams module). •To learn more, study the code for MapSet and NaturalSet. 73 https://hex.pm/packages/natural_set