CODEWITHSUNDEEP
lambdaschemeracket
Josh
Josh

Reputation: 519

data representations in scheme

I am supposed to develop a data representation of:

   <exp> = <var> | (lambda (<var>) <exp>) | (<exp> <exp>)

the subset contains 3 expressions. Variables, function of one argument, and function application.

My question is, how am I supposed to create data representation of the above if lambda are functions without names? This doesn't make sense. Well at least to me.

Upvotes: 1

Views: 91

Answers (2)

Sylwester
Sylwester

Reputation: 48745

I won't go into making data structures here since Joshua has done that already, but talk about functions in general.

No functions need a name. Some names points to function objects (procedures, closures).

So you have (lambda (x) x). In an interpreter lambda is a special form and it turns the form into a procedure (closure). An representation after evaluation might be (procedure (x) <env> x) where env is the current environment. Evaluating ((lambda (x) x) y) will evaluate the operator, which evaluates to (procedure (x) <env> x) and the evaluator will identify that as a procedure so it will evaluate the argument before applying x in the closures environment with the variable bindings.

How does functions with names make more sense? With a named eg. (define identity (lambda (x) x) The same mechanism is used to create the procedure, but the special form define creates a binding to the result so that identity is bound to (procedure (x) <env> x) in the environment. When you do (identity q) it will evaluate identity first as a part of the default case where you have an application so that the interpreter gets (procedure (x) <env> x) and when it analyses that it knows to evaluate the argument before application.

And this is just interpreted code. In a compiled one the differences would be a lot smaller and it's a possibility that it would have turned into the exact same compiled code since the name is just for programmers to abstract complexity into easily solvable parts.

Upvotes: 1

Joshua Taylor
Joshua Taylor

Reputation: 85873

This sounds like an exercise in rolling your own datatypes. Here's one way you could represent, create, access, and test for the structures. I've represented:

  • <var> by a list (var [name]) where [name] is whatever the name of the variable is (it could be a string, a symbol, a number, or anything else that you want to be the name of a variable);
  • lambda functions by a list (lambda [var] [exp]) where [var] and[exp] are variable and expression objects; and
  • function applications by a list (application [exp1] [exp2]) where [exp1] and [exp2] are expression objects.

It's important to notice that we're just using the data structures that Scheme has already provided us. This means that it would be possible, for instance, to access the name of a variable v by using (cadr v) instead of (var-name v), but we really should prefer the latter. It allows us, for instance, to change the underlying representation later, and as long as var-name is updated accordingly, all the code using var-name will continue to work.

(define (make-var name)
  (list 'var name))

(define (var? thing)
  (and (pair? thing)
       (eq? 'var (car thing))))

(define (var-name var)
  (cadr var))

(define (make-function var expression)
  (list 'lambda var expression))

(define (function? thing)
  (and (pair? thing)
       (eq? 'lambda (car thing))))

(define (function-var function)
  (cadr function))

(define (function-exp function)
  (caddr function))

(define (make-application expression1 expression2)
  (list 'application expression1 expression2))

(define (application? thing)
  (and (pair? thing)
       (eq? 'application (car thing))))

(define (application-applicand application)
  (cadr application))

(define (application-argument application)
  (caddr application))

(define (expression? thing)
  (or (var? thing)
      (function? thing)
      (application? thing)))

Upvotes: 1

Related Questions