Oberon – The Overlooked Jewel [pdf]
citeseerx.ist.psu.edu
citeseerx.ist.psu.edu
Prof Franz did his PhD under Niklaus Wirth. His thesis was on Semantic Dictionary Encoding - a method for storing a compact semantic tree representation of a program in what is effectively a prefix code (e.g. similar to Huffman coding) that it exploits beautifully to both compress the tree and to use heuristics (the same on the encoder and decoder) to generate templated code fragments to allow the code generator on load time to do less work. Published in '94, it unfortunately was totally overshadowed by Java.
It's still one of my favorite papers, and one day I still want to go down the route of actually implementing SDE properly (there are implementations for Oberon - one of the early remarkable feats was that because of the more compact representation, on MacOberon it was on some hardware faster to load and generate code from these "slim binaries" than it was to just load a native binary, because the code generator was fast enough to beat the disk IO cost of loading a larger binary...)
One of Franz' PhD students was Andreas Gal, who wrote the paper on trace trees and applied it to JIT'ing Javascript, and worked as CTO at Mozilla.
I think http://hokstad.com/semantic-dictionary-encoding is your work, so I assume it is a good description of what I can expect from reading that thesis.
http://hokstad.com/semantic-dictionary-encoding
Did you ever get around to exploring SDE's in a Ruby context?
The CPU/Memory/Disk gap has only grown since then - even with SSD drives it is still a lot bigger than twenty years ago. So this is probably even more true today than back then, no?
Reminds me of blosc, which uses data compression algorithms that are so fast that the cost of spending CPU cycles on it is lower than the savings in terms of reduced time to read/write to disk[0].
If the code is structured right, and you could certainly try to sort the code based on a dependency graph, you don't even need to load the entire file before you can start generating code from SDE (but you'd need to be prepared to stub out forward jumps so they point to something that'll generate or wait for generation of the rest where necessary).
So it looks like you could do some kind of heavy "portable optimisation" pass first, then distribute the resulting SDE of that, and do a second, lighter pass of "local" optimisations targeting the local architecture.
(in fact, I believe quite a lot of Franz' subsequent research has been in areas like that, though mostly JVM focused)
The Java approach is to do parsing, semantic analysis, and compilation to bytecode on one side of the network. Then JIT compilation is done on the other side.
The v8 / "modern JS" approach is to do gzip compression of source code on one side of the network. Then decompression, lazily parse, and lazily generate native code on the other side.
Now I recently look at v8's parser, and it's fiendishly complex [1] and somewhere north of 20K lines of code -- and yes that's just the parser.
So there are downsides. SDE might be more elegant and efficient overall (?) But when you are dealing with networked code, you can't change both sides of the wire at once. So we are sort of stuck with suboptimal interfaces and brute force on both sides.
That said, I do think there is a good argument to be made for shipping plain text source code and using brute force to make parsing and analysis in the browser fast. (That is, writing ridiculous amounts of hand-tuned C++ code.)
I just think SDE is worth more exploration. It lost out not because it failed to compete on merits with the JVM but because the JVM basically cut short any hope of it getting mindshare at the time.
It's possible the JVM or V8 approaches are simply superior designs. But we don't really know, because such huge resources have gone into making the JVM or v8 approaches work, and not just SDE but most other approaches from that time became near instant dead ends.
> The v8 / "modern JS" approach is to do gzip compression of source code on one side of the network. Then decompression, lazily parse, and lazily generate native code on the other side.
The interesting part of this is that you could treat SDE simply as a way to short-circuit the parsing and compression step by using it to serialize the AST and still retain exactly the same code generation. You can lazily generate native code from it, as long as you apply the heuristics to build the dictionary on load time (necessary to rebuild the correct tree).
Whether it'd be worth it is an open question, but I wish I had time to explore it.
I'm basically looking at ways to cut out the JSON.stringify step. So basically, first turn a JSON-friendly object into a binary representation, which is then compressed into a bytestream, and stored in a URI-safe string.
This might lead to something generally usable, and faster/smaller than lz-string. I know JSON alternatives like flatpack and messagepack exist, but this would be a much simpler, lighter JS library, single-digit kilobytes in size before gzipping. It also would probably be backwards compatible all the way to IE6.
[0] https://github.com/linnarsson-lab/loom-viewer/blob/master/cl...
That part of it is really independent of the code generation aspect, and could easily be adapted to serialize arbitrary types of tree structures.
Basically what you need is a general mechanism that takes a possibly templated rule, and adds to the dictionary. Then you need a mechanism that looks at a JS object and instead of spitting out JSON, matches the current node to one of the dictionary items and spits out a bit pattern and then recursively spits out the bit pattern for the template arguments. The decoder can basically be very simple recursive descent: Identify the dictionary entry, look it up, find the template rule, recursively call itself to retrieve the template patterns, and reconstitute the object.
The "magic" then lies in the heuristics, which can be very generic (e.g. suitable for any JSON) or very specific (e.g. embedding domain knowledge of what the trees are likely to be shaped like, or at least code to be able to recognize and encode complex shapes when seen).
FWIW here is a long thread I started about an AST serialization method, with some prototype code: https://www.reddit.com/r/ProgrammingLanguages/comments/79fkp...
It is lightly "compressed" -- there are no native pointers, but offsets instead. The in-memory format is the same as the on-disk format. You can mmap() a file and then start following "pointers" right away.
I didn't develop it for transmission over a network, but it could be used in place of Python's .pyc files, which essentially cache parsing and bytecode compilation, and are a big tree/graph data structure. It can represent arbitrary graphs.
You could add dictionary compression in a tree-aware way or a tree-oblivious way... not sure how that compares to SDE.
FWIW someone suggested WebAssembly on that thread, but it's apparently no longer an AST -- it's bytecode (I guess more similar to Java.)
That makes it harder to traverse - you can't jump to arbitrary locations without decoding everything before it, because you need to look at everything to apply the heuristics to build the dictionary. But it makes it likely to be far more compressed - e.g. you can have dictionary entries shorter than a byte, and you can build dictionary entries that represents whole subtrees, and in SDE's case those subtrees can be templated.
I think that overall startup time for example is a more interesting goal, not just the amount of data transferred over the network or streamed off disk.
Startup time can be saved by doing parsing and semantic analysis on one side of the network. And if you know your target architecture, you can do code generation there too, although that doesn't seem to be the way any systems have evolved -- even Android was doing native code generation on the device recently.
I guess I am having trouble seeing situations where both of these are true:
1) A compression algorithm specific to a file format is say 50% or 100% better than gzip or xz.
2) That 50% or 100% results in a big user-perceived improvement.
Most bytecode formats are "lazily" decoded, although they can be somewhat large. I sort of like the scheme I proposed because it's both compact and can be lazily decoded. You could make it more compact, but then you would have to decompress the whole thing up front.
> I think that overall startup time for example is a more interesting goal, not just the amount of data transferred over the network or streamed off disk.
I agree, but to that end size is a major factor, and if the tree is structured properly nothing stops you from being able to start executing the code during generation ("just" generate stubs for missing functions that will wait for or trigger generation of the missing function)
> Startup time can be saved by doing parsing and semantic analysis on one side of the network. And if you know your target architecture, you can do code generation there too, although that doesn't seem to be the way any systems have evolved -- even Android was doing native code generation on the device recently.
Agreed, and SDE will do the parsing and semantic analysis on the other end too.
> I guess I am having trouble seeing situations where both of these are true:
But that is not the goal. The goal is to generate architecture independent code in a format that is very fast to generate code for. The compression and reduced load time is just a happy side-effect of speeding up the code generation by structuring it for reusability of code fragments during generation.
As such the decompression is "free", as it's nothing more than very lightweight dictionary lookups and insertion during the code generation.
> Most bytecode formats are "lazily" decoded, although they can be somewhat large. I sort of like the scheme I proposed because it's both compact and can be lazily decoded. You could make it more compact, but then you would have to decompress the whole thing up front.
Lazy decoding is possible as described above, though I agree that ability to do "random access" when generating the code is a benefit. Systems like SDE certainly do depend on outputting the code in a sensible order. Though incidentally you can get a lot of that simply by carefully deciding on how to traverse the AST to generate the output. E.g. traverse outer definitions, then the main entrypoint and output any obvious dependencies first.
ftp://ftp.cis.upenn.edu/pub/cis700/public_html/papers/Franz97.pdf
http://www.ethistory.ethz.ch/rueckblicke/departemente/dinfk/...
https://en.wikipedia.org/wiki/Ceres_(workstation)
Along with its predecessor Lilith, for running a Modula-2 system.
There was even a Russian clone of the Lilith called Kronos https://en.wikipedia.org/wiki/Kronos_(computer)
Along with Plan 9, I see this project as a starting point for a deep dive into a world of alternative computing platforms.
(edited for spelling, bit-slice)
https://en.m.wikipedia.org/wiki/Atari_Transputer_Workstation
Includes some interesting stuff.
If you're interested in that field, this is the book: https://www.oldcomputerbooks.com/pages/books/K6246/mick-john...
I don't know much about bit-slice processors. They seem like an interesting historical footnote at this point. Are there any current applications for the technology?
I wonder why people didn't combine 16 chips to create 64-bit processors. Or did they?
Of course, 64 bit registers and less memory would have been useful for scientific computations. However, I think it is hard to build a fast integer multiplier from bit-sliced CPUs (you can, but by the time you are done, the CPU doesn’t look like a cascade of smaller width CPUs anymore). I would guess making floating point perform on bit sliced processors has its challenges, too.
I learned some interesting compiler techniques from reading that book.
You can run Project Oberon with this emulator (pre-built binaries available): https://github.com/pdewacht/oberon-risc-emu
This includes my own Oberon-07 compiler targeting the JVM: https://github.com/lboasso/oberonc
For example the Oberon definition below:
DEFINITION MathUtil;
PROCEDURE ln(x : REAL) : REAL;
END MathUtil.
exposes the Java MathUtil.ln() static method: public class MathUtil {
public static float ln(float x) {
return (float) java.lang.Math.log(x);
}
}
A client module can use now the Java implementation of ln: MODULE Client;
IMPORT MathUtil;
VAR x: REAL;
BEGIN
x: = MathUtil.ln(2.0);
MathUtil.ln()
END Client;
For a complete example see https://github.com/lboasso/oberonc/tree/master/examples/fern > DEFINITION
I am not sure, but would a MODULE only containing declarations (and no or empty body) also work, syntactically?Bluebottle OS, which introduced the variant known as Active Oberon, made use of multithreading in form of active objects, a concept similar to goroutines.
Its compiler Paco, is one of the first multithreaded compilers I know of.
SSL was not yet a thing when Oberon was popular in the mid-90's, so I don't remember if the browser of the time supported it.
Network programming was a mix of Ethernet and Oberon own protocols, there was support for network printing and file shares.
All books that Wirth wrote about Oberon were written using the text editors of the OS.
It looks like there's a box there but I can't click it.
I first heard this idea, in a slightly different form, from Vickie Markstein (part of IBM's 801 team) in early '88. She suggested using this idea as an acid test for optimizations. For example, if the compiler with value numbering compiled itself faster than the compiler without value numbering, then she'd say value numbering was worthwhile.
Given the organization of the 801 team, it's possible the idea was due to John Cocke or one of the other members. Doesn't matter much, I think.
I've never had the opportunity to test optimizations using this approach, but I think it would be a fun way to approach the question of adding optimizations to something fast & simple like the Oberon compiler, the Plan 9 compiler, or the Go compiler.
Indeed, for a _system_, like Oberon or Plan 9, where everything is compiled with the same compiler, we could go a step further and try adding the optimization, rebuilding everything, then timing the new compiler. That way any benefits the optimization brought to handling I/O and such would be properly credited and we'd (hopefully) see a steady improvement in the programmer's experience.
Preston
Having said that, the language goes a bit too far trying to be "as simple as possible but not too simple", at least to my taste -- in a way that Go seems to be, only much more so. It also looks verbose - especially compared to C. So, while I marvel at the language and have a feel for its weird beauty, I don't think I'd be comfortable using it in my day to day activity - I guess, C and C++ have spoiled me...
Procedure Procname ();
VAR
BEGIN
END Procname;Basically modules are loaded dynamically and any procedure that obeys to a specific signature could be called from the UI, via keyboard and mouse like the ACME editor on Plan 9.
The way they get their input, depends on the signature.
It could be like command line parameters, clipboard, or any selected UI element in another application.
Then again, we would probably have typescript, coffeescript, etc.. version of Oberon to solve this.
https://github.com/MarcoDelphiBooks/ObjectPascalHandbook/blo...
[0]: https://people.inf.ethz.ch/wirth/Oberon/Oberon07.Report.pdf
Does the layout of the letters matter in an argument against using the shift key?
There's Borland's ObjectPascal products, of course (from Turbo to Delphi), which were extremely successful for many years and still survive today. Pascal is nowhere as popular today as in its heyday, but there are people still using Delphi as well as Lazarus, a modern open-source Pascal implementation that's compatible with Delphi.
One of the most popular languages right now, Go, is heavily influenced by Modula and Oberon. Go is more complex, and opts for a more C-like syntax, but many of its concepts come directly from those languages. Another nascent language with a heavy ObjectPascal influence is Nim (which was created by a former ObjectPascaler).
Ada is another Pascal dialect that is far from dead.
Granted, I personally wouldn't want to use these languages today. Go and Nim are taking the programming language evolution further. But this article isn't about using Oberon today.
A more C-like syntax, with a more Pascal-like semantics, might actually be a reasonable sweet spot. (I think the C syntax won for a reason. It's terser, without being so terse it's unreadable, and therefore gives you higher bandwidth. Most peoples' complaints about C are the semantics, not the syntax - though I'm sure at least some people dislike that too...)
From the 1983 Ada reference manual [1]:
Another significant simplification of the design work
resulted from earlier experience acquired by several
successful Pascal derivatives developed with similar
goals. These are the languages Euclid, Lis, Mesa,
Modula, and Sue. Many of the key ideas and syntactic
forms developed in these languages have counterparts
in Ada. Several existing languages such as Algol 68
and Simula, and also recent research languages such
as Alphard and Clu, influenced this language in
several respects, although to a lesser degree than
did the Pascal family.
Ada was widely considered as being an evolution of Pascal at the time (e.g. [2]).[1] http://archive.adaic.com/standards/83lrm/html/lrm-01-03.html
[2] https://academic.oup.com/comjnl/article-pdf/25/2/248/1080494...
Worth having a look at.
Nice one, actually :) The main thing people do with jewels is look at them (apart from keeping them as a store of value).
> But ever since Pascal, the language aspect has been almost secondary to Wirth's work. Modula(-2) and Oberon both came out of larger system-level design projects that simultaneously also developed workstation computers, modular operating systems, and suites of innovative application programs. Unfortunately, these other important contributions were overshadowed by the programming languages they were associated with, and hence never received the recognition they deserved.
Oberon was both a programming language and an operating system implemented in that programming language. Much like LISP machines, the boundary between programming language and operating system is fuzzy.
Cobol postdates Algol so it doesn't make sense to see it as the source of the keyword-based syntax of the Algol and Algol derived languages.
Pascal is very much alive:
https://www.tiobe.com/tiobe-index/
Above Ruby, GO, Perl, Visual Basic, Swift and more.
http://www.astrobe.com/default.htm
MikroElektronika, selling Pascal and Basic compilers for all sort of microcontrollers and embedded platforms also since 1997.
Embarcadero is still selling Delphi.
The keywords are not much more clunky than SQL ones, and no one is required to write them as such, unless they enjoy using editors without auto-formatting capabilities.
Wirth-ian languages is about languages as engineering. They're precise and pragmatic - e.g. constructs were stripped out if Wirth did not feel he could translate them into assembly in a compact and simple and easily understandable manner; he put restrictions on adding improvements to the compiler that didn't "pay for themselves" etc. The entire toolchains and systems and languages he worked on is focused on this.
Dead as a dodo? You need to check your facts. For instance, the FreePascal mailing list is very much alive and well. People are using it to make and ship real projects and products. Not as many, maybe, in volume, compared to the most widely used languages such as Java, C#, C, JavaScript, etc., but definitely not a trivial number (anecdotal, based on what I've read, and seen on the mailing list).
Heck, even Delphi, which is a descendant of Pascal, is still going somewhat strong, with many users, despite wrong turns taken by Borland and others who owned it at different times. And there is also Lazarus, a sort of free clone of Delphi, based on Free Pascal with GUI support, IDE and libraries added.
As plenty of others have said here in the past, this board (HN) is representative of just a drop in the ocean compared to the amount of business software activity going on in the world. So you can't draw valid conclusions from what you read here, except for this microcosm.
And usually good s/w engineering principles were not the predominant factor in the inception of these systems anyway. They were commercially motivated, and hobbyist beginnings. And once you already have a big body of code...
For a more batteries included, see the Component Pascal dialect with Blackbox:
http://blackboxframework.org/index.php?cID=home,en-us
It had some uptake in Russia and embedded. Still a really, niche player for sure but it did. Also, Astrobe has an Oberon IDE and platform for embedded.
Finally, the most industrial one with longest time would be Free Pascal with Lazarus since it's sort of a Delphi port.
IDE training, native libraries available, and ease of integrating C libraries are all I would be concerned about if just trying to crank out features. They'll certainly pick up the language(s) with no trouble at all.
I'd take this moment to point out that while there existed _some_ Objective-C programmers in 2007, approximately 99% of the current Objective-C programmers in the world (by my wild speculation) learned this bizarre SmallTalky language just to make iOS apps.
- Put some cool code riddles on the company website that lots of hackers will like so that they will discuss them on Hacker News.
- Pay a more than sufficient salary.
> I believe that Wirth’s ultimate impact will be felt even stronger ten years from now than it is today, and that the legacy of his accomplished career devoted to The Art of Simplicity will be enduring.
Unfortunately I don't see any sign of that. The actual trend seems to be in the opposite direction.
"the one and only system that almost all members of the Institute for Computer Systems (including the secretary!) used on a daily basis for all their computing tasks"
Even the fonts were designed in-house.
"They taught us stuff like Oberon? Why not Java or C? I want to get a job later!"
Having properly understood the fundamentals, languages like Java and C can be picked up rather quickly.
Problem is, many tech jobs in Germany require an degree.
In those days BYTE used to have very good and interesting article about all kinds of both hardware and software topics, and not only mainstream (at the time) ones either. E.g. there was an issue dedicated to Lisp and another one dedicated to Smalltalk, IIRC. Later it got more commercialized, with less good content, shorter and less in-depth articles, and more ads.
Some old BYTE articles or issues are there on the Internet Archive.
https://archive.org/details/byte-magazine?&sort=-date&page=2
Just had a quick look for now; here are a Lisp and a Smalltalk issue:
https://archive.org/details/byte-magazine-1979-08
https://archive.org/details/byte-magazine-1981-08
, for anyone interested.
Occasionally feel like I should be typing `TButton = record`.
Not that surprising I guess since Anders Hejlsberg wrote Turbo Pascal, much of Delphi, was the lead dev on C# and TypeScript.
He's made a career out of writing productive environments for mortal developers.
I still think Pascal was my favourite language, the old joke back then was "Pascal has one way to do everything, the right way" compared to the expressiveness of a lot of languages.
The unsafe package kind of resembles SYSTEM, just that Oberon spec leaves it open the possibility to have Assembly intrisics in SYSTEM, given its goal as systems programming language.
Plan 9 is very much influenced by Oberon, and the Acme text editor in particular.
Web developers are even lower on the totem pole.
Is that supposed to be an insult?
[0] https://en.wikipedia.org/wiki/Charles_H._Moore
edit: Golang rulez!
Burroughs, nowadays sold by Unysis as ClearCase, was developed in 1961 using ESPOL, later improved and renamed as NEWP. Both Algol variants.
IBM research on RISC was done with PL/8, a PL/I variant, later used for writing IBM z firmware.
IBM i (OS/400) was initially written in PL/S, another PL/I variant.
Intel used PL/M extensively.
Xerox PARC moved from BCPL into Mesa, where Wirth got his inspiration for Modula-2, followed by Mesa/Cedar, which again influenced Wirth to create Oberon.
Mesa/Cedar designers went to DEC Olivetti, where they ended up designing Modula-2+ and Modula-3.
Apple started with Assembly and Object Pascal, only moving to C++ with PowerPlant due to market pressure.
During the early 80's C was just yet another systems language only available in expensive UNIX workstations. On home computers, on CP/M we only had dialects like Small-C, competing against everything else for attention.