Howdy all,

Up front, this is a homework question.

I'm pretty much completely clueless with lisp, so I'm going to post the assignment and the (what i believe to be) relevant code.

if anyone can lend me a hand, I'd be more than grateful.

write a program using just the purely functional features of Common Lisp (namely cons, car, cdr, cond, defun and whatever basic predicates and operators you know includeing print and read, but obviously no variables other than function parameters sequencing or loops that will simulate the behavior of the little imperative language described below.

you will turn in by email a single file containing all your necessary function definitions. your ultimate function will be such that evaluationg (imper prog) will simulate execution of the program prog written in the simple imperative language.

Example prog might be the expression:
(( input)n (a=1) (b=1) (m=1)
(while (m<n) ((c=(a+b)) (a=b) (b=c)
(m=(m+1))
)
)
(output b)
)



grammar

P->(L)|()
L->SL|S
S->(AW=WE)|(outputWE)|(inputW A)|
(ifW EW P)|(ifW EW PW elseW P)|(whileW EW P)
E-> N|A|(EW OW E)
O-> +|-|*|/|<|<=|=|and|or
N-> any numeric atom in Lisp
A-> any non-numeric atom in Lisp that is not used for anything else
W-> whitespace

Note that the whitespace is a required part of the syntax so that code in the little imperative language can be conveniently tokenized into list elements by Lisp. For example an expression such as ( a + b ) must have at least one space on either side of the + atom, so that Lisp will be able to recognize it as a list with three elements, rather than the somewhat bizarre single atom a+b. Also techinically the grammar says that (if(x < y) ((x = (x + 1)))) is illegal because it doesn't have any whitespace between the keyword if and the following expression, but the intent is for the whitespace to only be required where it makes things easier. In other words you don't have to call this an error.

Semantics
simlar to pretty much every imperative language. variables do not need to be declared.

Error handling

if the expression being interpreted is not correct either syntactically or semantically your imper function can behave in any way you wish. if you want to produce meaningful error output before haltin, that would be nice but is not required.

Hints

not allowed to use any non-functional features other than displaying and reading, which are arguably not purely functional sugh as using variables and assignment statements.

Probably want to make an auxiliary function, say
(imperexec code table)
that will take as input a fragment of imperative code and a table of pairs of non-numeric atoms and their current values and will simulate executiion of the fragment, producing appropriate output information and returning as its value an updated table with the pairs in it reflecting the results of any simulated assignment statements that were done.


Pertinent code:

(defun countList (x)
(cond
( (atom x) 0)
( T (+ 1 (countList (cdr x))) )
)
)

(defun countAtoms (x)
(cond
( (atom x) 1 )
( T (+ (countAtoms (car x)) (countAtoms (cdr x))) )
)
)

(defun retrieve (var table)
(cond
( (eq table NIL) NIL )
( (eq (caar table) var) (car (cdr (car table))) )
( T (retrieve var (cdr table)) )
)
)

(defun buildPair (var value)
(cons var (cons value ()))
)

(defun store (var value table)
(cond
( (eq NIL table)
(cons (buildPair var value) table )
)
( (first pair in table matches var)
(cons (buildPair var value) (cdr table))
)
( T
(cons (car table) (store var value (cdr table)))
)
)
)



(defun null. (x)
(eq x '())
)

(defun and. (x y)
(cond
( x (cond (y 'T) ('T '())) )
( 'T '() )
)
)

(defun not. (x)
(cond
( x '() )
( 'T 'T )
)
)

(defun append. (x y)
(cond
( (null. x) y )
( 'T (cons (car x) (append. (cdr x) y)) )
)
)

(defun list. (x y)
(cons x (cons y '()))
)

; different from Graham, page 7
(defun pair. (x y)
(cond
( (and. (null. x) (null. y)) '() )
( 'T (cons (list. (car x) (car y))
(pair. (cdr x) (cdr y)) )
)
)
)

(defun assoc. (x y)
(cond
( (eq (caar y) x) (cadar y) )
( 'T (assoc. x (cdr y)) )
)
)

(defun eval. (e a)
(cond

( (atom e) (assoc. e a) )

( (atom (car e))
(cond
( (eq (car e) 'quote) (cadr e) )
( (eq (car e) 'atom) (atom (eval. (cadr e) a)) )
( (eq (car e) 'eq) (eq (eval. (cadr e) a)
(eval. (caddr e) a) ) )
( (eq (car e) 'car) (car (eval. (cadr e) a)) )
( (eq (car e) 'cdr) (cdr (eval. (cadr e) a)) )
( (eq (car e) 'cons) (cons (eval. (cadr e) a)
(eval. (caddr e) a) ) )
( (eq (car e) 'cond) (evcon. (cdr e) a) )
( 'T (eval. (cons (assoc. (car e) a)
(cdr e)) a ) )
)
)

( (eq (caar e) 'label) (eval. (cons (caddar e) (cdr e))
(cons (list. (cadar e) (car e)) a))
)

( (eq (caar e) 'lambda )
(eval. (caddar e) (append. (pair. (cadar e) (evlis. (cdr e) a)) a))
)

)
)

(defun evcon. (c a)
(cond
( (eval. (caar c) a) (eval. (cadar c) a) )
( 'T (evcon. (cdr c) a) )
)
)

(defun evlis. (m a)
(cond
( (null. m) '() )
( 'T (cons (eval. (car m) a)
(evlis. (cdr m) a) ) )
)
)



and a test case:

(imper

'(
(output 12345)
(input n)
(output n)
(a = 3)
(b = 4)
(c = (a + b))
(output c)
(output (7 - 1))
(output (2 * 3))
(output (12 / 2))
(output 12345)
(output (2 < 3))
(output (3 < 2))
(output 12345)
(output (2 <= 3))
(output (3 <= 2))
(output (2 <= 2))
(output 12345)
(output (2 = 3))
(output (2 = 2))
(output 12345)
(output (1 and 1))
(output (1 and 0))
(output 12345)
(output (1 or 0))
(output (0 or 0))
(output 12345)
(output (2 and 3))
(output 12345)

(n = 10)
(k = 1)
(sum = 0)
(while (k <= n)
(
(output k)
(if (k <= 5)
(
(output (100 + k))
)
else
(
(output (200 + k))
)
)
(sum = (sum + k))
(k = (k + 1))
)
)
(output sum)

(if (3 < 4)
(
(output -1)
)
)

(if (4 < 3)
(
(output -1)
)
)

(output 123456789)

)

)



If i can do anything else to get some help, please let me know.

dhoss

Howdy all,

Up front, this is a homework question.

I'm pretty much completely clueless with lisp, so I'm going to post the assignment and the (what i believe to be) relevant code.

if anyone can lend me a hand, I'd be more than grateful.


Try searching some ebooks about LISP to learn the standards to help you do the HW.

Peace,

Going to be straight up, if you can't do that homework assignment, you might need to switch majors.

who said I couldn't do it? also, your reply is about as helpful as not saying anything at all, consider it a waste of time.

who said I couldn't do it? also, your reply is about as helpful as not saying anything at all, consider it a waste of time.

I'm pretty much completely clueless with lisp, so I'm going to post the assignment and the (what i believe to be) relevant code.


You did. Unless I have mistaken

clueless does not equal unable. clueless means i don't know lisp very well. it does not reflect my programming logic or problem solving abilities. You are very mistaken.

I just finished with my programming language concepts class. Writing a LISP compiler seems to be a pretty daunting task. I suggest downloading a common LISP interpreter and start playing around. To do things purely functional with LISP, you need to have a good understanding of lambda calculus. Obviously to accomplish this task, you will need to lower your ignorance to the language.

Don't understand why professors are so adamant about spending significant time with out dated languages. We covered it, but to be asked to learn the language to such a depth that you are able to write a compiler seems a little nutty.

Pete

To the OP - you are not likely going to find a lot of Lisp knowledge here; it just isn't that pervasive in commodity web hosting, which is what this site is primarily all about.

I'm reluctant to jump in myself - my Lisp experience amounts to some tinkering 10 years ago one afternoon.

Perhaps have a look at some of the contributors to Planet Lisp and ask whoever appears prolific and/or approachable for a pointer to resources.

http://planet.lisp.org/

meh luckily this class is over and it got done eventually, but I appreciate it.