Homework 2 (Abstract Syntax) Solution

Please follow carefully all of the following steps:

    1. Prepare a Haskell (or literate Haskell) file (ending in .hs or .lhs, respectively) that compiles without errors in GHCi. (Put all non-working parts in comments.)

    2. Submit one solution per group (each group can have up to 5 members) through Canvas.

Late submissions will not be accepted. Do not send solutions by email.



Exercise 1. Mini Logo


Mini Logo is an extremely simplified version of the Logo language for programming 2D graphics. The idea behind Logo and Mini Logo is to describe simple line graphics through commands to move a pen from one position to another. The pen can either be “up” or “down”. Positions are given by pairs of integers. Macros can be defined to reuse groups of commands. The syntax of Mini Logo is as follows (nonterminals are typeset in intalics, and terminals are typeset in typewriter font).

cmd
::=
pen mode

j
moveto (pos,pos)

j
def name ( pars ) cmd

j
call name ( vals )

j
cmd; cmd
mode
::=
up j down
pos
::=
num  j name
pars
::=
name, pars j name
vals
::=
num, vals j num

Note: Please remember that unspecified nonterminals, such as num and name, should be represented by corre-sponding predefined Haskell types, such as Int and String.

    (a) Define the abstract syntax for Mini Logo as a Haskell data type.

    (b) Write a Mini Logo macro vector that draws a line from a given position (x1,y1) to a given position (x2,y2) and represent the macro in abstract syntax, that is, as a Haskell data type value.

Note. What you should actually do is write a Mini Logo program that defines a vector macro. So the answer should have the following form.

def vector (...) ...

This is the textual representation in concrete syntax. Then you should write the same Mini Logo program in abstract syntax, that is, give a Haskell data type value in the following form (assuming Def is the constructor name representing the def production of the Haskell data type).

vector = Def "vector" ... ...

1

CS 381, Spring 2020, Homework 2
2


    (c) Define a Haskell function steps :: Int -> Cmd that constructs a Mini Logo program which draws a stair of n steps. Your solution should not use the macro vector.



(1,2)

(1,1)




(0,0)    (0,0)

Results of the Mini Logo programs produced by steps 1 and steps 3.

Exercise 2. Digital Circuit Design Language


Digital circuits can be built using the following four basic types of logical gates.


1


1

1


AND

0
OR

0








2


2

2







XOR    0    1    NOT

The “Digital Circuits Design Language” whose syntax is shown below can be used to describe circuits built from these gates.

circuit
::=
gates links
gates
::=
num:gateFn ; gates j ϵ
gateFn
::=
and j or j xor j not
links
::=
from num.num to num.num; links  j ϵ

Please note that logical gates as well as their input/output ports are identified by numbers. The inputs of a gate are numbered from top to bottom, starting from 1. The output is always numbered 0. Consider the following circuit, a half adder.








This circuit can be defined by the following DiCiDL program.

1:xor;

2:and;

from 1.1 to 2.1;

from 1.2 to 2.2;

    (a) Define the abstract syntax for the above language as a Haskell data type.

    (b) Represent the half adder circuit in abstract syntax, that is, as a Haskell data type value.

    (c) Define a Haskell function that implements a pretty printer for the abstract syntax.