<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Sven VC on Medium]]></title>
        <description><![CDATA[Stories by Sven VC on Medium]]></description>
        <link>https://medium.com/@svenvc?source=rss-69bbb011558e------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*aGKJXxZ8CNmGA7Rnfcsywg.png</url>
            <title>Stories by Sven VC on Medium</title>
            <link>https://medium.com/@svenvc?source=rss-69bbb011558e------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Fri, 20 Nov 2026 00:14:22 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@svenvc/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Understanding Base58 Encoding]]></title>
            <link>https://medium.com/concerning-pharo/understanding-base58-encoding-23e673e37ff6?source=rss-69bbb011558e------2</link>
            <guid isPermaLink="false">https://medium.com/p/23e673e37ff6</guid>
            <category><![CDATA[pharo]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[base58]]></category>
            <category><![CDATA[smalltalk]]></category>
            <dc:creator><![CDATA[Sven VC]]></dc:creator>
            <pubDate>Tue, 15 Dec 2020 19:45:30 GMT</pubDate>
            <atom:updated>2022-09-22T11:54:24.705Z</atom:updated>
            <content:encoded><![CDATA[<h4>It is all about integers</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*b8gvF2yAUkwXT8-Rh7gBFQ.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/@dancristianp?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Dan-Cristian Pădureț</a> on <a href="https://unsplash.com/t/experimental?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></figcaption></figure><p>Some time ago something popped up in my inbox that piqued my interest: a draft <a href="https://en.wikipedia.org/wiki/Request_for_Comments">RFC</a> about Base58 Encoding, <a href="https://tools.ietf.org/id/draft-msporny-base58-01.html">The Base58 Encoding Scheme</a>.</p><p>I already knew about Base58 encoding: it is technique to encode arbitrary binary data into a textual representation that is easier to handle, much like <a href="https://en.wikipedia.org/wiki/Base64">Base64</a>.</p><p>Base58 encoding was designed to encode Bitcoin addresses. It has the following characteristics:</p><ul><li>its alphabet avoids similar looking letters</li><li>it does not use non-alphanumeric characters</li></ul><p>These features help humans to make less errors and allows direct inclusion in filenames and URLs.</p><p>What did however confuse me a lot were the encoding and decoding algorithms in the RFC. They were describing a particular implementation instead of the mathematical principles.</p><p>So I started exploring to try understand what was going. Here is what I learnt. All code was written in <a href="https://pharo.org/">Pharo</a>, a pure object-oriented programming language and powerful environment, focused on simplicity and immediate feedback.</p><h3>Decimal numbers</h3><p>The most common way to notate integers is using <a href="https://en.wikipedia.org/wiki/Decimal">decimal notation</a>, or more precisely using <strong>the base-ten positional numeral system</strong>.</p><p>For a ten-based system, we need 10 digits, 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9. Each of these has a numerical value associated to them, again 0 to 9. So the base is 10, the alphabet is ‘0123456789’ and each digit’s value is its zero-based index in the alphabet.</p><p>The position in the digit string determines its meaning. From right to left, each increasing position corresponds to another, higher power of the base.</p><p>For example, 123 is seen as (1 * 100) + (2 * 10) + 3. Using powers of the base this becomes (1 * 10²) + (2 * 10¹) + (3 * 10⁰). We can rewrite this to avoid the power operation (((1 * 10) + 2) * 10) + 3.</p><p>Let’s try this in code:</p><pre>input := &#39;1234&#39;.<br>digits := &#39;0123456789&#39;.</pre><pre>n := 0.<br>input do: [ :each |<br>  n := n * 10 + (digits indexOf: each) — 1 ].<br>n.</pre><p>What we did above is parse a string, inputcontaining a decimal number into an internal machine number, n. Note that Pharo uses one-based indexes.</p><p>What about the other direction ? How do we produce the decimal number string given an internal machine integer ?</p><p>We can take the integer apart using the quotient (integer division) and modulo (remainder after integer division) with the base.</p><p>In Pharo, the operators are // for quotient and \\ for remainder. For example,</p><pre>10 // 3 = 3.<br>10 \\ 3 = 1.<br>(3 * 3) + 1 = 10.</pre><pre>n = (b * (n // b)) + (n \\ b).</pre><pre>123 \\ 10 = 3.<br>123 // 10 = 12.</pre><p>The fourth line above is the invariant that holds for quotient and remainder. The last two lines above show how we take the lowest (rightmost, least significant) digit out of an integer and shift the integer to the right.</p><p>Now, let’s try putting all of this together:</p><pre>n := 1234.<br>digits := &#39;0123456789&#39;.</pre><pre>(String streamContents: [ :out |<br>  [ n &gt; 0 ] whileTrue: [ <br>    out nextPut: (digits at: (n \\ 10) + 1).<br>    n := n // 10 ] ]) reverse.</pre><p>What we did was implement a printer for positive integers that produces a decimal number string given an internal machine integer.</p><p>Since we’re working from the right (least significant) to left (most significant) digit, we have to reverse the result.</p><h3>Any base, any alphabet</h3><p>The code that we wrote in the previous section seems specific to decimal numbers, but it is actually quite general.</p><p>By using the digits ‘0123456789ABCDEF’ and 16 instead of 10 as base, we get a parser and printer for <a href="https://en.wikipedia.org/wiki/Hexadecimal">hexadecimal numbers</a>.</p><p>Similarly, ‘01234567’ and 8 for <a href="https://en.wikipedia.org/wiki/Octal">octal numbers</a> and even ‘01’ and 2 for <a href="https://en.wikipedia.org/wiki/Binary_number">binary numbers</a>.</p><p>We can construct strange new variants by using odd bases and odd alphabets. For example, using ‘ABCDEFGHIJKL’ with base 12 would work just fine. In this particular system, 1234 would be written as ‘IGK’ — a number without actual digits.</p><h3>Bytes are integers too</h3><p>A sequence of 8-bit bytes, a ByteArray, can also be seen as one large integer, by considering each byte as a digit that is its own value, using base 256.</p><p>Here is code for the ByteArray to Integer conversion operation:</p><pre>bytes := #[ 10 20 30 40 50 60 ].</pre><pre>n := 0.<br>bytes do: [ :each |<br>  n := n * 256 + each ].<br>n.</pre><p>This is functionally equivalent to what the builtin Pharo method ByteArray&gt;&gt;#asIntegerdoes.</p><p>This bytes to integer conversion is also called the <a href="https://en.wikipedia.org/wiki/Endianness">network byte order, big endian, most to least significant digit form</a>. It is how 16-bit, 32-bit, 64-bit integers are stored in memory in such systems. This is in contrast to little endian systems where the order is reversed.</p><p>The reverse operation converts an Integer into a ByteArray, just like the builtin Integer&gt;&gt;#asByteArraymethod.</p><pre>n := 11081521574460.</pre><pre>(ByteArray streamContents: [ :out |<br>  [ n &gt; 0 ] whileTrue: [<br>    out nextPut: n \\ 256.<br>    n := n // 256 ] ]) reverse.</pre><p>Note how similar the code in this section is compared to the code in the first section. The only difference is that we do not need to convert a character from the alphabet into a numerical value or vice versa, since each element is its own value.</p><p>BTW, Integers in Pharo can be of arbitrary size, which is necessary to make this possible.</p><h3>The encoding principle</h3><p>Using the techniques described above, we can now describe Base58 <strong>encoding</strong> as follows:</p><ul><li>convert a ByteArray to an Integer</li><li>print that Integer using base 58 and a special alphabet</li></ul><p><strong>Decoding</strong> then becomes:</p><ul><li>parse the representation using base 58 and a special alphabet</li><li>convert that Integer to a ByteArray</li></ul><p>The 58 digit long <strong>alphabet</strong> to use is equal to</p><pre>&#39;123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz&#39;</pre><p>Note that this is a strange alphabet, since the decimal digits do not stand for themselves (1 is zero for example) and some letters are not used.</p><p>Here is a <strong>test</strong> vector from the RFC:</p><pre>&#39;Hello World!&#39; asByteArray.</pre><p>would be Base58 encoded to</p><pre>&#39;2NEpo7TZRRrLZSi2U&#39;.</pre><h3>Leading zeros</h3><p>We skipped over one significant detail though. Just like 1234, 01234 or 001234 are the same (i.e. the leading zero is insignificant), ByteArrays with leading zero bytes are encoded to the same integer.</p><p>For example,</p><pre>#[ 1 2 3 ] asInteger.<br>#[ 0 1 2 3 ] asInteger.<br>#[ 0 0 1 2 3 ] asInteger.</pre><p>are all equal to 66051. That is not what we want. In this case we want to preserve those leading zero bytes.</p><p>Luckily there is an elegant solution to handle this situation: add as many leading zeroes (or at least the digit representing zero) to the final encoding as there are leading zero bytes.</p><p>For the 3 examples above, that would result in ‘66051’, ‘066051’ and ‘0066051’ respectively. Of course, we need no additional zero after step one, but after step two.</p><p>In Base58 encoding, leading zeros are actual 1s. So the number of leading 1s is equal to the number of leading zero bytes, to be added in front of the ByteArray result after step two. Other than this, the leading 1s can be ignored, just like any leading zero.</p><p>For example, the RFC states that the <strong>test</strong> vector</p><pre>ByteArray readHexFrom: &#39;000000287fb4cd&#39;.</pre><pre>#[0 0 0 40 127 180 205]</pre><p>should be Base58 encoded to</p><pre>&#39;111233QC4&#39;</pre><h3>Putting it all together</h3><p>We are now ready to show the complete solution. First the <strong>decoding</strong>:</p><pre>alphabet := &#39;123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz&#39;.<br>input := &#39;2NEpo7TZRRrLZSi2U&#39;.</pre><pre>ByteArray streamContents: [ :out | | n |<br>  n := 0.<br>  input do: [ :each | | b |<br>    b := (alphabet <br>      indexOf: each <br>      ifAbsent: [ self error: &#39;Base58 digit expected&#39; ]) — 1.<br>    (n = 0 and: [ b = 0 ])<br>      ifTrue: [ out nextPut: 0 ].<br>    n := n * 58 + b ].<br>  out nextPutAll: n asByteArray ].</pre><p>Using the indexOf:ifAbsent:message instead of indexOf:takes care of an error case. Zero digits are output as zero bytes while the number itself is still zero (i.e. only for leading zeros). Next we decode using base 58 and the alphabet. Conversion to a ByteArray happens in the last line.</p><p>Secondly we implement the <strong>encoding</strong>:</p><pre>alphabet := &#39;123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz&#39;.<br>input := &#39;Hello World!&#39; asByteArray.</pre><pre>(String streamContents: [ :out | | r n |<br>  n := input asInteger.<br>  [ n &gt; 0 ] whileTrue: [ <br>    out nextPut: (alphabet at: (n \\ 58) + 1).<br>    n := n // 58 ].<br>  r := input readStream.<br>  [ r peekFor: 0 ] whileTrue: [ <br>    out nextPut: alphabet first ] ]) reverse.</pre><p>We start by converting the ByteArray to an Integer. Next we encode it using base 58 and the alphabet. Then we scan over the input bytes and output 1s as long as we see zero bytes. Finally we reverse the result.</p><blockquote>All in all, I find Base58 encoding quite elegant. I hope that my explanation is easier to understand by being closer to the actual mathematical principles used.</blockquote><p><strong>PS:</strong> Esteban A. Maringolo has a <a href="https://github.com/eMaringolo/pharo-base58">pharo-base58</a> project which contains additional features, including the ‘check’ algorithm. If you are looking for more, it is worth checking out.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=23e673e37ff6" width="1" height="1" alt=""><hr><p><a href="https://medium.com/concerning-pharo/understanding-base58-encoding-23e673e37ff6">Understanding Base58 Encoding</a> was originally published in <a href="https://medium.com/concerning-pharo">Concerning Pharo</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Quick, write me a Redis client]]></title>
            <link>https://medium.com/concerning-pharo/quick-write-me-a-redis-client-5fbe4ddfb13d?source=rss-69bbb011558e------2</link>
            <guid isPermaLink="false">https://medium.com/p/5fbe4ddfb13d</guid>
            <category><![CDATA[pharo]]></category>
            <category><![CDATA[smalltalk]]></category>
            <category><![CDATA[protocol]]></category>
            <category><![CDATA[redis]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Sven VC]]></dc:creator>
            <pubDate>Wed, 14 Jun 2017 12:28:01 GMT</pubDate>
            <atom:updated>2018-09-30T19:48:34.083Z</atom:updated>
            <content:encoded><![CDATA[<p>A beautiful protocol makes implementation easy</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*qzZNeEC34ctFU--qPXcUmg.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/@joelfilip">Joel Filipe</a></figcaption></figure><p><a href="https://redis.io/">Redis</a> is a networked, in-memory key-value store with optional durability, supporting different kinds of abstract data structures. Redis can be used to implement various server side architectural patterns.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*J_6GiP2Ol0PAyDwAWKNtUg.png" /></figure><p>You interact with Redis using a client/server protocol. Redis’ protocol is beautifully simple, which makes implementing it easy.</p><blockquote>This article shows how to quickly implement a minimal, yet fully functional Redis client in <a href="https://pharo.org/">Pharo</a>.</blockquote><h3>The protocol</h3><p><a href="https://redis.io/topics/protocol">RESP (REdis Serialization Protocol)</a> is a request/response protocol over a TCP connection. There are only 5 data types: simple strings, errors, integers, bulk strings and arrays. The first character indicates the type.</p><p><strong>Simple strings</strong> start with a <strong>+</strong> and run until end of line (CRLF, \r\n). These cannot contain embedded end of lines.</p><pre>+OK\r\n</pre><p><strong>Errors</strong> are similar but start with a <strong>—</strong> and end with CRLF.</p><pre>-ERR unknown command ‘GETT’\r\n</pre><p><strong>Integers</strong> start with with a <strong>:</strong> and end with CRLF</p><pre>:1\r\n</pre><p><strong>Bulk string</strong>s can contain anything and are prefixed by a <strong>$</strong> and an explicit byte count ending with CRLF. Then follows the actual contents. There is an extra CRLF at the end.</p><pre>$2\r\nOK\r\n</pre><p><strong>Arrays</strong> are the composite type. They start with a <strong>*</strong> and an element count ending with CRLF. After that the elements themselves follows.</p><pre>*2\r\n$3\r\nfoo\r\n$3\r\nbar\r\n</pre><p><strong>Commands</strong> (requests) from the client to the server are sent as an array of bulk strings. For example, the command to set a key to a value is called SET and takes two arguments, the key name and the value, both strings. So, “SET foo 100” will look as follows.</p><pre>*3\r\n$3\r\nSET\r\n$3\r\nfoo\r\n$3\r\n100\r\n</pre><p>As a convenience, a simpler entry format is also supported. These inline commands can be written on one line with arguments separated by spaces.</p><pre>SET foo 100\r\n</pre><p>Responses can be any of the 5 data types and depend on the command.</p><h3>The unit tests</h3><p>In the spirit of test driven development (TDD) we write down our expectations for 2 simple commands. The first is a simple PING command that gives a PONG reply. The second is an ECHO command that answers its argument.</p><pre><strong>TestCase</strong> subclass: #<strong>SimpleRedisClientTests</strong><br>  instanceVariableNames: ‘client’<br>  classVariableNames: ‘’<br>  package: ‘SimpleRedisClient’</pre><p>Each test needs a functional, connected client.</p><pre><strong>SimpleRedisClientTests&gt;&gt;#setUp</strong><br>  client := SimpleRedisClient new.<br>  client open</pre><pre><strong>SimpleRedisClientTests&gt;&gt;#tearDown</strong><br>  client close</pre><p>Here is our first test using a simplified inline command.</p><pre><strong>SimpleRedisClientTests&gt;&gt;#testPing</strong><br>  self assert: (client executeInline: #PING) equals: #PONG</pre><p>Our second test uses a general command with arguments.</p><pre><strong>SimpleRedisClientTests&gt;&gt;#testEcho</strong><br>  | string |<br>  string := ‘STR-’ , 99 atRandom asString.<br>  self assert: (client execute: { #ECHO. string }) equals: string</pre><h3>The client</h3><p>To connect to a server, our client will need to know a <strong>host</strong> and <strong>port</strong>. Once connected, we’ll have a <strong>connection</strong> representing the binary TCP stream. To work fluently with character based input and output, we’ll need <strong>in</strong> and <strong>out</strong> streams.</p><p>This is the class definition for the object implementing our Redis client.</p><pre><strong>Object</strong> subclass: #<strong>SimpleRedisClient</strong><br>  instanceVariableNames: ‘host port connection in out’<br>  classVariableNames: ‘’<br>  package: ‘SimpleRedisClient’</pre><p>First we add accessors for host and port, taking into account some useful defaults.</p><pre><strong>SimpleRedisClient&gt;&gt;#host</strong><br>  ^ host ifNil: [ host := ‘localhost’ ]</pre><pre><strong>SimpleRedisClient&gt;&gt;#host: </strong>string<br>  host := string</pre><pre><strong>SimpleRedisClient&gt;&gt;#port</strong><br>  ^ port ifNil: [ port := 6379 ]</pre><pre><strong>SimpleRedisClient&gt;&gt;#port: </strong>integer<br>  port := integer</pre><p>Opening and closing a client means dealing with the binary TCP socket stream and the characters streams to read from and to write to.</p><pre><strong>SimpleRedisClient&gt;&gt;#open</strong><br>  self close.<br>  connection := ZdcSocketStream <br>    openConnectionToHostNamed: self host <br>    port: self port.<br>  in := ZnCharacterReadStream on: connection.<br>  out := ZnCharacterWriteStream on: connection</pre><pre><strong>SimpleRedisClient&gt;&gt;#close</strong><br>  connection<br>    ifNotNil: [ <br>      [ connection close ] on: Error do: [ ].<br>      in := out := connection := nil ]</pre><p>Calling #close from #open makes it more robust and able to function as a re-open call. The raw TCP socket stream deals in bytes, not characters. The character streams add UTF-8 encoding &amp; decoding.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1002/1*Rby-nma62xLpYEL6DlwkhQ.png" /><figcaption>The character streams wrap the binary socket stream</figcaption></figure><p>A normal command execution consists of two phases: writing the command and reading the reply.</p><pre><strong>SimpleRedisClient&gt;&gt;#execute: </strong>commandArgs<br>  self writeCommand: commandArgs.<br>  ^ self readReply</pre><pre><strong>SimpleRedisClient&gt;&gt;#executeInline: </strong>command<br>  self writeInlineCommand: command.<br>  ^ self readReply</pre><p>What is left is the implementation of the protocol itself: writing commands and reading replies, following the specification.</p><h4>Writing commands</h4><pre><strong>SimpleRedisClient&gt;&gt;#writeCommand: </strong>args<br>  out nextPut: $*; print: args size; crlf.<br>  args do: [ :each |<br>    | string byteCount |<br>    string := each asString.<br>    byteCount := out encoder encodedByteCountForString: string.<br>    out <br>      nextPut: $$; print: byteCount; crlf; <br>      nextPutAll: string; crlf ].<br>  out flush</pre><pre><strong>SimpleRedisClient&gt;&gt;#writeInlineCommand: </strong>string<br>  out nextPutAll: string; crlf; flush</pre><p>Normal commands are arrays of bulk strings. First we write out the element count. Each command argument is converted to a string. The Redis protocol does not specify what encoding to use for strings, that is up to the client. For Redis, it is just a collection of bytes. We chose to use UTF-8, a variable length encoding. The string length after $ is a byte count though, not a character count. Therefor we use the encoder to compute how many bytes are needed to encode the string.</p><p>Inline commands are written as a single line.</p><p>A command is followed by a #flush to push all data over the wire.</p><h4>Reading replies</h4><p>Reading a reply starts by looking at the first character.</p><pre><strong>SimpleRedisClient&gt;&gt;#readReply</strong><br>  | first |<br>  first := in next.<br>  first = $+ ifTrue: [ ^ in nextLine ].<br>  first = $: ifTrue: [ ^ in nextLine asInteger ].<br>  first = $- ifTrue: [ ^ self error: in nextLine ].<br>  first = $* ifTrue: [ ^ self readArray ].<br>  first = $$ ifTrue: [ ^ self readBulkString ].<br>  self error: ‘Unknown reply type’</pre><p>Simple strings, errors and numbers are handled directly. Arrays and bulk strings are handled by helper methods.</p><pre><strong>SimpleRedisClient&gt;&gt;#readArray</strong><br>  | length array |<br>  length := in nextLine asInteger.<br>  length = -1 ifTrue: [ ^ nil ].<br>  array := Array new: length streamContents: [ :elements |<br>    length timesRepeat: [ elements nextPut: self readReply ] ].<br>  ^ array</pre><p>Array lengths of -1 are a special case and are different from an empty array. The correct number of elements are read by recursively invoking #readReply. Arrays can contains elements of different types.</p><pre><strong>SimpleRedisClient&gt;&gt;#readBulkString</strong><br>  | byteCount bytes |<br>  byteCount := in nextLine asInteger.<br>  byteCount = -1 ifTrue: [ ^ nil ].<br>  bytes := in wrappedStream next: byteCount.<br>  in nextLine.<br>  ^ in encoder decodeBytes: bytes</pre><p>This last method completes our implementation. Again, a length of -1 is treated as a special case. Since the length is a byte count, we access the #wrappedStream (i.e. the binary socket stream) and read the raw bytes in one block. Then we use the encoder to decode the bytes.</p><blockquote>In about 10 significant methods, we have now implemented a minimal but fully functional Redis client.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*lnwobYF6nBbXDELBMbdHQQ.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/@ed259">Edouard Ki</a></figcaption></figure><h3>More unit tests</h3><p>On top of this deceptively simple protocol, Redis implements a lot of functionality, all of which is accessible with our simple client. Here are a couple of examples, written in the form of additional unit tests.</p><p>The details of each command can be found in <a href="https://redis.io/commands">the online Redis command documentation</a>.</p><h4>Key-value storage</h4><p>Here is some basic key-value store usage.</p><pre><strong>SimpleRedisClientTests&gt;&gt;#testStringGetSetSimple</strong><br>  | string |<br>  string := ‘STR-’ , 99 atRandom asString.<br>  self assert: (client execute: #(DEL foo)) &gt;= 0.<br>  self assert: (client execute: #(EXISTS foo)) equals: 0.<br>  self assert: (client execute: #(GET foo)) isNil.<br>  self assert: (client execute: { #SET. #foo. string }) equals: #OK.<br>  self assert: (client execute: #(GET foo)) equals: string.<br>  self assert: (client execute: #(EXISTS foo)) equals: 1.<br>  self assert: (client execute: #(DEL foo)) &gt; 0.</pre><h4>Counters</h4><p>The value of a key can be interpreted as an integer counter with atomic operations. Undefined counters start from zero.</p><pre><strong>SimpleRedisClientTests&gt;&gt;#testSimpleCounter</strong><br>  client execute: #(DEL mycounter).<br>  self assert: (client execute: #(INCR mycounter)) equals: 1.<br>  self assert: (client execute: #(INCR mycounter)) equals: 2.<br>  self assert: (client execute: #(GET mycounter)) equals: ‘2’.<br>  self assert: (client execute: #(DECR mycounter)) equals: 1.<br>  self assert: (client execute: #(INCRBY mycounter 10)) equals: 11.<br>  client execute: #(DEL mycounter).</pre><h4>Other data structures</h4><p>Lists, sets, sorted sets and hash tables are some of <a href="https://redis.io/topics/data-types-intro">the supported data structures</a>. You can find more unit tests in the source code distributed (see load instructions at the end).</p><h4>Queues</h4><p>Our client is even flexible enough to support some special use cases. Lists can be uses as queues, with a blocking call to wait for new data.</p><pre><strong>SimpleRedisClientTests&gt;&gt;#testQueueSimple</strong><br>  | string semaphore |<br>  string := ‘STR-’ , 99 atRandom asString.<br>  semaphore := Semaphore new.<br>  client execute: #(DEL myqueue).</pre><pre>  [<br>    | anotherClient |<br>    anotherClient := SimpleRedisClient new.<br>    anotherClient open.<br>    semaphore signal.<br>    <em>&quot;Block waiting for data entering the queue&quot;</em><br>    self<br>      assert: (anotherClient execute: #(BRPOP myqueue 0)) <br>      equals: { #myqueue. string }.<br>    semaphore signal.<br>    anotherClient close<br>  ] <br>    forkAt: Processor userSchedulingPriority <br>    named: ‘testQueueSimple’.</pre><pre>  semaphore wait.<br>  self assert: (client execute: { #LPUSH. #myqueue. string }) &gt; 0.<br>  semaphore wait.<br>  client execute: #(DEL myqueue).</pre><p>The main thread waits until the forked thread is ready, coordinating using a semaphore. Then it pushes a new item onto the front of the queue.</p><p>The forked thread issues a blocking pop on the back of the queue. It will receive and remove the string pushed by the main thread.</p><h4>Pub/Sub</h4><p>Another use case is a pub/sub mechanism. Data is published to a channel. Multiple parties can subscribe to this channel. Each subscriber will receive notifications of data published.</p><pre><strong>SimpleRedisClientTests&gt;&gt;#testPubSubSimple</strong><br>  | semaphore string |<br>  string := ‘STR-’ , 99 atRandom asString.<br>  semaphore := Semaphore new.<br>  client execute: #(DEL mychannel).<br> <br>  [<br>    | anotherClient |<br>    semaphore wait.<br>    anotherClient := SimpleRedisClient new.<br>    anotherClient open.<br>    self assert: (anotherClient execute:<br>      { #PUBLISH. #mychannel. string }) &gt; 0.<br>    anotherClient close<br>  ] <br>    forkAt: Processor userBackgroundPriority <br>    named: ‘testPubSubSimple’.</pre><pre>  self <br>    assert: (client execute: #(SUBSCRIBE mychannel))<br>    equals: #(subscribe mychannel 1).<br>  semaphore signal.<br>  <em>&quot;Block waiting for data distributed over the channel&quot; </em><br>  self <br>    assert: client readReply <br>    equals: { #message. #mychannel. string }.<br>  self <br>    assert: (client execute: #(UNSUBSCRIBE mychannel)) <br>    equals: #(unsubscribe mychannel 0).<br>  client execute: #(DEL mychannel).</pre><p>Here the main thread blocks on reading an incoming notification after subscribing to the channel.</p><p>The forked thread publishes a string to the channel. The main thread will receive this string as a message from the channel.</p><h3>Conclusion</h3><p>It is a clever move of the Redis designers to offer such an elegant and simple protocol. It makes it easy to implement new clients, which leads to more users for their software.</p><p>For a dynamic, interactive language like Pharo it is important to be able to interact with as many services and servers as possible. Luckily writing new clients can be easy as well as fun.</p><h3>Source Code</h3><p>The source code for <strong>SimpleRedisClient</strong> and <strong>SimpleRedisClientTests</strong> can be found on GitHub under the URL <a href="https://github.com/svenvc/SimpleRedisClient">https://github.com/svenvc/SimpleRedisClient</a>.</p><p>To load the code in Pharo 6.1 or later, open <strong>World &gt; Tools &gt; Iceberg</strong>, click <strong>+</strong> to add a repository, select the option <strong>Clone From github.com</strong> and enter svenvc as owner name and SimpleRedisClient as project name. With the new repository selected, select <strong>Metacello &gt; Install baseline of SimpleRedisClient</strong>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5fbe4ddfb13d" width="1" height="1" alt=""><hr><p><a href="https://medium.com/concerning-pharo/quick-write-me-a-redis-client-5fbe4ddfb13d">Quick, write me a Redis client</a> was originally published in <a href="https://medium.com/concerning-pharo">Concerning Pharo</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[The code behind Google Authenticator]]></title>
            <link>https://medium.com/concerning-pharo/the-code-behind-google-authenticator-9c59c606a572?source=rss-69bbb011558e------2</link>
            <guid isPermaLink="false">https://medium.com/p/9c59c606a572</guid>
            <category><![CDATA[security]]></category>
            <category><![CDATA[pharo]]></category>
            <category><![CDATA[two-factor-authentication]]></category>
            <dc:creator><![CDATA[Sven VC]]></dc:creator>
            <pubDate>Fri, 04 Nov 2016 15:33:11 GMT</pubDate>
            <atom:updated>2025-09-15T07:21:37.911Z</atom:updated>
            <content:encoded><![CDATA[<p>Implementing Time-base One-Time Passwords in Pharo</p><p>As a programmer I was curious how <a href="https://en.wikipedia.org/wiki/Google_Authenticator">Google Authenticator</a>, an iOS or Andriod mobile app used to implement two-factor authentication (2FA), really worked and how I could implement it myself. Since it is a lot of fun to experiment with and implement this kind of stuff in <a href="https://pharo.org/">Pharo</a>, I decided to give it a try.</p><blockquote><strong>Note</strong>: source code access instructions can be found at the end.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*usOiHSzeCsZqSlsB41gmlw.png" /><figcaption>Screenshot showing Pharo computing the Google Authenticator code</figcaption></figure><p>Turns out that Google Authenticator is an implementation of something called ‘Time-base One-Time Passwords’ (TOTP). This is a standard algorithm specified in <a href="https://tools.ietf.org/html/rfc6238">RFC 6238</a> (TOTP: Time-Based One-Time Password Algorithm) &amp; <a href="https://tools.ietf.org/html/rfc4226">RFC 4226</a> (HOTP: An HMAC-Based One-Time Password Algorithm). Additionally, <a href="https://en.wikipedia.org/wiki/Base32">Base32</a> encoding is used to represent keys.</p><h3>Usage</h3><p>Google Authenticator is used to improve username/password authentication by requiring one time passwords generated from a previously shared secret.</p><p>On the server side initialization starts with the generation of a new shared secret.</p><pre>GoogleAuthenticator new<br>  randomSecret.</pre><p>Next we send #base32Secret to this object to turn the secret into a more human friendly form.</p><pre>&#39;HXDMVJECJJWSRB3HWIZR4IFUGFTMXBOZ&#39;</pre><p>Next this secret is shared with the client (this is often done using a QR code).</p><p>On the client side, initialization starts based on the shared secret.</p><pre>GoogleAuthenticator new <br>  base32Secret: &#39;HXDMVJECJJWSRB3HWIZR4IFUGFTMXBOZ&#39;.</pre><p>One time passwords are computed by sending #next or #nextPadded.</p><p>The server asks the client to provide the next one time password. The client uses his instance to compute it and informs the server of it. The server then does the same computation to validate the one time password.</p><p>In the example shown in the screenshot above, the code is <strong>672812</strong>.</p><p>Obviously, client &amp; server clocks must be synchronized. One time passwords remain valid for a period of 30 seconds. The message #timeRemaining tells you how far along we are in the current period.</p><p>Here is a functional unit test in commented example style for the interaction we just described.</p><pre><strong>GoogleAuthenticatorTests&gt;&gt;testClientServer</strong><br> | server sharedSecret client |<br> <em>“Server side an authenticator is set up, <br>  initialized with a secret”</em><br> server := GoogleAuthenticator new.<br> server randomSecret.<br> <em>“The shared secret is exchanged <br>  between the server and the client”</em><br> sharedSecret := server base32Secret.<br> <em>“The client sets up its authenticator, <br>  initialized with the shared secret”</em><br> client := GoogleAuthenticator new.<br> client base32Secret: sharedSecret.<br> <em>“Make sure we’re not too close <br>  to the end of the current period”</em><br> client timeRemaining &lt; 2 ifTrue: [ 2 seconds wait ].<br> <em>“From now on, both are in sync, <br>  generating the same one time passwords”</em><br> <strong>self</strong> assert: client next equals: server next.<br> <strong>self</strong> assert: client next equals: server next</pre><h3>Algorithm</h3><p>Let’s explore the actual computation taking place from known initial values as seen in the following unit test.</p><pre><strong>GoogleAuthenticatorTests&gt;&gt;testSimple</strong><br> | time secret authenticator |<br> time := 1478167454.<br> secret := &#39;HXDMVJECJJWSRB3HWIZR4IFUGFTMXBOZ&#39;.<br> authenticator := GoogleAuthenticator new.<br> authenticator base32Secret: secret.<br> authenticator time: time.<br> <strong>self</strong> assert: authenticator nextPadded equals: &#39;488676&#39;.</pre><p>Google Authenticator uses the following parameters:</p><ul><li>SHA1 HMAC</li><li>80 bit (10 byte) key/secret</li><li>64 bit (8 byte) time based message size</li><li>6 digit code length</li><li>30 seconds period</li><li>external key/secret representation in Base32</li></ul><p>TOTP does a computation based on 2 values: a key/secret and a time value.</p><p>Here the key/secret, externally represented (Base32 encoded) is the string ‘HXDMVJECJJWSRB3HWIZR4IFUGFTMXBOZ’. First we have to decode it.</p><pre>Base32Encoder new<br>  decode: &#39;HXDMVJECJJWSRB3HWIZR4IFUGFTMXBOZ&#39;.</pre><p>This gives us the byte array #[61 198 202 164 130 74 109 40 135 103 178 51 30 32 180 49 102 203 133 217] (or in hex 3DC6CAA4824A6D288767B2331E20B43166CB85D9).</p><p>For the time value the <a href="https://en.wikipedia.org/wiki/Unix_time">Unix time</a> is used, integer divided by the period. In our example, we’re using a fixed value, 1478167454 (corresponding to 2016–11–03T10:04:14Z).</p><pre>1478167454 // 30.</pre><p>The result, 49272248, is then converted to a byte array of size 8.</p><pre>49272248 asByteArrayOfSize: 8.</pre><p>This conversion gives us #[0 0 0 0 2 239 213 184] (or in hex 0000000002EFD5B8).</p><p>Now, the key/secret and the time based message are used to compute a SHA1 HMAC digest. This crypto algorithm is a standard part of Pharo.</p><pre>(HMAC on: SHA1)<br> key: #[61 198 202 164 130 74 109 40 135 103<br>        178 51 30 32 180 49 102 203 133 217];<br> digestMessage: #[0 0 0 0 2 239 213 184].</pre><p>This results in the following digest: #[127 67 212 219 236 88 54 168 158 177 36 112 177 244 112 88 224 169 130 215] (or in hex 7F43D4DBEC5836A89EB12470B1F47058E0A982D7).</p><p>Next, the RFC describes a way to convert (or truncate) this 20 byte array into a 32-bit integer. The first half byte (nibble) of the last of these 20 bytes is used as an offset to select 4 consecutive bytes. These 4 bytes are then converted to an integer, of which the top bit is cleared.</p><pre>#[127 67 212 219 236 88 54 168 158 177<br>   36 112 177 244 112 88 224 169 130 215]<br>  last bitAnd: 16rF.</pre><p>This gives us 7 as offset. As Pharo uses 1-based array indexing we add 1.</p><pre>#[127 67 212 219 236 88 54 168 158 177<br>   36 112 177 244 112 88 224 169 130 215]<br>  copyFrom: 8 to: 11.</pre><p>The 4 byte sub array is thus #[168 158 177 36] (hex A89EB124). Now we can apply the last truncation step.</p><pre>#[168 158 177 36] asInteger bitAt: 32 put: 0. </pre><p>This gives us 681488676. The final step is to reduce this number to the required code length, 6.</p><pre>681488676 \\ 1e6.</pre><p>And so we finally arrive at <strong>488676</strong>, the correct TOTP value !</p><h3>Source Code</h3><p>The fully documented source code with unit tests can be found on GitHub in a project called <a href="https://github.com/svenvc/GoogleAuthenticator">GoogleAuthenticator</a>.</p><p>This project also contains the source code and tests of <strong>Base32Encoder</strong>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9c59c606a572" width="1" height="1" alt=""><hr><p><a href="https://medium.com/concerning-pharo/the-code-behind-google-authenticator-9c59c606a572">The code behind Google Authenticator</a> was originally published in <a href="https://medium.com/concerning-pharo">Concerning Pharo</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Speeding up factorial computation by changing the order of multiplications]]></title>
            <link>https://medium.com/concerning-pharo/speeding-up-factorial-computation-by-changing-the-order-of-multiplications-f4da3a5576da?source=rss-69bbb011558e------2</link>
            <guid isPermaLink="false">https://medium.com/p/f4da3a5576da</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[pharo]]></category>
            <dc:creator><![CDATA[Sven VC]]></dc:creator>
            <pubDate>Tue, 24 May 2016 07:42:09 GMT</pubDate>
            <atom:updated>2016-09-28T10:53:30.847Z</atom:updated>
            <content:encoded><![CDATA[<p>This is a story about a small, seemingly innocent code change that speeds up a very simple computation. It is pretty magical and serves as an example of how things are not always what they seem.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*RuxaPPPrL6K09eF4pFhISw.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/@kvedula">Kamesh Vedula</a></figcaption></figure><h3>Factorial</h3><p>If you know a bit about programming and mathematics, you probably know factorial. The factorial of a non-negative integer number <strong>n</strong>, denoted as <strong>n!</strong>, is defined as the product of all positive integers less than or equal to n. In formula form,</p><pre>n! = n x (n-1) x (n-2) x (n-3) x … x 3 x 2 x 1</pre><p>According to the convention for an empty product, the factorial of zero is one, <strong>o! = 1</strong></p><p>Factorial is a popular example to explain recursion, as it is defined by the following two relations,</p><pre>factorial(0) = 1</pre><pre>factorial(n) = n * factorial(n-1)</pre><p>In programming languages that are powerful enough to transparently switch between different integer representations, factorial is often used to demonstrate this ability — the result grows <em>very</em> quickly.</p><p>The largest factorial that fits in a 32-bit integer is 12! and the largest one that fits in a 64-bit integer is 20! — after that you get an overflow.</p><p>In <a href="http://pharo.org/">Pharo</a>, factorial is built in, as a message understood by Integer objects. Computing 32! is seamless,</p><pre>32 factorial</pre><pre>  =&gt; 263130836933693530167218012160000000</pre><h3>The standard implementation</h3><p>The easiest, clearest and most beautiful way to implement factorial is to directly translate the recursive definition. This is the implementation that we find in Pharo.</p><pre><strong>Integer&gt;&gt;#factorial</strong><br>  <em>“Answer the factorial of the receiver.”</em></pre><pre>  <strong>self</strong> = 0 ifTrue: [ <strong>^</strong> 1 ].<br>  <strong>self</strong> &gt; 0 ifTrue: [ <strong>^</strong> <strong>self</strong> * (<strong>self</strong> — 1) factorial ].<br>  <strong>self</strong> error: <em>‘Not valid for negative integers’</em></pre><p>This does n multiplications, going down in the recursion and coming back out of it, starting with the smallest number building up towards a potentially large result.</p><p>Yes, replacing the recursion with a simple iteration will be a bit faster, but it won’t make much difference.</p><p>This implementation works quite well in practice. When you actually try it, looking at the result, and thus rendering such huge numbers, usually takes longer than the computation itself. How large a number are we talking about, you might ask ?</p><pre>10000 factorial numberOfDigits</pre><pre>  =&gt; 35660</pre><p>This last number is not even representable as a double IEEE floating point number, as it is ~ 2.846259681 x 10 ^ 35659.</p><h3>The faster implementation</h3><p>Here is a slightly different way to compute the product of all numbers between 1 and n. We can reformulate factorial using the more general product of all integers between n and m. Here is our particular implementation.</p><pre><strong>Integer&gt;&gt;#productTo: upper</strong><br><em>  “Return the product of all integers between <br>   the receiver (exclusive) and upper (inclusive).”<br></em> <br>  | delta product middle |<br>  delta := upper — <strong>self</strong>.<br>  delta &lt;= 0 ifTrue: [ <strong>^</strong> CollectionIsEmpty signal ].<br>  <strong>^</strong> delta &lt; 5<br>      ifTrue: [ <br>        product := upper.<br>        1 to: delta — 1 do: [ :each | <br>          product := (upper — each) * product ].<br>        product ]<br>      ifFalse: [ <br>        middle := (<strong>self</strong> + upper) bitShift: -1.<br>        (<strong>self</strong> productTo: middle) * (middle productTo: upper) ]</pre><p>We start by taking the difference, delta, between the upper and lower bounds of the interval for which we have to do the multiplications. If the delta is zero or negative we signal an exception — the interval is empty. Remember, the lower bound is exclusive.</p><p>In the most general case, the ifFalse block at the bottom, we apply a divide and conquer strategy. We split the interval in the middle and call ourselves recursively on each half, multiplying both sub results and we’re done.</p><p>If the difference is small, here less than 5, we don’t bother and just do the necessary multiplications. For example, if the delta between n and m is is 3, we compute and return m x (m-1) x (m-2).</p><p>As you can see, we do the same multiplications, just in a different order.</p><h3><strong>The speedup</strong></h3><p>Let’s run some benchmarks to see how our new implementation compares to the original one, and to test the new implementation for correctness.</p><pre>(1 to: 16) collect: [ :each | <br>  | n t1 t2 f1 f2 |<br>  n := 2 ** each.<br>  t1 := [ f1 := n factorial ] timeToRun.<br>  t2 := [ f2 := 1 productTo: n ] timeToRun.<br>  self assert: f1 = f2.<br>  { n. t1. t2 } ]</pre><p>We compute the factorials of the first 16 powers of 2 and see how long each computation took. This is the result.</p><pre>an Array(<br>  an Array(2 0:00:00:00 0:00:00:00)<br>  an Array(4 0:00:00:00 0:00:00:00)<br>  an Array(8 0:00:00:00 0:00:00:00)<br>  an Array(16 0:00:00:00 0:00:00:00) <br>  an Array(32 0:00:00:00 0:00:00:00) <br>  an Array(64 0:00:00:00 0:00:00:00)<br>  an Array(128 0:00:00:00 0:00:00:00)<br>  an Array(256 0:00:00:00 0:00:00:00)<br>  an Array(512 0:00:00:00 0:00:00:00)<br>  an Array(1024 0:00:00:00 0:00:00:00)<br>  an Array(2048 0:00:00:00.003 0:00:00:00)<br>  an Array(4096 0:00:00:00.011 0:00:00:00.001)<br>  an Array(8192 0:00:00:00.047 0:00:00:00.006)<br>  an Array(16384 0:00:00:00.097 0:00:00:00.026)<br>  an Array(32768 0:00:00:01.198 0:00:00:00.115)<br>  an Array(65536 0:00:00:07.913 0:00:00:00.535))</pre><p>As you can see, from the moment the computation takes longer than our clock’s resolution, the new implementation is faster, by about a factor 10 to about a factor 20. Let’s concentrate on some of the larger numbers.</p><pre>#(25000 50000 75000 100000) collect: [ :each | <br>  | t1 t2 f1 f2 |<br>  t1 := [ f1 := each factorial ] timeToRun.<br>  t2 := [ f2 := 1 productTo: each ] timeToRun.<br>  self assert: f1 = f2.<br>  { each. t1. t2 } ]</pre><p>Which gives us similar results.</p><pre>an Array(<br>  an Array(25000 0:00:00:00.787 0:00:00:00.065)<br>  an Array(50000 0:00:00:04.550 0:00:00:00.433)<br>  an Array(75000 0:00:00:17.679 0:00:00:00.852)<br>  an Array(100000 0:00:01:12.878 0:00:00:01.623))</pre><p>How is that even possible, since it is basically doing the same number of multiplications ?</p><h3>The explanation</h3><p>The reason our alternative implementation is faster is that it tries to multiply numbers that are of similar size, specifically when the numbers become large.</p><p>The original implementation builds up a large number by multiplying the running product by each consecutive small number in the interval.</p><p>The divide and conquer strategy of the alternative implementation creates a tree of intervals, to gradually grow the size of the numbers in a more balanced way.</p><p>And why would that be faster ?</p><p>The answer lies in how large (or big) integer arithmetic, specifically <a href="https://en.wikipedia.org/wiki/Multiplication_algorithm#Fast_multiplication_algorithms_for_large_inputs">multiplication</a>, is implemented. The standard algorithms to do this are variants of the <a href="https://en.wikipedia.org/wiki/Karatsuba_algorithm">Karatsuba algorithm</a> which is more efficient when multiplying two large numbers of comparable size.</p><p>By modifying the order in which our multiplications are done, we use that fact to our advantage.</p><h3>More about factorial</h3><p>The improved <a href="https://en.wikipedia.org/wiki/Factorial">factorial</a> implementation presented here is in no way the best one. If you want to explore the many possible implementations of this simple function, consult the incredible detailed <a href="http://www.luschny.de/math/factorial/FastFactorialFunctions.htm">Fast Factorial Functions website</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f4da3a5576da" width="1" height="1" alt=""><hr><p><a href="https://medium.com/concerning-pharo/speeding-up-factorial-computation-by-changing-the-order-of-multiplications-f4da3a5576da">Speeding up factorial computation by changing the order of multiplications</a> was originally published in <a href="https://medium.com/concerning-pharo">Concerning Pharo</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Tiny, yet so beautiful]]></title>
            <link>https://medium.com/concerning-pharo/tiny-yet-so-beautiful-1ef5149c910e?source=rss-69bbb011558e------2</link>
            <guid isPermaLink="false">https://medium.com/p/1ef5149c910e</guid>
            <category><![CDATA[pharo]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Sven VC]]></dc:creator>
            <pubDate>Wed, 09 Mar 2016 21:58:45 GMT</pubDate>
            <atom:updated>2016-03-10T19:22:46.475Z</atom:updated>
            <content:encoded><![CDATA[<h4>The smallest piece of great Pharo code</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*TH1xuJ2_657OHbA8EvIPQw.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/glencarrie">Glen Carrie</a></figcaption></figure><p>How do you introduce an unknown, alternative programming language to other developers ? One way to do so is by showing lots of small examples. That is what we did in <a href="https://medium.com/concerning-pharo/elegant-pharo-code-bb590f0856d0#.ngp7avab4">Elegant Pharo Code — Beautiful &amp; Powerful One-liners, Expressions and Snippets</a>.</p><p>But as noted at the end of that article, real <a href="http://pharo.org/">Pharo</a> programs are different. Object oriented programming and design are hard to teach, with code living in multiple places.</p><p>Another approach is to show and explain actual, coherent examples. That is the primary subject of most articles in the <a href="https://medium.com/concerning-pharo">Concerning Pharo</a> publication.</p><p>Real working code also contains some boilerplate code. This housekeeping stuff often obfuscates the really beautiful parts.</p><p><em>What if we turned the question upside down ?</em></p><blockquote>What would be the smallest piece of great Pharo code ? Something tiny yet very beautiful ?</blockquote><p>Here is one gem that I found and instantly fell in love with.</p><h3>Bits &amp; Bytes</h3><p>First, we need to set the context. Even though Pharo is a high level programming language, it is surprisingly well suited to do binary coding, to manipulate bits &amp; bytes. A typical task is to work with <a href="https://en.wikipedia.org/wiki/Mask_(computing)">bit masks</a>. Classic bitwise operations like bitwise AND, OR and NOT do of course exist on Integers. But directly accessing individual bits is just as easy.</p><pre>| mask |<br>mask := 0.<br>mask := mask bitAt: 3 put: 1.<br>mask := mask bitAt: 7 put: 1.<br>mask</pre><p>We start the mask all zero and then set the 3rd and 7th bit to 1 (Pharo counts from 1, Integers are immutable). The result is 68, or 1000100 in binary. Retrieving a bit is even simpler.</p><pre>mask bitAt: 3</pre><p>When interpreted as a flag, a Boolean property, a bit value of 1 is considered to be <strong>true</strong>, while a bit value of 0 is considered to be <strong>false</strong>. In our models in Pharo, flags will be Booleans, so we need to do a simple conversion.</p><pre>| mask |<br>mask := 0.<br>mask := mask bitAt: 3 <br>             put: (<strong>self</strong> flag1 ifTrue: [1] ifFalse: [0]).<br>mask := mask bitAt: 7 <br>             put: (<strong>self</strong> flag2 ifTrue: [1] ifFalse: [0]).<br>mask</pre><p>We are assuming our model object has #flag1 and #flag2 methods returning a Boolean value. The conversion when testing a bit is trivial.</p><pre>(mask bitAt: 3) = 1</pre><p>Although it is cool that we can write the inline test to do the conversion, it is not very elegant, ugly even. What if we introduced helper methods to clean things up a bit ?</p><pre><strong>flag1AsBit</strong></pre><pre>  ^ <strong>self</strong> flag1 ifTrue: [1] ifFalse: [0]</pre><p>Now we can write</p><pre>| mask |<br>mask := 0.<br>mask := mask bitAt: 3 put: <strong>self</strong> flag1AsBit.<br>mask := mask bitAt: 7 put: <strong>self</strong> flag2AsBit.<br>mask</pre><p>This is better, but it still is a lot of work, adding an additional method for each flag. And the test remains so silly, right ?</p><h3>Booleans</h3><p>Here is how Booleans are implemented in Pharo. They are objects like everything else, <em>of course</em>. There is an abstract class <strong>Boolean</strong> with two concrete subclasses, <strong>True</strong> and <strong>False</strong>.</p><pre>Object<br>   +--&gt; Boolean<br>           +--&gt; True<br>           +--&gt; False</pre><p>These classes have no state, they are pure behaviour: they react differently to different messages. The system makes sure that there is only one instance of each these two classes, <em>ever</em>, aptly named <strong>true</strong> and <strong>false</strong>. These are like predefined constants (and 2 out of the 5 reserved words in the language). They are instances respectively of classes True and False, that have common<br>superclass Boolean.</p><p>All logic is defined as messages sent to these classes. For example, consider the implementation of <strong>#and:</strong></p><pre><strong>Boolean&gt;&gt;and: alternativeBlock</strong> <br>  &quot;Non evaluating conjunction -- If the receiver is true, answer the value of the argument, alternativeBlock; otherwise answer false without evaluating the argument&quot;</pre><pre>  <strong>self</strong> subclassResponsibility<br></pre><pre><strong>False&gt;&gt;and: alternativeBlock</strong> <br>  &quot;Non evaluating conjunction -- answer with false since the receiver is false&quot;</pre><pre>  ^ <strong>self<br></strong></pre><pre><strong>True&gt;&gt;and: alternativeBlock</strong> <br>  &quot;Non evaluating conjunction -- answer the value of alternativeBlock since the receiver is true&quot;</pre><pre>  ^ alternativeBlock value</pre><p>The superclass implementation is the design specification. The 2 concrete implementations are elegantly simple. Note that <em>alternativeBlock</em> is a piece of delayed code, a lambda or closure, denoted using square brackets. And before you ask, yes, the compiler does some magic to maintain a good level of performance.</p><h3>The Gem</h3><p>Now we can finally introduce the tiny piece of code that is so beautiful: the <strong>#asBit</strong> message.</p><pre><strong>Boolean&gt;&gt;asBit</strong><br>  &quot;Convert me to an Integer using 1 for true and 0 for false&quot;</pre><pre>  <strong>self</strong> subclassResponsibility<br></pre><pre><strong>False&gt;&gt;asBit<br>  </strong>&quot;Return Integer 0 since I am false&quot;</pre><pre><strong>  </strong>^ 0<br></pre><pre><strong>True&gt;&gt;asBit<br></strong>  &quot;Return Integer 1 since I am true&quot;</pre><pre><strong>  </strong>^ 1</pre><p>“Is that it ?”, you are probably asking. Yes it is (I told you it was tiny).</p><h3>Why is this so great ?</h3><p>Let me tell you the various reasons why I think this is so cool. There are technical, design, philosophical and even social reasons.</p><h4>It is tiny</h4><p>It is so small, trivial even, that it is easily overlooked. Yet it is really great.</p><p>The message name is also short, to the point, easy to understand and follows common conventions.</p><h4>It solves our problem</h4><p>Given this method, we can rewrite our problematic code and live by the DRY (don’t repeat yourself) rule.</p><pre>| mask |<br>mask := 0.<br>mask := mask bitAt: 3 put: <strong>self</strong> flag1 asBit.<br>mask := mask bitAt: 7 put: <strong>self</strong> flag2 asBit.<br>mask</pre><p>In our model we keep working with booleans, yet at the moment we need a bit representation, a simple unary message does the necessary conversion.</p><p>The new method is certainly generic enough to be useful in many situations and thus deserves its place in the main system.</p><h4>It is impossible in most programming languages</h4><p>In most other programming languages, primitive types are not real objects, they are special. But even if some languages make them real objects, they do not allow you to add behaviour to them, they are closed to extensions.</p><p>In Pharo you can add methods to system classes, in a clean way, which gives you great power to build the system you want, by extending what is already available.</p><h4>It uses method dispatch</h4><p>Notice how the test is completely gone ! Where did it do ? How is that even possible ?</p><p>It uses Pharo’s method dispatch, the core technique where an identical message invokes different implementations depending on the class of the receiver. Sending #asBit to true results in the system selecting one implementation, while sending it to false results in another. This is also called polymorphism.</p><p>Making effective use of method dispatch is key to great object designs. Excessive use of tests, conditionals and especially case statements is often an indication that your design could be improved.</p><h4>It touches the core of object programming</h4><p>Object programming is about sending messages between objects, more so than it is about data abstractions. Behaviour is more important than internal structure.</p><p>In a good object program, your objects are intelligent beings that know how to do what you want them to do. And if they don’t, you extend their behaviour. Objects are much more than data structures.</p><p>Manipulating objects using their pre-existing API often leads to repetitive code. Extending their behaviour can solve this elegantly.</p><h4>It shows that even stateless objects are powerful</h4><p>As mentioned before, note how the 3 classes involved have no state, no instance variables. Still, their behaviour does really matter, makes a functional difference and solves actual problems.</p><h4>It shows that even constant methods are powerful</h4><p>Not only are the Boolean objects stateless, the #asBit method itself is constant as well, it just returns a constant value, no matter what. And again, the implementation does really matter, makes a functional difference and solves actual problems.</p><h4>It has cool comments</h4><p>Documentation is necessary. In this particular case, talking about ‘me’ and ‘I’ or your ‘own value’ is pretty cool, philosophically, isn’t it ?</p><h4>It has unit tests</h4><p>Pharo has a large suite of unit tests that are run each time something changes, to ensure that no functionality is being broken. Even a method as simple as #asBit needs its unit tests, see the 2 implementations of #testAsBit who basically assert the following 2 statements:</p><pre><strong>self</strong> assert: <strong>true</strong> asBit = 1</pre><pre><strong>self</strong> assert: <strong>false</strong> asBit = 0</pre><p>Unit tests also constitute documentation that is automatically maintained and thus always correct.</p><h4>It was added recently</h4><p>This code was added at the very end of 2012 and became part of the main Pharo image ever since. This is important because it means Pharo is constantly evolving.</p><h4>It is only in active use in Pharo</h4><p>The way Boolean works in Pharo is inherited by all Smalltalk implementations. The #asBit method is only in active use in Pharo, though it could be added to any of them. As a 21st century, fast evolving, actively developed system, Pharo accepts and uses good ideas like this one almost daily.</p><h4>It was added by cool people</h4><p>Pharo is being developed by a diverse, international community. One of our mottos is ‘<em>Pharo is yours</em>’, meaning that you are encouraged to see it that way, to contribute even small improvements.</p><p>In this particular case, Igor Stasenko (from Ukraine) and Camillo Bruni (from Switzerland) added this while working together at INRIA’s RMOD Lab in France. They probably did not invent it themselves, but they knew very well how cool it was, that they should use it and that it deserved its place in the image. Thanks guys !</p><blockquote>For all of the above reasons, this tiny piece of code is an excellent example of truly great Pharo code.</blockquote><h3>The End</h3><p>I hope you enjoyed this story. I hope I was able to make my point. Thank you for your time.</p><blockquote>Do you have a favourite piece of code ?</blockquote><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1ef5149c910e" width="1" height="1" alt=""><hr><p><a href="https://medium.com/concerning-pharo/tiny-yet-so-beautiful-1ef5149c910e">Tiny, yet so beautiful</a> was originally published in <a href="https://medium.com/concerning-pharo">Concerning Pharo</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[An Implementation of Unicode Normalization]]></title>
            <link>https://medium.com/concerning-pharo/an-implementation-of-unicode-normalization-7c6719068f43?source=rss-69bbb011558e------2</link>
            <guid isPermaLink="false">https://medium.com/p/7c6719068f43</guid>
            <category><![CDATA[unicode]]></category>
            <category><![CDATA[normalization]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Sven VC]]></dc:creator>
            <pubDate>Wed, 17 Feb 2016 08:55:15 GMT</pubDate>
            <atom:updated>2016-02-18T14:33:15.003Z</atom:updated>
            <content:encoded><![CDATA[<p>Streaming NFC, NFD, NFKC &amp; NFKD, normalization QC and normalization preserving concatenation.</p><p><em>Sven Van Caekenberghe, Henrik Sperre Johansen</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*SjCP-3HNvgHSdtlyqeKRkg.png" /></figure><p><a href="https://en.wikipedia.org/wiki/Unicode">Unicode</a> is an industry-wide international <a href="http://unicode.org/">standard</a> for the consistent encoding, representation, and handling of text expressed in almost all of the world’s writing systems. Unicode’s unifying character set contains tens of thousands of entries covering 129 modern and historic scripts, as well as multiple symbol sets.</p><p>The standard also includes related items, such as character properties, rules for normalization, decomposition, collation, rendering, and bidirectional display order. Taken together, this covers a complex set of functionality for internationalization and localization of computer software.</p><p>This article describes one implementation of normalization in a high level language. The sections <em>Decomposition</em> and <em>Composition</em> are very technical and can be skipped.</p><blockquote>The appendix describes how to get and install the actual software.</blockquote><h3>What is normalization and why do we need it ?</h3><p>Unicode, being a unifying character set, contains characters that allow similar results to be expressed in different ways.</p><p>A simple example in common languages (the Latin letter é, <a href="https://en.wikipedia.org/wiki/%C3%89">e-acute</a>) is</p><pre>LATIN SMALL LETTER E WITH ACUTE [U+00E9]</pre><p>which can equivalently be written as</p><pre>LATIN SMALL LETTER E [U+0065] + COMBINING ACUTE ACCENT [U+0301]</pre><p>The former being a composed normal form, the latter a decomposed normal form. In visible glyphs, we can write this relationship as</p><blockquote><strong>é = e + ´</strong></blockquote><p>Not only characters with diacritical marks have multiple representations. For instance, the ellipsis character of 3 dots, is equivalent to 3 separate dots in a row, if we are interested in semantic meaning.</p><pre>HORIZONTAL ELLIPSIS [U+2026]<br>FULL STOP [U+002E] + FULL STOP [U+002E] + FULL STOP [U+002E]</pre><blockquote>… = . + . + .</blockquote><p>Some characters have more than 2 representations. The Ångström symbol Å can be written in three ways.</p><pre>ANGSTROM SIGN [U+212B]<br>LATIN CAPITAL LETTER A WITH RING ABOVE [U+00C5]<br>LATIN CAPITAL LETTER A [U+0041] + COMBINING RING ABOVE [U+030A]</pre><p>It is possible to give many more examples in almost any language, most of which we would not understand. It is for example possible and quite common to have multiple combining marks on a single base letter.</p><p>Given that similar text can be written in different ways, we have a problem. How can we determine if two strings are equal ? How can we find a substring in a string ?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*bsgJ15EJcrlPe6wytst29g.jpeg" /><figcaption>Photo by Romain Vignes</figcaption></figure><p>The answer is to convert the string to a well-known form. This is <strong>normalization</strong>. Unicode normalization is a set of rules based on tables and algorithms. It defines two kinds of normalization equivalence: canonical and compatible.</p><p>Code point sequences that are defined as <strong>canonically equivalent</strong> are assumed to have the same appearance and meaning when printed or displayed. Our first and third examples above (é and Å) are examples of canonical mappings.</p><p>Code point sequences that are defined as <strong>compatible</strong> are assumed to have possibly distinct appearances, but the same meaning in some contexts. Our second example above (…) is an example of a compatible mapping. Other examples are different representation of the decimal digit 1, like the Roman numeral I or a 1 in a circle. In one sense they are the same, in another sense they are quite different.</p><p>Compatible equivalence is a superset of canonical equivalence. In other words each canonical mapping is also a compatible one, but not the other way around.</p><p><strong>Composition</strong> is the process of combining marks with base letters (multiple code points are replaced by single points whenever possible). <strong>Decomposition</strong> is the process of taking already composed characters apart (single code points are split into multiple ones). Both processes are recursive.</p><p>An additional difficulty is that the normalized ordering of multiple consecutive combining marks must be defined. This is done using a concept called the Canonical Combining Class or CCC, a Unicode character property.</p><p>All combined, four normalization forms are defined:</p><ol><li><strong>NFD</strong> — canonical decomposition and ordering</li><li><strong>NFC</strong> — composition after canonical decomposition and ordering</li><li><strong>NFKD</strong> — compatible decomposition and ordering</li><li><strong>NFKC</strong> — composition after compatible decomposition and ordering</li></ol><pre>     <strong>Decomposition Composition</strong><br><strong>NFD</strong>    canonical     no<br><strong>NFKD</strong>   compatible    no<br><strong>NFC</strong>    canonical     yes<br><strong>NFKC</strong>   compatible    yes</pre><h3>Unicode Character Data</h3><p>The Unicode standard consists of a large number of documents as well as a set of tables. The <a href="http://www.unicode.org/reports/tr44/">Unicode Character Database</a> is the most important one. The first step was to make this data, all 29,189 entries as of version 8 of the Unicode standard, available for usage and exploration.</p><p>You can send the message #unicodeCharacterData to Character or Integer objects. This will return an instance of UnicodeCharacterData when found. You can then query this object for more information.</p><pre>65 unicodeCharacterData</pre><pre>$A unicodeCharacterData</pre><p>An inspector extension helps to interpret and understand the different fields.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*kBCP-qTBAFGE49Dr4kQ0YQ.png" /></figure><p>The screenshot above shows, in the left pane, what inspecting the Unicode character data of our example letter é looks like. The right pane shows a large glyph view of the character involved.</p><p>Most standard fonts only support a limited subset of Unicode. Many code points will be displayed using the “missing” glyph (a vertical rectangle with a diagonal cross, a bit like ⊠). For better coverage, try switching to a font with wide Unicode support, such as <a href="https://en.wikipedia.org/wiki/Arial_Unicode_MS">Arial Unicode MS</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9WKCwbkyTJpu9uN_JBhO7w.png" /></figure><p>Inspecting the decomposition of a character is as simple as clicking on that field on the left, with the decomposed elements showing on the right.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*hdhKMr1D1yHkcNzYitp59A.png" /></figure><p>There is only a single inspector extension, yet it is quite useful in many situations. The previous screenshot shows the elements (i.e. characters) of the string <em>Ångström</em> being inspected on the left as Unicode character data details on the right.</p><p>We also added an extension to our environment’s search system to allow you to look up characters by name:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*W3xINA8P9DjOHbM2ePvCEQ.png" /></figure><p>The user entered <em>horizontal el</em> in the search field and got 5 entries back, the first one of which is previewed.</p><h3>Implementation Choices</h3><p>After building some prototypes and trying a couple of approaches, we arrived at our current implementation choices. We will implement all fundamental algorithms to work on code points (Unicode scalar values). As much as possible, we will implement them as operations on streams.</p><p>The reason is that in practice this feel right while offering maximal flexibility towards the future (other string or character representations). With a few conversion streams, and some convenience methods to help create these (#unicodeCodePoints and #unicodeCharacters), it becomes trivial to switch representations while preserving stream semantics.</p><pre>&#39;abc&#39; readStream unicodeCodePoints upToEnd<br>  =&gt; #(97 98 99)</pre><pre>#(97 98 99) readStream unicodeCharacters upToEnd<br>  =&gt; &#39;abc&#39;</pre><h3>Decomposition</h3><p>The decomposition procedure is basically to look up each code point in the Unicode Character Database, and replace it with its decomposed sequence, if any. This must be done recursively.</p><p>The next steps depend on a character code point property called the <strong>Canonical Combining Class</strong> (#canonicalCombiningClass or #ccc). When the CCC is zero, the character code point is called a starter (#isStarter), else it is a non-starter (#isStarter not).</p><p>After the first decomposition phase, all sequences of non-starters in the decomposition, including non-starters up to the next starter in the input, must be sorted according to their Canonical combining class.</p><p>We define a new class, <strong>UnicodeDecomposingReadStream</strong>, that wraps a code point read stream named <em>input</em>. The idea is that each time you read from it, it will decompose what it reads from its input. Since decomposition expands, we need a small internal FIFO <em>buffer</em>.</p><pre>Object subclass: #<strong>UnicodeDecomposingReadStream</strong><br>  instanceVariableNames: ‘input buffer’<br>  classVariableNames: ‘’<br>  category: ‘Unicode-Normalization’</pre><p>The basic read stream operation is next, which is equivalent in this case to returning the next code point after decomposition. We return and remove the first element from the internal buffer, filling it if necessary. EOF is implemented by returning nil.</p><pre><strong>next</strong><br>  buffer ifEmpty: [ self nextChunk ].<br>  buffer ifEmpty: [ ^ nil ].<br>  ^ buffer removeFirst</pre><p>Internally, the core operation is to get and fully decompose the next chunk of input, which we do into a buffer.</p><pre><strong>nextChunk</strong><br>  input atEnd<br>    ifFalse: [ <br>      self addMappingFor: input next.<br>      self addNonStarters ]</pre><p>Since we’ll be doing the additions to the buffer respecting the CCC order, we’re done. The first sub operation is abstract and has to be implemented by a concrete subclass.</p><pre><strong>addMappingFor:</strong> codePoint<br>  self subclassResponsibility</pre><p>The first concrete subclass is <strong>UnicodeNFDReadStream</strong> which implements this operation only when there is a canonical decomposition. When there is no applicable decomposition, the code point is added as is.</p><pre><strong>addMappingFor:</strong> codePoint<br>  | ucd |<br>  ucd := [ codePoint unicodeCharacterData ] <br>           on: NotFound do: [ ].<br>  (ucd notNil and: [ ucd hasCanonicalDecomposition ])<br>    ifTrue: [ <br>      ucd decompositionMappingDo: [ :each | <br>        self addMappingFor: each ] ]<br>    ifFalse: [ <br>      self addToBufferCccOrdered: codePoint ]</pre><p>The second concrete subclass is <strong>UnicodeNFKDReadStream</strong> which uses a slight variation. Here, both canonical and compatible mappings are applied.</p><pre><strong>addMappingFor:</strong> codePoint<br>  | ucd |<br>  ucd := [ codePoint unicodeCharacterData ] <br>           on: NotFound do: [ ].<br>  (ucd notNil and: [ ucd hasDecomposition ])<br>    ifTrue: [ <br>      ucd decompositionMappingDo: [ :each | <br>        self addMappingFor: each ] ]<br>    ifFalse: [ <br>      self addToBufferCccOrdered: codePoint ]</pre><p>Note the recursive invocation of #addMappingFor: in both cases.</p><p>Additions to the buffer are done by appending code points while maintaining CCC ordering. This is done by scanning from the end backwards until the correct insertion point is found.</p><pre><strong>addToBufferCccOrdered:</strong> codePoint<br>  | ccc index stop otherCCC |<br>  ccc := [ codePoint unicodeCharacterData ccc ] <br>           on: NotFound do: [ 0 ].<br>  index := buffer size.<br>  ccc = 0 <br>    ifFalse: [<br>      stop := false.<br>      [ index &gt; 0 &amp; stop not ] whileTrue: [ <br>        otherCCC := [ (buffer at: index) <br>                         unicodeCharacterData ccc ]<br>                      on: NotFound do: [ 0 ].<br>        ccc &lt; otherCCC<br>          ifTrue: [ index := index — 1 ]<br>          ifFalse: [ stop := true ] ] ].<br>  buffer add: codePoint afterIndex: index</pre><p>The second sub operation in getting the next chunk is to add any additional non-starters from the input, because it is possible that they have to be CCC reordered with what we already have in the buffer.</p><pre><strong>addNonStarters</strong><br>  | stop |<br>  stop := false.<br>  [ input atEnd | stop ] whileFalse: [ <br>    ([ input peek unicodeCharacterData isStarter not ]<br>         on: NotFound do: [ false ])<br>      ifTrue: [ self addMappingFor: input next ]<br>      ifFalse: [ stop := true ] ]</pre><p>These couple of methods fully implement the core of decomposition. Using it in its raw form consists of chaining a couple of read streams.</p><pre>&#39;élève&#39; readStream unicodeCodePoints <br>        unicodeNFD <br>        unicodeCharacters upToEnd<br>  =&gt; &#39;e´le`ve&#39;</pre><p>The above result shows the combining marks composed with a space, else they would not show clearly.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ehK5DH85TcVv4m0azookAg.jpeg" /><figcaption>Photo by Marcus dePaula</figcaption></figure><h3>Composition</h3><p>The elementary composition procedure operates between two starters, combining pairs, unless blocked. Combination is blocked when a code point with an out of order Canonical Combining Class interferes.</p><p>Because UnicodeCharacterData stores a mapping from a precomposed character code point to its constituents only, it is more efficient to precompute the reverse mapping. We create <strong>UnicodeComposer</strong> as a helper class.</p><pre>Object subclass: #<strong>UnicodeComposer</strong><br> instanceVariableNames: ‘combinations combiningCharacters’<br> classVariableNames: ‘Default’<br> category: ‘Unicode-Normalization’</pre><p>When necessary, the following initialization is invoked. A default instance of this class is cached in the <em>Default</em> class variable to avoid doing this process more than once.</p><pre><strong>initializeForComposition</strong><br>  combinations := IdentityDictionary new.<br>  combiningCharacters := IdentitySet new.<br>  UnicodeCharacterData database valuesDo: [ :each |<br>    each isPrimaryComposite ifTrue: [ | combination |<br>      combination := each decompositionMapping.<br>      <em>“combination first + combination second <br>         = each codePoint”</em><br>      combinations <br>        at: combination first <br>        ifPresent: [ :value | <br>          value at: combination second put: each codePoint ]<br>        ifAbsent: [ | value |<br>          value := IdentityDictionary new <br>                     at: combination second <br>                     put: each codePoint;<br>                     yourself.<br>          combinations at: combination first put: value ].<br>      combiningCharacters add: combination second ] ]</pre><p>Only primary composites are considered, these always map into two elements. The set of combining character will allow us to quickly determine whether a character can combine with another one. The combinations dictionary maps base characters with another dictionary, a map from combining character to the result.</p><p>Given the input e + ´ we find that ´ is indeed a combining character. Then we find that e can be a base for composition. This then gives us a map that includes ´ to é. Any of these conditions could be false and thus not lead to composition.</p><pre><strong>primaryCombinationOf:</strong> first <strong>and:</strong> second<br>  ^ (self isCombiningCharacter: second)<br>      ifTrue: [ <br>        self combinations <br>          at: first <br>          ifPresent: [ :compositions | <br>            compositions at: second ifAbsent: [ ] ] <br>          ifAbsent: [ ] ]</pre><p>We won’t go into the details here, but there is a Unicode code block of 11,184 code points that is algorithmically defined instead of being table driven: the <a href="https://en.wikipedia.org/wiki/Hangul_Syllables">Hangul Syllables</a>. Full test suite conformance can only be reached by fully implementing this part of the specification, which we did.</p><pre><strong>combinationOf:</strong> first <strong>and:</strong> second<br>  second ifNil: [ ^ nil ].<br>  ^ (self hangulCombinationOf: first and: second) <br>       ifNil: [ <br>         self primaryCombinationOf: first and: second ]</pre><p>The elementary public operation is to compose a buffer, consisting of an initial starter followed by CCC ordered non-starters, modifying it in place.</p><pre><strong>composeBuffer:</strong> buffer <br>  | lastCCC index ccc combination |<br>  lastCCC := 0.<br>  index := 2.<br>  [ index &lt;= buffer size ] whileTrue: [<br>    ccc := [ (buffer at: index) unicodeCharacterData ccc ]<br>             on: NotFound do: [ 0 ].<br>    combination := self combinationOf: buffer first <br>                        and: (buffer at: index).<br>    (combination notNil<br>        and: [ (lastCCC &lt; ccc) | (lastCCC = 0) ])<br>      ifTrue: [ <br>        buffer at: 1 put: combination.<br>        buffer removeAt: index ]<br>      ifFalse: [ <br>        index := index + 1. <br>        lastCCC := ccc ] ]</pre><p>We can now implement <strong>UnicodeComposingReadStream</strong> to process input chunk by chunk while composing each as a buffer. Each chunk will consist of an initial starter followed by CCC ordered non-starters and end with another starter. The last starter will become the initial starter for the next chunk.</p><pre>Object subclass: #<strong>UnicodeComposingReadStream</strong><br> instanceVariableNames: ‘input buffer first composer’<br> classVariableNames: ‘’<br> category: ‘Unicode-Normalization’</pre><p>Again, we wrap an <em>input</em> code point read stream and use a FIFO <em>buffer</em>. This time, start up is a bit more complicated and less elegant as the initial series of non-starters must be skipped — this is the role of <em>first</em>: to hold one of these non-starters until we are beyond that phase and have seen a starter, at which point it holds a special value. We hold the default instance of UnicodeComposer in <em>composer</em>.</p><pre><strong>next</strong><br>  self isFirstEmpty<br>    ifFalse: [ ^ self consumeFirst ].<br>  self shouldGetNextChunk <br>    ifTrue: [ self nextChunk ].<br>  self isFirstEmpty<br>    ifFalse: [ ^ self consumeFirst ].<br>  buffer ifEmpty: [ ^ nil ].<br>  ^ buffer removeFirst</pre><p>The basic processing step is to get a next chunk and compose it.</p><pre><strong>nextChunk</strong><br>  <em>“Initialize when needed, <br>   try putting first starter in buffer”</em><br>  first = #initialized <br>    ifFalse: [ <br>      self scanFirstStarter <br>        ifFalse: [ <em>“Non-starter is in first”</em> ^ self ] ].<br>  <em>“buffer = &lt;starter1&gt;”</em><br>  [<br>    self scanUntilStarter.<br>    “buffer = &lt;starter1&gt; … &lt;starter2&gt;”<br>    composer composeBuffer: buffer ]<br>      doWhileFalse: [ buffer size &gt; 1 or: [ input atEnd ] ]<br>  <em>“There has to be more than one element in the buffer <br>   unless we’re eof. Composition shrinks the buffer, <br>   sometimes recursively, but can need additional starters”</em></pre><p>The first phase is scanning for the first starter, immediately ansering non-starters.</p><pre><strong>scanFirstStarter</strong><br>  | current |<br>  <em>“Find the first starter in input to use, <br>   put it in buffer and return true.<br>   Else put the non-starter in first and return false.<br>   Switch to #initialized once we’ve seen <br>   the first starter or when empty.”</em><br>  input atEnd ifFalse: [ <br>    current := input next.<br>    ([ current unicodeCharacterData isStarter ]<br>         on: NotFound do: [ false ])<br>       ifTrue: [ <br>         buffer addLast: current. <br>         first := #initialized. <br>         ^ true ]<br>       ifFalse: [ <br>         first := current. <br>         ^ false ] ].<br>  first := #inialized.<br>  ^ false</pre><p>Once in the second phase, we scan until a starter.</p><pre><strong>scanUntilStarter</strong><br>  | current |<br>  <em>“Put non-starters and the next starter from input <br>   in the buffer, if any”</em><br>  [ input atEnd ] whileFalse: [ <br>    current := input next.<br>    buffer addLast: current.<br>    ([ current unicodeCharacterData isStarter ]<br>         on: NotFound do: [ false ])<br>       ifTrue: [ ^ self ] ]</pre><p>Some smaller helper methods round out our implementation.</p><pre><strong>isFirstEmpty</strong><br>  ^ first isNil or: [ first = #initialized ]</pre><pre><strong>consumeFirst</strong><br>  | current |<br>  current := first.<br>  first := nil.<br>  ^ current</pre><pre><strong>shouldGetNextChunk</strong><br>  <em>“One element should remain in the buffer <br>   for the next iteration unless we’re eof”</em><br> <br>  ^ buffer isEmpty <br>      or: [ buffer size = 1 and: [ input atEnd not] ]</pre><p>Again, using composition in its raw form consists of chaining a couple of read streams.</p><pre>&#39;e´le`ve&#39; readStream unicodeCodePoints <br>          unicodeCompose <br>          unicodeCharacters upToEnd<br> =&gt; &#39;élève&#39;</pre><p>The above input shows the combining marks composed with a space, else they would not render clearly. To generate the correct input string you can evaluate the following expression.</p><pre>#(101 769 108 101 768 118 101) readStream <br>                               unicodeCharacters<br>                               upToEnd</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*q6OoLgl5DdVrS6Xz6OGY2A.jpeg" /><figcaption>Photo by Amador Loureiro</figcaption></figure><h3>Normal Forms</h3><p>The decomposed normal forms, <strong>NFD</strong> and <strong>NDKD</strong> are reached by decomposition alone. The example given at the end of the decomposition chapter is enough.</p><p>The composed normal forms, <strong>NFC</strong> and <strong>NFKC</strong> are the result of composition after decomposition. We can elegantly express this by chaining.</p><pre><strong>unicodeNFC</strong><br>  <em>“Return a UnicodeComposingReadStream over the receiver <br>   that streams over Integer code points composing them <br>   after decomposing them canonically”</em><br> <br>  ^ self unicodeNFD unicodeCompose</pre><pre><strong>unicodeNFKC</strong><br>  <em>“Return a UnicodeComposingReadStream over the receiver <br>   that streams over Integer code points composing them <br>   after decomposing them compatibly”</em><br> <br>  ^ self unicodeNFKD unicodeCompose</pre><h3>Normalization Quick Check</h3><p>The code described previously is relatively complex and slow. By first checking if normalization is really needed, things can be sped up quite a bit.</p><p>The Normalization Quick Check procedure consists of a simple algorithm that consults a number of tables. For each normalization form, character code points are classified in three values: <strong>yes</strong>, it can occur as is in this normalization form, <strong>no</strong>, it cannot ever, or <strong>maybe</strong>, we don’t know.</p><pre><strong>normalizationQuickCheck:</strong> property <strong>forCodePoint:</strong> codePoint<br>  <em>“Return #Y (yes), #N (no) or #M (maybe) for property, <br>   #NFC_QC, #NFD_QC, #NFKC_QC or #NFKD_QC”</em><br> <br>  ^ (self normalizationQuickCheck at: property) <br>       at: codePoint ifAbsent: [ #Y ]</pre><pre><strong>normalizationQuickCheck:</strong> property <strong>forCodePointStream:</strong> stream<br>  | result lastCCC codePoint ccc check |<br>  result := #Y.<br>  lastCCC := 0.<br>  [ stream atEnd ] whileFalse: [<br>    codePoint := stream next.<br>    ccc := [ codePoint unicodeCharacterData ccc ]<br>             on: NotFound do: [ 0 ].<br>    (lastCCC &gt; ccc and: [ ccc ~= 0 ]) ifTrue: [ ^ #N ].<br>    check := self normalizationQuickCheck: property<br>                  forCodePoint: codePoint.<br>    check = #N ifTrue: [ ^ #N ].<br>    check = #M ifTrue: [ result := #M ]. <br>    lastCCC := ccc ].<br>  ^ result</pre><h3>Normalization High Level Interface</h3><p>To operate on Strings, a small tool, <strong>UnicodeNormalizer</strong>, offers a high level interface. This tool makes use of the Quick Check and some other properties to optimize the operations a bit, preventing unnecessary work. Next is the code for the canonical variants, the compatible variants are similar.</p><pre><strong>toNFC:</strong> string<br>  <em>“Return the NFC of string, <br>   the canonical composition normal form”</em><br> <br>  (self isAlreadyNFC: string) ifTrue: [ ^ string ]. <br>  ^ string readStream unicodeCodePoints <br>           unicodeNFC unicodeCharacters upToEnd</pre><pre><strong>isAlreadyNFC:</strong> string<br>  <em>“Latin1 strings are always in NFC”</em><br>  ^ string isByteString or: [ <br>      (UnicodeCharacterData normalizationQuickCheck: #NFC_QC<br>                            forString: string) = #Y ]</pre><pre><strong>toNFD:</strong> string<br>  <em>“Return the NFD of string, <br>   the canonical decomposition normal form”</em><br> <br>  (self isAlreadyNFD: string) ifTrue: [ ^ string ]. <br>  ^ string readStream unicodeCodePoints <br>           unicodeNFD unicodeCharacters upToEnd</pre><pre><strong>isAlreadyNFD:</strong> string<br>  <em>“ASCII strings are always in NFD”</em><br>  ^ (string isByteString and: [ string isAsciiString ]) <br>      or: [ (UnicodeCharacterData <br>               normalizationQuickCheck: #NFD_QC<br>               forString: string) = #Y ]</pre><h3>Normalization Preserving Concatenation</h3><p>Extracting sub strings out of a normalized string maintains normalization. The reverse, string concatenation, does not. Characters at the join point might interact and compose. Consider the following:</p><blockquote>éle + `ve = élève</blockquote><p>The last e of the first string and the first `of the second string combine under NF(K)C. Note also the two strings of size 3 combine to a string of size 5.</p><p>The algorithm to efficiently concatenate while maintaining a specified normalization form is implemented in <strong>UnicodeConcatenator</strong>. The idea is to search backward from the end of the first string and forward from the beginning of the second string until we find so called stable characters which cannot interact. Then the middle section is normalized. Care is taken to minimize copying and allocation.</p><pre><strong>concatenateString:</strong> first <strong>with:</strong> second<br>  | lastStable firstStable middle result |<br>  first ifEmpty: [ ^ second ].<br>  second ifEmpty: [ ^ first ].<br>  lastStable := first findLast: <br>                  self isStableCharacterBlock.<br>  lastStable = 0 ifTrue: [ lastStable := 1 ].<br>  firstStable := second findFirst: <br>                   self isStableCodePointBlock.<br>  firstStable = 0 ifTrue: [ firstStable := second size ].<br>  (lastStable = first size and: [ firstStable = 1 ])<br>    ifTrue: [ ^ first , second ].<br>  middle := (first copyFrom: lastStable to: first size) <br>              , (second copyFrom: 1 to: firstStable).<br>  middle := self normalizeString: middle.<br>  result := first class new: (lastStable — 1 + <br>                              middle size + <br>                              second size — firstStable).<br>  result <br>    replaceFrom: 1 <br>      to: lastStable — 1 <br>      with: first <br>      startingAt: 1;<br>    replaceFrom: lastStable <br>      to: lastStable + middle size — 1 <br>      with: middle <br>      startingAt: 1;<br>    replaceFrom: lastStable + middle size <br>      to: result size <br>      with: second<br>      startingAt: firstStable + 1. <br>  ^ result</pre><pre><strong>isStableCharacterBlock</strong><br>  | quickCheckProperty |<br>  quickCheckProperty := self quickCheckProperty.<br>  ^ [ :each | <br>      ([ each unicodeCharacterData isStarter ] <br>           on: NotFound do: [ true ]) and: [ <br>         (UnicodeCharacterData <br>            normalizationQuickCheck: quickCheckProperty<br>            forCodePoint: each codePoint) = #Y ] ]</pre><p>The tool has to be initialized to a specific normal form before use.</p><pre>UnicodeConcatenator forNFC <br>    concatenateString: &#39;abce&#39; <br>    with: &#39;´def&#39;<br>  =&gt; &#39;abcédef&#39;</pre><h3>Conformance Tests</h3><p>There is a test file in the standard specification for testing conformance to normalization. No less than 18,593 individual input sequences and their resulting 4 normal forms are part of this test suite.</p><p>The Pharo Unicode project passes all these tests 100% !</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*WQn3A4vCpVo2nSGeIWjcyQ.png" /></figure><h3>Usage Guidelines</h3><p>In practice, you will chose one of the 4 normal forms for all of your strings. When text enters your application, you will have to make sure it is converted to your chosen normalization form.</p><p>Studies seem to indicate that more than 99% of all text on the internet is in NFC, making it the most popular normal form.</p><p>Should you use the safe form of concatenation ? To be absolutely safe, yes, but in practice probably not all the time.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/471/1*v7aNftxNwrHrmEtIIFzydw.png" /></figure><h3>References</h3><ul><li><a href="https://en.wikipedia.org/wiki/Unicode">https://en.wikipedia.org/wiki/Unicode</a> — The main Wikipedia article about Unicode</li><li><a href="https://en.wikipedia.org/wiki/Unicode_equivalence">https://en.wikipedia.org/wiki/Unicode_equivalence</a> — The article about normalization (equivalence)</li><li><a href="http://unicode.org/">http://unicode.org</a> — The main website discussing the official standard</li><li><a href="http://www.unicode.org/versions/Unicode8.0.0/ch03.pdf">http://www.unicode.org/versions/Unicode8.0.0/ch03.pdf</a> — The relevant part of the core standard itself, chapter 3, in particular 3.11 about normalization forms, but all the rest for key definitions and concepts</li><li><a href="http://www.unicode.org/reports/tr15/">http://www.unicode.org/reports/tr15/</a> — The annex describing normalization forms and several additional algorithms as well as implementation guidelines</li><li><a href="http://www.unicode.org/reports/tr44/">http://www.unicode.org/reports/tr44/</a> — The annex describing the Unicode Character Database</li></ul><h3>Appendix: The Pharo Unicode project</h3><p><a href="http://pharo.org/">Pharo</a>, a unique immersive live development environment has pretty good support for Unicode. You can read more about the current situation in the first part of the <a href="http://files.pharo.org/books/enterprisepharo/book/Zinc-Encoding-Meta/Zinc-Encoding-Meta.html">Character Encoding and Resource Meta Description</a> chapter of the Enterprise Pharo book.</p><p>The goal of the Pharo Unicode project is to gradually improve and expand Unicode support in Pharo. Much work remains to be done and contributions are more than welcome.</p><p>The code discussed in this article is available from <a href="http://smalltalkhub.com/">SmalltalkHub</a> in a project called <a href="http://www.smalltalkhub.com/#!/~Pharo/Unicode">Unicode</a>. It was written for Pharo 4 and 5.</p><p>The easiest way to load the code is by using the <strong>Configuration Browser</strong> or <strong>Pharo Project Catalog</strong>. Search for <em>Unicode</em> and click <em>Install stable version</em>. You can load the code manually using its Metacello configuration.</p><pre>Gofer it<br>  smalltalkhubUser: &#39;Pharo&#39; project: &#39;Unicode&#39;;<br>  configuration;<br>  loadStable.</pre><p>Database files will be loaded automatically, on-demand, either from a URL over the internet or from a local file cache (extract <a href="http://www.unicode.org/Public/UNIDATA/UCD.zip">UCD.zip</a> next to your image). Processed datasets are then kept in your Pharo image.</p><p>Alternatively, you can <strong>download a prebuilt image</strong> containing everything as the latest successful build artifact from the Pharo Contribution CI job called <a href="https://ci.inria.fr/pharo-contribution/job/Unicode/">Unicode</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7c6719068f43" width="1" height="1" alt=""><hr><p><a href="https://medium.com/concerning-pharo/an-implementation-of-unicode-normalization-7c6719068f43">An Implementation of Unicode Normalization</a> was originally published in <a href="https://medium.com/concerning-pharo">Concerning Pharo</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Pharo Days 2016]]></title>
            <link>https://medium.com/concerning-pharo/pharo-days-2016-c52fe4d7caf?source=rss-69bbb011558e------2</link>
            <guid isPermaLink="false">https://medium.com/p/c52fe4d7caf</guid>
            <category><![CDATA[pharo]]></category>
            <category><![CDATA[programming-languages]]></category>
            <dc:creator><![CDATA[Sven VC]]></dc:creator>
            <pubDate>Wed, 09 Dec 2015 14:39:08 GMT</pubDate>
            <atom:updated>2016-03-08T09:07:58.930Z</atom:updated>
            <content:encoded><![CDATA[<h4>March 31 &amp; April 1, Namur, Belgium</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*QbFTcWNsJbghuJqHNaze3A.jpeg" /><figcaption>Location: Cercle de Wallonie, Avenue de la Vecquée 21, B-5000 Namur</figcaption></figure><p><strong>Mark your calendar</strong>: on Thursday March 31 &amp; Friday April 1 we are organising the Pharo Days 2016. This year we moved the location to Namur, Belgium, just a bit south of Brussels, at the very beautiful location of the ‘Cercle de Wallonie’ overlooking the river Meuse.</p><blockquote>We’ll update this page moving forward. You can ask questions on any of the Pharo mailing lists or you can <a href="/service/mailto:board@pharo.org">email the Pharo Board</a>.</blockquote><p>Join the Pharo community for the Pharo Days 2016. Meet your online colleagues, programmers and hackers in real life and experience how much you can pick up in just two days. Learn about key technologies, talk to core developers and other users, pair program and contribute to Pharo. Have fun and enjoy yourself.</p><h3>Schedule</h3><p>Each day has a similar schedule. The morning consists of a handful of twenty minute <strong>tech talks</strong>, the afternoon is an <strong>open pair programming workspace, coding sprint</strong> and free <strong>demo room</strong>.</p><h4>Thursday March 31</h4><p>08:30–09:00 — Registration and Welcome</p><p>09:00–09:20 — <strong>Welcome</strong> (Stéphane D)<br>09:20–09:40 — <strong>Finalizing Pharo 5 </strong>(Stéphane D — Marcus D)<br>09:40–09:45 — Q &amp; A<br>09:45–10:15 — <strong>GT’s</strong> <strong>Moldable Tools </strong>(Andrei C)<br>10:15–10:20 — Q &amp; A</p><p>10:20–10:40 — Break</p><p>10:40–11:00 —<strong>Reflectivity In Practice</strong> (Marcus D)<br>11:00–11:05 — Q &amp; A<br>11:05––11:25 — <strong>Data Formats &amp; Protocols </strong>(Sven VC)<br>11:25–11:30 — Q &amp; A<br>11:30–11:50 —<strong>Unified FFI </strong>(Esteban L)<br>11:50–11:55 — Q &amp; A</p><p>12:00–13:30 — Lunch</p><p>13:30–14:30 — <strong>How To Contribute To Pharo</strong> (Marcus D)<br>14:30–18:00 — Coding Sprint 1 + Free Open Pair Programming</p><p>13:30–16:00 — Getting Started with Pharo Workshop</p><p>19:00–21:00 — Social Event &amp; Lunch</p><h4>Friday April 1</h4><p>08:45–09:00 — Welcome</p><p>09:00–09:30 — <strong>Pharo Community Update</strong> (Stéphane D)<br>09:30–09:50 — <strong>Seaside 3 </strong>(Johan B)<br>09:50–09:55 — Q &amp; A<br>09:55–10:15 — <strong>Using Git For Source Code Management</strong> (Esteban L)<br>10:15–10:20 — Q &amp; A</p><p>10:20–10:40 — Break — Project Expo</p><p>10:40–11:00 — <strong>What You Should Know About Spur </strong>(Esteban L)<br>11:00–11:05 — Q &amp; A<br>11:05–11:25 — <strong>Bloc: Towards a vector-based GUI </strong>(Aliaksei S)<br>11:25–11:30 — Q &amp; A<br>11:30–11:50 — <strong>Plans for Pharo 6 </strong>(Marcus D)<br>11:50–11:55 — Q &amp; A</p><p>12:00–13:30 — Lunch</p><p>13:30–14:30 — Free Presentations — Show Your Project<br>14:30–18:00 — Coding Sprint 2 + Free Open Pair Programming</p><h3>Tech Talks</h3><p>The Tech Talks are short and fast paced overviews and demos of things you can do with Pharo. Here are some more details about each of them.</p><p>Tech Talk 1 — <strong>Finalizing Pharo 5</strong></p><p>We are in the final weeks of the development of Pharo 5. Learn about everything that happened.</p><p>Tech Talk 2 — <strong>GT’s</strong> <strong>Moldable Tools</strong></p><p>The triad of GT Inspector, GT Spotter and GT Debugger not only offer new tools, they introduce a new approach to moldable tools and combine to great effect with minimal effort.</p><p>Tech Talk 3 — <strong>Reflectivity In Practice</strong></p><p>New possibilities in reflectivity can now be used to gain real world advantages in day to day development.</p><p>Tech Talk 4 — <strong>Data Formats &amp; Protocols</strong></p><p>Talking to the outside world and understanding that conversation is a fundamental capability of any practical software tool. Luckily Pharo understands some of the most common data formats as well as some common protocols.</p><p>Tech Talk 5 — <strong>Unified FFI</strong></p><p>Integrating with C libraries from Pharo is changing towards a new Unified FFI. Get up to speed on what is new.</p><p>Tech Talk 6 — <strong>Seaside 3</strong></p><p>Seaside is moving forward while being a stable framework for building real world web applications.</p><p>Tech Talk 7 — <strong>Using Git For Source Code Management</strong></p><p>Discover how easy it is to use Git as your source code management tool. A hands on practical guide.</p><p>Tech Talk 8 — <strong>What You Should Know About Spur</strong></p><p>With Pharo 5, we are moving to the new Spur VM architecture. The facts, the details and the possibilities.</p><p>Tech Talk 9 — <strong>Bloc: Towards a vector-based graphical user interface</strong></p><p>Take a time-machine journey to see the future of Pharo’s graphical framework. Discover current status, find out latest news and explore our future plans.</p><p>Tech Talk 10 — <strong>Plans for Pharo 6</strong></p><p>Once Pharo 5 is released, we’ll start the Pharo 6 development. Get up to speed on some of the plans for that release.</p><h3>Sprints</h3><p>A Pharo Sprint is an activity where a number of developers get together to resolve issues and contribute to the system. There will be two sprints, each time in the afternoon. For the Pharo Days we will start the sprints with an introduction and overview of the Pharo development process. Learn about slices, continuous integration, the monkey, the git export and the CI build process.</p><h3>Getting Started with Pharo Workshop</h3><p>In the afternoon of the first day there will be a ‘Getting Started with Pharo’ tutorial for those who feel their basic practical knowledge and skills of working with Pharo needs a boost. Expect the level of the ‘Pharo by Example’ book, we’ll start easy and then go fast.</p><h3>Open Pair Programming</h3><p>It is natural and productive to sit together with someone else to do some pair programming and hacking. It is amazing how much you can learn from other Pharo developers. On the Pharo Days we make explicit room for this activity.</p><h3>Free Demo Room</h3><p>Events like the Pharo Days are an ideal opportunity to show what you have been working on. For this there will be a continuous free demo room, where a table and a presentation board give you a little platform to show us your work.</p><h3>Pricing</h3><p>The Pharo Days are a two day event with catering included (2 lunches, 1 diner, drinks and snacks) in a nice environment with full facilities (main room, auxiliary rooms, office furtniture and wireless network).</p><p>€ 199 — Regular<br>€ 149 — For individual Pharo Association Members<br>€ 89 — For individual Pharo Gold Association Members<br>€ 89 — For Pharo Consortium Members (1, 2 or 4 for bronze, silver or gold)<br>€ 39 — Students (including diner)</p><h3>Registration</h3><p>For official registration we are using <a href="http://www.eventbrite.com/e/pharo-days-2016-tickets-22454533113">EventBrite</a>. You can buy tickets using PayPal and hence any credit card. If absolutely necessary, you can opt for an off line payment. Please register on time.</p><blockquote><a href="http://www.eventbrite.com/e/pharo-days-2016-tickets-22454533113">&gt;&gt; Goto to the registration page.</a></blockquote><p>For social registration you can use <a href="http://doodle.com/poll/rsc86cqzxbgwr9tr">Doodle</a>. Spread the word: <a href="http://pharodays2016.pharo.org/">http://pharodays2016.pharo.org</a>.</p><h3>Accommodation</h3><p><a href="https://en.wikipedia.org/wiki/Namur">Namur</a> is a medium sized city in Belgium with plenty of options for accommodation, like Hotels and B&amp;B’s. Here are a couple of links that should get you started when searching for a place to stay:</p><ul><li><a href="https://www.google.be/maps/search/Hotels/@50.4438797,4.8318124,14z/data=!4m11!2m10!3m6!1sHotels!2sCercle+de+Wallonie,+Avenue+de+la+Vecqu%C3%A9e+21,+5000+Namur!3s0x47c1998142465f57:0x8981b81fcf569a15!4m2!1d4.849322!2d50.4438469!5m2!5m1!1s2016-03-31">Google Search</a></li><li><a href="https://www.tripadvisor.fr/Hotels-g188663-Namur_The_Ardennes_Wallonia-Hotels.html">TripAdviser</a></li><li><a href="http://www.namurtourisme.be/hebergement.php?page=hotels">Official Tourist Website</a></li><li><a href="https://www.airbnb.com/s/Namur--Belgium?guests=&amp;checkin=03%2F31%2F2016&amp;checkout=04%2F01%2F2016&amp;ss_id=v0voame5&amp;source=bb&amp;s_tag=0c56F67G">Airbnb</a></li></ul><p>Feel free to ask more questions on the mailing lists.</p><p>Pharo Days were already organised multiple times in the past, first in 2011, then in 2012, 2013 &amp; 2015. If you’re interested, you can have a look at <a href="https://medium.com/concerning-pharo/pharo-days-2015-6336d6ee2a23#.vm35p5th0">the Pharo Days 2015 page</a>. At the top there are links to videos and slides.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/471/1*v7aNftxNwrHrmEtIIFzydw.png" /></figure><p>The Pharo Days 2016 are organised by the <a href="http://pharo.org/">Pharo Community</a>, the Pharo Board, the <a href="http://consortium.pharo.org/">Pharo Consortium</a> and the <a href="http://association.pharo.org/">Pharo Association</a> with support from <a href="http://www.inria.fr/">INRIA</a> and <a href="http://esug.org/">ESUG</a>.</p><h3>Pharo Zen</h3><p><em>Our values and convictions are condensed in this simple list.</em></p><p>Magic only at the right place.<br>Messages are our vocabulary.<br>Easy to understand, easy to learn from, easy to change.<br>Perfection can kill movement.<br>Classes structure our vocabulary.<br>Better a set of small polymorphic classes than a large ugly one.<br>Simplicity is the ultimate elegance.<br>Quality is an emerging property.<br>Simple processes to support progress.<br>Objects all the way down.<br>Learning from mistakes.<br>Abstraction and composition are our friends.<br>A system with robust abstractions that a single person can understand.<br>There is no unimportant fix.<br>Examples to learn from.<br>Tests are important but can be changed.<br>Communication is key.<br>Polymorphism is our esperanto.<br>One step at a time.<br>Explicit is better than implicit.<br>Fully dynamic and malleable.<br>Beauty in the code, beauty in the comments.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c52fe4d7caf" width="1" height="1" alt=""><hr><p><a href="https://medium.com/concerning-pharo/pharo-days-2016-c52fe4d7caf">Pharo Days 2016</a> was originally published in <a href="https://medium.com/concerning-pharo">Concerning Pharo</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Pharo @ Beta Nine]]></title>
            <link>https://medium.com/concerning-pharo/pharo-beta-nine-59ee972d321a?source=rss-69bbb011558e------2</link>
            <guid isPermaLink="false">https://medium.com/p/59ee972d321a</guid>
            <dc:creator><![CDATA[Sven VC]]></dc:creator>
            <pubDate>Mon, 01 Jun 2015 15:10:27 GMT</pubDate>
            <atom:updated>2015-06-03T13:31:09.807Z</atom:updated>
            <content:encoded><![CDATA[<p><a href="http://www.beta9.be/">Beta Nine</a> is a software engineering company from Hasselt, Belgium. Founded in 1996, our main activity is advanced software development and consultancy in object, inter/intranet and Java technology.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/321/1*JBIy98Jx6HoxGN77D9XIMA.jpeg" /></figure><p>Since a couple of years we became a product company. We build, operate and commercialise the <a href="http://t3-platform.net/">T3 Platform</a>, a vehicle track &amp; trace and fleet management SaaS solution, sold internationally through a number of partners.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/225/1*PE8odwtu6M1Ngy14sx69Pg.jpeg" /></figure><p>Today, there are about 10.000 paying subscriptions to the platform, accessed by hundreds of customers and users via a number of web applications and services — 24/7/365.</p><h2>Technology</h2><p>Ultimately, what counts for the — paying — customer is that a product solves a problem. The combination of effectiveness, reliabiliy, quality, features, service and price defines a successful commercial product.</p><p>The customer does not care what technology is used to build a product. That is a good thing, because it allows the developers to choose those technologies that help them to deliver a good product.</p><p>Since 2010, <a href="http://www.pharo.org/">Pharo</a> is an important part of our technology stack.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/471/1*8YhkaeGF1s5Xc1pnqqVyMg.png" /></figure><p>Pharo’s pure dynamic object oriented language and immersive live environment focused on simplicity and feedback makes it ideal for both development and deployment of web applications and web services.</p><blockquote>Here are a number of success stories of Pharo at Beta Nine.</blockquote><h2>T3 Easy REST Back End</h2><p>T3 Easy is the entry level variant of the main product that we offer. It is a web application with the client part completely written in JavaScript, loaded as a single web page. The front end communicates directly with a REST back end written in Pharo.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*KzZAD3GFYM5d5S82FHckbg.png" /></figure><p><a href="http://zn.stfx.eu/zn/index.html">Zinc HTTP Components</a> with the Zinc-REST and NeoJSON frameworks are used to offer a robust, secure standard REST API for the JavaScript client web app to use. The application is deployed on a headless Linux server using 4 stateless images load balanced by <a href="http://en.wikipedia.org/wiki/Apache_HTTP_Server">Apache</a>. T3 Easy has been part of our commercial portfolio since 2011.</p><h2>T3 Protocol Proxies</h2><p>The T3 Platform supports a variety of GPRS/GPS hardware devices installed in vehicles. Although T3 has is own native communication protocol, many devices use their own protocol. The protocol proxies allow for devices with foreign protocols to connect to the platform.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*J2QdVaE-5cY88OA0K8XNvg.png" /></figure><p>Developing and deploying low level binary protocols over UDP and TCP using a high level interactive live environment is very efficient and infinitely more pleasant than any of the classic approaches. The different proxies are deployed in a single image on a headless Linux server. The image is serving about one thousand connections and hundreds of thousands of messages a day with an uptime of several weeks. Pharo based protocol proxies have been in production use since 2012.</p><h2>T3 Mobile<br>Web Application</h2><p>The main interface to T3 is a desktop class web application. To more easily access a subset of that functionality via mobile devices, smartphones and tablets, a specific T3 Mobile web application was built from scratch.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*UAkk_bNaHkjzbJmdv-tITQ.png" /></figure><p>T3 Mobile is a responsive mobile first web application written completely using the excellent <a href="http://pharo.pharocloud.com/bootstrap">Seaside/Bootstrap</a> framework in Pharo. It is using Zinc HTTP Components as the server adaptor for Seaside and as the client to talk to the REST back end. It is deployed as 2 stateful images behind <a href="http://en.wikipedia.org/wiki/Nginx">Nginx</a>, which does static resource serving, sticky session proxying and HTTPS termination. <a href="http://en.wikipedia.org/wiki/Memcached">Memcached</a> is used to handle some shared session info. T3 Mobile is in production use since April 2014.</p><h2>T3 Data Mining</h2><p>Running a commercial SaaS product at a non-trivial scale requires lots of housekeeping and bookkeeping. Correctly invoicing complex and changing usage of a software platform is a challenge. This can be seen as a data mining problem.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*NPWpFfVGyFieb202DoZ1LQ.png" /></figure><p>T3 exposes its functionality as a REST API that can easily be accessed using Zinc HTTP Components’ client and NeoJSON. We modelled part of the domain, but leave a large part as just Dictionaries and Arrays. Scripting, calculating usage and generating reports is much easier and fun in Pharo. Since 2010, every single monthly invoice for T3 was based on numbers computed in Pharo.</p><h2>T3 Product Development</h2><p>Evolving a commercial product and responding to a wide variety of customer requests often requires quickly prototyping and deploying small extension applications.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*G5pEVzME4nWOyg0WywDDnw.png" /></figure><p>Given a codebase that already supports the applications above and effectively models the domain, Pharo is an ideal environment for explorative product development and has been used succesfully for this purpose many times over.</p><h2>Supporting Pharo</h2><p>We understand the value proposition of the open source and community supported platform that <a href="http://www.pharo.org/">Pharo</a> is: it contains many man years of effort by some of the best software developers out there.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/486/1*ItuPBHP-6V09WXNvqsB4Lw.png" /></figure><p>That is why we give back: first and foremost by developing and maintaining a number of <a href="http://stfx.eu/">open source libraries</a> (Zinc HTTP Components, Zinc-WebSockets, Zinc-SSO, Zinc-REST, Zinc-AWS, Zodiac TLS/SSL Streams, NeoJSON, NeoCSV, STON, ZTimestamp and Stamp), but also by being a <a href="http://consortium.pharo.org/">Pharo Consortium</a> and <a href="http://association.pharo.org/">Pharo Association</a> member and by serving on the <a href="http://pharo.org/about">Pharo Board</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=59ee972d321a" width="1" height="1" alt=""><hr><p><a href="https://medium.com/concerning-pharo/pharo-beta-nine-59ee972d321a">Pharo @ Beta Nine</a> was originally published in <a href="https://medium.com/concerning-pharo">Concerning Pharo</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[LampSort Revisited, Visualised]]></title>
            <link>https://medium.com/concerning-pharo/lampsort-revisited-visualised-6652055ef858?source=rss-69bbb011558e------2</link>
            <guid isPermaLink="false">https://medium.com/p/6652055ef858</guid>
            <dc:creator><![CDATA[Sven VC]]></dc:creator>
            <pubDate>Sun, 18 Jan 2015 18:17:08 GMT</pubDate>
            <atom:updated>2015-01-20T09:29:14.051Z</atom:updated>
            <content:encoded><![CDATA[<h4>Combining Object Logging &amp; Agile Visualisation</h4><p>To understand or study an algorithm, a piece of code or an application you start by reading the code. Many developers add logging to code as a way to look at what is happening. In a live environment like <a href="http://www.pharo.org/">Pharo</a> you can also use the debugger to step through code.</p><p>Traditional logging is either too coarse and misses information, or too detailed and floods the reader with information. In both cases the output consists of dead strings that you cannot look into or that you cannot ask any more questions.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*EmFt6N36omX9uzCnRsvtSQ.png" /><figcaption>An excerpt from system.log — Note the mix of formats</figcaption></figure><p>The debugger is very detailed, but only for what is on the stack at the position where you are halted. It can only move forward in time in small steps. Often you step too far or you seem to be clicking like crazy.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/845/1*FVugaN4bw3tgvwBFkrjnSg.png" /><figcaption>The Pharo debugger</figcaption></figure><blockquote>This article suggests another approach. By combining object logging, agile visualisation and advanced tools, you can get amazing insight into your code, easily.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*k43GrfZ00aHmmwrZZsYwKw.jpeg" /></figure><h4>LampSort</h4><p>As an example, we’ll be using <a href="https://medium.com/concerning-pharo/lampsort-a-non-recursive-quicksort-implementation-4d4891b217bd">LampSort, a non-recursive QuickSort implementation</a>. Please follow the link to read up about this cool variant.</p><p>In what follows, we are interested in visualising a sorting algorithm and simplify code to that end. Try to image how you can go from here to a more complex, real world application.</p><h4>Object Logging</h4><p>Unlike traditional logging where you generate strings, object logging is a technique where we <strong>reify</strong> what we want to log into a real object. Think of this object as representing the event that happened.</p><p>It is up to you to decide what to log and which information to include. There are no rules. Don’t be cheap, it is hard to predict what will be needed later on. What is not included is lost forever.</p><p>In real applications you will probably already have most of the data that you want to include at hand, so the cost is acceptable. Just be careful with structure sharing and destructive modifications.</p><p>Once the log object is created, you should send it off to whoever is interested, if anyone. It turns out we already have a pretty good mechanism for doing that in Pharo, namely <strong>Announcements</strong>. We might as well use that to <strong>emit</strong> log event objects.</p><h4>LampSortLogEvent</h4><p>We begin by setting up a class hierarchy of log objects. Here is our root class, <strong>LampSortLogEvent</strong>.</p><pre>Announcement subclass: <strong>#LampSortLogEvent</strong><br>  instanceVariableNames: ‘data’<br>  classVariableNames: ‘LampSortLogEventAnnouncer’<br>  category: ‘LampSortVisualized-LogEvents’</pre><p>Each log event will hold a copy of the data array that we are sorting, at the moment the log event was emitted.</p><pre><strong>data: sequenceableCollection</strong><br>  data := sequenceableCollection copy</pre><p>On our class side we’ll maintain a unique instance of an Announcer, the one we’ll be using to notify interested consumers of log events that are emitted.</p><pre><strong>announcer</strong><br>  ^ <strong>self</strong> class announcer</pre><pre><strong>emit</strong><br>  <strong>self</strong> announcer announce: <strong>self</strong></pre><p>And on the class side we have a lazy initialisation for the Announcer.</p><pre><strong>announcer</strong><br>  ^ LampSortLogEventAnnouncer <br>      ifNil: [ <br>        LampSortLogEventAnnouncer := Announcer new ]</pre><p>Here is one of the concrete log event subclasses, <strong>LampSortPivotSelected</strong>. It feels natural to name these using past tense. This particular event is emitted when the algorithm selects a pivot from a sub interval of the data, which is always the first element of the interval is this particular version of the algorithm.</p><pre>LampSortLogEvent subclass: <strong>#LampSortPivotSelected</strong><br>  instanceVariableNames: ‘interval’<br>  classVariableNames: ‘’<br>  category: ‘LampSortVisualized-LogEvents’</pre><p>It is important to give each log event a good <strong>printOn</strong>: implementation. This main printed representation will be used in several context later on. Make it clear, to the point and not too long.</p><pre><strong>pivotIndex</strong><br>  ^ interval first</pre><pre><strong>pivotValue</strong><br>  ^ data at: <strong>self</strong> pivotIndex</pre><pre><strong>printOn: stream</strong><br>  stream <br>    &lt;&lt; ‘Selected pivot ‘; print: <strong>self</strong> pivotValue; <br>    &lt;&lt; ‘ @ ‘; print: <strong>self</strong> pivotIndex;<br>    &lt;&lt; ‘ from ‘; print: interval</pre><p>Along the same lines we define a couple of others, one for each of the important steps in the LampSort algorithm:</p><ul><li><strong>LampSortPartitioned</strong> (left, right)</li><li><strong>LampSortSwapped</strong> (oneIndex, anotherIndex)</li><li><strong>LampSortIntervalSelected</strong> (interval, intervals)</li><li><strong>LampSortIntervalRemoved</strong> (interval, intervals)</li><li><strong>LampSortIntervalsAdded</strong> (newIntervals, intervals)</li></ul><p>The last 3 will inherit from <strong>LampSortIntervalsEvent</strong> because they all hold the intevals set. It is a bit of work, but with the code generation tools you can automate most of the coding.</p><p>Here is how the log event objects are used.</p><pre>LampSortPivotSelected new<br>  data: data;<br>  interval: interval;<br>  emit</pre><p>Just make a new instance, set the necessary properties and send it emit.</p><h4>LampSortInstrumented</h4><p>We are now ready to use the log event objects that we defined. The original LampSort implementation consists of just 2 elegant methods, <strong>sort</strong> and <strong>partition:</strong> — read <a href="https://medium.com/concerning-pharo/lampsort-a-non-recursive-quicksort-implementation-4d4891b217bd">the original article explaining LampSort</a> for an detailed explanation.</p><p>To maintain that easy to read version, we are going to create a new one, <strong>LampSortInstrumented</strong>, where we introduce helper methods for each important step in the algorithm.</p><pre><strong>sort</strong><br>  | intervals one |<br>  intervals := Set with: (1 to: data size).<br>  [ intervals isEmpty ]<br>    whileFalse: [ <br>      one := <strong>self</strong> selectIntervalFrom: intervals.<br>      one size &gt; 1<br>        ifTrue: [ <br>          <strong>self</strong> <br>            joinIntervals: intervals <br>            with: (<strong>self</strong> partition: one) ].<br>          <strong>self</strong> removeInterval: one from: intervals ]</pre><pre><strong>partition: interval</strong><br>  | pivot index |<br>  pivot := <strong>self</strong> selectFirstElementAsPivot: interval.<br>  <strong>self</strong> swap: interval first with: interval last.<br>  index := interval first.<br>  interval first to: interval last — 1 do: [ :each | <br>    (data at: each) &lt; pivot<br>      ifTrue: [ <br>        <strong>self</strong> swap: each with: index.<br>        index := index + 1 ] ].<br>  <strong>self</strong> swap: interval last with: index.<br>  ^ <strong>self</strong> splitInterval: interval around: index</pre><p>In each helper methods, we’ll do 2 things:</p><ol><li>create and emit a log event</li><li>do whatever has to be done in that step</li></ol><p>All in all, there are 6 helper methods.</p><pre><strong>selectIntervalFrom: intervals</strong><br>  | selection |<br>  selection := intervals anyOne.<br>  LampSortIntervalSelected new<br>    data: data;<br>    intervals: intervals;<br>    interval: selection;<br>    emit.<br>  <strong>^</strong> selection</pre><pre><strong>removeInterval: interval from: intervals</strong><br>  LampSortIntervalRemoved new<br>    data: data;<br>    intervals: intervals;<br>    interval: interval;<br>    emit.<br>  intervals remove: interval</pre><pre><strong>selectFirstElementAsPivot: interval</strong><br>  LampSortPivotSelected new<br>    data: data;<br>    interval: interval;<br>    emit.<br>  <strong>^</strong> data at: interval first</pre><pre><strong>swap: oneIndex with: anotherIndex</strong><br>  LampSortSwapped new<br>    data: data;<br>    oneIndex: oneIndex;<br>    anotherIndex: anotherIndex;<br>    emit.<br>  data swap: oneIndex with: anotherIndex</pre><pre><strong>splitInterval: interval around: pivotIndex</strong><br>  | left right |<br>  left := interval first to: pivotIndex — 1.<br>  right := pivotIndex + 1 to: interval last.<br>  LampSortPartitioned new<br>    data: data;<br>    left: left;<br>    right: right;<br>    emit.<br>  <strong>^</strong> Array with: left with: right</pre><p>Note how in the last method, the left and right intervals were already at hand, created as part of the algorithm. We just use them in the log object at no cost.</p><p>This concludes the instrumentation of our algorithm. In your own applications, you can do what you want to make the generation of log events as convenient as possible.</p><h4>Textual Logging</h4><p>One aspect of object logging is that it is compatible with traditional, textual logging. How ? By using the print representations. Here is how to log to the classic Pharo Transcript.</p><pre>LampSortLogEvent announcer <br>  subscribe: LampSortLogEvent <br>  do: [ :event | Transcript crShow: event ].</pre><pre>LampSortInstrumented new sort: #(7 12 3 20 5 8 2) copy.</pre><p>We subscribe to all Announcements that are subclasses of LampSortLogEvent and show their printed representation on the Transcript. This is the result.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/503/1*waqOkR6hUWBqHcKRQY0yaQ.png" /></figure><p>We can use to same technique to append to a log file or the system log. In this simplified demo, our log event objects do not contain their own timestamp — this and any other relevant information is easy to add.</p><h4>Inspecting Log Events</h4><p>The standard <strong>GT-Inspector</strong> tool (part of <a href="http://gt.moosetechnology.org/">The Glamorous Toolkit</a>) makes it easy to look at Announcements generated by any Announcer, thus we can use it to look at our log event objects. Here is how to get started.</p><pre>LampSortLogEvent announcer inspect.</pre><pre>LampSortInstrumented new sort: #(7 12 3 20 5 8 2) copy.</pre><p>Inspect the LampSortLogEvent announcer and run the algorithm on an example array. The array gets copied because the algorithm sorts destructively in-place.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*wjU3cMvR7umgHauWs3KFWA.png" /></figure><p>We now have a tool to browse what happened.</p><p>The left pane shows each announcement that came in, most recent on top, oldest at the bottom. The time stamp is added automatically. Note how our print representation is used.</p><p>When you select an indivual log event, its details are shown in the right pane. You can see the data evolve.</p><p>By moving up and down in the list, you go effectively forward respectively backward in time. You can study in detail how the algorithm works.</p><blockquote>Now imagine being able to do this for your complex enterprise application.</blockquote><h4>Using an Object Log</h4><p>Hopefully, you can already see how log event objects might be useful in more complex situations. Here are two examples that show what a difference an object log makes.</p><p><em>How many swaps were executed when sorting a specific array?</em></p><pre>(OrderedCollection streamContents: [ :out |<br>  | subscription |<br>  subscription := LampSortLogEvent announcer <br>    subscribe: LampSortSwapped<br>    do: [ :event | out nextPut: event ].<br>  LampSortInstrumented new sort: #(7 12 3 20 5 8 2) copy.<br>  LampSortLogEvent announcer unsubscribe: subscription ]) <br>    size</pre><p><em>Answer</em><strong>: 12</strong></p><p>By subscribing to just one type of log event we effectively filter, which gives us the number of swaps. The log event class hierarchy is one dimension for filtering an object log.</p><p><em>How many swaps had no effect?</em></p><pre>(OrderedCollection streamContents: [ :out |<br>  | subscription |<br>  subscription := LampSortLogEvent announcer <br>    subscribe: LampSortSwapped<br>    do: [ :event | out nextPut: event ].<br>  LampSortInstrumented new sort: #(7 12 3 20 5 8 2) copy.<br>  LampSortLogEvent announcer unsubscribe: subscription ]) <br>    count: [ :event | event oneIndex = event anotherIndex ]</pre><p><em>Answer:</em> <strong>1</strong></p><p>When the source and target index of a swap are the same, the swap has no effect. Note how we can get actual useful information directly from the log event object.</p><p>An object log can be saved to a file or database or transported over the network as such using a suitable serialisation framework, like FUEL or STON. You can convert your event log objects to JSON and integrate with other tools.</p><h4>Visualising LampSort</h4><p>Can we do even more? Yes we can!</p><p>To explain sorting algorithms we can visualize the sorting of an array of numbers using a bar chart. Modifications to the data can be expressed as the exchange of bars.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/496/1*brFpIwVOQlZ4uQ3EBCwjzA.png" /></figure><p>The <a href="http://agilevisualization.com/">Agile Visualization</a> project is an extensive, rapidly evolving eco system of libraries and frameworks on top of <a href="http://www.pharo.org/">Pharo</a> and <a href="http://moosetechnology.org/">Moose</a> that allows for all kinds of visualisation, from very simple to very complex ones.</p><p>Of course, there is a learning curve. But there is documentation and lots of examples. I got help as well — thanks Pierre! Once you get started, it becomes a lot of fun.</p><p>You typically start experimenting with a script in a playground, where you can immediately see the result. Here is a screenshot of such a script in action.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_Gu2h4sEeKzDd9De7D7erA.png" /></figure><p>Once you have enough code you can start integrating it in your application. What we are going to do is add a new, visual GT-Inspector presentation for our log event object hierarchy, built using Roassal2.</p><pre><strong>gtInspectorViewIn: composite</strong><br>  &lt;gtInspectorPresentationOrder: 20&gt;<br>  composite roassal2<br>    title: ‘View’;<br>    initializeView: [ self buildInspectorView ]</pre><p>By adding this method to <strong>LampSortLogEvent</strong> we create an entry point for a new presentation called ‘View’, delegating to <strong>buildInspectorView</strong>.</p><pre><strong>buildInspectorView</strong><br>  | builder dataSet |<br>  dataSet := <strong>self</strong> dataSet.<br>  builder := RTGrapher new.<br>  builder extent: (dataSet numberOfPoints * 32 + 256) @ 256.<br>  builder add: dataSet.<br>  builder axisX noLabel; noTick.<br>  builder axisY noLabel; noTick.<br>  builder build.<br>  <strong>self</strong> highlight: builder view.<br>  ^ <strong>self</strong> withLegend: builder view</pre><pre><strong>dataSet</strong><br>  | dataSet |<br>  dataSet := RTStackedDataSet new.<br>  dataSet points: (<strong>self</strong> data withIndexCollect: [ :e :i | i -&gt; e ]).<br>  dataSet y: #value.<br>  dataSet interaction popup<br>    text: [ :e | &#39;{1} @ {2}&#39; format: { e value. e key } ].<br>  dataSet barShape width: 20; color: Color lightGray.<br>  <strong>^</strong> dataSet</pre><pre><strong>withLegend: view</strong><br>  <strong>^</strong> RTLegendBuilder new<br>      view: view;<br>      addText: <strong>self</strong> printString;<br>      build</pre><p>RTGrapher is a builder that constructs a chart based on a dataset, in this case an RTStackedDataSet. The dataset uses index-&gt;value Associations as models for its datapoints, because we need to be able to distinguish between equal values on different positions. We add a mouse hover popup that shows the value and position of each element. We set the base color and some sizes. It makes no sense to have additional information on the axises. We are reusing our print representation as a legend.</p><p>The <strong>highlight:</strong> method will do nothing in this abstract class and will be overridden in concrete subclasses to indicate the specifics of that log event. Apart from the highlight: methods, there is no visualisation code in the subclasses. Here is the code for LampSortPivotSelected.</p><pre><strong>highlight: view</strong><br>  <strong>self</strong> interval do: [ :each |<br>    (<strong>self</strong> elementFrom: view at: each) color: Color black ].<br>  (<strong>self</strong> elementFrom: view at: <strong>self</strong> pivotIndex) color: Color blue</pre><p>The interval is shown by making the bars black, the pivot bar is made blue. Each concrete subclass knows automatically what to do.</p><p>With this machinery in place, we can again open a GT-Inspector on our Announcer and run the algorithm. This time the ‘View’ tab of each log event will visually show what happened.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*BeuXmEbaLZd6Wmw81-NYvw.png" /></figure><p>Again, we can go back and forth over the events, playing the algorithm forward or backward, in a sense manually animating the computation.</p><h4>Above and Beyond</h4><p>The visualisation that we did in the previous section does a adequate job in showing graphically what each step represents — in a reasonable amount of code.</p><p>But it wouldn’t be graphics if there wasn’t always something extra, something better that we can do. Roassal2 includes animation facilities and Pierre showed me how to apply them in this particular case. When showing a LampSortSwapped log event, we’ll not only <em>color</em> the two bars involved in the swap, but also <em>animate</em> the bars being swapped.</p><p>And here is the <strong>highlight:</strong> code for <strong>LampSortSwapped</strong>.</p><pre><strong>highlight: view</strong><br>  | one another |<br>  one := <strong>self</strong> elementFrom: view at: <strong>self</strong> oneIndex.<br>  one color: Color red.<br>  another := <strong>self</strong> elementFrom: view at: <strong>self</strong> anotherIndex.<br>  another color: Color green.<br>  view addAnimation: (RTLinearMove <br>    to: another position x @ one position y <br>    during: 0.5 <br>    on: one).<br>  view addAnimation: (RTLinearMove <br>    to: one position x @ another position y <br>    during: 0.5 <br>    on: another).<br>  one model key: <strong>self</strong> anotherIndex.<br>  another model key: <strong>self</strong> oneIndex</pre><p>First we change the colors of the elements. Next a linear move animation is added to both elements, which will play for half a second. We already know where to move to, the location of the other element. Note how we also change the model of the elements involved by updating their index — they were moved after all — so that the popup shows the correct value while hovering over the bars.</p><p>Here is a screencast movie showing the final result — the animation wasn’t strictly necessary, but it <em>is</em> very cool, right ?</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FRrsm6E7iA9w%3Ffeature%3Doembed&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DRrsm6E7iA9w&amp;image=http%3A%2F%2Fi.ytimg.com%2Fvi%2FRrsm6E7iA9w%2Fhqdefault.jpg&amp;key=d04bfffea46d4aeda930ec88cc64b87c&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/0b34946021cfe6768fc029e491065bf6/href">https://medium.com/media/0b34946021cfe6768fc029e491065bf6/href</a></iframe><h4>Acknowledgements</h4><p>I thank <a href="http://tudorgirba.com/">Tudor ‘Doru’ Girba</a> and <a href="http://bergel.eu/">Alexandre Bregel</a> and their collaborators for the Moose Technology suite and the Agile Visualisation Tools respectively. Pierre Chanson helped me tremendously by writing the first version of the visualisation and animation — I learned a lot by discussing various aspects of this article with him. My ideas around object logging were shaped in various discussions on the Pharo mailing lists and in conversations with Doru in particular. Doru also reviewed a draft of this article.</p><h4>Getting the code</h4><p>If you want to play with the code yourself, you can clone the GitHub repository <a href="https://github.com/svenvc/lampsort.git">https://github.com/svenvc/lampsort.git</a>. Open a <a href="https://ci.inria.fr/moose/job/moose-5.1/lastSuccessfulBuild/">Moose 5.1</a> image and use the Monticello Browser to add a FileTree repository. First, select the <em>LampSort</em> package and load it. Next, select the <em>LampSortVisualized</em> package and load it too.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6652055ef858" width="1" height="1" alt=""><hr><p><a href="https://medium.com/concerning-pharo/lampsort-revisited-visualised-6652055ef858">LampSort Revisited, Visualised</a> was originally published in <a href="https://medium.com/concerning-pharo">Concerning Pharo</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[LampSort, a non-recursive QuickSort implementation]]></title>
            <link>https://medium.com/concerning-pharo/lampsort-a-non-recursive-quicksort-implementation-4d4891b217bd?source=rss-69bbb011558e------2</link>
            <guid isPermaLink="false">https://medium.com/p/4d4891b217bd</guid>
            <dc:creator><![CDATA[Sven VC]]></dc:creator>
            <pubDate>Mon, 08 Dec 2014 18:15:00 GMT</pubDate>
            <atom:updated>2015-01-18T19:03:11.967Z</atom:updated>
            <content:encoded><![CDATA[<p>The divide and conquer partitioning is at the heart of QuickSort</p><p>Yesterday I came across <a href="http://bertrandmeyer.com/2014/12/07/lampsort/">a blog entry</a> by <a href="http://en.wikipedia.org/wiki/Bertrand_Meyer">Bertrand Meyer</a> (of <a href="http://en.wikipedia.org/wiki/Eiffel_(programming_language)">Eiffel</a> fame) titled ‘<strong>Lampsort</strong>’. In it he discusses an alternative <a href="http://en.wikipedia.org/wiki/Quicksort">QuickSort</a> implementation used by <a href="http://en.wikipedia.org/wiki/Leslie_Lamport">Leslie Lamport</a> (of <a href="http://en.wikipedia.org/wiki/LaTeX">Latex</a> fame) as an example during talks. I was curious and tried to implement the algorithm in <a href="http://www.pharo.org/">Pharo</a>, where I think the idea comes out very beautifully.</p><h4>The Heart of QuickSort</h4><p>We all know <a href="http://en.wikipedia.org/wiki/Quicksort">QuickSort</a> as an elegant recursive sorting algorithm. However, the recursion is not fundamental to the algorithm, it is just an implementation detail. It is possible to think differently about QuickSort and to implement it without recursion. <em>This is LampSort.</em></p><p>At its heart, QuickSort is a <strong>divide and conquer</strong> algorithm: it takes a big problem and reduces it in smaller problems over and over again until the parts get so small that they are trivial to solve.</p><p>The fundamental step of QuickSort is the <strong>partition</strong> operation. Given an interval [start, stop] over the data array that we have to sort, partition does the following:</p><ul><li>pick a <strong>pivot</strong>, any element inside the interval, let’s pick the first one</li><li>split the interval in two sub intervals: one containing the elements smaller than the pivot and one containing the elements larger than the pivot</li><li>continue on the 2 sub intervals</li><li>intervals with zero or one element are sorted by default</li></ul><p>The second step can be done elegantly and efficiently in-place with a single iteration over the interval, swapping elements if needed. Details about the partition operation can be found in <a href="http://en.wikipedia.org/wiki/Quicksort">the Wikipedia article</a>. Note that the pivot itself is part of none of the sub intervals.</p><p>The third step, to <em>continue on the 2 sub intervals</em>, is traditionally expressed using recursion. But there is an other way to implement this step.</p><blockquote>We can make the interval an actual object and track the work that we have to do using a set holding intervals.</blockquote><p>Here is the algorithm:</p><ul><li>start by adding the complete interval to the set</li><li>each time we partition, we take an interval out of the set, split it and add the 2 sub intervals</li><li>empty or singleton intervals need no further work and get removed from the set</li><li>eventually the set will be empty and we’re done !</li></ul><p>The intervals track <em>where</em> we have to work, the actual data array is sorted <em>in-place</em> as we go. At the end, the array will be completely sorted.</p><h4>Pharo Code</h4><p>Let’s create a new class that will hold our LampSort implementation, with data as an instance variable.</p><pre>Object subclass: #<strong>LampSort</strong><br>  instanceVariableNames: &#39;data&#39;<br>  classVariableNames: &#39;&#39;<br>  category: &#39;LampSort&#39;</pre><p>And generate basic accessors.</p><pre><strong>data</strong><br>  ^ data</pre><pre><strong>data: sequenceableCollection</strong><br>  data := sequenceableCollection</pre><p>For users, the main entry point will be the following method that destructively sorts its argument.</p><pre><strong>sort: sequenceableCollection</strong><br>  ^ <strong>self</strong> <br>      data: sequenceableCollection;<br>      sort;<br>      data</pre><p>Which will get invoked like this, where we copy a literal constant:</p><pre>LampSort new sort: #(7 12 3 20 5 8 2) copy.</pre><p>Sort implements the core of LampSort, the iteration that replaces the recursion.</p><pre><strong>sort</strong><br>  | intervals one |<br>  intervals := Set with: (1 to: data size).<br>  [ intervals isEmpty ]<br>    whileFalse: [ <br>      one := intervals anyOne.<br>      one size &gt; 1<br>        ifTrue: [ intervals addAll: (self partition: one) ].<br>      intervals remove: one ]</pre><p>The <strong>#to:</strong> message creates intervals. Note the use of <strong>#anyOne</strong> — it really does not matter which interval is taken. Empty or singleton intervals are not processed further and just get removed.</p><p>The final step is the partition operation.</p><pre><strong>partition: interval</strong><br>  | pivot index |<br>  pivot := data at: interval first.<br>  data swap: interval first with: interval last.<br>  index := interval first.<br>  interval first to: interval last — 1 do: [ :each | <br>    (data at: each) &lt; pivot<br>      ifTrue: [ <br>        data swap: each with: index.<br>        index := index + 1 ] ].<br>  data swap: interval last with: index.<br>  ^ { interval first to: index — 1. index + 1 to: interval last }</pre><p>The first element of the interval is taken as pivot. The pivot is first moved out of the way to the end of the interval.</p><p>Next, a single pass is made over the interval. Elements smaller that the pivot are moved forward. Certain elements will be swapped more than once. Elements equal to the pivot end up in the right sub interval, in possibly random positions.</p><p>Finally, the pivot is moved in place. This position indicates where the interval needs to be split in 2 sub intervals. We return an array containing the 2 sub intervals. Note that the pivot is excluded from either interval.</p><h4>Getting the code</h4><p>If you want to play with the code yourself, you can clone the GitHub repository <a href="https://github.com/svenvc/lampsort.git">https://github.com/svenvc/lampsort.git</a>. Open <a href="http://pharo.org/download">Pharo 3 or 4</a> and use the Monticello Browser to add a FileTree repository.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/630/1*_9QIJrp_4LVSaMt6tTuayQ.png" /></figure><p>Select the LampSort package and load it. Navigate to the LampSort class or LampSortTests unit tests.</p><h4>The Next Step</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*M1KEbn6H1JVkYCzoJRgfZw.jpeg" /></figure><p>In a followup article, <a href="https://medium.com/concerning-pharo/lampsort-revisited-visualised-6652055ef858">LampSort Revisted, Visualised</a>, object logging, agile visualisation and advanced tools are combined to get amazing insight into the LampSort code, easily.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4d4891b217bd" width="1" height="1" alt=""><hr><p><a href="https://medium.com/concerning-pharo/lampsort-a-non-recursive-quicksort-implementation-4d4891b217bd">LampSort, a non-recursive QuickSort implementation</a> was originally published in <a href="https://medium.com/concerning-pharo">Concerning Pharo</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>