представления данных в схеме

Question

я должен развивать представление данных:

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

подмножество содержит 3 выражения. Переменные, функция одного аргумента и приложение функции.

Мой вопрос: как я должен создавать представление данных выше, если lambda являются функциями без имен? Это не имеет смысла. Ну, по крайней мере, для меня.

Answer 1

Это звучит как упражнение по переводу ваших собственных типов данных. Вот один из способов, который вы могли бы представлять, создавать, получать доступ и тестировать структуры. Я представлял:

• <var> списком (var [name]) где [name] является то, что имя переменной (это может быть строка, символ, число, или что-нибудь еще, что вы хотите быть имя Переменная);
• лямбда-функции по списку (lambda [var] [exp]) где [var] и [exp] - объекты переменной и выражения; и
• функциональные приложения по списку (application [exp1] [exp2]), где [exp1] и [exp2] являются объектами выражения.

Важно отметить, что мы просто используем структуры данных, которые система уже предоставила нам. Это означает, что можно было бы, например, получить доступ к имени переменной v, используя (cadr v) вместо (var-name v), но мы действительно должны предпочесть последний. Это позволяет нам, например, изменить базовое представление позже, и до тех пор, пока обновляется var-name, весь код с использованием var-name будет продолжать работать.

(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))) 

Answer 2

Я не буду вдаваться в создание структур данных здесь с Joshua has done that already, но говорить о функциях вообще.

Никаких функций не требуется. Некоторые имена указывают на функции объектов (процедуры, закрытия).

У вас есть (lambda (x) x). В переводчике lambda - специальная форма, и она превращает форму в procedure (закрытие). Представление после оценки может быть (procedure (x) <env> x), где env - текущая среда. Оценка ((lambda (x) x) y) будет оценивать оператор, который оценивается до (procedure (x) <env> x), и оценщик идентифицирует это как процедуру, поэтому он будет оценивать аргумент перед применением x в среде замыканий с привязками переменных.

Как функционируют функции с именами? С названным, например. (define identity (lambda (x) x) Этот же механизм используется для создания процедуры, но специальная форма define создает привязку к результату, так что identity привязан к (procedure (x) <env> x) в среде. Когда вы сделаете (identity q), он сначала оценит identity как часть случая по умолчанию, в котором у вас есть приложение, так что интерпретатор получает (procedure (x) <env> x) и когда он анализирует, что он знает, чтобы оценить аргумент перед приложением.

И это только что истолкованный код.В скомпилированном случае различия были бы намного меньше, и это было бы возможно, что он превратился бы в тот же самый скомпилированный код, поскольку имя предназначено только для программистов для абстрактной сложности в легко разрешимые части.