Реализация языков программирования

Общая схема реализации функциональных языков

ML, JScript, Hope, Lisp.

Аппликация и абстракция в них выражаются средствами языка. Любой из этих языков может быть выражен в λ-исчислении. Часто языки дополняют структурами, логическими, арифметическими и прочими операциями.

Пример. Выражения на языке Lisp.

((lambda(xy)(apply+(list(xy)))34) = (λx.λy(+(xy)))34

Hо в Lisp сложение можно записать как (+34).

Есть множество функциональных языков (ФЯ). Все они легко переводятся в λ-исчисление.

	Редукция графа (РГ) λ-исчисление интерпретаторы

ML LISP HOPE

Результат (Нормальная форма).

λ-исчисление (расширен- ное)

Суперкомбинаторы Комбинаторная логика, Алгоритмы Маркова, Трансформационные системы  

ФЯ

Компиляция в коды абстрактных машин (АМ),SECD, KAM Комбинаторная логика, Категориальная комбинаторная логика(KKЛ).  

Расширенное λ-исчисление

λ (λ-абстракция);

@ (аппликация);

TRUE; FALSE; 0,1…; +; /; =; >; <; cons; head; tail (конструкторы данных);

null (распознает пустой список);

If … then… else…;

let;

letrec (позволяет явно записать подстановку); quote (возможно определение через K).

(λx.x+3)3 let x=3 in x+3

letrec fun =H(fun) in fun(arg)

Пример. a) let x=3 in λy.+xy→ λy.+3y

b) Lisp # '(lambda(x) ML -fun foo [ ]=4 _cоns

(cоnd: foo x=(x::3)

(x(cons x’3)) >val foo fn:(’а list)

(# T ’ 4))) →int list

Дата добавления: 2014-01-11