13 ms·

Six Months with Julia: Parse-Time Transpilation in 80 Lines or Less

72 points by montalbano 7y ago

eigenspace 7y ago
Beautiful showcase of Julia's metaprogramming features. For those lispers around, these string macros are used for arbitrary syntax, but if your desired syntax can be parsed by julia's parser, then you can just use regular macros which operate like Lisp1 macros with hygiene being something you opt out of instead of into.
- dan-robertson 7y ago
  I found Julia’s macros to be pretty difficult. Unlike lisp’s, it’s not obvious what the (somewhat lisp like) ast of a given piece of code will be. That ast also frequently changed between language versions. It also wasn’t documented when I last checked (ages ago). I recall the parsing rules around quoting were particularly confusing. It also seemed there were multiple valid asts for some expressions which would sometimes be magically canonicalised but maybe I was mistaken about that. I still think there’s a lot to like about Julia.
  - eigenspace 7y ago
    Yes, I found while I was learning the ropes of metaprogramming, I did a lot of quoting and dumping of code and then just reading the output structure to teach myself how a given piece of code get's lowered. Honestly, even if there were good docs for this, I think just quoting code at the REPL is a faster and more direct way to get that information anyways. This f course does increase the cognitive overhead when you're writing macros. I think this additional complexity is a bit unavoidable given that Julia aims to provide something more like mathy syntax. > t also seemed there were multiple valid asts for some expressions which would sometimes be magically canonicalised but maybe I was mistaken about that. Yes, there are some things like that that happen, and to introspect that process you can use the Meta.@lower macro to see the canonicalization.
    - dan-robertson 7y ago
      > I think this additional complexity is a bit unavoidable given that Julia aims to provide something more like mathy syntax. I’m not sure I agree with regard to the canonicalisation. But also there are generally a few ways to do macros in different languages: - Macros that run in a preprocessor. This can be quite structured with macros written into the source code file (eg C) or they may exist inside the preprocessor (eg camlp4 would have a modified ocaml+macros grammar and output pure ocaml after expanding the macros) - CL style reader macros/Perl style language extensions dynamically modify the syntax/grammar of the language in somewhat arbitrary ways. These may operate at a text level (eg CL) or a higher parse tree level. - CL style: macros look similar to function calls, expansion works in a well defined way and they manipulate a regular syntax tree which is obvious from the syntax - scheme/rust style macros which are rule-based and automatically hygienic. In scheme the rules are easy to write because the AST is obvious. In rust these are a little harder to write but the ast is interesting: macro calls are distinguishable from other syntax at parse time and their arguments are passed on as “trees of tokens with balanced brackets”, a bit like sexps but there are a few types of paren pair. This way the rest of the language syntax need not apply inside the arguments to a macro and one doesn’t need to know the structure of the ast - Julia style macros: you get an untyped ast that isn’t obvious from the written code and you can modify it unhygienically like in CL macros. - ocaml ppx/rust proc macros: you get a typed ast (ie one in which the types let you know all possible ways some syntax you’re interested in may be represented) with certain extension points that may be used to call macros, and you can unhygienically modify that ast. I think in the rust case your ast input may be in the “tree of tokens with balanced parens” form, and you may only be able to look at the ast related to the proc macro call that invokes you. In ocaml ppxes, they get the whole ast of the file and have to find the extension points they care about. There’s no tree-of-tokens in the ast and the extension points need to contain valid expressions/types. The ppx must remove any references to these extension points from the ast (replacing them with valid syntax) or compilation will fail.
