So what is this mysterious link between Lisp and OOP?
I was really hoping that this would talk about meta-object protocols, COLAs, and the equivalence of lambdas and objects.
The C++ code with an explicit release made me cringe. Why not just use std::shared_ptr, since you’re implementing reference counting. Ideally, your Element would be a smart pointer that either contained an inline integer value or a pointer to some real refcounted value. This is a C++ model of how most real Lisp implementations work.
Of course… I could have. But I did not. I did some experiments when I first discovered all these new structures such as unique_ptr or shared_ptr, and I must say I was not very impressed by their implementation efficiency.
Second, shared_ptr is quite heavy to use, and frankly as it is the case for many of these modern structures, pretty horrible to read…
std::shared_ptr p = std::make_shared();
Finally, release can be used in many ways:
- It can delete a object
- It can push the object back into a pool of reusable object
- It does nothing on constant values
It has the advantage of readability and simplicity, which is my main objective here. Using shared_ptr would completely muddy most of my code.
You don’t need to use the built in shared pointer type, which is generic and so not optimised for various cases, to write idiomatic and clean C++. You write a LispValue class that is a tagged union of either a pointer to some rich structure or an embedded value. Most Lisp implementations use tagging on the low bit, with modern CPUs and addressing modes it’s useful to use 0 to indicate an integer and 1 to indicate a pointer because the subtract 1 can be folded into other immediate offsets for field or vtable addressing. If the value is a pointer, the pointee exposes non-virtual refcount manipulation operations in the base class. Your value type calls these in its copy constructor and copy assignment operator. For move assignment or move construction, your value type simply transfers ownership and zeroes out the original. In its destructor, you drop the ref count. When the refcount reaches zero, it calls a virtual function which can call the destructor, put the object back into a pool, or do anything else.
Implemented like this, you have no virtual calls for refcount manipulation and so all of your refcount operations are inlined. All refcount operations are in a single place, so you can switch between atomic and non atomic ops depending on whether you want to support multiple threads. More importantly, it is now impossible by construction to have mismatched refcount operations. Any copy of the value object implicitly increments the refcount of the object that it refers to, any time one is dropped, it does the converse. Now you can store LipsValues in any C++ collection and have memory management just work.
I don’t use C++ collection. For instance, my List implementation is based on a template of my own, which is designed to make CDR as fast as possible.
Beside, if you think your solution would work better, you can implement it yourself and see if it brings any benefits compared to my own implementation. The code of LispE compiles on all platforms, you might be able to tweak the Element class itself, which contains the reference counter that is shared by all classes.
Combined Object-Lambda Architectures. They were fashionable for a whole about 20 years ago as VMs built around the equivalence of object models and lambdas as a way of building different object models (class vs prototype, single vs multiple inheritance, and so on) on the same core substrate. Most of what they could do is also expressive in CLOS.
As far as I know they’re part of the “Reinventing Computing” research from VPRI. Ian Piumarta is one of the researchers on this and has a series of languages: Coke, Jolt, Pepsi that relate to this
Good article! But with the caveat that tree-walking interpreters are the slowest type, so most “real” (practical) language implementations move to a bytecode representation, or else compile to native code or transpile to a faster language.
(I guess pure LISP interpreters are by necessity tree-walking. Or are there any that compile to bytecode?)
Common LISP actually compiles to a binary.
Compiling to bytecode does not ensure a faster interpreter, as demonstrated by Python. :-)
What make other approaches faster is very often the fact that some very efficient heuristics will detect recurrent patterns in the tree that will be collapsed into faster routines. Whatever your compiler you still have to run your execution tree in a way or another.
As a simple example, consider an expression in tree form like 1+2. It’s easy to move to a linearizes form suitable for a stack machine. You can write it in postfix notation as 1 2 +. Push 1, Push 2, Add.
I find the “S-Expressions enable macros” take fairly unconvincing. Parsing a language is generally not difficult (shoo, C++ and YAML), and working with an AST is just like any other data structure… Much of macro usage in Lisps also takes the “quasiquote and unquote” form which doesn’t depend on syntax (or “lack thereof”) nearly as much:
macro do-and-release (block, releaser) {
~{
let v = ,block;
if (v) {
(,releaser)(v);
}
}
}
Lisp macros are better! But not because of the syntax, but for other reasons:
Full-powered macros can be embedded right next to the code that uses them without ceremony: no code-generation, janky declarative macro system, or separate compilation unit required
Deep identification with the language: everyone uses them, all the tools support them well
Language is interpreted so the macros can just be interpreted, instead of needing a slow compilation process
The beauty of macros-as-s-exps though is that you don’t have to do anything special to walk through the passed expression and manipulate it. The Elixir macro page shows this example:
{:if, [],
[{:!, [], [true]},
[do: {{:., [],
[{:__aliases__,
[], [:IO]},
:puts]}, [], ["this should never be printed"]}]]}
As the example output from the macro:
defmacro macro_unless(clause, do: expression) do
quote do
if(!unquote(clause), do: unquote(expression))
end
end
When called like this:
Unless.macro_unless true, do: IO.puts "this should never be printed"
It explains that this is, in practice what the macro received as input:
macro_unless(true, [do: {{:., [], [{:__aliases__, [alias: false], [:IO]}, :puts]}, [], ["this should never be printed"]}])
Once you’re familiar with how it all works, there’s no issue. The beauty of the Lisp macros is that the data structure that your function gets to process is exactly the same as what is written in your code. Since the parse tree maps virtually 1:1 to the source representation, you don’t have to try to grok and manipulate an intermediate AST form; you get to play with it exactly the way it appears in the code.
I don’t get why new programmers bounce off parens. The view from my chair is they are the best thing about lisp and they make everything understandable.
I don’t really understand it, but I do acknowledge that it’s far easier to persuade programmers to try unfamiliar semantics in a new language than unfamiliar syntax. Java programmers find it easy to move to C++ than Objective-C, even though Objective-C is far more semantically similar to Java than C++ is. They’ll move to JavaScript even more easily, even though the object model is a totally different family of OOP.
I was really hoping that this would talk about meta-object protocols, COLAs, and the equivalence of lambdas and objects.
The C++ code with an explicit
releasemade me cringe. Why not just usestd::shared_ptr, since you’re implementing reference counting. Ideally, your Element would be a smart pointer that either contained an inline integer value or a pointer to some real refcounted value. This is a C++ model of how most real Lisp implementations work.Of course… I could have. But I did not. I did some experiments when I first discovered all these new structures such as unique_ptr or shared_ptr, and I must say I was not very impressed by their implementation efficiency.
Second, shared_ptr is quite heavy to use, and frankly as it is the case for many of these modern structures, pretty horrible to read…
Finally, release can be used in many ways:
It has the advantage of readability and simplicity, which is my main objective here. Using shared_ptr would completely muddy most of my code.
You don’t need to use the built in shared pointer type, which is generic and so not optimised for various cases, to write idiomatic and clean C++. You write a LispValue class that is a tagged union of either a pointer to some rich structure or an embedded value. Most Lisp implementations use tagging on the low bit, with modern CPUs and addressing modes it’s useful to use 0 to indicate an integer and 1 to indicate a pointer because the subtract 1 can be folded into other immediate offsets for field or vtable addressing. If the value is a pointer, the pointee exposes non-virtual refcount manipulation operations in the base class. Your value type calls these in its copy constructor and copy assignment operator. For move assignment or move construction, your value type simply transfers ownership and zeroes out the original. In its destructor, you drop the ref count. When the refcount reaches zero, it calls a virtual function which can call the destructor, put the object back into a pool, or do anything else.
Implemented like this, you have no virtual calls for refcount manipulation and so all of your refcount operations are inlined. All refcount operations are in a single place, so you can switch between atomic and non atomic ops depending on whether you want to support multiple threads. More importantly, it is now impossible by construction to have mismatched refcount operations. Any copy of the value object implicitly increments the refcount of the object that it refers to, any time one is dropped, it does the converse. Now you can store LipsValues in any C++ collection and have memory management just work.
I don’t use C++ collection. For instance, my List implementation is based on a template of my own, which is designed to make CDR as fast as possible. Beside, if you think your solution would work better, you can implement it yourself and see if it brings any benefits compared to my own implementation. The code of LispE compiles on all platforms, you might be able to tweak the Element class itself, which contains the reference counter that is shared by all classes.
What are “COLAs”? Internet searches for various flavors of “lisp cola” and “plt cola” yielded nothing.
Combined Object-Lambda Architectures. They were fashionable for a whole about 20 years ago as VMs built around the equivalence of object models and lambdas as a way of building different object models (class vs prototype, single vs multiple inheritance, and so on) on the same core substrate. Most of what they could do is also expressive in CLOS.
As far as I know they’re part of the “Reinventing Computing” research from VPRI. Ian Piumarta is one of the researchers on this and has a series of languages: Coke, Jolt, Pepsi that relate to this
Good article! But with the caveat that tree-walking interpreters are the slowest type, so most “real” (practical) language implementations move to a bytecode representation, or else compile to native code or transpile to a faster language.
(I guess pure LISP interpreters are by necessity tree-walking. Or are there any that compile to bytecode?)
Common LISP actually compiles to a binary.
Compiling to bytecode does not ensure a faster interpreter, as demonstrated by Python. :-)
What make other approaches faster is very often the fact that some very efficient heuristics will detect recurrent patterns in the tree that will be collapsed into faster routines. Whatever your compiler you still have to run your execution tree in a way or another.
Common Lisp is a language with several different implementations. Some of them compile to native code binaries and some don’t.
SBCL can produce native code?
yes, it does compile to native code
CLISP compiles to bytecode.
As a simple example, consider an expression in tree form like 1+2. It’s easy to move to a linearizes form suitable for a stack machine. You can write it in postfix notation as 1 2 +. Push 1, Push 2, Add.
I don’t know what “pure” means here. Here is
evalin a tiny interpreter/compiler, https://github.com/udem-dlteam/ribbit/blob/d0082a08df12efca921d37daf04d64fb4ad63b78/src/lib/max-tc.scm#L1078-L1079The paper, http://www.iro.umontreal.ca/~feeley/papers/YvonFeeleyVMIL21.pdf And previous discussions, https://lobste.rs/s/8vtuhs/small_portable_scheme_implementation
I find the “S-Expressions enable macros” take fairly unconvincing. Parsing a language is generally not difficult (shoo, C++ and YAML), and working with an AST is just like any other data structure… Much of macro usage in Lisps also takes the “quasiquote and unquote” form which doesn’t depend on syntax (or “lack thereof”) nearly as much:
v.s.
Lisp macros are better! But not because of the syntax, but for other reasons:
I’m both with you and not :).
Elixir is a great example of a language without s-expressions that handles macros quite beautifully. See: https://elixir-lang.org/getting-started/meta/macros.html
The beauty of macros-as-s-exps though is that you don’t have to do anything special to walk through the passed expression and manipulate it. The Elixir macro page shows this example:
As the example output from the macro:
When called like this:
It explains that this is, in practice what the macro received as input:
Once you’re familiar with how it all works, there’s no issue. The beauty of the Lisp macros is that the data structure that your function gets to process is exactly the same as what is written in your code. Since the parse tree maps virtually 1:1 to the source representation, you don’t have to try to grok and manipulate an intermediate AST form; you get to play with it exactly the way it appears in the code.
I don’t get why new programmers bounce off parens. The view from my chair is they are the best thing about lisp and they make everything understandable.
I’ve seen this funny remark somewhere:
(f x y)— too many parenthesesf x y— too academicf(x, y)— just rightI don’t really understand it, but I do acknowledge that it’s far easier to persuade programmers to try unfamiliar semantics in a new language than unfamiliar syntax. Java programmers find it easy to move to C++ than Objective-C, even though Objective-C is far more semantically similar to Java than C++ is. They’ll move to JavaScript even more easily, even though the object model is a totally different family of OOP.
Why
(lambda (x) x)and not something simpler likeid?