Build Your Own Lisp: Community Project

Build Your Own Lisp is about how to create your own Lisp using C. How many lainons would be interested in reading and working through the exercises of this book together? Its about 180 pages, not too big of a commitment but enough content to keep us busy for a couple of weeks at least. Im hoping this could bring C programmers, Lispers, novices and wizards together for an interesting but accessible project. Let me know ITT if you are interested so we can begin a discussion on a start date. Here is a tentative syllabus, feel free to offer any suggestions: Week One : Chapters 1,2,3 and 4 (20 pages) Week Two : Chapters 5, 6, 7, 8 (27 pages) Week Three: Chapters 9 and 10 (32 pages) Week Four: Chapters 11 and 12 (48 pages) Week Five: Chapters 13 and 14 (41 pages) Week Six : Chapters 15 and 16 (12 pages) The book is available for free online here: http://buildyourownlisp.com/contents And I have attached the pdf as well.

Honestly this looks like the perfect book for a group project. Ive seen this book before but didnt really take a close look at it. But looking through the chapters is covers a lot of valuable stuff about data structures. I always get bored on data structures books and give up on them. Since the book is using C no one should get stuck and not be able figure anything out on their own. So lets skip the first 4 chapters which is just into material and start on chapters 5 and 6.

>>3811 Im glad you think so, Im hoping it will be an enjoyable yet challenging experience for everyone. I think you are correct about the intro material, it is unlikely that someone with no prior experience with C will be inspired by this thread to start learning. If no one protests, I think we can safely skip the 20 page C introduction and jump into chapter 5. If thats the case we could potentially tackle this book in 4-5 weeks instead of 6.

>>3811 For complicated group programming projects they often use a wiki. But I think the material is simple enough that we can just use this thread to post our thoughts and our work.

>>3812 I think the 20 page intro is valuable for newbies or those in need of a refresher. What's the harm in tacking on an extra week?

This book is grade A learning material. I did this book maybe 60% through and that taught me a metric ton about C and what goes into an interpreter. Never finished it though, I guess all the success went to my head and I just dropped the book.

I asked this on the Lisp general but it's even more relevant here. Where can we get detailed explanations of the essential optimizations applied by high-performance Lisp implementations? Assuming the Pareto principle is true, 20% of the optimizations will get us 80% of the performance improvement enjoyed by these Lisps. If we find out which optimizations are those and how to implement them, we can make a high-quality Lisp implementation.

Sounds really interesting, I agree I'm okay with skipping the first five chapters on C, but it might be nice if it were included in the sylabus anyways, so that people who needed/wanted to learn C have the opportunity.

I read this book not too long after I started programming. It was quite enjoyable for learning C. I supplemented it with K&R.

>>3813 Yes, I was hoping this thread would be a suitable hub for discussion and code examples. >>3815 I dont think there is much harm as it is only 20 pages long and while I do not want to alienate beginners, I dont want to bore more experienced programmers. There seems to be somewhat of a mixed consensus regarding skipping the intro to C, so for those in favor of skipping, would you be willing to wait a week or so from the start date to get into the juicy stuff? >>3820 Im glad to hear you got some value out of the book, this is my first time working through it so Im excited. I hope you join us and give the book another chance. >>3828 I hope we can be in a better position to answer that question after we finish the book and exercises. I would like for people with a background in Lisp to join in the hopes that they will offer a different perspective. >>3829 Yes, I do not need a C refresher personally but I do not want to alienate anyone new to C. Although, I skimmed the intro to C and only a single paragraph is dedicate to explaining pointers so I am uncertain as to how useful it will be to a beginner. >>3831 Glad to hear you enjoyed it and I hope you join in the discussion, perhaps you will get alot more out of it now that you are more experienced.

>>3833 >There seems to be somewhat of a mixed consensus regarding skipping the intro to C, so for those in favor of skipping, would you be willing to wait a week or so from the start date to get into the juicy stuff? Im the first guy who responded, I have no problem with spending a week on C. >>3828 >Where can we get detailed explanations of the essential optimizations applied by high-performance Lisp implementations? Thats a huge subject on its own. Advanced Lisp implementations abstract Lisp syntax into optimized data structures, so in a sense there is a programming language of its own hidden inside the compiler. Also you have to be somewhat of a hardware expert to find optimal ways to translate the high level code into machine instructions.

>>3835 I'm interested as I'm currently reading both Understanding and using C pointers and Language implementation patterns Where do I sign up folks ?

Well its been a day and it looks like we have a good couple of people interested in this project, which is great! Now the question of when to begin the reading. Hopefully everyone planning to be involved is at a stopping point or slow down period on their current projects so perhaps if everyone had a couple of days to wrap things up and let the thread get more views, we could start then? How does Monday, October 2nd sound? This way the more experienced C programmers will have time while the rest catch up and we can all get on the same page the week of the 9th. Is this too early, or too late, would we rather start this weekend? Please leave your input. >>3837 Right here! Welcome!

>>3839 cool, i'm down for that

>>3839 Just dropping by for the first time; this sounds cool. Right now I'm in a language course that should have practical stuff like this, but the prof decided to focus more on theory. Been trying some compiler stuff on my own, and this sounds like an interesting direction to take that. Do we start the reading next week, or should I do that on the weekend? I guess I'll see you guys on monday.

>>3841 Hey, welcome. This project sounds like a great supplement to your current course! Im sure you will have some very valuable insights. I would like to start sooner than later so people dont lose interest but this weekend may be too short notice for some people. Of course, anyone can begin reading whenever they feel like but I think there is great value (and fun) to work through it as a group. Lets see what some other lainons think and commit to a date. Im really excited!