otde 7y ago
Thanks for reading, y'all! I am quite new to anything lisp-y, but I did my best to honor the lisp wizards that came before me with this one.
lostmsu 7y ago
In C# since 2007. Feature is called LINQ expressions. Not sure fully grokked it, but the difference appears to be, that in Julia the final Julia code is checked by the compiler at compile time?
- uryga 7y ago
  sorry but did we read the same article? how's compiling brainfuck into Julia via macros related to LINQ?
  - lostmsu 7y ago
    Expression BrainFuck(string code) => Expression.Constant(42); // parser would go there var bfFunc = BrainFuck(@"arbritrary code").Compile(); WriteLine(bfFunc(someArg)); // <- prints 42 As I mentioned later the difference appears to be that Julia does `Compile` call at compile time, thus giving you build-time validation. P.S. this exact code won't work, but it shows the idea.
    - uryga 7y ago
      ah sorry, the naming threw me off. TIL you can manipulate/compile ASTs in C#! https://docs.microsoft.com/en-us/dotnet/api/system.linq.expressions?view=netframework-4.8 https://docs.microsoft.com/en-us/dotnet/api/system.linq.expr... i guess all the macro stuff is under System.Linq.Expressions because LINQ expressions like from score in scores where score > 80 select score aren't just for SQL and can desugar to arbitrary C# code, is that right?
      - lostmsu 7y ago
        I think they are limited quite a bit. E.g. do not support classes, latest C# features, etc. They were made exactly for SQL among other things. With SQL target your example will use this feature: scores will be IQueryable, and "IQueryable.Where" will take Expression, which C# compiler will generate from "score > 80" during compilation. Then the specific database engine will convert that "Expression" instance to SQL query for execution. Of course, there are other ways to generate more .NET code at runtime. But not at compile time, which I wish we had.
peter_d_sherman 7y ago
Excerpt: " julia> a = function (x); x += 1; x += 1; return x; end #13 (generic function with 1 method) julia> @code_llvm a(3) ; @ none:1 within `#13' define i64 @"julia_#13_17607"(i64) { top: ; ┌ @ int.jl:53 within `+' %1 = add i64 %0, 2 <-- <one instruction, not two> ; └ ret i64 %1 }" Prior to reading this article, I did not know that Julia could compile LLVM at the function level... very cool!
- asg 7y ago
  It can also show you assembly at the function level: julia> a=1+2im; b=2+4im; @code_native a+b .text ; ┌ @ complex.jl:271 within `+' pushq %rbp movq %rsp, %rbp ; │ @ complex.jl:271 within `+' @ int.jl:53 vmovdqu (%r8), %xmm0 vpaddq (%rdx), %xmm0, %xmm0 ; │ @ complex.jl:271 within `+' vmovdqu %xmm0, (%rcx) movq %rcx, %rax popq %rbp retq nopw %cs:(%rax,%rax) ; └
- ddragon 7y ago
  You can also use @code_native to look at the assembly code of any function, @code_lowered/@code_typed to see the Julia IR (which you can also modify before fully compiling, which is how source-to-source differentiation with Zygote works) and @code_warntype to evaluate the type inference result. This is a nice diagram of Julia's multi-stage compilation: https://blog.rogerluo.me/images/julia-compile-diagram.png https://blog.rogerluo.me/images/julia-compile-diagram.png
fmakunbound 7y ago
Lisp user here. Is bf" like a reader macro?
- eigenspace 7y ago
  Yes, it's a string macro which is essentially a reader macro. We also have regular macros that operate on Julia's AST. There's some really useful and approachable info here: https://docs.julialang.org/en/v1/manual/metaprogramming/index.html https://docs.julialang.org/en/v1/manual/metaprogramming/inde... You can think of Julia as a Lisp-1 with opt out hygenic macros hiding behind Algol syntax. However, the AST is very lispy: julia> dump(:(x^2 - 1)) Expr head: Symbol call args: Array{Any}((3,)) 1: Symbol - 2: Expr head: Symbol call args: Array{Any}((3,)) 1: Symbol ^ 2: Symbol x 3: Int64 2 3: Int64 1 The `:` is how you quote code in Julia, and `dump` is just a convenient function for printing nested data-structures. Furthermore, you can see this package https://github.com/swadey/LispSyntax.jl https://github.com/swadey/LispSyntax.jl for a string macro that lets julia use Lisp style syntax instead.
  - fmakunbound 7y ago
    Thanks for the explanation. I'm checking it out.
wbhart 7y ago
There's a fairly sophisticated transpiler from a computer algebra system language called Singular, to Julia, here: https://github.com/tthsqe12/SingularInterpreter/ https://github.com/tthsqe12/SingularInterpreter/ It's still being developed, but Basically Works TM. It does give some speedups over the original interpreter for the language, which has been in use for about 30 years: https://github.com/tthsqe12/SingularInterpreter/blob/master/contrib/timings.md https://github.com/tthsqe12/SingularInterpreter/blob/master/...
boznz 7y ago
<pedantic> Shouldnt we replace "lines of code" with "statements" since with most compilers line breaks are optional <\pedantic>

