reika,at15

[ref] dotty

http://dotty.epfl.ch/docs/internals/overall-structure.html
https://www.slideshare.net/Odersky/compilers-are-databases/15
- the new AST is pretty simple

[impl-j][anltr] Variable Syntax and Semantics

Before introducing list and records, it's better to first have variable up and running, which also requires the type checker (infer?) #24 working as well, if we have just pure number .... everything can be done at compile time ...

Syntax

allow/force type in variable declaration a = 1 or int a = 1, we should be able to infer some type
- use let style, allow (not forced) to specify the type, but will infer right hand side and compare, error if what the user want on left side is not what he write on right side

Semantics

mutable, immutable?
there are many kinds of mutable values in OCaml, but there are no mutable variables

Untyped visitor

symbol table?

[impl-go] Go implementation of RCL

Same as the python one #51, the main issue for Go is its runtime lack supports of visitor, there is several PR for that antlr/antlr4#1841 (should be the latest on, updated on 2017/10/03)

One thing to note is, we may not need generated BaseVisitor from ANTLR, most DSL in Go are using handwritten parser and have a walk function, we should be able to find a way to use the context w/o the base

Skylark (build language for bazel) https://github.com/google/skylark/blob/master/syntax/walk.go
HCL https://github.com/hashicorp/hcl/blob/master/hcl/ast/walk.go
TiDB Node#Accept , Visitor#Enter,Leave
OPA Open Policy Agent Visitor

[antlr] Grammar rule for record is wrong: extraneous input ' '

literal
    : BOOL # BoolLiteral
    | INT # IntLiteral
    | DOUBLE # DoubleLiteral
    | STRING # StringLiteral
    ;

// TODO: [0:123]
list
    : '[' literal (' ' literal)* ']'
    ;

term
    : literal # LiteralTerm
    | list # ListTerm
    // FIXME: the record rule is wrong
    | '{' ID ':' literal (',' ID ':' literal)* '}' # RecordTerm // TODO: allow record to have non-literal types? nested record etc.
    | '(' term ')' # BracketsTerm
    ;

java -cp ./third_party/antlr-4.7-complete.jar:./build/libs/reika-0.0.1-SNAPSHOT.jar org.antlr.v4.gui.TestRig me.at15.reika.parser.Reika prog -gui
{a: 123, b: 124};
line 1:3 extraneous input ' ' expecting {BOOL, INT, DOUBLE, STRING}
line 1:8 extraneous input ' ' expecting ID
line 1:11 extraneous input ' ' expecting {BOOL, INT, DOUBLE, STRING}

[impl-j] Visitor pattern

It is used when traverse ANTLR generated parse tree, also mentioned in ANTLR3 book P113 External Tree Visitor

~~it seems~~ the accept method, although identical, need to be declared in every subclass of node

[antlr] Support negative number

We need negative number, but if we put the sign into the token INT and DOUBLE, it would create trouble for 1 - 2, it is no longer INT MINUS INT, but INT INT.

// what we want
irk> -1
-1 : float
irk > 1 - 2
-1 : float

Don't bother trying to handle them in the lexer, handle uniary-minus in the parser instead

https://liucs.net/cs664s16/antlr.html
http://teaching.idallen.com/cst8152/97s/unary_minus.html
add unary operations

[impl-j][test] Add test coverage to CI

JUnit5 does not generate test to standard location
seems no working converage tools JaCoCo #5 etc. junit-team/junit5#1024
- there is a blog https://vocabhunter.github.io/2017/10/17/migrating-to-junit-5.html
- workaround based on PR's refer to that issue 8066a6d
it seems our hits are all 1 .... while some should be more than one

The results of any tests run via the JUnit Platform Gradle plugin will not be included in the standard test report generated by Gradle; however, the test results can typically be aggregated by your CI server software. See the reportsDir property of the plugin
reportsDir file('build/test-results/junit-platform') // this is the default

some code quality platforms (codecay, code beat) also support coverage report
- didn't find the entrance in codebeat

Other code quality tools

[impl-j][antlr] Grammar

Current spec is 0.1

Optional

use new line instead of ;, it is mentioned in ANTLR 4 P216 Fun with Python new lines
support Java Doc like block comment for @author etc.

[git] Invalid folder name breaks checkout on windows

I was trying take notes of the dotty video #35 and download games while on windows, but failed to checkout when clone

fatal: cannot create directory at 'doc/talk/cmps253-Re:Reika': Invalid argument

rename the talk folder

[tapl] Untyped lambda-calculus

From at15/mini-impl#6

Note TAPL use nameless representation for function parameter (binding), we chose to use name, it is easier to implement but error pron, more discussion can be found in the original issue

syntax
parser
ast builder
evaluator

[tapl][antlr] Untyped lambda-calculus is not parsed correctly when abstraction body contains application

