Thursday, June 27, 2013

Tcl պրոցեդուրաները

Tcl լեզվում պրոցեդուրները (կամ ֆունկցիաները) սահմանվում են proc հրամանի միջոցով։ Այն ստանում է երեք արգումենտ. ա) սահմանվող պրոցեդուրայի անունը, բ) արգումենտների ցուցակը, և գ) մարմինը։ Օրինակ, տրված x և y թվերից մեծը որոշող ֆունկցիան կարելի է սահմանել հետևյալ կերպ.

proc max { x y } {
    if { $x > $y } then {
        return $x
    }
    return $y
}

Կամ, եթե չենք ուզում օգտագործել if հրամանը.

proc max { x y } {
    return [expr {$x > $y ? $x : $y}]
}

Այս երկու օրինակներում էլ return հրամանն օգտագործված է ֆունկցիայի մարմնից արժեք վերադարձնելու համար։ Tcl պրոցեդուրաները կառուցված են այնպես, որ եթե նրա մարմնում, կամ կատարման որևէ ճյուղում, որը բերում է պրոցեդուրայի ավարտի, բացակայում է return հրամանը, ապա ֆունկցիայի վերադարձրած արժեք է համարվում դրա կատարման ժամանակ վերջին արտահայտության հաշվարկված արժեքը։ Սա հաշվի առնելով, կարող են նախորդ օրինակը գրել առանց return հրամանի.

proc max { x y } {
    expr {$x > $y ? $x : $y}
}

Եթե պրոցեդուրան սպասում է միայն մեկ արգումենտ, ապա սահմանման ժամանակ այդ միակ ֆորմալ արգումենտի անունը կարելի է գրել առանց ձևավոր փակագծերի։ Օրինակ, Սահմանենք մի պրոցեդուրա, որը ստուգում է տրված բառի պալինդրոմ լինելը.

proc palindrom? str {
    string equal $str [string reverse $str]
}

Իսկ եթե արգումենտների ցուցակում վերջին կամ միակ արգումենտի անունը args է, ապա նրա միջոցով, որպես ցուցակ, պրոցեդուրայի մարմնին են փոխանցվում կամայական թվով արժեքներ։ Օրինակ, ահմանենք մի ֆունկցիա, որը հաշվում է երկու և ավելի թվերի թվաբանական միջինը.

proc average { a b args } {
    set sum [expr {$a + $b}]
    foreach n $args {
        set sum [expr {$sum + $n}]
    }
    return [expr {$sum / (2 + [llength $args])}]
}

Ահա նաև այս պրոցեդուրայի օգտագործման մի քանի օրիակ.

average 1.1 2.2                    ; # => 1.6500000000000001
average 1.1 2.2 5.5 4.4 3.3        ; # => 3.3
average 1.2 2.3 3.4                ; # => 2.3000000000000003

proc հրամանը հնարավորություն է տալիս սահմանել նաև լռելությոն (default) արժեքով արգումենտներ ունեցող պրոցեդուրաներ։ Այդ դեպքում արգումենտը տրվում է երկու տարրերի ցուցակի տեսքով, որոնցից առաջինը ֆորմալ արգումենտի անունն է, իսկերկրորդը՝ նրա լռելության արժեքը։ Օրինակ, սահմանենք մի ֆունկցիա, որը վերադարձնում է \(y\) թվի \(n\) աստիճանի արմատը՝ \(\sqrt[n]{y}\), եթե \(n\)-ը տրված չէ, այն համարվում է \(2\)։

proc root { y {n 2} } {
    expr exp(log($y) / $n)
}

Ահա կիրառման օրինակներ.

root 1024           ; # => 32.0
root 1024 5         ; # => 4.0
root 1024 10        ; # => 2.0

Monday, June 24, 2013

Scheme պրոցեդուրաները

Scheme ծրագրավորման լեզվում պրոցեդուրաները սահմանվում են lambda ծառայողական բառով, որին հետևում են արգումենտների ցուցակը և պրոցեդուրայի մարմինը կազմող արտահայտությունները։ Օրինակ, կարող եմ սահմանել տրված երկու թվերի քառակուսիների գումարը հաշվող պրոցեդուրա․

(lambda (x y) (+ (* x x) (* y y)))

