Preface

meta-lisp uses S-expression syntax.

• The module top level consists of statements.
• Statements are composed of expressions.

All meta-Lisp syntax is presented below in groups.

Table of Contents

• Preface
• Table of Contents
• Comments
  • Line comments
  • (@comment)
• Literals
  • Atoms
  • (@list)
  • (@set)
  • (@hash)
  • (@text)
  • (@quote)
  • (@sexp)
• Variables
  • (define)
  • Variables
  • Qualified variables
• Functions
  • Function application
  • (lambda)
  • (define)
• Types
  • Atomic types
  • Container types
  • (->)
  • (claim)
  • (admit)
  • (the)
  • (all)
  • (define-type)
• Conditionals
  • (if)
  • (when)
  • (unless)
  • (cond)
  • (and)
  • (or)
• Sequencing and bindings
  • (begin)
  • (let)
  • (letrec)
  • local (define)
• Algebraic data types
  • (define-algebraic-type)
  • (define-struct-type)
  • (define-enum)
  • (define-struct)
  • (match)
• Opaque types
  • (define-opaque-type)
• Modules
  • (module)
  • (import)
  • (import-as)
  • (import-all)
  • (private)
• Testing
  • (define-test)

Comments

Line comments

Comments start with ; and extend to the end of the line.

Lisp programmers typically write two ;; for line comments.

;; This is a comment
(define x 42) ;; end-of-line comment

(@comment)

(@comment <sexp> ...)

(@comment) is ignored at compile time and evaluates to void.

(@comment (lambda (<parameter> ...)
            <body>))
(@comment (if <condition> <consequent> <alternative>))
(@comment foo bar)

@comment is recognized as a syntactic keyword by the parser. Its content is a literal S-expression that is not evaluated.

Literals

Atoms

Integers consist of digits, with an optional negative sign.

42
-1
0

Floats have a decimal point.

3.14
-2.5

Strings are wrapped in double quotes.

"hello"
""

Symbols start with a single quote followed by a name.

'foo
'bar

Booleans are true and false — they are not literals, but variables bound to boolean values.

The void value is void — also not a literal, but a variable bound to the void value.

(@list)

(@list <exp> ...)

Creates a list.

(@list 1 2 3)
(@list "a" "b" "c")

The @ prefix avoids occupying the variable name list.

The empty list (@list) evaluates to null, printed as #null.

(@set)

(@set <exp> ...)

Creates a set.

(@set 1 2 3)

(@hash)

(@hash <key> <value> ...)

Creates a hash table.

(@hash 'a 1 'b 2)
(@hash "a" 1 "b" 2)

(@text)

(@text <exp> ...)

Concatenates text expressions into a single text.

(@text "hello" " " "world")
(@text "(" x ")")
(@text)

The example above is equivalent to:

(text-concat (@list "hello" " " "world"))
(text-concat (@list "(" x ")"))
(text-concat (@list))

(@quote)

'<sexp>
(@quote <sexp>)

Create list of symbols or literal atoms.

'(a b c)         ;; => (@list 'a 'b 'c)
'(1 2 3)         ;; => (@list 1 2 3)

Equivalent to:

