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?
- Stuff between
@$ ... $@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 thatYis 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. - The lambda expression which appears to take
nodeas 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. - The number of children is randomly determined, but a maximum recursion depth is set and helps govern the expansion of the tree.
- A generator is also made available as a binding for this example so that Lorem Ipsum gibberish can be produced. We want string names, but we don't really care what the names are. In fact, we want gibberish names so that hierarchy will seem reasonable regardless of each node's name and definition properties.
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).