Սա x և y ֆորմալ արգումենտներով պրոցեդուրա է։ Եթե ուզենամ այն կիրառել 3 կամ 4 արգումենտների նկատմամբ, ապա պետք է գրեմ․

((lambda (x y) (+ (* x x) (* y y))) 3 4)  ; => 25

Այս անհարմար գրառումից խուսափելու համար կարող եմ պրոցեդուրային անուն տալ՝ define ծառայողական բառի օգնությամբ այն կապելով որևէ սիմվոլի հետ.

(define sum-squares
    (lambda (x y) (+ (* x x) (* y y))))

Եվ արդեն կարող եմ պրոցեդուրան արգումենտների նկատմամբ կիրառել sum-squares անունով։

(sum-squares 3 4)  ; => 25

Պրոցեդուրայի սահմանումն ավելի համառոտ կարելի է գրել առանց lambda ծառայողական բառի օգտագործման՝ define սահմանման առաջին արգումենտը դարձնելով ցուցակ, որի առաջին տարրը սահմանվող պրոցեդուրայի անունն է, իսկ հաջորդողները՝ ֆորմալ արգումենտները։ Օրինակ,

(define (sum-squares x y)
    (+ (* x x) (* y y)))

Ես նախնտրում եմ lambda-ի օգտատգործմամբ տարբերակը։ Կարծում եմ, որ դա ավելի համահունչ է define բառի հետ։

Հիմա, ենթադրենք, պետք է սահմանել պրոցեդուրա, որը իրար է գումարում տրված թվերը։ Առաջին միտքն այն է, որ սհամանել մեկ արգումենտով պրեցեդուրա և նրան փոխանցել թվերի ցուցակը։ Օրինակ այսպես.

(define sum-list
    (lambda (l)
        (if (null? l)
            0
            (+ (car l) (sum-list (cdr l))))))

Սա ռեկուրսիվ պրոցեդուրա է, որ 0 է վերադարձնում դատարկ ցուցակի դեպքում, իսկ ոչդատարկ ցուցակների համար ցուցակի առաջին տարրը գումարում է պոչի տարրերի գումարին։ Այս պրոցեդուրան պետք է կիրառել հետևյալ կերպ.

