last day (15 days later) » 

8:05 PM
Hi @Konrad
On the grammar. Can you clarify some of the following:
 
go ahead …
 
your examples show:
f 42       => f(42)
42 + b     => (42 + b)
f 42 + b   => f(42 + b)
Now, what does 'b' mean? b()?
 
good question!
in fact, the language does support side-effect functions so yes, b must call the function. On the other hand, it must also support first class functions, as in map f array … in this context f wouldn’t be called immediately
 
Also, what would this mean: f 42 + b 43 + 57?
 
I’m guessing this cannot be parsed without type information
 
8:08 PM
f(42 + b(43+57)) or f(42 + b(43) + 57)
@KonradRudolph +1 on that
 
And the second would at the moment be parsed as f((42 + (b(43)) + 57), no?
wait
no, it wouldn’t
 
@KonradRudolph I was expecting the opposite, really
 
Yes, I think (and without having looked at the parse tree) that it’s f(42 + b(43+57))
 
Anyways, if the order is deterministic (doesn't depend on semantic info) you can model it.
 
ok, a language shouldn’t be this misleading
 
8:10 PM
@KonradRudolph My feeling, indeed. I thought I'd get that out of the way before spending too much energy on getting it solved in Spirit :)
 
damn, I’d really hoped that I wouldn’t need parentheses for function calls but looking at this, it’s really just a pain in the ass for the user to figure out what their code is doing
… or do you see a good way of making this crystal-clear to the user (never mind creating an unambiguous grammar) without introducing parentheses?
 
@KonradRudolph Lisp has solved that :)
 
I mean, Haskell somehow does it … but even there it’s sometimes hard to see what’s called and what the arguments are …
Hmpf. Lisp is an elegant language, but not really readable
 
@KonradRudolph It was a joke. They chose the other end of the spectrum
@KonradRudolph I bet it is because Haskel (I hear) is strong typed. So it knows the expected argument list for a function call, and can probably bind function applications to it's directly adjacent arguments based on the knowledge about their number? Just guessing
 
Yes … at least there are some cases in Haskell which cannot be parsed without type information
 
8:15 PM
At least I think you need something akin to map 'f args (or map {f} args etc) for the firstclass function thign
 
So my motivation for doing this without function call parentheses was that the language should mimic the command streams in a Bash shell where one command pipes its output into the next command’s input
to build complex workflows
 
@KonradRudolph You seem to be looking for concatenative programming? Stack based languages are usually examples of that.
IOW just use Brainfuck and never need a parenthesis.
 
You may want to ask @JonPurdy or @CatPlusPlus about this, because they have lots of experience in that field, IIRC
 
I wasn’t aware of the term, but it seems that yes
Essentially I’m working with a lot of data which undergoes one transformation after the other
 
8:17 PM
Factor already has most of the features you described, as far as I can see. the Cat is a big fan of Factor
 
so I thought it would be helpful to have a syntax which expresses this … à la
file.read "data.csv" | csv.parse | project 1 | sort | print
… or somethign like this
 
@KonradRudolph Doesn't postfix notation come naturally to the 'data pipe' model?
 
In a way … but infix notation for expressions is often just more convenient
 
[ 1 7 3 8 ] sort print
[data] csv.parse 1 project sort print
 
Hmm, I like more explicit delimiters than whitespace but yes, this sort of looks like what I had in mind
I’m gonna look at Factor, thanks for the pointer
 
8:21 PM
@KonradRudolph Factor is 'like' smalltalk in that it comes with a 'universe' (the base image in Factor speak) that you can modify while running. It does come with some nifty modes for interop with native code, but I haven't used those myself. Again, ask the Cat maybe
I think he pointed me to an excellent Youtube introduction once in the Lounge
 
 
2 hours later…
10:01 PM
@sehe Just fyi, I just had an idea how to solve the dilemma from above, and I think that Haskell actually does this similarly
the idea is to require that any arguments to a function call that are not a primary token be parenthesised.
That is, the expression f 42 + b 43 + 57 wouldn’t be valid in the first place; instead, the user would have to write either (f 42) + (b (43 + 57)) or something similar
 
hi
 
The change in the grammar would be pretty minimal
This seems to work, too
 
@KonradRudolph Ah, you tried it already?
 
well, the change is really simple
Just change call = id >> +addition; to call = id >> +(('(' > expression > ')') | primary);
 
ah I just made up:
        call = id >> -(primary | '(' > addition > ')')
 
10:06 PM
… and adapt the definition of unary to remove the now-redundant parentheses
well, the argument cannot be optional, otherwise the parser will choke on a + b because it parses a as a function identifier and then cannot handle the rest
So for now this grammar cannot correctly parse nullary functions … those still need to be disambiguated later using type information … I think that’s a fundamental restriction though.
 
@KonradRudolph huh. I'd personally parse a + b as a() + b(), so that would make the argument very optional?
Also, you had it optional before (call = id >> *addition was in your gist)
 
well then you need to change the definition of expression … which, come to think of, I’ll try
Yes, the gist parses the wrong grammar, as it says in the question ;)
 
