Hacker News Reader

> In chapter 4, you write your own Lisp interpreter. If they had chosen C++, would you be writing a C++ compiler? Or a Lisp interpreter in C++? Either way, it would be ugly.

It's an interpreter for a small subset of Scheme, but Scheme is of course itself small and simple†, which means that it's not hard to mentally extrapolate from the small subset to the rest of the language. C++ is a large language, and so it would be less compelling to implement a small subset of it. And you could of course use C++ to implement Lisp, as you say; chapter 4 actually covers several programming paradigms quite alien to Scheme itself, so implementing a functional programming language in C++ would be quite reasonable. As I read it, the main point of chapter 4 is that it's not true that "Most languages give you some abstractions, and others simply can't be built." Metacircularity makes chapter 4 very effective at convincing you that what you've written is actually a real programming language, but it has confused you into missing (what I read as) the main point of the chapter. Perhaps it was counterproductive.

If not, though, it would be quite reasonable to achieve the same pedagogical metacircularity in Lua, Prolog, Forth, ML, Smalltalk, GHC Core, my own Bicicleta, or any number of other small, simple languages. I don't know about you, but those languages feel very different (from Lisp and from one another) to me.

† "Simple" here refers, for better or for worse, to the observed behavior of the language, not the difficulty of its implementation. Much of this is easy to gloss over in a metacircular interpreter, where you can inherit garbage collection, procedure call semantics, dynamic typing, threading, call/cc, and even parsing, lazy evaluation, and deterministic evaluation order, from the host language. (The book points out many of these points.) If you were going to design a language at Scheme's programming level with an eye to making the implementation as simple as possible, Scheme would not be that language.

>>> It's an interpreter for a small subset of Scheme, but Scheme is of course itself small and simple†, which means that it's not hard to mentally extrapolate from the small subset to the rest of the language. C++ is a large language, and so it would be less compelling to implement a small subset of it

Exactly. This is the point of Lisp. I think many languages are over complicated for no good reason.

① Yes, in a sense, this is the point of "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I." But Lisp is a much larger and more diverse phenomenon than McCarthy's 1960 paper. For example, Common Lisp is not small and simple, although it is not as complicated as C++, and it's still part of "Lisp".

② Regardless of whether it is or is not the point of _Lisp_, it is not really the point of _SICP_, which is about different approaches to structuring programs. One of them is the Lisp approach.

Even though it doesn't look like it, I could've sworn Prolog was homoiconic.

Smalltalk can also do a lot of the cool lisp wizardry. I know Alan Kay (a user on here who was on the team that designed Smalltalk at Xerox-PARC) likes both langs. I've never heard him describe what he thinks are the pros and cons of both though.

You can write a lisp in a few lines of Forth. I've never done it, but people talk about it a lot, so I'm going to assume fact.

> You can write a lisp in a few lines of Forth.

Seems unlikely. Forth isn't garbage collected, is untyped, etc etc. So you'd have to add those things in "a few lines".

Though I guess it depends what you mean by "a few". I was thinking a couple of dozen. Looks like someone's done it in 500 (though without GC -- is that still Lisp?): https://forums.parallax.com/discussion/160027/lisp-technical...

Not all Lisps had GC in the early days.

There were some mainframe implementations that would just allocate until there was no more memory left.

In addition to not technically needing a GC, a simple GC can be small if you don't care (much) about performance. One variation over a basic tricolor mark and sweep using linked lists for each "color" is basically (ruby-ish pseudocode):

  # At this point all objects are in the "white" set. We don't know if they're reachable (in which case they're garbage)

  # Mark roots
  push_registers_to_stack
  stack.each {|ob| grey.append(ob) } # You need to do this to any other roots as well, e.g. any pointers from bss.

  # Iteratively scan every object, moving unscanned objects into the "grey" set (reachable but unscanned)
  grey.each  {|ob|
    ob.referenced_objects.each {|ref| grey.append(ref) }
    # "ob" has now been scanned, so moving it into the black set (reachable *and* scanned)
    grey.delete(ob)
    black.append(ob)
  } 
  # What remains in the "white" set is now the garbage, so free it. You can also, if you want, move this aside and free it lazily.
  white.each {|ob| ob.free }
  white = black

A "real" implementation of the above can be done in <100 lines in many languages. Doing efficient gc gets more complex very quickly, though.

The mruby gc is a good place to see a more realistic tricolor mark and sweep that is also incremental and also includes a generational collection mode. It's about 1830 lines of verbose and well commented C including about 300 lines of test cases and a Ruby extension to interact with it. A simpler one like the above could certainly be much smaller even in C.

