GOPHERSPACE.DE - P H O X Y
gophering on hngopher.com
HN Gopher Feed (2017-11-26) - page 1 of 10
 
___________________________________________________________________
Lisp in fewer than 200 lines of C
196 points by jfo
https://carld.github.io/2017/06/20/lisp-in-less-than-200-lines-o...
0-lines-of-c.html
___________________________________________________________________
 
[deleted]
 
piinbinary - 3 hours ago
After reading Peter Norvig's post about a lisp implementation [0],
I decided to write one in Python.I got something working in 65
lines [1][0] http://norvig.com/lispy.html[1]
https://gist.github.com/jmikkola/b7c6c644dff1c07891c698f0a52...
 
raphlinus - 1 hours ago
See also Ben Lynn's implementation[1] in about 100 lines of
Haskell. Admittedly it's not a totally fair comparison because it's
relying on Haskell's runtime, but it's still an excellent
demonstration of Haskell's power and expressiveness compared with a
lower level language.[1]:
https://crypto.stanford.edu/~blynn/lambda/lisp.html
 
  vog - 46 minutes ago
  To be fair, it is not just that Haskell is a "high-level
  language", but that it is a language in the ML family of
  languages. ML means "Meta Language" and was specifically designed
  to be used to implement (other) languages.
 
krat0sprakhar - 4 hours ago
Really cool! A more complete implementation in 1000 lines of C for
getting started: http://www.buildyourownlisp.com
 
