Instantly share code, notes, and snippets.

# cellularmitosis/Makefile

Last active January 11, 2020 05:10
Show Gist options
• Save cellularmitosis/9d3dc3803979fb461350c3873617f78e to your computer and use it in GitHub Desktop.
A Lisp interpreter in C, part 3: floats

Blog 2020/1/10

# A Lisp interpreter in C, part 3: floats

Let's learn how to write a Lisp interpreter in C!

In part 3, we implement support for reading, evaluating, and printing C double floating-point numbers.

This post doesn't cover any new ground (it is nearly identical to part 2), but will set up some interesting type promotion issues for us to tackle in later posts!

## Lisp forms

We add a new struct to represent C double floating-point numbers:

forms.h:

struct CDouble_ {
FormType type;
double value;
};
typedef struct CDouble_ CDouble;

int new_cdouble(CDouble** cdpp, double d);
bool is_cdouble(Form* formp);

and add an entry to our FormType enum:

forms.h:

TypeSymbol = 10,
TypeCLong = 20,
+    TypeCDouble = 30,
};
typedef enum FormType_ FormType;

We add a function which attempts to parse a floating-point number:

/* Tries to parse a double from buffp intp dp.
Returns true or false. */
static bool try_parse_double(const char* buffp, double* dp) {
char* endptr;
double d = strtod(buffp, &endptr);
if (errno != 0) {
errno = 0;
return false;
} else if (endptr == buffp || *endptr != '\0') {
return false;
} else {
*dp = d;
return true;
}
}

return 0;
}
}
+
+        /* a floating-point literal. */
+        double d;
+        success = try_parse_double(buffp, &d);
+        if (success) {
+            CDouble* cdp;
+            new_cdouble(&cdp, d);
+            *formpp = (Form*)cdp;
+            return 0;
+        }

/* assume anything else is a symbol. */
Symbol* symp;

## The evaluator

eval.c:

