Fork me on GitHub

so you have a cfg where the terminals are predicates, and the predicates can be defined as themselves being a cfg


@hiredman: I agree with you that a pattern language for Tree<T> exists. I also agree that this pattern language has derivation rules, where some rules are choices of the form choiceA | choiceB | choiceC | ... ; and other nodes are of some form that builds up trees. I am not sure that calling this CFG-like is correct.


It is a CFG


Regexs describe sets, CFGs commonly do not exhaustively list all terminals instead defining sets of terminals via regexes. CFGs describe sets. Given a cfg, swap the sets described by regexes for sets described by cfgs. You've swapped sets for sets, just a different set builder notation.


(I am well aware that CFGs are more powerful than regexes, that just means that CFGs can describe more sets than regexes can, but they are still sets)


Point me to one text book / peer reviewed paper that shows how to use CFG to pattern math over trees.


@qqq I think you're being very belligerent here. If you want to find peer reviewed papers etc, you should use Google/Bing/whatever and find them yourself instead of demanding that others here do your research for you.


(that was just the first vaguely relevant seemingly result from a very, very brief search that you could easily do yourself)


@seancorfield: The link you posted has nothing to do with parsing.


My point here is: CFG, as traditionally used in CS, , is for List -> Tree. Besides @hiredman, I have never heard anyone claim that CFG can be used to parse Trees -- and that such a textbook / peer reviewed paper does not exist.


The CFGs you are looking at are already being used to parse simple trees


In that the terminals are sets of lists of character, not just sets of characters


@seancorfield: Would it be less "very belligerent" if I instead wrote it as: "Point me to one text book / peer reviewed paper that shows how to use CFG to pattern match over trees, and I'll be convinced your definition makes sense." ? Here, @hiredman is making a claim that standard usage of CFG does not claim. I am asking him to back up him claim with peer reviewed article, rather than his own claims.


A cfg is not a function with the type list -> tree, you should maybe read that Wikipedia article a little closer


Given, an alphabet Sigma, CFGs define a subset of Sigma^* which can be mapped do an AST specified by the derivation rules.


Note that Sigma^* is over Vec<Sigma>, not a Tree.


If you can point me to one peer reviewed theoretical CS resource that claims that CFGs recognize subsets of Tree<Sigma>, I'll concede the argument.


Otherwise, I am maintaining my claim that CFGs are only used to recognize Sigma^*, which is Vec<Sigma> in our discussion so far.


They don't need to recognize Tree<Sigma>, if you accept that tokens in you "language" can be any type, not just strings, then you make you token type Tree


So sigma is a set whose elements are trees


Sigma, in typical CS literature is either {0, 1}, or alphanumeric. Is there anyone else in the CS Theory community that uses the definition you use ?


Sure, because parsers typically parse text, but just because it's typical that doesn't mean that is all there is


@seancorfield in DMs asked me to drop this conversation, so I'm leaving it here as is.


A cfg is a logical/mathematic object, where "string" is an abstract notion that can be anything


I'm making one more statement because I think I can resolve our disagreement: Traditional CFGs have type signature: Vec<Sigma> -> bool I am looking for a pattern language to specify functions of type signature: Tree<Sigma> -> bool @hiredman if you "add trees to Sigma" as you suggest, CFGs still have type signature Vec<Sigma> -> bool the only difference is that Sigma is now defined as Sigma = Letter | Tree ... Now, in this case, I will concede that the CFG is "recognizing lists of trees", but this CFG is not recognizing individual trees. I.e., the type signature is Vec<Tree> -> bool; whereas I am after Tree -> bool.

Alex Miller (Clojure team)12:11:02

Does this have anything to do with spec? Can we move further conversation to #off-topic or something?


Hi, is there a way to generate a good documentation from speced functions? I know the discussion about spec meta from last year but did'nt find any update ... anything new ?

Alex Miller (Clojure team)15:11:55

the doc generator we use for core and contrib (autodoc) does make docs for specs

Alex Miller (Clojure team)15:11:05

but autodoc is frustratingly hard to use in practice


do you know what authodoc version clojure uses?


I can find a tag 1.1.2 but that's 5 years old ...


saw this already 🙂


If clojure doc is generated with 1.1.2, I will give the autodoc-lein an update to use the 1.1.2 version also ...

Alex Miller (Clojure team)15:11:52

