block by bmershon aed2b8a1bc3883710fc08de7744594ab

Branching Process

In Matthew Butterick’s fantastic book Beautiful Racket the reader is encouraged to develop a novel extension to the JSON language (really, a data format) which permits arbitrary S-expressions (symbolic expressions) to be placed in the code so long as the S-expressions evaluate to a value supported by JSON. Long story short, a language is created that reads in this funny looking JSON and produces valid JSON which results from evaluating the special S-expressions peppered throughout the input source. The language is called jsonic to suggest the extra power with which it has been embued.

Well, I thought it would be neat to stretch the notion of what an S-expression might evaluate to when it is placed inside what looks like otherwise valid JSON. What if we wanted to make a tree-like structure with JSON. This is a fairly common use case, as many data structures might either be fed by or serialize their data to a JSON data structure that looks like this:

// The root node.
{
  data: // ...
  children: [
    {
      data:
      children: [
        // and so on...
      ]
  ]
}

I happened to be working on a project that requires just such a data structure; I wanted to generate random files on the fly that can encode random tree structures with some randomly populated fields such as type and name and definition and id. As a means for playing more with Racket, I figured I’d bend the rules and encode the information for specifying a random tree in this fancy jsonic language.

What I ended up with was this:

#lang jsonic
// Brooks Mershon, 2017
//
// A recursive definition for a random tree structure,
// written in jsonic, which extends JSON to support
// arbitray Racket symbolic expressions (S-expressions).
{
 // This is the root node.
 "name": "root",
 "id": @$ (uuid-generate) $@,
 "type": @$ (list-ref '(5 20) (random 0 2)) $@,
 "children":@$
 ; The following S-expression creates a random list of nodes.
 (map
  ; No define allowed in an expression context, so the
  ; applicative-order Y combinator is used to provide
  ; a mechanism for recursion.
  (Y
    ; "Almost" a recursive definition for a node. The following relies on
    ; Y-Combinator to create a fixpoint for this function.
    (lambda (node)
      ; A recursive definition for a node.
      (lambda (depth)
        ; A node is returned with a random subtree if depth > 0.
        (hash 'name (string-join (lorem-generate (random 1 3)))
              'definition (string-join (lorem-generate (random 1 5)))
              'id (uuid-generate)
              'type (list-ref '(5 20) (random 0 2))
              'children (if (zero? depth)
                            '() ; No children, otherwise...
                            (map (lambda (n) (node (- depth 1)))
                                 ; Random number of children in [0, max-width]
                                 (range 0 (random 0 3))))))))
   ; The top level of the tree has between 5 and 15 children, each with a maximum depth
   ; of their subtree limited to a number between 5 and 15.
   (map (lambda (n) (random 1 5)) (range 1 (random 2 6))))
 $@
}

What’s going on here?

Here is the resulting perfectly valid JSON when the above code is parsed as “jsonic” code:

{
  "name": "root",
  "id": "6D80DAA4-7014-427A-82C3-6504FD7F646B",
  "type": 20,
  "children": [
    {
      "type": 5,
      "id": "F6AE9C17-CBE5-4AB5-80C3-2D21DEC9C334",
      "name": "natoque suspendissewp",
      "definition": "plateahta gravida consectetuer sed",
      "children": [
        {
          "type": 20,
          "id": "1B5C95E8-364F-43EC-B46E-3CECEDC5D921",
          "name": "amet",
          "definition": "eleifendcss cursus ante faucibus",
          "children": [
            {
              "type": 5,
              "id": "BF0E32C6-594B-41F2-A0AC-10E1A4032107",
              "name": "hacscm",
              "definition": "aenean aeneanwri",
              "children": [
                {
                  "type": 20,
                  "id": "543E8C2E-E697-40FA-BAD5-2C91C2956B58",
                  "name": "ultricesrpm",
                  "definition": "posuererng at",
                  "children": []
                },
                {
                  "type": 20,
                  "id": "ACD37FEE-C258-404B-A93E-6D11520ED28C",
                  "name": "quisque nec",
                  "definition": "maurisdp erat aeneanhdf ac",
                  "children": []
                }
              ]
            }
          ]
        }
      ]
    },
    {
      "type": 5,
      "id": "7261AC38-234C-4F5C-9B1C-6BC450F0431F",
      "name": "nislunv sedwml",
      "definition": "liberoppz vestibulumcha cubiliasgml milma",
      "children": [
        {
          "type": 20,
          "id": "F5AE2AB0-38EB-4C7C-B142-9CC88D680E48",
          "name": "urnaprt vel",
          "definition": "ut",
          "children": [
            {
              "type": 5,
              "id": "171020F7-792A-4B2D-9CAD-556F32FDD970",
              "name": "tristique in",
              "definition": "id pedeset atconf",
              "children": []
            }
          ]
        },
        {
          "type": 5,
          "id": "180B8AB5-5243-4FB6-8CB8-47570E723646",
          "name": "nibhw60",
          "definition": "maurisvew",
          "children": [
            {
              "type": 20,
              "id": "169F4B51-14AE-466B-B196-CF3B739BB01B",
              "name": "atlma aliquamsmi",
              "definition": "amet",
              "children": [
                {
                  "type": 20,
                  "id": "3D5F3C41-AB3B-428A-BBCA-111542995048",
                  "name": "a vehiculaxif",
                  "definition": "acuri diam turpis vulputateras",
                  "children": [
                    {
                      "type": 5,
                      "id": "684152E1-46A8-4844-BEB7-FE907328B0BF",
                      "name": "aliquam",
                      "definition": "anteg inzip etiamppt",
                      "children": []
                    }
                  ]
                }
              ]
            },
            {
              "type": 5,
              "id": "03CC3A39-9856-4B31-A6F0-A341AECBE46B",
              "name": "elementumdcr euras",
              "definition": "aliquamsh vitae",
              "children": []
            }
          ]
        }
      ]
    }
  ]
}

That’s a nice tree. By tweaking the parameters, we can make an even bigger tree (warning: 717 KB, 13,000 lines).

See also

lorem.rkt