path: root/liblali.h

/*
 * lali (Lali Another Lisp Implementation)
 *
 * Author: Daniel Cerqueira (dan.git@lispclub.com)
 * Maintainer: Daniel Cerqueira (dan.git@lispclub.com)
 * Version: 0.0
 * Keywords: lali, lisp, implementation, interpreter, lisp1.5,
 *           computer programming language
 * Homepage: https://gitlab.com/alexandre1985/lali
 * SPDX-License-Identifier: GPL-3.0-or-later
 *
 * Copyright (C) 2025 Daniel Cerqueira
 *
 * This file is part of lali.
 *
 * lali is free software; you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation; either version 3 of the License, or (at your option) any later
 * version.
 *
 * This program 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program; if not, see <https://www.gnu.org/licenses/>.
 *
 *
 * lali software is based on tiny-lisp <https://github.com/matp/tiny-lisp/>
 * version from 2016, written by Matthias Pirstitz, which is released to public
 * domain under Unlicense <https://unlicense.org/>.
 */

#ifndef LIBLALI_H
#define LIBLALI_H

#include <sys/mman.h>
#include <sys/stat.h>
#include <ctype.h>
#include <errno.h>
#include <fcntl.h>
#include <setjmp.h>
#include <stdarg.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <time.h>


#if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
#define MAP_ANONYMOUS        MAP_ANON
#endif

typedef struct Object Object;

typedef enum Type {
  TYPE_NUMBER,
  TYPE_STRING,
  TYPE_SYMBOL,
  TYPE_CONS,
  TYPE_LAMBDA,
  TYPE_MACRO,
  TYPE_PRIMITIVE,
  TYPE_ENV
} Type;

struct Object {
  Type type;
  size_t size;
  union {
    /* struct { double number; };                      // number */
    struct { char string[sizeof (Object *[3])]; };  // string, symbol, number
    struct { Object *car, *cdr; };                  // cons
    struct { Object *params, *body, *env; };        // lambda, macro
    struct { int primitive; char *name; };          // primitive
    struct { Object *parent, *vars, *vals; };       // env
    struct { Object *forward; };                    // forwarding pointer
  };
};

extern Object *symbols;
extern Object *nil;
extern Object *n;
extern Object *t;
extern Object *f;

typedef enum StreamType {
  STREAM_TYPE_STRING,
  STREAM_TYPE_FILE
} StreamType;

typedef struct Stream {
  StreamType type;
  char *buffer;
  int fd;
  size_t length, capacity;
  off_t offset, size;
} Stream;

typedef struct Memory {
  size_t capacity, fromOffset, toOffset;
  void *fromSpace, *toSpace;
} Memory;

extern jmp_buf exceptionEnv;

// EXCEPTION HANDLING /////////////////////////////////////////////////////////

#define exception(...)       exceptionWithObject(NULL, __VA_ARGS__)

#ifdef __GNUC__
void exceptionWithObject(Object *object, char *format, ...)
  __attribute__ ((noreturn, format(printf, 2, 3)));
#endif

void exceptionWithObject(Object *object, char *format, ...);

// GARBAGE COLLECTION /////////////////////////////////////////////////////////

/* This implements Cheney's copying garbage collector, with which memory is
 * divided into two equal halves (semispaces): from- and to-space. From-space
 * is where new objects are allocated, whereas to-space is used during garbage
 * collection.
 *
 * When garbage collection is performed, objects that are still in use (live)
 * are copied from from-space to to-space. To-space then becomes the new
 * from-space and vice versa, thereby discarding all objects that have not
 * been copied.
 *
 * Our garbage collector takes as input a list of root objects. Objects that
 * can be reached by recursively traversing this list are considered live and
 * will be moved to to-space. When we move an object, we must also update its
 * pointer within the list to point to the objects new location in memory.
 *
 * However, this implies that our interpreter cannot use raw pointers to
 * objects in any function that might trigger garbage collection (or risk
 * causing a SEGV when accessing an object that has been moved). Instead,
 * objects must be added to the list and then only accessed through the
 * pointer inside the list.
 *
 * Thus, whenever we would have used a raw pointer to an object, we use a
 * pointer to the pointer inside the list instead:
 *
 *   function:              pointer to pointer inside list (Object **)
 *                                  |
 *                                  v
 *   list of root objects:  pointer to object (Object *)
 *                                  |
 *                                  v
 *   semispace:             object in memory
 *
 * GC_ROOTS and GC_PARAM are used to pass the list from function to function.
 *
 * GC_TRACE adds an object to the list and declares a variable which points to
 * the objects pointer inside the list.
 *
 *   GC_TRACE(gcX, X):  add object X to the list and declare Object **gcX
 *                      to point to the pointer to X inside the list.
 */

