Lisp implementation in sed | Hacker News Reader

Lisp implementation in sed

github.com

207 pointsinglesp60 comments

Ahahah. Awesome. There is even an 'awk' version: https://github.com/darius/awklisp

I wrote that, and I gotta say sed is a much crazier target.

More sed fun: http://aurelio.net/projects/sedsokoban/

Indeed. There are few wide-spread programming languages around any more that lack such things as, say, any form of arithmetic whatsoever.

sed has regular expressions. I think you could do some binary arithmetic fairly easily with regular expressions and find and replace...

Yep, that's pretty much how you have to do it. (If all you need is increment/decrement, though, you can actually do it pretty concisely with decimal-digit strings. Skipping the binary-to-decimal conversion greatly simplifies displaying numerical values.)

The GNU sed manual has examples like that at the end. It always seemed odd to show examples of things that are so awkward and inefficient. If they meant for sed to do those things, presumably they would have made commands for them.

> to show examples of things that are so awkward and inefficient

Yeah. As in, better done in awk. The opposite of awkward is sedward.

Kudos, there was also this one: http://www.cs.cmu.edu/afs/cs/Web/Groups/AI/lang/lisp/impl/aw... Possibly based on the same newsgroup post?

That one's a cooler hack because it runs in old awk, from before they supported user-defined functions. The whole read-eval-print composition is a straight-line series of loops, with the recursions unrolled into explicit stack manipulation. If you want to see how to write fairly readable code within those restrictions, it's instructive. It even has a cooler name. (I said so when bringing it up in my documentation.)

On the other hand, awklisp has some value as a readable Lisp interpreter in a lower-level but still reasonable language, in between the usual Lisp-in-Lisp and Lisp-in-C tutorials.

That's kind of funny, because awk is already a programming language.

Would someone mind giving a quick explanation of how this works? I have only used sed to replace text in files and directories. How do people write interpreters and game loops with this unix utility?

With difficulty.

I started playing with the idea of making a programming language out of sed at one point, but then I decided that, even if I succeeded, it would be a waste of time.

I didn't take into account Hacker News.

woah woah woah. we don't just throw around "waste of time" like that :)

I was wrong, obviously.

Becoming famous by wasting time is something to consider...

the sed language allows conditional jumps to labels. That makes it powerful enough to write programs in.

If you had to just write programs by running a series of sed substitution expressions to a file over and over, and not use conditionals... it might still be possible to program in. Much harder to think about, though.

sed is provably Turing complete: http://www.catonmat.net/blog/proof-that-sed-is-turing-comple... which means that it's effectively able to simulate any other Turing-complete language (provided enough processing power and memory).

> sed is provably Turing complete

This submission is in itself, an elegant proof that sed is Turing complete.

Wouldn't the opposite - stream editor (programmable) in Lisp - be more useful?

Well, if you count Emacs in batch mode, such a thing already exists.

Well, OK: I'm curious, can I use the sed to Perl utility, to then make a Lisp implementation in Perl?

Trying this myself, it returns an error:

    s2p: expression #1: extra characters after command (d)

Thankfully, I've never had the job of porting a sed script to Perl, so I'm not exactly sure what that's all about. The docs mention this error, but don't explain what it means,

http://perldoc.perl.org/s2p.html

Aaaaand, obviously Perl has CPAN, so there's really no need (except to be evil):

https://metacpan.org/pod/CljPerl

(there's a few, actually, because TIMTOWTDI!)

This is amazing. Just reading the code makes my head hurt, but you implemented a language with it.

Here, for example, is the implementation of `atom` (I think):

  /(atom /{
    /\[\S\+\]/{
      s/.*/[]/
      bpop_context
    }
    s/.*/t/
    bpop_context
  }

If this was (the only available) programming, I'd quit.

Kudos, I think, to the author. His pain tolerance exceeds mine by a vast amount.

> If this was (the only available) programming, I'd quit.

We started with nothing, remember? Just the bare metal. If this were the only available programming, I'd write an interpreter for a better language.

Never imagine that your current suite of tools is all there is.

It will be a challenge to make an interpreter for a better language faster than dead slow.

I would bet on a compiler for a better language instead. That way, only one person would have to wait ages and ages. I doubt the result would be fast, but it wouldn't be insanely, insanely, insanely slow, either.

I would much rather hand assemble machine code than program in sed. I imagine most people have a better understanding of how computer architecture works than how to do arithmetic and logic with sed.

The way you can nest conditions in sed, like /foo/ { /bar/x }, is pretty powerful, and I knew a good bit of sed before I realized you could do that. It's not readily obvious from the manual.

The author has won an IOCCC contest. This would have just pricked him a bit.

So I guess if all languages are eventually converging on Lisp, are all Lisps eventually converging on sed? Is sed the bottom turtle or are there more?

Now you have three problems.

Oh come on. They took an unreadable language and implemented a slightly less unreadable language in it. That's at least two problems and one solution.

To what, I don't know.

did I misinterpret or did you just call lisp "[nearly] unreadable"? all languages are unreadable for the uninitiated.

You didn't misinterpret.

i am not particularly gifted at computer science and especially not programming languages. by necessity, the only languages i know are JavaScript and lisp. so I am always surprised to hear lisp is "unreadable" as opposed to "unfamiliar".

I think that Lisp got a reputation for being unreadable because some Lisp programmers have the tendency to get too far into macros to extend the language, resulting in a language that other developers have not seen before.

My theory is that it has to do with not having any operators, except parentheses, and using exclusively prefix notation, where other languages allow infix for doing arithmetic. Also, in Scheme loops are usually recursion, which means they have no standard form and they are upside-down from usual (the loop condition and increment are near the bottom, where the recursive call is).

I like scheme to be honest, especially the racket style of preferring define over let. Combined with well chosen variable names, list comprehensions, pattern matching and optional square brackets, all but the trailing ))))) becomes not a problem.

