Init lali programming language.

1 files changed, 362 insertions, 0 deletions

diff --git a/liblali.h b/liblali.h
new file mode 100644
index 0000000..797587d
--- /dev/null
+++ b/liblali.h
@@ -0,0 +1,362 @@
+/*
+ * 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
+    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 *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 *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 ////////////////////////////////////////////////////////////
+
+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