Returns 0. */
int eval_form(Form* formp, Form** resultpp) {
/* for now, all forms evaluate to themselves. */
-    if (is_symbol(formp) || is_clong(formp)) {
+    if (is_symbol(formp) || is_clong(formp) || is_cdouble(formp)) {
*resultpp = formp;
return 0;

## The printer

We implement support for printing CDouble objects:

printer.c: (error handling elided):

/* Prints the CDouble in dp into fp.
Returns 0 or errno. */
static int print_cdouble(CDouble* dp, FILE* fp) {
int err = fprintf(fp, "CDouble: %f", dp->value);
return 0;
}

and stitch it into print_form():

printer.c:

} else if (is_clong(formp)) {
CLong* lp = (CLong*)formp;
return print_clong(lp, fp);
+    } else if (is_cdouble(formp)) {
+        CDouble* dp = (CDouble*)formp;
+        return print_cdouble(dp, fp);
} else {
assert(false);
}

## Try it out

Our interpreter understands floating-point now!

\$ echo foo 42 3.14 | ./lisp
Symbol: foo
CLong: 42
CDouble: 3.140000

## Next time

In part 4 we'll add support for strings!

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /* This file is Copyright (C) 2019 Jason Pepas. */ /* This file is released under the terms of the MIT License. */ /* See https://opensource.org/licenses/MIT */ #ifndef _ERRCODE_H_ #define _ERRCODE_H_ enum ErrCode_ { /* not an error. */ E_success = 0, /* A catch-all "unknown" error. */ /* Note: we start at 10,000 to skip past the errno range. */ E_unknown = 10000, /* We ran out of buffer while reading a token. */ E_file_get_token__buff_overflow = 10010, }; typedef enum ErrCode_ ErrCode; #endif
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /* This file is Copyright (C) 2019 Jason Pepas. */ /* This file is released under the terms of the MIT License. */ /* See https://opensource.org/licenses/MIT */ #include "eval.h" #include "printer.h" #include /* Evaluates formp into resultpp. Returns 0. */ int eval_form(Form* formp, Form** resultpp) { /* for now, all forms evaluate to themselves. */ if (is_symbol(formp) || is_clong(formp) || is_cdouble(formp)) { *resultpp = formp; return 0; /* unsupported form. */ } else { assert(false); } }
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /* This file is Copyright (C) 2019 Jason Pepas. */ /* This file is released under the terms of the MIT License. */ /* See https://opensource.org/licenses/MIT */ #ifndef _EVAL_H_ #define _EVAL_H_ #include "forms.h" int eval_form(Form* formp, Form** resultpp); #endif
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /* This file is Copyright (C) 2019 Jason Pepas. */ /* This file is released under the terms of the MIT License. */ /* See https://opensource.org/licenses/MIT */ /* All of the Lisp forms. */ #include "forms.h" #include #include #include #include /* Symbol */ /* Malloc's a Symbol into sympp and copies sp into it. */ int new_symbol(Symbol** sympp, const char* sp) { Symbol* symp = malloc(sizeof(Symbol)); if (symp == NULL) { int err = errno; errno = 0; return err; } symp->type = TypeSymbol; size_t len = strlen(sp); symp->valuep = malloc(len + 1); if (symp->valuep == NULL) { free(symp); int err = errno; errno = 0; return err; } strcpy(symp->valuep, sp); *sympp = symp; return 0; } /* Is formp a Symbol? */ bool is_symbol(Form* formp) { return formp->type == TypeSymbol; } /* CLong */ /* Malloc's a CLong into clpp, initializing it with l. Returns 0 or errno. */ int new_clong(CLong** clpp, long l) { CLong* clp = malloc(sizeof(CLong)); if (clp == NULL) { int err = errno; errno = 0; return err; } clp->type = TypeCLong; clp->value = l; *clpp = clp; return 0; } /* Is formp a CLong? */ bool is_clong(Form* formp) { return formp->type == TypeCLong; } /* CDouble */ /* Malloc's a CDouble into cdpp, initializing it with d. Returns 0 or errno. */ int new_cdouble(CDouble** cdpp, double d) { CDouble* cdp = malloc(sizeof(CDouble)); if (cdp == NULL) { int err = errno; errno = 0; return err; } cdp->type = TypeCDouble; cdp->value = d; *cdpp = cdp; return 0; } /* Is formp a CDouble? */ bool is_cdouble(Form* formp) { return formp->type == TypeCDouble; }
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /* This file is Copyright (C) 2019 Jason Pepas. */ /* This file is released under the terms of the MIT License. */ /* See https://opensource.org/licenses/MIT */ /* All of the Lisp forms. */ #ifndef _FORM_H_ #define _FORM_H_ #include /* The list of Lisp form types. */ enum FormType_ { _Type_UNINITIALIZED = 0, TypeSymbol = 10, TypeCLong = 20, TypeCDouble = 30, }; typedef enum FormType_ FormType; /* A type-erased Lisp form. */ struct Form_ { FormType type; }; typedef struct Form_ Form; /* Symbol */ struct Symbol_ { FormType type; char* valuep; }; typedef struct Symbol_ Symbol; int new_symbol(Symbol** sympp, const char* sp); bool is_symbol(Form* formp); /* CLong */ struct CLong_ { FormType type; long value; }; typedef struct CLong_ CLong; int new_clong(CLong** clpp, long l); bool is_clong(Form* formp); /* CDouble */ struct CDouble_ { FormType type; double value; }; typedef struct CDouble_ CDouble; int new_cdouble(CDouble** cdpp, double d); bool is_cdouble(Form* formp); #endif
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /* This file is Copyright (C) 2019 Jason Pepas. */ /* This file is released under the terms of the MIT License. */ /* See https://opensource.org/licenses/MIT */ #include "repl.h" #include "forms.h" #include #include int main() { int err = repl(); if (err) { fprintf(stderr, "Error %d.\n", err); return err; } else { return EXIT_SUCCESS; } }
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 CC=gcc -g -std=c99 -Wall -Werror -D_POSIX_C_SOURCE=200809L lisp: main.o forms.o reader.o eval.o printer.o repl.o \$(CC) -o lisp *.o main.o: main.c \$(CC) -c main.c forms.o: forms.h forms.c \$(CC) -c forms.c reader.o: reader.h reader.c \$(CC) -c reader.c eval.o: eval.h eval.c \$(CC) -c eval.c printer.o: printer.h printer.c \$(CC) -c printer.c repl.o: repl.h repl.c \$(CC) -c repl.c clean: rm -f *.o lisp test: lisp ./run_tests.sh .PHONY: clean
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /* This file is Copyright (C) 2019 Jason Pepas. */ /* This file is released under the terms of the MIT License. */ /* See https://opensource.org/licenses/MIT */ #include "printer.h" #include /* Prints the Symbol in symp into fp. Returns 0 or errno. */ static int print_symbol(Symbol* symp, FILE* fp) { int err = fprintf(fp, "Symbol: %s", symp->valuep); if (err < 0) { return err; } else { return 0; } } /* Prints the CLong in lp into fp. Returns 0 or errno. */ static int print_clong(CLong* lp, FILE* fp) { int err = fprintf(fp, "CLong: %li", lp->value); if (err < 0) { return err; } else { return 0; } } /* Prints the CDouble in dp into fp. Returns 0 or errno. */ static int print_cdouble(CDouble* dp, FILE* fp) { int err = fprintf(fp, "CDouble: %f", dp->value); if (err < 0) { return err; } else { return 0; } } /* Prints the Form in formp into fp. Returns 0 or errno. */ int print_form(Form* formp, FILE* fp) { if (is_symbol(formp)) { Symbol* symp = (Symbol*)formp; return print_symbol(symp, fp); } else if (is_clong(formp)) { CLong* lp = (CLong*)formp; return print_clong(lp, fp); } else if (is_cdouble(formp)) { CDouble* dp = (CDouble*)formp; return print_cdouble(dp, fp); } else { assert(false); } }
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /* This file is Copyright (C) 2019 Jason Pepas. */ /* This file is released under the terms of the MIT License. */ /* See https://opensource.org/licenses/MIT */ #ifndef _PRINT_H_ #define _PRINT_H_ #include "forms.h" #include int print_form(Form* formp, FILE* fp); #endif
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /* This file is Copyright (C) 2019 Jason Pepas. */ /* This file is released under the terms of the MIT License. */ /* See https://opensource.org/licenses/MIT */ #ifndef _READ_H_ #define _READ_H_ #include "forms.h" #include /* A line-oriented FILE* buffer. */ struct FBuff_ { FILE* fp; char* buffp; size_t size; size_t len; char* nextp; }; typedef struct FBuff_ FBuff; int new_fbuff(FBuff** fbpp, FILE* fp); void free_fbuff(FBuff* fbp); bool is_fbuff_eol(FBuff* fbp); void fbuff_skip_buffered_ws(FBuff* fbp); int read_form(FBuff* fbp, Form** formpp); #endif
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /* This file is Copyright (C) 2019 Jason Pepas. */ /* This file is released under the terms of the MIT License. */ /* See https://opensource.org/licenses/MIT */ #include "repl.h" #include "reader.h" #include "printer.h" #include "eval.h" #include #include #include #include /* Is fp a tty? */ bool is_file_tty(FILE* fp) { int result = isatty(fileno(fp)); if (result == 0) { errno = 0; return false; } else { return true; } } /* Should the REPL prompt be displayed? */ bool should_display_prompt(FBuff* fbp) { if (!is_file_tty(fbp->fp)) { return false; } else { return is_fbuff_eol(fbp); } } /* Starts a read-eval-print loop. Loops until EOF or I/O error. Returns 0 or error. */ int repl() { FBuff* fbp; int err = new_fbuff(&fbp, stdin); if (err) { return err; } while (true) { fbuff_skip_buffered_ws(fbp); if (should_display_prompt(fbp)) { /* display the prompt. */ int err = fputs("> ", stdout); if (err == EOF) { free_fbuff(fbp); err = errno; errno = 0; return err; } } /* read the next Lisp form. */ Form* formp; err = read_form(fbp, &formp); if (err) { if (err == EOF) { break; } else { int err2 = fprintf(stderr, "Error %d.\n", err); if (err2 < 0) { free_fbuff(fbp); return err2; } continue; } } /* evaluate the form. */ Form* resultp; err = eval_form(formp, &resultp); if (err) { int err2 = fprintf(stderr, "Error %d.\n", err); if (err2 < 0) { free_fbuff(fbp); return err2; } continue; } /* print the result. */ err = print_form(resultp, stdout); if (err) { free_fbuff(fbp); return err; } err = fputs("\n", stdout); if (err == EOF) { free_fbuff(fbp); err = errno; errno = 0; return err; } /* loop. */ continue; } free_fbuff(fbp); return 0; }
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /* This file is Copyright (C) 2019 Jason Pepas. */ /* This file is released under the terms of the MIT License. */ /* See https://opensource.org/licenses/MIT */ #ifndef _REPL_H_ #define _REPL_H_ int repl(); #endif
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #!/bin/bash set -e -o pipefail for f in `ls test*.input` do base=\$(basename \$f .input) echo \$base cat \${base}.input | ./lisp > /tmp/\${base}.out diff -urN \${base}.expected /tmp/\${base}.out done echo "all tests passed"
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 CLong: 1 CLong: 1 CLong: 2 CLong: 3 CDouble: 1.200000 Symbol: foo Symbol: "foo" Symbol: "line Symbol: one Symbol: line Symbol: two" Symbol: true Symbol: nil
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 1 1 2 3 1.2 foo "foo" "line one line two" true nil
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 Symbol: () Symbol: ( Symbol: ) Symbol: (1) Symbol: (1 Symbol: 2) Symbol: (1 Symbol: 2) Symbol: (1(2()))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 () ( ) (1) (1 2) (1 2) (1(2()))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 Symbol: ;comment Symbol: ; Symbol: comment Symbol: 1;comment CLong: 1 Symbol: ; Symbol: comment Symbol: (1(;comment Symbol: 2;comment Symbol: ))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 ;comment ; comment 1;comment 1 ; comment (1(;comment 2;comment ))