Imperative representation of Peyton Jones' "enriched" λ-Calc language

README.md

Inter.h is a part of VEBLEN --- a functional language similar to the ML-family of languages, Miranda, Alice, Haskell etc. Still highly WIP.

It contains representation of 'enriched' λ-Calc language to serve as level-1 intermediate representation of VEBLEN.

This 'enriched' λ-Calc is taken from Peyton Jones' monograph "The Implementation of Functional Languages" (1987, University of College London).

We can represent this "enriched" form of λ-Calculus with the grammar which Peyton Jones provides at p40:

expr ::= const
      | variable
      | expr expr # application
      | λ '.' pattern '.' expr # abstraction
      | "let" pattern '=' expr "in" expr
      | "letrec" pattern '=' expr { pattern '=' expr } "in" expr
      | expr "[]" expr # infix
      | "case" expr of pattern "=>" expr { pattern => expr }
      ;
pattern ::= const 
         | variable
         | constructor pattern { pattern }
         ;

My notation is a bit different from what he uses.

An addition to this "enriched" λ-Caclulus is the type system for VEBLEN. I did not bother to remove it. But I did remove memory management macros.

If you stumble upon this, please report any mistakes to .chubak on Discord or chubakbidpaa [at] riseup [dot] net (also gamil).

Enjoy.

Inter.h

#ifndef INTER_H
#define INTER_H

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define INTER_Member INTER_Variant
#define INTER_Ident INTER_String

struct INTER_String;
struct INTER_Type;
struct INTER_Exrp;
struct INTER_Const;
struct INTER_Variable;
struct INTER_Abstraction;
struct INTER_Application;
struct INTER_Let;
struct INTER_Letrec;
struct INTER_Case;
struct INTER_Pattern;
struct INTER_SumType;
struct INTER_ProdType;
struct INTER_Variant;

struct INTER_String {
  uint8_t *buffer;
  size_t buf_length;

  struct INTER_String *next;
};

struct INTER_Type {
  struct INTER_Ident *name;
  struct INTER_Symtab **static_link;

  enum {
    TYPE_Product,
    TYPE_Sum,
    TYPE_Variable,
  } kind;

  union {
    struct INTER_ProdType *v_product;
    struct INTER_SumType *v_sum;
    struct INTER_String *v_variable;
  };
};

struct INTER_Expr {
  enum {
    EXP_Constant,
    EXP_Variable,
    EXP_Application,
    EXP_Abstraction,
    EXP_Let,
    EXP_Letrec,
    EXP_Infix,
    EXP_Case,
    EXP_Pattern,
  } kind;

  union {
    struct INTER_Const *v_const;
    struct INTER_Variable *v_variable;
    struct INTER_Application *v_application;
    struct INTER_Abstraction *v_abstraction;
    struct INTER_Let *v_let;
    struct INTER_Letrec *v_letrec;
    struct INTER_LetIn *v_letin;
    struct INTER_Infix *v_infix;
    struct INTER_Case *v_case;
    struct INTER_Pattern *v_pattern;
  };

  struct INTER_Type *repr_type;
  struct INTER_Expr *next;
};

struct INTER_Const {
  uint8_t repr[MAX_CONST_REPR + 1];
  struct INTER_Symtab **static_link;

  enum {
    CONST_Number,
    CONST_String,
    CONST_Operator,
    CONST_Intrin,
    CONST_Ident,
    CONST_Tuple,
    CONST_List,
    CONST_Map,
  } kind;
};

struct INTER_Variable {
  uint8_t repr[MAX_VARIABLE_REPR + 1];
  struct INTER_Symtab **static_link;

  enum {
    VAR_Function,
    VAR_Constructor,
  } kind;
};

struct INTER_Symtab {
  uintmax_t key_hash;
  struct INTER_String *key;
  struct INTER_String *value;

  struct INTER_Symtab *next;
};

struct INTER_Application {
  struct INTER_Expr *subj;
  struct INTER_Expr *obj;

  enum {
    REL_Surjective,
    REL_Injective,
  } rel;
};

struct INTER_Abstraction {
  struct INTER_Pattern *patt;
  struct INTER_Expr *abs;
};

struct INTER_Let {
  struct INTER_Pattern *rhs;
  struct INTER_Expr *lhs;
  struct INTER_Expr *in;

  struct INTER_Let *next;
};

struct INTER_Letrec {
  struct INTER_Let *lets;
  size_t num_lets;
  struct INTER_Let *in;
};

struct INTER_Infix {
  struct INTER_Expr *left;
  struct INTER_Expr *right;
  struct INTER_String *fatbar;
};

struct INTER_Case {
  struct INTER_Variable *discrim;
  struct INTER_Pattern *patts;
  size_t num_patts;
};

struct INTER_Pattern {
  enum {
    PATT_Const,
    PATT_Variable,
    PATT_Cons,
  } kind;

  struct INTER_Expr *expr1;
  struct INTER_Expr *expr2;

  struct INTER_Pattern *next;
};

struct INTER_SumType {
  ssize_t cons_arity;
  ssize_t poly_arity;

  struct INTER_Variant *variants;
};

struct INTER_ProdType {
  ssize_t memb_num;

  struct INTER_Member *members;
};

struct INTER_Variant {
  struct INTER_Ident *name;
  struct INTER_Type *value;

  struct INTER_Variant *next;
};

#endif