What are good base combinators?

I have this feeling that we can provide a few very low level combinators that will be the foundation for several higher level combinators. For instance: making a Y combinator would enable us to describe all kinds of recursions and iterations and could be the foundation for array contains element, array contains sequence, all elements are present in array, each element is present at most n times in the array, following attribute child will eventually find a child with id 4711 and so on.

I realized the attr combinator is probably such a combinator since it allows us to assert things like: the name attribute of X is Y but also the Nth element of XS is an X.

I think this is where we need to look into parser combinators and understand what the basic set is and why. Also, how it applies to our domain (attr for instance is does probably not have a corresponding combinator but seems pretty basic in our domain (?)).

I read a bit more about parser combinators and not surprisingly I think we can steal the mechanics pretty much completely. Properties of parser combinators:

can take one or more parsers as arguments and return a new parser
a parser can optionally consume part of the input
on success unconsumed input is returned
on failure 'empty' is returned
pasers are symtrical so that they can be bound together (parser A's output can be fed as input to parser B etc). That allows a monadic bind.

How this translates to assert combinators

an assertion combinator can take one or more asserts and return a new assertion
an assertion can assert input and return a promise for a result
an assert can optionally consume part of the input
on success the unconsumed input is used to resolve the returned promise
on failure a message of what went wrong is used to reject the returned promise.
since promises are chainable and an assert resolves the unconsumed input many assertions can be combined using then.
since assertions can consume promises one can make assertions for sequence, any, all, repeat etc just as is possible with parsers.

As an example, the attr assertion should resolve to the value of the key it asserts (it currently resolves to the object that contains the key but that should be changed). Given that attr consumes the object it assers and returns the key several attr can be used to dig deeper into an object.

Consider this structure:

var a = {
  b: {
    c: { message: "hello" },
    d: { message: "bye" }}};

the following combined assert:

when(attr('b', has('c')).
  then(attr('c', equals('hello')));

This can of course be sugared and is pretty internal but then is pretty equivalent to bind and by consuming or not consuming one can dig deeper into a structure as with attr or sequence or make more asserts on the same structure as with all.

conclusion

I think the promise model supports what we need to be able to build pretty powerful assertions from very simple building blocks. It seems to me that the model would be very easy to extend and I would not be surprised if it could open up for new styles of testing where a domain language evolves in the form of new asserts build from existing asserts... Exciting stuff!

Can't wait to perish more of what you're bringing up :) For now I've got only this much on attr:

It appears to me that it can be viewed as composed of more fundamental things: attr is kind of "the assertion version" of what is sometimes called a projection (in type theory, basically def #1 here). So if we assume that project is the function that takes a key k and an object o and returns the value v := o[k] (JavaScript),

project :: k -> o -> v

and if we view a partially applied assertion, as from referee-combinators, as a predicate, ie. a function that takes a value and returns a boolean:

class Predicate a :: a -> Bool

(to be taken rather informally, as an illustration - NOT as real or even tested Haskell code)

...then attr has this type (signature):

attr :: k -> Predicate a -> o -> Bool

...and you can imagine how to make it from project and a given predicate.

Oh yeah, VERY exciting stuff it is indeed :D

I think you are right. I'm not sure exactly what that means but it feels good.

Definitely the part that a primitive assert (or a readily combined assert) is equivalent to a predicate in your example.

I'm reading up on the paper I linked to in another thread (tried to find one that was sort of formal but still easy to read, I'm not that clever). It seems it will be a lot of fun fleshing out the combinators.

Yeah, I'm having a lot of fun already :D

I'll try to make my thoughts on that more concrete soon. In fact it isn't that fancy as it might look. No smart monads or so. My main problem (but also fun) is that JS has nothing remotely a type system like Haskell's to guide you, and I have not yet sorted out the implications of that (= how far we can go in JS).

Definitely the part that a primitive assert (or a readily combined assert) is equivalent to a predicate in your example.

:) Well, next step is to consider asserts in general (as opposed to [only] readily combined assert). What then are these? Relations I'd say...

I'm reading up on the paper I linked to in another thread (tried to find one that was sort of formal but still easy to read, I'm not that clever)

'twas +2 from me in the other thread - and I mean it! Given the authors alone (and 1996 > 1992 but not 2013) I'd say you've come very close to the ideal paper for us.

