vavr-io / vavr Goto Github PK

Allow to apply filters to tokens/rules:

• rule & filter1 & filter2 & ...
• TOKEN & filter1 & filter2 & ...

Example Use Case: Function definition

• function name and parameter names are identifiers but no keywords
• an identifier consists of one or more letters (upper and lower case)
• keywords: 'function', 'return'

functionDefinition : ID '(' ( ID ( ',' ID )* )? ')'

ID : [a-zA-Z]+ & ~( 'function' | 'return' )

// this is semantically the same
ID : [a-zA-Z]+ & ~'function' & ~'return'

In the context of filter, not ~ is also applicable to rules and tokens:

• P & ~rule
• P & ~TOKEN

Priority of the filter operator &:

• P1 & P2 P3 is the same as (P1 & P2) P3
• If P1 and P2 should occur in a sequence, write P1 & ( P2 P3 )

See also #12.

Write a generator that is compiled and run in the Maven generate-sources phase.

The classes Tuples and Functions (+ tests) mentioned above are highly repetitive and an ideal target for code generation.

To take advantage of grammar evolution and continuous grammar bootstrapping (as described in #33) execute the grammar bootstrapping as part of the generate-sources phase (does this make sende?).

Tasks:

Create generator framework:

• create generator templates (simulate java rich-string by denoting as array of strings which is joined with newline!?)
• write magic string indentation function for java like this: https://gist.github.com/danieldietrich/5174348

Update Maven .pom:

• compile generator
• run generator
• add new source directories, e.g. src/main/gen, src/test/gen

see Javamagazin 3.2014 S.22

The Grammar parser should warn that the Rules unused and UNUSED are not used.

startRule : STRING | INT ;
unused : .*
STRING : '"' [a-zA-Z]* '"' ;
INT : [0-9]+ ;
UNUSED : .*

• for xml processing (sort, filter/mutator, xslt, ...)
• type helpers (hasInterface, hasSubclass, hasSuperclass, isOfType, ...)
• Tree representation (Nodes (root, inner, leaf), traversal, ...)
• search (DepthFirstSearch, BreadthFirstSearch)
• etc.

precedence (priority of different operators):

• ~[a-z]+ equals (~([a-z]))+

associativity (binding of operators with same priority):

• INT '^' INT '^' INT equals ( INT '^' ( INT '^' INT ) )
• INT '+' INT '+' INT equals ( ( INT '+' INT ) '+' INT )

A greedy quantifier ?, * or + repeats the associated token as many times as possible.

A non-greedy quantifier ??, *? or +? first repeats the associated token as few times as required and then expands step by step while trying to match the next token by backtracking.

Example: Greedy parsing multiline comments

comment : '/*' ~'*/'* '*/'

Example: Non-greedy parsing multiline comments

comment : '/*' .*? '*/'

Create io.rocketscience.java.util.Either<L,R> similar to
http://www.scala-lang.org/api/2.10.3/#scala.util.Either
taking into account that Java 8 has no pattern matching etc.

Follow up on #23

...and move List.zipWithIndex etc. to the Streams wrapper.

• The wrapper implements the delegate/decorator pattern. The original stream is augmented with additional/missing functionality.
• Perhaps move it to javaslang.collection.
• All collection.stream()/.parallelStream() methods should return this wrapper.

• [ok] Sequence/Subrule.toString() : RulePart instead of Rule
• [xx] Code dups in parse methods
• [ok] Comments
• [#49] del isLexical() and add ParseResult.isLexical in order to check at runtime, if Subrule is lexical
• [ok] rename ParseResult.toToken() -> ParseResult.combine()
• [ok] typo: thread-safe instead of thread safe
• [ok] COMBINER = parser -> parser.flatMap(ParseResult::combine)
• [ok] Better: delete Transformer. Instead: lex ? parsed.map(ParseResult::combine) : parsed
• [xx] Transformer extends Function<...> instead of SerializableFunction1

Add classes to package java.collection.tree for DFS/DepthFirstSearch and BFS/BreadthFirstSearch or add static methods

• Tree.depthFirstSearch( T -> T[] )
• Tree.depthFirstSearch( T -> T[], Consumer<Integer> heartbeat, int heartbeatInterval )
• Tree.breadthFirstSearch( T -> T[] )
• Tree.breadthFirstSearch( T -> T[], Consumer<Integer> heartbeat, int heartbeatInterval )

/**
 * The recurse function T -> T[] returns the children of an object (which is not necessarily a Tree).
 * TODO: Should the resulting array be (1) null, (2) T[] {} or (3) Optional<T[]> or (1) + (2)?
 */
@FunctionalInterface
interface Recurse<T> {
  T[] apply(T t);
}

Use case: reduce overhead of parsing a textual grammar to obtain a parser.

Grammar rules can haz no semicolon. Instead of

rule1 : alt11 | alt12 | alt13 ;

rule2 : alt21 | alt22 | alt23 ;

we may write

rule1 : alt11 | alt12 | alt13

rule2 : alt21 | alt22 | alt23

See http://stackoverflow.com/questions/8284919/negating-inside-lexer-and-parser-rules

Repenser-la-propagation-des-exceptions-avec-Java-8

These:

• http://en.m.wikipedia.org/wiki/Monad_(functional_programming)
• http://docs.typelevel.org/api/scalaz/nightly/index.html#scalaz.package$$ReaderWriterState$
• http://stackoverflow.com/questions/11619433/reader-writer-state-monad-how-to-run-this-scala-code
• https://hackage.haskell.org/package/transformers-0.3.0.0/docs/Control-Monad-Trans-RWS-Lazy.html
• http://functionaltalks.org/2013/06/27/ben-kolera-isolating-side-effects-with-monads/

Monad Transformers:

• http://en.m.wikipedia.org/wiki/Monad_transformer
• http://en.m.wikibooks.org/wiki/Haskell/Monad_transformers
• http://book.realworldhaskell.org/read/monad-transformers.html
• http://eed3si9n.com/learning-scalaz/Monad+transformers.html
• http://www.cs.virginia.edu/~wh5a/personal/Transformers.pdf
• http://www.haskell.org/haskellwiki/Monad_Transformers_Explained

Approach: use the exec plugin to execute a code generator:

<plugin>
    <groupId>org.codehaus.mojo</groupId>
    <artifactId>exec-maven-plugin</artifactId>
    <version>${maven.exec.version}</version>
    <executions>
        <execution>
            <id>javaslang-generate-sources</id>
            <goals>
                <goal>java</goal>
            </goals>
            <phase>generate-sources</phase>
            <configuration>
                <mainClass>JavaslangGenerator</mainClass>
                <arguments>
                    <argument>${javaslang.generated.sources.dir}</argument>
                </arguments>
            </configuration>
        </execution>
    </executions>
</plugin>

Alternative labels are helpful when traversing the parse tree.

expr
  : expr '*' expr # Mul
  | expr '+' expr # Add
  | INT # Int
  ;

Direct recursion:

expr : expr '*' expr
     | expr '+' expr
     | INT

INT : '0'..'9'+

Indirect recursion:

expr : mul | add | INT

mul : expr '*' expr

add : expr '+' expr

INT : '0'..'9'+

Formulate and implement a strategy to find the start rule of a grammar.

1st: Write a (textual) meta-grammar of grammars grammar.grammar (in its own language).

2nd: Programatically define an analogous grammar. Because it is a grammar for grammars it should be able to parse the textual meta-grammar defined in the first step.

class BootstrapGrammar extends Grammar {

    BootstrapGrammar() {
        super(BootstrapGrammar::grammar);
    }

    static Parser.Rule grammar() {
        return rule("grammar", ...);
    }
}

3rd: Let the Java grammar written in the 2nd step parse the textual meta-grammar. Transform it to a new Grammar instance. Then generate a Java file containing a Grammar implementation based on this model.

Try<String> bootstrap(String grammarDef) {
    return new BootstrapGrammar().parse(grammarDef))
            .flatMap(parseTree -> transform(parseTree)) // parseTree = concrete syntax tree (cst)
            .map(grammar -> generateJava(grammar)); // grammar = abstract syntax tree (ast)
}

4th: Let the resulting Grammar parse the initial textual grammar grammar.grammar. Again compile it, i.e. transform it to a Grammar instance and generate a Java file containing a Grammar implementation. This second compile result (4th step) should be the same as the first compile result (3rd step). Verify that by comparing both generated files.

Try<String> compile(String grammarDef) {
    return new GeneratedGrammar().parse(grammarDef))
            .flatMap(parseTree -> transform(parseTree)) // parseTree = concrete syntax tree (cst)
            .map(grammar -> generateJava(grammar)); // grammar = abstract syntax tree (ast)
}

