Semantics with applications

What Hacker News says

1. tom_melliorJul 2020
   Another good one is:

   * Concrete Semantics by Nipkow and Klein http://concrete-semantics.org/, which is also an introduction to the Isabelle/HOL proof assistant and formalizes all of the PL content in Isabelle

   There's also:

   * Semantics with Applications: An Appetizer by Nielson and Nielson https://www.springer.com/gp/book/9781846286919, apparently a newer edition of an older book I liked and which used to be available as a free PDF, but the link from my browser history is now broken

   Show morethread
2. sriram_malharOct 2019
   Oh yes. Grad school is all reading. I recall reading these books in their entirety.

   Security Engineering. Ross Anderson

   The Formal Semantics of Programming Languages. Glynn Wynskell.

   Communicating Sequential Processes. Tony Hoare. This book is surprising in its compactness and lucidity.

   Pi Calculus. Robin Milner.

   Semantics With Applications. Hanne Riis Nielson

   On Concurrent Programming. Fred Schneider.

   Specifying Systems with TLA+. Leslie Lamport.

   Distributed Algorithms. Nancy Lynch.

   Reliable Distributed Computing. Ken Birman and Robert Van Renesse.

   I'm sure I'll recall more as soon as I hit "reply".

   Show morethread
3. fusiongyroSep 2018
   To understand how computers work is the reason that compilers is the capstone class in many CS programs. It unites automata with algorithms and machine code, bringing everything together in one program. I'm pretty sure I wouldn't have gotten through this exercise myself outside college.

   A lot of the resources out there are going to assume you have one or two sides of this triangle already and are ready to bring it all together. If you don't then you'll probably feel like you're in over your head.

   I would recommend checking out "Let's Build a Compiler". It's a bit old-fashioned but at least things are pretty simple. https://compilers.iecc.com/crenshaw/

   Different flavors of Markdown are not a bad place to start. Try and find something with a real syntax. As I recall, the original/official version is defined by a Perl program and has no true grammar. But other variants probably do.

   SQL is not simple. Just the parser for PostgreSQL's dialect was around 1500 lines of code, last I checked. Although, if you did a small subset, maybe it wouldn't be so bad.

   I really like the book Semantics with Applications which discusses the meaning of different programming languages. When I was starting out, it seemed to me like there was a lot riding on the syntactic differences between languages like C and Pascal. Now having seen the fringe, a lot of those differences are not as significant to me as they were before. This book helps you drill into what makes some languages different below the surface, and how to model those differences formally.

   I think it's eminently possible to make a small language, like "While", in a few pages of code. I would start with a very simple unambiguous grammar, and a little interpreter for it, but if you really want the full experience, generate assembler. This paper sort of presents the language I'm talking about, but there is a lot here about type theory and semantics that may not be interesting to you, so just ignore that. https://arxiv.org/pdf/1603.08949.pdf When I took compilers ~15 years ago, we generated code for nasm because gas syntax was too weird for us. Anyway.

   Another approach that looks interesting to me is "many small steps": http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf The idea here is to start with a program that only knows about integers, but handle everything end-to-end. Then you slowly add features one-by-one, but in an end-to-end fashion. I think this would be a lot easier to iterate and it hearkens back to Crenshaw's approach.

   A lot of compiler construction material focuses on Lisp and Scheme. This is because it sort of hides or ignores the parsing problem. You will probably have to learn some other languages to build a compiler; it wouldn't hurt to know some Lisp or Scheme to be able to access these resources. A lot of people build a Lisp-like language as their first for this reason too. Just something I'm pointing out.

   Anyway, it's a noble goal and best of luck!

   Show morethread
4. timtadhApr 2013
   I also highly recommend "Semantics with Applications" by Nielson and Nielson. I read it this January and it is an excellent book. It is very approachable for someone with only the lightest background in formal methods. If you are looking for a good introduction to the field I would start there. I am definitely going to look into the OPs book it looks awesome.

   download http://www.daimi.au.dk/~bra8130/Wiley_book/wiley.html

   print http://www.amazon.com/Semantics-Applications-Appetizer-Under...

   EDIT:

   after reading the author page it looks like the OPs book has not been updated so keep in mind that it is the state of the field as of the 80s. The work by Nielson and Nielson is fairly recent. I would also suggest "Principles of Program Analysis" for a follow up book.

   http://www.amazon.com/Principles-Program-Analysis-Flemming-N...

   Show morethread
