Source Code for Module jazzparser.formalisms.music_halfspan.harmstruct

  1  """Harmonic structure from semantics. 
  2   
  3  Functions for converting a logical form to trees representing the harmonic  
  4  structure. This is a list of trees of the dependencies in the logical form. 
  5   
  6  """ 
  7  """ 
  8  ============================== License ======================================== 
  9   Copyright (C) 2008, 2010-12 University of Edinburgh, Mark Granroth-Wilding 
 10    
 11   This file is part of The Jazz Parser. 
 12    
 13   The Jazz Parser is free software: you can redistribute it and/or modify 
 14   it under the terms of the GNU General Public License as published by 
 15   the Free Software Foundation, either version 3 of the License, or 
 16   (at your option) any later version. 
 17    
 18   The Jazz Parser is distributed in the hope that it will be useful, 
 19   but WITHOUT ANY WARRANTY; without even the implied warranty of 
 20   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the 
 21   GNU General Public License for more details. 
 22    
 23   You should have received a copy of the GNU General Public License 
 24   along with The Jazz Parser.  If not, see <http://www.gnu.org/licenses/>. 
 25   
 26  ============================ End license ====================================== 
 27   
 28  """ 
 29  __author__ = "Mark Granroth-Wilding <mark.granroth-wilding@ed.ac.uk>"  
 30   
 31  from .semantics import Semantics, List, EnharmonicCoordinate, \ 
 32              FunctionApplication, Predicate, Coordination, Variable, \ 
 33              LambdaAbstraction, Now 
 34  from jazzparser.misc.tree import ImmutableTree, Node 
 35  from jazzparser.data.dependencies import DependencyGraph 
 36   
 37 -def semantics_to_dependency_trees(sems): 
 38      """ 
 39      Converts the given Semantics (logical form) to a tree representation  
 40      of the dependencies in it. 
 41       
 42      """ 
 43      if not isinstance(sems, Semantics): 
 44          raise SemanticsToTreesError, "input must be a Semantics" 
 45      if not isinstance(sems.lf, List): 
 46          raise SemanticsToTreesError, "top level of semantics must be a List" 
 47       
 48      trees = [] 
 49      # Process each lf in the list individually 
 50      for lf in sems.lf: 
 51          root = lf_to_depedency_tree(lf) 
 52          tree = ImmutableTree(root) 
 53          trees.append(tree) 
 54       
 55      return trees 
 56   
 57 -def lf_to_depedency_tree(lf, bound_var=None): 
 58      if type(lf) is EnharmonicCoordinate: 
 59          # Base case: a final resolution, root of the tree 
 60          return Node(lf.zero_coord) 
 61      elif type(lf) is FunctionApplication: 
 62          # Recurse to get the tree for the argument first 
 63          arg_tree = lf_to_depedency_tree(lf.argument, bound_var=bound_var) 
 64           
 65          if isinstance(lf.functor, Predicate): 
 66              if type(lf.functor) is Now: 
 67                  # Exclude this from the trees 
 68                  return arg_tree 
 69              # Predicate becomes a node label 
 70              leaf = Node(lf.functor.name) 
 71              arg_tree.leftmost_leaf().children.append(leaf) 
 72              return arg_tree 
 73          elif type(lf.functor) is Coordination: 
 74              # Coordination does the interesting stuff 
 75              trees = [] 
 76              for cadence in lf.functor: 
 77                  # Each cadence should be a function 
 78                  if type(cadence) is not LambdaAbstraction: 
 79                      raise SemanticsToTreesError, "invalid cadence: %s" % cadence 
 80                  var = cadence.variable 
 81                  # Get a tree for the cadence 
 82                  # Request that its variable be returned as the root 
 83                  tree = lf_to_depedency_tree(cadence.expression, bound_var=var) 
 84                  # The root node should be that corresponding to the bound variable 
 85                  # We can throw that away and take its subtree 
 86                  trees.append(tree[0]) 
 87              # Connect these trees up with the argument's tree 
 88              arg_tree.leftmost_leaf().children = trees 
 89              return arg_tree 
 90          else: 
 91              raise SemanticsToTreesError, "unknown functor: %s (%s)" % \ 
 92                      (lf.functor, type(lf).__name__) 
 93      elif type(lf) is Variable: 
 94          # Check it's the right variable 
 95          if lf != bound_var: 
 96              raise SemanticsToTreesError, "got unbound variable '%s'. Bound "\ 
 97                  "variable was '%s'" % (lf, bound_var) 
 98          # Return this as the root of the (sub)tree 
 99          return Node("var") 
