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?
@$ ... $@ delimeters is evaluated as pure racket code. Unfortunately, (define ...) is not supported in an expression environment. In order to play with a recursive node definition, I ensure that Y is available by exposing a definition of the applicative-order Y combinator as an aviaible binding in what is called the “expander” for this jsonic language.node as a parameter is “almost” a recursive function. It relies on the Y combinator to provide a fixpoint to the function. See my explanation of the Y combinator, which largely draws upon Mike Vanier’s excellent write-up.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).