72 points by montalbano 7y ago

Beautiful showcase of Julia's metaprogramming features. For those lispers around, these string macros are used for arbitrary syntax, but if your desired syntax can be parsed by julia's parser, then you can just use regular macros which operate like Lisp1 macros with hygiene being something you opt out of instead of into.

dan-robertson 7y ago
I found Julia’s macros to be pretty difficult. Unlike lisp’s, it’s not obvious what the (somewhat lisp like) ast of a given piece of code will be. That ast also frequently changed between language versions. It also wasn’t documented when I last checked (ages ago). I recall the parsing rules around quoting were particularly confusing. It also seemed there were multiple valid asts for some expressions which would sometimes be magically canonicalised but maybe I was mistaken about that. I still think there’s a lot to like about Julia.
- eigenspace 7y ago
  Yes, I found while I was learning the ropes of metaprogramming, I did a lot of quoting and dumping of code and then just reading the output structure to teach myself how a given piece of code get's lowered. Honestly, even if there were good docs for this, I think just quoting code at the REPL is a faster and more direct way to get that information anyways. This f course does increase the cognitive overhead when you're writing macros. I think this additional complexity is a bit unavoidable given that Julia aims to provide something more like mathy syntax. > t also seemed there were multiple valid asts for some expressions which would sometimes be magically canonicalised but maybe I was mistaken about that. Yes, there are some things like that that happen, and to introspect that process you can use the Meta.@lower macro to see the canonicalization.
  - dan-robertson 7y ago
    > I think this additional complexity is a bit unavoidable given that Julia aims to provide something more like mathy syntax. I’m not sure I agree with regard to the canonicalisation. But also there are generally a few ways to do macros in different languages: - Macros that run in a preprocessor. This can be quite structured with macros written into the source code file (eg C) or they may exist inside the preprocessor (eg camlp4 would have a modified ocaml+macros grammar and output pure ocaml after expanding the macros) - CL style reader macros/Perl style language extensions dynamically modify the syntax/grammar of the language in somewhat arbitrary ways. These may operate at a text level (eg CL) or a higher parse tree level. - CL style: macros look similar to function calls, expansion works in a well defined way and they manipulate a regular syntax tree which is obvious from the syntax - scheme/rust style macros which are rule-based and automatically hygienic. In scheme the rules are easy to write because the AST is obvious. In rust these are a little harder to write but the ast is interesting: macro calls are distinguishable from other syntax at parse time and their arguments are passed on as “trees of tokens with balanced brackets”, a bit like sexps but there are a few types of paren pair. This way the rest of the language syntax need not apply inside the arguments to a macro and one doesn’t need to know the structure of the ast - Julia style macros: you get an untyped ast that isn’t obvious from the written code and you can modify it unhygienically like in CL macros. - ocaml ppx/rust proc macros: you get a typed ast (ie one in which the types let you know all possible ways some syntax you’re interested in may be represented) with certain extension points that may be used to call macros, and you can unhygienically modify that ast. I think in the rust case your ast input may be in the “tree of tokens with balanced parens” form, and you may only be able to look at the ast related to the proc macro call that invokes you. In ocaml ppxes, they get the whole ast of the file and have to find the extension points they care about. There’s no tree-of-tokens in the ast and the extension points need to contain valid expressions/types. The ppx must remove any references to these extension points from the ast (replacing them with valid syntax) or compilation will fail.

otde 7y ago

Thanks for reading, y'all! I am quite new to anything lisp-y, but I did my best to honor the lisp wizards that came before me with this one.

lostmsu 7y ago

In C# since 2007. Feature is called LINQ expressions. Not sure fully grokked it, but the difference appears to be, that in Julia the final Julia code is checked by the compiler at compile time?

