3

According to the answers on this question, only five real functions are needed to implement anything in Lisp, provided you implement the eval function in the language itself. Am I correct?

I want to implement a very minimalistic Lisp in in Java, making it as minimal as possible with an interpreter that is as small and simple as possible. Can I do that with just those five functions? How will it even call eval from Java? I'm not sure how to approach this. Anyone have any examples of interpreters written like this with a very minimal implementation in another language?

Community
  • 1
  • 1
user3035609
  • 55
  • 3
  • It's becoming too common when a genuine, valid question is closed by people who are incapable of understanding it due to their own ignorance. It's perfectly obvious what OP is asking, and it's a pretty practical and specific question. Shame on SO. If you cannot understand the question - just walk away, ok? – SK-logic Nov 26 '13 at 12:18
  • @SK-logic I agree that "unclear what you're asking" is the wrong reason to close this question. However, the second paragraph is a list of questions, some of which are really too broad and would attract list answers (e.g., "How will it even call eval from Java?" and "Anyone have any examples of interpreters written like this with a very minimal implementation in another language?") I think that this question would need to be a much more specific programming question before it's really on-topic for Stack Overflow. – Joshua Taylor Nov 26 '13 at 13:04
  • @JoshuaTaylor, it still boils down to a single question (although I agree that the given wording is far from perfect): "which minimal set of primitives is needed to build a minimalistic Lisp implementation". – SK-logic Nov 26 '13 at 13:06
  • @SK-logic The title does, but the question doesn't. The question also asks, e.g., "How will it even call eval from Java?" If an answer only enumerates the primitives, then it won't answer "how does my Lisp call eval from Java?" If it only answers "how does my Lisp call eval from Java?" then it won't answer "what are the necessary primitives?" A snarky approach would focus on "Am I correct?" and just reply "yes". I don't think it's unclear what the OP was asking, but I think that the OP was asking too much in one question. – Joshua Taylor Nov 26 '13 at 13:18
  • @JoshuaTaylor, an invocation of an `eval` function in a minimalistic interpreter is definitely dependent on a choice of the interpretation primitives. Not sure one can design these things separately (see my answer for example). – SK-logic Nov 26 '13 at 13:41
  • @SK-logic: I was puzzled because he/she links to a question and answers, posted already on Stackoverflow, and asks 'am I correct'? – Rainer Joswig Nov 26 '13 at 16:22
  • 5 primitives is very little and almost impossible even when the host is lisp based. The most difficult would be `read` and `print`. When that said your evaluator could be very simple if your environment structure has all the special forms and primitives and compunds in it. Eg. you make evaluation of symbol, a pre-eval where you evaluate the first argument. Based on it being syntax, compund-syntax, procedure, prtimitive-procedure you do different things with it. My env starts off with 4 syntax' (quote,if,lambda,flambda) and 7 procedures (cons,car,cdr,print,read,eq,symbolp) – Sylwester Nov 27 '13 at 01:26
  • @Slywester, it should be possible to have just two evaluation primitives (S and K) and two runtime primitives (readchar and putchar, for communicating with the outside world). Although, it is far from practical indeed. – SK-logic Nov 27 '13 at 13:00
  • @SK-logic it doesn't matter as long you can create the lisp primitives in it. I read you only need lambda, but that is half true. You need macros to rewrite nice lisp code into lambda nestings or SK logic. – Sylwester Nov 27 '13 at 14:36
  • @SK-logic BTW I find many "SK logic in Scheme" but no "Scheme in SK logic" so there must be something missing :) Would SK be a better approach to make an eager evaluating Scheme than just using lambda or is it the same? How would input/output affect it? – Sylwester Nov 27 '13 at 14:44
  • @Sylwester, the implementation I suggested in my answer does not actually need lambda (lambda lifting and closure instantiation is performed by a compiler). For "lisp in SK" - see a link in my answer below. It's a lazy lisp implementation, but it's always possible to implement an eager interpreter or a compiler on top of a lazy one. – SK-logic Nov 27 '13 at 15:00
  • Indeed I find this question perfectly valid and it's not the first one that IMO gets killed for no reasons. I wonder if it's because of the need of maintaining a certain pop culture image of lispers being angry jerks. I would also like to answer, but I cannot. – 6502 Nov 27 '13 at 16:20

2 Answers2

4

You don't have to implement too much in Java.

Even S-expressions parsing can be implemented in Lisp, with the Java part being only responsible for reading some simple serialised form. For example, in a Forth-like syntax, as in (a (b c)) -> a b c NIL . . NIL . ., where . makes a cons cell.

Java runtime should provide the very minimal set of primitives. No need to support full Lisp semantics, it's easier to implement a compiler from a "full" Lisp into a simplified bootstrap language in Lisp itself. The bootstrap language may support following primitives:

  • FUNCTION, Making a function object, with a given number of arguments and a given body
  • ARG, Accessing the n-th argument of a function
  • VAR, Accessing the n-th slot of a closure
  • IF primitive
  • APPLY primitive
  • CONST primitive
  • CLOSURE primitive - similar to a function object, but initialising a number of closure environment slots

It's easy to implement such an interpreter in Java, with all of the primitives above being classes implementing the same AstNode interface with a method Run(Environment env).

On the Lisp side, a simple "compiler" must be implemented, which will perform lambda lifting and variables enumeration. Things like let, let*, etc., can be implemented as simple macros (with macro expander also implemented in Lisp itself).

A minimal set of runtime library functions provided by Java should contain car, cdr, cons, listp, nullp, symbol to string and string to symbol conversions, string concatenation, and an access to the Java reflection for implementing everything else from the Lisp side.

Of course, such interpreter is not going to be very efficient - for example, you'd have to implement recursive functions via Y-combinator. But, you'll only need it to bootstrap the next iteration of a language, of course implemented in Lisp as well, which will compile the same source language into Java bytecode.

Variations are possible - one may implement, say, a simple graph reduction engine instead of an interpreter above, it's even simpler, but is even less efficient.

SK-logic
  • 9,605
  • 1
  • 23
  • 35
1

You need a REPL (read-eval-print loop), written in Java, that will read and parse any Lisp line provided by the user : that is the role of your eval function. Parsing a Lisp s-expression is rather easy : the first item of the list is a function call, other elements are arguments applied to that function. And applying a function just means replacing the function's body with the given attributes, and reduce it until you reach axioms. For example :

((lambda (x y) (cons x (cons y x))) 1 2)

will be evaluated as

(cons 1 (cons 2 1))

And, here, you've reached the level where you only have axioms. The axiomatic functions, actually, are not functions per se, they are special forms, i.e. treated directly by your eval function, which means they have to be implemented in Java, too.

Well, be aware that your lisp interpreter with only these 7 axioms will be very primitive, though. You will have no arithmetic operations, no comparisons, no strings, etc. All of that will have to be implemented on top of the axioms.

Fabien
  • 12,486
  • 9
  • 44
  • 62