kleene.h

Go to the documentation of this file.

/* -*- C -*-
 * Serene programming language
 * Copyright (C) 2019-2026 Sameer Rahmani <lxsameer@lxsameer.com>
 *
 * This library is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library.  If not, see <https://www.gnu.org/licenses/>.
 */
 
#pragma once
 
/** @file
 In admiration of [Stephen Cole Kleene](https://en.wikipedia.org/wiki/Stephen_Cole_Kleene).
 
 The first layer of IR of the compiler. Any source level language should elaborate to this
 IR.
 
 The tree is deliberately small and already in A-normal form. Every operand is an
 atom, a variable, a literal, or a global reference, and anything compound is
 named by an enclosing `let`. The reader checks that shape and rejects input that
 breaks it. Nodes carry no source level types.
*/
 
#include <stddef.h>
#include <stdint.h>
 
#include "serene/rt/errors.h"
 
#ifdef __cplusplus
extern "C" {
#endif
 
typedef struct srn_mm_t srn_mm_t;
typedef struct srn_context_t srn_context_t;
typedef struct srn_value_t srn_value_t;
typedef struct srn_metadata_t srn_metadata_t;
typedef struct srn_sexp_tree_t srn_sexp_tree_t;
 
typedef enum srn_kleene_node_tag_t : size_t {
  /// local variable reference
  SRN_KL_VAR,
  /// literal (int, string, char)
  SRN_KL_LIT,
  /// top level name reference
  SRN_KL_GLOBAL,
  /// closure: params, body
  SRN_KL_FN,
  /// function application
  SRN_KL_APP,
  /// partial application
  SRN_KL_PAPP,
  /// primitive op on atoms
  SRN_KL_PRIM,
  /// constructor: integer tag + atom fields
  SRN_KL_CTOR,
  /// bind one expression, then continue
  SRN_KL_LET,
  /// branch on a scrutinee's constructor tag
  SRN_KL_CASE,
  /// define a label that can jump to
  SRN_KL_LABEL,
  /// jump to a label with atom args
  SRN_KL_JUMP,
} srn_kleene_node_tag_t;
 
typedef struct srn_kleene_node_t srn_kleene_node_t;
 
/// One arm of a `case`. Matches a constructor tag and binds that constructor's
/// fields to fresh locals before running the body.
typedef struct srn_kleene_arm_t {
  /// Constructor tag this arm matches. This tag is basically the tag number
  /// of a constructor in a the type.
  int32_t tag;
  /// Names bound to the constructor's fields, in order
  const char **binders;
  /// Number of fields the constructor carries
  size_t binder_count;
  /// The body of the case
  srn_kleene_node_t *body;
} srn_kleene_arm_t;
 
/// SRN_KL_VAR: a reference to a bound local by name.
typedef struct srn_kleene_local_t {
  const char *name;
} srn_kleene_local_t;
 
/// SRN_KL_GLOBAL: a reference to a top-level definition by name.
typedef struct srn_kleene_global_t {
  const char *name;
} srn_kleene_global_t;
 
/// SRN_KL_FN: a closure. Free variables are captured implicitly by the lowering,
/// the source lists only the parameters.
typedef struct srn_kleene_fn_t {
  /// Parameter names, in order
  const char **params;
  size_t param_count;
  srn_kleene_node_t *body;
} srn_kleene_fn_t;
 
/// SRN_KL_APP and SRN_KL_PAPP: `fn` applied to `args`. Each arg is an atom
/// node (VAR, LIT, or GLOBAL).
typedef struct srn_kleene_app_t {
  srn_kleene_node_t *fn;
  srn_kleene_node_t **args;
  size_t arg_count;
} srn_kleene_app_t;
 
/// SRN_KL_PRIM: primitive `op` over atom `args`.
typedef struct srn_kleene_prim_t {
  /// Name of the primitive operation
  const char *op;
  srn_kleene_node_t **args;
  size_t arg_count;
} srn_kleene_prim_t;
 
/// SRN_KL_CTOR: build a value with constructor `tag` from atom `fields`.
typedef struct srn_kleene_ctor_t {
  /// Constructor tag, relative to the value's type
  int32_t tag;
  /// Atom fields
  srn_kleene_node_t **fields;
  /// Number of fields
  size_t field_count;
} srn_kleene_ctor_t;
 
/// SRN_KL_LET: evaluate `rhs`, bind it to `name`, then evaluate `body`.
typedef struct srn_kleene_let_t {
  /// Name the result of `rhs` is bound to
  const char *name;
  /// The expression to evaluate and bind
  srn_kleene_node_t *rhs;
  /// The continuation, evaluated with `name` in scope
  srn_kleene_node_t *body;
} srn_kleene_let_t;
 
/// SRN_KL_CASE: match `scrutinee` against `arms`. The reader guarantees the tags
/// are distinct.
typedef struct srn_kleene_case_t {
  /// The atom being matched
  srn_kleene_node_t *scrutinee;
  /// The arms, one per matched constructor tag
  srn_kleene_arm_t *arms;
  /// Number of arms
  size_t arm_count;
} srn_kleene_case_t;
 
/// SRN_KL_LABEL: a label `name` taking `params`, whose `body` runs when jumped
/// to, in scope of `cont`.
typedef struct srn_kleene_label_t {
  /// The label's name, referenced by a matching jump
  const char *name;
  /// Parameter names the jump supplies
  const char **params;
  /// Number of parameters
  size_t param_count;
  /// The code run when the label is jumped to
  srn_kleene_node_t *body;
  /// The continuation in scope of the label
  srn_kleene_node_t *cont;
} srn_kleene_label_t;
 
/// SRN_KL_JUMP: hand `args` to the label named `label`.
typedef struct srn_kleene_jump_t {
  /// Name of the target label
  const char *label;
  /// Atom arguments handed to the label's parameters
  srn_kleene_node_t **args;
  /// Number of arguments
  size_t arg_count;
} srn_kleene_jump_t;
 
/// A node of the Kleene tree. `tag` selects the active union member.
struct srn_kleene_node_t {
  /// Which variant `as` holds
  srn_kleene_node_tag_t tag;
 
  /// Source metadata for diagnostics, may be NULL
  srn_metadata_t *metadata;
 
  /// Every member is one word, a pointer or an immediate, so the union stays
  /// word sized. The static assert below pins this.
  union {
    /// SRN_KL_VAR
    srn_kleene_local_t *var;
    /// SRN_KL_LIT: a literal the reader has already boxed
    srn_value_t *lit;
    /// SRN_KL_GLOBAL
    srn_kleene_global_t *global;
    /// SRN_KL_FN
    srn_kleene_fn_t *fn;
    /// SRN_KL_APP and SRN_KL_PAPP
    srn_kleene_app_t *app;
    /// SRN_KL_PRIM
    srn_kleene_prim_t *prim;
    /// SRN_KL_CTOR
    srn_kleene_ctor_t *ctor;
    /// SRN_KL_LET
    srn_kleene_let_t *let;
    /// SRN_KL_CASE
    srn_kleene_case_t *scase;
    /// SRN_KL_LABEL
    srn_kleene_label_t *label;
    /// SRN_KL_JUMP
    srn_kleene_jump_t *jump;
  } as;
};
 
_Static_assert(
  sizeof(((srn_kleene_node_t *)0)->as) == sizeof(void *),
  "srn_kleene_node_t's union should be word sized"
);
 
/// A single top-level definition, `(def name body)`.
typedef struct {
  const char *name;        ///< the global this definition binds
  srn_kleene_node_t *body; ///< the definition's value, often an FN
} srn_kleene_def_t;
 
/// A parsed Kleene module, the unit the reader returns and the builder consumes.
typedef struct {
  srn_kleene_def_t *defs; ///< top-level definitions in source order
  size_t def_count;       ///< number of definitions
} srn_kleene_module_t;
 
/**
 * Parse the Kleene source in `src` (of length `len`) into `*out`.
 *
 * Nodes are allocated from `mm` and remain valid for that arena's lifetime.
 * On success returns NULL and writes the module to `*out`. On a syntax or shape
 * error returns an error built on `ctx`, describing the offending offset, and
 * leaves `*out` untouched.
 */
srn_error_t *srn_kleene_read(srn_context_t *ctx, const char *src, srn_kleene_module_t *out);
 
/**
 * Write `module` back out as Kleene text into the buffer `buf` of size `cap`.
 *
 * Returns the number of bytes the full text needs, not counting a terminating
 * NUL. When that exceeds `cap` the buffer holds a truncated result, call again
 * with a large enough buffer. Reading then printing a module yields equivalent
 * text, which makes the format usable as a golden-test artifact.
 */
size_t srn_kleene_print(const srn_kleene_module_t *module, char *buf, size_t cap);
 
#ifdef __cplusplus
}
#endif