• zip
• unzip
• splitAt
• takeWhile
• dropWhile
• ...

Notation:

• subrule : ( alternative1 | )
• rule : alternative3 | ;

Example: mayBeArray : 'var' IDENTIFIER ( '[' ']' | ) ';'

The Antlr parser has two phases: lexing and parsing.

• The lexer may skip characters the parser does not need to see, e.g. whitespace, comments, etc.
• The parser hides so called fragment rules from the parse tree.

We see that Antlr distinguishes the fact of hiding something from the result in a technical way. Parts of the grammar are attributed in different ways because the author of the grammar implicitly knows how the Altr framework works.

The Jslp (Javaslang Parser) has only one phase which combines lexing and parsing. The author of Jslp grammars should be able to attribute parts of the grammar in a uniform way. E.g. the Antlr lets us declare associativity of operators as <assoc=right> and <assoc=left>. Additionally it attributes rules as prefix fragment and it lets us declare (lexer?) rule alternatives as -> skip. That are three different ways to attribute something, which is too diverse, imo.

Therefore I suggest to simplify attributation, e.g. like this

rule<hidden> : alternative1
             | alternative2<hidden>
             | ( subrule1 | subrule2 )<hidden>
             | INT op<assoc=right> INT
             | ( '/*' ~'*/'* '*/' )<combined, hidden> // same as <combined=true, hidden=true>
             ;
