Skip to content

language_reference.md

Latest commit

 

History

History
243 lines (171 loc) · 6.54 KB

language_reference.md

File metadata and controls

243 lines (171 loc) · 6.54 KB

Refal Language Reference

Introduction

This document provides a reference for the Refal programming language as implemented by our compiler. Refal (REcursive Functions Algorithmic Language) is a functional programming language based on pattern matching and term rewriting, developed by Valentin Turchin in the 1960s.

Syntax

Program Structure

A Refal program consists of a set of function definitions. Each function contains one or more sentences, which are pattern-matching rules.

[<$ENTRY>] FunctionName {
  Pattern1 = Result1;
  Pattern2 = Result2;
  ...
  PatternN = ResultN;
}

The $ENTRY keyword marks an entry point function, which is the starting point of program execution.

Expressions

Refal programs operate on expressions, which are sequences of terms. Terms can be:

  1. Symbols: Atomic values like characters, numbers, or words
  2. Variables: Placeholders that match parts of expressions
  3. Function calls: Invocations of other functions

Symbols

Symbols are the basic building blocks of Refal expressions:

  • Characters: Single characters enclosed in single quotes, e.g., 'a'
  • Numbers: Integer literals, e.g., 42
  • Words: Strings enclosed in single quotes, e.g., 'hello'

Variables

Refal has three types of variables, each with different matching behavior:

  • s-variables: Match exactly one symbol, e.g., s.X
  • e-variables: Match any expression (including empty), e.g., e.List
  • t-variables: Match exactly one term (a symbol or a bracketed expression), e.g., t.Term

Variable names start with the appropriate prefix (s., e., or t.) followed by an identifier.

Function Calls

Function calls are enclosed in angle brackets and contain the function name followed by its argument:

<FunctionName Argument>

The argument is an expression that is passed to the function.

Patterns and Matching

Patterns in Refal are expressions that may contain variables. A pattern matches an expression if there exists a substitution of variables that makes the pattern identical to the expression.

For example, the pattern s.X e.Y s.X matches any expression that starts and ends with the same symbol, with any expression (including empty) in between.

Comments

Refal supports C-style comments:

  • Single-line comments: // This is a comment
  • Multi-line comments: /* This is a multi-line comment */

Semantics

Evaluation Model

Refal uses a pattern-matching evaluation model:

  1. When a function is called with an argument, the sentences of the function are tried in order.
  2. For each sentence, the pattern is matched against the argument.
  3. If a match is found, the variables in the pattern are bound to the corresponding parts of the argument.
  4. The result expression is evaluated with these variable bindings and returned.
  5. If no pattern matches, the program terminates with an error.

Built-in Functions

Refal includes several built-in functions:

  • Prout: Prints an expression to standard output
  • Print: Prints an expression to standard output without a newline
  • Card: Reads a line from standard input
  • Arg: Retrieves command-line arguments
  • Add, Sub, Mul, Div, Mod: Arithmetic operations
  • Numb: Converts a string to a number
  • Symb: Converts a number to a string
  • Chr: Converts a character code to a character
  • Ord: Converts a character to its character code
  • True, False: Boolean constants

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>>>;
}

List Reversal

$ENTRY Go {
  /* empty */ = <Prout <Reverse ('a' 'b' 'c' 'd' 'e')>>;
}

Reverse {
  /* empty */ = /* empty */;
  s.Head e.Tail = <Append <Reverse e.Tail> s.Head>;
}

Append {
  /* empty */ s.X = s.X;
  e.List s.X = e.List s.X;
}

Pattern Matching Examples

// Match the first and last elements of a list
FirstAndLast {
  s.First e.Middle s.Last = (s.First s.Last);
}

// Check if a list is a palindrome
IsPalindrome {
  /* empty */ = 'True';
  s.A = 'True';
  s.A e.Middle s.A = <IsPalindrome e.Middle>;
  e.Other = 'False';
}

// Extract elements at even positions
EvenPositions {
  /* empty */ = /* empty */;
  s.X /* empty */ = s.X;
  s.X s.Y e.Rest = s.X <EvenPositions e.Rest>;
}

Advanced Features

Nested Patterns

Refal allows patterns to contain nested structures, such as parenthesized expressions:

ProcessPair {
  (s.X s.Y) e.Rest = <Process s.X s.Y> <ProcessPair e.Rest>;
  /* empty */ = /* empty */;
}

Pattern Guards

Although not part of standard Refal, some implementations support pattern guards, which are additional conditions that must be satisfied for a pattern to match:

Factorial {
  s.N, <IsPositive s.N> : 'True' = <Mul s.N <Factorial <Sub s.N 1>>>;
  0 = 1;
}

Higher-Order Functions

Refal can implement higher-order functions by passing function names as data:

Map {
  s.F /* empty */ = /* empty */;
  s.F s.X e.Rest = <Apply s.F s.X> <Map s.F e.Rest>;
}

Apply {
  'Square' s.X = <Mul s.X s.X>;
  'Double' s.X = <Mul s.X 2>;
}

Best Practices

Function Organization

  • Place the entry point function at the beginning of the program
  • Group related functions together
  • Use meaningful function and variable names

Pattern Matching

  • Order patterns from specific to general
  • Ensure all possible inputs are covered by patterns
  • Use appropriate variable types (s., e., t.) for clarity

Error Handling

  • Include patterns for error cases
  • Return meaningful error messages
  • Consider using a Result-like pattern for functions that can fail

Performance Considerations

  • Avoid unnecessary function calls
  • Be mindful of pattern matching complexity
  • Consider tail recursion for recursive functions

Limitations and Considerations

  • Refal is a pure functional language without side effects (except for I/O functions)
  • Pattern matching can be computationally expensive for complex patterns
  • The language lacks built-in support for common data structures like maps or sets
  • Error handling is primarily through pattern matching, not exceptions

References