Ruby-ish pseudo code is somewhat remote from working Forth.

It's remote in that it looks very different, but not in terms of complexity. The operations used in the pseudo code are basically just.

- Pushing registers onto the stack

- Iterating over the stack

- Appending to a linked list

- Popping the first entry off a linked list

- Iterating over a linked list

- Calling a function/method ("free") to release the memory. In it's most naive form this would mean appending it to a linked list of free memory.

The two first requires dipping into assembler in a lot of languages. The rest will be tiny in most languages, including Forth, but my Forth knowledge is very rudimentary hence why I didn't try.

This is actually a random side project of mine! https://github.com/tgvaughan/scheme.forth.jl

I always have problems with the definition of homoiconicism...

Prolog code is represented the same way as data, but (AFAIK) there is no functionality for manipulating code at run-time or interpretation-time. I believe allowing macros is a necessary condition for homoiconicism, if I'm right, then Prolog isn't it.

No, I think just code is data is code right?

Also, I'm not sure macros are needed for a language which doesn't do compilation.

> there is no functionality for manipulating code at run-time or interpretation-time

Sure there is: http://www.swi-prolog.org/pldoc/man?section=manipterm

Example:

    ?- foo(Bar, Baz) =.. List.
    List = [foo, Bar, Baz].

And:

    ?- F =.. [foo, Bar, Baz].
    F = foo(Bar, Baz).

You can do all that with term-rewriting in Prolog, you can use a grammar to parse a file of arbitrary text and transform it into prolog terms to be executed etc

McCarthy himself said, "Pure Lisp was a discovery, everything that has been done with it since has been an invention." He said this to a class at Stanford in 2008, reported in HN! [1]

[1] https://news.ycombinator.com/item?id=185348

Chuck Moore always says he did not invent FORTH, but discovered it.

It's fascinating the relationship between Lisp and Forth. I am quite sure there is something about these two old simple languages and the concept of duality in mathematics that we are missing.

You're not the only one to observe this. It was observed and explored by Manfred von Thun with Joy, a purely functional programming language based on Forth. Modern "concatenative" languages continue this tradition:

https://en.wikipedia.org/wiki/Concatenative_programming_lang...

I've been working with Joy for a few years now and I have to say that it seems to me to combine the best parts of Forth and Lisp.

It's ridiculously elegant.

Do you have a link to whatever project you are working on? I'm interested in Joy but not aware of anyone working on or with it in recent decades.

Sure! I developed an interpreter for Joy in Continuation-Passing Style in Python: http://joypy.osdn.io/

I had just implemented type inference[1] when I got smashed over the brain by Prolog. So now the Python code is in limbo because the Prolog implementation of Joy is blindingly elegant[2].

In Prolog, the Joy interpreter is also the Joy type inferencer.[2]

The compiler (from Joy expressions to new Prolog rules) is five lines long.[2]

[1] http://joypy.osdn.io/notebooks/Types.html

[2] https://osdn.net/projects/joypy/scm/hg/Joypy/blobs/tip/thun/...

Thanks!

Yes, there's a real connection between concatinative languages and logic languages. In some sense you can think of a concatinative logic language as Joy with the ability to push "unknown" values onto the stack, as well as a few constraint manipulatives. That's somewhat orthogonal, but it makes sense an interpreter for Joy would be quite compact in prolog.

Thanks for the links, I'll review your work later!

Cheers!

You might also like: http://conal.net/papers/compiling-to-categories/

He transforms Haskell to a point-free form that's suspiciously like Joy... ;-)

> It's fascinating the relationship between Lisp and Forth.

Is there more to the relationship than "Lisp is written as a preorder tree, and Forth is written as a postorder tree"?

Short answer: no.

Longer answer: actually another common feature is that both can execute code at compile-time (macros).

Full answer: really, no. They are fundamentally different: Lisp is a decent symbolic language, Forth is a decent portable assembler.

Really, no. They are fundamentally identical executable lambda calculus, despite Lisp's attempts to look abstract by shrouding itself in parentheses and Forth's attempts to look like "portable assembler" by exposing most implementation details.

There is an ancestral relationship. Chuck Moore studied under McCarthy directly.

Yep. And back in the 1970's Chuck Moore wrote a book describing the implementation and design of FORTH, and it is pretty close to LISP. And I asked Chuck Moore directly, in person, if there was a connection to LISP, and he said "yes".