I had a quick read through it. It is a bit hard to sort out exactly what is relevant to our domain and what we can leave behind in the parser domain.

Parser combinators carry with them both parsed and remaining content. I think we don't need to carry "parsed" (asserted) content with us since our goal is not to build an AST, just to verify a structure.

Combinators that seem relevant:

choice
many
seq (handled with bind, same as plus?)
sat (my feeling is that this is any primitive assert with added consumption)

We also have some aspects that i think are different from parsers and that is for instance that we may need to parse a mix of objects, arrays and primitive values while parsers mainly deal with sequences of primitives. I do think that this is not a hard problem. It is just a little bit different from the parser-problem

Given this basic set I think we can combine asserts to verify pretty much anything... (I probably missed something but I think the parsers I mentioned are at least needed)

I've been thinking a lot more about projections and your little recipe should work for pretty much every assertion. Most of them will have identity as projection which as you know means that they will assert exactly what they are passed as actual. As in your example attr uses a projection that gets the value v from the attribute k on object o.

While the attr projection can also be used on arrays there are projections that are interesting that can be used on iterable elements such as head, tail, head(tail). Given such a projection one can combine an assertion that can check that all elements in an array are ordered for instance.

By disconnecting projections and predicates as you suggest the variations are endless. While we may not want an unsuspecting user to be familiar with all those concepts and nitty gritty details I think it will be a big win to use this kind of thinking "under the hood" and also make sure that a user that wants to use them may do so. (as in not hiding them but make sure they can be set aside easily if you just want to use the higher level (not order this time) assertions that we provide such as sorted)).

My feeling is that to be able to support consuming (which I have come to realize is more like narrowing or filtering the input). We have to:

project the value to assert
also project the value to resolve on success which allows us to
- traverse objects
- not traverse objects for operations such as and.
provide a raw assertion as a predicate.

Something like this:

function(projection, predicate) {
   return function(actual) {
       return when(projection(actual)).
          spread(function(head, tail) {
              return when(predicate(head)).then(_.constantly(tail), _identity);
          } )
       }
   }
}

This was coded on free hand and is not tested. This is my intention:

projection takes actual and returns an array with
1. the value to check head
2. the value to pass on in case of success tail
spread is a whenspecific method that just applies a returned array to the next function
the predicate checks head and resolves on success.
- this will yield tail since _.constantly will return it on success
- in case of error the message will be passed on with identity....

Not sure I got all my neurons lined up properly. My point is, I think that there is a general abstraction for waht we want to do that involves your idea with projections and predicates. Also, making the projection not only return what to assert but also what to resolve on success traversing all the structures we may need to assert is just a matter of defining new projections.

On the other hand... attr could just return a promise for the value under attr and pass it on to the next assert via a seq or bind... It seems to me that part of the fluff is already in the promise concept??? thinking out loud sorry

Very interesting, returning not only a value but also a value and kind of a guide how to continue computation...!

Terminology ("don't call it Schnitzel projection")

Just one little thing first: we need to distinguish clearly between

the basic operation that . or [``] performs in JS. There it happens to lack a representation as a function (as opposed to eg application). So we need to make our own, but that's easy enough.
any mapping operation in general

Well, if you think about it there's really no doubt about how to name them. 2. is just "function" and 1. is "projection", in the restricted sense, ie project k o = o[k] (and nothing else). It's not my idea, it's standard.

Your Example

What you're actually trying to do in your example (I think) is formulating all p, p a predicate - with the list DEconstructor abstracted out^[1]. I understand that you said it's coded on free hand, and that's ok. It's just that I couldn't see a way of typing it, so therefore I'm guessing a bit, and asking you to correct me should I be mistaken about what you had in mind.

Anyways, abstracting out the list deconstructor from all p is interesting in itself. It means abstracting away the concrete representation of lists! That is a very cool idea!

Then, somewhat mixed in, I see this notion of acting on a value (apply predicate) AND, depending on the outcome of that, direct subsequent computation. I think that would be what they call deterministic choice in the paper.

What I DON'T see at all (sorry), is projection (in the strict sense). Maybe only (and implicit) if the representation of lists were fixed to pairs of first and rest - but hey, that would render abstraction over list representation pointless, wouldn't it?

Conclusion

Should you see criticism in par. "Your Example" then plz don't be put off. Rather: plz read again and you'll see it's the contrary :)