autodoc is conceptually well structured (split into separate programs to "collect" data and export docs, but super difficult to use well in practice


yea .. a read about


do have a link for the setup clojure uses itself ?

Alex Miller (Clojure team)15:11:02

but Clojure's use of autodoc is particularly weird

Alex Miller (Clojure team)15:11:29

it's using 1.1.2 though


cool - thanx. If we find our way through I will give feedback ... maybe we did some steps in right direction valuable for others :-)

Alex Miller (Clojure team)15:11:32

I would love to take the good stuff in autodoc and turn it into something actually usable (Clojure's specific usage of it for core and contrib is additional layer of bespoke weirdness over the top)

Alex Miller (Clojure team)15:11:57

but it's hard for that to ever get enough priority


We will spend one day on this ... let's see wether there is going sth on 🙂


what spec (or related) libraries are there for testing database services are there ? I heard about such a library on a podcast but don't remember which one. Context: I would like to test a Java ERP solution and services will depend on data. I am curious if generative testing can help with this.

Colin P. Hill18:11:01

What do you want the library to do?


hi, I would like to do db integration tests and insert a bunch of related records based on the relationship betwe them. I want to test user roles - and that requires user-role record but also depends on user records and maybe account or permission records. These should be generated as well .


kind of along those lines


I remember a library designed for this purpose - but don't remember which

Colin P. Hill13:11:18

It sounds like you might actually be describing a library made at my company: Obviously a bit of conflict of interest in me highlighting it, but if it helps, I haven't personally worked on it and haven't yet even learned how to use it 😅


yep, that is the one


@alexmiller: Valid point, future (if any) debates on whether CFGs can recognize trees will be moved elsewhere. If you don't mind, I do have a question for you. 'spec' is basically a pattern language which, among other things, can be viewed as a shorthand for describing functions with type signature 'Tree -> bool' . (Given a spec, some s-exp trees are accepted; others are rejected.) Question: in the design of spec, is there some formal theoretical foundation spec is built upon (say, the tree equiv of regex / cfg / ll parsing / lr parsing / ...), or has it largely been a collection of useful techniques (i.e. we should be able to use it to validate pattern A, pattern B, pattern C, ... ).

Alex Miller (Clojure team)17:11:25

Spec is built on two logical foundations - sets (maps as sets of attributes) and regular expressions (not regex as string matching but the more general idea). The latter impl is based on Matt Might’s work with regular expression derivatives, but that's really an implementation detail. This is not about trees or parsing, it's about whether a value is in the predicative set described by the spec. As it is inherently predicative, and predicates can be anything, this is I think much broader than pattern matching.

Alex Miller (Clojure team)17:11:50

From day 1, the ideas of being predicate based, and automatically generative were considered to be required.

Alex Miller (Clojure team)18:11:12

specs work on values, there is no s-exp tree

Alex Miller (Clojure team)18:11:38

there's no explicit notion of trees at all

Alex Miller (Clojure team)18:11:02

specs are descriptors/validators of sets of accepted values. some specs are composite and describe composite values. conceptually, I guess you could say those are trees, but that is more implicit than explicit.

Alex Miller (Clojure team)18:11:39

if specs are "is this value in the set?", generators are "give me example values in that set", so these are intrinsically related

Colin P. Hill19:11:39

Given a map and a spec that describes it, is there a way to yield a map which only contains those keys which were specified? I don't want to write my spec so that it rejects unspecified keys, but I also don't want to write what is effectively another description of the map shape in the select-keys that I'll need before handing the map down to the database.

Alex Miller (Clojure team)19:11:14

no, I know people have made things around spec

Alex Miller (Clojure team)19:11:36

in spec 2 we have added a validation flag to validate in a "closed" mode

Alex Miller (Clojure team)19:11:15

we very much believe this should not be a property of the spec (but it may be a useful property of an act of checking)

👍 2
Colin P. Hill19:11:58

Big agree on that. I'm working with a custom extension to spec which adds closed map validations. It's been useful for making sure we don't hand things off in places where extra fields might be damaging, but there are other places where we want to describe the same shape while allowing it to be extensible. Currently trying to rewrite a use of it to follow some other strategy.


Are there any guarantees on the running time of spec? I.e. given a s-exp with at most N nodes and at most D depth, if there some big-Oh expression on the time it takes the spec validator to decide whether the s-exp belongs in the spec ?

Colin P. Hill19:11:49

A spec can be any arbitrary predicate, so not in the general case

Alex Miller (Clojure team)19:11:51

given that predicates are arbitrary functions, no