(@quote (a b c))  ;; => (@list 'a 'b 'c)
(@quote (1 2 3))  ;; => (@list 1 2 3)

(@sexp)

(@sexp <sexp>)

Converts an s-expression into a sexp-t value, preserving source location information for each sub-node.

The sexp-t type is defined as:

(define-enum sexp-t
  (symbol-sexp (content symbol-t) (location source-location-t))
  (text-sexp (content text-t) (location source-location-t))
  (int-sexp (content int-t) (location source-location-t))
  (float-sexp (content float-t) (location source-location-t))
  (list-sexp (elements (list-t sexp-t)) (location source-location-t)))

Usage examples:

(@sexp foo)           ;; => (symbol-sexp 'foo <location>)
(@sexp (a b c))       ;; => (list-sexp
                      ;;      (list (symbol-sexp 'a) (symbol-sexp 'b) (symbol-sexp 'c))
                      ;;      <location>)

Variables

(define)

(define <name> <exp>)

Defines a module-level variable.

(define answer 42)
(define greeting "hello")

Variables

A variable references a bound name.

Names consist of letters, digits, - and other characters.

x
factorial
list-length
list-is-empty

Qualified variables

<module-name>/<name> references a name from another module.

builtin/list-length
builtin/list-is-empty

Qualified names can be used directly without (import). (import) is specifically for removing the <module-name> prefix.

Functions

Function application

(<target> <arg> ...)

Function application is the most important syntax.

If the first position of an S-expression is not a syntactic keyword, it is treated as a function application.

The first position is the function, the rest are arguments.

The function expression is evaluated first, then all argument expressions are evaluated, then the function is applied.

(iadd 1 2)
(println "hello")
((lambda (x) x) 1)

When a function is applied with insufficient arguments, partial application occurs (via currying).

((iadd 1) 2)

Equivalent to:

(iadd 1 2)

And (iadd 1) can be passed as a value to other functions or returned as a result.

(define add1
  (iadd 1))

Equivalent to:

(define (add1 x)
  (iadd 1 x))

(lambda)

(lambda (<parameter> ...)
  <body>)

Creates an anonymous function.

(<parameter> ...) is the formal parameter list, <body> is one or more expressions. When the function is applied, actual arguments are bound to the formal parameters, then <body> is evaluated.

(lambda (x) (iadd x 1))
((lambda (x) (iadd x 1)) 2)  ;; => 3

Multiple parameters:

(lambda (x y)
  (iadd x y))

Equivalent to:

(lambda (x)
  (lambda (y)
    (iadd x y)))

(define)

(define (<name> <parameter> ...)
  <body>)

Defines a function.

Defining a function is equivalent to defining a variable whose value is a lambda.

(define (add1 x)
  (iadd 1 x))

Equivalent to:

(define add1
  (lambda (x)
    (iadd 1 x)))

The function body <body> can be multiple expressions:

(define (f x)
  (let ((y (iadd x 1)))
    (imul y 2)))

Types

Atomic types

Type	Description	Example
int-t	Integer	42 -1
float-t	Float	3.14 -2.5
text-t	String	"hello"
symbol-t	Symbol	'foo
bool-t	Boolean	true false
void-t	Void	void
file-t	File	(open-input-file "abc.txt")

Container types

Type	Description
(list-t E)	Immutable list of elements of type E
(array-t E)	Mutable array of elements of type E
(set-t E)	Set of elements of type E
(hash-t K V)	Hash table with keys K and values V

(->)

(-> <arg-type> ... <ret-type>)

Function type.

Takes <arg-type> parameters and returns <ret-type>.

For example:

(-> int-t int-t)
(-> int-t int-t int-t)
(-> text-t bool-t)

(claim)

(claim <name> <type>)

Declares the type of a name.

The compiler infers the type from (define)'s <body> and checks it against the (claim).

(claim add1 (-> int-t int-t))
(define (add1 x) (iadd x 1))

(claim answer int-t)
(define answer 42)

(admit)

(admit <name> <type>)

Admits the type of a name.

Similar to (claim), but the compiler does not check the (define)'s <body>.

(admit make-point (-> float-t float-t point-t))
(define (make-point x y)
  (@list 'make-point x y))

(the)

(the <type> <exp>)

Explicitly annotates <exp> with a type.

The compiler checks whether <exp>'s actual type matches. Useful for clarifying intent or helping type inference.

(the int-t 42)
(the (-> int-t int-t)
  (lambda (x)
    (iadd x 1)))

(all)

(all (<type-parameter> ...)
  <type>)

A type containing type variables.

Type variables are usually single uppercase letters, referenced within <type>. Used in claim for generic function signatures.

(claim identity (all (A) (-> A A)))

(claim car (all (E) (-> (list-t E) E)))
(claim cdr (all (E) (-> (list-t E) (list-t E))))
(claim cons (all (E) (-> E (list-t E) (list-t E))))

(define-type)

(define-type <type-name>
  <body>)

(define-type (<type-name> <type-parameter> ...)
  <body>)

Defines a new type. <type-name> becomes a type constructor, and <body> is an expression that evaluates to a type. With type parameters, the parameters can be referenced within <body>.

For example:

(define-type (non-empty-list-t A)
  (pair-t A (list-t A)))

Usage:

(the (non-empty-list-t int-t) (make-pair 1 (@list 2 3)))

Conditionals

(if)

(if <condition>
  <consequent>
  <alternative>)

Conditional branch.

<condition> is evaluated. If true, <consequent> is evaluated and returned. Otherwise, <alternative> is evaluated and returned.

(define (abs x)
  (if (int-less x 0)
    (ineg x)
    x))

(when)

(when <condition>
  <body>)

Executes when condition is true. Used for side effects.

When <condition> is true, <body> is evaluated; otherwise skipped. <body> can contain multiple expressions. A (when) expression always returns void.

(when is-debug
  (print "debug mode")
  (newline))

(unless)

(unless <condition>
  <body>)

Executes when condition is false. Used for side effects.

When <condition> is false, <body> is evaluated; otherwise skipped. <body> can contain multiple expressions. An (unless) expression always returns void.

(unless (equal x 0)
  (print (idiv 1 x))
  (newline))

(cond)

(cond
  (<question> <answer>)
  ...)

Multi-branch conditional.

Each <question> is evaluated in order. The <answer> of the first true branch is evaluated and returned. The last <question> can be else as the default branch.

(define (classify x)
  (cond
   ((int-is-positive x) "positive")
   ((int-is-negative x) "negative")
   (else "zero")))

(and)

(and <exp> ...)

Short-circuit and.

Evaluates left to right. Stops and returns the value at the first false. Returns the last value if all are true.

(and (is-int x) (int-is-positive x))

Returns true with zero arguments.

(or)

(or <exp> ...)

Short-circuit or.

Evaluates left to right. Stops and returns the value at the first true. Returns the last value if all are false.

(or (equal x 0) (equal x 1))

Returns false with zero arguments.

Sequencing and bindings

(begin)

(begin <body>)

Sequential execution.

<body> can be multiple expressions <exp> ..., evaluated in order. Returns the value of the last expression. Earlier expressions are typically for side effects.

(begin
  (println "step 1")
  (println "step 2")
  42)  ;; => 42

The <body> of (lambda) and (define) function bodies both work like (begin)'s <body>.

`(define (f x)
  (let ((y (iadd x 1)))
    (imul y 2)))

(let)

(let ((<name> <exp>)
      ...)
  <body>)

Sequential local variable bindings.

Each <exp> can reference previously bound names.

(let ((x 1))
  (iadd x 1))  ;; => 2

(let ((x 1)
      (y 2))
  (iadd x y))  ;; => 3

(let ((x 1)
      (y (iadd x 1)))
  (iadd x y))  ;; => 3

(letrec)

(letrec ((<name> <exp>)
         ...)
  <body>)

Similar to (let), but supports recursion and mutual recursion.

All <exp>s can reference all <name>s.

Mutual recursion:

(letrec ((is-even
          (lambda (n)
            (if (equal n 0)
              true
              (is-odd (isub n 1)))))
         (is-odd
          (lambda (n)
            (if (equal n 0)
              false
              (is-even (isub n 1))))))
  (assert (is-even 4)))

Sequential dependency:

(letrec ((a 1)
         (b (iadd a 1)))
  b)  ;; => 2

local (define)

(define (<name> <parameter> ...) <body>)
(define <name> <exp>)

Local recursive variable bindings in <body>.

Allows (define) inside <body>. Replaces nested (letrec) to reduce indentation.

Mutual recursion (equivalent to the (letrec) example above):

(begin
  (define (is-even n)
    (if (equal n 0)
      true
      (is-odd (isub n 1))))
  (define (is-odd n)
    (if (equal n 0)
      false
      (is-even (isub n 1))))
  (is-even 4))

Sequential dependency:

(begin
  (define a 1)
  (define b (iadd a 1))
  b)  ;; => 2

(let) and (define) can be mixed:

(begin
  (let ((one 1))
    (define a one)
    (define b (iadd a one))
    b))  ;; => 2

Algebraic data types

Algebraic data types are the core data type mechanism in meta-lisp.

meta-lisp provides syntax from explicit to convenient for defining data types:

Syntax	Purpose
(define-algebraic-type)	Multiple constructors, all names explicit
(define-struct-type)	Single constructor, all names explicit
(define-struct)	Single constructor, names generated by convention
(define-enum)	Multiple constructors, names generated by convention

All convenience syntax ultimately expands to (define-algebraic-type). The most commonly used are (define-enum) and (define-struct).

(define-algebraic-type)

(define-algebraic-type <type-name>
  ((<constructor-name> (<field-name> <type>) ...)
   <predicate-name>
   (<field-name> <accessor-name> <modifier-name>)
   ...)
  ...)

(define-algebraic-type (<type-name> <type-parameter> ...)
  ((<constructor-name> (<field-name> <type>) ...)
   <predicate-name>
   (<field-name> <accessor-name> <modifier-name>)
   ...)
  ...)

Algebraic data types are the core mechanism for building composite data structures.

(define-algebraic-type) is the most fundamental form — all names are explicitly specified by the user.

Only <modifier-name> is optional. If omitted, the field reference is immutable.

For example:

(define-algebraic-type point-t
  ((make-point (x float-t) (y float-t))
   is-point
   (x point-x point-put-x)
   (y point-y point-put-y)))

This generates functions with the following types:

(claim make-point (-> float-t float-t point-t))
(claim is-point (-> point-t bool-t))
(claim point-x (-> point-t float-t))
(claim point-y (-> point-t float-t))
(claim point-put-x (-> point-t float-t void-t))
(claim point-put-y (-> point-t float-t void-t))

Usage example:

(define p (make-point 1.0 2.0))
(is-point p)    ;; => true
(point-x p)     ;; => 1.0
(point-put-x p 3.0)
(point-x p)     ;; => 3.0

For single-constructor algebraic types, the predicate is-point is redundant and meaningless. Predicates are only meaningful when there are multiple constructors.

Types defined with (define-algebraic-type) can have type parameters.

For example:

(define-algebraic-type (my-list-t E)
  ((nil)
   is-nil)
  ((li (head E) (tail (my-list-t E)))
   is-li
    (head li-head li-put-head)
    (tail li-tail li-put-tail)))

This generates functions with the following types:

(claim nil (all (E) (-> (my-list-t E))))
(claim is-nil (all (E) (-> (my-list-t E) bool-t)))
(claim li (all (E) (-> E (my-list-t E) (my-list-t E))))
(claim is-li (all (E) (-> (my-list-t E) bool-t)))
(claim li-head (all (E) (-> (my-list-t E) E)))
(claim li-tail (all (E) (-> (my-list-t E) (my-list-t E))))
(claim li-put-head (all (E) (-> (my-list-t E) E void-t)))
(claim li-put-tail (all (E) (-> (my-list-t E) (my-list-t E) void-t)))

(define-struct-type)

(define-struct-type <type-name>
  (<constructor-name> (<field-name> <type>) ...)
  <predicate-name>
  (<field-name> <accessor-name> <modifier-name>)
  ...)

(define-struct-type (<type-name> <type-parameter> ...)
  (<constructor-name> (<field-name> <type>) ...)
  <predicate-name>
  (<field-name> <accessor-name> <modifier-name>)
  ...)

Similar to (define-algebraic-type), but with only one constructor.

(define-struct-type point-t
  (make-point (x float-t) (y float-t))
  is-point
  (x point-x point-put-x)
  (y point-y point-put-y))

Equivalent to:

(define-algebraic-type point-t
  ((make-point (x float-t) (y float-t))
   is-point
   (x point-x point-put-x)
   (y point-y point-put-y)))

The (define-struct-type) syntax comes from Scheme, originating from the Scheme 48 dialect, where it was called define-record-type.

We have extended this syntax with type annotations for <field-name>, i.e. (<field-name> <type>).

(define-algebraic-type) is modeled after (define-struct-type), extended to support multiple constructors.

(define-enum)

(define-enum <type-name>
  (<constructor-name> (<field-name> <type>) ...)
  ...)

(define-enum (<type-name> <type-parameter> ...)
  (<constructor-name> (<field-name> <type>) ...)
  ...)

Defines an algebraic data type with multiple constructors. Each constructor generates names for a predicate, accessor, and modifier by convention.

(define-enum exp-t
  (var-exp (name symbol-t))
  (apply-exp (target exp-t) (arg exp-t))
  (lambda-exp (parameter symbol-t) (body exp-t)))

Equivalent to:

(define-algebraic-type exp-t
  ((var-exp (name symbol-t))
   is-var-exp
   (name var-exp-name var-exp-put-name))
  ((apply-exp (target exp-t) (arg exp-t))
   is-apply-exp
   (target apply-exp-target apply-exp-put-target)
   (arg apply-exp-arg apply-exp-put-arg))
  ((lambda-exp (parameter symbol-t) (body exp-t))
   is-lambda-exp
   (parameter lambda-exp-parameter lambda-exp-put-parameter)
   (body lambda-exp-body lambda-exp-put-body)))

For a given <constructor-name>, the naming rules are:

• <predicate-name> = is-<constructor-name> -- is-var-exp
• <accessor-name> = <constructor-name>-<field-name> -- var-exp-name
• <modifier-name> = <constructor-name>-put-<field-name> -- var-exp-put-name

(define-struct)

(define-struct <type-name>
  (<field-name> <type>)
  ...)

(define-struct (<type-name> <type-parameter> ...)
  (<field-name> <type>)
  ...)

Defines a single-constructor struct. <type-name> must end with -t, in the form <base-name>-t. <base-name> is used to generate other names.

(define-struct point-t
  (x float-t)
  (y float-t))

Equivalent to:

(define-algebraic-type point-t
  ((make-point (x float-t) (y float-t))
   is-point
   (x point-x point-put-x)
   (y point-y point-put-y)))

For a given <type-name>, the naming rules are:

• <type-name> = <base-name>-t -- point-t
• <predicate-name> = is-<base-name> -- is-point
• <constructor-name> = make-<base-name> -- make-point
• <accessor-name> = <base-name>-<field-name> -- point-x
• <modifier-name> = <base-name>-put-<field-name> -- point-put-x

(match)

(match <target>
  (<pattern> <body>)
  ...)

Destructures algebraic data types using pattern matching.

(define-enum exp-t
  (var-exp (name symbol-t))
  (apply-exp (target exp-t) (arg exp-t))
  (lambda-exp (parameter symbol-t) (body exp-t)))

(define (evaluate exp env)
  (match exp
    ((var-exp name)
     (env-lookup-of-fail name env))
    ((apply-exp target arg)
     (apply (evaluate target env) (evaluate arg env)))
    ((lambda-exp parameter body)
     (closure-value env parameter body))))

Opaque types

(define-opaque-type)

(define-opaque-type <type-name> <representation-type>
  (<interface-name> <interface-type>)
  ...)

(define-opaque-type (<type-name> <type-parameter> ...) <representation-type>
  (<interface-name> <interface-type>)
  ...)

Defines an opaque type, hiding its internal representation.

For example, the builtin box-t with internal representation (array-t E):

(define-opaque-type (box-t E) (array-t E)
  (make-box (-> (box-t E)))
  (box-is-empty (-> (box-t E) bool-t))
  (box-put (-> (box-t E) E void-t))
  (box-get-maybe (-> (box-t E) (maybe-t E))))

When implementing interface functions, it is equivalent to declaring:

(claim make-box (all (E) (-> (array-t E))))
(claim box-is-empty (all (E) (-> (array-t E) bool-t)))
(claim box-put (all (E) (-> (array-t E) E void-t)))
(claim box-get-maybe (all (E) (-> (array-t E) (maybe-t E))))

Thus interface functions can use list APIs internally:

(define (make-box) (make-array))

(define (box-put box value)
  (if (box-is-empty box)
    (array-push box value)
    (array-put box 0 value)))

When using interface functions, it is equivalent to declaring:

(claim make-box (all (E) (-> (box-t E))))
(claim box-is-empty (all (E) (-> (box-t E) bool-t)))
(claim box-put (all (E) (-> (box-t E) E void-t)))
(claim box-get-maybe (all (E) (-> (box-t E) (maybe-t E))))

External code can only operate on box-t through interface functions:

(claim box-get (all (E) (-> (box-t E) E)))
(define (box-get box)
  (match (box-get-maybe box)
    ((just value) value)
    ((nothing) (error "box is empty"))))

Modules

A folder can be treated as a package. All .meta files within the package are considered part of it.

A package can have multiple modules.

The module system is decoupled from the file system — the path and filename of a module file do not matter. Code for the same module can be split across different files.

(module)

(module <module-name>)

Declares the current module.

Every .meta file must have a module declaration, typically at the top.

Within the same package, names from other modules can be referenced via <module-name>/<name>.

Functions in the same module, even if written in different files, can be mutually recursive.

even.meta:

(module example)

(define (is-even n)
  (if (equal n 0)
    true
    (is-odd (isub n 1))))

odd.meta:

(module example)

(define (is-odd n)
  (if (equal n 0)
    false
    (is-even (isub n 1))))

(import)

(import <module-name> <name> ...)

Imports specified names from another module.

After importing, names can be used directly without the qualified prefix.

(import math pi circumference)

After this,

math/pi
math/circumference

can be abbreviated to:

pi
circumference

(import-as)

(import-as <module-name> <prefix>)

Imports a module with a modified prefix.

<module-name>/<name> becomes <prefix>/<name>.

(import-as meta m)

After this,

meta/exp-t

can be abbreviated to:

m/exp-t

(import-all)

(import-all <module-name>)

Imports all names from a module.

All names become referenceable without a prefix.

If the current module already has a name with the same name, that name is skipped.

Thus, unqualified references still resolve to the current module's own names. In other words, local definitions can override names introduced by (import-all).

(private)

(private <name> ...)

Marks names as private.

Private names cannot be referenced by other modules.

(module serial-number)

(private serial-number-hash)
(define serial-number-hash (make-hash))

Testing

(define-test)

(define-test <test-name> <body>)

Defines a test.

<body> can contain multiple assertions.

(claim add1 (-> int-t int-t))
(define (add1 x) (iadd x 1))

(define-test add1-test
  (assert-equal 2 (add1 1))
  (assert-equal 0 (add1 -1)))

The following assertions are supported:

• (assert x) -- Asserts x is true.
• (assert-not x) -- Asserts x is false.
• (assert-equal lhs rhs) -- Asserts lhs equals rhs (using equal).
• (assert-not-equal lhs rhs) -- Asserts lhs does not equal rhs.