From #6 , we got trouble when parsing lambda-calculus when function body is a function application

(lambda x. x) (lambda x. x x);

currently we have

term: ID # Var
    | 'lambda' ID '.' term # Abs
    | term term # App
    | '(' term ')' # Brackets
    ;

the function body is x x, but we didn't parse it correctly

[antlr] Lexer and Parser

Related #18

Actually I didn't really figured out parser lexer problem when building old reika, because it was so simple and I was mainly following grammar on the book that I didn't meet any problem

why we should not put the negative sign in lexer, and make it a parser rule instead
what happens to the symbols we used in parser rules
- based on generated tokens file, they become token with higher precedence
  - why there are two same tokens file ....
difference between lexer and parser
- https://stackoverflow.com/questions/2842809/lexers-vs-parsers
- ANLTR3 books talked about it in P27, one read character and one read tokens
- ANLTR4 book took IP address as example in P81

[ref] Lisp

[impl-j] Better AST Nodes

Current AST node class has several problems

where to put type, now we have type property in the abstract class, but we also treat user specified type as a node, and that type is stored in property v, which may cause mistake when writing visitor, further more, we may not need to store this as a AST node
when compute type, we use type.Checker which generates new tree instead of updating existing one, which waste resource since we never use the old one
keep information of token location, so when there is error, we can specify the exact location, in old reika, there is just one pass (convert parse tree to AST and type check) #31
use annotation ?decorator for the identical accept method
enhance visitor interface #27 , it seems use different name is a more common practice (to avoid error?) or faster?
treat REPL and file differently, when in REPL, every input is a block, while in file, it is not the case, so simple call parser.prog is not correct

Ref

[antlr] Avoid duplicated rules for binary operations including minus

Related #18

Since the syntax for all the binary operations are the same, it's a waste to specify them differently

e   :  e '*' e # Mul
     | e '-' e # Minus
     | INT
     ;

Currently, I have two way to solve this

1. Put all binary operators into one token in lexer

e : e BINARY_OP e # BinaryOp;

BINARY_OP : '*' | '/' | '+' | '-';

which caused two troubles

lost the precedence between '*' and '+' #19
can't handle negative number, because - is for both negative and minus #18

2. Use same label for multiple alternatives

in ANTLR4 P264 15.3 Parser Rules

you can reuse the same label on multiple alternatives to indicate that the parse-tree walker should trigger the same event for those alternatives

e  : e '*' e # BinaryOp
   |  e '+' e # BinaryOp
   | INT
   ;

but you can't get token defined in parser rule, the context for visitor does not have it

it might be possible to get is using label https://github.com/antlr/antlr4/blob/master/doc/parser-rules.md#rule-element-labels

[impl-j] Settings

Compiler Settings, what should be printed etc. scalc could be a good? example again. Need to allow passing in configuration from command line flags using JCommander #37

settings class #45
parse command line arguments #45
? read default setting from home?

[git] Add GitHook to run test before push

when using IDEA, sometimes there are unexpected import i.e. in #31 travis

[impl-j][std] Plot graph in browser when using java runtime