They are both very different, technically, but culturally they are very similar. Both of them are extremely simple and build complex programs from a few fundamental principles. Both of them are disengaged from the more mainstream languages. Both of them broaden your perspectives as a programmer. Both of them have excellent books that were written a long time ago but are still relevant today. Both of them gave rise to specialized hardware (stack computers and Lisp machines). Both of them encourage you to write your own interpreter when you are learning them... Although both languages are very different, learning one or the other actually is a quite similar experience.

Forth is actually disengaged from mainstream languages; Lisp being disengaged from mainstream languages is just a meme believed by some non-Lisp programmers (something to do with those parentheses). Basic Lisp is very similar to mainstream languages in the Algol family. Lisp dialects usually have nested block structure, with local variables that can be assigned, functions with formal parameters with ordinary by-value argument passing and so on. Javascript is a mainstream language and has strong ties to Lisp, much more so than to Forth. Python is more closely related to Lisp than to Forth. C is more closely related to Lisp than to Forth. Java is more closely related to Lisp than to Forth ....

Forth isn't written as a tree; the tree structure in the evaluation/compilation comes from the semantics of the words (how many elements of the value stack they consume).

In Lisp we know that (eql 1 2 3) is a "too many arguments" error. It doesn't just take 1 2 from the stack, push back the answer, and leave 3 beneath it.

Lisps are actually fairly conventional block-structured languages, having more in common with Pascal than with Forth. Lexical scopes, local variables, function calls with arguments going to formal parameters and all that.

> In Lisp we know that (eql 1 2 3) is a "too many arguments" error. It doesn't just take 1 2 from the stack, push back the answer, and leave 3 beneath it.

That error also comes from the semantics. You can't tell that (eql 1 2 3) is a too-many-arguments error just by looking at the tokens. That could be a 3-ary function, or an "eql is not a function" error.

The parentheses in Lisp code certainly suggest a particular tree structure, but they don't require it by virtue of their graphical form. And once you're willing to look up the arity of functions, Forth is written directly in its own tree structure to exactly the same degree that Lisp is, just with structural markers elided.

Think about it another way: a classmate in compilers class asked me once how Lisp handled operator precedence. Obviously, with the tree structure of the code fully specified, Lisp doesn't handle operator precedence because the question can't arise.

Note that this is just as true of Forth.

We can tell that 3 arguments are being applied to eql from that expression; when this is compiled, the generated call will pass 3 arguments, regardless of whether eql likes that, or whether such a function even exists. In the absence of any static checks, it will have to be caught at run time; but it will be caught.

Also, Lisp supports variadic functions with the same safety. Delimitation of arguments is necessary for variadic functions, like list.

The structure of every top-level form is an actual tree object in memory that is constructed before anything else happens. It can be walked by macros, or quoted so that the program accesses it as data directly.

Basically, nothing like Forth.

> Delimitation of arguments is necessary for variadic functions, like list.

This is not the case; you can easily have a Forth word that consumes however many arguments as are on the stack.

Ah, but the argument was made that Forth code has an implicit tree structure based on looking up the arity of functions, in place of explicit delimitation with parentheses. How can that be if some function takes N arguments, where N is, say, a run-time value, itself on the stack.

Starting Forth by Leo Brodie is a classic book. Forth is a very elegant language. I came across a javascript implementation of it recently, which you can look up yourself :)

As a kid I went from basic to assembly. When I was shown Forth by my dad's friend I was totally caught up in Forth on my C64. I later tried Pascal which is also great but it wasn't close to forth in my mind. It was awesome Except you had to pay for the language and I am guessing that is why it died.

Currently my preferred language is Racket because it is so fun and practical, reminds me of the earlier days of Python but much more thought out. You write you code (which is fun) and you have an executable all within one setting.