>>3842 Monday works great, just didn't want to show up without knowing what was going on!

>>3839 That works for me

Just looking through the book, any reason they use cc instead of gcc?

>>3845 cc stands for 'C compiler' and represents the default C compiler on your system which is gcc (GNU C compiler) on Linux, so cc is just a symlink to gcc on Linux. I guess it would be clang on Mac.

I also want to mention that the compile command used in the book doesnt have optimization turned on: cc -std=c99 -Wall hello_world.c -o hello_world gcc outputs stupid slow code without optimization, this is the command I would use: gcc -std=c99 -W -Wall -O2 hello_world.c -o hello_world // or clang -std=c99 -W -Wall -O2 hello_world.c -o hello_world The -O2 flag gives level 2 optimization, it also generates extra warnings. Ive heard level 3 does some outlandish optimization that is not quite stable. I can never understand why beginners C books hardly ever turn on optimization, like what is the point of using a language like C if youre only going to generate slow code with it. Also the -W flag produces extra warnings beyond what -Wall does.

I just did chapters 5 and 6 this evening, this is a really short book, each chapter is just one page. It shouldnt take a more than a week for everyone to do this. If anyone has questions on chapters 5 and 6 let me know.

>>3847 Optimizations make it harder to reason about and step through code in a debugger. Turning off optimizations will result in machine code which closely represents the high level code you wrote and I think is much better for learning even if it is slower.

https://github.com/kanaka/mal This might be of interest.

I have some C experience, think I'm going to write my own parser instead of using the existing library. Anyone have some good reading on parsing? Shouldn't be too hard since lisps are relatively easy to parse compared to most languages.

>>3860 It's not super efficient, but you could just write a statemachine that finds matching brackets in a string and then recurses. That's probably the simplest way to build a sysntax tree. A bit more advanced would be to start with a tokenizer that pre-processes the string.

>>3860 >Shouldn't be too hard since lisps are relatively easy to parse compared to most languages. The parser library he made for the book just doesnt parse Lisp, it will parse syntax for any language you invent. I was thinking of translating his parser library into another programming language as a good way to figure out how to make parsers.

>>3859 that "Make a Lisp" guide looks like it could be a good follow-on as it lets you make a Lisp in any programming language

>>3861 >>3860 that's what a lexical analyzer does, writing a state machine in C is complex and tedious enough that there's programs to automate this with regex, namely `lex`, if you also want to check for syntactic errors you would use `bison`, the thing is that a formal language composed of matching nested brackets is not a regular language, therefore you can not build a state machine that identifies this language (so `lex` will not suffice), the nested matching parens language is what is called a "context free grammar", therefore you would need to use `bison`. SO answer to give you a better explanation: https://stackoverflow.com/questions/133601/can-regular-expressions-be-used-to-match-nested-patterns if you would like to take a quick look at how to make a lexical analyzer with lex and how it works, there's this project i finished not long ago, just look at the readme.md for the relevant info. (or just look at the code used to build the state machine with flex, it's the `scanner.l` file) https://github.com/Sleepful/C-scanner

I'm really interested in this, and considering I'm not often here I want to ask you did you do any other projects in this vain? I really like the idea of a group project and mutual help and solution sharing.

>>3860 >I'm too l33t to follow the book I'm going to write my own parser >....guys how do I write my own parser? I don't think this is a good direction to take the thread to be honest.

>>3915 I've done parsing by hand once or twice before, just want to read more about the subject.

I haven't really posted on lainchan before, but this place introduced me to Lisp and this project sounds really interesting.

>>3860 This book is about C compilers but there are two big chapters that cover the nitty gritty of parsing which may be of some help. If you do write your own parser, please be sure to share, I would be interested to see it as I have never written one myself. >>3930 Hello and welcome, we are "officially" starting the book this Monday but feel free to begin now. The chapters are very short, I just read chapters 1-4 and did the exercises in ~30 minutes.

>>3911 You should join us, its a small book but its going to be a blast! I personally have never taken the initiative to start a group study project but have been apart of a group reading of K&R on irc which was sooo impactful and fun. I tried to join various group projects here and on 8chan but they have a tendency to fizzle out because people lose interest or the group lacks any general structure or direction due to irresponsible OPs. Also I always participated in group readings of classical literature at 4chan's /lit/ and have had nothing but good experiences and want to carry that over to programming. If BYOL goes well I would love to start or participate in an SICP or data structures and algorithms study group. I mean I was planning on studying algorithms over the winter anyway, why not invite others to do the same?

Hey! I'm really interested in this project, Mr. Endian! I'm currently taking a Computer Systems class in C, so I'd love to sort of use what i've learned about C to make a Lisp! Just out of curiosity, will discussion regarding this book be on the irc or the \lambda\ board (or both).

The only thing I don't like about the book is that you're required to use that parser combinators library to build the project. Libraries and other forms of external dependencies are tricky business. They will significantly increase the complexity of the build system. Since this is a tutorial that targets even people unfamiliar with C, it doesn't make sense to worry about such things. It would be better to make the completely self-contained so that a really simple, hand-written makefile can build it. The makefile gets updated with each chapter. So I'd be much happier if the book featured a really simple recursive descent parser right in the source code. Symbolic expressions are easy enough to parse that you can simply explain how to do it instead of using a library that takes declarative grammar as input.

