CSci532 Programming Languages and Paradigms: Homework 3 Solutions

Due date: Friday, November 07, 2008 in class
Each homework may have a different weight, which depends on its level of difficulty.
Absolutely no copying others' work

  1. Evaluate the semantics of these combinations of keystrokes 
         10 – 5 +/- M+ 6 × MR M+ =
    using the denotational definition of the calculator language.     (25%)
    Ans> 
    meaning[[10 – 5 +/- M+ 6 × MR M+ =]] = d 
   where perform[[10 – 5 +/- M+ 6 × MR M+ =]](0, nop, 0, 0) = (a, op, d, m)
    The evaluation proceeds as follows: 
      perform[[10 – 5 +/- M+ 6 × MR M+ =]]( 0, nop, 0, 0 )
= ( perform[[6 × MR M+ =]] º evaluate[[10 – 5 +/- M+]] )( 0, nop, 0, 0 )
= perform[[6 × MR M+ =]]( calculate[[M+]] º evaluate[[10 – 5 +/-]] )( 0, nop, 0, 0 )
= perform[[6 × MR M+ =]]( calculate[[M+]]( calculate[[+/-]] º
    evaluate[[10 – 5]] ) )( 0, nop, 0, 0 ) 
= perform[[6 × MR M+ =]]( calculate[[M+]]( calculate[[+/-]]( 
    evaluate[[5]] º compute[[–]] º evaluate[[10]] ) ) )( 0, nop, 0, 0 )
= perform[[6 × MR M+ =]]( calculate[[M+]]( calculate[[+/-]](
    evaluate[[5]]( compute[[–]]( evaluate[[10]] ( 0, nop, 0, 0 ) ) ) ) ) )
= perform[[6 × MR M+ =]]( calculate[[M+]]( calculate[[+/-]]( 
    evaluate[[5]]( compute[[–]]( 0, nop, 10, 0 ) ) ) ) )
= perform[[6 × MR M+ =]]( calculate[[M+]]( calculate[[+/-]]( 
    evaluate[[5]]( 10, minus, 10, 0 ) ) ) )
= perform[[6 × MR M+ =]]( calculate[[M+]]( calculate[[+/-]]( 10, minus, 5, 0 ) ) ) 
= perform[[6 × MR M+ =]]( calculate[[M+]]( 10, minus, -5, 0 ) ) 
= perform[[6 × MR M+ =]]( 10, nop, 15, 15 ) 
= evaluate[[6 × MR M+ =]]( 10, nop, 15, 15 ) 
= ( calculate[[=]] º evaluate[[6 × MR M+]] )( 10, nop, 15, 15 )
= calculate[[=]]( calculate[[M+]] º evaluate[[6 × MR]] )( 10, nop, 15, 15 )
= calculate[[=]]( calculate[[M+]]( evaluate[[MR]] º
    compute[[×]] º evaluate[[6]] ) )( 10, nop, 15, 15 ) 
= calculate[[=]]( calculate[[M+]]( evaluate[[MR]](
    compute[[×]]( evaluate[[6]]( 10, nop, 15, 15 ) ) ) ) )
= calculate[[=]]( calculate[[M+]]( evaluate[[MR]]( 
    compute[[×]]( 10, nop, 6, 15 ) ) ) )