akashakya - 2 hours ago
If you like this, you might like Lisp interpreter written in
assembly in a single file. It is one of the best commented code
ever written imo.https://github.com/marcpaq/arpilisp
 
  sparkie - 31 minutes ago
  Another small lisp implementation:
  http://piumarta.com/software/lysp/Also, another, more interesting
  Lisp by the same author: (http://piumarta.com/software/maru/).
  Maru is basically a lisp where some of the core functions like
  eval and apply are extensible from user code. There's basically a
  global map of types to evaluators and applicators, with some
  functions for you to register your own types and get the
  evaluation behavior you want.
 
Areading314 - 3 hours ago
This is more of historical interest than of technological
interest...
 
  ColinWright - 2 hours ago
  I think you are mistaken.  There is much to learn from
  implementations such as this, and the techniques used form the
  basis of much more complex systems.  The technology remains very
  relevant.FWIW, I didn't downvote you, as I don't downvote someone
  simply because I believe they're wrong, or because I disagree
  with them.
 
    sparkie - 26 minutes ago
    While I agree that it's not just historical interest - there's
    still much that can be learned from Lisp - this implementation
    is certainly not the place to learn it. There's no garbage
    collection, which is really the biggest concern of a proper
    lisp implementation in a language like C. Without GC, it's a
    gimmick implementation. There's no practical use for it.
 
      ColinWright - 17 minutes ago
      There is much to be learned from incomplete, toy
      implementations.  Not least, the interested reader can see if
      they can extend the existing implementation to include the
      missing features.Insisting that learners/students should only
      ever read and study complete, perfect implementations is, I
      think, a mistake.  I've learned a great deal from studying,
      and subsequently improving and extending, implementations
      that are imperfect and incomplete.
 
asveikau - 4 hours ago
No calls to free() to match calloc(), no overflow checking in
gettoken() and then I read this:> a program with missing or
unmatched parenthesis, unresolved symbols, etc will likely just
result in something like a segmentation fault.I understand this is
just a fun thing to hack on, but this is an irresponsible way to
write software. I hope no one here is reading this and thinking
it's how they should be writing C.
 
  [deleted]
 
  fsloth - 3 hours ago
  "but this is an irresponsible way to write software"Segfault is a
  totally safe way to terminate a process on a modern desktop os.
  Besides - there is no 'correct' way to write software.
 
    asveikau - 3 hours ago
    Sorry, this is wrong. A segfault means you got lucky and your
    bad memory access hit an unmapped or otherwise invalid page.
    Other times the program will keep running with incorrect
    results. Many such issues represent exploitable bugs.In any
    case it's a bad issue and should not be a normal failure mode
    for a syntax error.
 
      fsloth - 3 hours ago
       "Other times the program will keep running with incorrect
      results. Many such issues represent exploitable bugs."None of
      which matter if it's a prototype, running on a developers
      machine.If you want memory safety you run the program through
      valgrind anyway with a large input dataset. And write unit
      tests. And integration tests. And so on.The baggage of
      production quality software development environment is so
      high it easily stifles the joy of quick and dirty
      prototypes.The main use of prototype is to facilitate
      understanding. This is the most critical constraint, whose
      needs drive over anything else.Besides, who on earth is going
      to exploit a few hundreds of lines of code a developer runs
      on his or her own machine?
 
        asveikau - 3 hours ago
        I don't know if you noticed this but C hackers are a
        minority on here. Thus it's not unreasonable to think
        people get an impression of how C is done from submissions
        here. We owe it to the craft to serve as good examples.
        It's not as burdensome as you suggest.
 
          fsloth - 2 hours ago
          I see your point, but respectfully disagree that an
          incomplete implementation should stop a submitter from
          sharing his or her discoveries. This is an aesthetic
          position - I think interesting ideas are more important
          than clean implementations (It is left as an exercise to
          the reader... is an ok position, IMO).
 
      agumonkey - 3 hours ago
      I think people were referring to the free-free approach where
      you just quit a short lived program without deallocating
      anything.
 
  ac2u - 3 hours ago
  The author isn't responsible if people read it and think it's how
  they should be writing C, especially when the objective of
  writing lisp in as little C as possible is communicated.So why is
  it fair to label it irresponsible?
 
    chii - 3 hours ago
    it's not irresponsible, but copy/paste proliferation does
    exist, and happens surprisingly often with code posted online
    like this. When you write code for posting online, you'd want
    to consider this problem.
 
      sillysaurus3 - 3 hours ago
      If you have to worry about the entire world whenever you do
      anything, you'll never get anything done.
 
    DSMan195276 - 3 hours ago
    I would add that there is already hundreds of implementations
    of Lisp in C and hundreds of little tutorials that are
    extremely similar to this online anyway, it's not like one more
    is going to make a difference.Yes, his C code could be a lot
    better, but at the end of the day it really doesn't matter and
    nobody is going to be using this for anything important.
 
    asveikau - 3 hours ago
    > The author isn't responsible if people read it and think it's
    how they should be writing C,Seems we disagree on the basic
    premise then. If someone learns the wrong thing based on my
    example I view myself as responsible. (I have not been a
    perfect example all the time either. We owe it to ourselves and
    others to always improve on that front.)
 
  DonaldFisk - 3 hours ago
  It's a lot longer if it's done properly.   You should use an
  array of dotted pairs to store your list elements, out of which
  you build a free list, from which you allocate by calling cons.
  To garbage collect, you mark all objects in use (on the stack, or
  accessible from the symbol table) and then you add the unmarked
  conses to the free list.   You should not be using malloc or
  calloc at all, certainly not to implement cons.Below is some of
  the relevant code in C/C++ from the virtual machine of Emblem
  (the Lisp dialect I'm using to implement inter alia my visual
  dataflow language, Full Metal Jacket).   To keep things short I
  haven't included initialization or the garbage collector.
  cons_op takes the top two stack entries (one on the stack, the
  other in tos), conses them, and returns it in
  tos.-------------------    typedef struct ListStruct {
  void *head;         void *tail;     } *List;      static struct
  ListStruct consTable[NUM_CONSES];      static List freeStore;
  #define hd(X) (((List)(X))->head)     #define tl(X)
  (((List)(X))->tail)     #define NIL (void *)&consTable[0]
  #define null(X) ((X) == NIL)      static void **stack;     static
  void *tos; /* Top of stack register. */     static long sp;
  static void cons_op()     {         List x;          if
  (null(freeStore)) { cons_gc(); }         x = freeStore;
  freeStore = (List)tl(freeStore);         hd(x) = stack[sp++];
  tl(x) = tos;         tos = x;     }
  ----------------------Alternatively, instead of C you could use a
  garbage collected language such as Java, C#, or Go, and then not
  have to worry about memory management.
 
  ythn - 4 hours ago
  If people always wrote software responsibly we'd have a great
  deal fewer interesting projects on GitHub
 
    tree_of_item - 4 hours ago
    Would it really be so hard to do this exact same thing in a
    memory safe language? Would that stifle the author's creativity
    in any way?
 
      wyager - 3 hours ago
      Writing Lisp in 200 lines of Haskell wouldn?t be nearly as
      interesting. The whole point is (presumably) that it?s fun to
      code golf in C because it?s not very expressive. Relax, no
      one is going to use the OP?s code to run a pacemaker.
 
      macintux - 3 hours ago
      People often do what they love with the tools they love.
      Complaining that someone wrote a hobby project with C is akin
      to complaining that your neighbor made a decorative baseball
      bat with her lathe instead of a 3D printer.
 
BMorearty - 1 hours ago
That's fun. Here's Jisp, my Lisp implementation in a tiny bit of
JavaScript. It supports declaring functions, interop with
JavaScript, quoting a list, variable arg lists, and more:
http://www.ducklet.com/jisp/.
 
sago - 2 hours ago
Writing your own Lisp-ette is a brilliant evening or weekend
project, regardless of the language. It's some of the simplest non-
toy parsing you can attempt, a bit of light data structure work,
and understanding eval/apply is 80% of the work in implementing it.
I would highly recommend anyone to have a go, and try not to follow
existing code too closely: figure out the problems in your language
of choice.The post identifies some of it's own weaknesses (memory
handling, errors), which are quite C specific. Or at least easier
to handle in other languages, where you can punt those issues to
the host language runtime. But it will be a fun extension to fix
them (a job for the second evening / weekend of coding ;) )But,
imho, the beauty of writing a Lisp is that there are a bunch of
things you can do from there, some more difficult, but several are
achievable step-by-step in a day or a few days each. I'd first add
a few special forms more than the OP (quote, if, progn, math
operations), then my suggestions:1. Defining names (if you haven't
already), both let and define special forms.2. Lambdas.3. Tail call
optimisation (I suggest this not because it's an optimisation, this
Lisp doesn't need optimising, but because TCO is a bite-sized
extension.)4. Lexical scoping of lambdas.5. Continuations.
call/cc6. And if you're really brave (or skilled, or just
masochistic), macros.I was encouraged to do this as a new grad
student, and it was one of the most fun and educational experiences
I remember. I didn't get as far as macros back then, but
implementing call/cc was a definite pivot point in my programming
competence.
 
  DonaldFisk - 1 hours ago
  I found none of these particularly difficult.   (I've never
  attempted 3. or 5. though.)   Functional values, however, are
  difficult.   They work effortlessly in interpreted code, but in
  compiled code you're faced with the upwards funarg problem:
  https://en.wikipedia.org/wiki/Funarg_problem#Upwards_funarg_...A
  solution is needed if you want lazy evaluation.
 
    sago - 1 hours ago
    How did you do lambdas and lexical scoping without 'functional
    values'?
 
      theoh - 1 hours ago
      Presumably by implementing only the simpler "downwards"
      funargs: the ability to pass functions into a function scope
      but never return them.
 
      DonaldFisk - 1 hours ago
      That's explained in https://en.wikipedia.org/wiki/Funarg_prob
      lem#Downwards_funar...In addition to return address and
      dynamic link, you need to store a static link in each stack
      frame.
 
    aarongolliver - 45 minutes ago
    5 is do-able by an undergrad, though the first time you
    encounter the concept it can be difficult to grapple how you
    would implement it.
 
  ioddly - 25 minutes ago
  > Writing your own Lisp-ette is a brilliant evening or weekend
  project, regardless of the language.Just be careful about scope
  creep. I started one as a weekend project five years ago and I'm
  still not finished ;)
 
  roywiggins - 1 hours ago
  Another fun one is a Forth interpreter. I tried to make one in
  Rust once, I can't say I actually succeeded but it's fun to
  tinker with. It is simple enough that you can probably write a
  bad one in assembly without that much assembly knowledge.
 
  tree_of_item - 2 hours ago
  If you go with (hygenic) fexprs instead of macros, they're both
  easier to implement and more expressive, at the expense of
  performance.Check out John Shutt's thesis for more information on
  hygenic fexprs:
  https://web.wpi.edu/Pubs/ETD/Available/etd-090110-124904/unr...
 
    sago - 2 hours ago
    Thanks for the tip. If it wasn't the end of the weekend, I'd be
    tempted to break out emacs.
 
    sparkie - 8 minutes ago
    Here's a small implementation of Kernel in around 700 lines of
    Haskell
    [https://github.com/vito/hummus/tree/master/src/Hummus]. Note
    that it's not Kernel proper, as it uses delimited continuations
    instead of the guarded undelimited continuations in the Kernel
    report, plus there's a few other differences and some
    bugs.Anyone looking for a more complete implementation, check
    out klisp [http://klisp.org]. It's not 100%, but has some stuff
    not included in the Kernel report, some of it lifted from R6RS.
    The main thing it's missing which it desperately needs is an
    FFI.
 
[deleted]
 
  anonfunction - 3 hours ago
  Wrong thread?
 
    drdrey - 3 hours ago
    Look at "denisehilton"'s post history, it's all spam
 
  luckydata - 3 hours ago
  somebody's machine learning algorithms need better training.
 
[deleted]
 
lisper - 1 hours ago
Lisp with full lexical closures in ~100 lines of
Python:http://www.flownet.com/ron/lisp/l.pyThe interpreter itself
is 48 lines.
 
jstanley - 2 hours ago
While this is very cool, it has at least one buffer overflow
vulnerability. There is no bounds checking in gettoken().Also, the
talk about pointers being aligned to "8 bit boundaries" I think
means 8 byte boundaries. Memory is not bit-addressable (at least,
not in C, on anything popular).But I don't mean to detract from the
project! It is very cool nonetheless :)
 
SonOfLilit - 3 hours ago
If you like short interpreter implementations, you might like this:
http://code.jsoftware.com/wiki/Essays/Incunabulum
 
  tromp - 2 hours ago
  or this interpreter of a lazy lambda calculus based language in
  25 lines of (obfuscated) C:http://www.ioccc.org/2012/tromp/tromp.
  chttp://www.ioccc.org/2012/tromp/hint.html
 
  agumonkey - 3 hours ago
  I love how it demonstrates how recursion/loops and
  shape/dimension based programming can be both thin, fast and
  generic
 
[deleted]