Table of Contents for Programming Languages: a survey
spectrums:
What is a low-level language? Two definitions are:
More specifically, a low-level language:
One common class of CPU-time overhead is automatic memory management. In languages with garbage collection, a call to the garbage collector sometimes takes a long time, and in languages with reference counting, a single reference decrement could in the worst case lead to an arbitrarily long cascade of memory deallocations. In addition, automatic memory management may not deallocate memory as soon as the programmer knows that it could be deallocated, so this often adds memory overhead. In addition, in languages with automatic memory management, the programmer must interact closely with automatic memory management if they want to pass a pointer to memory allocated by their program to an outside process, and in many languages with automatic memory management, the necessary primitives do not exist (in the base language; most languages have an extension API that includes these facilities, but utilizing the extension API often requires use of another language, such as C). For these reasons, 'lack of mandatory automatic memory management' is considered by many to be another criterion for a language to be considered 'low-level'.
If there are two languages A and B, and A compiles to B, then according to our definition, B <= A, because if B does not give you the capability to control CPU or memory in some way, then neither can A. One might think that ordering is strict, that is, B < A, that is, A must be at least a little higher level than its compilation target language, but this is not true; for example, you can write a 'compiler' that compiles a language to itself by merely returning as output the same source code that it was given. One can imagine less trivial examples, too, however, in which there are two languages which are equally able to express low-level constructs but which express them in differently ways; such a pair of languages could compile to each other.
Some fans of high-level languages might define things a little differently; instead of enumerating abilities of low-level languages, they might enumerate lists of things that their favorite high-level languages 'take care of for you' so that you 'don't have to worry about' them.
todo leaky abstractions
see also Part Implementation, Chapter Efficiency.
discipline (safe vs unsafe; tradeoff between programming time and debugging time (part of this: protect programmers from themselves), also flexibility vs self-documenting architecture for programming-in-the-large, also making others's code easy to read) (Yegge's liberal vs. conservative: https://plus.google.com/110981030061712822816/posts/KaSKeg4vQtz) Yegge gives some specific features that are polarized in this spectrum:
big/small
performant/not (fast/slow)
lazy/eager
functional/not note: the word 'functional' is used in multiple ways when talking about programming languages:
Often, the latter two concepts coincide; because their incidence is highly correlated, some confusion has developed between them, and the word 'functional' has come to mean either or both. Languages which are both (pure function)-centric and (first class function)-centric often are based on a lambda calculus-like fundamental model.
statically typed/dynamically typed/gradually typed/mostly untyped http://ecee.colorado.edu/~siek/gradualtyping.html
should we list models of computation here? maybe just the most 'important' ones in terms of programming language families:
turing, assembly, imperative lambda calc, ? , haskell/purely functional concatenative, ?, forth?, joy relational, ?, SQL logic programming, ?, prolog combinatorial, Nock, Hoon mu-recursive, ?, ? grammar-based, O-meta, ? (see also the list of Turing-equivalent systems in the formal chapter)
early binding/late binding (static/dynamic)
strictly typed/not
scripting/systems/application/end-user/embedded scripting/glue scripting: one liners from command line?
a language that is invented for people to write programs in.
(note: one might say 'general purpose' but this is more often used to talk about application domain; e.g. general purpose vs. systems vs. scripting)
agglomerative vs. spartan
agglomerative: 'offer all features that programmers find useful'
spartan: 'be opinionated.'
motivations for spartan can be:
agglomerative: non-orthogonal features are okay, because they save programmers time
spartan: minimal orthogonal subset of features
the defining characteristic of a spartan language design is to say, "Yeah, we agree that this feature would be commonly and practically useful, but it is not strictly necessary and we're not going to include it ever". (note the 'ever'; all programming languages have to initially omit some desired features because they don't have time to implement them, or because they are as of yet unsure what the best design is for the feature) (note the 'commonly': all programming languages omit features because they think they would only be of niche usefulness, therefore their complexity cost outweighs their benefit) (note the 'agree': often a language designer feels that some proposed feature would not really serve any significant use, and that existing mechanisms are just as good) (that being said, these criteria are rarely absolutely met; there is almost always some arguent that adding feature X has disadvantage Y). The usual reason given for the omission is that some other way of accomplishing the same thing is more in keeping with the desired style.
'spartan' is similar to the term 'Fluchtpunkt' as used in http://replove.herokuapp.com/sakura/index.html
examples: Python's OOWTDI, e.g. iteration over recursion, disinclusion of tail call optimization
examples: Golang's dislike of exceptions, possibly golang's exclusion of generics
examples of some agglomerative languages: 'practical lisps' from http://replove.herokuapp.com/sakura/index.html
a language with a very heavy focus on simplicity.
usually because it is an intermediate target of compilers and/or interpreters, for interoperability or for other reasons. Sometimes just for the sake of simplicity (e.g. Nock).
what sets this apart from 'spartan' languages is that a 'spartan' language will still include non-orthogonal features if their exclusion would make it just too annoying to program in the language; but a kernel language isn't expected to be a sensible way for humans to program in, or even to read; even the language designer prefers to program in something higher-level.
a kernel language is not necessarily completely orthogonal.
A common case of non-orthogonality is the inclusion of multiple ways to do the same thing for reasons of efficiency, e.g. a kernel language might provide an integer addition operator even though Successor (+1), along with basic control constructs, is theoretically sufficient to express addition, because on most platforms integer addition can be accomplished in O(1) (constant time) by an optimized primitive, whereas calling Successor n times to add n to a number is an O(n) operation. Similarly, a kernel language might provide floating-point data types and arithmetic even though it could theoretically only provide bitstreams or only provide integers, and expect a library to handle floating point, because by providing floating-point primitives it can map these to optimized implementations on the underlying platform.
examples:
interoperable common targets:
intermediate targets and cross-compilation bootstrap subsets of various languages:
languages which have spartan motivations to be kernel languages:
languages which have pedagogical motivations to be a kernel language:
languages which are designed to be used embedded within or as scipting for other applications or devices.
such languages are sometimes very small in order to make them efficient and portable.
sometimes, like DSLs, they have features for specific niche application domains.
examples:
a language with an even more extreme focus on simplicity than kernel languages. Generally the calculii are absolutely orthogonal.
The purpose of the calculii is usually not to program in or to compile to, but rather as a mathematical abstraction about which theorems may be proved. The smallness of the language is crucial because often proofs will have to treat each part of the language by cases. The length, readability, and often the efficiency of the resulting programs is immaterial.
examples: Turing machines, lambda calculus, SKI combinator calculus
a "domain-specific language" is a term for a language which, rather than being "general purpose" or even with a tilt towards a domain such as 'systems programming', is narrowly targeted at a niche domain.
todo examples:
a sub-Turing DSL is a DSL that is not Turing complete
todo examples:
a data language is a language intended to express data, but not computation on that data
examples: HTML, XML, the literal-defining subset of any other language
todo: merge with above?
(big ideas; constraints)
these are not mutually exclusive
block-structured
GOTO considered harmful ; ban (discipline) on GOTO; flow control via primitives for selection (if) and iteration (e.g. while) and subroutine call and return
call stack
differing opinions on what it is
encapsulation of data with methods
forced encapsulation (access modifiers) vs. consenting adults
object scope; self object
message passing
polymorphism
Bob Martin claims that OOP also involves a ban (discipline) on calling functions via pointers; he claims that, because polymorphism covers the main reason to do this, along with the polymorphism in OOP tends to come a removal of the ability (or cultural encouragement) to do this at all, improving discipline (http://blog.8thlight.com/uncle-bob/2012/12/19/Three-Paradigms.html)
prototype vs. class-based
single vs. multiple inheritance
inheritance vs. composition
functions of OOP:
"OOP to me means only messaging, local retention and protection and hiding of state-process, and extreme late-binding of all things. It can be done in Smalltalk and in LISP. There are possibly other systems in which this is possible, but I’m not aware of them." -- Alan Kay
more on how Kay defines OOP: " Which didn’t even require inheritance, which is not like we know it today:
I’m sorry that I long ago coined the term “objects” for this topic because it gets many people to focus on the lesser idea.
Where the big missing piece lacking in mainstream typed OO languages today is:
The big idea is “messaging”
He advocates focus should instead be on messaging and the loose-coupling and interactions of modules rather than their internal object composition:
The key in making great and growable systems is much more to design how its modules communicate rather than what their internal properties and behaviors should be." -- http://mythz.servicestack.net/blog/2013/02/27/the-deep-insights-of-alan-kay/
The concepts of instances of classes, of objects with properties, and of different types of things which act autonomously according to their nature, go back at least to Plato and Aristotle. See An Aristotelian Understanding of Object-Oriented Programming, Object-Oriented Programming and Objectivist Epistemology: Parallels and Implications.
based on Turing machine
based on expression evaluation
referential transparency
don't use variable assignment
discipline/ban on (most) side-effects
higher-order functions function composition maps
tail call optimization
partial function application
closures
anonymous functions
based on lambda calculus
"Here's the gist: in most mainstream languages, you describe how to solve a particular problem; in declarative languages, you merely describe the result you want, and the language itself figures out how to get there." -- http://brikis98.blogspot.com/2014/04/six-programming-paradigms-that-will.html
examples: prolog, SQL
disadvantages: if the way that the language figures out how to solve the problem is inefficient, you end up having to learn about what it's doing and optimizing it anyway, in which case the resulting program is even harder to work with than imperative languages because of the additional layer of abstraction.
advantages: less syntax, opportunities for metaprogramming, close to the metal
disadvantages: programmer has to keep the contents of the stack in mind at all times. Named variables (and keyword arguments) can be seen as an invention to avoid having to do this.
SK combinators Y combinator
??? what family is Nock in? is it combinatory? is it its own thing?
dependent typing: can capture properties of values, e.g. you can say 'a list with 3 elements' or 'a list with at least one element' or 'a number less than 255'. fully generalized dependent typing can capture arbitrary computable properties of values. Inference with fully generalized dependent typing is intractable.
http://www.infoq.com/presentations/data-types-issues
slide 12
classify type systems into dimensions static/dynamic, weak/strong:
dynamic, weak: assembly dynamic, moderate: js, ruby dynamic, strong: python, clojure dynamic-ish but somewhat static, moderate: typescript, dart static-ish but somewhat dynamic, moderate: java, C# static-ish but somewhat dynamic, strong: scala static, weak: C static, strong: OCaml, Haskell
slide 13
classify type systems into dimensions coarse/detailed, weak/strong:
coarse, weak: C coarse, strong ("my way or the highway"): Go, Java 4, Pascal detailed, weak ("cutting corners"): eiffel, typescript, dart detailed, strong ("type it to the max"): scala, F#, haskell, ocaml moderate, moderate: C#, java 5+
My Way or The Highway (coarse, strong):
" Simple type systems No generics Not that extensible by users
Type it to the Max: " Rich* language to write types Type combination forms, including generics. Type systems often inspired by logic.
Where dynamic languages had the upper hand: – No type-imposed limits to expressiveness Rich type system + escape hatches such as casts – No boilerplate Type Inference – Easier for exploration Bottom type Nothing, ???
Other Strengths of Dynamic • Simpler languages − Rich types add complexity • Fewer puzzling compiler errors
Cutting corners: Appeal to user’s intuitions (covariant generics). – Employee are Persons – So functions from Employees to Employers are also functions from Persons to Employers, right? • Embrace unsoundness. • Easy, and superficially simple. • But, fundamentally, a hack. • Can we build great designs on false theories?
Precision Soundness Simplicity Take Any Two?
"
hmm what "take any two" would i say? maybe:
permissive of power (e.g. dynamic languages permit generics, even though their type system doesn't 'understand' this concept) simple/easy to learn and use precise (e.g. you can have generics in dynamic languages, but they aren't typechecked; it's more precise to have a language whose type system knows about generics specifically)
i guess that's the same as what he said; he's replacing my 'precise' with 'sound', and my 'precision' with 'permissive of power'