#define GC_ROOTS             gcRoots
#define GC_PARAM             Object *GC_ROOTS

#define GC_PASTE1(name, id)  name ## id
#define GC_PASTE2(name, id)  GC_PASTE1(name, id)
#define GC_UNIQUE(name)      GC_PASTE2(name, __LINE__)

#define GC_TRACE(name, init)                                                     \
  Object GC_UNIQUE(GC_ROOTS) = { TYPE_CONS, .car = init, .cdr = GC_ROOTS };      \
  Object **name = &GC_UNIQUE(GC_ROOTS).car;                                      \
  GC_ROOTS = &GC_UNIQUE(GC_ROOTS)

Object *gcMoveObject(Object *object);

void gc(GC_PARAM);

// MEMORY MANAGEMENT //////////////////////////////////////////////////////////

size_t memoryAlign(size_t size, size_t alignment);

Object *memoryAllocObject(Type type, size_t size, GC_PARAM);

// CONSTRUCTING OBJECTS ///////////////////////////////////////////////////////

Object *newObject(Type type, GC_PARAM);

Object *newObjectFrom(Object **from, GC_PARAM);

//Object *newNumber(double number, GC_PARAM);
Object *newNumber(char *string, GC_PARAM);

Object *newObjectWithString(Type type, size_t size, GC_PARAM);

Object *newStringWithLength(char *string, size_t length, GC_PARAM);

Object *newString(char *string, GC_PARAM);

Object *newCons(Object **car, Object **cdr, GC_PARAM);

//Object *newSymbolWithLength(char *string, size_t length, GC_PARAM);
Object *newSymbolWithLength(Type type, char *string, size_t length, GC_PARAM);

Object *newSymbol(char *string, GC_PARAM);

Object *newObjectWithClosure(Type type, Object **params, Object **body, Object **env, GC_PARAM);

Object *newLambda(Object **params, Object **body, Object **env, GC_PARAM);

Object *newMacro(Object **params, Object **body, Object **env, GC_PARAM);

Object *newPrimitive(int primitive, char *name, GC_PARAM);

Object *newEnv(Object **func, Object **vals, GC_PARAM);

// STREAM INPUT ///////////////////////////////////////////////////////////////

/* The purpose of the stream functions is to provide an abstraction over file
 * and string inputs. In order to accommodate the REPL, we need to be able to
 * process character special files (such as stdin) character by character and
 * evaluate expressions as they are being entered.
 */

int streamGetc(Stream *stream);

Stream *streamSeek(Stream *stream, int offset);

int streamPeek(Stream *stream);

// READING S-EXPRESSIONS //////////////////////////////////////////////////////

Object *readExpr(Stream *stream, GC_PARAM);

int readNext(Stream *stream);

int initialReadNext(Stream *stream);

int peekForward(Stream *stream, bool shebang);

int peekNext(Stream *stream);

int readWhile(Stream *stream, int (*predicate)(int ch));

Object *readUnary(Stream *stream, char *symbol, GC_PARAM);

Object *readString(Stream *stream, GC_PARAM);

int isSymbolChar(int ch);

Object *readNumberOrSymbol(Stream *stream, GC_PARAM);

Object *reverseList(Object *list);

