Skip to content

refal_compiler.md

Latest commit

 

History

History
243 lines (179 loc) · 7.3 KB

refal_compiler.md

File metadata and controls

243 lines (179 loc) · 7.3 KB

Refal Compiler Documentation

Overview

This document provides comprehensive documentation for the Refal compiler, which translates Refal source code into WebAssembly (WASM), eBPF, and LLVM IR. The compiler is implemented in Rust and follows a modular design to support multiple compilation targets.

Table of Contents

  1. Introduction to Refal
  2. Compiler Architecture
  3. Installation
  4. Usage
  5. Compilation Targets
  6. Examples
  7. Contributing
  8. References

Introduction to Refal

Refal (REcursive Functions Algorithmic Language) is a functional programming language based on pattern matching and term rewriting. It was developed by Valentin Turchin in the 1960s at the Moscow Institute of Physics and Technology.

Key Features

  • Pattern Matching: Refal's primary computation mechanism is pattern matching against expressions.
  • Term Rewriting: Programs are defined as sets of rewriting rules.
  • Functional Paradigm: Refal is a pure functional language with no side effects.
  • Dynamic Typing: Variables are dynamically typed.
  • Variable Types: Refal has three types of variables:
    • s-variables: Match single symbols
    • e-variables: Match arbitrary expressions (including empty)
    • t-variables: Match non-empty expressions

Basic Syntax

A Refal program consists of a set of functions, each containing pattern-matching sentences:

$ENTRY Go {
  /* empty */ = <Prout 'Hello, World!'>;
}

Each sentence has a pattern on the left side of the equals sign and a result expression on the right side. The pattern is matched against the function's argument, and if it matches, the result expression is evaluated and returned.

Compiler Architecture

The compiler follows a traditional multi-stage compilation pipeline:

Refal Source Code → Lexical Analysis → Parsing → AST → 
Semantic Analysis → IR Generation → Target Code Generation → Output

Components

  1. Lexer: Converts Refal source code into tokens
  2. Parser: Builds an Abstract Syntax Tree (AST) from tokens
  3. Semantic Analyzer: Performs type checking and semantic validation
  4. IR Generator: Converts AST to an intermediate representation
  5. Target Code Generators: Convert IR to WASM, eBPF, or LLVM IR
  6. CLI: Command-line interface for the compiler

Directory Structure

refal/
├── src/
│   ├── main.rs            # Entry point
│   ├── parser/            # Lexer and parser implementation
│   │   ├── mod.rs
│   │   ├── lexer.rs
│   │   ├── parser.rs
│   │   └── ast.rs         # AST definitions
│   ├── compiler/          # Compiler implementation
│   │   ├── mod.rs
│   │   ├── ir.rs          # Intermediate representation
│   │   ├── analyzer.rs    # Semantic analyzer
│   │   ├── wasm/          # WebAssembly backend
│   │   │   ├── mod.rs
│   │   │   └── generator.rs
│   │   ├── ebpf/          # eBPF backend
│   │   │   ├── mod.rs
│   │   │   └── generator.rs
│   │   └── llvm/          # LLVM backend
│   │       ├── mod.rs
│   │       └── generator.rs
│   └── cli/               # Command-line interface
│       ├── mod.rs
│       └── options.rs
├── docs/                  # Documentation
├── tests/                 # Integration tests
└── examples/              # Example Refal programs

Installation

Prerequisites

  • Rust (1.56.0 or later)
  • Cargo (comes with Rust)
  • LLVM (for LLVM backend)

Building from Source

  1. Clone the repository:

    git clone https://github.com/larp-devs/refal.git
cd refal

  2. Build the project:

    cargo build --release

  3. The compiled binary will be available at target/release/refal.

Usage

Basic Usage

refal -i input.ref -o output.wasm -t wasm

Command-Line Options

  • -i, --input <FILE>: Input Refal file (required)
  • -o, --output <FILE>: Output file (optional, defaults to input file with appropriate extension)
  • -t, --target <TARGET>: Compilation target (wasm, ebpf, llvm, defaults to llvm)
  • -l, --opt-level <LEVEL>: Optimization level (none, default, aggressive)
  • -v, --verbose: Enable verbose output
  • --help: Display help information

Examples

Compile a Refal program to WebAssembly:

refal -i examples/hello.ref -t wasm

Compile a Refal program to eBPF:

refal -i examples/hello.ref -t ebpf

Compile a Refal program to LLVM IR:

refal -i examples/hello.ref -t llvm

Compilation Targets

WebAssembly (WASM)

The WebAssembly backend generates WebAssembly Text Format (WAT) files that can be converted to binary WASM files using standard WebAssembly tools. The generated WebAssembly code can run in browsers, Node.js, and other WebAssembly runtimes.

Implementation Details

  • Pattern matching is implemented using WebAssembly's control flow constructs
  • Memory management for Refal's dynamic data structures is handled through WebAssembly's linear memory
  • Function calls are implemented using WebAssembly's function table

eBPF

The eBPF backend generates eBPF bytecode that can be loaded into the Linux kernel or used with eBPF virtual machines. This enables Refal programs to run in sandboxed environments with minimal overhead.

Implementation Details

  • Pattern matching is adapted to eBPF's limited instruction set
  • Memory access is carefully managed to comply with eBPF's constraints
  • The generated code passes the eBPF verifier's checks

LLVM

The LLVM backend generates LLVM Intermediate Representation (IR) that can be compiled to native code for various architectures. This provides the best performance and portability.

Implementation Details

  • Pattern matching is implemented using LLVM's control flow constructs
  • Memory management leverages LLVM's memory operations
  • Optimization passes improve the performance of the generated code

Examples

Hello World

$ENTRY Go {
  /* empty */ = <Prout 'Hello, World!'>;
}

Factorial

$ENTRY Go {
  /* empty */ = <Prout <Factorial 5>>;
}

Factorial {
  0 = 1;
  s.N = <Mul s.N <Factorial <Sub s.N 1>>>;
}

Palindrome Checker

$ENTRY Go {
  /* empty */ = <Prout <IsPalindrome 'racecar'>>;
}

IsPalindrome {
  /* empty */ = 'True';
  s.A = 'True';
  s.A e.Middle s.A = <IsPalindrome e.Middle>;
  e.Other = 'False';
}

Contributing

Contributions to the Refal compiler are welcome! Here's how you can contribute:

  1. Fork the repository
  2. Create a feature branch: git checkout -b feature-name
  3. Commit your changes: git commit -am 'Add feature'
  4. Push to the branch: git push origin feature-name
  5. Submit a pull request

Development Workflow

  1. Make sure tests pass: cargo test
  2. Format your code: cargo fmt
  3. Check for linting issues: cargo clippy

References