proj-plbook-plPartFormal

Table of Contents for Programming Languages: a survey


Part : Formal stuff

Note on academia research: academia is great but:

upshot: lots of hidden gems but huge time committment to find them and read them. Can't trust language in papers that claims that this or that is important for you to know.

http://www.cis.upenn.edu/~bcpierce/courses/670Fall04/GreatWorksInPL.shtml

http://lambda-the-ultimate.org/

c2.com

retrospective papers and blog posts by designers of great languages

preferentially read academic works that are designed to be read easily, rather than only to get past reviewers:

review papers textbooks talk slides introductory-ish encyclopedic works

note: if you ARE a programming languages academic, reading only these will be insufficient; you also have to keep up with some current literature, so that you are well-placed to make a new contribution.


todo:

Trevor Jim, What are principal typings and what are they good for? http://web.archive.org/web/20081118065537/http://www.church-project.org/reports/electronic/Jim:MIT-LCS-1995-532.pdf


universal combinatorial logic (not turing universal):

" Proposition 3 (Post) A necessary and sufficient condition that a set of operations form a basis for the nonzeroary Boolean operations is that it contain operations that are respectively nonaffine, nonmonotone, nonstrict, noncostrict, and nonselfdual " -- http://boole.stanford.edu/cs353/handouts/book3.pdf

NAND and NOR are universal

---

unconventional computer implementations:

https://news.ycombinator.com/item?id=7824588

---

https://surface.syr.edu/cgi/viewcontent.cgi?article=1012&context=lcsmith_other Definitional interpreters for higher-orderprogramming languages by John C. Reynold

about meta-circular interpreters, classifying them into four classes, and how to transform them between the classes

Abstract. Higher-order programming languages (i.e., languages in which procedures or labels can occur as values) are usually defined by interpreters that are themselves written in a programming language based on the lambda calculus (i.e., an applicative language such as pure LISP). Examples include McCarthy’s? definition of LISP, Landin’s SECD machine, the Vienna definition of PL/I, Reynolds’ definitions of GEDANKEN, and recent unpublished work by L. Morris and C. Wadsworth. Such definitions can be classified according to whether the interpreter contains higher-order functions, and whether the order of application (i.e., call by value versus call by name) in the defined language depends upon the order of application in the defining language. As an example, we consider the definition of a simple applicative programming language by means of an interpreter written in a similar language. Definitions in each of the above classifications are derived from one another by informal but constructive methods. The treatment of imperative features such as jumps and assignment is also discussed

---

https://aleksandarmilicevic.github.io/hola/ https://news.ycombinator.com/item?id=19265061


Links


Chapter ?: CS theory 101 Chapter ?: Models of computation (Turing-equivalent systems) (also, models of concurrent computation) Chapter ?: Sub-Turing models of computation Chapter ?: Halting Chapter ?: Semantics