Object *readList(Stream *stream, GC_PARAM);

// WRITING OBJECTS ////////////////////////////////////////////////////////////

char *removeZeroPadding(char *string);

void writeObject(Object *object, bool readably, FILE *file);

// ENVIRONMENT ////////////////////////////////////////////////////////////////

/* An environment consists of a pointer to its parent environment (if any) and
 * two parallel lists - vars and vals.
 *
 * Case 1 - vars is a regular list:
 *   vars: (a b c), vals: (1 2 3)        ; a = 1, b = 2, c = 3
 *
 * Case 2 - vars is a dotted list:
 *   vars: (a b . c), vals: (1 2)        ; a = 1, b = 2, c = nil
 *   vars: (a b . c), vals: (1 2 3)      ; a = 1, b = 2, c = (3)
 *   vars: (a b . c), vals: (1 2 3 4 5)  ; a = 1, b = 2, c = (3 4 5)
 *
 * Case 3 - vars is a symbol:
 *   vars: a, vals: nil                  ; a = nil
 *   vars: a, vals: (1)                  ; a = (1)
 *   vars: a, vals: (1 2 3)              ; a = (1 2 3)
 *
 * Case 4 - vars and vals are both nil:
 *   vars: nil, vals: nil
 */

Object *envLookup(Object *var, Object *env);

Object *envAdd(Object **var, Object **val, Object **env, GC_PARAM);

Object *envSet(Object **var, Object **val, Object **env, GC_PARAM);

// PRIMITIVES /////////////////////////////////////////////////////////////////

Object *primitiveSpace(Object **args, GC_PARAM);

Object *primitiveAtom(Object **args, GC_PARAM);

/* Object *primitiveEq(Object **args, GC_PARAM);
 */

Object *primitiveDif(Object **args, GC_PARAM);

Object *primitiveCar(Object **args, GC_PARAM);

Object *primitiveCdr(Object **args, GC_PARAM);

Object *primitiveCons(Object **args, GC_PARAM);

Object *primitivePrint(Object **args, GC_PARAM);

Object *primitivePrinc(Object **args, GC_PARAM);

Object *primitiveNewline(Object **args, GC_PARAM);

Object *primitiveRead(Object **args, GC_PARAM);

Object *primitiveTime(Object **args, GC_PARAM);

Object *primitiveRandom(Object **args, GC_PARAM);

Object *primitiveAdd(Object **args, GC_PARAM);

Object *primitiveSubtract(Object **args, GC_PARAM);

Object *primitiveMultiply(Object **args, GC_PARAM);

Object *primitiveDivide(Object **args, GC_PARAM);

Object *primitiveRemainder(Object **args, GC_PARAM);

// EVALUATION /////////////////////////////////////////////////////////////////

/* Scheme-style tail recursive evaluation. evalProg, evalProgs, evalCond, and
 * PRIMITIVE_EVAL, return the object in the tail recursive position to be
 * evaluated by evalExpr. Macros are expanded in-place the first time they are
 * evaluated.
 */

Object *evalExpr(Object **object, Object **env, GC_PARAM);

Object *evalSet(Object **args, Object **env, GC_PARAM);

Object *evalProg(Object **args, Object **env, GC_PARAM);

Object *progs1(Object **stop, Object **body, Object **env, GC_PARAM);

Object *evalProgs(Object **args, Object **env, GC_PARAM);

Object *evalCond(Object **args, Object **env, GC_PARAM);

Object *evalFill(Object **args, Object **env, GC_PARAM);

Object *evalLambda(Object **args, Object **env, GC_PARAM);

Object *evalMacro(Object **args, Object **env, GC_PARAM);

Object *expandMacro(Object **macro, Object **args, GC_PARAM);

Object *expandMacroTo(Object **macro, Object **args, Object **cons, GC_PARAM);

Object *evalList(Object **args, Object **env, GC_PARAM);

Object *evalRead(GC_PARAM);

Object *newRootEnv(GC_PARAM);

#endif