5. timtadhFeb 2013
   I usually reference a combination of: Dragon Book, Muchnicks: Advanced Compiler Design, and Semantics with Applications. I have been meaning to pick up a copy of Engineering a Compiler. (I should also note I am currently reading: Principles of Program Analysis, it is a good book focusing on just theory. Read Semantics with Applications first it is basically the follow up)

   A guess my point is this: I have learned a great deal from the Dragon book. I think it is a solid book that has taught me a lot. There may be better books out there but I haven't read one yet (Advanced Compiler Design is great but it really is only about optimization and analysis you need an undergrad book to supplement it).

   Finally, I have encountered worse books on the subject of compilers. So yes, this is a book that I would recommend and continue to recommend.

   ps. You mis-characterize the length of the lexing and parsing coverage. It starts on page 109 and ends on page 302, the content goes to 964. Chapter wise: 3-4 lexing->parsing, (chapter 1-2 are really an introduction and illustrative example so they don't count). Chapters 5-8 cover the rest of what you need to get a working compiler + some other stuff. Chapters 9-12 (page wise 583-964) cover optimization and analysis in depth. So really, nearly 40% is optimization while about 20% is syntax analysis. This book has a lot of good material most of it isn't to do with syntax analysis and the syntax analysis is for the most part high quality.

   Show morethread
6. mahmudSep 2009
   Indulge yourself:

   http://library.readscheme.org/

   The must reads are Keny Dybvig's thesis, "Three Implementations of Scheme". The original lambda papers can wait until you read the Orbit paper, an optimizing compiler for T by Kranz, Rees et al.

   The Lisp implementation bibliography pretty much runs through PL research like a vein. Some of the stuff you must read for Lisp are typically in "books"; Christian Quinnec's Lisp in Small Pieces is the most important work, but you will need a good foundation in denotational semantics (you can get by with the one chapter in the little book by Nielson and Nielson, "Semantics with Applications: A Formal Introduction".

   Somewhere in there you will brush against various compilation methods and IRs for the lambda calculus, most importantly continuation passing style. Most semantics text introduce lambda calculus and its three rules, but none go in depth into this like the tall green book by Andrew Appel, "Compiling with Continuations", a good chunk of which can be read in Appel's other papers. Appel's work is MLish in nature, but don't let that stop you; most optimizing Lisp compilers are MLish down underneath anyway. CMUCL does very good type inference but gets short of implementing a full Hindley-Milner. Felleisen et al's "The Essence of Compiling with Continuations" might also come handy, though it's heavy on the theory. Andrew Kennedy continues the saga with "Compiling with Continuations Continued", this time CPS gives way to A-Normal Form, another IR. He describes the techniques used by a compiler targeting .NET.

   Most compiling "meat" can be found in the bits-and-bytes type papers. Wilson's GC bibliography "Uniprocessor Garbage Collection Techniques" is a must, it should have been called "What Every Programmer Should Know About Garbage Collection". Not to be confused with Richard Jones' "the Garbage Collection Bibliography". Boehm's "Garbage Collection in an Uncooperative Environment" is sheer hacking bravado, perhaps second only to "Pointer Swizzling at Page Fault Time", which should introduce you to memory management for disk-based heaps (i.e. object stores) among other things.

   Your start in hacking runtimes will probably be David Gudeman's "Representing Type Information in Dynamically Typed Languages"; this is where you learn how stuff looks inside the computer when you no longer need to malloc and free. A previous hacking of a Pascal dialect prepared me for this wonderful paper.

   Implementations of runtimes are documented by Appel, for SML/NJ, Robert MacLaclahn's "Design of CMU Common Lisp" (also perhaps Scott Fahlman's CMU report on CMUCL's precursor, "Internal Design of Spice Lisp", but that confused the crap out of me as I don't know the machine architecture they're talking about.) You will also enjoy the Smalltalk research starting with L. Peter Deutsch's first optimizing Smalltalk compiler, documented in "Efficient Implementation of Smalltalk-80", follow the Smalltalk lineage btw, all they way up to David Ungar's "The Design and Evaluation of a High Performance Smalltalk System" making sure NOT to ignore Self and its literature, also spearheaded by Ungar (Start your Smalltalk hacking career with Timothy Budd's "A Little Smalltalk", should take you about a weekend and will absolutely prepare you for dynamic languages; a similar system is described by Griswold and Griswold, compiler, intermediate representation and VM, but that one is for ICON.)

   Dynamic type inference and type-checking (TYPEP and SUBTYPEP, CLASS-OF, INSTANCE-OF, etc) you can learn a good chunk of how CLOS should look like to the runtime system from Justin Graver's "Type-Checking and Type-Inference for Object Oriented Programming Languages". He scratches the surface, and you should supplement this with a selection from Smalltalk and Self, though neither will prepare you for multiple-dispatch, for that peer into Stanley Lippman's "Inside the C++ Object System".

   I have deliberately avoided "classics" on Lisp, compiler construction, optimization, and other stuff. None of the books and papers I have recommended are as popular as SICP, PAIP, or AMOP. Or even the popular PL books, like EoPL, van Roy and Haridi, both of which you should read by the way, but they're stuff that you need to read and understand to be able to implement a practical Lisp implementation, or at least satisfy your curiosity.

   Show morethread