From 1c217ee6ac5aacd2f37b1d0e69a71ac94afd5acd Mon Sep 17 00:00:00 2001 From: Daniel Cerqueira Date: Wed, 28 May 2025 12:37:55 +0100 Subject: Init lali programming language. --- liblali.h | 362 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 362 insertions(+) create mode 100644 liblali.h (limited to 'liblali.h') 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 . + * + * + * lali software is based on tiny-lisp + * version from 2016, written by Matthias Pirstitz, which is released to public + * domain under Unlicense . + */ + +#ifndef LIBLALI_H +#define LIBLALI_H + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + + +#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 -- cgit