wip json-fold (Re: json-fold, json-slice and json-transformer (Re: make json-stream-read a fold-like operation?)) Amirouche Boubekki 23 Jan 2020 19:08 UTC

I pushed a wip branch.

Le jeu. 23 janv. 2020 à 11:05, Amirouche Boubekki
<xxxxxx@gmail.com> a écrit :
>
> Thanks Duy for requesting the fold-like procedure.
>
> I read on the work of Oleg Kiselyov work on XML and SSAX. It is very
> interesting [0][1]. The description of the foldts (extended tree fold)
> is very inspiring.

One definition of foldts is the following:

;; XXX: foldts is not used. It was copied here for documentation
;; purpose (public domain, by Oleg Kiselyov).
(define (foldts fdown fup fhere seed tree)
  ;; - fhere is applied to the leafs of the tree
  ;;
  ;; - fdown is invoked when a non-leaf node is entered before any of
  ;; the node's children are visited. fdown action has to generate a
  ;; seed to be passed to the first visited child of the node.
  ;;
  ;; - fup is invoked after all the children of a node have been
  ;; seen. The first argument is the local state at the moment the
  ;; traversal process enters the branch rooted at the current node. The
  ;; second argument is the result of visiting all child branches.  The
  ;; action of fup isto produce a seed that is taken to be the state of
  ;; the traversal after the process leave the currents the current
  ;; branch.
  (cond
   ((null? tree) seed)
   ((not (pair? tree))      ; An atom
    (fhere seed tree))
   (else
    (let loop ((kid-seed (fdown seed tree))
               (kids (cdr tree)))
      (if (null? kids)
      (fup seed kid-seed tree)
      (loop (foldts fdown fup fhere kid-seed (car kids))
        (cdr kids)))))))

Because JSON has three types of nodes: leaf, array and object I
changed the signature to:

  (json-fold array-start array-end object-start object-end fhere seed events)

Anyway, I will skip the actual definition of json-fold and try to
describe how it works: from right-to-left:

- EVENTS is a generator that follows the same protocol as the
procedure previously known as json-stream-read. It will generate
constructs that look like '(json-value 42) '(json-structure .
object-start) etc...

- (FHERE leaf seed), the first argument is a leaf (just like in
foldts), in the case of JSON, leafs are the types: number, string,
boolean and null (otherwise said, things associated with json-value
symbol in the json-generator-read protocol.)

- (OBJECT-END plist seed) where plist is reversed (!) property list
e.g. value2 key2 value1 key1 ...and seed is accumulated value. It is
similar to foldts FUP

- (OBJECT-START seed) must return a new seed (called kid-seed in
foldts) that will be used as the seed of the recursive call to
json-fold and that eventually becomes the above plist. It is similar
to foldts FDOWN.

ARRAY-END and ARRAY-START look like their object counter part.

There is a trick in the above explanation, in the general case,
OBJECT-END takes as first argument the result of the recursive call to
json-fold that takes as seed the value returned by OBJECT-START seed.
Like foldts makes explicit there two seeds, kid-seed and seed.  It
will be a challenge to explain that.

json-fold allows to make it, at least, much more easy to create custom
representation of JSON types. Here is the implementation of json-read:

https://github.com/scheme-requests-for-implementation/srfi-180/blob/c916f0069f87ef41c4c54fb6317dd018aba22895/srfi/json.scm#L425-L463

Next, I will focus on json-lines / sequences, json-pp and updating the
specification.

I might revisit the idea of json-slice later.