WS : [ \t\r\n]+<hidden> ; // same as WS<combined, hidden> : [ \t\r\n]+ ;

Attributes are technically <key=value> pairs and semantically properties of the attributed element. In the case of a boolean property, value may be omitted if it is true, i.e. <hidden=true> is the same as <hidden>.

Perhaps it is better for readability to add the rule attributes after ;, like this:

rule : alternative1
     | alternative2<hidden>
     | ( subrule1 | subrule2 )<hidden>
     | INT op<assoc=right> INT
     | ( '/*' ~'*/'* '*/' )<combined, hidden> // same as <combined=true, hidden=true>
     ;<hidden>
WS : [ \t\r\n]+<hidden> ; // same as WS : [ \t\r\n]+ ;<combined, hidden>

But on the other hand, Java's annotations are prefixed, so we may also do the same here:

<hidden>
rule : alternative1
     | alternative2<hidden>
     | ( subrule1 | subrule2 )<hidden>
     | INT op<assoc=right> INT
     | ( '/*' ~'*/'* '*/' )<combined, hidden> // same as <combined=true, hidden=true>
     ;
WS : [ \t\r\n]+<hidden> ;
// same as:
// <combined, hidden>
// WS : [ \t\r\n]+ ;

Create a template language which allows to write templates like this:

package xyz;

template(String s, Integer i) """
    package javaslang;
    public final class Tuples {
        @for (int i = 1; i <= 3; i++) {
        public static class Tuple@i implements Tuple, Serializable {
            public int arity() {
                return @i;
            }
        }
        } // for-end
    }
"""

The template above expands to this:

package javaslang;
public final class Tuples {
    public static class Tuple1 implements Tuple, Serializable {
        public int arity() {
            return 1;
        }
    }
    public static class Tuple2 implements Tuple, Serializable {
        public int arity() {
            return 2;
        }
    }
    public static class Tuple3 implements Tuple, Serializable {
        public int arity() {
            return 3;
        }
    }
}

The compiled template (= generator) looks like this:

package xyz;