Armed with that and a copy of Threaded Interpretive Languages by Loeliger (How I found out about the book is beyond me) from the library I managed to put together a complete(ish) Forth for the Apple ][ running ProDOS.

I think the magic bit with Forth is that it's easy to see how to write one by the time you've finished Starting Forth.

Is it though? Man, maybe I'm dumb :)

I wish there was an easy checklist: Create stack data structure, create return stack, create primitives ...etc.

https://factorcode.org/

What does Factor have to do with my question? Yes it's a concatenative language that is still maintained although Slava left. I'm guessing it wouldn't make a great example if you're suggesting going through source.

And it seems to be free for personal use: https://www.forth.com/starting-forth/

When I read SICP, I worked through the exercises in Forth. I had to implement my own garbage collector, create dialect extensions for nice list notation, build a thunk-based mechanism for closure... with the right groundwork laid, Forth can keep up pretty well. I was always somewhat dissatisfied that cute metacircular lisp interpreters leave as tautologies so many important details of their own mechanics.

It functions as a good way to whet the appetite of the reader or student. SICP's meta-circular implementation occupies a kind of sweet spot, it imparts to students that only just grokked recursion to understand how the programming language itself is just a program they can understand and tinker with. The state machine implementation of the Scheme interpreter sort of breaks the meta-circularity to dismantle the tautologies.

How did you learn how to write your own Forth? Brodie shows how to just think in and use one already written right?

Jones Forth is an extremely readable tutorial how to write a Forth.

I've gone through it before, but it has been ages. Maybe I'll check again...thanks.

This resonates. I once sought to create a DSL on top of F# for workflows only to end up inventing lisp again. It was a humbling experience. The thing about lisp and why I dont use it in the workplace regularly is that it's dense and inconsistent. Dense because it's easy to write a profound amount of logic in one line which hurts readability if youre not careful. Inconsistent because you and I could be master programmers and write perfectly effective solutions that do the same thing and the code can look entirely different. This hurts interchangeability and it doesnt scale well, which disqualifies it from most enterprise projects. Similar to perl. That being said all my personal projects are done using clojure because it's such an easy/fun platform to work with

Regarding the discovery vs. invention question. It has indeed already been discussed within philosophy. Here are just two examples in philosophy of mathematics: https://philpapers.org/rec/DETDIA-3 https://philpapers.org/rec/FINMDO

Incidentally, I found building a Lisp interpreter in C++ using the SICP interpreter recipe a great exercise.

We had a follow-up course to SICP that started with the meta-circular interpreter, broke that one down even further and eventually moved completely to a C-implementation. Most insightful course I ever had. We got assignments such as: "add co-routines to the continuation-passing style meta-circular interpreter, and to the stack-based C interpreter."

>What?? In chapter 4, you write your own Lisp interpreter. If they had chosen C++, would you be writing a C++ compiler?

There was a site [0] that had SiCP exercises in various other languages.

[0]: https://web.archive.org/web/20100503233725/http://www.codepo...

> What?? In chapter 4, you write your own Lisp interpreter. If they had chosen C++, would you be writing a C++ compiler? Or a Lisp interpreter in C++?

That's in chapter 5 :)

Exercise 5.51. Develop a rudimentary implementation of Scheme in C (or some other low-level language of your choice) by translating the explicit-control evaluator of section 5.4 into C. In order to run this code you will need to also provide appropriate storage-allocation routines and other run-time support.

Ha, well I guess my secret's out - I skipped some of the exercises! And I'm not surprised to see I skipped that one. Even now, 5.51 and 5.52 seem like they would be more hard than fun. But given that SICP is my favorite CS book, maybe I owe it to myself to go for 100% completion.

> I can't imagine SICP using a language that doesn't feel a lot like Lisp.

SICP's main value proposition is not a language but developing thinking in terms of creating abstractions through compositions. LISP like language certainly helps but most modern languages does have this ability although verbose and possibly subjectively ugly in many cases.

SICP with Python: https://wizardforcel.gitbooks.io/sicp-in-python/content/

SICP with JavaScript: https://www.comp.nus.edu.sg/~cs1101s/sicp/

"epistemology or a similar field has pondered the "invented or discovered" question already, and if so, I want to read about it."

Yep. Me too. In fact, request for essay! It sounds like a topic I'd love to read pg meander into, for example.

I think anytime invention starts to seem like a discovery, it's probably a good invention.

I'm not sure there is a fundamental difference between the two. If you strain hard enough and get precise enough with your definitions, you could probably describe any invention as a discovery and the reverse. Recursively, that probably means any such definitions are inventions rather than discoveries.

It's discussed briefly [0] in Dirk Gently.

[0] https://www.goodreads.com/quotes/488211-sir-isaac-newton-ren...

> I'm guessing epistemology or a similar field has pondered the "invented or discovered" question already, and if so, I want to read about it.

Any course or book on the Philosophy Of Science would cover that. Are numbers discovered or invented? Did the ancient hindu mathematician invent the number zero or did he discover it? You could argue that the symbolic representation of zero was invented ( or was it? ) but the idea of the number zero was discovered. The more you delve into it, the more you realize things aren't as straightforward as you might have imagined.

Or quicksort. Is it an invention or a discovery? You could go back and forth on it forever.