pmatos / nora Goto Github PK

View Code? Open in Web Editor NEW

56.0 6.0 2.0 1.6 MB

An experimental Racket implementation using LLVM/MLIR

License: Apache License 2.0

Racket 2.47% CMake 5.65% Python 1.87% C++ 89.69% C 0.33%

racket mlir llvm-frontend

nora's Introduction

NORA

NORA is an experimental Racket implementation written with a LLVM backend.

Building & Testing

There's not much happening right now, but the right way to try this is by running a cmake configuration build and running the unit and integration tests.

$ git clone https://github.com/pmatos/nora
$ cd nora 
$ mkdir build && cd build
$ cmake -G Ninja ..
$ ninja test

All tests should pass. If you do modifications, you can run the testing workflow with act inside the nora directory with the following command line:

$ act -P ubuntu-22.04=ghcr.io/catthehacker/ubuntu:act-22.04 -j test

Linklets

Everything in Racket land is compiled down into a linklet. The linklet uses the language of Fully Expanded Programs (FEP), therefore to compile Racket one needs an expander, a compiler for FEP, and a FEP runtime. The runtime of FEP is responsible to implement access to OS specific stuff like threads, filesystem, etc (which is what in RacketCS is being done by Rumble).

FEP vs Linklets

FEP (Fully Expanded Programs) are not the same as Linklets. According to Matthew Flatt in an email: "The benefit of the layer is that you can more easily arrive at an implementation where you can run the expander itself on the target platform.". For example, Pycket used FEP but transitioned to using linkets in pycket/pycket#232. Racketscript has this ongoing PR to compile to linklets: racketscript/racketscript#266

Compilation of Racket

Racket is a special language to compile due to its dependency on an expander. This expander is currently implemented in Racket (a few years ago it was in C), and lives in the main racket repository.

Since this expander is written in Racket, it needs to bootstrap itself. In other words, we need a precompiled expander to expand the expander into a linklet so that we can then link that into the compiler to expand user programs. At the moment we are extracting the racket expander into our repo and until we implement our own, there's no reason we can't use Racket's.

So the MVP plan would be to have something that resembles:

      Racket Source --(1)--> expander.rktl (linklet) --------------(4)------------\
                                |                                                 |
User Code ----------------------+(2)-----------> Expanded User Code ---------(5)--|
                                                                                  |
                                                                              NIR Dialect 
                                                                               (MLIR)
                                                                                  |
                                                                                  |(7)
                            Runtime ------------------(3)-------------------> LLVM IR
                                                                                  |
                                                                                 (6)
                                                                                  |
                                                                             JIT/Binary

The driver of the compilation is, unexpectedly, the expander. The expander holds the code to read a racket module and compile it. It is the job of NORA to quickstart that by starting to interpret the expander and provide the hooks required by the expander for everything to work.

Steps:

We extract expander.rktl (the expander linklet through bootstrapping) from the Racket sources;
User code is expander using the expander linklet (requires expander interpreter);
Runtime is compiled using LLVM to LLVM IR;
Expander linklet is compiled using LLVM to LLVM IR;
The compiler frontend transforms the s-expr ast into an MLIR dialect called NIR (Nora IR);
LLVM compiles the LLVM IR modules to Binary or we JIT them;
NIR is lowered to LLVM IR;

Nora Videos

Nora Announcement @ Racketfest 2023

Other related projects using MLIR-C

Brutus
- Suggested by https://github.com/femtomc
PyTorch importer
- Suggested by https://github.com/stellaraccident
Rise Lang
- Also video here RISE A functional pattern-based language in MLIR
MLIR for Functional Programming (video)
Clasp
- Also video: Common Lisp in LLVM

nora's People

Contributors

Stargazers

Watchers

Forkers

matrixkoo vitalyankh

nora's Issues

GCC does not compile nora

GCC can't compile nora atm. However, since we track MLIR very close to HEAD of LLVM it might be that this is not realistic. Support for C++20 might be different etc. So I am putting this here but won't look into it in the near future.

Interpret define-syntaxes

Interpret begin

Add scan-build to push workflow

Should save the SARIF file and add it to the security tab.

Also add a PR workflow that warns the user in the PR if the patch has a problem.

Templatize ToTopLevelNode and ToExprNode

We have defined ToTopLevelNode and ToExprNode structs with operator() to upcast variants. I am sure there's a way to simplify this in C++.

This should be a NFC enhancement.

Interpret begin0

Interpret case-lambda

Implement error handling based on the LLVM diagnostic system

Use LLVM RTTI style class hierarchy for AST Nodes

LLVM provides dyn_cast for downcasts. We should use those goodies from the LLVM lib.
Search for static_cast, and there are mostly the places where dyn_cast can be used.

Investigate use of llvm::dbgs instead of PLOG

We are using plog for logging but possibly better is to use llvm::dbgs facility.

Split writer from dumper

We need a Writer class that writes Racket values, as opposed to the dumper who is supposed to dump ASTNodes.

An example where these differs is values.

The Writer should write (values 1 2) as

1
2

while the Dumper should dump it as

(values 1 2)

;; RUN: norac %s | FileCheck %s
;; CHECK: 12
(linklet () ()
  (define-values (fn) (values 0))
  (let-values (((x) (values 2)))
     (set! fn (lambda (y) (+ x y))))
  (let-values (((x) (values 3)))
     (fn 10)))

There's a warning from ubsan as well:

Cannot set undefined identifier.
Expected lambda expression in Application.
/home/pmatos/dev/nora/src/include/interpreter.h:43:52: runtime error: member call on null pointer of type 'ast::ValueNode'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /home/pmatos/dev/nora/src/include/interpreter.h:43:52 in
UndefinedBehaviorSanitizer:DEADLYSIGNAL
==23846==ERROR: UndefinedBehaviorSanitizer: SEGV on unknown address 0x000000000000 (pc 0x56310e36d3d7 bp 0x7ffebfb63690 sp 0x7ffebfb63650 T23846)
==23846==The signal is caused by a READ memory access.
==23846==Hint: address points to the zero page.
    #0 0x56310e36d3d7 in Interpreter::getResult() const /home/pmatos/dev/nora/src/include/interpreter.h:43:52
    #1 0x56310e36cae7 in main /home/pmatos/dev/nora/src/main.cpp:53:26
    #2 0x7f2ef4c3c78f  (/usr/lib/libc.so.6+0x2378f) (BuildId: 4a4bec3d95a1804443e852958fe59ed461135ce9)
    #3 0x7f2ef4c3c849 in __libc_start_main (/usr/lib/libc.so.6+0x23849) (BuildId: 4a4bec3d95a1804443e852958fe59ed461135ce9)
    #4 0x56310e33aa74 in _start (/home/pmatos/dev/nora/build/bin/norac+0x164a74) (BuildId: ff1360b6f90819159bf3d99f7e8a9ddb2f700ae2)

UndefinedBehaviorSanitizer can not provide additional info.
SUMMARY: UndefinedBehaviorSanitizer: SEGV /home/pmatos/dev/nora/src/include/interpreter.h:43:52 in Interpreter::getResult() const
==23846==ABORTING

I also think that even once this is fixed nora will print 13, rather than 12.

Remove ArithPlus and possibly other AST nodes that are runtime

The current nodes that should be part of runtime should be removed and added to the environment during a prepareRuntime method executed at Interpreter construction time.