Source Code Overview

See Repo Layout for the overall structure of the repo and the package organization scheme.

Qi Lib

The source code for the Qi language is contained in the qi-lib folder.

At a high level, the code includes:

• Interface macros that embed Qi into Racket
• The Qi language specification which is divided into a core language and extended forms
• An expander that translates extended forms into core forms
• A compiler that translates core forms into Racket

qi-lib
│
├── flow
│   ├── aux-syntax.rkt
│   ├── core
│   │   ├── compiler
│   │   │   ├── 0010-normalize.rkt
│   │   │   ├── 0100-deforest.rkt
│   │   │   ├── 1000-qi0.rkt
│   │   │   ├── 2000-bindings.rkt
│   │   │   └── deforest
│   │   │       ├── cps.rkt
│   │   │       ├── fusion.rkt
│   │   │       ├── syntax.rkt
│   │   │       └── templates.rkt
│   │   ├── compiler.rkt
│   │   ├── passes.rkt
│   │   ├── private
│   │   │   └── form-property.rkt
│   │   ├── runtime.rkt
│   │   ├── strategy.rkt
│   │   └── syntax.rkt
│   ├── extended
│   │   ├── expander.rkt
│   │   ├── forms.rkt
│   │   ├── runtime.rkt
│   │   └── syntax.rkt
│   │   └── util.rkt
│   └── space.rkt
├── flow.rkt
├── info.rkt
├── macro.rkt
├── main.rkt
├── on.rkt
├── private
│   └── util.rkt
├── switch.rkt
└── threading.rkt

The top level of the folder contains the Racket-level interface macros and any supporting utilities for embedding Qi into Racket. flow.rkt invokes the expander followed by the compiler to generate target (Racket) code from source (Qi) code. It also contains main.rkt which is the implicit module required when doing (require qi), and macro.rkt which contains APIs for writing Qi macros, and info.rkt which contains package configuration for Raco.

The flow folder contains the Qi language (i.e. not concerned with its embeddings into Racket). Within the flow folder, core contains the core language, including the compiler (which is responsible for generating Racket code from core Qi expressions), and extended includes all of the non-core forms and the expander (which generates core Qi forms from non-core forms).

The compiler folder within the core folder also contains individual modules for each pass of the compiler. Currently, that's just two passes, normalization (0010-normalize.rkt) and deforestation (0100-deforest.rkt). In addition, it also contains the code generation (1000-qi0.rkt) and bindings (2000-bindings.rkt) "passes." These aren't technically optimization passes, but instead, stages to be done after optimization. But they are incorporated as if they were regular passes. It also contains passes.rkt which has macros that interface with Racket's expansion machinery to report transformations performed by the compiler so that they are visible in the Macro Stepper, and strategy.rkt which contains utilities that may be needed in compiler passes, such as syntax tree traversal and finding fixed points. private/form-property contains interfaces to manipulate a syntax property (called nonterminal) that Syntax Spec attaches to syntax representing a use of a Qi core form, to aid us in traversing the syntax tree to apply compiler rewrite rules. We expect this to be a temporary solution and Syntax Spec will likely abstract this for us in the future.

The deforest folder within compiler contains the implementation of stream fusion. cps.rkt contains the "continuation-passing style" stream components that serve as the deforested runtime for list operations. fusion.rkt contains the pattern matching that rewrites sequences of fusable operations as fused streams. syntax.rkt contains the syntax classes for stream producers, transformers and consumers that form the primitives of the deforested runtime, to which all list operations are mapped. templates.rkt contains some utilities for use in syntax templates used in deforestation.

In the extended folder, the non-core forms are defined as Qi macros in forms.rkt. The expander is implemented in expander.rkt using syntax-spec, which allows us to declare a core-language grammar using a custom syntax, from which it generates the expander for us. util.rkt contains a "de-expander" used to partially reconstruct Qi surface syntax in generating error messages during compilation. The de-expander is a temporary hack, and eventually we would get this information from Syntax Spec.

The syntax.rkt file in each of core and extended contains syntax classes that help in parsing core and non-core syntax, respectively.

The runtime.rkt file in each of core and extended contains the actual implementations (including helper code) for core and non-core forms, respectively.

aux-syntax.rkt contains "auxiliary" syntax classes used in both core and extended forms.

space.rkt contains provisions for using the Qi binding space, for instance, defining functions in the Qi binding space.

private/util.rkt contains non-implementation-related utilities used anywhere.

Qi Test

The tests for the code in the Qi library are contained in the qi-test folder.

qi-test
├── info.rkt
└── tests
    ├── compiler
    │   ├── passes.rkt
    │   ├── private
    │   │   └── expand-util.rkt
    │   ├── rules
    │   │   ├── deforest.rkt
    │   │   ├── full-cycle.rkt
    │   │   ├── normalize.rkt
    │   │   └── private
    │   │       └── deforest-util.rkt
    │   ├── rules.rkt
    │   ├── runtime.rkt
    │   └── strategy.rkt
    ├── compiler.rkt
    ├── definitions.rkt
    ├── expander.rkt
    ├── flow.rkt
    ├── list.rkt
    ├── macro.rkt
    ├── on.rkt
    ├── private
    │   └── util.rkt
    ├── qi.rkt
    ├── space.rkt
    ├── switch.rkt
    ├── threading.rkt
    └── util.rkt

The full test suite is contained in tests/qi.rkt. This test suite is a composition of all of the other test suites located in other modules in the package, each of which may themselves be a composition of test suites located in other, more specific, modules.

Many of these modules test similarly-named modules in qi-lib but don't necessarily reflect the same directory hierarchy as qi-lib. Most of them are normal unit tests that validate the semantics of the language, that is, they ensure that a Qi program with given inputs produces the expected outputs when run.

The test suite in compiler.rkt is somewhat different, however. It composes various test suites in the compiler/ folder that test various aspects of the compiler in different ways, some of which are ordinary tests ensuring that utilities used by the compiler function as expected, while others are syntactic tests (rules.rkt, and the test suites in the rules folder that it composes), validating that certain expected translations are made (for instance, to achieve a speedup at runtime).