Wednesday, April 18, 2018

Trie Demo

https://codepen.io/wshager/full/zWBzMV

It says "directed acyclic word graph", which I think is the correct term, but I just found out on Wikipedia that this is indeed a trie. The difference is illustrated quite precisely, but I think it's really the same thing. I didn't use an existing algorithm, but I just made this up myself. I didn't study computer science (and I'm mostly glad I didn't). If you did, let me know if it's any good.

Tuesday, March 20, 2018

Rich Reducers

Writing parsers is not for humans. Humans define grammars, and feed those to parsers. However, I was determined to try my hand at making a parser for XQuery in XQuery as a human, because I saw that the language is actually quite consistent. The same is true for XML and S-expressions, for example, and for those languages there already exist hand-built parsers (for example in in JavaScript, see https://github.com/isaacs/sax-js and https://github.com/fwg/s-expression respectively).

After all, how hard can it be? Well pretty damn hard, as I've worked on it on and off for two years. Yet only recently I came up with three basic utility functions that help to understand how a parser actually works. These functions are variations of the widely known reduce (or fold) function.

Looking ahead

What you often need to do when parsing a string of text – character by character – is to look at what the next character is. For example, a colon has several different meanings in XQuery, so the parser needs some context to decide if a colon is part of a qualified name, a comment or an assignment. This can only be decided by "peeking" at the next character. A "peek" method is often available under this name in a parser in some object-oriented environment, but not in a strictly functional language like XQuery. So, time to introduce a function that actually does what I need: reduce-ahead.

The function I've created in XQuery could obviously also be written in other languages. Let's start by recapping what the regular reduce function does. Given some list-like structure (e.g. an array, a sequence, or a stream), and a starting value, apply a function to each item in the list, and return the accumulated result. Example:

  1. A list: (1,2,3,4)
  2. reduce with starting value: 0
  3. A function that adds each value to the accumulative result:
    (accumulative,currentItem) => accumulative + currentItem

Now each call will return an intermediate result for each item in the list:


iterationaccumulativecurrentItem
101
212
333
464

After the last function call, the result will of course be 10.

My reduce-ahead function simply adds an extra parameter to the accumulating function, that contains the next item in the list. With this function we could return another value depending on which item comes next in the list. The following function doesn't add when the next item equals 4:
(accumulative,currentItem,nextItem) => nextItem == 4 ? accumulative : accumulative + currentItem


iterationaccumulativecurrentItemnextItem
1012
2123
3334
434

Now the outcome will be 7.

This functionality is easily extrapolated to a parser, where it can look ahead whenever a character should be disambiguated. Other variants in the same spirit are reduce-behind, that provides the previous item in the list, and reduce-around, that provides both the next and previous item.

Especially when reducing streams this is quite useful, because you can't simply (read: efficiently) inspect a stream by using an index. Apart from hand-made parsers other use cases for this powerful principle may pop up in the future.

JavaScript implementation: https://gist.github.com/wshager/df8e0c67281068cd5d01f30452df7287

Friday, March 16, 2018

Pleidooi voor een meer formele benadering van programmeren

Programmeren is zowel een wetenschap als een gereedschap. De "man van de praktijk" loopt gaandeweg tegen problemen aan die formeel allang verkend zijn. Deze zaken zijn veelal uitgewerkt in ingewikkelde wetenschappelijke publicaties. Dat niet iedereen die leest is begrijpelijk, maar veel kennis is ook geïmplementeerd in functionele talen, als Haskell, Scala en recente LISP/ML varianten. Om inzicht te krijgen in fundamentele concepten is het verstandig om contact te houden met de ontwikkelingen in dergelijke talen. Ook in Javascript begint deze kennis door te dringen, al is dit geen zuivere functionele taal...

Kennis van zuiver functioneel programmeren opdoen kan door zelf een taal te leren of door bronnen te raadplegen op het WWW, zoals diverse blogs en tutorials (er zijn ook veel videos) of hulp te vragen van experts op StackOverflow. Het doel is niet om zo'n taal te gebruiken, maar om concepten te doorgronden die eraan ten grondslag liggen. Dit geldt overigens ook voor XQuery, een taal met een veel minder steile leercurve dan bovengenoemde. Maar XQuery heeft wel een aantal beperkingen, die blijven voortbestaan door het isolement waarin de taal zich bevindt, namelijk in de impopulaire wereld van XML. Echter is de taal niet in isolement ontstaan, en er zijn ook hierin verborgen juweeltjes die je kunt vinden door simpelweg met de taal te werken.

De verborgen formele oorsprong van XQuery zit in zaken als:

  • de monadische aard van sequences: alle data is veilig “ingepakt” zonder dat je daarover hoeft na te denken
  • for-comprehensions: ingepakte data zijn intuitief uit te spreiden en zo te verwerken
  • parallelle computatie: sequences lenen zich uitstekend voor impliciete luie evaluatie en het afhandelen van asynchrone processen

Ook Michael Kay van Saxon, de bekendste en meest gebruikte implementatie van XQuery (en XSLT), heeft toegegeven dat een XQuery implementatie zonder enige vorm van luie evaluatie slecht zal performen. Een voorbeeld van een implementatie zonder luie evaluatie is eXist-db: er is geen verschil tussen "complexe-computatie()" en "complexe-computatie()[1]". De functie wordt in zijn geheel uitgevoerd, voordat alleen het eerste item in de sequence wordt uitgevraagd. Kay maakt zelf overigens ook fouten, volgens mij door de theorie niet goed genoeg te bestuderen (hij noemt zichzelf beslist praktisch). Er is wel een formele specificatie van XQuery, maar die is weinig leerzaam in dit opzicht:
https://www.w3.org/TR/xquery-semantics/

De voordelen van XQuery zijn tegelijkertijd ook een nadeel. Het maakt gebruik van formele concepten, die zijn weggestopt voor de "eindgebruiker". Dit kan enerzijds gebruiksgemak vergroten, maar zorgt er anderzijds voor dat je je eigenlijk nauwelijks ontwikkelt als programmeur. Ik denk dat het beter is om zaken op de één of andere manier expliciet te maken of ergens uit te leggen. Maar ik denk nog meer dat het alleen mogelijk is om concepten te doorgronden door ze zelf te bouwen. Dat is niet mogelijk in een taal die is geïmplementeerd als black box. We moeten daar dus af en toe uit zien te komen.

Ik zie in JavaScript een zeer toegankelijke taal, die door velen wordt omarmt en waarin het mogelijk is om allerlei concepten uit te werken, voor zover ze nog niet zijn toegevoegd aan de taal zelf. Ik zou dit graag met anderen samen doen die JavaScript beheersen en openstaan voor een meer formele benadering, maar tegelijk realiseer ik mij dat iedereen hierin zijn eigen ontwikkelingsweg heeft te gaan. Ik denk echter dat het op dit moment voor iedereen die van software zijn beroep heeft gemaakt, noodzakelijk is om de volgende zaken te verkennen:

  • Reactive Extensions for Javascript / Observables / Streams
  • Immutable datastructuren
  • Een vorm van type-aanduiding
  • Code-generatie op basis reeds bekende, overzichtelijke tools, zoals formulieren, spreadsheets of gestructureerde editors, vooral in plaats van de ouderwetse database / CMS / CRM


Ik denk dat we zelf begrip moeten opbrengen voor deze zaken, anders raakt de kennis uit ons blikveld. Niet iedereen zal op hetzelfde moment en met dezelfde controle de kennis aan kunnen wenden, maar waar het nu om draait in software is precies bekend. Net als in zelfverdediging zijn er maar een paar dingen die je moet weten om jezelf enigszins te kunnen verdedigen. Je kunt zeggen: "ik bouw software, maar ik hoef niet alles zelf te begrijpen". Je kunt je uiteraard aan de confrontatie onttrekken... totdat er toch iets op je pad komt. Maar dan heb je in ieder geval de noodzakelijke gereedschappen om daarmee om te gaan.


"RxJS is een hamer"