Should you NOT see criticism in par. "Terminology (...)" then plz read again ;) But don't be put off either.

So I guess what I'm trying to say is this: +1 (if not more) for putting this up, "What are good base combinators?"! But getting this clear - and I mean really clear: like you said, "to know not only which to choose but also why" - will require substantial work. That is: disciplined thinking and discipline in terminology. Not totally but to a certain standard. Additionally, the two are inter-dependent, IMHO. Hence coming up with - and then sticking to - a suitable terminology is a crucial part of the work. It seems to me that part of what you express in your last post,

[...] part of the fluff is already in the promise concept???

might come from "not having done the homework", in the sense of discipline above (and NONE else!^[2]). Right now I, personally, feel overcharged with where to locate the promise concept in all that. So my strategy is to strip down and define "homeworks", the smaller the better. May lead to more of them - but that's fine!

Two more things...

... which are important for me to say: there is no problem with wild speculations or "thinking out loud". None at all, really - _as long as it's clearly marked as such_. Your last post is a perfect positive example :) Apart from that I'd like to add that I am enjoying these discussions. It might appear otherwise every now and then but I really mean it. So: Thank you :)

^[1] The list deconstructor (type [a] -> (a, [a])) is the inverse of the list constructor (type a -> [a] -> [a]). There are no such lists in JS per se; you called them "iterable elements". It may be a bit confusing because those functions, the list constructor and the list deconstructor, are oftentimes not directly available. For example

in LISP the constructor is identical to making a pair, ie (x, ys) IS the list with x the first element and ys the rest of elements (again a list). The deconstructor is not one function that returns a pair but rather two functions car ("head") and cdr ("tail"). You can view car as project 0 and cdr as project 1 on tuples. The deconstructor would combine those to form a pair, xs -> (project 0 xs, project 1 xs). But hey, in LISP this IS the list xs itself, so there's really no point in having an explicit deconstructor!
in Haskell the colon : is used to refer to both, depending on the context. It's in pattern matching where : means the deconstructor and elsewhere it means the constructor.

^[2] NOT "know this paper or that" or "had you only paid more attention in 'Functional programming 101'" or something like that. ONLY wrt organizing your very own thinking!

Oh, and before I forget: have you been wondering what I was doing all that time? ...whereas when I put up prs it's always lots of commits?

Well, taking as a hint where this discussion went so far - can you guess what I was (and still am) fiddling around with? ;)

Just to not leave this hanging: No offence taken, ever. I think that we may have different approaches to solving problems. I tend to start out sloppy and refine. A strict terminology or formal specifications are not my strong sides. I'm trying to adapt and appreciate your patience with me. I will probably always need one hand in the cookie jar while thinking... I'm sort of the type that thinks with my hands...

About my homework I'm sort of having an incremental approach to that too. In general you can expect that I'm thinking out loud most of the time. I'll try to be more clear about that given the means of communication.

I have no idea what you're up too :) I just thought you had a life and when you had time fiddled with the tests?

What I'm currently up too is trying to implement my first proper combinator bind or should it be seq. I will get back to you about the previous post tomorrow (sleepytime now) but I can give one clarification to my confusing code: I used the well known head + tail which indicates a sequence. What became less clear because of that is that the same technique can be used for primitives

v -> (v, v) or objects o -> k -> (o[k], o[k])

In my confusion about projections I really meant separating selecting part of a structure that goes into an assert. And by returning a pair of [valueToAssert, nextValueToresolve] one can decide wether or not to traverse a structure or just pass it along in order to chain asserts (for instance to implement and). Also, I realized that attr should really not assert anything, it should just grab the value and pass it along (by resolving the returned promise). By having that approach one can to this: o.k1.k2.k3.k4 -> assert -> r.

but I still haven't done my homework so time to sleep :)

Just to not leave this hanging: No offence taken, ever. I think that we may have different approaches [...]

Glad to hear. And: our having different approaches does have an advantageous side. I think we have already created some evidence of that :)

[...] given the means of communication.

Exactly that is the point. We both know of course that this form of communication bears a peculiar contrast in it: while what you're receiving from the other side is very limited / deprived (as eg compared to personal contact), at the same time there are very few limitations in what and when you send (as eg compared to snail-mail or even email. Or take personal contact: even both talking at the same time can happen more easily here!). While knowing this in general requires no big genius it's NOT a matter of course to always apply that knowledge appropriately in practice. Especially when things are getting exciting :)

