C interpreter in Lisp/scheme/python

Discussion in 'C Programming' started by bolega, Jun 14, 2010.

  1. bolega

    bolega Guest

    I am trying to compare LISP/Scheme/Python for their expressiveness.

    For this, I propose a vanilla C interpreter. I have seen a book which
    writes C interpreter in C.

    The criteria would be the small size and high readability of the code.

    Are there already answers anywhere ?

    How would a gury approach such a project ?

    Bolega
     
    bolega, Jun 14, 2010
    #1
    1. Advertisements

  2. bolega

    Vinay Guest

    you could read "scheme 9 from empty space". you can find it here
    http://www.t3x.org/
     
    Vinay, Jun 14, 2010
    #2
    1. Advertisements

  3. bolega

    Gene Guest

    Probably doesn't meet your intent, but this is a really impressive bit
    of (whacky) art:

    http://www.ioccc.org/1996/august.hint

    and find the code at

    http://www.ioccc.org/years-spoiler.html

    under 1996.
     
    Gene, Jun 14, 2010
    #3
  4. Take a look at this

    When I first got a summer job at MIT’s Project MAC almost 30 years
    ago, I was
    delighted to be able to work with the DEC PDP-10 computer, which was
    more fun
    to program in assembly language than any other computer, bar none,
    because of
    its rich yet tractable set of instructions for performing bit tests,
    bit masking, field
    manipulation, and operations on integers. Though the PDP-10 has not
    been manufactured
    for quite some years, there remains a thriving cult of enthusiasts who
    keep old PDP-10 hardware running and who run old PDP-10 software—
    entire
    operating systems and their applications—by using personal computers
    to simulate
    the PDP-10 instruction set. They even write new software; there is now
    at
    least one Web site whose pages are served up by a simulated PDP-10.
    (Come on,
    stop laughing—it’s no sillier than keeping antique cars running.)
    I also enjoyed, in that summer of 1972, reading a brand-new MIT
    research
    memo called HAKMEM, a bizarre and eclectic potpourri of technical
    trivia.1 The
    subject matter ranged from electrical circuits to number theory, but
    what intrigued
    me most was its small catalog of ingenious little programming tricks.
    Each such
    gem would typically describe some plausible yet unusual operation on
    integers or
    bit strings (such as counting the 1-bits in a word) that could easily
    be programmed
    using either a longish fixed sequence of machine instructions or a
    loop, and then
    show how the same thing might be done much more cleverly, using just
    four or
    three or two carefully chosen instructions whose interactions are not
    at all obvious
    until explained or fathomed. For me, devouring these little
    programming nuggets
    was like eating peanuts, or rather bonbons—I just couldn’t stop—and
    there was a
    certain richness to them, a certain intellectual depth, elegance, even
    poetry.
    “Surely,” I thought, “there must be more of these,” and indeed over
    the years I
    collected, and in some cases discovered, a few more. “There ought to
    be a book of
    them.”
    I was genuinely thrilled when I saw Hank Warren’s manuscript. He has
    systematically
    collected these little programming tricks, organized them
    thematically,
    and explained them clearly. While some of them may be described in
    terms of
    machine instructions, this is not a book only for assembly language
    programmers.
    The subject matter is basic structural relationships among integers
    and bit strings
    in a computer and efficient techniques for performing useful
    operations on them.

    These techniques are just as useful in the C or Java programming
    languages as
    they are in assembly language.
    Many books on algorithms and data structures teach complicated
    techniques
    for sorting and searching, for maintaining hash tables and binary
    trees, for dealing
    with records and pointers. They overlook what can be done with very
    tiny
    pieces of data—bits and arrays of bits. It is amazing what can be done
    with just
    binary addition and subtraction and maybe some bitwise operations; the
    fact that
    the carry chain allows a single bit to affect all the bits to its left
    makes addition a
    peculiarly powerful data manipulation operation in ways that are not
    widely
    appreciated.
    Yes, there ought to be a book about these techniques. Now it is in
    your hands,
    and it’s terrific. If you write optimizing compilers or high-
    performance code, you
    must read this book. You otherwise might not use this bag of tricks
    every single
    day—but if you find yourself stuck in some situation where you
    apparently need
    to loop over the bits in a word, or to perform some operation on
    integers and it just
    seems harder to code than it ought, or you really need the inner loop
    of some integer
    or bit-fiddly computation to run twice as fast, then this is the place
    to look. Or
    maybe you’ll just find yourself reading it straight through out of
    sheer pleasure.

    source
    http://www.hackersdelight.org./foreword.pdf

    =======
    Standard Disclaimer, nothing personal







    Hey Racist and INcompetent FBI Bustards, where is the ANTHRAX Mailer ?
    Where are the 4 blackboxes ? Where are the Pentagon Videos ? Why did
    you release the 5 dancing Israelis compromising the whole 911
    investigation ? If the Dubai Police can catch Mossad Murderers and put
    the videos and Iranian Police can why cant you put the Pentagon
    Videos ? If Iran police can put the AMERICAN TERRORIST, Riggi and
    puting on INTERNATIONAL MEDIA a day after catching him without
    TORTURE, why cant you put the INNOCENT patsies on the MEDIA. Why did
    you have to LIE about Dr Afiya Siddiqui and torture that Innocent
    little mother of 3 and smashing the skull of her one child ?




    There are CRIMINAL cases against CIA CRIMINAL Bustards in Italian
    courts.

    FBI bustards paid a penalty of $5.8 million to Steven Hatfill, but
    only because he was a white. They got away with MURDER of thousands of
    Non-whites in all parts of the world.

    Daily 911 news : http://911blogger.com

    http://www.youtube.com/watch?v=tRfhUezbKLw

    http://www.youtube.com/watch?v=x7kGZ3XPEm4

    http://www.youtube.com/watch?v=lX18zUp6WPY
     
    nanothermite911fbibustards, Jun 14, 2010
    #4
  5. Probably doesn't meet your intent, but this is a really impressive bit
    Lisp runs faster than C. Once you get more time away from screwing
    Palestinians, and other false-flags, you will find ideas like these

    How to make Lisp go faster than C
    Didier Verna
    Abstract
    Contrary to popular belief, Lisp code can be very ef-
    cient today: it can run as fast as equivalent C code
    or even faster in some cases. In this paper, we explain
    how to tune Lisp code for performance by introducing
    the proper type declarations, using the appropriate
    data structures and compiler information. We also
    explain how eciency is achieved by the compilers.
    These techniques are applied to simple image process-
    ing algorithms in order to demonstrate the announced
    performance on pixel access and arithmetic operations
    in both languages.

    =======
    Standard Disclaimer, nothing personal







    Hey Racist and INcompetent FBI Bustards, where is the ANTHRAX Mailer ?
    Where are the 4 blackboxes ? Where are the Pentagon Videos ? Why did
    you release the 5 dancing Israelis compromising the whole 911
    investigation ? If the Dubai Police can catch Mossad Murderers and put
    the videos and Iranian Police can why cant you put the Pentagon
    Videos ? If Iran police can put the AMERICAN TERRORIST, Riggi and
    puting on INTERNATIONAL MEDIA a day after catching him without
    TORTURE, why cant you put the INNOCENT patsies on the MEDIA. Why did
    you have to LIE about Dr Afiya Siddiqui and torture that Innocent
    little mother of 3 and smashing the skull of her one child ?




    There are CRIMINAL cases against CIA CRIMINAL Bustards in Italian
    courts.

    FBI bustards paid a penalty of $5.8 million to Steven Hatfill, but
    only because he was a white. They got away with MURDER of thousands of
    Non-whites in all parts of the world.

    Daily 911 news : http://911blogger.com

    http://www.youtube.com/watch?v=tRfhUezbKLw

    http://www.youtube.com/watch?v=x7kGZ3XPEm4

    http://www.youtube.com/watch?v=lX18zUp6WPY
     
    nanothermite911fbibustards, Jun 14, 2010
    #5
  6. He would have his 10 year LISP sink in, meditate for 10 days and
    start from scratch with a typical LISP approach.

    He would have his 10 year Algol68 sink in, meditate for 10 days and
    start from scratch with a typical Algol68 approach.
    (Scheme is not different enough from LISP, to make this interesting.
    Hey Scheme *is* a dialect of LISP.)

    He would have his 10 year Python sink in, meditate for 10 days and
    start from scratch with a typical Python approach.

    Maybe he would code "one to throw away".

    The outcome would be extremely interesting, but ...
    Groetjes Albert
     
    Albert van der Horst, Jun 14, 2010
    #6
  7. bolega

    fortunatus Guest

    Holy cow has this gone off topic! To OP - start writing a C context
    free grammar of a subset of C (arithmetic expressions IMHO are the
    historical root of C and a good place to start in any case), start
    writing a parser of a subset of your subset grammar (in a lisp of your
    chioce - Scheme and CL for instance are going to be pretty much
    equivalent in this task), and really the rest will be obvious...

    I'd go that far before posting on the topic again...
     
    fortunatus, Jun 14, 2010
    #7
  8. I propose a vanilla C interpreter.

    I think, only someone who hasn't written such a beast can put together
    "vanilla" and "C interpreter" together.


    Stefan
     
    Stefan Monnier, Jun 14, 2010
    #8
  9. bolega

    Tim Rentsch Guest

    Asking whether Lisp is faster than C is like asking why it's
    colder in the mountains than it is in the summer.
     
    Tim Rentsch, Jun 20, 2010
    #9
  10. bolega

    Define Macro Guest

    Maybe instead of full C, you should try something simplified, like
    Tiny-C (http://primepuzzle.com/tc/) or Arena, or maybe even Pike (some
    minimal variant thereof).
     
    Define Macro, Jun 21, 2010
    #10
  11. bolega

    Richard Bos Guest

    YM warmer.

    HTH; HAND.

    Richard
     
    Richard Bos, Jul 7, 2010
    #11
  12. bolega

    Richard Bos Guest

    You think wrong. There is no reason to believe it impossible[1] to write
    a vanilla C interpreter. In fact, it's probably slightly easier to
    ensure that your implementation is _exactly_ vanilla if you make it an
    interpreter rather than a compiler.
    The real question is whether it's worth the trouble, writing an
    interpreter and then only providing vanilla C. Presumably for didactic
    reasons it could.

    Richard

    [1] It's certainly possible to write a C interpreter, because it's been
    done; but I don't know how vanilla they are.
     
    Richard Bos, Jul 7, 2010
    #12
  13. This look like a huge project for an evaluation of expressiveness
    which result is obvious. Lisp (including Scheme) is more expressive
    than Python, for many definitions of expressiveness (see for instance
    http://www.ccs.neu.edu/scheme/pubs/scp91-felleisen.ps.gz if you like
    academic papers). However, who cares? What matters in everyday life
    are other things, like the availability of libraries, tools, easy of
    maintenance, etc.

    In your proposed project the choice of the parsing library would
    matter a lot. Writing languages is a domain where Lisp is
    traditionally strong, so you may find good libraries to help you with
    the task. My guess is that it would take more or less the same amount
    of effort both in Python and in Lisp. The place where Lisp has an
    advantage is writing an *embedded* language: then thanks to macros you
    could write a *compiled* sublanguage. Doing the same in Python is
    essentially impossible.

    Michele Simionato
     
    Michele Simionato, Jul 7, 2010
    #13
  14. bolega

    Rivka Miller Guest

    You should probably narrow down your project to one. For example,
    write a LISt Processor Meta Circular Evaluator in C.

    You can take Paul Graham's rendition as a start and forget about
    garbage collection.

    Start with getchar()/putchar() for I/O.

    Although C comes with a regex library, you probably do not need a
    regex or parser at all for this. This is the beauty of LISP which is
    why McCarthy was able to bypass the several man years of effort
    involved in FORmula TRANslator. Even as a young boy like L. Peter
    Deutsch was able to write it in assembly for one of the PDP's.

    You will have go implement an associative array or a symbol-value
    table probably as a stack or linked list. You will have to decide how
    you implement the trees, as cons cells or some other method. Dynamic
    scoping is easy to implement and that is what elisp has. I am not
    aware of any book that provides implementation of LISP in C and
    explains it at the same time.

    This is the extent of help I can provide, someone else can probably
    help you more.

    Anyone know what the first initial of L. Peter Deutsch stand for ?

    Rivka
     
    Rivka Miller, Jul 7, 2010
    #14
  15. original Karl Valentin would be <colder outside than nighttime>
    but yours is in his sense.

    Wolfgang
     
    wolfgang.riedel, Jul 7, 2010
    #15
  16. C does not come with a regexp library

    Laurence according to wikipedia (search time 2s)
     
    Nick Keighley, Jul 8, 2010
    #16
  17. oops! He was born Laurence but changed it legally to "L." including
    the dot
     
    Nick Keighley, Jul 8, 2010
    #17
  18. Too bad, "Laurence" is a nice name.
     
    Pascal J. Bourguignon, Jul 8, 2010
    #18
  19. bolega

    Mark Tarver Guest

    Probably you want to look at this thread

    http://groups.google.co.uk/group/co...025e27?hl=en&lnk=gst&q=minim#54afe11153025e27

    where I specified a toy language Minim (much simpler than C) and the
    goal was to construct an interpreter for it. Similar problem.

    Many solutions were given in different languages. The thread is very
    long.

    One thing you might look at is whether some sort of lexer/parser is
    supported in any of your targets. Qi supports a compiler-compiler Qi-
    YACC that allows you to write in BNF which makes this kind of project
    much easier.

    See

    http://www.lambdassociates.org/Book/page404.htm

    for an overview

    Mark
     
    Mark Tarver, Jul 8, 2010
    #19
  20. He probably hates the nickname "Larry".
     
    George Neuner, Jul 8, 2010
    #20
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.