Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Implement a programming language in 7 lines

matt.might.net

Post reply on HN
Print view View original

11–18 of 18 posts

Re: Implement a programming language in 7 lines

#11

Post by agumonkey »

duaneb wrote: post #6
nickpsecurity wrote: post #2

This one is a cheat because read does a lot of the work. I can tolerate treating STDIN/OUT as black boxes because they often are. The Scheme interpreter's functionality is what's custom. The read function is crucial to it. So, it's implementation should be included. That puts this way over 7 lines. The good news is that I now know where the name Y Combinator comes from. I imagine it will take me a lot longer to wrap…

I do recommend learning the Y Combinator; it's the answer to the problem "How do I have a recursive anonymous function?"

Beside the theoretical side of Y, what made it interesting to me was the few tutorials on how one could derive it to stop an infinite expansion, which is a feeling I often get when trying to solve a problem, creates another similar problem only slightly different. Now I stop and try to find how to make bind the tail to the dog's mouth.

Re: Implement a programming language in 7 lines

#12

Post by segmondy »

Implementing a programming language in a few lines has always been done.

Here is an example in prolog of such a meta interpreter.

    interpret(true):- !.
    interpret(GoalA, GoalB):- !,interpret(GoalA),interpret(GoalB).
    interpret(Goal):- clause(Goal, Body), interpret(Body).

Re: Implement a programming language in 7 lines

#13

Post by segmondy »

nickpsecurity wrote: post #7
jerf wrote: post #4

Earlier quoted context omitted.

Eh, "implement X in Y lines" for Y < 10 is pretty much always a cheat. At least this cheat has solid computer science behind it; most such cheats boil down to "import library; library.cheat()", or, for the particular "implement a programming language", JavaScript "eval".

Nah, there's those that are cheats and those that are solid work. Here's a LISP in 500 lines of C I just found that doesn't seem to cheat: https://gist.github.com/sanxiyn/523967 It was one of many from the link below. The Scheme in Racket example would've been even easier to specify concretely because it's so easy to implement read in a Scheme. Gets the C and C++ implementations more props for doing things directly.…

A better lisp, in prolog in 160 lines. http://www.metalevel.at/lisprolog/lisprolog.html

Re: Implement a programming language in 7 lines

#14

Post by [deleted] »

nickpsecurity wrote: post #7
jerf wrote: post #4

Earlier quoted context omitted.

Eh, "implement X in Y lines" for Y < 10 is pretty much always a cheat. At least this cheat has solid computer science behind it; most such cheats boil down to "import library; library.cheat()", or, for the particular "implement a programming language", JavaScript "eval".

Nah, there's those that are cheats and those that are solid work. Here's a LISP in 500 lines of C I just found that doesn't seem to cheat: https://gist.github.com/sanxiyn/523967 It was one of many from the link below. The Scheme in Racket example would've been even easier to specify concretely because it's so easy to implement read in a Scheme. Gets the C and C++ implementations more props for doing things directly.…

[deleted]

Re: Implement a programming language in 7 lines

#15

Post by jerf »

segmondy wrote: post #13
nickpsecurity wrote: post #7

Earlier quoted context omitted.

Nah, there's those that are cheats and those that are solid work. Here's a LISP in 500 lines of C I just found that doesn't seem to cheat: https://gist.github.com/sanxiyn/523967 It was one of many from the link below. The Scheme in Racket example would've been even easier to specify concretely because it's so easy to implement read in a Scheme. Gets the C and C++ implementations more props for doing things directly.…

A better lisp, in prolog in 160 lines. http://www.metalevel.at/lisprolog/lisprolog.html

cough It would seem to me that both 500 and 160 are substantially larger than 10.

Re: Implement a programming language in 7 lines

#16

Post by nickpsecurity »

jerf wrote: post #15
segmondy wrote: post #13

Earlier quoted context omitted.

A better lisp, in prolog in 160 lines. http://www.metalevel.at/lisprolog/lisprolog.html

cough It would seem to me that both 500 and 160 are substantially larger than 10.

Reminds me of the tale of the two programmers arguing. One says "Mine actually works right." The other retorts, "But mine runs faster!" The first merely sighs.

Building almost nothing and using a very, high-level language definitely helps keep line count low. I wonder if we should count the runtime in these very-HLL examples. One like PreScheme, a system variant, I'd probably not count the runtime although might count the running time. :)

Re: Implement a programming language in 7 lines

#17

Post by nickpsecurity »

segmondy wrote: post #13
nickpsecurity wrote: post #7

Earlier quoted context omitted.

Nah, there's those that are cheats and those that are solid work. Here's a LISP in 500 lines of C I just found that doesn't seem to cheat: https://gist.github.com/sanxiyn/523967 It was one of many from the link below. The Scheme in Racket example would've been even easier to specify concretely because it's so easy to implement read in a Scheme. Gets the C and C++ implementations more props for doing things directly.…

A better lisp, in prolog in 160 lines. http://www.metalevel.at/lisprolog/lisprolog.html

That's a trip. Reminds me of when I studied and toyed with AI programs. The first books I learned taught LISP, Prolog, and mixing the two. We'd normally implement Prolog in LISP. Allegro still does. Neat to see it done the other way.

Want a fun project? Run this one through a Prolog compiler and create some LISP benchmarks. Then, recode it in the Mercury language, which IIRC is No 1 logic language, then see how that code performs (and looks). Should be straight-forward and enlightening for those interested in logic programming.

Re: Implement a programming language in 7 lines

#18

Post by nickpsecurity »

duaneb wrote: post #6
nickpsecurity wrote: post #2

This one is a cheat because read does a lot of the work. I can tolerate treating STDIN/OUT as black boxes because they often are. The Scheme interpreter's functionality is what's custom. The read function is crucial to it. So, it's implementation should be included. That puts this way over 7 lines. The good news is that I now know where the name Y Combinator comes from. I imagine it will take me a lot longer to wrap…

I do recommend learning the Y Combinator; it's the answer to the problem "How do I have a recursive anonymous function?"

The brief description I saw and sltkr's comment look like gibberish to me. Not enough math or FP background I guess. I think learning it is probably going to be part of a larger, mind-altering effort for me when I eventually dig deep into FP to understand it. Lambda calculus, too, while I'm at it.
Post reply on HN