The memory models that underlie programming languages (2016) | Hacker News Reader

The memory models that underlie programming languages (2016)

canonical.org

177 pointsbshanks35 comments

The older I become the more I realize how influential Lisp is/was. The Lisp memory model presented here looks like object oriented data structures, if you squint a little. Java dragged C++ programmers 'halfway to Lisp' [1]. I now do a lot of programming on Python, which is so obviously like Lisp that MIT teaches it instead of Scheme. We don't have continuations and macro yet in mainstream languages, but we'll get there.

[1] http://people.csail.mit.edu/gregs/ll1-discuss-archive-html/m...

One reason: Lisp was the first to use a garbage collector and thus needed a form of managed memory. In the 60s and early 70s it was relatively alone with its feature set and a bunch of things in the early evolution of Lisp (like compilers (1962), images as memory dumps (1962 or before), records, arrays, large and small numbers, ...) lead to runtimes supporting these features. Special 'machines' appeared in the 70s which implemented parts of the runtimes in virtual machines or even physical machines (the JVM is in some ways technically similar to other Lisp runtimes -> that's why Steele talked about half-way to Lisp, which in reality may only be 1/4 of the way). In the 70s/80s then the need for larger memories in Lisp programs lead to a bunch of new garbage collection schemes, like generational GC. In the 70s/80s then new languages appeared which were influenced by Lisp implementation techniques: like ML or Smalltalk. Later languages like Ruby were influenced by the implementation of Emacs Lisp.

On Xerox's paper about Mesa/Cedar they describe how they saw as influential to support the same kind of development workflow as Lisp/Smalltalk on a strongly typed systems language.

Meaning the REPL, dynamic code reloading, debugger, ...

Then we had to wait a couple of decades to catch up and aren't still not there.

> Python, which is so obviously like Lisp

Hang on! Do you mean some similarity other than what is talked about in the article?

The main dissimilarity between python and lisp is that you can't use code as data in python, so there's no macros. In most other ways they're pretty similar.

Serious lambdas and closures? Sophisticated array handling? A full-featured numerical tower? Conditions? Python's namespaces seem primitive compared to Lisp. Etc.

>"A full-featured numerical tower"

What is a numerical tower?

https://en.m.wikipedia.org/wiki/Numerical_tower

Code is data is often touted as the integral feature of lisp though, so without it, a language really isn’t much like lisp at all.

This comparison by prominent Lisp/AI figure Peter Norvig is a good treatment of the similarity: http://norvig.com/python-lisp.html

Sorry I'm a python veteran but lisp luddite. When you say python is so obviously like Lisp, are you referring generally to the ability to override the language syntax behaviour? Eg. __eq__ ?

Correct me if I'm wrong, but isn't this article talking about data layout in memory, and not memory models at all?

https://en.wikipedia.org/wiki/Memory_model_(programming)

Regardless, interesting to read about "old" languages, such as Cobol. The way data was laid out in Cobol programs made sense with old computing resource limitations.

There's a footnote for the first sentence of TFA that addresses this.

You mean this?

"² I’m calling these six conceptualizations “memory models”, even though that term used to mean a specific thing that is related to 8086 addressing modes in C but not really related to this. (I’d love to have a better term for this.)"

I think that's even more wrong. The Wikipedia article gives a pretty good idea what the term means.

I think a good term for what he's talking about is "data [structure] memory layout".

The wikipedia article talks about one thing the term means. The thing the article talks about is definitely not data structure layout in memory, though.

Some passages are suggesting otherwise:

"In this object-graph memory model, if you have several entities of the same type, each one will be identified by a pointer, and finding a particular attribute of an entity involves navigating the object graph starting from that pointer."

I consider even the Cobol case as a kind of data structure, although a very limited and inflexible one:

"For example, an account object might have an account-holder field from bytes 10 to 35, which might contain a middle-name field from bytes 18 to 26."

Sayeth Wikipedia https://en.wikipedia.org/wiki/Data_structure:

"In computer science, a data structure is a particular way of organizing and storing data in a computer so that it can be accessed and modified efficiently"

Anyways, I kinda agree with you as well. Usually when talking about data structures it's related to some particular algorithm, say a red-black tree.

The first thing you quoted says absolutely nothing about layout. But more importantly, layout might come up but it's not what the article is about and it does not use the term 'memory model' as a stand-in for layout.

I consider that first thing as data is laid out in more or less random [0] locations, with pointers between objects holding the whole thing together.

I guess we understand (memory) layout differently. How'd you define it?

[0]: Random as in allocated addresses may vary between invocations.

You don't know if it's laid out 'at random' because, again, the thing is not actually about layout.

I think you're getting a little hung up on this being 'wrong' and missing what the thing is trying to convey. Scroll down to the bits about SQL or hierarchal filesystems.

I think a critical approach you can try is that maybe these things are different in some important ways and perhaps that's why there is no obvious unified term that comes to mind to describe them and see where that takes you. 'Kragen confused some overarching abstraction he's trying to describe with "memory layout"' is likely neither true nor fruitful.

He's just using the term archaically. Before caches were combined with SMP on consumer level systems (which is remarkably recent), the term 'memory model' did mean various forms of data layout decisions.

The 8086 thing was legitimately called a memory model, choosing how the distinction between the 64k segments would be treated logically by your program. https://en.wikipedia.org/wiki/Intel_Memory_Model

> The 8086 thing was legitimately called a memory model...

Damn, completely forgot about that despite using many of those segmentation rules like "tiny", "large" and so on a long long time ago.

That's one meaning of memory model. Historically, however, "memory model" refers to the theoretical way that a language represents memory, independently of platform. For example, see this presentation (http://www.cs.cornell.edu/courses/cs2022/2011sp/lectures/lec...) of "The C Memory Model" (which happens to deal with memory layout very intimately, because C is very close-to-the-metal).

The use of "memory model" to describe primarily threading/concurrency behavior seems to be a Java innovation that's been picked up by the Go community.

This is the best way to categorize programming languages, but applying it only to relatively unpopular languages seems a strange choice.

I'd categorize the popular ones like this:

- One sparse byte array: C, C++

- GC heap with class instances with fields: Java, C#, etc.

- Affine structs and enums on the stack, plus library support for heap and other models: Rust

- Dictionaries and primitives: JavaScript, Python, Ruby, etc.

- Immutable structs and enums on the heap: (safe) Haskell

- Textual/array/dictionary variables, global and local: bash and other shells

What about Golang?

Same category as Java. Values can go on the stack in Go, but it's an optimization, the language semantics are still essentially based on the casual use of the heap.

There's a way in which C# is Java done right. Go can be seen as Java done right, for a different definition of "right". On paper they are virtually identical languages. In practice they are quite different.

>"Go can be seen as Java done right, for a different definition of "right"

Can you explain this? In what sense is Go "Java done right"? The OPs comment isnt offering me much insight into your comment. Thanks.

For as popular as Java is, and as much work has been put into it, and as high quality as its multiple JVM implementations may be, it still shows its heritage as a language designed for a different purpose entirely (to run set-top boxes) than either the one Sun wanted to put it to ("write once run anywhere") or the one it ultimately ended up dominating (server-side code).

The biggest example in my opinion is the grave error that Java made in making classes declare their conformance to interfaces. Go's structural typing is uniformly superior, and I believe this one change is roughly 80% of Go's ability to have generally simpler code and to avoid the framework monstrosities that populate the Java world. I fully recognize that sounds bizarre if you've only used one or the other, but I believe it. The ability to declare an interface in my module that some other module that knows nothing about me automatically conforms to prevents people in the Go ecosystem from having to pre-emptively buy into huge frameworks to solve this simple problem. (This is a great deal of the reason I darned near classify Go as a scripting language; for all the drama about "missing generics" I find the experience of writing Go to feel much more like Python than like writing Java.) I have enough of the "explicit better than implicit", formal proof Haskell-y sort of stuff in me to understand where that impulse comes from, but I believe that this is a case where those intuitions are disproved by experience.

Recently I was looking at an crash dump in an Atlassian product, and it clearly had two of those monstrous frameworks in there. We were 600 stack levels deep at the point of the failure. ~100 of them I could excuse as a template renderer recursing on the AST of the template, but there was just this amazing amount of junk in the stack trace. You don't get that in Go code; it looks more like a typical Python dump in depth.

There's a few other places where Go gets things right just by virtue of being newer; again, contra to accusations that the designers have never heard of newer tech, it has closures in it from the get-go. (Yes, I am aware those are hardly new, but if the designers really were completely closed off those wouldn't go in there.) Go has value types from the beginning, which Java is still jamming in. There's a few other things too, like just generally being a bit more memory-aware than Java and a bit more able to put things on the stack, even if the optimizer is generally not that great. It's the combination of these little fixes that are the reason why Go hangs in there with Java performance wise by most measures, and is often more memory efficient, despite the probably 3+ orders of magnitude more effort put into the JVMs.