@KonradRudolph Wait a sec. I think it is easier than all of that.
@KonradRudolph Meaning you changed more than one thing? Now you're confusing me.
 
@sehe Sorry, yes
 
What about: call = id >> *expression with expression = primary | call | '(' > expression > ')'
That ^^ would look somewhat closer to 'usual' expression grammars I've seen and facilitate creating an AST from it a-la the bool grammar example
 
10:15 PM
same problem, no?
 
10:34 PM
@KonradRudolph oh, no plinks :)
I'd say something like this should work:
 
sorry
Anyway, this parser would choke on a + b
 
        expression = addition | simple;

        addition = simple >>
            (  ('+' > expression)
             | ('-' > expression)
            );

        simple = '(' > expression > ')' | call | unary | number;

        call = id >> *expression;

        unary = qi::char_("-+") > expression;

        // terminals
        id = qi::lexeme[+qi::char_("a-z")];
        number = qi::double_;
This parses okay, even for a + ++--4 - a 4 5; on my initial test
 
hmm, I’ll have a look at that
Hmm, that seems to work across a wide range of expressions
I don’t yet see how, though
ah wait, nonsense
but now the operator associativity is wrong
a + b + c will be parsed as a + (b + c)
 
@KonradRudolph That's easily changed, not?
 
Is it? The canonical way to change it is to use the definition of addition that I initially used, and that will (in your case) make the rest go haywire
 
10:47 PM
@KonradRudolph mmm too occupied a.t.m. will look later
 
ok
that said, it actually seems to work
 
@KonradRudolph How do you want it parsed?
I mean, ((a) + b) + c seems obvious. Until you mix in a minus
 
what happens then?
 
a + b - c + d - e -> ?
 
All elementary mathematical operations are usually left associative
Well, ((((a + b) - c) + d) - e
At least by convention
 
10:50 PM
Ok, I guess you can just let it bind to the left by definition :)
True. Sorry about that bf*rt
 
But it seems to be fixed easily
 
    addition = simple >>
       +(  ('+' > expression)
         | ('-' > expression)
        );
?
 
yes, exactly
 
That way, only the ast will become a bit different
 
And it occurs to me that before I continue tweaking the grammar I need to generate an AST and pretty-print it, otherwise this whole thing devolved into guesswork as to how the expression is actually parsed
Incidentally, if you could just post a link to this chat room as an answer to the question I could upboat and accept it
 
10:58 PM
@KonradRudolph Maybe I will :) I'd copy the sample of course. Later
 
11:17 PM
Hah. I've got something postable now
I've implemented the simplest AST I could think of (working with boost::variant as always)
If you enable BOOST_SPIRIT_DEBUG, it will spew 1482 of debug logging for the following input file:
f (+a);
I have a hunch, things could be optimized by adding expectations and reordering branches in parse expressions. However, things parse and you'll have as printing
@KonradRudolph oh, plink btw
 
11:32 PM
@sehe the debug log is nice but it’s not really a substitute for a pretty-printed AST in terms of readability ;)
 
@KonradRudolph You're telling me :) That's why I was sweating on getting the stuff to stream nicely. I just remembered I could of course use Karma to pretty print stuff...
Anyways, with this:
struct addition_t;
struct call_t;
struct unary_t;
typedef double number_t;

typedef boost::variant<
    number_t,
    boost::recursive_wrapper<call_t>,
    boost::recursive_wrapper<unary_t>,
    boost::recursive_wrapper<addition_t>
    > expression_t;

struct addition_t
{
    expression_t lhs;
    char binop;
    expression_t rhs;

    friend std::ostream& operator<<(std::ostream& os, const addition_t& a)
        { return os << "(" << a.lhs << ' ' << a.binop << ' ' << a.rhs << ")"; }
};

struct call_t
And parsing like:
        std::vector<expression_t> script;
        bool ok = qi::phrase_parse(begin, end, *(grammar > ';'), space, script);

        for (auto& expr : script)
            std::cout << "AST: " << expr << '\n';
You get AST: f((+ a()), ) for the same input f (+a);
@KonradRudolph As you can see, I have the trailing , thing because I'm lazy. Will do the karma route now
 
@KonradRudolph mmm. well nevermind, time to go to bed any ways. Let me post the current state of affairs so you can shoot down all the bugs :)
 
Thanks ;)
 
Hmm. Running the test input (a + b - c + d - e) turns out that I'm still building the addition expression the wrong way: 1 + 2 - 3 + 4 - 5 yields
AST: (1 + (2 - (3 + (4 - 5))))
 

  last day (15 days later) »