>>3860 >>3931 I've found this really simple Lisp implementation on GitHub: https://github.com/rui314/minilisp/blob/master/minilisp.c At one thousand lines of well-commented code, it's a pretty good illustration of what a finished Lisp interpreter project looks like. It uses a recursive descent parser like I suggested in >>3936. The parser represents about 15 to 20% of the source code. It is quite easy to understand by starting from the read_expr function and proceeding recursively until you've understood every function. Here's the parser section of the code: //====================================================================== // Parser // // This is a hand-written recursive-descendent parser. //====================================================================== #define SYMBOL_MAX_LEN 200 const char symbol_chars[] = "~!@#$%^&*-_=+:/?<>"; static Obj *read_expr(void *root); static int peek(void) { int c = getchar(); ungetc(c, stdin); return c; } // Destructively reverses the given list. static Obj *reverse(Obj *p) { Obj *ret = Nil; while (p != Nil) { Obj *head = p; p = p->cdr; head->cdr = ret; ret = head; } return ret; } // Skips the input until newline is found. Newline is one of \r, \r\n or \n. static void skip_line(void) { for (;;) { int c = getchar(); if (c == EOF || c == '\n') return; if (c == '\r') { if (peek() == '\n') getchar(); return; } } } // Reads a list. Note that '(' has already been read. static Obj *read_list(void *root) { DEFINE3(obj, head, last); *head = Nil; for (;;) { *obj = read_expr(root); if (!*obj) error("Unclosed parenthesis"); if (*obj == Cparen) return reverse(*head); if (*obj == Dot) { *last = read_expr(root); if (read_expr(root) != Cparen) error("Closed parenthesis expected after dot"); Obj *ret = reverse(*head); (*head)->cdr = *last; return ret; } *head = cons(root, obj, head); } } // May create a new symbol. If there's a symbol with the same name, it will not create a new symbol // but return the existing one. static Obj *intern(void *root, char *name) { for (Obj *p = Symbols; p != Nil; p = p->cdr) if (strcmp(name, p->car->name) == 0) return p->car; DEFINE1(sym); *sym = make_symbol(root, name); Symbols = cons(root, sym, &Symbols); return *sym; } // Reader marcro ' (single quote). It reads an expression and returns (quote <expr>). static Obj *read_quote(void *root) { DEFINE2(sym, tmp); *sym = intern(root, "quote"); *tmp = read_expr(root); *tmp = cons(root, tmp, &Nil); *tmp = cons(root, sym, tmp); return *tmp; } static int read_number(int val) { while (isdigit(peek())) val = val * 10 + (getchar() - '0'); return val; } static Obj *read_symbol(void *root, char c) { char buf[SYMBOL_MAX_LEN + 1]; buf[0] = c; int len = 1; while (isalnum(peek()) || strchr(symbol_chars, peek())) { if (SYMBOL_MAX_LEN <= len) error("Symbol name too long"); buf[len++] = getchar(); } buf[len] = '\0'; return intern(root, buf); } static Obj *read_expr(void *root) { for (;;) { int c = getchar(); if (c == ' ' || c == '\n' || c == '\r' || c == '\t') continue; if (c == EOF) return NULL; if (c == ';') { skip_line(); continue; } if (c == '(') return read_list(root); if (c == ')') return Cparen; if (c == '.') return Dot; if (c == '\'') return read_quote(root); if (isdigit(c)) return make_int(root, read_number(c - '0')); if (c == '-' && isdigit(peek())) return make_int(root, -read_number(0)); if (isalpha(c) || strchr(symbol_chars, c)) return read_symbol(root, c); error("Don't know how to handle %c", c); } }