So this is also bit of a matter of "discipline" which I had in mind but didn't emphasize above.

Well, in order to live up to my own standards - I'll end this post here and comment on the tech stuff in a separate one :)

What I'm currently up too is trying to implement my first proper combinator bind or should it be seq.

Sorry, I'm afraid I have to get on your nerves again about naming. I think you should neither call it bind nor should you call it seq. Rather: and or maybe all. Let me explain:

I'll start with some general arguments against the two, and only then argue in favour of and (or maybe all). I'm saying this beforehand s.t. you know where to look for my assumptions about what you wanna do: in the latter. And correct or make explicit where necessary.

bind is way too "overloaded". We're in JS, you know. Of course I know that you do NOT mean that "bind", but hey - we're in JS, you know... Then, more importantly, there is the monadic bind which is probably what you have in mind. But that's not a good fit either. Or at least I see some strong indicators that it isn't: Firstly, as of now, there's only some - albeit strong - feeling that there exists something like an "assertion monad" (at least I have it, still). BUT how that might look like - we have no idea (or at least I don't have one, still). Secondly, >>= (monadic bind) is for chaining monads (precisely: instances of one particular monad). Note that I am avoiding the term "sequencing". For the Parser monad this indeed corresponds to sequencing in the grammar, while ++ corresponds to alternation in the grammar. However, this (interpretation) is just a nice and intuitive coincidence in the Parser monad. Here's a counterexample: the List monad. What is "sequencing" of lists? Concatenation of course. But in the List monad concatenation is ++ whereas >>= is "mapMany" or "selectMany"^[1].

seq also has an "overloading problem", albeit not as much as bind. One might think of some kind of list, maybe lazy ones, what you had called "iterable elements". Now, what you have in mind MUST be more than just a list of assertions. You wouldn't need an assertion combinator for that, you'd just make an array of assertions or so. So, similar to the argument against bind above, "seqing assertions" doesn't tell you how to interpret it. It is not specific enough (you'll remember the discussion about the name of what is now referee-combinators).

and (or maybe all^[2]): that is obviously a very basic thing and a good candidate for a first go (alternatively/dually: or / any). So, you're given a set of assertions (note again that I'm avoiding "sequence" or "list"). What might you be interested in about that set? Seems pretty obvious to me. Am I guessing right that this is what your "first proper combinator" is about?

^[1] just tell me if I should explain what "mapMany" is and I will. But the point is that >>= cannot at all be always naturally interpreted as "sequencing".

^[2] So what's the difference between and and all (or, dually, between or and any)? To be honest, I haven't yet sorted this out completely (in this context). But I feel it's good advice to take and simply as a binary operator - better NOT use varargs! - and think of all as some sort of "lifted" or "higher-order". Hence, what you want to do first is just binary and.

I'll have to address your points about projection etc more properly later. Quite some interesting points but need to be somewhat "dissected" (too many aspects mixed I think), so...

Just this (now me "thinking out loud"):

The converse of "projection" is called "pairing" (or "tupling" in general). The CL combinator for pairing is called D and the two projections D₁ and D₂. Setting aside tedious technicalities^[1], you can think of D's type as a -> b -> {a, b}, D₁'s {a, b} -> a and D₂'s {a, b} -> b where {a, b} is an ad-hoc invention of mine, to stand for "a pair of an a and a b, whatever its concrete representation might be. I'm just avoiding normal parens ( & ) for disambiguation.

Now, this is not exactly the same as v -> {v, v} (in your notation above: v -> (v, v)) and not exactly the same as o -> k -> {o[k], o[k]}^[2]. BUT: stand back and try "blinking a bit" - isn't what you had called "projection" above rather more like the converse, ie pairing (of a special kind)?!

On the other hand,

selecting part of a structure

is a very fine characterization of "projection", IMHO. I just cannot help but think of the two as converses...

Can you see? I'm defining miniscule "homeworks" for myself. Working off each, though, still yields more stuff than I'd like :}

^[1] There's more than one way to encode a pair in CL and so there's more than one possible "implementation" for D and the corresponding D₁, D₂.

^[2] They can of course be implemented exactly in CL. Just tell me.

busterjs / referee-combinators