It is possible to draw graph in Java using its own UI library, but it's way better if we can generate graph in browser. We might want to split the runtime to separate project in the future, so using the compiled java file don't need to bring the compiler around (along with antl's icu deps #39 )

find a web framework that supports websocket (so we can push to client)
embed static assets
might just use netty instead of using a full framework

[impl-j][type] Type Checker

It's better to introduce type checker before we start introducing operator overload for +, -

should we have type inference, if so, how much? #26 , actually, we don't have function, there is no need for type inference, variable declaration is just let binding, and user specified type is just a hint
the name for the type checker class, Checker, ~~Reconstructor, Inferer~~

Ref

ANTLR3 Chapter 8. Enforcing Static Type Rules

[impl-py] Python implementation for RCL

Since a main reason for using ANTR is to generate parser in different language, it's time to start using this feature with the simpler dialect RCL #49

generate parser
be able to use it
publish to pypi (?) what about requirements (antlr python3 runtime)
- http://peterdowns.com/posts/first-time-with-pypi.html

[ref] Julia

ast https://docs.julialang.org/en/stable/devdocs/ast/
type system https://docs.julialang.org/en/stable/manual/types/

[antlr] Setup ANTLR

Although for implementing the checker in TAPL we don't need a parser, but the doc in old Reika is not a step by step guide to tell how to use ANTLR from scratch, and it's for Java only while we are planning to support multiple language in the newer version

generate the parser
visualization (don't remember if I have to generate parser and put in class path)
try a different language, js? it would be cool to run it in browser
use it with gradle in real project, might need to setup the project structure first
test helpers
error trackers
- xephonhq/tsdb-proxy-java#5
- parser error
- lexer error, can reuse
- a generic class wrapper w/ getParseError, getLexerError 0288fa4

[tapl] Arithmetic

From at15/mini-impl#6 we start our implementation of TAPL's type checker from simple untyped arithmetic expressions (a.k.a calculator)

define syntax based on OCaml implementation
- everything is expression (I think I saw this in the book, statement is just expression of type unit)
- might need to annotate the grammar so generated parser can have correct context
java ast builder
java interpreter (eval)
python ast builder
- does the annotation work the same way as Java?

[antlr] Precedence of arithmetic operators

If we mix all the binary operators (+, -, *, /) together, we lost the precedence, and user need to explicitly add () to have multiply executed before plus. The reason we put them together is we want to avoid duplicated code in visitor when building AST, because the operator is the only difference

Currently we have (this is wrong)

term
    : literal # TmLiteral
    | '-' term # TmNegative
    | term BINARY_OP term # TmBinaryOp
//    | list # TmList
//    | record # TmRecord
    | '(' term ')' # TmBrackets
    ;

BINARY_OP
    : '+'
    | '-'
    | '*'
    | '/'
    ;

for 1 + 2 * 3 we have

     *
  +   3
1  2

but we should have

   +
1   *
   2  3

[impl-j] Parse command line arguments

apache commons cli seems to be too old
jcommander seems to be a good choice https://github.com/cbeust/jcommander

TODO

-show-phases to show all the phases in compiler (may vary based on source file type, rkmd, rkql etc.)

[dialect] Reika Configuration Language RCL

Due to need from xephonhq/awesome-time-series-database#38 , we want a configuration language that we can point out which line in the configuration file is wrong, i.e. get an AST w/ position instead of clean object (if we want)

syntax, consider YAML, TOML, HCL
ANTLR grammar
implementation, since we want to use it in awesome-tsdb Java may not be the best chocie
- javascript
- python

In the long term, RCL should be merged into Reika compiler

Ref

https://github.com/open-policy-agent/opa a high-level declarative language to author and enforce policies across your stack
https://github.com/hashicorp/hcl2 HCL + HIL string interpolation https://github.com/hashicorp/hil
GCL http://alexandria.tue.nl/extra1/afstversl/wsk-i/bokharouss2008.pdf used in Borg as BCL

[tool] Setup Gradle

ANTLR works best with Java, old Reika tsdb-proxy-java/ql is using Gradle instead of maven, we will continue using Gradle, but I forgot how to use Gradle entirely, this issue is used to track the progress of having a gradle project using ANTLR

multiple projects? TAPL is quite independent from others, and might be split out in the future
- Reika needs a type checker, a interpreter, but they may not need two different projects, just a command line parameter should work just fine
- use different main class would just work, no need to specify the only main class for jar and build multiple jar for different project
gradle tasks for compile the parser
- can't use gradle w/ ANLTR's tree visualization, Makefile may not work as well, ayi did work
bug, it seems gradle task always run when gradle build, use doLast solve this
error-prone https://github.com/google/error-prone
filter using tag, but it seems there is no way except changing gradle file manually
tried to use the standalone launcher, but can't find the class .... https://github.com/junit-team/junit5/blob/master/documentation/src/docs/asciidoc/running-tests.adoc#running-tests-console-launcher-options java -jar junit-platform-console-standalone-1.0.2.jar -d src/main, but no test found ...

[antlr] Left Recursion

When reading the book Language Implementation Patterns (ANTLR3), found a example of list, which seems to have indirect left recursion. But as I remember ANTLR4 handles LR better but still can't handle indirect left recursion (it is mentioned in the ANTLR4 book somewhere)

From ANTLR3 book P26, example text is [a, b, c], [a, [b, c], d]

grammar NestedNameList;
list : '[' elements ']' ;
elements : element (',' element)* ;
element: NAME | list ;
NAME : [a-zA-Z]+;

[test] Use JUnit 5

idea support it https://blog.jetbrains.com/idea/2016/08/using-junit-5-in-intellij-idea/
I don't have much experience w/ JUnit 4 as well, just run and assert, no much lost for migration
http://junit.org/junit5/docs/current/user-guide/

[tapl] Simple Bool

From at15/mini-impl#6

Before implement subtyping, let's first finish typing, this match to simplebool and Chapter 10 in TAPL

[tapl] Untyped lambda-calculus left side for Application does not have to be Abs node, can be a var node

At first I defined abs as type Node and ASTBuilder works, but after switching to Abs, it broke

public static class App extends Node {
  public final Abs abs;
  public final Node param;

guess it is due to (lambda x. x) (lambda x. x x);, in (lambda x. x x) there is a application and x is a var instead of a abs, it can become abs if some one bind it, the var here can be anything ... and (lambda x. x x) seems never terminate?

java.lang.ClassCastException: me.at15.tapl.untyped.UntypedAst$Var cannot be cast to me.at15.tapl.untyped.UntypedAst$Abs

[ref] Juttle dataflow programming language

https://github.com/juttle/juttle

[impl-j] Profiler

We need to know how long we spend on each compile phase, also it would be good if we could count time in our test and REPL, after all ... these data are kind of like time series .... scalac's could be an example

simple timer
collect jvm metrics

[type] Type Inference

Though not sure what our type system gonna be (3 days before the presentation)

we need inference even without function, let x = 1; let y = x + 1
want operator overload, so 1 + [1, 2, 3] can work

Ref

https://stackoverflow.com/questions/415532/implementing-type-inference
Programming Languages: Application and Interpretation 15.3.2 Type Inference

[impl-j] Use Graal vm as backend

Although this repo is almost dead ... just use issues to keep notes

Graal can be used to implement language that runs on jvm (it has many cool features that I don't even understand the name of them ...)

[ref] Pandas

[ref] kx/q

http://code.kx.com/q/
Q for Mortals http://code.kx.com/q4m3/0_Overview/
APL https://en.wikipedia.org/wiki/APL_(programming_language)

Typo

http://code.kx.com/q/tutorials/in-memory-queries/ &amp -> &
http://code.kx.com/q4m3/1_Q_Shock_and_Awe/ homogenous -> homogeneous

[ref] Weld

https://github.com/at15/papers-i-read/issues/89

Weld is a language and runtime for improving the performance of data-intensive applications. It optimizes across libraries and functions by expressing the core computations in libraries using a common intermediate representation, and optimizing across each framework

Shrink Jar size

shrink jar, it's 16 MB w/ deps, comes w/ com.ibm.icu, which is 25 MB .... (introduced by ANTLR? or some other lib?)
add gradle report plugin, https://stackoverflow.com/questions/21645071/using-gradle-to-find-dependency-tree

I think I should not rely on complete ANTLR jar, and only use the runtime jar

[ref] InfluxQL 2.0

[doc] Course project report

Similar to at15/snowbot#20 due on tomorrow ... end of finals week, Friday Dec 15. 6-20 pages ... so again ... it's report driven development

Introduction

motivation
brief summary of the accomplishment
description of notation

Body

related work

Conclusion

accomplishment
open problem

ANTLR generated parser lacks @Override found by error-prone

When using https://github.com/google/error-prone found the following warning, now I manually add it, but it need to be add again after every change of grammar, don't know if anyone mention it or is already fixed in upstream

@Override
public boolean sempred(RuleContext _localctx, int ruleIndex, int predIndex) {

I changed it manually for now ...

[impl-j][test] Re-structure test by level of language features

Currently we have two folder for test scripts, arith and arith_typed which are quite misleading, arith_typed is actually the one with let binding. Since we are adding list a more ideal folder structure should be

primitve
   - int_double_float_only
   - negative
   - binary_op
   - let (previous arith_typed) 
list
   - binary_op_overload (1 + [1, 2, 3])

[impl-j[std] Standard library in Java

We need standard library if we want to more than just calculator, it can be used in both REPL (interpreted) and compiled (actually transpile, we convert to Java file and let javac do the hard work, and run it with our runtime in class path)

Compiler

inject symbol of standard libary

Numeric

vector
random etc.

Graphic

plot #41

[ref] Kotlin

https://kotlinlang.org/docs/reference/

[tracker] Migrate code from tsdb-proxy java

Currently Reika lies in https://github.com/xephonhq/tsdb-proxy-java , it should be a project of its own and imported in tsdb-proxy-java(go) as a library for query and benchmark. Also we can't just copy the code or use git subtree, clean up need to be done and existing git history is not that useful.

Tooling

re structure the folder
list detail plan
doc for tracking issue and progress along side github issues
github issue labels and templates, milestone, project etc.
setup travis
setup lint
- https://www.codacy.com/ seems have used it before
- https://codecov.io used when writing hadoop assignments https://github.com/at15/forum-search, but it seems old report is not stored
- https://coveralls.io old UI, but works fine
- https://codebeat.co/ too strict, always say my go code have too many instance variables ....

Code

migrate the parser and interpreter

Extra

formalize the process and templates for starting and planning a new project, and apply it to other projects I am working on, notably xephon-k, gommon and Ayi
- cadvisor's issues label explanation https://github.com/google/cadvisor/blob/master/docs/development/issues.md
https://docs.sentry.io/internal/contributing/

at15 / reika Goto Github PK

reika's Introduction

Reika

reika's People

Contributors

Stargazers

Watchers

reika's Issues

Ref

1. Put all binary operators into one token in lexer

2. Use same label for multiple alternatives

Ref

Typo

Compiler

Numeric

Graphic

Recommend Projects

Recommend Topics

Recommend Org