I think that's pretty much a straw man. Where is all this terrible macro-laden Lisp code? Well, it's probably not totally made up, but you run into overcomplicated abstractions in every language.

Somehow it seems more likely that people are put off by the slightly "isolationist" culture of Lisp, or the historical clash between Lisp and Unix, or whatever, and then this "unreadable" idea is like a rationalization for not liking the language? This is just a hunch...

You could make all kinds of arguments for the difficulty and obscurity of Haskell, yet it's winning ground quite effectively. I think this basically started with the success of GHC and Cabal/Hackage in creating an infrastructure that's familiar and efficient.

The Lisp world always had good infrastructure engineering. The main compilers (SBCL, CMUCL, etc) are very impressive! But it takes a very intensive kind of community engagement nowadays to stay up to date.

I still think Lisp could have a renaissance. Maybe it's already going on with Clojure. And of course Emacs is quite strong.

The ideal of programming seems to be software architectures based on layers of coherent abstraction. That's very, um, abstract, and there are different ways to do it. With OO, you imagine objects cooperating in layers. With Haskell-like functional programming, you use a mathematical style of abstraction, trying to find theories and algebras that make sense and compose, building applications out of combinations of well-typed values, etc.

Paul Graham describes the Lisp style in his texts on Lisp. You can see it in Emacs's various DSLs (for defining customization parameters, for traversing buffers, etc). It encourages abstraction layers built so as to form mini-languages. So a library can easily provide custom syntactic forms. Instead of having a small number of syntactic forms (if, for, etc) and an expression language based on function application, Lisp is syntactically extensible.

Programming is not a solved problem! We still aren't really sure about how to design programs, how to create coherent abstraction layers. The Haskell approach is very interesting, but not totally fleshed out. People are still working out the best way to structure concurrent I/O pipelines with error handling, for example. I sort of lost my train of thought, but Lisp is very interesting!

It's not a straw man for me -- it's what I think of a lot of Lisp code.

I think it's really instructive to compare things written in the early days of Clojure to Clojure right now. Some times I just want to find the author of some code block, shake them, and yell "No! The only reader macros you are allowed to use are ', `, and #() !". Absolutely beautiful language, but way too easy to make unreadable.

I'm not justifying Lisp's reputation, I am trying to explain it. Whether Lisp's reputation is justified or not is immaterial to my comment. Personally, I believe that the reputation is not justified.

Basic Lisp is pretty readable. But, ironically, if you dump enough reader macros into your code it becomes very unreadable very quickly.

Most Lisp code I've seen is heavy on the reader macros.

I appreciate the fact that one reply to your comment it "yes, not enough macros", and the other is "indeed, too many macros".

Say what? Both replies are saying that macros can make it tough to read. (Though, personally, I don't have a problem with most macros -- just reader macros.)

One theory that people often bring up vis-a-vis readability of lisp is that people seem to have a harder time parsing symbols than words (so all the parens makes it harder to look through a file).

Compared to python or coffeescript, it feels like there's a lot less noise

Another theory is that there are far fewer symbols in Lisp than python or coffeewhatever, making it easier to read.

this is more of a "symbols per line" argument rather than "symbols in the language" argument.

    grade = (student) ->
      if student.excellentWork
        "A+"
      else if student.okayStuff
        if student.triedHard then "B" else "B-"
      else
        "C"

(from coffescript examples)

Imagine how many more symbols that would have in any lisp dialect

    (defun grade (student)
      (cond ((excellent-work student) :a+)
            ((okay-stuff     student) (if (tried-hard student) :b :b-))
            (t                        :c)))

Erlang, just for fun:

  grade(#student{work=Work, tried_hard=Tried}) -> grade1(Work, Tried).
  grade1(excellent_work, _) -> 'a+';
  grade1(okay_stuff, yes) -> b;
  grade1(okay_stuff, _) -> 'b-';
  grade1(_, _) -> c.

Edit: formatting.

Or, if we're going to go with Prolog-inspired syntax, then why not Prolog?

    grade(Student, Grade) :-
        worked(Student, Work), work_grade(Work, Student, Grade).
    work_grade('Excellent', _, 'A+').
    work_grade('Okay', Student, 'B') :- tried_hard(Student).
    work_grade('Okay', _, 'B-').
    work_grade(_, _, 'C').

I'm a bit rusty, and I don't have a Prolog interpreter to hand to test, so I might have got some syntax wrong.

I'm always amazed that I hardly ever program in Lisp and yet these short snippets are more readable than any other language.

Yes, I've never understood why

    dostuff(x)

is considered so much more readable than

    (dostuff x)

   ;; comparing with racket:

   (define (grade student)
     (cond 
      [(excellent-work student) "A+"]
      [(and (okay-stuff student) (tried-hard student)) "B"]
      [(okay-stuff student) "B-"]
      [else "C"]))

   ;; Or

   (require racket/match)

   (define (grade student)
     (match (map (lambda (fn) (fn student)) 
                 '(excellent-work okay-stuff tried-hard))
       [(list #t _ _)  "A+"]
       [(list _ #t #t) "B"]
       [(list _ #t _)  "B-"]
       [else           "C"]))

Clojure:

    (defn grade [student]
      (cond
        (excellent-work student)  "A+"
        (okay-stuff student)      (if (tried-hard student) "B" "B-")
        :else                     "C"))

Having a Lisp will make it a little easier to write the Javascript interpreter. Baby steps.

brace yourself for sed flappy bird

Oh, excellent. Once I have JS I'll be able to run Clojure code on it.

Reply on news.ycombinator.com