public final Generator??? {
    public static String template(String s, Integer i) {
        final StringBuilder result = new StringBuilder();
        result
            .append("package javaslang;\")
            .append("    public final class Tuples {\n");
        for (int i = 1; i <= 3; i++) {
            result
                .append("        public static class Tuple" + i + " implements Tuple, Serializable {\n")
                .append("            public int arity() {\n")
                .append("                return " + i + ";\n")
                .append("            }\n")
                .append("        }\n")
                .append("    }\n");
        }
        return result;
    }
}

See "Play Framework Starter", p. 27

Given a function of type Function<T, R> and a derived function

final SerializableFunction<T, R> lambda = t -> function.apply(t);

the result of Lambdas.getLambdaSignature(lambda) should be (Function) -> R but actually is (Function, Object) -> Object.

Hint by Lukas Eder:
null instanceof A returns false. Therefor no additional null check is necessary in equals.
See http://docs.oracle.com/javase/specs/jls/se8/html/jls-15.html#jls-15.20.2

Implement a new Parser class RegEx implements RulePart which parses text based on a regular expression.

The syntax is the same as in Java. Example: [^\s][a-zA-Z_0-9]. See java.util.regex.Pattern.

Possible notation: * via slash: /regex/

Given a parser T, a user-defined quantifier consists of a lower bound L and an upper bound U: T{L,U}, where 0 <= L <= U. If L equals U we may write T{L}.

Example 1: [a-z]{1,3} parses a lower case letter which may occur at minimum one and at most three times.

Example 2: The Charset [a-z]{3} is equal to [a-z]{3,3}.

Whitespace configuration:

Update: See also issue #27.

• Whitespace can be declared via WS : ... -> skip ; or WHITESPACE : ... -> skip ;.
• There is an implicit default whitespace declaration, e.g. WS : [ \t\r\n]+ -> skip ;.
• Additionally whitespace should be customizable, i.e. by overwriting the default whitespace rule
• (note: currently not clear how to distinguish fragment and -> skip because there will be only a parsing phase/no lexing phase and then fragment and skip have the same semantics...)

Rules for handling whitespace:

• When parsing (rule starts with lower-case), then whitespace is parsed automatically.
• When lexing (rule starts with upper-case), then whitespace is not parsed automatically.
• Lexer rules can only reference other lexer rules.
• Parser rules can reference parser and lexer rules and can also declare anonymous lexer rules.

The current parser implementation does not distinguish between a lexing and a parsing phase. Lexing takes place while parsing. I.e. the parser changes its scope depending of the rule.

There are two kind of rules - parser rules and lexer rules. Parser rules start with a lower case character, lexer rules start with an upper case character.

When parsing takes place within a parser rule, the parser is in parser scope. The names of the parsed rules are the inner nodes of the resulting parse tree. Whitespace is automatically parsed (and ignored by default). Whitespace handling can be user-defined by the whitespace rule WS (default: WS : [ \t\r\n]+ -> skip ;).

When parsing takes place within a lexer rule, the parser is in lexer scope. Lexer rules may reference only lexer rules. The parse result of a lexer rule is combined, i.e. the results of all referenced lexer rules are combined to one result, where whitespace is not parsed automatically or ignored. The parse results of the combined lexer rules are the leafs of the parse tree.

• simplicity first: only one choice (e.g. not ' and " for string literals)
• negation: be closer to ant '~' or more like java ??
• ...

Charset, Range and Literal Parsers have to escape/unescape special characters properly.

Example:

List.prependAll(Iterable) will make javaslang.collection.List easier to use in conjunction with java.util Collections.

The same holds for Tree/Node, e.g. Node.attachAll(Iterable) instead of Node.attachAll(List).

Invent a Pattern interface which adds more mature pattern matching capabilities to Match API.
Focus lies on object decomposition using type and value information. Wildcards would be great.

Brainstorming:

// class to match by pattern
class A {
  String val1;
  int val2;
  boolean irrelevantForTheFollowingMatch;
}

// tagging interface
interface Pattern {
}

// example: Proxy creation to get a View of A
interface APattern<A> extends Pattern {
  String val1(A obj); // matches an A with any val1
  default int val2(A obj) { return 2; } // matches an A with val2 == 2
}

// caze will create a Proxy for p of type APattern
// which also gives access to the runtime object of type A
// and the attributes defined in
Matchs.caze(APattern p, (A obj) -> a.val1)

Additionally, it would be nice to provide a programatic way to create Patterns instead of an interface declaration, e.g. via Annotation, Builder, ...

The constraint is, as always for Javaslang, to use only JVM (+ Javaslang) classes and no 3rd party libs.

S.th. similar to this:

// TODO: return type R vs Void
public <T> Builder<R> caze(SerializableConsumer<T> consumer) {
    requireNonNull(consumer, "consumer is null");
    cases.add(caze(None.instance(), (T t) -> {
        consumer.accept(t);
    }, Void.class));
    return this;
}

Delete Parser.isLexical() and add ParseResult.isLexical() in order to check at runtime if a Subrule is lexical.

Could this help? https://gist.github.com/aslakhellesoy/3678beba60c109eacbe5

Status quo:

Matchs
    .<?> caze((Some<String> s) -> s) // currently this case matches
    .caze((Some<Integer> s) -> s)
    .apply(new Some<>(1));

Goal:

Matchs
    .<?> caze((Some<String> s) -> s)
    .caze((Some<Integer> s) -> s) // match by correct type and generic type parameter
    .apply(new Some<>(1));

Add openjdk8 to the list of jdks of .travis.yml.
Ensure that code coverage runs only once. Need a test-script for that?

Code is covered 100%, now add more semantic tests.

Example: javaslang.lambda.FunctionsTest misses tests of correct behavior of SerializablePredicate etc.

Definition of a function:

• list(element, delimiter) : ( element ( delimiter element )* )?

Usage of a function

• jsonArray : '[' list(json, ',') ']' // Java-like
• jsonArray : '[' (list json ',') ']' // Lisp-like

Unfortunately the Java-like notation is ambiguous, because f(x)* could mean:

1. f(x)* = f (x)* = f x*: first f then zero or more times x
2. zero or more times of the rule reference f(x)

A Lisp-like notation clarifies this a little bit:

1. (f x*) applies x* to f
2. (f x)* applies x to f and repeats the result

The priority of function calls should be lower than the priority of operators.

Wire together tree traversal (with walkers: preorder, inorder, postorder, level-order) and tree transformation.

Suggestion: Take the rewrite-rule approach using the Match API (enhanced by #8).