>>3936 >Libraries and other forms of external dependencies are tricky business. They will significantly increase the complexity of the build system. Since this is a tutorial that targets even people unfamiliar with C, it doesn't make sense to worry about such things. It would be better to make the completely self-contained so that a really simple, hand-written makefile can build it. The makefile gets updated with each chapter. libraries are not difficult at all, in fact I learned how easy it is to include a library through this book. There are only two files you need: mpc.c and mpc.h you just put these two files in the same folder as your code file. And then you just put #include "mpc.h" in your code file and then put mpc.c in the console compile command so it will get linked like this: clang -std=c99 -W -Wall -O2 x.c mpc.c -ledit -lm -o parsing (I am calling my main file x.c because I give it a different name each chapter) >So I'd be much happier if the book featured a really simple recursive descent parser right in the source code. Symbolic expressions are easy enough to parse that you can simply explain how to do it instead of using a library that takes declarative grammar as input. Im currently on chapter 9 of this book, in the code that I have done so far there is this function: lval eval(mpc_ast_t* t) { if (strstr(t->tag, "number")) { errno = 0; long x = strtol(t->contents, NULL, 10); // function returns on error return errno != ERANGE ? lval_num(x) : lval_err(LERR_BAD_NUM); } char* op = t->children[1]->contents; // eval is being called recursively for first child node lval x = eval(t->children[2]); int i = 3; while (strstr(t->children[i]->tag, "expr")) { // eval called recursively on all the rest of the child nodes x = eval_op(x, op, eval(t->children[i])); i++; } return x; } as you can see in this function, eval (the name of the overall function) is being called recursively on children[] which is an array that holds all the child nodes of *t (the mpc_ast_t datatype is the entire abstract syntax tree, or in other words, the entire program you pass into the parser) that is passed into this function

>>3944 >There are only two files you need: mpc.c and mpc.h you just put these two files in the same folder as your code file. Huh. I had forgotten the library was that small. If you copy the library's files into your source tree, it's as if it was part of your project all along. It will get compiled along with the rest of the project. All the issues pretty much go away. >as you can see in this function, eval (the name of the overall function) is being called recursively on children[] That's the evaluator, not the parser. The recursive descent parser transforms streams of characters into Lisp objects. eval transforms Lisp objects into other Lisp objects. They are indeed quite similar, but not the same

>>3932 I'm really interested now - I will keep following this thread, and join. Btw. it is so good to meet helpful and nice people, after 10 years on 4chan this almost seem like a troll site.

Alright! Week One has begun and so has the realization that my initial time table is likely to be very inaccurate as the chapters are really short, we absolutely can finish this in a week or two. We will see what happens. Chapter 2 goes over basic installation. You really only need a C compiler, access to CLI, the author's mpc parser, gdb debugger and a text editor. As has been mentioned ITT, we are using the authors parser lib (I know, I know) which you can find here https://github.com/orangeduck/mpc , just drop mpc.c and mpc.h in the directory with your other source files and be sure to include it in your headers. Chapter 3 goes over some basic C concepts and in chapter 4 we begin with our first program, a minimal REPL using some functions from libedit, and some very valuable information on the C preprocessor. Libedit's readline function is pretty straightforward but the add_history function is a little bit more intricate, here is the source code: https://ghostbin.com/paste/77odh Here is my code for the REPL with some superficial modifications from the exercises at the end of the chapter: #include <stdio.h> #include <stdlib.h> #include <editline/readline.h> #include <editline/history.h> int main(int argc, char **argv) { puts("mai lispfu v0.1"); puts("Press Ctrl-c to exit\n"); for(;;) { char *input = readline("REPL> "); add_history(input); printf("%.*s\n", 10, input); free(input); } } Its probably too early to ask, but I would like to get some feedback on how far everyone has progressed and what they think of it so far. If anyone needs any further help with installation and environment setup or any questions regarding the basics of C, by all means ask away in this thread and I will try my best to help in any way I can.

>>4008 I've got the basic REPL running. I installed development packages on a Linux VPS and have been using it as my environment.

>>4008 I'm in the middle of chapter 9. Even though this book is just copy & pasting code, the author doesn't tell you where to paste the code so it can be tricky to get the program to compile. Also the author doesn't go into much detail explaining how the code works. I want to suggest Atom as a code editor. If you install the atom-beutify plugin and then click the settings button, expand the general section and click beautify on save. Then scroll down to the C section and check beautify on save. You have to have uncrustify installed on your system for this to work

>>4008 I was planning to get started this evening. We could probably cut the time roughly in half or so. I'm not sure how complicated the later chapters will become.

>>4012 I suppose we'll fill in the blanks in our understanding as we go along.

>>4012 you could also use [literally any editor] with [literally any c formatter]

>>4012 > the author doesn't tell you where to paste the code so it can be tricky to get the program to compile Im on chapter 7 and thus far, he references the entire program at the end of every chapter. >Also the author doesn't go into much detail explaining how the code works. I noticed this too...in particular he does not explain how mpc works, Ive been having to read the source code to figure out whats going on in some of the mpc function calls. Speaking of which, while attempting to do the end of chapter 6 exercises, I ran into way more difficulty than I should have setting up the problem due to my unfamiliarity with mpc. I can only get one parser to work at a time and was unsuccessful at combining exersices one and two into the mpca_lang function so I had to create two which caused additional problems. I can see that mpc is very powerful but its frustrating. #include <stdio.h> #include "mpc.h" #include <editline/readline.h> #include <editline/history.h> int main(int argc, char **argv) { mpc_parser_t* exer_one = mpc_new("exer_one"); //mpc_parser_t* exer_two = mpc_new("exer_two"); mpc_parser_t* Lispy = mpc_new("lispy"); mpca_lang(MPCA_LANG_DEFAULT,"exer_one : /[a,b]+/; lispy :/^/<exer_one>/$/;", exer_one, Lispy); //mpca_lang(MPCA_LANG_DEFAULT, "exer_two : /[ab]+a?/; lispy :/^/exer_two>/$/;", exer_two, Lispy); for(;;) { char *input = readline("REPL> "); add_history(input); mpc_result_t r; if(mpc_parse("<stdin>", input, Lispy, &r)){ mpc_ast_print(r.output); mpc_ast_delete(r.output); }else { mpc_err_print(r.error); mpc_err_delete(r.error); } } mpc_cleanup(1, exer_one); //mpc_cleanup(1, exer_two); }

>>4008 Got to chapter 7. Don't know how much time I'll have this week, so you guys should progress however you want.

>>4059 after you clean up exer_one you should be able to repeat the code for exer_two

>>4008 Honestly, I have a little bit of experience with C, but the majority of my experience is/was on GNU/Linux, as such it was pretty enlightening to learn a little bit more about the C preprocessor, I'm definitely going to continue working through the course! I also found his description of the C language at the beginning of the book to be very beautiful. As far as good/bad practice goes, is using 'puts' still good practice or is printf generally considered to be better?

>>4065 puts writes a string to the program's standard output. printf takes a format string and a variable number of parameters; it makes a new string with the parameters spliced into it and writes that to the program's standard output. If you call printf with only one argument, your compiler probably optimizes it to puts.

I started reading the book yesterday and so far it has been pretty good, especially the grammar stuff in chapter 5. I realize the c code given in the book is not intended to be production level code, but there's a bug in the fake readline function from chapter 4. static char buffer[2048]; /* Fake readline function */ char* readline(char* prompt) { fputs(prompt, stdout); fgets(buffer, 2048, stdin); char* cpy = malloc(strlen(buffer)+1); strcpy(cpy, buffer); cpy[strlen(cpy)-1] = '\0'; return cpy; } If the user inputs 2047 or more characters and presses return the buffer will contain 2047 chars and a \0 at the end. cpy will then also have a length of 2048 bytes but the second to last char will be replaced by \0. This is normally used to get rid of the trailing \n but in this case we're losing a character. To avoid that there should be something like if (strlen(buffer) != 2047) cpy[strlen(cpy)-1] = '\0'; Now, I don't know how many of you are using windows and even then it's only a problem if you input exactly 2047 characters because more than that won't fit in the buffer anyways. I'm more interested in how this is handled in the real readline function. Does it also have a maximum size for how big a line can be (except memory limitations of course)? Does it malloc a fixed size and uses realloc if there are more characters? What do you think?

>>4076 >If the user inputs 2047 or more characters and presses return the buffer will contain 2047 chars and a \0 at the end. as I recall, the book mentions that fgets() does not put a \0 at the end so it has to be put in manually

>>4077 The man page of fgets says a \0 is put in the last place. >fgets() reads in at most one less than size characters from stream and >stores them into the buffer pointed to by s. Reading stops after an >EOF or a newline. If a newline is read, it is stored into the buffer. >A terminating null byte ('\0') is stored after the last character in >the buffer. Anyway, how do you get indentation in a \[code\] block? Do you have to use spaces?

>>4081 >Anyway, how do you get indentation in a \[code\] block? >Do you have to use spaces? just paste the code, the indentation will be maintained, both spaces or tabs should work

>>3810 This book teaches how to build a language but doesn't even attempt to describe the piss-easy recursive descent parser for a basic Lisp and instead chooses to push the author's parser generator library. Shameful.

>>4067 Only if your one argument to printf ends in \n, puts inserts that automatically

>>4085 To be fair, you can do it in a way that will let you easily replace the parser with your own. That's what I'm doing, just using the parser to gather everything into lists. The progression seems to work well for absolute beginners, it would seem a lot more daunting at the beginning rather than the end.

>>4076 >I'm more interested in how this is handled in the real readline function. Does it also have a maximum size for how big a line can be (except memory limitations of course)? >Does it malloc a fixed size and uses realloc if there are more characters? What do you think? The GNU Readline documentation specifies that the return value of the readline() function is a malloc-ed string that need be freed when no longer in use. I believe it's also the case that it will simply reallocate as the input grows.

>>4085 from the side-note box in the middle of chapter 9: >Other Lisps have a slightly different definition of what an S-Expression is. In most other Lisps S-Expressions are defined inductively as either an atom such as a symbol of number, or two other S-Expressions joined, or cons, together. >This naturally leads to an implementation using linked lists, a different data structure to the one we are using. I choose to represent S-Expressions as a variable sized array in this book for the purposes of simplicity, but it is important to be aware that the official definition, and typical implementation are both subtly different.

Has anyone done the exercises for chapter 7? I dont know jack about trees and Im stumped on the first exercise...I guess I cant into recursion, feels bad man. long count_leaves(mpc_ast_t *t) { static long leaves = 1; if(t->tag == NULL && t->contents == NULL) return leaves; else { for(int i = 0; i < t->children_num; i++) leaves += count_leaves(t->children[i]); } return leaves; }

>>4099 I think the tag and contents won't be null for leaves, check the output of mpc_ast_print(r.output); the tags look like: "expr|number|regex" and the content looks like: '1' Welcome to nano-lisp v0.0 Press Ctrl-c to exit =8 ( + 1 2 3 ( + 1 2 3 ) ) > char:1:1 '(' symbol|operator|char:1:3 '+' expr|number|regex:1:5 '1' expr|number|regex:1:7 '2' expr|number|regex:1:9 '3' expr|> char:1:11 '(' symbol|operator|char:1:13 '+' expr|number|regex:1:15 '1' expr|number|regex:1:17 '2' expr|number|regex:1:19 '3' char:1:21 ')' char:1:23 ')' LIST: ( + 1 2 3 ( + 1 2 3 ) ) RESULT: 12 I'm not sure about the specifics of mpc, but when a pair of brackets has another pair of brackets nested inside it, this is an "expression inside an expression." In other words, the inner expression is the child of the outer expression. With the expression ( + 1 2 3 ), we have an expression with four child nodes, six if you add the two brackets, which mpc does. The children have no children of their own. With ( + 1 ( + 2 3 ) ) though, we'll have one expression with 5 children, with one having five children of it's own. Don't know how much sense that will make, hope it's helpful. Anyway, A leaf should have children_num == 0, right? That should work for your base case. I wouldn't use static here either... what were you using it for? (It will make the value of the variable persist between functional calls, as if it were a global variable. Be careful with that.)

>>4101 >LIST: ( + 1 2 3 ( + 1 2 3 ) ) >RESULT: 12 you have successfully counted all the tokens of your input, now you just have to filter out everything that is not a number to get number of leaves

>>4103 eheh, no that's 6+6 actually, the value of the expression.

>>4099 you could take the easy way and just modify the number_of_nodes() function in ch7 as it already does the recursion for you, you just have to put a counter variable on the end clause of the recursion

Thanks for this thread. Working through something as a group is always fun and a great way to sure up holes in one's knowledge. I've found it very fulfilling as a measure of my progress in programming since I had read the first few chapters some time ago and found the interpreter difficult to understand, this time even the bonus questions have been a breeze. I'm sure they wont stay that way since I'm only up to chapter 8, but I look forward to the challenge.

Has anyone done the exercises for chapter 8? One of the questions asks `Can you change how lval is defined to use a union instead of a struct?' It seems perfectly clear to me that lval could be defined as follows to save a few bytes: typedef struct { int type; union { long num; int err; } } lval; However, this is not using a union instead of a struct, as the question asks. I'm not sure how to tackle this since type must remain distinct from the data. I could remove type-checking, but I don't think that's in the spirit of the question.

>>4228 Wait what? How does one identify the value's type without a type tag? Pointer hacks?

>>4229 >>4228 I know one can encode integers in pointers by redefining the meaning of some bit, probably a bit that would screw up the alignment of the pointer if set. So if it's set it's an incorrectly aligned pointer and the implementation takes the other bits and interprets them as an integer, and if it's not set it's a valid pointer and we dereference it to get the tagged union.

Hey, I'm trying to racketize the language a bit (make it more like racket. So I want to return a number if it's by itself, and only allow operators inside the paren. Examples: 5 -> 5 (+ 1 2) -> 3 + 1 2 -> ERROR I have an idea on how to do that, but I'm a bit lost when it comes to the eval function. Can someone give me a hint or two on how would I go about this?

>>4228 I dont know much about unions so I dont know if the switch statement inside the lval_print() function can detect which variable type in the union is being used, so you may have to embed the union in the struct as you already have. Also Ive heard that unions are unstable and not used very much in C or C++. >>4231 Have you done chapter 8 yet which covers errors? I dont want to explain stuff that you havent covered in the book yet.

>>4237 >I dont know if the switch statement inside the lval_print() function can detect which variable type in the union is being used, so you may have to embed the union in the struct as you already have. This was my line of thinking too, I don't see any way to differentiate between expression values using a union alone. As far as I understand it all union variables are `in use' simultaneously, as they occupy the same memory address. Unions are probably considered unstable because reading a variable type other than the one that was set most recently is undefined behaviour. That said, pretty much every compiler out there will give you the data interpreted as if it were the type you asked for.

>>4237 just starting working through it. A bit busy with CS classes rn.

I'm currently in chapter 6 doing the bonus exercises and I cannot figure out why my grammar rule for decimal numbers does not work. number: /-?[0-9]+/ | /-?[0-9]+/ '.' /[0-9]+/ \ | '1' '.' '1' ; \ I think it should be pretty straightforward: match a normal number then a dot and then another string of digits. The 1.1 was just a test to see if it generally works, but that also gives me: lispy> + 1.1 <stdin>:1:4: error: expected one of '0123456789', '-', one or more of one of '0123456789', '1', '(' or end of input at '.' Hm, now that I write this I thought of the possibility that mpc might read the 1, think it's case 1 of the number rule and then gets thrown off by the dot. Does mpc not do any backtracking to check if another case of the same rule applies? I'm going to try reordering the cases.

>>4391 okay, putting the decimal rule before the normal one worked. But you can do it even simpler by making the .x part optional in the first place, like: number: /-?[0-9]+/ /[.][0-9]+/? ;

How's everyone going with this? I'm not sure whether I should take silence to indicate that progress has stalled or everyone is hard at work. Personally I've just finished chapter 10, which is on schedule, I believe. As for the chapter itself, I'm sure I must be missing something obvious when it comes to the implementation of cons. The solution I ended up on seems overly complex compared to the other exercises which were all easily solvable with previously implicated functions and only took an understanding the AST structure. /* Return y with x consed onto the front of its cell list assume y is a qexp */ lval* lval_cons(lval *x, lval *y) { y->count++; y->cell = realloc(y->cell, sizeof(lval*) * y->count); memmove(&y->cell[1], &y->cell[0], sizeof(lval*) * (y->count - 1)); y->cell[0] = x; return y; }

>>4394 >I'm not sure whether I should take silence to indicate that progress has stalled or everyone is hard at work. Im dropping out. Ive done most of the helping in this thread so far so quite honestly my absence will be missed. The C code in this book just makes me want to vomit. I am sick of C in general with all the stupid memory allocations and struct pointer references which can be seen in your code snippet. So unless someone wants to convert the code in this book to Go, Rust or Julia, Im out.

>>4405 Would you mind elaborating on what you find particularly disgusting about the C code? I've heard this complaint about the book before, but I don't have enough experience with the nitty-gritty of C to pass judgement.

>>4406 using realloc on these tiny variables just seems so ancient, like if I was using a computer with 4k of memory I could see that kind of programming would be needed. and the overuse of pointers for things that dont need to be pointers in modern languages, C is starting to look like Fortran and Cobol to me

>>4409 >>4405 This book isn't the ultimate word in language implementation. You can do things very differently if you want to. I posted a recursive descent parser earlier in the thread that would have eliminated the mpc dependency. That doesn't help the people who are following the book though. Your two complaints are a matter of aesthetic. There's nothing wrong with using realloc to reallocate memory or pointers to refer to structures. I haven't actually read the later chapters in the book; perhaps they haven't implemented a garbage collector yet? Maybe that's why the code looks "ancient" to you. Once the language has a garbage collector, memory allocation operations become much simpler and centralized; you may simply ask the system for new cells. The memory allocations and reallocations and dead object reuse are all hidden. Here's a simple blog post that explains how it works: http://journal.stuffwithstuff.com/2013/12/08/babys-first-garbage-collector/ >>4394 I'm just lurking. I come here everyday but don't post much.

>>4405 >>4409 >I am sick of C in general with all the stupid memory allocations and struct pointer references >>using realloc on these tiny variables just seems so ancient, like if I was using a computer with 4k of memory I could see that kind of programming would be needed. and the overuse of pointers for things that dont need to be pointers in modern languages, C is a very literal reflection of how computers actually work. Your so called "modern languages" are not magic. At the lowest levels they also realloc tiny blocks of memory and hold pointers to everything as well. The only difference is that it is all hidden from you the user.

>>4409 You shouldn't be allowed to program computers.(Elaborate on your opinions; avoid spilling soykaf.)

>>4413 >C is a very literal reflection of how computers actually work. This is a total myth, C is not "closer to hardware". Back in the 70s and 80s there was very little in the way of operating systems and programs controlled hardware directly Your so called "modern languages" are not magic. At the lowest levels they also realloc tiny blocks of memory and hold pointers to everything as well. The only difference is that it is all hidden from you the user. Languages like Java and C# go nuts allocating everything on the heap. "modern languages" like Go, Rust, Swift very rarely allocate data on the heap which have to be held by reference pointers. >>4414 you know the whole "Im a grey bearded hacker that does everything in C and asm" meme is starting to get really old, its not funny anymore, you have never, ever used C or asm to do systems programming, you are a little boy who is larping like every other "C guru" on 4chan

>>4416 >Back in the 70s and 80s there was very little in the way of operating systems and programs controlled hardware directly The operating system interface forms part of the computer's architecture in any modern incarnation of the concept. As far as your program is concerned, the OS is part of the machine, an extra set of instructions. Programming against the OS is systems programming. >Go, Rust, Swift very rarely allocate data on the heap which have to be held by reference pointers All of those languages support all kinds of memory allocation. It's a lot more complicated than you're letting on. For example, Go's stacks, and therefore every stack-allocated variable, are allocated on the "heap"; every time a stack overflow occurs, it is reallocated to a larger region and the old contents copied over. By definition, all unregisterized data is accessed through the processor's many addressing modes. They are pointed to. >you are a little boy who is larping like every other "C guru" on 4chan It's time to stop posting.

>>4416 >This is a total myth, C is not "closer to hardware". I can see why someone might think that if they have only ever written C code under a single operating system on a single processor architecture. But a person like that really shouldn't be spreading their worthless opinions on the matter. >Back in the 70s and 80s there was very little in the way of operating systems and programs controlled hardware directly Does your 2017 operating system control hardware directly? What language is it written in? I'm really don't understand what you are trying to say here. >Languages like Java and C# go nuts allocating everything on the heap. "modern languages" like Go, Rust, Swift very rarely allocate data on the heap which have to be held by reference pointers. Whether data is is stored on the heap or not depends on how you use the data and how long you keep it alive. Some languages may be better at spotting opportunities to optimize your code but heap usage is fundamentally independent of your language choice. Like I said before, what is happening here is that you are just completely clueless about the layers of crap underneath your high level "modern language" and conclude that C is just being unnecessarily retarded. It's not. C is the naked truth that other languages are lying to you about. >you know the whole "Im a grey bearded hacker that does everything in C and asm" meme is starting to get really old, its not funny anymore, you have never, ever used C or asm to do systems programming, you are a little boy who is larping like every other "C guru" on 4chan I'm pretty sure I'm making more money writing C than you mate.

>>4427 >>Back in the 70s and 80s there was very little in the way of operating systems and programs controlled hardware directly >Does your 2017 operating system control hardware directly? What language is it written in? I'm really don't understand what you are trying to say here. OK, it was late at night when I posted that and I didnt explain that very well. Try again: Back in the 70s and 80s you had very simple operating systems, in fact they really werent even operating systems but just program loaders because the OS could not multitask it gave the program total control of the computer so that the program became the OS and controlled the hardware directly. So you needed a 'systems language' which basically means very weak typing to allow you to form bits to map directly to memory. Also computers back then had 4k of memory which made garbage collection impossible, which is why a lot of great languages like CPL, Ada, Modula were designed in the 60s and 70s and never able to be used because there was no hardware that had enough memory to support it. All these factors are gone now. Programs dont touch hardware at all but go through an OS API for everything. Using manual memory management is simply stupid in this day and age, there is no way a human programmer is going to match compiler optimization for controlling memory. In C++ you end up using various forms of reference counting which is in itself a form of garbage collection that has the same overhead as automatic reference counting garbage collection. As an example, original implementations of Javascript used reference counting gc until they were modernized with mark & sweep gc. Everything about C is just needless cruft and busywork when running in an OS userspace. Unfortunately I cant prove anything I have said here because so far no one has made any large scale application in any of these modern languages that can be compared to C/C++. Benchmarks are never an accurate measure of programming language speed although benchmarks do support what I say.

>>4434 >Using manual memory management is simply stupid in this day and age, there is no way a human programmer is going to match compiler optimization for controlling memory. In case you didn't notice, we are writing a programming language. Automatic memory management doesn't materialize out of thin air, it gets written. Garbage collection necessarily involves the use of memory management system calls provided by the operating system. Seriously, stop derailing the thread. If you don't wanna help, just quietly leave. We're all familiar with the viewpoint you're expressing; nobody cares.

>>4436 ok, sry, I wont post

>>4394 Midterm week, but I'll try to get back at it. I'm not too far behind from you, think I stopped at ch 8.

>>4434 >Programs dont touch hardware at all but go through an OS API for everything The software world is much bigger than userspace applications running under an x86 desktop OS. >Everything about C is just needless cruft and busywork when running in an OS userspace. All your high level interpreters and compilers and system libraries are still written in C. C is the foundation on which everything is build. All this "cruft and busywork" still exists but in high level languages it is just work that someone else has already done for you and therefor you incorrectly assume is needless. This is exactly the reason why someone like you should learn C. >Also computers back then had 4k of memory which made garbage collection impossible, which is why a lot of great languages like CPL, Ada, Modula were designed in the 60s and 70s Lisp had a garbage collector in the 60s. The Ada specification was also written with the intention of having a garbage collector but no one bothered implementing one because Ada is primarily used for real time safety critical systems where garbage collectors are dangerous and inconvenient. > reference counting which is in itself a form of garbage collection Reference counting and garbage collection are forms of automatic memory management but they are very distinct concepts. When you blur things together like this it is obvious you have limited knowledge of what you are talking about.

>>4434 >Back in the 70s and 80s you had very simple operating systems, in fact they really werent even operating systems but just program loaders because the OS could not multitask it gave the program total control of the computer so that the program became the OS and controlled the hardware directly. So you needed a 'systems language' which basically means very weak typing to allow you to form bits to map directly to memory But that isnt fuarrrking true, at all. Christ, UNIX, what you're probably typing from, is from the 70s, and wasnt noted for bringing about a revolution of OSes presenting an interface. It drew its habits from systems in the SIXTIES which were clearly not operating in some kind of bare metal NOOS('no-os') program loader style. and it was written in C, rather characteristically.

>>4449 >>4464 I promised I would not post off topic discussions on this thread any more so I have responded to your posts on the beginners thread. >>4465 I dont think its worth starting a new thread just to wrap up this discussion and I think this topic could benefit beginners. I consider myself to be sort of a beginner as I am not professional yet.

Got tired of declaring new rules and made a little X-macro thing to automate that. Might be useful for someone. Pay attention to MAX_GRAMMAR_SIZE if you add lots of rules and stuff. // grammar.h #define MAX_GRAMMAR_SIZE 4096 #define CONCAT_GRAMMAR(a,b,...) \ strncat(buffer, #a ,MAX_GRAMMAR_SIZE); \ strncat(buffer, " : " , MAX_GRAMMAR_SIZE); \ strncat(buffer, #b , MAX_GRAMMAR_SIZE); \ strncat(buffer, " ; " , MAX_GRAMMAR_SIZE); #define LIST_GRAMMAR(a,b,...) a, #define DECL_GRAMMAR(a,b,...) mpc_parser_t* a = mpc_new(#a); #define COUNT_GRAMMAR(a,b,...) +1 #define COMPILE_GRAMMAR(G) \ G(DECL_GRAMMAR) \ char buffer[MAX_GRAMMAR_SIZE]; \ G(CONCAT_GRAMMAR) \ mpca_lang(MPCA_LANG_DEFAULT, buffer, G(LIST_GRAMMAR) 0); #define CLEANUP_GRAMMAR(G) \ mpc_cleanup( 0 G(COUNT_GRAMMAR), G(LIST_GRAMMAR) 0 ); // main.c #define ALL_RULES(X) \ X( number, /-?[0-9]+/ )\ X( operator, '+' | '-' | '*' | '/' | '#' | '_')\ X( symbol, <number> | <operator> | /[a-zA-Z][a-zA-Z0-9]*/ )\ X( expr , '(' <symbol> <expr>+ ')' | <number>)\ X( nano, /^/ <symbol> <expr>+ /$/ | '(' <symbol> <expr>+ ')' ) COMPILE_GRAMMAR(ALL_RULES) for(;;) { char *input = readline("=8 "); add_history(input); mpc_result_t r; if(mpc_parse("<stdin>", input, nano, &r)) { mpc_ast_print(r.output); NODE * list = buildList(r.output); printf("\nLIST: "); printList(list); printf("\n"); printf("\nRESULT: %d\n",eval(list)); freeList(list); mpc_ast_delete(r.output); } else { mpc_err_print(r.error); mpc_err_delete(r.error); } printf("%s\n", input); free(input); } CLEANUP_GRAMMAR(ALL_RULES)

>>4518 indentation fuarrrked up sorry. Also I should mention the main.c code is actually in main().

I finished this book on my day off today, including the exercises. I'd like to at least implement garbage collection, since there's a thread here containing a few guides for that. Going in I knew at least the syntax of C and was already very familiar with Lisps. To begin with the latter; I don't think the book really communicated what makes Lisp special. I realise now that that was never really the intent, but while reading I was sometimes left wondering if the author himself really understood what he was evangelising. Where I think the book does deserve merit is as a interactive demonstration of writing a large programme in C, including all the nitty-gritty of memory management and pointer manipulation. When and where those techniques should be used is very difficult to communicate through a standard explanation such as you would see on Stack Overflow and usually only comes with experience. As such, I do feel like I have a better understanding of how programmes are written in C now.

>>4645 >I don't think the book really communicated what makes Lisp special. What would you say that is? To me it's the fact Lisp allows you to customize eval. FEXPRs essentially let you turn a regular Lisp function into an eval clause.

http://www.iso-9899.info/wiki/Main_Page#Stuff_that_should_be_avoided If you want to learn C you should not use this to be fair.

>>4645 >I don't think the book really communicated what makes Lisp special. From what I read in Lisp books, Lisp is meant to be implemented in Lisp with only the basic primitive functions implemented in some compile-to-binary language. If fact many books mention that the original Lisp implmentation only used 7 primitive functions. Here is some more info I found doing a quick google: https://stackoverflow.com/questions/3482389/how-many-primitives-does-it-take-to-build-a-lisp-machine-ten-seven-or-five Im going to upload a book which in my opinion is the simplest and best book for learning how a compiler works