100      else: 
101          raise SemanticsToTreesError, "unhandled lf type: %s (%s)" % \ 
102                  (lf, type(lf).__name__) 
103                   
104   
105 -def semantics_to_dependency_graph(sems): 
106      """ 
107      Converts the semantics to a L{jazzparser.data.dependencies.DependencyGraph}  
108      of the dependencies in it. Returns this graph and a mapping from the  
109      indices of the graph to the timings in the semantics. 
110       
111      """ 
112      if not isinstance(sems, Semantics): 
113          raise SemanticsToDependenciesError, "input must be a Semantics. "\ 
114              "Got: %s" % type(sems).__name__ 
115      if not isinstance(sems.lf, List): 
116          raise SemanticsToDependenciesError, "top level of semantics must be a "\ 
117              "List. Got '%s'" % type(sems.lf).__name__ 
118       
119      all_arcs = [] 
120      next_index = 1 
121      time_mapping = {} 
122      # Process each lf in the list individually 
123      root_arcs = [] 
124      for lf in sems.lf: 
125          # Get the arcs for this part of the graph 
126          arcs,node_times,__,root_arc = lf_to_depedency_arcs(lf) 
127           
128          # It's possible to end up with nodes occurring at the same time 
129          #  from this. These should be merged and arcs between them removed 
130          time_nodes = {} 
131          rename = {} 
132          for node,time in node_times.items(): 
133              if time in time_nodes: 
134                  rename[node] = time_nodes[time] 
135              else: 
136                  time_nodes[time] = node 
137          arcs = [(rename.get(source, source), rename.get(target, target), label) \ 
138                  for (source,target,label) in arcs] 
139          # Get rid of the arcs between them 
140          arcs = [(s,t,l) for (s,t,l) in arcs if s != t] 
141          for node in rename: 
142              del node_times[node] 
143           
144          # The nodes are arbitrarily ordered: reorder according to times 
145          arcs,node_times,root_arc = \ 
146                      _reorder_nodes(arcs, node_times, root_arc, shift=next_index) 
147          all_arcs.extend(arcs) 
148          root_arcs.append(root_arc) 
149          time_mapping.update(node_times) 
150           
151          # Take the last numbered node in this graph so we know where to  
152          #  start numbering the next 
153          next_index += len(node_times) 
154       
155      # Add a root node and make all the tonic arcs point to it 
156      for (source, label) in root_arcs: 
157          all_arcs.append((source,0,label)) 
158       
159      return DependencyGraph(all_arcs), time_mapping 
160   
161 -def _reorder_nodes(arcs, node_times, root_arc, shift=0): 
162      # Sort by the times and enumerate in that order to key new node indices 
163      ordering = list(enumerate(sorted(node_times.items(), key=lambda x:x[1]))) 
164      # Shift all the indices on by a fixed amount 
165      ordering = [(i+shift, old) for (i,old) in ordering] 
166      # Construct a mapping from the old node labels to the new 
167      node_map = dict([(old_node,new_node) for (new_node,(old_node,time)) \ 
168                              in ordering]) 
169      new_node_times = dict([(new_node,time) for (new_node,(old_node,time)) \ 
170                              in ordering]) 
171      # Apply the mapping to the node indices in the arcs 
172      new_arcs = [(node_map[source], node_map[target], label) for \ 
173                              (source,target,label) in arcs] 
174      # Apply the mapping to the special root arc 
175      if root_arc is not None: 
176          root_arc = (node_map[root_arc[0]], root_arc[1]) 
177      return new_arcs,new_node_times,root_arc 
178       
179 -def lf_to_depedency_arcs(lf, start_index=0, bound_var=None): 
180      if type(lf) is EnharmonicCoordinate: 
181          # Base case: a final resolution 
182          # Add a node to the graph 
183          # Set the special arc to the root node to go from here 
184          return [], {start_index: lf.time}, start_index, (start_index, lf) 
185      elif type(lf) is FunctionApplication: 
186          # Recurse to get the arcs for the argument 
187          if type(lf.argument) is Variable: 
188              # We're applying to a variable 
189              # Assume it's the one that's been bound, create arcs pointing to  
190              #  the node that was associated with it 
191              if bound_var is None: 
192                  raise SemanticsToDependenciesError, "got unbound variable "\ 
193                      "'%s'" % lf 
194              arcs = [] 
195              node_times = {} 
196              arg_start_index = bound_var 
197              root_arc = None 
198          else: 
199              arcs,node_times,arg_start_index,root_arc = \ 
200                      lf_to_depedency_arcs(lf.argument,  
201                                           start_index=start_index, 
202                                           bound_var=bound_var) 
203          # Take indices greater than those used in the argument 
204          start_index += len(node_times) 
205           
206          if isinstance(lf.functor, Predicate): 
207              if type(lf.functor) is Now: 
208                  # Exclude this from the trees 
209                  return arcs,node_times,arg_start_index,root_arc 
210              # Predicate becomes a label on an arc going to the argument 
211              # Create a new node (implicitly) and add an arc to the arg 
212              arcs.append((start_index, arg_start_index, lf.functor.name)) 
213              node_times[start_index] = lf.functor.time 
214              outer_index = start_index 
215          elif type(lf.functor) is Coordination: 
216              # Coordination does the interesting stuff 
217              for i,cadence in enumerate(lf.functor): 
218                  # Each cadence should be a function 
219                  if type(cadence) is not LambdaAbstraction: 
220                      raise SemanticsToDependenciesError, "invalid cadence: %s" % cadence 
221                  # Get a tree for the cadence 
222                  # Give the index of the arg's start so the cad can resolve to it 
223                  cad_arcs,cad_times,cad_outer,__ = \ 
224                                  lf_to_depedency_arcs(cadence.expression,  
225                                                       start_index=start_index, 
226                                                       bound_var=arg_start_index) 
227                  # Increment the start index by the number of nodes that  
228                  #  were added by the cadence 
229                  start_index += len(cad_times) 
230                  # Add all the cadence's arcs 
231                  arcs.extend(cad_arcs) 
232                  # Merge in the timings for the cadence's nodes 
233                  node_times.update(cad_times) 
234                  # The node for the outermost element comes from the first cad 
235                  if i == 0: 
236                      outer_index = cad_outer 
237          else: 
238              raise SemanticsToTreesError, "unknown functor: %s (%s)" % \ 
239                      (lf.functor, type(lf).__name__) 
240           
241          return arcs,node_times,outer_index,root_arc 
242      elif type(lf) is Variable: 
243          raise SemanticsToDependenciesError, "variable '%s' was found on its "\ 
244              "own. It should have had something applied to it" % lf 
245      else: 
246          raise SemanticsToDependenciesError, "unhandled lf type: %s (%s)" % \ 
247                  (lf, type(lf).__name__) 
248                   
249   
250 -class SemanticsToTreesError(Exception): 
251      pass 
252   
253 -class SemanticsToDependenciesError(Exception): 
254      pass 
255