> One sparse byte array: C, C++

What does sparse mean in this context?

Thinly populated. The whole address space is the array and addresses/pointers are indices into it. This point of view might not necessarily be supported by the actual language specifications, though.

Really disappointed with the treatment of Forth, and other non conventional languages. Forth doesn’t have anything really resembling von Neumann machine random access memory. Neither, for the record, does Turing machines. But the author dismissed these as oddities when in fact they are the most unique examples of something different.

Well, many Forths provide some form of access to heap[1] which is altogether that different from e.g. C malloc

[1] https://www.complang.tuwien.ac.at/forth/gforth/Docs-html/Hea...

[2] http://www.mosaic-industries.com/embedded-systems/legacy-pro...

I'm interested in human-like storage layers and wondering if anything has been done here. Content-associative memory is one idea but doesn't go far enough. Neural nets are a lot closer but at the moment they seem limited to pattern matching rather than storage and exploration, although I guess you could say supervised training is equivalent to storage.

I'm thinking of a DSL on top of a pure associative memory, which will remember Things with weighted connections to other Things. Matching consists of not only showing the idea but also related ones more distant. Is there anything like this?

The last time this is posted, the author had me at "Interlude: why is there no Lua, Erlang, or Forth memory model?" .. and .. a year later, it still holds true.

