▲ 127 points
back
64 comments
"Like the border between two warring states, the boundary between language and program is drawn and redrawn, until eventually it comes to rest along the mountains and rivers, the natural frontiers of your problem".
I wish pg programmed even today and kept writing about it.
So how do you know that your low-level construct is on the path to where you want to be?
Quite often, you can see immediately that you need to represent X, that representing X requires foo() and bar(), and you can confidently make these things with a reasonable expectation of their usefulness. This already depends, however, on having done some sort of preliminary high-level design thinking. How much you need to do to be confident that you can identify an efficient set of primitives depends on what you are trying to do and how familiar you are with its problems. Writing primitives and utilities can simply be a way to avoid tackling the difficult bits.
For a cautionary tale providing a counterpoint to this article, there is this somewhat well-known case involving writing a Sudoku solver:
http://ravimohan.blogspot.in/2007/04/learning-from-sudoku-so...
I find it's a valuable heuristic simply to try to make your code short (in tokens, of course, not characters).
That rule means that it's worth defining a new operator if you use it enough to save more than the amount of code you need to define it.
There are exceptions, of course. I have a higher standard for macros. But overall the principle of optimizing for brevity has held up through decades of programming of various types.
> I find it's a valuable heuristic simply to try to make your code short (in tokens, of course, not characters).
Make it short in characters as well.
Fitting more code on the screen makes it possible to see common subsequences and methods of abstraction not otherwise possible. It has dramatically improved my programming, and I recommend anyone who can to spend 6-8 months practicing it.
For more on the subject:
- https://news.ycombinator.com/item?id=13571159
I disagree. I recently read through Real World Haskell (http://book.realworldhaskell.org/read/ though it seems down right now?) as a refresher, and it devotes a lot of time to examples of the form "here is a three-line function, but aargh, it is too long, let's turn it into a two-line function by peppering it with <$> and <*> and <@!^!@> operators!". The savings in code size is small, but in every single case I found their "shorter", "simpler" program harder to read.
I suspect that's a pedagogical device to motivate introducing a style that can make code shorter and more readable, not a prescription to always convert three lines to two by using sigils.
The best way I know is to delay introducing the new abstraction until you have enough material to justify it. This means tolerating more repetition than you want the program to have in the long run, but only temporarily, while you build up a repertoire of cases that can eventually be abstracted away. You wait for the code to tell you how it 'wants' to become shorter, rather than trying to decide the primitives in advance. It's still just a bet that an abstraction will prove useful—i.e. will allow you to write future cases without thinking—and it still might not work out, but this puts the odds in your favor.
It works the other way around too: when an abstraction such as a Lisp macro turns out not to be a good fit, simply inline all its usages and delete the macro. This makes the program more repetitive, but only temporarily, while you wait to spot a different abstraction that fits the material better. This again is listening to how the code 'wants' to be: if you get resistance (increased complexity) while moving in a certain direction, backtrack.
I try to give every concrete case veto power over a new abstraction. That is, if I've got six cases of a pattern in my code, and five can nicely be shortened with a macro but one is stubborn and refuses, I tend not to write that macro. I used to, but have observed that such abstractions tend to need undoing later. Instead, I'll hold off, tolerate temporary bloat, and wait for more cases. Perhaps when there are nine or ten, I'll get a new idea for a language construct that can express all of them nicely, and then I'll add that construct in the way that pg describes. It's like the Tao Te Ching says: "If you want to shrink something, you must first allow it to expand" [1]. When you hit on a good way to compress code, it feels like a satisfying click [2].
With such an approach, the program seems to breathe: expanding a little and contracting a little, but never straying too far from simple overall. Lisps are the best medium I know of for this. You get finer and more immediate feedback from the material of the code: less is consumed by the noise of the language itself, so it can be adapted to fit the problem better. Your brain fills up more with the dance between problem and solution instead of the externalities of the tools. And you have a wider range of tools for actually working the adaptation. The result feels more like molding clay with your hands than carving bricks with a chisel.
1. http://taotechingme.com/chapter-36-if-you-want-to-shrink-som...
2. https://www.npr.org/2010/12/30/132488837/The-Behind-The-Scen...
There is an interesting parallel here between bottom-up programming and the common law system. Common-law courts don't create law in advance; they wait for conflicts to arise.
After enough similar conflicts arise and cases have been decided, an abstract "law" organically emerges that is used to decide future similar conflicts.
It's also kind of just like concept formation and theory building in science.
In algebraically or mathematically oriented communities like much of the Haskell world, you see a similar kind of "bottom-up programming" but with an added focus on compositional structures with laws for reasoning.
When a Haskell module really comes together beautifully, it's because you've managed to extract useful standalone concepts that combine in an algebraic way, with binary operators, associativity, and so on.
Eric Evans in Domain-Driven Design, usually considered a book about object orientation, also comes to a conclusion that if most of a program's logic can be expressed in pure functions and closed operations on value objects, then you can attain a "supple design."
I suppose the Lisp community has concepts like "value abstractions and syntactic abstractions" or something like that, one of them being related to well-suited data types, and the other being related to macros.
Incidentally, I've recently come to realize that Agda, the dependently-typed Haskell-style language, comes very close to being Lisp-like in its support for syntactic abstractions: you can go a long way with just custom mixfix operators (e.g., defining if_then_else_)... and then there's also a sophisticated macro system, using an AST data type and a "typechecker monad."
It's a lot of fun!
That reminds me of a blog post[0] I once read by Casey. It does a great job of capturing my thoughts on the subject: in short, that premature abstraction is evil and a productivity killer. Many programmers fall into the trap because of how tempting it is to try and make everything neat and tidy, despite the costs in programmer productivity, program performance, and code maintainability.
So how do you know that your low-level construct is on the path to where you want to be?
It's kind of growing the grass and let people walk on it, then decide where to put slabs on the paths.
Anyway I bet you are considering the cost of making changes. That cost is different for different languages.
It seems like what Paul is describing, is the niche filled by libraries/frameworks.
When you have a website to build, you reach for an existing web framework, because it has already done the bottom-up steps for you.
The same could be said of choosing a language, OS, hardware, etc.
Existing technologies allow for increased productivity, at the cost of it becoming increasingly difficult to understand the bigger picture. The 'bottom-up' part at this point, is choosing which Ruby/Java/Python/etc libraries to use. The productivity bar has been set high, leaving little time for bottom-up decision making or education. Hence MongoDB and the never-ending tales of mediocre solutions gaining adoption due to marketing hype.
Curiously enough - academia isn't able to solve this problem well, because they're encouraged to produce 'novelty', rather than sit down and digest the mess we're in, to help clarify matters a little. They're in the same rat-race, of getting things done on a 6-12 month schedule.
There's a quote that I really like - "Prolific programmers contribute to certain disaster." [0]
Ah well :)
> When you have a website to build, you reach for an existing web framework, because it has already done the bottom-up steps for you.
As I see it, it is from bottom to a greatest common denominator though. The tools you choose are not likely to have everything up to your "up", you still have to build your domain specific (but still abstract) "primitives".
Almost everyone should build their own framework on top of existing frameworks for their own domain. At work, we have a common look and feel for all our applications so that's build into the framework. We have specific domain specific data types -- those would never go into someone else's generic framework but they are in ours.
I find this idea of building your own framework to be pretty rare -- I do it because I've actually had to build frameworks for platforms that didn't have them -- but most programmers are content to use what they're given but never think of extending it.
I agree with you, the frameworks/libraries have done the bottom-up for you, to say, 70-80%. The other 20%, you need to work out on your own.
The final 20-30% are really marrying the exact business needs, with the underlying libraries/frameworks you're using.
The smaller the % of work needed to marry the business needs with the libraries, the more it starts to look like an application, like Photoshop, and less like programming.
> they're encouraged to produce 'novelty', rather than sit down and digest the mess we're in
How to live efficiently on the mess we are in is a perfectly good research area, one of the kind that severely improves the career of the researchers.
Frameworks are known to impose a top-down and previsible style.
Reading some of the replies that interpret pg's essay as talking about "libraries" or "frameworks" or "metaprogramming" doesn't look quite right to me.
I argue that instead of those 3, the most applicable terminology to map to pg's idea would be a "DSL" ("Domain Specific Language".)[1] The "DSL" terminology seemed to have gained currency around 2008 so this old 1993 essay wasn't able to use it. In any case, his point is to program Lisp in such a way as to build a "DSL" inside of Lisp and you then program your higher level concepts on that DSL. His key quotes:
>a principle which could be called bottom-up design-- changing the language to suit the problem. In Lisp, you don't just write your program down toward the language, you also build the language up toward your program.
>Instead of a single, monolithic program, you will get a larger language with more abstract operators, and a smaller program written in it.
One can also pursue the "DSL" concept with other programming languages. In C++, you can design the classes to be a "DSL". In fact, one of the derided features of C++ such as operator-overloading was motivated by allowing a custom "DSL" to integrate into the language better.
Lisp is an interesting programming language for writing an embedded DSL because the custom "mini language" you write looks like other builtin Lisp syntax.
Why the other proposed terms don't seem to fit:
- "metaprogramming" : this is usually describing programs generating other programs either at compile time (e.g. templates) or runtime (e.g. the eval() function in Javascript/Python)
- "libraries" : these are often non-domain-specific reusable code... such as a string library, matrix math library, or a TCPIP library
- "framework" : this is usually a source-code runtime (basically an application "loop") with customization points to call your custom code
PG's essay like many other programming essays suffers from misinterpretation because it doesn't include any explicit source code to illustrate the ideas. Therefore, writing in metaphors invites misunderstanding.
The whole point of Forth was that you didn't write programs in Forth you wrote vocabularies in Forth. When you devised an application you wrote a hundred words or so that discussed the application and you used those hundred words to write a one line definition to solve the application. It is not easy to find those hundred words, but they exist, they always exist.
-- Chuck Moore, 1x Forth (1999)
> currency around 2008 so this old 1993 essay wasn't able to use it
Embedding languages in Lisp is a concept since around 1962 (Daniel Bobrows METEOR Lisp extension for pattern based string processing). There are a bunch of Lisp articles written before 1980 which describe it and advocate using it.
> Lisp is an interesting programming language for writing an embedded DSL because the custom "mini language" you write looks like other builtin Lisp syntax.
Not really. Lisp is useful for DSL development because it provides the necessary extension features: which allows one to reuse a lot of the Lisp machinery (reader/parser, interpreter, compiler, macros, object-system, memory management, ...).
Common Lisp already comes with DSLs as part of the standard: format strings and LOOP are examples. They actually don't look like Lisp syntax - format strings are radically different and LOOP statements use more algol like syntax.
example for a FORMAT string:
CL-USER 2 > (format t
"~{~#[~;~a~;~a and ~a~:;~@{~a~#[~;, and ~:;, ~]~}~]~}"
(list 1 2 3 4 5))
1, 2, 3, 4, and 5
NIL
CL-USER 3 > (loop for i in '(1 324 2345 323 2 4 235 252)
when (oddp i)
do (print i)
and collect i into odd-numbers
and do (terpri)
else
collect i into even-numbers
finally
(return (values odd-numbers even-numbers)))
1
2345
323
235
(1 2345 323 235)
(324 2 4 252)
metaprogramming means to be able to program on the language level. It has not much to do with program generation. For example in Lisp you can program new syntactic constructs via macros. One can also program the 'reader' which allows one to program the token reader. There are various other ways to program at the language level - the most complex is the Meta-Object Protocol of CLOS, the Common Lisp Object System - which allows one to program the object system system itself in itself.
metaprogramming facilities are tools to develop DSLs.
>Embedding languages in Lisp is a concept since around 1962
You misunderstood what I wrote. I was talking about the terminology PG used, not the concept. PG couldn't time-travel to the future and write "DSL" in his 1993 essay so more readers would instantly understand what he was talking about.
> it provides the necessary extension features: which allows one to reuse a lot of the Lisp machinery
I agree. The "looks built in" is a characterization that some Lisp programmers (maybe not you) would call the ability to add "new syntax" to Lisp. It's a way of contrasting with something like C++. You can't "extend the C++ language" with new syntax for your custom project unless you fork the GCC or Clang compiler and add new keywords to the parser. All new so-called capabilities to embed a "DSL" has to be done as "functions()" with obvious parentheses to call it. Lisp ("code is data!") doesn't have this hard boundary.
>metaprogramming means to be able to program on the language level.
I agree. There's parsing/manipulating its own AST as a data structure but "metaprogramming" also has lot of currency usage to describe programs writing programs and the usage of dynamic eval().
It is from the introduction to On Lisp, and there is a great deal of explicit source code in that. A lot of which is in fact about domain-specific languages.
I feel that the C ABI is local maximum, with a massive associated opportunity cost. Imagine if all the operators that have been written, "bottom up", in one language could be easily accessible from others. And the only way to leverage that today is to go through the crusty, unsafe API that no-one really wants to export to unless it's required in the spec of a project.
Swift soon being able to call python is a massive step forward, but a lower level API that wouldn't require a runtime yet still was superior to C's feels like a massive win for the industry that's just waiting to happen.
>, but a lower level API that wouldn't require a runtime yet still was superior to C's feels like a massive win for the industry that's just waiting to happen.
A lower-level binary API was tried before in the 1990s by various players. Microsoft's effort was COM/COM+ to unify programming languages across binary boundaries.[1] Another initiative was CORBA.[2]
Those technologies are still alive in various legacy forms but they haven't taken over the landscape like the proponents thought they would. (Although the whole MS .NET ecosystem introduced in 2002 is arguably a continuation of COM+ by a different name.)
[1] https://en.wikipedia.org/wiki/Component_Object_Model
[2] https://en.wikipedia.org/wiki/Common_Object_Request_Broker_A...
I see what you mean that COM and Corba tried to unify programming across language boundaries. But they were not a low-level ABI type thing. They explicitly pushed a particular idea of what objects are and what they are for.
In any case, judged by the standard of becoming a universal ABI, they were also designed to "fail" in the sense that MS wasn't going too sit around and standardise it across operating systems, while the CORBA was a (feeble) response from the Unix world that no one expected would take off on Windows.
I think PG's ultimate point was about metaprogramming, which kind of turns your request on its head. Don't bother writing python bindings to the operators you wrote bottom up in lisp or forth: metaprogram in lisp or forth to give yourself the parts of python you find useful for the project.
Nothing stops a language runtime from creating a new ABI, and using it within the runtime.If it is much better than C and stable enough, people will adopt it. Compiler developers do not run away from that kind of project.
I'd say the problem is that nobody created anything that is much better and stable enough. That second one is a large problem on non-C languages.
Ive been recommending that, too. The better languages should use C's datatypes, calling conventions, have a seemless FFI, and generate C (at least optionally). This way, they can build on C's ecosystem instead of getting trampled by it. The C code can also be gradually rewritten.
On the LISP side, one might start with a combo of PreScheme with C compatibility, Rust-style memory management, and Racket-like DSL support. Maybe even embed it in DrRacket for tooling. Then, one can build up other Scheme-like features on top of it with an interpreted version.
So, that's an example of how to get the benefits of both.
You mean if Swift could call Rust instead?
On the practical front, this approach is tenable when programming for yourself or by yourself. How do you articulate this if you are consulting, your client isn't tuned to this thinking and want you to describe architectures and timelines? A statement like "I'll be working to create some primitives and based on what I see I'll choose to build or modify structures when appropriate." - doesn't fly. Though we might do that at the end of the day, I'm curious to hear here about what HNers think would be some good ways to talk about this process .. or not.
> How do you articulate this if you are consulting?
I don't.
How would you feel if your client concerns themselves with the colour choices in your text editor?
Our job is to learn their business problem and deliver a solution. We are the expert at that, not them, so we choose how we want to do it.
Btw Peter Nair's "programming as theory building" is the best description of this approach I know of.
Naur
I don't think bottom-up is a good way to describe the capabilities Lisp gives you.
You can go totally top-down in your design, which is the pattern I was encouraged to use by SICP ("wishful thinking" = top down). But Lisp doesn't make you stop when you reach the language level. "I wish my language would give me a concise way of saying whether variable x has the same value it had in the last iteration of this loop" is not a wish you can fulfill in a language without macros, for example.
Bottom up is also C and Unix:
It is the way I think. I am a very bottom-up thinker. If you give me the right kind of Tinker Toys, I can imagine the building. I can sit there and see primitives and recognize their power to build structures a half mile high, if only I had just one more to make it functionally complete. I can see those kinds of things. The converse is true, too, I think. I can’t— from the building—imagine the Tinker Toys. When I see a top-down description of a system or language that has infinite libraries described by layers and layers, all I just see is a morass. I can’t get a feel for it. I can’t understand how the pieces fit; I can’t understand something presented to me that’s very complex. Maybe I do what I do because if I built anything more complicated, I couldn’t understand it. I really must break it down into little pieces. - Ken Thompson, Unix and Beyond: An Interview with Ken Thompson, 1999
I've found a similar process by sketching up the domain logic, or typical steps of it, in as high level of pseudo-code as I can. Play around with it to try to optimize (factor) expressiveness. One then starts to see commonalities, and thus a domain-specific language(s) emerges. This language(s) may resemble or even become an API(s).
From a different direction, form a relational model, even if not using an RDBMS, to clarify the relationships between the domain parts.
Once you do both of these, then a bigger picture starts to form, and you refine it to have the API's work properly from the data relationship perspective.
> Few would dispute, at least, that high level languages are more powerful than machine language.
I would! =) How is power of language defined?
Level of abstractions, high-level vs low-level? Attractive language syntax (DSL/macro/syntax sugar)? Tools, support and libraries? Community traction, popular, paid-more? Optimized and effective code? Low entry-barrier?
Depending on definition on what powerful language is, winners might become losers and vice versa.
This.
Be a highlevel programmer: know enough languages to pick the right one for the task at hand. Do not take part in language wars.
bottom up programming is actually what a lot of jr developers do when starting out their careers and i would advise against it.
a top-down approach would be clean and simple and the complexities are hidden away from interface:
User.create(data)
whereas, a bottom-up would be look like you just hacked things on top of each other:
create_user( validate_user_data(format_user_data(data) ) )
but, i do know lisp kinda forces you to code that way, so pg's article may have a lot to do with that.
You can still do something like User.create(data) using a bottom up approach in designing the interface. If we had a module User, we could do something like (using Haskell syntax, since that's the functional language I know):
create = User (validate . format $ data)
Only the create function needs be exposed, but the useful bit is that the create function is built out of the composition of smaller functions which makes it easy to change or completely swap out a component of the whole process. A top-down User.create function would likely be a rather large, monolithic chunk of code.
Interesting that your two examples would be called: object-oriented ("top-down") and functional ("bottom-up").
After a lifetime of programming, I actually prefer the latter approach: composing functions that are without side effects and independently testable.
I'm not sure if your examples reflect the top-down/bottom-up concepts in the original article, and certain don't agree that "a lot of jr developers" prefer the bottom-up approach, or that it looks "hacked on top of each other". Maybe it's just personal preference..
Yeah, I second the preference for the latter approach. It encourages more reusable components - you get to use `format_user_data` in situations which don't require data validation, for example.
The one downside is the second style of code is a little uglier in languages without a good function composition operator, like Python. I enjoy writing stuff like
user = data
|> format_user_data
|> validate_user_data
Interesting, I got the exact opposite experience with junior developers. They often try to design a system top-down. Fail to do so well enough because they don't have enough experience from the bottom up.
Concur. Same experience. And I did the same mistakes when I was one of them junior devs too :)
It seems programming bottoms up is the only way to go - consider coding with your bottoms down, quite embarrassing.
His bottom up design sounds like the libraries and frameworks of today.
Need to sort a list? There's a sorting function in this library. Need to host a website? There's a framework over there for that.
The main takeaway seems to be the need to create utility level libraries for your own work that is specialized to your needs.
I believe the "bottom part" should be interchangeable, like switching to a different CPU architecture, or switching to a different framework. The bottom part is an implementation detail. The API is important since that's what you interact with.
I think it's best to have as few dependencies as possible, try to keep everything independent and interchangeable. I like to view my code as a graph structure, try to keep the functions and its dependent functions as a Directed-Acyclic-Graph and avoid cycles.
Beware, he was using the term "bottom up" in a meaning that diverges from current mainstream usage of the term: the bottom is the language, not the architecture.