Show HN: a Lisp that uses JSON instead of S-expressions (in .js) | Hacker News Reader

Show HN: a Lisp that uses JSON instead of S-expressions (in .js)

github.com

69 pointsjes519970 comments

I really like Lisp (I was even paid to develop in it for 6 years) and these days I love JSON because of its Lisp-ish nature - but those expressions look damn ugly to me.

You could lose the quotes around strings, but you'd still have the commas.

Maybe start with lisp and just add {key: value key2: value2} syntax for tables? It'd be useful to get ruby-style keyword args for free, at least.

I spend a lot of time thinking about keyword args because I've been working on a lisp interpreter that supports them. Here's a webserver that is nice to read because of a crucial keyword arg (it starts with a colon):

http://github.com/akkartik/wart/blob/460565a2e0/064http-serv...

Like in python the keyword arg is always optional. You could delete it from this definition and it would behave the same.

In conclusion: please try to include python-style keyword args in your next language. You never know when they'll come in handy.

What's wrong with Common Lisp's keyword arguments? I'm not being snarky, just asking. I'd say CL works at least as well as Python in this respect.

No, in Common Lisp you can't mix a keyword arg for a non-keyword param, or vice versa.

Couldn't you write a macro to call functions using whatever mixture of keyword and non-keyword params you wanted?

Or perhaps using some CLOS magic do to do this behind the scenes, e.g. no-applicable-method

http://www.lispworks.com/documentation/HyperSpec/Body/f_no_a...

[NB It's been a long time since I did much Lisp]

Yes, that's basically what my repo does. It started out as an attempt to build 'arc using macros atop Common Lisp' like the original critics claimed could be done. I pretty much succeeded (and I've been told it's very readable) except that I ended up with a lisp-2. (Lately I've been building it in naked C to get out of that constraint: http://github.com/akkartik/wart/tree/unstable)

I wasn't aware of no-applicable-method; thanks for that pointer.

You can do (&rest all-args &key keyword1 (keyword 2 default2)) and then try to figure out all-args in the function body.

How does Python handle mixing order of specifying keyword args positionally and with a keyword?

Python requires all args following a keyword arg to be keyword args:

  >>> def foo(a=0, b=1, c=2): return [a, b, c];
  ... 
  >>> foo(34)
  [34, 1, 2]
  >>> foo(b=34)
  [0, 34, 2]
  >>> foo(b=34, 35)
  File "<stdin>", line 1
  SyntaxError: non-keyword arg after keyword arg

I chose instead to simply bind args by position after keyword args have been taken:

  wart> (foo :b 34 35)
  (35 34 2)

Common Lisp already has hashtables (not to mention simple association lists) what it doesn't have is a standard syntax for them. However, this is pretty easy to add with reader macros, for example:

http://frank.kank.net/essays/hash.html

> Maybe start with lisp and just add {key: value key2: value2} syntax for tables? It'd be useful to get ruby-style keyword args for free, at least.

This is how Clojure hacks around keyword args, and altho destructuring kind of makes up for it, it's not that pretty. (It's not pretty in Ruby either) Hash table literals are a nice addition to Lisp but I think it's kind of ugly to use them for keyword args.

Ah, that's good to know, thanks.