Lua doesn't get quite the cred it should, in the language wars. Its one of those "just going under the radar, getting things done" languages..

EDIT: like, isn't everything a finite map eventually, or at least partially expressible, idktb......

The LISP model is/was slightly different. Generally there were a lot of slightly different LISP models, but the first few LISPs were organized in cons cells and atoms. Actually the latter was 'atomic symbols'. An atomic symbol was kind of an object and some attributes in a property list: typical for symbols and functions. Even numbers were stored as kind of pseudo atomic symbol. See the Lisp 1.5 manual from 1962, section 7.3 - where the memory model is described.

Then LISP models evolved to still use cons cells, but there now are a bunch of primitive objects (which were not introduced by Java, but existed in LISP long before) like certain numbers and characters. LISP then also did not organize everything as atomic symbol. Atoms were not symbols and a bunch of other data types. For example numbers were no longer (pseudo) atomic symbols. There are atoms, but atom then only meant: all data types which are not cons cells. Where originally there were only cons cells and atomic symbols.

LISP tries to avoid to store pointers to primitive numbers/characters and can store them directly. Most objects are tagged and tags for primitive types are stored without added words. Thus a cons cell with two numbers can be two words and each word is some primitive number. The implementation may also avoid to tag cons cells. Instead the pointer to a cons cell will be tagged. Similar is true for vectors. vectors also may not only be vectors of pointers, but can store primitive objects directly and may be optimized for some primitive objects: for example a vector of bits is just a vector header and a one dimensional packed array of bits. The header can't be avoided, but the bits will be stored directly and not as array of pointers to bits. Some objects may be allocated on the stack or in registers - for example primitive numbers may exist multiple times in memory - but other data objects may only exist once - like a string, which is a vector of characters.

So for primitive data types (some numbers, characters, ...) LISP tries to avoid pointers to them, makes them as small as possible, has the tags integrated into the word representation (thus on a 64bit machine typically a fixnum integer will not be able to use all 64 bits, because the tags need to be represented) and integrates the bits in such a way that they can be efficiently set and checked, possibly even by processor instructions - like on a SPARC processor which has 'some' primitive support for that.

Other types of things in memory then are symbols, functions (also machine coded functions) and record-like objects: structures and instances of classes. Those records usually will use a vector to store their slots. Even more data types exist with a low-level representation like hashtables and multi-dimensional arrays. The organization of these objects in memory can be relatively simple (one big pool) or complex (multiple type sorted pools with generations).

> Atoms were not symbols and a bunch of other data types

I meant:

Atoms were now symbols and a bunch of other data types.

Reply on news.ycombinator.com