uryga 7y ago
sorry but did we read the same article? how's compiling brainfuck into Julia via macros related to LINQ?
- lostmsu 7y ago
  Expression BrainFuck(string code) => Expression.Constant(42); // parser would go there var bfFunc = BrainFuck(@"arbritrary code").Compile(); WriteLine(bfFunc(someArg)); // <- prints 42 As I mentioned later the difference appears to be that Julia does `Compile` call at compile time, thus giving you build-time validation. P.S. this exact code won't work, but it shows the idea.
  - uryga 7y ago
    ah sorry, the naming threw me off. TIL you can manipulate/compile ASTs in C#! https://docs.microsoft.com/en-us/dotnet/api/system.linq.expressions?view=netframework-4.8 https://docs.microsoft.com/en-us/dotnet/api/system.linq.expr... i guess all the macro stuff is under System.Linq.Expressions because LINQ expressions like from score in scores where score > 80 select score aren't just for SQL and can desugar to arbitrary C# code, is that right?
    - lostmsu 7y ago
      I think they are limited quite a bit. E.g. do not support classes, latest C# features, etc. They were made exactly for SQL among other things. With SQL target your example will use this feature: scores will be IQueryable, and "IQueryable.Where" will take Expression, which C# compiler will generate from "score > 80" during compilation. Then the specific database engine will convert that "Expression" instance to SQL query for execution. Of course, there are other ways to generate more .NET code at runtime. But not at compile time, which I wish we had.

peter_d_sherman 7y ago

Excerpt: " julia> a = function (x); x += 1; x += 1; return x; end #13 (generic function with 1 method) julia> @code_llvm a(3) ; @ none:1 within `#13' define i64 @"julia_#13_17607"(i64) { top: ; ┌ @ int.jl:53 within `+' %1 = add i64 %0, 2 <-- <one instruction, not two> ; └ ret i64 %1 }" Prior to reading this article, I did not know that Julia could compile LLVM at the function level... very cool!

asg 7y ago
It can also show you assembly at the function level: julia> a=1+2im; b=2+4im; @code_native a+b .text ; ┌ @ complex.jl:271 within `+' pushq %rbp movq %rsp, %rbp ; │ @ complex.jl:271 within `+' @ int.jl:53 vmovdqu (%r8), %xmm0 vpaddq (%rdx), %xmm0, %xmm0 ; │ @ complex.jl:271 within `+' vmovdqu %xmm0, (%rcx) movq %rcx, %rax popq %rbp retq nopw %cs:(%rax,%rax) ; └
ddragon 7y ago
You can also use @code_native to look at the assembly code of any function, @code_lowered/@code_typed to see the Julia IR (which you can also modify before fully compiling, which is how source-to-source differentiation with Zygote works) and @code_warntype to evaluate the type inference result. This is a nice diagram of Julia's multi-stage compilation: https://blog.rogerluo.me/images/julia-compile-diagram.png https://blog.rogerluo.me/images/julia-compile-diagram.png

fmakunbound 7y ago

Lisp user here. Is bf" like a reader macro?

eigenspace 7y ago
Yes, it's a string macro which is essentially a reader macro. We also have regular macros that operate on Julia's AST. There's some really useful and approachable info here: https://docs.julialang.org/en/v1/manual/metaprogramming/index.html https://docs.julialang.org/en/v1/manual/metaprogramming/inde... You can think of Julia as a Lisp-1 with opt out hygenic macros hiding behind Algol syntax. However, the AST is very lispy: julia> dump(:(x^2 - 1)) Expr head: Symbol call args: Array{Any}((3,)) 1: Symbol - 2: Expr head: Symbol call args: Array{Any}((3,)) 1: Symbol ^ 2: Symbol x 3: Int64 2 3: Int64 1 The `:` is how you quote code in Julia, and `dump` is just a convenient function for printing nested data-structures. Furthermore, you can see this package https://github.com/swadey/LispSyntax.jl https://github.com/swadey/LispSyntax.jl for a string macro that lets julia use Lisp style syntax instead.
- fmakunbound 7y ago
  Thanks for the explanation. I'm checking it out.

wbhart 7y ago

There's a fairly sophisticated transpiler from a computer algebra system language called Singular, to Julia, here: https://github.com/tthsqe12/SingularInterpreter/ https://github.com/tthsqe12/SingularInterpreter/ It's still being developed, but Basically Works TM. It does give some speedups over the original interpreter for the language, which has been in use for about 30 years: https://github.com/tthsqe12/SingularInterpreter/blob/master/contrib/timings.md https://github.com/tthsqe12/SingularInterpreter/blob/master/...

boznz 7y ago

<pedantic> Shouldnt we replace "lines of code" with "statements" since with most compilers line breaks are optional <\pedantic>