I still think there's room for experimenting with a Lisp that has the hashmap (a.k.a. dictionary, associative array, property bag) as its organizing principle rather than the list. There's nothing better than hashmaps for exploratory programming. If there is something to be gained from building a Lisp in terms of them (from the ground up; I don't mean support for object literals), I'd like to know what it is. This has little to do with syntax.

You could argue that Javascript is a language with the hashmap as its central data structure. It doesn't have a macro system/quotations/other LISPy things, of course, but you can certainly frame your argument as "would JS benefit from <LISP feature>?"

Yes, JS certainly is that (or comes close), which is the thing I like the most about JS and miss the most in Lisp - so much so that I wrote macros to allow me to use JS-style objects wherever possible. (I don't mean JS-style OO, which I avoid at all costs. Hate "this" and "prototype", love "a.b" and "a[b]".) The benefit of the hashmap for exploratory programming is so great that it raises the question of whether a fully regular/metaprogrammable Lisp could be evolved from it. Not clear if it would be practical, or add anything of value, but if it did it would be interesting.

This presents a very thorny language design problem. Lists have this very nice property that they are ordered, which lets you attach implied semantics to the position of an element, e.g.:

(defun foo (a b c) ...)

We know this is a function defining because the symbol DEFUN is in the FIRST position of the list.

Associative arrays are unordered, so you have to explicitly label everything:

{ top-level-form : defun, arguments : { 1 : a, 2 : b, 3 : c }, ... }

Or something like that. You can see where that would get annoying.

Exercise for the reader: what happens if you base a Lisp-like language on vectors instead of cons cells?

Could you allow (a b c) as a synonym for { 0 a 1 b 2 c }? That's more or less how JS deals with this, though JS feels messy under the hood.

what happens if you base a Lisp-like language on vectors instead of cons cells?

I want to know that too! One thing is that you lose cons and cdr (except by copying the vector), so you lose the ability to do most of the classic Lisp things efficiently. You must have something in mind other than this?

> Could you allow (a b c) as a synonym for { 0 a 1 b 2 c }?

Yes, of course, but all you've done is re-invent vectors.

> you lose cdr (except by copying the rest of the vector)

Copying the rest of the vector is not semantically equivalent to CDR unless you are being purely functional. But you can actually implement CDR using displaced vectors.

> You must have something in mind other than this?

Could be :-)

Try writing EVAL for a vector-based Lisp and see what happens. In particular, when you're done, make a list of all the primitives you needed to employ in order to do it. There's a deep insight at the end of this process. (No, I'm not going to tell you what it is.)

Yes, of course, but all you've done is re-invent vectors.

True, but only as a device to keep the playing field open for any new benefits that might spring from universal hashmaps. What are they? I don't know, that's the question. Maybe there aren't any, but that itself would be interesting as a negative result (the L in Lisp is there for a reason).

What I'd really like to know is what would complete this sequence: list:Lisp, array:APL, stack:Forth, hashmap:?. That would be really interesting, no? And no one seems to be working on it, which is surprising given the ubiquity of hashmaps in modern languages (especially JS, but also Python, Lua, etc).

when I had a similar thought about hashmaps, I noticed that a hashmap is basically a function that takes one argument and returns a constant. And then I fell into a Turing tar pit about Church encoding. ... I'd love to try again, though.

> In particular, when you're done, make a list of all the primitives you needed to employ in order to do it. There's a deep insight at the end of this process. (No, I'm not going to tell you what it is.)

Having done this before (https://github.com/munificent/lark), all it meant for me was that numbers and basic integer arithmetic became primitive. The clever bit about McCarthy's original metacircular interpreter is that it didn't need any types at all beyond atoms and cons cells: no bools, no ints, no nothing.

I found it interesting, but I don't know if I reached any deep insight. Maybe that's just me, or maybe I missed something.

I suppose depth is in the eye of the beholder. That's pretty much it: to build a Lisp out of vectors you need numbers as primitives. To build a Lisp out of cons cells you don't.

Follow-up exercise: do you need numbers to build a Lisp out of associative arrays? (Hint: this is not a trivial question to answer.)

In Clojure an associative array auto-decomposes to a sequence of pairs when necessary.

Rereading McCarthy's paper yesterday I noticed for the first time that it didn't need numbers. But I hadn't connected all the dots yet.

I'll bite: cdr gets expensive? You could represent a list as a naked array of lisp pointers, but then cons gets expensive. And good luck garbage collecting the vectors.

> cdr gets expensive

Yes, that's one thing. But do you really need CDR?

> You could represent a list as a naked array of lisp pointers, but then cons gets expensive.

Actually, it's much worse than that. CONS actually becomes impossible. (Think about it.) But maybe there's something else that you can use instead of CONS?

> And good luck garbage collecting the vectors

Why would that be a problem? Extant Lisps collect vectors just fine.

"Extant Lisps collect vectors just fine."

But they don't permit pointers inside the vectors, do they? I think if you permit internal pointers so you can have copyless cdr, computing reachability would get really expensive.

The phrase "permit pointers inside the vectors" doesn't really make sense. Vectors are just ordered collections of objects. They don't have insides and outsides, except insofar as the objects contained by the vector could be (but usually aren't) considered "inside" the vector. Lisp vectors are usually implemented as arrays of pointers, so in that sense pointers are "permitted" inside vectors. But I'm guessing that's not what you meant. (I have no idea what you actually meant.)

  (a (b (c . nil))
  ^  ^
  |  |
  |  |
  A  B

If you implement lists as vectors with car/cdr (I'm still thinking about your other questions) and choose to have cdr not copy results out of the original cell, you can end up in the (rope-like) situation above with pointer B (value (b c)) in addition to pointer A (value (a b c)). But that makes GC inefficient. For a vector to be GC'd you have to know what internal pointers it has, and then you have to make the choice to copy them out if they're 'toward the end', or to leave the vector uncollected.

(ignore pointers to a, b, and c.)

Ah. What you are calling a "pointer to the inside of a vector" is actually called a displaced vector. It's a standard Common Lisp feature, and no problem for modern GCs.

Interesting! Thanks.

It does mean that you are potentially keeping around masses of data when you only care about one or two elements. Normally not an issue, but normally internal pointers ("displaced arrays") aren't a central organizational concept in a language.

The point of json, I think, is that you'd only use associative arrays when you need them.

Nobody seems to have mentioned the advantage of table literals: free syntax for ruby-style keyword arts.

  (defun foo (a b c))

could accept a map of variable names

  (foo {a: 1, b: 2, c: 3})

> Associative arrays are unordered

That's not true in general, is it? It's just hash maps that are unordered. You can use a tree to represent an associative array (so the order of keys is found by a tree traversal), or a "worse" method like an association list (linked list). You can also just store a linked list of keys along with your hash map.

You are conflating the abstract data type with its implementation. A hash-map is one implementation of an associative array. A tree is another implementation of an associative array. A tree happens to depend on an ordering of the keys in order to do efficient lookup and a hash-map doesn't, but this is an implementation detail. It's not part of the definition of an associative array. And this is a good thing because not all data types have well defined orderings but you still might want to use them as keys, with symbols being the most notable example.

I think the mistake the parent post has made is conflating the kind of ordering you're referring to -- ordering in a tree implementation to allow for O(log n) resolution -- and ordering to preserve the position of each key-value pair as it was in the source structure. These are only the same thing if the source structure already happens to be sorted by some kind of ordering, something that obviously cannot be extended to the general case of preserving positionality.

AFAIK, the only two ways to preserve positionality as part of an associative array are (1) to store as a postional list of key-value pairs and use linear search to find matching keys, or (2) to use an additional data structure as an index, either by storing as a positional list and having a additional map from key value into the positions, or by storing as a map and having an additional list of keys stored in positional ordering.

Or by having the map nodes have a "next" pointer.

Duh, I should have thought of that. Thank you.

Smalltalk requires explicit labeling of all but the first argument (though they are ordered) for keyword messages. Good naming conventions can make this enjoyable (at least subjectively).

In a hashmap based lisp, I'd expect defun to look something like

(define-function: (foo-with-a: a b: b c: c) with-body: ...)

Of course, since you're using an unordered representation, one could instead say (with-body: ... define-function: (c: c b: b foo-with-a: a)), which is significantly more confusing. This also means you probably can't do implicit progn.

progn in general will probably be unpleasant, unfortunately, unless one includes syntactic sugar for ordered sequences, which might defeat the purpose of an associative-array-based Lisp.

The first thing I've noticed about a vector-based Lisp is that you actually need primitive integers so that you can do indexing, which isn't the case with cons-cell based Lisps.

> Exercise for the reader: what happens if you base a Lisp-like language on vectors instead of cons cells?

I've been thinking about this in terms of a self-hosted Parenscript. What I see is a lot more pattern matching and map/reducing. Not altogether a bad thing.

Lua tables are a general-purpose associative structure that are used for both map and list functions in that language: there's syntactic sugar for both consecutive integer keys and simple string keys, and the former are used to make sequences (with internal, semantics-preserving optimizations in the Lua runtime for storing them). They strike me as one of the best options for a single core data structure if one were limited to one.

I haven't use Lua, but that sounds exactly like JavaScript objects. JavaScript does get on very well with basically just these objects.

They're similar, but the Lua form is much cleaner. In particular, JS objects only permit string keys, which makes Arrays sort of preposterous; they also have other baggage related to the prototype system. Lua tables can have any type except nil (which is not truly first-class in Lua) as keys, and can also have "metatables", which are of similar or greater power to the latter baggage but semantically somewhat simpler. To me this makes a world of difference.

How is this different than S-expressions? It seems equivalent modulo syntax.

"They are typically represented in text by parenthesized, whitespace-separated sequences" - S-expression, Wikipedia, emphasis added.

He should call them SMexp.

(Mexp used []..out)

Any new McCarthy LISP implementation is destined to provoke the programming equivalent of "git offa mah lawn!"

Get thee to the arc forum, where the six of us will provide good entertainment: http://arclanguage.org/item?id=15422

What is the purpose of the "quote" parameter? The only place it is in the code is here:

else if(x[0] == 'quote'){ return x[1];

So why not just skip that extra verbosity? What am I missing?

Quote prevents evaluation. If you didn't quote it, x[1] would get evaluated as code.

Does it use more JSON data types than arrays? The only examples are

  ["map", ....]

I don't see any `{ }`, etc.

Yes, it supports object literals as hashmaps. I'll try to add some more examples, soon.

There is only one other composite data type besides arrays: objects. I don't think these are being used for invoking functions, but I think it would be interesting to try.

Many people seem to confuse lisp's expressiveness with its syntax.

Syntax is just the beginning.

How you abuse it, to get things done is the more important thing. Please take time to explore this aspect more than those silly fracking parens.

I'm sorry, but I cannot get excited over Yet Another Implementation of McCarthy's LISP[1]. If your Lisp had _any_ interesting feature, e.g. call/cc, or object system, or nifty macro system, or something else, then, maybe, but doing the the same old, trivial thing, again and again, does not seem very interesting for me.

We don't usually see yet another Brainfuck interpreter, or yet another Fibonacci queue implementation on HN's front page, so why LISP?

[1] - http://lib.store.yahoo.net/lib/paulgraham/jmc.lisp

Because it's pretty straightforward - there's very little parsing involved (in this case basically none).

No, there's a lot of parsing happening. It's just that you're using (part of) the Javascript parser to do it.

I didn't claim it was revolutionary, I just keep hearing LISP hackers say "there's no reason to care about XML or JSON if you've got S-Expressions, which are so much cleaner"

This project is exercising (proving? refuting?) that claim. I recognize that this isn't the most ambitious project in the world, but it was a Thanksgiving-weekend hack.

I'm thrilled that it got the 20 votes necessary to get it on the front page of HN.

I vote for "prove". All those extra and unnecessary quotes and commas. Blech. And all that extra ugliness just so you can re-use the JS parser? IMHO there's no excuse for this. It's really easy to write a parser that does the Right Thing, e.g.:

http://www.flownet.com/ron/lisp/l.py

(cranky

You know, we have the upvote arrow for things that excite you, and the “Go read something else and comment on it” feature for things that don’t float your boat.

Clearly this is not spam and it is not off-topic. So:

You asked the OP and/or your fellow HNers why they upvoted this onto the front page. I ask you, why this comment, what value does it add to my life to read about how smart and educated you are?

What about all the people who haven’t seen an implementation of McCarthy’s Lisp? Do they not deserve to find this interesting? Should they turn in their HN accounts and head over to reddit?

I wrote an implementation of Scheme in Java with macros, tail call optimization, lambda hoisting, a bunch of stuff. Yet I find this interesting. Is there something wrong with me?

)

Raganwald, you pretentious douche:

> I wrote an implementation of Scheme in Java with macros, tail call optimization, lambda hoisting, a bunch of stuff.

Greenspun’s Tenth Law is widely accepted, demonstrations of it in action add nothing of value to the programming community. Furthermore, writing a Scheme in Java is likely to be a project where you learned nothing of interest about Lisp or about Java.

—signed, Nikolai Bourbaki

Misapplication? I thought the Law was meant to describe accidental implementations of Lisp rather than overt ones.

In other words, "the complicated system you made _just happens_ to contain a Lisp, and if you had noticed that requirement in the first place its design would have been cleaner."

I think you have captured the spirit of the law. The project in question was the development of a scripting language for something-or-other, so this wasn’t an accidental implementation of Lisp, it was done with malice aforethought.

That's kind of an inappropriate response. Pointing out one has implemented Scheme with all the bells and whistles as a condition in which the implementor is still interested in Lisp implementations and similar stuff is not a pretension or a statement that it was some kind of tremendous feat.

I have a motorcycle, but I'm still interested in not only other motorcycles, but also bicycles. I don't think this makes me a pretentious douche.

Maybe he meant that his Java implementation of Scheme contains an ad-hoc implementation of Lisp.

Wait.. why is raganwald replying to raganwald?

He’s meta-circularly tail-calling himself out.

I looked up Nicolai Bourbaki -- and then I got the joke :)

I think the "any interesting feature" in this case is the fact it uses JSON rather than s-expressions. This may not be a feature you think it needs, but it's interesting nonetheless.

It still uses S-expressions, albeit with different kind of parentheses and separators. The whole point of S-expressions is that syntax is irrelevant.

Reply on news.ycombinator.com