= calculate[[=]]( calculate[[M+]]( evaluate[[MR]]( 6, times, 6, 15 ) ) ) 
= calculate[[=]]( calculate[[M+]]( 6, times, 15, 15 ) ) 
= calculate[[=]]( 6, nop, 90, 105 )  
= ( 6, nop, 90, 105 )
    Therefore meaning[[10 – 5 +/- M+ 6 × MR M+ =]] = 90.

  2. Add unary minuses to the integer arithmetic expressions and add its semantics to (a) the denotational semantics and (b) the operational semantics.     (30%)
    Ans>
    • Denotational semantics:
      • Syntax: Adding the item E ::= '–'E to the syntactic domains
      • Semantics: Adding the item E[['–'E]] = 0 – E[[E]] to the semantic functions

    • Operational semantics:
      • Syntax: Adding the item E ::= '–'E to the abstract syntax
      • Semantics: Adding the following two rules to the reduction rules;
        • '–'V ⇒ 0 – V
        •          E ⇒ E1         
           '–'E ⇒ '–'E1
  3. The operational semantics of identifiers was skipped in the discussion. Add the semantics of identifiers to the operational semantics of the sample language.     (15%)
    Ans> 
         <'a'|Env> ⇒ <a|Env>
     <'b'|Env> ⇒ <b|Env>
        …
     <'z'|Env> ⇒ <z|Env>

     <I 'a' | Env> ⇒ <I . a | Env>
     <I 'b' | Env> ⇒ <I . b | Env>
        …
     <I 'z' | Env> ⇒ <I . z | Env>
    where the symbol ‘.’ is the operation of string concatenation.

  4. Use the operational semantics of the sample language to reduce the following program to its environment:     (30%) 
       x := 0 – 4;
   if  x  then  x := x  else  x := 0 – x  fi;
   while  x  do  x := x – 2  od
    Ans> Let
      S0 = x ':=' '0' '–' '4',
      S1 = 'if' x 'then' x':='x 'else' x':='0'–'x 'fi', and
      S2 = 'while' x 'do' x ':=' x '–' '2' 'od'. 
       <S0; S1; S2 | Env0>
        <x ':=' '0' '–' '4' | Env0>
 ⇒ <x ':=' 0 '–' '4' | Env0>
 ⇒ <x ':=' 0 '–' 4 | Env0>
 ⇒ <x ':=' –4 | Env0>
 ⇒ Env0 & {x = –4} = {x = –4}
        <S0; S1; S2 | Env0>
 ⇒ <S1; S2 | {x=–4}>
        <'if' x 'then' x ':=' x 'else' x ':=' '0' '–' x 'fi' | {x = –4}>
 ⇒ <'if' –4 'then' x ':=' x 'else' x ':=' '0' '–' x 'fi' | {x = –4}>
 ⇒ <x ':=' '0' '–' x | {x = –4}>
 ⇒ <x ':=' 0 '–' x | {x = –4}> 
 ⇒ <x ':=' 0 '–' –4 | {x = –4}> 
 ⇒ <x ':=' 4 | {x = –4}>
 ⇒ {x = 4}
        <S1; S2 | {x = –4}> 
 ⇒ <S2 | {x = 4}>
        <'while' x 'do' x ':=' x '–' '2' 'od' | {x=4}>
        <x ':=' x '–' '2'  | {x = 4}>
 ⇒ <x ':=' 4 '–' '2'  | {x = 4}>
 ⇒ <x ':=' 4 '–' 2  | {x = 4}>
 ⇒ <x ':=' 2  | {x = 4}> 
 ⇒ {x = 2}
        <'while' x 'do' x ':=' x '–' '2' 'od' | {x=4}> 
 ⇒ <x ':=' x '–' '2'; 'while' x 'do' x ':=' x '–' '2' 'od' | {x=4}>
 ⇒ <'while' x 'do' x ':=' x '–' '2' 'od' | {x=2}>
        <x ':=' x '–' '2'  | {x = 2}>
 ⇒ <x ':=' 2 '–' '2'  | {x = 2}>
 ⇒ <x ':=' 2 '–' 2  | {x = 2}>
 ⇒ <x ':=' 0  | {x = 2}>
 ⇒ {x = 0}
        <'while' x 'do' x ':=' x '–' '2' 'od' | {x=2}> 
 ⇒ <x ':=' x '–' '2'; 'while' x 'do' x ':=' x '–' '2' 'od' | {x=2}>
 ⇒ <'while' x 'do' x ':=' x '–' '2' 'od' | {x=0}>
 ⇒ {x=0}
    The final environment is {x=0}.