(sum-list '())         ; => 0
(sum-list '(1))        ; => 1
(sum-list '(1 2 3 4))  ; => 10

Բայց ավելի բնական կլիներ, եթե ես կարողանայի գրել այսպիսի արտահայտություններ.

(sum)          ; => 0
(sum 1)        ; => 1
(sum 1 2 3 4)  ; => 10

Այլ կերպ ասած՝ ունենալ պրոցեդուրա, որի արգումենտների քանակը ֆիքսված չէ. դրանք կարող են կա՛մ բացակայել, կա՛մ լինել անորոշ քանակի։

Երբ lambda կառուցվածքի առաջին արգումենտը տրված է որպես ատոմ (այլ ոչ թե որպես ցուցակ), ապա պրոցեդուրայի արգումենտը համարվում է անորոշ քանակի։ Օրինակ, հիշատակված sum պրոցեդուրան, օգտագործելով sum-list պրոցեդուրան, կարելի է սահմանել հետևյալ կերպ.

(define sum
    (lambda nums
        (sum-list nums)))

Երբ այս կերպ սահմանված պրոցեդուրան կիրառվում է արգումենտների նկատմամբ, այդ արգումենտներից կազմվում է ցուցակ և փոխանցվում է պրոցեդուրային։ Բնականաբար, պրոցեդուրայի մարմնում պետք է ֆորմալ արգումետի հետ աշխատել որպես ֆունկցիա։ Օրինակ, եթե sum պրոցեդուրան սահմանելու լինեի առանց sum-list պրոցեդուրայի օգտագործման, ապա պետք է գրեի.

(define sum
    (lambda nums
        (if (null? nums)
            0
            (+ (car nums) (apply sum (cdr nums))))))

apply հրամանն օգտագործված է այն պատճառով, որ sum պրոցեդուրայի ռեկուրսիվ կանչի ժամանակ (cdr nums) ցուցակը նրան փոխանցվելու է որպես նոր ցուցակի միակ տարր։

Tuesday, June 4, 2013

Բարձր կարգի ֆունկցիաներ և անանուն ֆունկցիաներ

Երկու սերտ հասկացություններ՝ բարձր կարգի ֆունկցիա և անանուն ֆունկցիա, որոնք լայնորեն կիրառվում են ֆունկցիոնալ ծրագրավորման մեջ, որոնց տրամադրած մեխանիզմները հնարավորություն են տալիս կազմակերպել ավելի բնական, ավելի գեղեցիկ, ավելի ընթեռնելի ծրագրեր։

Ֆունկցիան կոչվում է բարձր կարգի, եթե նրա արգումենտներից գոնե մեկը ֆունկցիա է, կամ նրա վերադարձրած արժեքն է ֆունկցիա։

Ես ուզում եմ բարձր կարգի ֆունկցիաները ցուցադրել տրված ֆունկցիայի որոշյալ ինտեգրալի թվային հաշվման օրինակով։ Ենթադրենք պետք է իրականացնել integral ֆունկցիան, որն արգումենտում ստանում է \(f(x)\) ինտեգրվող ֆունկցիան և \([a;b]\) ինտեգրման միջակայքը։ $$ \mathrm{integral}(f, a, b)=\int\limits_a^b f(x)dx $$ Այս integral ֆունկցիան երկրորդ կարգի է, որովհետև նրա f արգումենտը առաջին կարգի ֆունկցիա է։

Ինտեգրալի թվային հաշվման համար ընտրենք սեղանների մեթոդը, որի դեպքում ինտեգրման միջակայում \(f\) ֆունկցիայի գրաֆիկը մոտարկվում է ուղիղ գծով, իսկ ինտեգրալի արժեքը ընդունվում է \((a,0)\), \((a,f(a))\), \((b,f(b))\) և \((0,b)\) գագաթներով սեղանի մակերեսին հավասար։ \[ \mathrm{trapezoid}(f, a, b)=(b-a)\frac{f(a)+f(b)}{2} \] Common Lisp լեզվով այս բանաձևը ծրագրավորվում է հետևյալ կերպ.
(defun trapezoid (f a b)
  (* (- b a) (/ (+ (funcall f a) (funcall f b)) 2.0)))
integral ֆունկցիայի արգումենտում տրված f ֆունկցիա-արգումենտը ֆունկցիայի մարմնում օգտագործված է funcall ֆունկցիայի միջոցով, որը տրված ֆունկկցիա-օբյեկտը կիրառում է տրված արգումենտների նկատմամբ։

C++11 լեզվով նույն integral ֆունկցիան կարելի է գրել հետևյալ կերպ.
double trapezoid( std::function<double(double)> f, double a, double b )
{
  return (b - a) * ((f(a) + f(b)) / 2);
}
Եթե այս ֆունկցիայով հաշվենք, օրինակ \(f(x)=x^2\) ֆունկցիայի ինտեգրալը \([-1;1]\) միջակայքում, ապա կստանանք \(2\) արժեքը՝ իրական \(2/3\)-ի փոխարեն։

Պարզ է, որ սեղանների մեթոդը կարող է բավարար ճշտություն ապահովել միայն այն դեպքում, երբ ինտեգրման միջակայքը շատ փոքր է։ Օգտագործելով այդ փաստը, սահմանեմ integral ֆունկցիան, որի \(\varepsilon\) արգումենտը ցույց է տալիս ինտեգրման միջակայքի ամենամեծ թույլատրելի չափը։ Այն դեպքում, երբ \(b-a\gt\varepsilon\), միջակայքը կկիսեմ երկու հավասար մասերի և իրար կգումարեմ այդ երկու մասերում հաշված ինտեգրալների արժեքները։ Այլ կերպ ասած, ինտեգրալի հաշվման նոր բանաձևն է հետևյալը. \[ \mathrm{integral}(f, a, b, \varepsilon)= \left\{ \begin{array}{ll} \mathrm{trapezoid}(f, a, b), & |b - a|\le\varepsilon, \\ \mathrm{integral}(f, a, \frac{a+b}{2}, \varepsilon) + \mathrm{integral}(f, \frac{a+b}{2}, b, \varepsilon), & |b - a|\gt\varepsilon.\\ \end{array} \right. \] Այս integral ֆունկցիան նույնպես երկրորդ կարգի է, քանի որ նրա արգումենտներում ամենաբարձր կարգը առաջինն է։ integral ֆունկցիայի սահմանումը Common Lisp լեզվով ունի այսպիսի տեսք.
(defun integral (f a b &optional (eps 0.001))
  (if (<= (- b a) eps)
      (trapezoid f a b)
      (let ((m (/ (+ a b) 2)))
        (+ (integral f a m eps) (integral f m b eps)))))
Նույն ֆունկցիան C++11 լեզվով կունենա հետևյալ տեսքը։
using mathfunc = std::function<double(double)>;

double integral( mathfunc f, double a, double b, double eps = 0.001 )
{
  if( b - a <= eps)
    return (b - a) * ((f(a) + f(b)) / 2);

  auto m((a + b) / 2);
  return integral(f, a, m, eps) + integral(f, m, b, eps);
}
Հիմա, ենթադրենք, ուզում եմ հաշվել \(f(x)=x^3\) ֆունկցիայի ինտեգրալը \([0;2]\) միջակայքում: Նախ սահմանեմ այդ ֆունկցիան Lisp լեզվով.
(defun f (x) (* x x x))
Ապա integral ֆունկցիայի օգնությամբ հաշվեմ սրա ինտեգրալը տրված միջակայքում.
(integral #'qub 0 2.0)   ; => 4.0
Եթե պետք լինի հաշվել, օրինակ, \(f(x)=x^2-3x\) ֆունկցիայի ինտեգրալը, ապա սա նույնպես պետք է սահմանել
(defun f (x) (- (* x x) (* x 3)))
ապա integral ֆունկցիան կիրառել այս f ֆունկցիայի նկատմամբ։ Բայց անանուն ֆունկցիաների մեխանիզմը հնարավորություն է տալիս խուսափել ինտեգրվող ֆունկցիայի առանձին սահմանումից։ Օրինակ, այս վեջին ֆունկցիան \([-2;1]\) միջակայքում ինտեգրելու համար կարելի է գրել.
(integral #'(lambda (x) (- (* x x) (* x 3))) -2 1)
Այստեղ integral ֆունկցիայի կանչի մեջ lambda մակրոսով ստեղծվել է ինտեգրվող ֆունկցիային համապատասխան անանուն ֆունկցիա։
C++11 լեզվում նույնպես կարելի է գրել համարժեք արտահայտություն.
integral([](double x)->double{ return x*x-3*x;}, -2, 1);
որտեղ անանուն ֆունկցիան սահմանված C++11 լեզվի []()->{} կառուցվածքով։

Բայց սեղանների մեթոդը ինտեգրալի հաշվման միակ մեթոդը չէ։ Օրինակ, \(f\) ֆունկցիան \([a;b]\) հատվածի վրա կարելի է մոտարկել ոչ թե ուղիղ գծով, այլ պարաբոլով։ Այս մեթոդը կոչվում է Սիմպսոնի մեթոդ և ներկայանում է հետևյալ բանաձևով. \[ \mathrm{simpson}(f, a, b)=\frac{b-a}{6}\left(f(a)+4f\Big(\frac{a+b}{2}\Big)+f(b)\right) \] Եվ ինտեգրալի հաշվման թվային մեթոդը նույնպես կարելի է տալ integral ֆունկցիային որպես արգումենտ։ Այդ դեպքում կստանանք մի նոր, երրորդ կարգի ֆունկցիա. \[ \mathrm{integral}(method, f, a, b, \varepsilon)= \left\{ \begin{array}{ll} method(f, a, b), & |b - a|\le\varepsilon, \\ \mathrm{integral}(f, a, \frac{a+b}{2}, \varepsilon) + \mathrm{integral}(f, \frac{a+b}{2}, b, \varepsilon), & |b - a|\gt\varepsilon.\\ \end{array} \right. \] Ծրագրավորենք այս ֆունկցիան Common Lisp լեզվով.
(defun integral (method f a b &optional (eps 0.001))
  (if (< (- b a) eps)
      (funcall method f a b)
      (let ((m (/ (+ a b) 2)))
        (+ (integral method f a m eps) 
           (integral method f m b eps)))))
Եվ C++11 լեզվով։
using method = std::function<double(mathfunc,double,double)>>;

double integral( method r, mathfunc f, double a, double b, double delta = 0.001 )
{
  if( b - a < delta )
    return r(f, a, b);

  auto m((a + b) / 2);
  return integral(r, f, a, m, delta) + integral(r, f, m, b, delta);
}